# Double Auctions with Two-sided Bandit Feedback

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 13 Aug 2022.

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

- [Competing Bandits in Matching Markets](https://mlsanity.com/paper/1906.05363/) (2019)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Bandit Learning in Decentralized Matching Markets](https://mlsanity.com/paper/2012.07348/) (2020)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Beyond log2(T) Regret for Decentralized Bandits in Matching Markets](https://mlsanity.com/paper/2103.07501/) (2021)
- [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015)
- [Regret, stability & fairness in matching markets with bandit learners](https://mlsanity.com/paper/2102.06246/) (2021)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [Learning Theory and Algorithms for Revenue Optimization in Second-Price Auctions with Reserve](https://mlsanity.com/paper/1310.5665/) (2013)
- [Learning in Multi-Stage Decentralized Matching Markets](https://mlsanity.com/paper/2102.06988/) (2021)
- [Real-Time Optimisation for Online Learning in Auctions](https://mlsanity.com/paper/2010.10070/) (2020)

## Abstract (arXiv)

Double Auction enables decentralized transfer of goods between multiple buyers and sellers, thus underpinning functioning of many online marketplaces. Buyers and sellers compete in these markets through bidding, but do not often know their own valuation a-priori. As the allocation and pricing happens through bids, the profitability of participants, hence sustainability of such markets, depends crucially on learning respective valuations through repeated interactions. We initiate the study of Double Auction markets under bandit feedback on both buyers' and sellers' side. We show with confidence bound based bidding, and `Average Pricing' there is an efficient price discovery among the participants. In particular, the regret on combined valuation of the buyers and the sellers -- a.k.a. the social regret -- is O(log(T)/Delta) in T rounds, where Delta is the minimum price gap. Moreover, the buyers and sellers exchanging goods attain O(√T) regret, individually. The buyers and sellers who do not benefit from exchange in turn only experience O(logT/ Delta) regret individually in T rounds. We augment our upper bound by showing that ω(√T) individual regret, and ω(logT) social regret is unattainable in certain Double Auction markets. Our paper is the first to provide decentralized learning algorithms in a two-sided market where both sides have uncertain preference that need to be learned.