Online Market Equilibrium with Application to Fair Division

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 no envy, 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. • 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. 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 a measurable (possibly continuous) item space.