Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies bidding in the first pice auction with budget constraints. In this problem, there are n bidders/buyers and T rounds of auctions. In each round t, an item arrives and the bidders observe their value for the item and need to submit a bid for it. The paper studies if one can design a bidding policy that results in an online market equilibrium (OME). The authors present a pacing algorithm in which the submitted bid of a buyer is equal to the buyer's pacing factor and his/her bid. The pacing factor is then get updated over time. It is shown that under the pacing algorithm, the pacing factors, which are the dual variable of the budget constraints, converge. In addition,  the buyers' time-averaged utility converges to the optimal equilibrium utility and the buyers' time-averaged expenditure converges to the target budget range. 
main_review: The idea of pacing is based on the literature on online convex optimization and in particular online descent algorithms. This idea has been used in reference [7] of the paper for second-price auctions. 
 ([7] S. R. Balseiro and Y. Gur. Learning in repeated auctions with budgets: Regret minimization
and equilibrium. Management Science, 65(9):3952–3968, 2019.)
The authors did not cite and discuss [7] properly. Note that [7] has nice equilibrium results for stochastic and adversarial markets. At the high level [7] also designs a pacing algorithm in which the pacing factors (dual variables of budgets constraints) get updated over time. Hence, it is not clear if the current paper has a significant contribution. 

Another point is about presenting the results. At the end of the day, the authors solve bidding in the first pice auction with budget constraints. But, for some reason, the authors avoid discussing their problem in this form and this can cause confusion. In particular, the intro is not very to the point.

Finally, the paper may not be the best fit for this conference. EC  for example might be a better fit. 
limitations_and_societal_impact: see above
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: =Paper summary=
The authors study an online Fisher market. Unlike classic Fisher markets, here the items arrive one by one in an online fashion and must be immediately and irrevocably allocated to a set of static agents. The online market equilibrium notion introduced is a pair of sequences of (step-wise) allocations and prices, such that the market clears and the agents have no regret in hindsight. The authors present an algorithm for allocating the items, named PACE dynamics, with the property that the prices and the utilities converge to those of an equilibrium as the number of time steps goes to infinity. PACE is essentially the dual averaging algorithm on a regularized convex program that is the reformulation of the dual of the generalized Eisenberg-Gale convex program of Gao and Kroer [24]. Experiments on real datasets are also presented, showcasing that PACE converges fast in practice.

main_review: =Strengths - Weaknesses=

The paper is well-written, although it is a bit dense and notation-heavy at times. The topic is an interesting twist in a classic economics model that is well-motivated by modern applications. There is novelty in the model itself and the proposed dynamics is not just a direct application of dual averaging. Given other recent results in asymptotic online fair division (see below), a guarantee similar to that of Theorem 6 (and thus the ones of Theorems 3-5) is probably the best one could hope for. The paper is clearly technical and the authors did try to make the submission self contained in that respect. That being said, it is also a fact that this work relies a lot on the heavy machinery of Xiao [48] and Gao and Kroer [24]. Also, as all the proofs are in the supplementary material, I only read the proofs of Theorems 3, 4 and 5. 
While I have some concerns about NeurIPS being the right venue for this work (mostly in terms of presentation opf the content), this is a solid paper.

  
=Comments for authors= 

-- There is recent work on vanishing envy in online fair division that should be included and discussed. See, e.g., the following papers and the references therein:
* Gerdus Benade, Aleksandr M. Kazachkov, Ariel D. Procaccia, Christos-Alexandros Psomas: How to Make Envy Vanish Over Time. EC 2018: 593-610
* David Zeng, Alexandros Psomas: Fairness-Efficiency Tradeoffs in Dynamic Fair Division. EC 2020: 911-912

-- line 154, “The item must be allocated irrevocably to *one* buyer.”: While this is what eventually happens in PACE, my understanding is that this is not part of the description of the model. Please clarify. 

-- The $B_i$s were a constant source of confusion for me. In fact, things only got clear after reading the last supplementary section of the appendix. In particular, it is never stated explicitly in the main paper what the $B_i$ are. It is not even clear whether they are the total or the per-step budget of agent $i$, until fully understanding Definition 3. The informal discussion before Definition 3 talks about “per-period expenditure rate” but a “period” is never defined either. Also, I assumed that being the budget per step, there would be some kind of per step budget constraint and that the remaining budget of a step $t$ would be transferred to the budget of step $t+1$. Apparently this is not what happens, as $B_i$ is interpreted as a (very) soft constraint. Both this and a lower bound on $B_i$ should be discussed.

--In connection to a discussion about a lower bound on $B_i$, if I am not mistaken, currently there is no restriction on $B_i$ being a function of $t$, say $O(1/t)$, something that would completely break down the convergence bounds. So maybe it should be stated explicitly that $B_i$ is independent of the step and is something like $\Omega(1/n)$.

-- Is there a sufficiently small value for $\delta_0$? I did not find the comment in appendix B very clear. It seems like any $\delta_0 > 0$ should work.

-- line 262: the last term should be $\frac{1}{t} g^t$ (i.e., the overbar should be missing).

-- Maybe it would be useful to define the strong convexity modulus of a convex function.

-- line 342: “where … as in Theorem 6” can be removed as this is Theorem 6. 

-- line 355: I believe this should be $T=100n$.


=Questions to authors=

If possible, I would like to see a response to my 2nd, 4th, and 5th comments above.


------------ AFTER REBUTTAL ------------
I have read the other reviewers' comments and the authors' rebuttal. I appreciate the effort the authors put into this. My comments were addressed adequately and I remain positive about this submission.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper investigates the problem of finding market equilibrium in an online Fisher market. Different from the traditional static Fisher market, in the online setting the items arrive one by one following an unknown distribution. The algorithm needs to allocate the items in the same online fashion with the goal that the time-averaged allocation and utilities asymptotically converge to an online market equilibrium. The main result of this paper is a simple PACE algorithm that achieves this goal. The algorithm maintains a pacing variable for each buyer and at each step assigns the item to the buyer with the highest paced value, after which the pacing variables are updated accordingly. In the essence, this PACE algorithm is a version of the dual averaging algorithm applied to the dual of the EG convex program, and therefore enjoys many nice converging properties. The authors also discuss the implication of this PACE algorithm to the online fair division problem and extend it to the Fisher market with a continuum of items. Finally, experiments are conducted to show its quick convergence in practice.
main_review: This paper studies a very natural and well-motivated problem of online resource allocation and proposes a simple dynamic with nice converging properties. The results are strong, in the sense that the dynamic is simple and intuitive, and does not need to know the underlying item arriving distribution and can converge to a market equilibrium with fast converging time. The paper is also well-written, with clear intuition and explanation provided at each step.

The idea of the PACE dynamic is rather straightforward once its connection to the dual averaging dynamic is established. As a result, the converging proof is not particularly innovative. Although I understand it is also not trivial and a lot of details need to be taken care of to ensure the convergence of the time-averaged utilities, expenditure, allocation and realized prices to the equilibrium at the same time.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The submission considers a setting of static buyers and online arriving items from an i.i.d. distribution. Buyers have linear utilities for items and budget constraints that only have to be satisfied in expectation. 

The authors propose running a centralized first-price auction, together with a simple distributed algorithm for adaptively adjusting a pacing multiplier for the buyers’ bids. They show that after a sufficiently large number of rounds (polynomial in the number of buyers), their procedure converges to the static equilibrium outcome with all its nice properties.

main_review: Understanding distributed convergence to approximate equilibria in online settings is an important problem. I’m not very clear on how novel the current submission is compared to related work, e.g. on pacing equilibria.

[EDIT: The above concern has been mostly addressed by authors in rebuttal.]

I’m also pretty annoyed with the way the dependence on number of buyers is hidden. The introduction promises convergence rate O(log(t)/t), and claims that the method is appropriate for “internet-scale”. Then Theorem 3 has a quadratic dependence on \sigma, which is basically \kappa, which is basically the $n$. Theorems 4 and 5 has an additional factor called C, which is again \sigma^2 (so n^4 in total if I’m not mistaken). The guarantee of Theorem 6 has parameters \zeta and \delta which are “as in Theorem 6”…

I think that the paper would benefit from being written in a simpler setting with discrete items and much less notation.


limitations_and_societal_impact: N/A
review_title: null

Meta-review: I decided to accept the paper since it presents an interesting problem and provides a novel solution with a surprising connection to the dual averaging technique. 
In the final version, please make sure to clearly and explicitly discuss the bounds and their dependence on the problem parameters.

Decision: Accept (Poster)