# Online Market Equilibrium with Application to Fair Division

arXiv: https://arxiv.org/abs/2103.12936 · HTML: https://mlsanity.com/paper/2103.12936/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2021.

## Built on by (most cited first, 8 of 8)

- [Learning Fair Division from Bandit Feedback](https://mlsanity.com/paper/2311.09068/) (2023)
- [Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets](https://mlsanity.com/paper/2202.05881/) (2022)
- [Keep Everyone Happy: Online Fair Division of Numerous Items with Few Copies](https://mlsanity.com/paper/2408.12845/) (2024)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)
- [Online Parameter Identification of Generalized Non-cooperative Game](https://mlsanity.com/paper/2310.09511/) (2023)
- [Large-Scale Contextual Market Equilibrium Computation through Deep Learning](https://mlsanity.com/paper/2406.15459/) (2024)
- [Towards Model-Free Learning in Dynamic Population Games: An Application to Karma Economies](https://mlsanity.com/paper/2605.11042/) (2026)
- [Attribution Markets: A Fisher-Market Formulation for Fractional Credit Assignment Between Planned Tasks and Performed Actions](https://mlsanity.com/paper/2607.20694/) (2026)

## Abstract (arXiv)

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.