# Online Learning for Equilibrium Pricing in Markets under Incomplete Information

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 81 references that are in the map.
- First posted on arXiv 21 Mar 2023.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [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)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives](https://mlsanity.com/paper/1506.03374/) (2015)
- [On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient](https://mlsanity.com/paper/1803.06573/) (2018)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds](https://mlsanity.com/paper/1909.05499/) (2019)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (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)
- [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)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [No-Regret and Incentive-Compatible Online Learning](https://mlsanity.com/paper/2002.08837/) (2020)
- [An Improved Analysis of LP-based Control for Revenue Management](https://mlsanity.com/paper/2101.11092/) (2021)
- [Learning Economic Parameters from Revealed Preferences](https://mlsanity.com/paper/1407.7937/) (2014)
- [Opportunities for Price Manipulation by Aggregators in Electricity Markets](https://mlsanity.com/paper/1606.06510/) (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)
- [Distributed Mechanism Design for Multicast Transmission](https://mlsanity.com/paper/1803.08111/) (2018)
- [Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements](https://mlsanity.com/paper/2205.00825/) (2022)

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

- [Constrained Online Decision-Making: A Unified Framework](https://mlsanity.com/paper/2505.07101/) (2025)

## Abstract (arXiv)

The computation of equilibrium prices at which the supply of goods matches their demand typically relies on complete information on agents' private attributes, e.g., suppliers' cost functions, which are often unavailable in practice. Motivated by this practical consideration, we consider the problem of learning equilibrium prices over a horizon of T periods in the incomplete information setting wherein a market operator seeks to satisfy the customer demand for a commodity by purchasing it from competing suppliers with cost functions unknown to the operator. We first consider the setting when suppliers' cost functions are fixed and develop algorithms that, on three pertinent regret metrics, simultaneously achieve a regret of O(1) when the customer demand is constant over time, and O(√T) when the demand varies over time. In the setting when the suppliers' cost functions vary over time, we demonstrate that, in general, no online algorithm can achieve sublinear regret on all three metrics. Thus, we consider an augmented setting wherein the operator has access to hints/contexts that reflect the variation in the cost functions and propose an algorithm with sublinear regret in this augmented setting. Finally, we present numerical experiments that validate our results and discuss various model extensions.