# Learning and Collusion in Multi-unit Auctions

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 120 references that are in the map.
- First posted on arXiv 27 May 2023.

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

- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Stochastic Shortest Path with Adversarially Changing Costs](https://mlsanity.com/paper/2006.11561/) (2020)
- [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [Learning in repeated auctions](https://mlsanity.com/paper/2011.09365/) (2020)
- [Optimal Learning for Structured Bandits](https://mlsanity.com/paper/2007.07302/) (2020)
- [Incentive-aware Contextual Pricing with Non-parametric Market Noise](https://mlsanity.com/paper/1911.03508/) (2019)
- [The Price of Anarchy in Auctions](https://mlsanity.com/paper/1607.07684/) (2016)
- [Combinatorial Auctions via Posted Prices](https://mlsanity.com/paper/1411.4916/) (2014)
- [Efficiency Guarantees in Auctions with Budgets](https://mlsanity.com/paper/1304.7048/) (2013)
- [Mechanisms for Multi-Unit Auctions](https://mlsanity.com/paper/1401.3834/) (2014)
- [LP-based Approximation for Personalized Reserve Prices](https://mlsanity.com/paper/1905.01526/) (2019)
- [Walrasian Dynamics in Multi-unit Markets](https://mlsanity.com/paper/1712.08910/) (2017)
- [Reducing Inefficiency in Carbon Auctions with Imperfect Competition](https://mlsanity.com/paper/1912.06428/) (2019)
- [Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions](https://mlsanity.com/paper/2007.12653/) (2020)
- [Making Auctions Robust to Aftermarkets](https://mlsanity.com/paper/2107.05853/) (2021)
- [On the Efficiency of the Walrasian Mechanism](https://mlsanity.com/paper/1311.0924/) (2013)
- [The Invisible Hand of Dynamic Market Pricing](https://mlsanity.com/paper/1511.05646/) (2015)
- [Walrasian Pricing in Multi-unit Auctions](https://mlsanity.com/paper/1602.08719/) (2016)

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

- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Improved learning rates in multi-unit uniform price auctions](https://mlsanity.com/paper/2501.10181/) (2025)
- [Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization](https://mlsanity.com/paper/2510.19591/) (2025)
- [Online Learning for Dynamic Vickrey-Clarke-Groves Mechanism in Unknown Environments](https://mlsanity.com/paper/2506.19038/) (2025)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)

## Abstract (arXiv)

We consider repeated multi-unit auctions with uniform pricing, which are widely used in practice for allocating goods such as carbon licenses. In each round, K identical units of a good are sold to a group of buyers that have valuations with diminishing marginal returns. The buyers submit bids for the units, and then a price p is set per unit so that all the units are sold. We consider two variants of the auction, where the price is set to the K-th highest bid and (K+1)-st highest bid, respectively. We analyze the properties of this auction in both the offline and online settings. In the offline setting, we consider the problem that one player i is facing: given access to a data set that contains the bids submitted by competitors in past auctions, find a bid vector that maximizes player i's cumulative utility on the data set. We design a polynomial time algorithm for this problem, by showing it is equivalent to finding a maximum-weight path on a carefully constructed directed acyclic graph. In the online setting, the players run learning algorithms to update their bids as they participate in the auction over time. Based on our offline algorithm, we design efficient online learning algorithms for bidding. The algorithms have sublinear regret, under both full information and bandit feedback structures. We complement our online learning algorithms with regret lower bounds. Finally, we analyze the quality of the equilibria in the worst case through the lens of the core solution concept in the game among the bidders. We show that the (K+1)-st price format is susceptible to collusion among the bidders; meanwhile, the K-th price format does not have this issue.