Online Market Equilibrium with Application to Fair Division
Authors: Yuan Gao
Alex Peysakhovich
Christian Kroer
Venue: NeurIPS 2021 Poster (2021)
Keywords: market equilibrium
fair division
online optimization
mechanism design

Abstract: Computing market equilibria is a problem of both theoretical and applied interest. Much research to date focuses on the case of static Fisher markets with full information on buyers' utility functions and item supplies. Motivated by real-world markets, we consider an online setting: individuals have linear, additive utility functions; items arrive sequentially and must be allocated and priced irrevocably. We define the notion of an online market equilibrium in such a market as time-indexed allocations and prices which guarantee buyer optimality and market clearance in hindsight. We propose a simple, scalable and interpretable allocation and pricing dynamics termed as PACE. When items are drawn i.i.d. from an unknown distribution (with a possibly continuous support), we show that PACE leads to an online market equilibrium asymptotically. In particular, PACE ensures that buyers' time-averaged utilities converge to the equilibrium utilities w.r.t. a static market with item supplies being the unknown distribution and that buyers' time-averaged expenditures converge to their per-period budget. Hence, many desirable properties of market equilibrium-based fair division such as envy-freeness, Pareto optimality, and the proportional-share guarantee are also attained asymptotically in the online setting. Next, we extend the dynamics to handle quasilinear buyer utilities, which gives the first online algorithm for computing first-price pacing equilibria. Finally, numerical experiments on real and synthetic datasets show that the dynamics converges quickly under various metrics.

Online Market Equilibrium with Application to Fair Division
Yuan Gao Columbia University gao muo.yoanncollmii edu
Alex Peysakhovich Facebook AI Research alex, peys@gmail com
Christian Kroer Columbia University
chri Aaristian www.rroolumbia.ccoooomoooomm.... edu
Abstract
Computing market equilibria is a problem of both theoretical and applied interest. Much research to date focuses on the case of static Fisher markets with full infor- mation on buyers' utility functions and item supplies. Motivated by real-world markets, we consider functions; items arrive sequentially and must be allocated and priced irrevoca- bly. We define the notion of an online market equilibrium in such market as time-indexed allocations and prices which guarantee buyer optimality and market clearance in hindsight. We propose simple, scalable and interpretable allocation and pricing dynamics termed as PACE. When items are drawn i.i.d. from an un- known distribution (with possibly continuous support), show that PACE leads to an online market equilibrium asymptotically. In particular, PACE ensures that buyers' time-averaged utilities converge the equilibrium utilities w.r.t. static market with item supplies being the unknown distribution and that buyers' time- averaged expenditures converge their per-period budget. Hence, many desirable properties of market equilibrium-based fair division such as envy-freeness, Pareto optimality, and the proportional-saree guarantee also attained asymptotically in the online setting. Next, we extend the dynamics to handle quasilinear buyer utilities, which gives the first online algorithm for computing first-price pacing equilibria. Finally, numerical experiments on real and synthetic datasets show that the dynamics converges quickly under various metrics.
online setting: individuals have linear, additive utility
1 Introduction
A market is said to be in equilibrium when supply is equal to demand. Computing prices and allocations which constitute a market equilibrium (ME) has long been a topic of interest [17 20 28 31 38) [43] Most existing work focuses on the case of static markets. However, in this paper we consider the case online markets where items arrive sequentially. We consider the extension
of market equilibrium to this setting and provide market dynamics which quickly converge to an equilibrium the case of online Fisher markets.
In static Fisher markets there is a fixed supply of each item, individual preferences are linear, additive, and items divisible (or equivalently, randomization is allowed so individuals can purchase not just items but lotteries over items). In general, finding market equilibria a hard problem [4] 39 47]
However, in static linear Fisher markets, equilibrium prices and allocations can be computed via solving the Eisenberg-Gar Gale (EG) convex program 22 37].
We consider online extension of Fisher markets where buyers constantly present but items arrive one-at-a-time. Buyers' budgets are per-period and represent their respective 'bidding powers' instead of being binding constraints. We extend the definition of market equilibrium to the online setting: online equilibrium allocations and prices are time-indexed and, when averaged across time, form an equilibrium in a corresponding static Fisher market where item supplies are proportional
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to item arrival probabilities. Due to the stochastic nature of online Fisher markets, any online algorithm can only attain an online market equilibrium asymptotically. that is, the allocations and prices approximately satisfy the equilibrium conditions after running the algorithm for a long time.
We propose market dynamics that find these equilibria in an online fashion based the dual averaging algorithm applied to reformulation of the dual of the EG convex program. We refer to this mechanism as PACE (Pace According to Current Estimated utility). In PACE, each buyer is assigned a utility pacing multiplier at time 0. When an item arrives, the individual with the highest adjusted utility (its valuation times the multiplier) receives that item and pays a price equal to its adjusted utility. The pacing multipliers of all individuals are then adjusted according to closed-form rule which is given by the time average of the subgradient of the dual of the EG program. Intuitively. the pacing multipliers of those that did not receive the item go up while the receiver's 's' typically (but not always) goes down. We show that PACE yields item allocations and prices that satisfy various equilibrium properties asymptotically, for example no-regret and envy-freeness.
One important application of market equilibrium is fair allocation using the competitive equilibrium from equal incomes (CEEI) mechanism 112 46]. In CEEI, each individual is given an endowment of faux currency and reports her valuations for items; then, a market equilibrium is computed and the items are allocated accordingly. However, many fair division problems are online rather than static. These include the allocation of impressions content in certain recommender systems [4]] workers to shifts, donations to food banks [2]. scarce compute time to requestors [25] 22 40 or
blood donations to blood banks [32. Similarly, online advertising can also be thought of as the allocation of impressions to advertisers via a market though with a budget of real money rather than faux currency. In the static CEEI case with linear additive preferences, the resulting equilibrium outcomes (i.e. results of the EG program) have been described as "perfect justice" [3. In the online case, PACE achieves the same fair allocations as CEEI asymptotically. See Appendix [A] for more related work in the areas of (static and online) equilibrium computation and fair division.
We evaluate PACE experimentally in several market datasets. Convergence to good outcomes happens quickly in experiments. Taken together our results, we conclude that PACE is an attractive algorithm for both computing online market equilibria and online fair division.
Main contributions. We consider the problem of allocating and pricing sequentially arriving items to n buyers. This setting is termed as an online Fisher market. Given a sequence of item arrivals, we define an online market equilibrium the items' allocations and prices that, in hindsight, ensure buyer optimality and market clearance. We propose the PACE dynamics, which can be viewed as a nontrivial instantiation of the dual averaging algorithm a reformulation of the dual of the Eisenberg-Gard Gale convex program. Leveraging the convergence theory of dual averaging, we show that, when item arrivals are drawn from an (unknown) underlying distribution s, possibly over an infinite/continouus item space. PACE ensures the following.
The pacing multipliers generated by PACE converge to the static equilibrium utility prices. Here, "static" means w.r.t. an underlying static Fisher market.
Buyers' time-averaged utilities converge to the static equilibrium utilities.
Buyers' time-averaged expenditures converge to their respective budgets.
These convergences are all in mean square with rates O(log t)) ((logt)/tt and O(log t)2 /t), respectively, where the constants in these rates involve moderate polynomials of n. In this way, PACE generates allocations and prices that constitute particular, the allocations and prices ensure that the allocation is Pareto optimal, and buyers have no regret, no envy, and get at least their proportional share asymptoticallly We also extend PACE to the case of quasilinear buyer utilities, which yields the first online algorithm for computing first-price pacing equilibria. Finally, numerical experiments suggest that PACE converges much faster than its theoretical rates in terms of pacing multipliers, utilities and expenditures.
online market equilibrium in the limit. In
2 Static and Online Fisher Markets
Static Fisher markets and equilibria. We first introduce static Fisher markets and their equilibria. Following the recent work 24 $2], we consider measurable (possibly continuous) item space.

---

Below are the technical preliminaries for the subsequent online setting. They can be skimmed through and referred back to as needed.
From now on, we define [k] == (1,...,Ak }} for any E N = (0,1,2..... and R (R++, resp.) as the set of nonnegative (positive, resp.) real numbers. Let [AA] [0, 1} denote the indicator function of an event A.
(a) There are n buyers (individuals), each having a budget B; > 0.
(b) The item space is finite measure space (0,M, (z) with 0 < pu()) cc. From now on, T. (and I_ resp.) denote the set of (nonnegative, resp.) L functions on & for any p E [o] (including p o0). Below are some concrete special cases for illustration.
(i) Finite: θ = [m]. M = 2/ml = {A: S [m]} and ((A) = =a uufa) (all 2 subsets measurable and the measure is given by point mass each item).
(ii) I Lebesgue-measurabbe
14 is the Lebesgue measure on TR .M is the Lebesgue o-algebra and Ô is (Lehessue-Jmeeasrabhl subset of IRd with positive finite measure. For example, can be a compact subset of Rd with a nonempty interior.
(iii) Countably infinite: @ N and ((A) Eae p((a) for any A C N. where p(N) < 0. For example, p(a) can be the probability mass of Poisson distribution, in which case M, μ) is a probability space.
(c) The supplies of items is 8 E L i.e., item 0 E θ has supply s(0). Since O is compact, it is measurable with finite measure. For the finite case Q [m], we have (S1,-.-, 8m) Ry.
(d) The valuation of each buyer i on all items is es T i.e., buyer i has valuation (0) on item E O. For the finite case θ = [m]. we have U; = (wal.... Vim) E R..
(e) For buyer i, allocation of items æ4. L gives utility of
u(xx,) == (o,, x2)
2: (O))))(0))
where the angle brackets are based on the notation of applying bounded linear functional to vector U; in the Banach space L and the integral the usual Lebesgue integral. For the finite case + = [m]] we have 2; = (Til. Zim) E IRT and the utility is
un (x(.)) = (vi, xii) = Σ 3
VijTij.
the usual Euclidean vector inner product. We will use (L denote the aggregate allocation of items to all buyers, i.c., the concatenation of all buyers' allocations.
The prices items are modeled as p L1; in other words, the price of item 0 θ p(0). For the finite case θ = [m]. we have (Pi..... .Pm) E RT.
g For a measurable item subset C θ, let (A) = SA (f) (and similarly for and s), the U; undinduced measure of A. For the finite case θ = [m]. for any item subset A C [m]. 0; (A4 Σjea Vij (and similarly for p(A) and s(A)).
(h) Without loss of generality, we assume unit total budget [|]]| 1, unit total supply s(O) 1 and normalized buyer valuations (Vi, s) = 1. In other words, all items have total value of 1 for every buyer.
Given item prices p L2,, the demand of buyer i is set of uilitt- allocations given the prices and budget:
Definition 1.
Dx(p) = arg max (v,, xe E L (p, xz) S B.}.
The associated utility level U.(p) is defined as the value of (vi, 22) for any 24 D₂(p). Definition 2. A market equilibrium (ME) is an allocation-price pair (x",p" (Lę))" L such that the following holds.
(i) Supply feasibility: E, xx S
(ii) Buyer optimality: x D.(p") all i.
3

---

- (iii) Market clearance: ( E, x1) 0 (any item with positive price is fully allocated).
In the above definition and subsequently, all equations involving measurable functions are understood as "holding almost everywhere." For example, -; Σ means the (measurable) set {0 E E;;; (0) S x()) has the same measure θ. Given ME (x* (c",,"),, -p",, we often denote the (unique) equilibrium utilities as un = (vi; af).. For a finiteddimensional linear Fisher market, it well known that a ME can be computed via solving the EG convex program. Recently, (24) generalized this framework to handle the case of an infinite item space. More specifically, consider the following
(possibly infinit-dlimensiona)) convex programs.
sup Σ Bd log(us, 24) s.t. Σ x S =E(LT)"
Exi$s.
(PEG)
(p,s) - pe 1,4,,ERR
inf
-B
B, log Bi
s.t. p 2 8,0,, Vi.
(DEG)
The following theorem summarizes the results in [24 $3] regarding the above convex programs capturing market equilibria. As shown in that work, the above convex programs satisfy strong duality and their optimal solutions (which correspond to ME) can be characterized by the KKT optimality conditions. We slightly generalize the assumptions of [24] by allowing non-uniform item supplies instead of s(Ø) the results in [2 $3), can be found in the Appendix.
for all E e. For completeness, a proof, which is mainly based on the proofs of
Theorem 1. The following hold regarding (Pgc) and DDg
Both suprema are altained.
Given x* feasible (PEC) and (p", (8)) feasible to (Ec)) they are both optimal if and only if
the following holds: (i) ,->, xi}
(market clearance), (ii) (p" - -3 xx) = 0 (buyer
only receives items within its "winning set' {p² 3 v; (ii) and (v), xx) ui = B
(buyer gets its maximum possible utility from x²). In this case, (x",p") is a ME.
Conversely, for a ME (x*,p") ,p"), it holds that (i) x* is an optimal solution of (PEG) and (ii) (p". where 3 = BB/ (Vi, xT),, is an optimal solution of DEG
In the above theorem, 33 is known as buyer i's utility price, i.e., price per unit utility at equilibrium. As is well known, ME pp")," the allocations are
inline Pareto optimal,
inline envy-free (in a budget weighted sense, i.e., (1, BB)/BB 2 "V,,tt//B BB for all k + i), inline proportional (i.e., (u) 2 (v,, s) 1/n); see, e.g.. 24 Theorem 3].
Online Fisher markets and equilibria. We now consider a simple online variant of the Fisher market setting, referred to as an online Fisher market (OFM). There are n buyers, each with a valuation 0 E L!. Assume there are discrete time steps = 2, At each time step t, an item 6, arrives and each buyer i sees a value 2 (())). The item must be allocated irrevocably to one buyer. Each buyer i has budget B, > O representing her per-period expenditure rate.
Next, we introduce the notions of demand, utility level and online market equilibrium in an OFM. All of them are defined based on sequences of arrived items and their prices; they do not require any distributional assumption on the item arrivals.
Definition 3. Let the arrived items be (0-)re(t) An allocation (of arrived items) is (xr (tr)))))) (n]- where x. E [0, 1] is the fraction of the item 0, allocated buyer iP Let the prices of the arrived
1 'This assumption is similar to one made in the literature on budget management auctions, where each buyers has a per-period expenditure rate and the overall budget equal to the rate times the number of time periods. If a hard budget cap across all time periods is desired, then PACE and similar mechanisms may deplete some buyers' budgets close the end of the horizon 66 g
We allow fractional allocations in the detinition for more generality. As we will see, fractional allocation is not needed: PACE generates allocations and prices that satisfy the OME conditions asymptotically via assigning each arrived item to one buyer.

---

items be (0+)))=(()) The demand of each buyer (in hindsight) at time t is
DJ argmax max (=])e)
i Σ (0.)2T : OS 2 S1, Σ p (0+) - Bi
(1)
Let U, be the utility level associated with this demand, i.e., the maximum value in ①. An online market equilibrium (OME) is a pair of allocations (o) (x,1) and prices p" (07) such that the following holds.
(i) Total allocation does not exceed the unit amount of the item E, 20 S 1or all
(ii) Buyers' realized allocations are optimal in hindsight: (xī) E for all i.
(iii) Market clearance: Σ; x] 1 =fror T such that p" (0-) >
In words, Ü is the maximum possible (time-averaged) utility buyer could have attained via choosing from the arrived items (f)) in hindsight, subject to their respective posted prices (p" (0+)) and her current total budget t.,, with D being the set of such Ellity-maximizing (time-indexed) allocations subject to per-period item availability constraints. An OME is pair of allocations and prices that make buyers optimal in hindsight and market cleared.
Given an OFM, we define the associated underlying static Fisher market as having the same n buyers and an item space & with supply being the (unknown) distribution from which the arriving items 0, are drawn. To clarify the concepts of OFM and OME, consider some simple special cases.
Suppose all item arrivals .1...., Bg are known in advance. Then, the OFM is the same as static n x Fisher market with the same buyers and the items, each having a unit supply. Here, buyer i's valuation of item is Gür vs (0+). To compute an OME, it suffices to solve the classical (fiite-dimennionnll) Eisenberg- Gale convex program, that is, (PFG) with = (1)
8 = (1,...,1) 1) E TR. and x E T Let the static ME be (x" pp") E nxxx [R4 When each item 0, arrives, OME allocates fraction 2, of the item to each buyer and set its price as p.
Suppose the sequentially arriving items are drawn i.i.d. from known underlying distribution E I (which specifies random variable 0 ~ such that P A] ((A) for any measurable set C +) and all buyers' valuations v; are known. Suppose we have also computed static ME .p") (Definition [ of market with buyer valuations 1ú budgets B, and item supplies being the distribution s (the underlying static market). Then, when a new item 0, (which is drawn from the distribution s) arrives at time f, set its price p0 (0c) and allocate a fraction of (0.))(O0)) of it to each buyer (assume s(0,) > 0, i.e., only items with positive supplies can appear). Then, the time-averaged utility of each buyer is E ni (0:)) (0.). which converges to Ea-s [u; (0)x;(() (0) = Je v: (0())=z (0)d0 = un a.s. by to the Strong Law of Large Numbers. Since the online process is carried out using static equilibrium prices and allocations, the static ME properties (Definition 2 ensure the required OME properties hold asymptotically.
The above special cases require full knowledge of either the exact future item arrivals the un- derlying static market to attain an OME Next, we propose a simple, distributed dynamics which generates allocations and prices that satisfy the OME conditions asymptotically without requiring such knowledge (in particular, without knowledge of the distribution s).
3 The PACE Dynamics
In this section, introduce the PACE (Pacing According to Current Estimated utility) dynamics that prices and allocates sequentially arriving items via (i) maintaining a pacing multiplier for each buyer and (ii) simple, distributed updates (1] In $5. we will show that PACE is instantiation of dual averaging [48) a stochastic first-order method for regularized optimization, applied to a reformulation of (Dec)). In the PACE dynamics, each buyer maintains a pacing multiplier S% starting from an initial value 33 = 1 + 60 for some small on > 0 (e.g., dn 0.05). At time step i, the following events take place.
Paacing and pacing multipliers terminology in budget management in large-scale ad auctions
18 19
5

---

(a) An item 6g appears and each buyer i sees a value (x(6)) for the item.
(b) Each buyer bids their paced value ((te( for the item.
(c) The item is allocated to the highest bidder (the winner at t): i, = arg max, (0,) with ties broken arbitrarily. For concreteness, we always choose the lowest winning index, i.e.,
i = min arg max (..)
Then, the price of Og is set by the first-price rule
(0)) = max (0,) = 31 (0,)
and the winner it pays this price p0() for the item fz.
(d) Each buyer i gets utility
- = (0,)((i = it}.
In other words, the winner is gets va, (0,) and other buyers get zero. (c) Each buyer updates its cumulative average utility ut:
1 7
(f) Each buyer i updates their pacing multiplier +7+1 as follows:
+ -I(.,,,.(BB/a))) minfmax B. h4].
where 1 = B,/(1 5n) and h; = 1 1 do for some fixed do > 0 (e.g.. óo = 0.05).
As will be seen in $5. buyer i's equilibrium pacing multiplier (i.e., utility price) satisfies I; < Br < h; and her per-period utiliity uf corresponds to the ith component of stochastic subgradient of function on / in a reformulation of the convex program (DEG). on which we run dual averaging. Furthermore, the update rule for 8,+1 is such that, if the realized utilities ūt were the true static equilibrium utility for buyer i, then 3 would be the equilibrium multiplier. Note that PACE does not randomize (any randomness can only come from the market environment from which item arrivals are drawn) and assigns every item to a single buyer without splitting it.
The simplicity and distributed nature of PACE makes it desirable for large-scale practical use.
It can be run on arbitrary sequential item arrivals and only requires buyers' valuations (0,) on the arrived items (rather than all valuations v; over the potentially large item space). No parameter tuning is needed (in particular, no stepsize tuning as in many first-order optimization methods).
When run as a centralized allocation mechanism, PACE only needs to maintain O(n) scalars,
namely, B5. B, and ūे for all At time f, observes buyers' valuations v; (0.) of the item 6,, compute bids B3 (0.)), finds the winner i, set the price as the maximal bid 8 2; (0,) and allocates the item to the winner; finally, it updates n' and g++1 in (f) which takes O(n) time.
PACE can also be run among the buyers a decentralized manner, in which case each buyer only maintains two scalar values: the pacing multiplier B and tvme-averaged utility it When new item arrives, each buyer only performs a few simple arithmetic operations to create a bid F (0.), receives her utility (if she wins) and subsequently updates iž! and gt+1.
These make PACE suitable for Internet-scale online fair division and online Fisher market applications. In particular, it is very reminiscent of how Internet advertising auctions are run. There, similar auction-baut based system is used, with the pacing multiplier ensuring that each advertiser smooths out their budget expenditure across the many auctions. The primary difference between this and our setting is that (i) the auction can first-price or second-price and (ii) buyers usually have quasilinear utilities, that is, utility of the item minus the expenditure (price paid) 6 18) In C we extend PACE to quasilinear utilities, which provides a novel online algorithm for first-price pacing equilibrium computation [19].

---

Dual Averaging
In this section, we briefly recap the setup and general convergence results of dual averaging 35 48 which will be used in the analysis of PACE. First, we introduce some notation for this and the next section. Let ((+) denote the i'th unit basis vector in IR" and E IR" denote the vector of I's For 2,y E R" [r, v/ denotes the Cartesian product of intervals IT Wh] C R", All norms without a subscript are Euclidean 2-norms, unless otherwise stated.
Let V be closed, strongly convex function with domain dom V/ := {w E R": (w) < oo}. Here, we do employ any auxiliary regularizing function, since our problem has natural source of strong convexity (i.e., a strongly convex v) through the - B; log B3 terms in (DEc)- Let Z C R be an arbitrary sample space. For each z E Z, let f= be convex and subdiffernntiable function on dom V. Considers the following regularized convex optimization problem [48 $1.1]:
min (.f(w)) + V(w),,
t0
where the expectation is taken over probability distribution D on Z. We assume access to oracle that, given any Jt and t E dom V, returns a subgradient g¹ E (w). The dual averaging algorithm (DA) 48 Algorithm 1J, with a strongly convex Vi and auxiliary regularizer, is follows. First, set E arg min,.. (w) and go 0. Then, for each / = 1,2...., DA performs the following steps:
(1) Observe St and compute g¹ E @)(("").
(2) Update the average subgradient (the dual average) via g' - --- +1'0-
Compute the next iterate w arg min, (Ø" w) ((w).
The following convergence guarantee on DA is proved as part of the proof of Corollary 4 in [88
Theorem 2. Dual averaging generates iterates w such that
Ellw" -w"l" w²11 (6 + log l)G²
to²
where G2 is an upper bound on Ellg' t= 1,2,... and the strong convexity modulus of
When solving the stochastic optimization problem (2). in Theorem 2 we can set G² to be an upper bound on supwedom v Ellg: (w)ll? where 9: (w) is subgradient oracle mapping each (2, w) E Z x dom V subgradient and the expectation over z D and possible randomness of the subgradient oracle. We will shortly see that reformulation of PPG when cast into the form (2). exhibits stochastic subgradients that are exactly buyers' received utilities in each time step. Using Theorem 2 we can show that the sequence of pacing multipliers 3 generated by PACE converges to the underlying (equilibrium) utility prices 3 the static Fisher market.
5 Convergence Analysis of the PACE dynamics
We will now show that PACE correspond to running DA on the vector 8 of pacing multipliers for the buyers. To this end, we first reformulate (DEG) into (fiite-dimensional) convex program in in the form of
(max Bi00
min 9
Σ
B, log
s.l. E [B/(1 (1 66)1,,
where & >> 0 is an arbitrarily small constant. The bounds on ,3 do not change the optimal solution,
(B,1] 1) for each i. Detailed steps of the reformulation are given in Appendix B because 37 E (B,,
In order to run DA, we need to compute a subgradient of fo B + max; (.),(0) at any 0 e.
Following 24 {5], since fa a piecewise linear function, a subgradient
go == Ui. (t)) (f),
where i" = min arg max; (0),(0) is the winner (see, e.g., 10 Theorem 3.50J).
We can now show that the PACE dynamics corresponds to running DA
Here, (
- -, B, log 3r with dom v = [B/(1+ 6p), (1 + 1.. First, choose 3¹ = arg min = (1+ 6n) (i.e., 8 = + 6, for all i) and go = At each time step / = 1, 2..., given the current pacing multiplier 8¹, DA applied to ( unrolls the following steps.
7

---

An item Or arrives, having value vs (6.) for each buyer i. The function ft in DA is
fe. : |3 + max (0,)
The winner is it min arg max; (0t) and subgradient is g' uie, elt)) E (8)) Its ith entry is exactly the realized Single-perioon utility of individual at time t in PACE, that is, g. =
(O,) & xt.
Update the dual average (time-average) utilities): for each i, compute g' g' + 1 i.e.
g
9. (-1
2 (O,)((( :.)
Update the pacing multipliers:
g
arg min
(g' Bc log
The minimization problem is separable in each i and exhibits a simple and explicit solution which recovers step
f in PACE (where T uf):
B
B
arg min AE(B/((66)111))
{ot B, Bo Bi) + 87 (L6.)
As mentioned earlier, PACE does not require a stepsize parameter. This is because DA is stepsize-free given a strongly convex regularizer V, which is indeed the case in our reformulation in the above update step for o the directions of change
addition,
follows.
For a non-winner * 4,, we have uf = and hence of S at-1. This implies 35+1 2 3 In words, a non-winner's pacing multiplier weakly increases. The increase is strict if a 0, i.e., buyer i has already received a nonzero utility.
For the winner is, ūž may become greater than o in which case B,!! S In words, the winner's pacing multiplier may go up or down.
In order to analyze PACE, we assume v, (0) = 1, n E I. (normalized and a.e. -bounded valuations and that there is underlying item distribution - from which the item arrivals 0,, t = 2, drawn i.i.d Define the underlying static Fisher market one having the same n buyers (each with valuation v and budget B₁) and item supplies s. Denote the equilibrium utilities and utility prices w.r.t. the underlying static market as and 8*, respectively. We further assume that the valuations are i; E L (i.e., a.e--bounded on the item space). This is not restrictive: since an individual item has value (0) for each buyer i, should be finite value.
Convergence of pacing multipliers. After aligning PACE with DA, the convergence of the pacing multipliers 3r follows directly from Theorem 2 Theorem 3. PACE generates pacing multipliers 3 such that
Bl 13 < +6+ log G) t= 1,2,
to
min, B. where G max; (.: S max; ||vell a (1+6p]2-
In other words, we have mean-square convergence of 3 to 3" at a ((log rate. Since |[ = 1, we have min; B, < 1/n. Hence, (l1/n) and the constant in the bound is Q(n²). Whether such dependence on n can be improved via new analysis remains an interesting research question.
Convergence of utilities. We next show that the time-averaged utility a' (which equals to the dual average g') converges to the equilibrium utility vector u" of the underlying Fisher market. A key step in the proof is to bound the probability of projection in updating 3 that is, P[B./ ot $ 14, w:]].
"The a.e. bboundeddeess assumption is needed in subsequent convergence analysis. Since θ has finite measure, it holds that LF L4_ For finite item space e = [m.]. both are equal to IRT
'The distributional assumption on item arrivals (i.e., they are drawn i.i.d. from an unknown distribution s) is needed to establish asymptotic equilibrium properties of PACE. See Appendix B for an example that any algorithm yield arbitrarily suboptimal allocations without such distributional assumption.
8

---

Theorem 4. For each i, let e, : minsh; -5 - 1, > O be the minimum distance to the
pacing-maule multiplier interval. Let ||0|,x := max, || It holds that
[uill
( 11+ do
E(ab - ut)² v
+
E
2 Ex
Hence, letting C
(min, B. ((1|v) م0 /50) + (1 + 5o)²), we have
E u² u²1l S C. (6 + log(t + 1))G²
(1 1)o2
Note that C {2(")). Hence, in this and the next theorems, the constant in the bound is 32(n²*). which arises from and a O(min, B,) = (l.nn).
Convergence of expenditures. The expenditure of buyer i at time step t is bj In other words, only the winner i, spends a nonzero amount, which is its bid. Let - 1 bg be buyer i's average expenditure. Utilizing the above convergence results, we show mean-squared convergence of b' to B at an O(log 1)²/t) rate.
}.
Theorem 5. For each holds that
8 (87) u;) 2110:11
E (B) 2
Σ
B - 3212
For t 2 3 and the constant C' defined in Theorem we have
2G
|10 12 (log (log 1)2
E - B1
6(C + [|0+))0|13)) + (C + 61]u|13)) logt
to
2
PACE attains OME asymptotically. Next, we show that PACE attains OME asymptotically. i.e., it generates allocations and prices that make buyers no-regret and envy-free in the limit (these notions will be clarified shortly). Let x¹ == Ii i,} denote whether buyer i, is the winner (i.e., whether she allocated the item O, at time 1) Utilizing Theorems 4
and []] we can show that buyer i's regret, that is, the difference between the maximum possible utility in hindsight Ü, (Definition 3 and the realized utility ut. vanishes as f grows. The same holds for each buyer's envy. In other words, at large t, in hindsight, no buyer prefers another buyer's 's set of allocated items (up to vanishing error)
Theorem 6. Denote E la wi] A
|||||>> Ex=1 11- - -3 Let r max (ū - u/, }} be the regret of buyer at time t. Then, it holds that rf S e + 7t/ Br and E(r))² O (logtt) t)² /t). Furthermore, define the envy of buyer (w.Ft. all other buyers) at time t be p max; aty/ Bx - ut/ Br, where iii Ei (;(0)) )a% is buyer i's time-averaged utility given her own valuations and of buyer k's allocations. Denote of = (t=r1(0 33 (x)))) It holds that
B&b, 7i
1 ((( max kei
6(1 log (log 1)3 A 1 and E(n < |101 G2
p 5 B, +
to²
2
Hence, the envy p of buyer i vanishes in mean square, i.e., B(p))² O ((logt))/t)
In light of Definition 3 Theorem G shows that (x. ((.)))())x is approximately optimal for buyer i. Since PACE also ciears the market, we conclude that it attains OME asymptotically, Recall that theorem 4 ensures that buyers' पi converge to their static equilibrium utilities uf. Since the latter satisfy Pareto optimality and proportional share guarantee (u: B, for all i), are the time-averaged realized utilities in the limit. Together with Theorem we conclude that PACE achieves the said fairness and efficiency guarantees, namely, Pareto optimality, envy- -rey-freenes and proportional-shar guarantee, asymptotically.
'In a static market, given an allocation æ E IR _ the (maximum, budget-weighted) envy of buyer i toward others" bundles is pa(x) = max (e,, / B2 (v., 2///BB (see, e.g., [12 46).. It is well-known that pi (x*) 0 for all i at equilibrium, consequence of buyer optimality (Definition

---

Novs 1500, mn 1500 (Muc. Helat vn Errors]
Househrold, n 2876, in 50 (Max Reletive Errons]
Inf-Dam - 100, D- [0, MMa Reletive Errons)
6:5
0.5
11 - 1A0
[ -0 19
6.25
I|0 "Mo""l
IKB 60100""""000 II.
-- -
I11 8 NP NP"
0.3
[K -u Mi
[|0] u0 10
|100* -" 1v0
0:30
0.1
6.0
6.44
30008
0C993
3000
120000
120000
51530
115649
173550
250080
287500
2009
4093
6300
100M
Moviel 1500, 1500 LAve. Ballativn Erunn)
Householld, 2076, (No.. Beletive Emara)
InA.km zo 100, 9- [0, [0 LAoerage Relative Errons)
[[t Ihue
Bule
Ijnin [(5 Np uu
Illp- -pp--p00 ""p 11.01
I 1pp Nate
5.25
162
66
6.44
30008 00890
20000
120000
150300
51530 11564
173900
250086
287500
2000
1000
Figure 1: In all of our markets, iterates of the PACE dynamics quickly converges to their static equilibrium values both in the average case and the worst-off-buyer case. The horizontal line shows the fraction of u" achieved by the proportional share solution. The PACE utilities quickly outperform the proportional share utilities. Vertical lines indicate when t is multiple of 10n.
Experiments
We evaluate the PACE dynamics in several real and synthetic datasets, namely, Movielens, Household Items and an infiiitedimmnniioall market instance with item space Q = [0. 1] and v, being linear functions on [0, 1]. For the first two datasets, see [31] for more information and exploratory data analysis. For all datasets, we consider the CEEI (fair division) setting where B, = 1/n for all i. For 1500, 2876, 100, respectively), we run PACE for T = 10n
each dataset (with number of buyers time steps (iterations). More details on the experiments and additional plots displaying convergence of expenditures be found in Appendix [ Figure displays the mean values of the average and maximum relative errors of the pacing multipliers and time-averaged cumulative utilities over 10 repeated experiments with different seeds (relative errors of cumulative spending w.r.t. total budgets are plotted separately in Appendix D). The standard errors are also displayed as vertical bars but are very small and nearly invisible. Vertical dotted lines indicate 10n The figures do not show the initial iterates
= 1, 1,....,55 5n.
We that PACE converges very quickly numerically: within 10 epochs (10n time steps) average deviations in most quantities falls within 5% of the equilibrium quantity, with the worst case not far behind. An important point is that budget spend takes much longer converge than utility. This demonstrates an important practical difference for using PACE an allocation scenario where budgets are 'real money' (e.g. Internet ad impressions) compared to CEEI-like setting, where budgets are faux currency only used for fair division.
7 Conclusion
We introduced the concept of an online Fisher market and proposed the PACE dynamics. We showed that when items arrive sequentially and stochastically, PACE converges to equilibrium outcomes of the underlying market model. Furthermore, we showed that, as a consequence of this, PACE can be used in online fair division problems to generate an online allocation that, asymptotically, achieves the compelling fairness properties of CEEI.
Many questions remain for future research. We mostly focused on the case where budgets are faux currency and there are many open questions for adapting PACE to a real-money budget-management setting as well as more complicated nonlinear utility models. Another imperative question, especially for practitioners, is whether PACE guarantees some level of incentive-compatibliiy
10

---

References
[1] M. Aleksandrov and T. Walsh. Online fair division: A survey. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 13557-13562, 2020.
[2] M. Alcksandrov, H. Aziz, S. Gaspers, and T. Walsh. Online fair division: Analysing a food bank problem. arXiv preprint arXiv: /50.000070,000055
[3] C. Amsperger. Envy-freennee and distributive justice. Journal of Economic Surveys, 8(2): 155-186, 1994.
[4] Y. Azar, N. Buchbinder, and K. Jain. How to allocate goods in an online market? Algorithmica, 74(2):589-601, 2016.
[5] H. Aziz, S. Gaspers, S. Mackenzie, and T. Walsh. Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence, 227:71-92, 2015.
[6] Balseiro, Kim, M. Mahdian, and Mirrokni. Budget management strategies in repeated auctions. In Proceedings of the 26th International Conference on World Wide Web, pages 15-23, 2017.
[7] S. R. Balseiro and Y. Gur. Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9):3952-3968, 2019.
[8] R. Balseiro, O. Besbes, and G. Y. Weintraub. Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science, 61(4):864-884, 2015.
[9] M. H. Bateni, Y. Chen, D. Ciocan, and V. Mirrokni. Fair resource allocation in volatile marketplace. Available at SSRN 2789380, 2018.
[10] A. Beck. First-order methods in optimization, volume 25. SIAM, 2017.
[11] B. Birnbaum, N. R. Devanur, and L. Xiao. Distributed algorithms via gradient descent for fisher markets. In Proceedings of the 12th ACM conference on Electronic commerce, pages 127-136. ACM, 2011.
[12] E. Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 1196))1061111100 2011.
[13] I. Caragiannis, D. Kurokawa, H. Moulin, sonable fairness of maximum Nash welfare. In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 305 322. ACM, 2016.
Procaccia, N. Shah, and J. Wang. The unrea-
[14] X. Chen and S.-H. Teng. Spending is not easier than trading: on the computational equivalence of fisher and arrow-debreu equilibria. In International Symposium on Algorithms and Computation, pages 647-656. Springer, 2009.
[15] Y. K. Cheung, M. Hoefer, and P. Nakhe. Tracing equilibrium in dynamic markets via distributed adaptation. Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 1225-1233 2019.
[16] R. Cole and V. Gkatzelis. Approximating the Nash social welfare with indivisible items. SIAM Journal on Computing, 47(3):1211-1236, 2018
[17) R. Cole N. R. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. V. Vazirani, and S. Yazdanbod. Convex program duality, fisher markets, and Nash social welfare. 18th ACM Conference on Economics and Computation, EC 2017. Association for Computing Machinery, Inc, 2017.
[18] V. Conitzer, C. Kroer, E. Sodomka, and N. F. Stser-Moses. Multiplicative pacing equilibria in auction markets. In International Conference on Web and Internet Economics, 2018.
[19] V. Conitzer, C. Kroer, D. Panigrahi, O. Schrijvers, E. Sodomka, N. E. Stier-Moses, and C. Wilkens. Pacing equilibrium first-price auction markets. In Proceedings of the 2019 ACM Conference Economics and Computation. ACM, 2019.
11

---

[20] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing Nash equilibrium. SIAM Journal on Computing, 39(1):195-259) 2009.
[21] A. Dvoretzky, A. Wald, J. Wolfowitz, et al. Relations among certain ranges of vector measures. Pacific Journal of Mathematics, 1(1):59-74, 1951.
[22] E. Eisenberg and D. Gale, Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30(1):165-166, 1959.
[23] Y. Gao and C. Kroer. First-order methods for large-seale market equilibrium computation. In Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[24] Y. Gao and C. Kroer. Infinite-dimensional fisher markets and tractable fair division. arXiv preprint arXiv:2010.03025, 2021.
[25] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Nsdi, volume 11, pages 24-24, 2011.
[26] K. Goldberg, T. Roeder, D. Gupta, and C. Perkins. Eigentaste: A constant time collaborative filtering algorithm. information retrieval, 4(2):133-151, 2001.
[27] F. M. Harper and J. A. Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
[28] L. Kantorovich. Mathematics in economics: achievements, difficulties, perspectives. Technical report, Nobel Prize Committee, 1975.
[29] I. Kash, A. D. Procaccia, and N. Shah. No agent left behind: Dynamic fair division of multiple resources. Journal of Artificial Intelligence Research, 51:579-603, 2014.
[30] C. Kroer and A. Peysakhovich. Scalable fair division for "at most one' preferences. arXiv preprint arXiv: 1909,/0999,99 2019.
[31] C. Kroer, A. Peysakhovich, E. Sodomka, and N. E. Stier-Moses. Computing large market equilibria using abstractions. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 745-746, 2019.
[32] D. C. McElfresh, C. Kroer, S. Pupyrev, E. Sodomka, K. A. Sankararaman, Z. Chauvin, N. Dexter, and J. P. Dickerson. Matching algorithms for blood donation. In Proceedings of the 21st ACM Conference Economics and Computation, pages 463-464, 2020.
[33] R. Murray, C. Kroer, A. Peysakhovich, and P. Shah. Robust market equilibria with uncertain preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2192-2199, 2020.
[34] R. Murray, C. Kroer, A. Peysakhovich, and P. Shah. https:/rresearch. fb. bb.com/bblggg000000//oosstt market-equilibria- hww--hooootottt-- -uuerttan--uuerr-eeeee
Sep 2020.
[35] Y. Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221-259, 2009.
[36] Y. Nesterov and V. Shikhman. Computation of fisher-gale equilibrium by auction. Journal of the Operations Research Society of China, 6(3):349-38, 2018
[37] N. Nisan, T. Roughgarden, Tardos, and V. V. Vazirani, Algorithmic game theory. Cambridge University Press, 2007.
[38] A. Othman, T. Sandholm, and E. Budish. Finding approximate competitive equilibria: efficient and fair course allocation. In AAMAS, volume 10, pages 873-880, 2010.
[39] A. Othman, C. Papadimitriou, and A. Rubinstein. The complexity of fairness through equilib- rium. ACM Transactions on Economics and Computation (TEAC), 4(4):1-19, 2016.
12

---

[40] D. C. Parkes, A. D. Procaccia, and N. Shah. Beyond dominant resource fairness: Extensions, limitations, and indivisibilities.. ACM Transactions on Economics and Computation (TEAC), (1):1-22, 2015.
[41] A. Peysakhovich and C. Kroer. Fair division without disparate impact. Mechanism Design for Social Good, 2019.
[42] B. Plaut and T. Roughgarden. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 1432)10039-1088, 2020.
[43] H. Scarf et On the computation of equilibrium prices. Number 232. Cowles Foundation for Research in Economics at Yale University New Haven, CT, 1967.
[44] V. I. Shmyrev. An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics, 3(4):505, 2009.
[45] Sinclair, S. Banerjee, and C. L. Yu. Sequential fair allocation: Achieving the optimal envy-efficiency tradeoff curve. arXiv preprint arXiv:2105.05308. 2021.
[46] H. R. Varian et al. Equity, envy, and efficiency. Journal of Economic Theory, 91):633-91, 1974.
[47] V. V. Vazirani and M. Yannakakis. Market equilibrium under separable, piecewise-linear, concave utilities. Journal of the ACM (JACM), 58(3):1-25, 2011.
[48] L. Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11:2543-255 2596, 2010.
[49] L. Zhang. Proportional response dynamics in the fisher market. Theoretical Computer Science, 2222))22661226966 2011.
Checklist. We answered the questions as accurately as possible and believe that many of them do not apply our work. We are happy to elaborate further should there be any questions or concerns.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Yes.
(b) Did you describe the limitations of your work? Yes.
(c) Did you discuss any potential negative societal impacts of your work? N.A.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
Yes.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? Yes.
(b) Did you include complete proofs of all theoretical results? Yes.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? Yes.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? N.A.
(c) Did you report error bars (e.g.. with respect to the random seed after running experiments multiple times)? Yes.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? No. (N.A.)
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
13

---

(a) If your work uses existing assets, did you cite the creators? Yes.
(b) Did you mention the license of the assets? N.A.
(c) Did you include any new assets either in the supplemental material or as a URL? No.
(d) Did you discuss whether and how consent was obtained from people whose data you 're using/curating? Yes.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? No. (N.A.)
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? N.A.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? N.A.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? N.A.
14


Reviews:
[{"review_id": "qUBo5sbiPOM", "reviewer": "Reviewer_P1UM", "summary": "=Paper summary=\nThe 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "=Strengths - Weaknesses=\n\nThe 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. \nWhile 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.\n\n  \n=Comments for authors= \n\n-- 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:\n* Gerdus Benade, Aleksandr M. Kazachkov, Ariel D. Procaccia, Christos-Alexandros Psomas: How to Make Envy Vanish Over Time. EC 2018: 593-610\n* David Zeng, Alexandros Psomas: Fairness-Efficiency Tradeoffs in Dynamic Fair Division. EC 2020: 911-912\n\n-- 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. \n\n-- 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.\n\n--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)$.\n\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.\n\n-- line 262: the last term should be $\\frac{1}{t} g^t$ (i.e., the overbar should be missing).\n\n-- Maybe it would be useful to define the strong convexity modulus of a convex function.\n\n-- line 342: “where … as in Theorem 6” can be removed as this is Theorem 6. \n\n-- line 355: I believe this should be $T=100n$.\n\n\n=Questions to authors=\n\nIf possible, I would like to see a response to my 2nd, 4th, and 5th comments above.\n\n\n------------ AFTER REBUTTAL ------------\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6.5 hours"}, "extra_text": {}}, {"review_id": "QHIr4fm0K1L", "reviewer": "Reviewer_3dLo", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "JEQbvyB89k", "reviewer": "Reviewer_ZYd4", "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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n ([7] S. R. Balseiro and Y. Gur. Learning in repeated auctions with budgets: Regret minimization\nand equilibrium. Management Science, 65(9):3952–3968, 2019.)\nThe 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. \n\nAnother 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.\n\nFinally, the paper may not be the best fit for this conference. EC  for example might be a better fit. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "see above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "4PcKxx43y2G", "reviewer": "Reviewer_pkgu", "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. \n\nThe 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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n[EDIT: The above concern has been mostly addressed by authors in rebuttal.]\n\nI’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”…\n\nI think that the paper would benefit from being written in a simpler setting with discrete items and much less notation.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

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)