Online Market Equilibrium with Application to Fair Division
Year: 2022

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’ timeaveraged 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.

heading: 1 Introduction
text: 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 of 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 in 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 are divisible (or equivalently, randomization is allowed so individuals can purchase not just items but lotteries over items). In general, finding market equilibria is a hard problem [14, 39, 47]. However, in static linear Fisher markets, equilibrium prices and allocations can be computed via solving the Eisenberg-Gale (EG) convex program [22, 37].
We consider an online extension of Fisher markets where buyers are 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 (NeurIPS 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 on the dual averaging algorithm applied to a 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 a 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 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 [12, 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 to content in certain recommender systems [34], workers to shifts, donations to food banks [2], scarce compute time to requestors [25, 29, 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 as 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 on a reformulation of the dual of the Eisenberg-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/continuous 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. to 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)/t), O((log t)/t) 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 an online market equilibrium in the limit. In 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 asymptotically. 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.

heading: 2 Static and Online Fisher Markets
text: Static Fisher markets and equilibria. We first introduce static Fisher markets and their equilibria. Following the recent work [24, §2], we consider a 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, . . . , k} for any k ∈ N := {0, 1, 2, . . . } and R+ (R++, resp.) as the set of nonnegative (positive, resp.) real numbers. Let I{A} ∈ {0, 1} denote the indicator function of an event A.
(a) There are n buyers (individuals), each having a budget Bi > 0. (b) The item space is a finite measure space (Θ,M, µ) with 0 < µ(Θ) < ∞. From now on, Lp
(and Lp+, resp.) denote the set of (nonnegative, resp.) L p functions on Θ for any p ∈ [1,∞] (including p = ∞). Below are some concrete special cases for illustration.
(i) Finite: Θ = [m], M = 2[m] = {A : A ⊆ [m]} and µ(A) = ∑
a∈A µ(a) (all 2 m subsets
are measurable and the measure is given by a point mass on each item). (ii) Lebesgue-measurable: µ is the Lebesgue measure on Rd, M is the Lebesgue σ-algebra
and Θ is a (Lebesgue-)measurable subset of Rd with positive finite measure. For example, Θ can be a compact subset of Rd with a nonempty interior.
(iii) Countably infinite: Θ = N and µ(A) = ∑
a∈A µ(a) for any A ⊆ N, where µ(N) < 0. For example, µ(a) can be the probability mass of a Poisson distribution, in which case (N,M, µ) is a probability space.
(c) The supplies of items is s ∈ L∞+ , i.e., item θ ∈ Θ has supply s(θ). Since Θ is compact, it is measurable with a finite measure. For the finite case Θ = [m], we have s = (s1, . . . , sm) ∈ Rm+ .
(d) The valuation of each buyer i on all items is vi ∈ L1+, i.e., buyer i has valuation vi(θ) on item θ ∈ Θ. For the finite case Θ = [m], we have vi = (vi1, . . . , vim) ∈ Rm+ . (e) For buyer i, an allocation of items xi ∈ L∞+ gives a utility of
ui(xi) := ⟨vi, xi⟩ := ∫ Θ vi(θ)xi(θ)dθ,
where the angle brackets are based on the notation of applying a bounded linear functional xi to a vector vi in the Banach space L1 and the integral is the usual Lebesgue integral. For the finite case Θ = [m], we have xi = (xi1, . . . , xim) ∈ Rm+ and the utility is
ui(xi) = ⟨vi, xi⟩ = ∑ j vijxij ,
the usual Euclidean vector inner product. We will use x ∈ (L∞+ )n to denote the aggregate allocation of items to all buyers, i.e., the concatenation of all buyers’ allocations.
(f) The prices of items are modeled as p ∈ L1+; in other words, the price of item θ ∈ Θ is p(θ). For the finite case Θ = [m], we have p = (p1, . . . , pm) ∈ Rm+ .
(g) For a measurable item subset A ⊆ Θ, let vi(A) := ∫ A vi(θ)dθ (and similarly for p and s),
the vi-induced measure of A. For the finite case Θ = [m], for any item subset A ⊂ [m], vi(A) = ∑ j∈A vij (and similarly for p(A) and s(A)).
(h) Without loss of generality, we assume a unit total budget ∥B∥1 = 1, a unit total supply s(Θ) = 1 and normalized buyer valuations ⟨vi, s⟩ = 1. In other words, all items have a total value of 1 for every buyer.
Definition 1. Given item prices p ∈ L1+, the demand of buyer i is its set of utility-maximizing allocations given the prices and budget:
Di(p) := argmax{⟨vi, xi⟩ : xi ∈ L∞+ , ⟨p, xi⟩ ≤ Bi}.
The associated utility level Ûi(p) is defined as the value of ⟨vi, xi⟩ for any xi ∈ Di(p). Definition 2. A market equilibrium (ME) is an allocation-price pair (x∗, p∗) ∈ (L∞+ )n × L1+ such that the following holds.
(i) Supply feasibility: ∑
i x ∗ i ≤ s.
(ii) Buyer optimality: x∗i ∈ Di(p∗) for all i.
(iii) Market clearance: ⟨p∗, s− ∑
i x ∗ i ⟩ = 0 (any item with a positive price is fully allocated).
In the above definition and subsequently, all equations involving measurable functions are understood as “holding almost everywhere.” For example, ∑ i xi ≤ s means the (measurable) set {θ ∈ Θ :∑
i xi(θ) ≤ s(θ)} has the same measure as Θ. Given a ME (x∗, p∗), we often denote the (unique) equilibrium utilities as u∗i = ⟨vi, x∗i ⟩. For a finite-dimensional linear Fisher market, it is 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 infinite-dimensional) convex programs.
sup x∈(L∞+ )n ∑ i Bi log⟨vi, xi⟩ s.t. ∑ i xi ≤ s. (PEG)
inf p∈L1+, β∈Rn+
( ⟨p, s⟩ −
∑ i Bi log βi
) s.t. p ≥ βivi, ∀ i. (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 s instead of s(θ) = 1 for all θ ∈ Θ. For completeness, a proof, which is mainly based on the proofs of the results in [24, §3], can be found in the Appendix. Theorem 1. The following hold regarding (PEG) and (DEG).
• Both suprema are attained. • Given x∗ feasible to (PEG) and (p∗, β∗) feasible to (DEG), they are both optimal if and only if
the following holds: (i) ⟨p∗, s− ∑
i x ∗ i ⟩ = 0 (market clearance), (ii) ⟨p∗−β∗i vi, x∗i ⟩ = 0 (buyer
i only receives items within its ‘winning set’ {p∗ = β∗i vi}) (ii) and ⟨vi, x∗i ⟩ = u∗i := Bi/β∗i (buyer i gets its maximum possible utility from x∗i ). In this case, (x
∗, p∗) is a ME. • Conversely, for a ME (x∗, p∗), it holds that (i) x∗ is an optimal solution of (PEG) and (ii) (p∗, β∗), where β∗i := Bi/⟨vi, x∗i ⟩, is an optimal solution of (DEG).
In the above theorem, β∗i is known as buyer i’s utility price, i.e., price per unit utility at equilibrium. As is well known, in a ME (x∗, p∗), the allocations x∗ are
inline Pareto optimal, inline envy-free (in a budget weighted sense, i.e., ⟨vi, x∗i ⟩/Bi ≥ ⟨vi, x∗k⟩/Bk for all k ̸= i), inline proportional (i.e., ⟨vi, x∗i ⟩ ≥ ⟨vi, s⟩/n = 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 vi ∈ L1+. Assume there are discrete time steps t = 1, 2, . . . . At each time step t, an item θt arrives and each buyer i sees a value vi(θt). The item must be allocated irrevocably to one buyer. Each buyer i has a budget Bi > 0 representing her per-period expenditure rate. 1
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 (θτ )τ∈[t]. An allocation (of arrived items) is (xτi )(τ,i)∈[t]×[n], where xτi ∈ [0, 1] is the fraction of the item θτ allocated to buyer i.2 Let the prices of the arrived
1This assumption is similar to one made in the literature on budget management in 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 to the end of the horizon [6–8].
2We allow fractional allocations in the definition 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 (pτ (θτ ))τ∈[t]. The demand of each buyer i (in hindsight) at time t is
Dti = argmax (zτi )τ∈[t]
{ 1
t t∑ τ=1 vi(θτ )z τ i : 0 ≤ zτi ≤ 1, ∀ τ, 1 t t∑ τ=1 pτ (θτ )z τ i ≤ Bi
} . (1)
Let Û ti be the utility level associated with this demand, i.e., the maximum value in (1). An online market equilibrium (OME) is a pair of allocations (xτi )(τ,i)∈[t]×[n] and prices pτ (θτ ) such that the following holds.
(i) Total allocation does not exceed the unit amount of the item ∑
i x τ i ≤ 1 for all τ .
(ii) Buyers’ realized allocations are optimal in hindsight: (xτi )τ∈[t] ∈ Dti for all i. (iii) Market clearance: ∑ i x τ i = 1 for τ such that p τ (θτ ) > 0.
In words, Û ti is the maximum possible (time-averaged) utility buyer i could have attained via choosing from the arrived items (θτ )τ∈[t] in hindsight, subject to their respective posted prices (pτ (θτ ))τ∈[t] and her current total budget tBi, with Dti being the set of such utility-maximizing (time-indexed) allocations subject to per-period item availability constraints. An OME is a 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 s being the (unknown) distribution from which the arriving items θt are drawn. To clarify the concepts of OFM and OME, we consider some simple special cases.
• Suppose all item arrivals θ1, . . . , θt are known in advance. Then, the OFM is the same as a static n × t Fisher market with the same buyers and the t items, each having a unit supply. Here, buyer i’s valuation of item τ is viτ = vi(θτ ). To compute an OME, it suffices to solve the classical (finite-dimensional) Eisenberg-Gale convex program, that is, (PEG) with Θ = [t], s = (1, . . . , 1) ∈ Rt+ and x ∈ Rn×t+ . Let the static ME be (x∗, p∗) ∈ Rn×t+ ×Rt++. When each item θτ arrives, OME allocates a fraction x∗iτ of the item to each buyer i and set its price as p ∗ τ . • Suppose the sequentially arriving items are drawn i.i.d. from a known underlying distribution s ∈ L∞+ (which specifies a random variable θ ∼ s such that P[θ ∈ A] = s(A) for any measurable set A ⊆ Θ) and all buyers’ valuations vi are known. Suppose we have also computed a static ME (x∗, p∗) (Definition 2) of a market with buyer valuations vi, budgets Bi and item supplies being the distribution s (the underlying static market). Then, when a new item θt (which is drawn from the distribution s) arrives at time t, set its price as p∗(θt) and allocate a fraction x∗i (θt)/s(θt) of it to each buyer i (assume s(θt) > 0, i.e., only items with positive supplies can appear). Then, the time-averaged utility of each buyer i is 1t ∑t τ=1 vi(θt)x ∗ i (θt)/s(θt),
which converges to Eθ∼s[vi(θ)xi(θ)/s(θ)] = ∫ Θ vi(θ)x ∗ i (θ)dθ = u ∗ i 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 or the underlying 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).

heading: 3 The PACE Dynamics
text: In this section, we 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.3 In §5, we will show that PACE is an instantiation of dual averaging [48], a stochastic first-order method for regularized optimization, applied to a reformulation of (DEG). In the PACE dynamics, each buyer maintains a pacing multiplier βti , starting from an initial value β1i = 1 + δ0 for some small δ0 > 0 (e.g., δ0 = 0.05). At time step t, the following events take place.
3Pacing and pacing multipliers are terminology in budget management in large-scale ad auctions [18, 19].
(a) An item θt appears and each buyer i sees a value vi(θt) for the item. (b) Each buyer i bids their paced value βtivi(θt) for the item. (c) The item is allocated to the highest bidder (the winner at t): it = argmaxi β t ivi(θt), with ties
broken arbitrarily. For concreteness, we always choose the lowest winning index, i.e.,
it = min argmax i
βtivi(θt).
Then, the price of θt is set by the first-price rule
pt(θt) = max i βtivi(θt) = β t itvi(θt)
and the winner it pays this price pt(θt) for the item θt. (d) Each buyer i gets a utility
uti = vi(θt)I{i = it}. In other words, the winner it gets vit(θt) and other buyers get zero.
(e) Each buyer i updates its cumulative average utility ūti:
ūti = 1
t t∑ τ=1 uτi = t− 1 t ūt−1i + 1 t uti.
(f) Each buyer i updates their pacing multiplier βt+1i as follows:
βt+1i = Π[li,hi](Bi/ū t i) := min{max{li, Bi/ūti}, hi}.
where li = Bi/(1 + δ0) and hi = 1 + δ0 for some fixed δ0 > 0 (e.g., δ0 = 0.05).
As will be seen in §5, buyer i’s equilibrium pacing multiplier (i.e., utility price) satisfies li < β∗i < hi and her per-period utility uti corresponds to the ith component of a stochastic subgradient of a function on β in a reformulation of the convex program (DEG), on which we run dual averaging. Furthermore, the update rule for βt+1i is such that, if the realized utilities ū t i were the true static equilibrium utility for buyer i, then βt+1i 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 vi(θt) on the arrived items (rather than all valuations vi 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, βti , Bi and ū t i for all i. At time t, it observes buyers’ valuations vi(θt) of the item
θt, compute bids βtivi(θt), finds the winner it, set the price as the maximal bid β t it vit(θt) and
allocates the item to the winner; finally, it updates ūt and βt+1 as in (f), which takes O(n) time. • PACE can also be run among the buyers in a decentralized manner, in which case each buyer
only maintains two scalar values: the pacing multiplier βti and time-averaged utility ū t i. When a new item arrives, each buyer only performs a few simple arithmetic operations to create a bid βtivi(θt), receives her utility (if she wins) and subsequently updates ū t i and β t+1 i .
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, a similar auction-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 be first-price or second-price and (ii) buyers usually have quasilinear utilities, that is, utility of the item minus the expenditure (price paid) [6–8, 18]. In §C, we extend PACE to quasilinear utilities, which provides a novel online algorithm for first-price pacing equilibrium computation [19].

heading: 4 Dual Averaging
text: 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 e(i) denote the i’th unit basis vector in Rn and 1 ∈ Rn denote the vector of 1’s. For x, y ∈ Rn, [x, y] denotes the Cartesian product of intervals ∏n i=1[xk, yk] ⊆ Rn. All norms ∥ · ∥ without a subscript are Euclidean 2-norms, unless otherwise stated.
Let Ψ be a closed, strongly convex function with domain domΨ := {w ∈ Rn : Ψ(w) < ∞}. Here, we do not employ any auxiliary regularizing function, since our problem has a natural source of strong convexity (i.e., a strongly convex Ψ) through the −Bi log βi terms in (DEG). Let Z ⊆ Rd be an arbitrary sample space. For each z ∈ Z, let fz be a convex and subdifferentiable function on domΨ. Considers the following regularized convex optimization problem [48, §1.1]:
min w Efz(w) + Ψ(w), (2)
where the expectation is taken over a probability distribution D on Z. We assume access to an oracle that, given any ft and w ∈ domΨ, returns a subgradient gt ∈ ∂ft(w). The dual averaging algorithm (DA) [48, Algorithm 1], with a strongly convex Ψ and no auxiliary regularizer, is as follows. First, set w1 ∈ argminw Ψ(w) and ḡ0 = 0. Then, for each t = 1, 2, . . . , DA performs the following steps:
(1) Observe ft and compute gt ∈ ∂ft(wt). (2) Update the average subgradient (the dual average) via ḡt = t−1t ḡ t−1 + 1t ḡ t. (3) Compute the next iterate wt+1 = argminw{⟨ḡt, w⟩+Ψ(w)}.
The following convergence guarantee on DA is proved as part of the proof of Corollary 4 in [48]. Theorem 2. Dual averaging generates iterates wt such that
E∥wt − w∗∥2 ≤ (6 + log t)G 2
tσ2 ,
where G2 is an upper bound on E∥gt∥2, t = 1, 2, . . . and σ is the strong convexity modulus of Ψ.
When solving the stochastic optimization problem (2), in Theorem 2, we can set G2 to be an upper bound on supw∈domΨ E∥gz(w)∥2, where gz(w) is a subgradient oracle mapping each (z, w) ∈ Z × domΨ to a subgradient and the expectation is over z ∼ D and possible randomness of the subgradient oracle. We will shortly see that a reformulation of DEG, 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 βt generated by PACE converges to the underlying (equilibrium) utility prices β∗ of the static Fisher market.

heading: 5 Convergence Analysis of the PACE dynamics
text: We will now show that PACE correspond to running DA on the vector βt of pacing multipliers for the buyers. To this end, we first reformulate (DEG) into a (finite-dimensional) convex program in β in the form of (2):
min β
(〈 max
i βivi, s 〉 − ∑ i Bi log βi ) s.t. β ∈ [B/(1 + δ0), (1 + δ0)1], (3)
where δ0 > 0 is an arbitrarily small constant. The bounds on β do not change the optimal solution, because β∗i ∈ (Bi, 1) for each i. Detailed steps of the reformulation are given in Appendix B. In order to run DA, we need to compute a subgradient of fθ : β 7→ maxi βivi(θ) at any θ ∈ Θ. Following [24, §5], since fθ is a piecewise linear function, a subgradient is
gθ(β) := vi∗(θ)e (i∗) ∈ ∂fθ(β),
where i∗ = min argmaxi βivi(θ) is the winner (see, e.g., [10, Theorem 3.50]). We can now show that the PACE dynamics corresponds to running DA on (3). Here, Ψ(β) = − ∑
i Bi log βi with domΨ = [B/(1 + δ0), (1 + δ0)1]. First, choose β 1 = argminΨ = (1 + δ0)1
(i.e., β1i = 1 + δ0 for all i) and ḡ 0 = 0. At each time step t = 1, 2, . . . , given the current pacing multiplier βt, DA applied to (3) unrolls the following steps.
• An item θt arrives, having value vi(θt) for each buyer i. The function ft in DA is fθt : β 7→ max
i βivi(θt).
• The winner is it = min argmaxi β t ivi(θt) and a subgradient is g t = vitjte (it) ∈ ∂ft(βt). Its
ith entry is exactly the realized (single-period) utility of individual i at time t in PACE, that is, gti = vi(θt)I{i = it} = uti.
• Update the dual average (time-averaged utilities): for each i, compute ḡt = t−1t ḡ t−1 + 1t g t, i.e.,
ḡti = t− 1 t ḡt−1i + 1 t vi(θt)I{i = it}.
• Update the pacing multipliers:
βt+1 = argmin β∈[B/(1+δ0),(1+δ0)1]
{ ⟨ḡt, β⟩ −
∑ i Bi log βi
} .
The minimization problem is separable in each i and exhibits a simple and explicit solution which recovers step (f) in PACE (where ḡti = ū t i):
βt+1i = argmin βi∈[B/(1+δ0),1+δ0]
{ ḡtiβi −Bi log βi } ⇒ βt+1i = Π[Bi/(1+δ0),1+δ0] ( Bi ūti ) .
As mentioned earlier, PACE does not require a stepsize parameter. This is because DA is stepsize-free given a strongly convex regularizer Ψ, which is indeed the case in our reformulation (3). In addition, in the above update step for βt+1i , the directions of change are as follows.
• For a non-winner i ̸= it, we have uti = 0 and hence ūti ≤ ū t−1 i . This implies β t+1 i ≥ βti . In
words, a non-winner’s pacing multiplier weakly increases. The increase is strict if ūt−1i > 0, i.e., buyer i has already received a nonzero utility.
• For the winner it, ūtit may become greater than ḡ t−1 it , in which case βt+1it ≤ β t it
. In words, the winner’s pacing multiplier may go up or down.
In order to analyze PACE, we assume vi(Θ) = 1, vi ∈ L∞+ (normalized and a.e.-bounded valuations)4 and that there is an underlying item distribution s ∈ L∞+ from which the item arrivals θt, t = 1, 2, . . . are drawn i.i.d.5 Define the underlying static Fisher market as one having the same n buyers (each with valuation vi and budget Bi) and item supplies s. Denote the equilibrium utilities and utility prices w.r.t. the underlying static market as u∗ and β∗, respectively. We further assume that the valuations are vi ∈ L∞+ (i.e., a.e.-bounded on the item space). This is not restrictive: since an individual item θ has value vi(θ) for each buyer i, it should be a finite value.
Convergence of pacing multipliers. After aligning PACE with DA, the convergence of the pacing multipliers βt follows directly from Theorem 2. Theorem 3. PACE generates pacing multipliers βt such that
E∥βt − β∗∥2 ≤ (6 + log t)G 2
tσ2 , t = 1, 2, . . . ,
where G2 = maxi Eθ∼s[vi(θ)2] ≤ maxi ∥vi∥2∞, σ = mini Bi(1+δ0)2 .
In other words, we have mean-square convergence of βt to β∗ at a O((log t)/t) rate. Since ∥B∥1 = 1, we have mini Bi ≤ 1/n. Hence, σ = O(1/n) and the constant in the bound is Ω(n2). 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 ūt (which equals to the dual average ḡt) converges to the equilibrium utility vector u∗ of the underlying Fisher market. A key step in the proof is to bound the probability of a projection in updating βt+1i , that is, P[Bi/ū t i /∈ [li, ui]].
4The a.e.-boundedness assumption is needed in subsequent convergence analysis. Since Θ has a finite measure, it holds that L∞+ ⊆ L1+. For a finite item space Θ = [m], both are equal to Rm+ .
5The 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 can yield arbitrarily suboptimal allocations without such a distributional assumption.
Theorem 4. For each i, let ϵi := min{hi − β∗i , β∗i − li} > 0 be the minimum distance to the pacing-multiplier interval. Let ∥v∥∞ := maxi ∥vi∥∞. It holds that
E(ūti − u∗i )2 ≤ ( ∥vi∥2∞ ϵ2i + ( 1 + δ0 Bi )2) E(βt+1i − β ∗ i ) 2.
Hence, letting C = 1(mini Bi)2 ( (∥v∥∞/δ0)2 + (1 + δ0)2 ) , we have
E∥ūt − u∗∥2 ≤ C · (6 + log(t+ 1))G 2
(t+ 1)σ2 .
Note that C = Ω(n2). Hence, in this and the next theorems, the constant in the bound is Ω(n4), which arises from C and σ = O(mini Bi) = O(1/n).
Convergence of expenditures. The expenditure of buyer i at time step t is bti = βtivi(θt)I{i = iτ}. In other words, only the winner it spends a nonzero amount, which is its bid. Let b̄ti = 1 t ∑t τ=1 b τ i be buyer i’s average expenditure. Utilizing the above convergence results, we show mean-squared convergence of b̄t to B at an O((log t)2/t) rate. Theorem 5. For each i, it holds that
E(b̄ti −Bi) ≤ 2 [ (β∗i ) 2E(ḡti − u∗i )2 + 2∥vi∥2∞ 1
t t∑ τ=1 E(βτi − β∗i )2 ] .
For t ≥ 3 and the constant C defined in Theorem 4, we have
E∥b̄t −B∥2 ≤ 2G 2
tσ2
( 6(C + ∥v∥2∞) + (C + 6∥v∥2∞) log t+
∥v∥2∞ 2
(log t)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 xti := I{i = it} denote whether buyer it is the winner (i.e., whether she is allocated the item θt at time t) Utilizing Theorems 4 and 5, we can show that buyer i’s regret, that is, the difference between the maximum possible utility in hindsight Û ti (Definition 3) and the realized utility ūti, vanishes as t grows. The same holds for each buyer’s envy. In other words, at a large t, in hindsight, no buyer prefers another buyer’s set of allocated items (up to a vanishing error).6
Theorem 6. Denote ξti = |ūti − u∗i |, ∆ti = |b̄ti − Bi|, γt = ∥v∥∞
t ∑t τ=1 ∥βτ − β∗∥∞. Let rti :=
max{Û ti − ūti, 0} be the regret of buyer i at time t. Then, it holds that rti ≤ ξti + γt/Bi and E(rti) 2 = O ( (log t)2/t ) . Furthermore, define the envy of buyer i (w.r.t. all other buyers) at time t be ρti = maxk ū t ik/Bk − ūti/Bi, where ūtik = 1t ∑t τ=1 vi(θτ )x τ k is buyer i’s time-averaged utility given her own valuations and of buyer k’s allocations. Denote ηti = 1 t ∑t τ=1(p
∗(θt)− βτi vi(θt))xti. It holds that
ρti ≤ 1
Bi
( ξti +max
k ̸=i
∆tk + η t k
Bk
) and E(ηti) 2 ≤ ∥v∥ 2 ∞G 2
tσ2
( 6(1 + log t) + (log t)2
2
) .
Hence, the envy ρti of buyer i vanishes in mean square, i.e., E(ρ t i)
2 = O ( (log t)2/t ) .
In light of Definition 3, Theorem 6 shows that (xτi )(i,τ)∈[n]×[t] is approximately optimal for buyer i. Since PACE also clears the market, we conclude that it attains OME asymptotically. Recall that theorem 4 ensures that buyers’ ūti converge to their static equilibrium utilities u ∗ i . Since the latter satisfy Pareto optimality and proportional share guarantee (u∗i ≥ Bi for all i), so are the time-averaged realized utilities in the limit. Together with Theorem 6, we conclude that PACE achieves the said fairness and efficiency guarantees, namely, Pareto optimality, envy-freeness and proportional-share guarantee, asymptotically.
6In a static market, given an allocation x ∈ Rn×m+ , the (maximum, budget-weighted) envy of buyer i toward others’ bundles is ρi(x) = maxk⟨vi, xk⟩/Bk − ⟨vi, xi⟩/Bi (see, e.g., [12, 46]). It is well-known that ρi(x ∗) = 0 for all i at equilibrium, a consequence of buyer optimality (Definition 2).
0 30000 60000 90000 120000 150000
0.1
0.2
0.3
0.4
0.5
0.6
MovieLens, n = 1500, m = 1500 (Max Relative Errors)
||(uPS u * )/u * || ||( t * )/ * || ||(ut u * )/u * ||
0 57520 115040 172560 230080 287600 0.0
0.2
0.4
0.6
0.8
Household, n = 2876, m = 50 (Max Relative Errors)
||(uPS u * )/u * || ||( t * )/ * || ||(ut u * )/u * ||
0 2000 4000 6000 8000 10000 0.00
0.05
0.10
0.15
0.20
0.25
0.30
0.35
0.40 Inf-Dim n = 100, = [0, 1] (Max Relative Errors)
||(uPS u * )/u * || ||( t * )/ * || ||(ut u * )/u * ||
0 30000 60000 90000 120000 150000 0.00
0.05
0.10
0.15
0.20
0.25
0.30 MovieLens, n = 1500, m = 1500 (Ave. Relative Errors)
||(uPS u * )/u * ||1/n ||( t * )/ * ||1/n ||(ut u * )/u * ||1/n
0 57520 115040 172560 230080 287600 0.0
0.1
0.2
0.3
0.4
0.5
0.6 Household, n = 2876, m = 50 (Ave. Relative Errors)
||(uPS u * )/u * ||1/n ||( t * )/ * ||1/n ||(ut u * )/u * ||1/n
0 2000 4000 6000 8000 10000 0.00
0.05
0.10
0.15
0.20
Inf-Dim n = 100, = [0, 1] (Average Relative Errors)
||(uPS u * )/u * ||1/n ||( t * )/ * ||1/n ||(ut u * )/u * ||1/n
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 a multiple of 10n.

heading: 6 Experiments
text: We evaluate the PACE dynamics in several real and synthetic datasets, namely, MovieLens, Household Items and an infinite-dimensional market instance with item space Θ = [0, 1] and vi 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 Bi = 1/n for all i. For each dataset (with number of buyers n = 1500, 2876, 100, respectively), we run PACE for T = 10n time steps (iterations). More details on the experiments and additional plots displaying convergence of expenditures can be found in Appendix D. Figure 1 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 t = 10n The figures do not show the initial iterates t = 1, . . . , 5n.
We see 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 to converge than utility. This demonstrates an important practical difference for using PACE in an allocation scenario where budgets are ‘real money’ (e.g. Internet ad impressions) as compared to a CEEI-like setting, where budgets are faux currency only used for fair division.

heading: 7 Conclusion
text: 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-compatibility.

Review summaries:
=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. 

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. 

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. 

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.