# Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 76 references that are in the map.
- First posted on arXiv 27 Apr 2022.

## Builds on (most cited first, 29 of 29)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2002.10421/) (2020)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Simple and Fast Algorithm for Binary Integer and Online Linear Programming](https://mlsanity.com/paper/2003.02513/) (2020)
- [Regularized Online Allocation Problems: Fairness and Beyond](https://mlsanity.com/paper/2007.00514/) (2020)
- [Uniformly bounded regret in the multi-secretary problem](https://mlsanity.com/paper/1710.07719/) (2017)
- [Fair Dynamic Rationing](https://mlsanity.com/paper/2102.01240/) (2021)
- [Watch and Learn: Optimizing from Revealed Preferences Feedback](https://mlsanity.com/paper/1504.01033/) (2015)
- [Online Nash Social Welfare Maximization with Predictions](https://mlsanity.com/paper/2008.03564/) (2020)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [Online Convex Optimization with Perturbed Constraints](https://mlsanity.com/paper/1906.00049/) (2019)
- [Nash Social Welfare Approximation for Strategic Agents](https://mlsanity.com/paper/1607.01569/) (2016)
- [Learning Economic Parameters from Revealed Preferences](https://mlsanity.com/paper/1407.7937/) (2014)
- [Online Market Equilibrium with Application to Fair Division](https://mlsanity.com/paper/2103.12936/) (2021)
- [Beyond Worst-Case Analysis](https://mlsanity.com/paper/1806.09817/) (2018)
- [Convex Program Duality, Fisher Markets, and Nash Social Welfare](https://mlsanity.com/paper/1609.06654/) (2016)
- [Online Learning for Traffic Routing under Unknown Preferences](https://mlsanity.com/paper/2203.17150/) (2022)
- [Social welfare and profit maximization from revealed preferences](https://mlsanity.com/paper/1711.02211/) (2017)
- [Dynamics of Distributed Updating in Fisher Markets](https://mlsanity.com/paper/1806.04746/) (2018)
- [Online Resource Allocation under Partially Predictable Demand](https://mlsanity.com/paper/1810.00447/) (2018)
- [Fisher Markets with Linear Constraints: Equilibrium Properties and Efficient Distributed Algorithms](https://mlsanity.com/paper/2106.10412/) (2021)
- [Markets for Efficient Public Good Allocation with Social Distancing](https://mlsanity.com/paper/2005.10765/) (2020)

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

- [Online Learning for Equilibrium Pricing in Markets under Incomplete Information](https://mlsanity.com/paper/2303.11522/) (2023)
- [Large-Scale Contextual Market Equilibrium Computation through Deep Learning](https://mlsanity.com/paper/2406.15459/) (2024)

## Abstract (arXiv)

Fisher markets are one of the most fundamental models for resource allocation. However, the problem of computing equilibrium prices in Fisher markets typically relies on complete knowledge of users' budgets and utility functions and requires transactions to happen in a static market where all users are present simultaneously. Motivated by these practical considerations, we study an online variant of Fisher markets, wherein users with privately known utility and budget parameters, drawn i.i.d. from a distribution, arrive sequentially. In this setting, we first study the limitations of static pricing algorithms, which set uniform prices for all users, along two performance metrics: (i) regret, i.e., the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an oracle with complete information, and (ii) capacity violations, i.e., the over-consumption of goods relative to their capacities. Given the limitations of static pricing, we design adaptive posted-pricing algorithms, one with knowledge of the distribution of users' budget and utility parameters and another that adjusts prices solely based on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees. Finally, we present numerical experiments to compare our revealed preference algorithm's performance to several benchmarks.