# Learning in Repeated Multi-Unit Pay-As-Bid Auctions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 115 references that are in the map.
- First posted on arXiv 27 Jul 2023.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [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)
- [Learning Simple Auctions](https://mlsanity.com/paper/1604.03171/) (2016)
- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017)
- [Learning Theory and Algorithms for Revenue Optimization in Second-Price Auctions with Reserve](https://mlsanity.com/paper/1310.5665/) (2013)
- [Optimal Learning for Structured Bandits](https://mlsanity.com/paper/2007.07302/) (2020)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [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)
- [Learning Product Rankings Robust to Fake Users](https://mlsanity.com/paper/2009.05138/) (2020)
- [Learning Optimal Reserve Price against Non-myopic Bidders](https://mlsanity.com/paper/1804.11060/) (2018)
- [Non-Stationary Bandits with Auto-Regressive Temporal Dependency](https://mlsanity.com/paper/2210.16386/) (2022)
- [Learning and Efficiency in Games with Dynamic Population](https://mlsanity.com/paper/1505.00391/) (2015)
- [Correlated and Coarse equilibria of Single-item auctions](https://mlsanity.com/paper/1601.07702/) (2016)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Learning to bid in revenue-maximizing auctions](https://mlsanity.com/paper/1902.10427/) (2019)
- [Online Resource Allocation with Convex-set Machine-Learned Advice](https://mlsanity.com/paper/2306.12282/) (2023)
- [Online Second Price Auction with Semi-bandit Feedback Under the Non-Stationary Setting](https://mlsanity.com/paper/1911.05949/) (2019)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Dynamic Reserve Prices for Repeated Auctions: Learning from Bids](https://mlsanity.com/paper/2002.07331/) (2020)
- [On the Inefficiency of Standard Multi-Unit Auctions](https://mlsanity.com/paper/1303.1646/) (2013)

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

- [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)

## Abstract (arXiv)

Motivated by Carbon Emissions Trading Schemes, Treasury Auctions, Procurement Auctions, and Wholesale Electricity Markets, which all involve the auctioning of homogeneous multiple units, we consider the problem of learning how to bid in repeated multi-unit pay-as-bid auctions. In each of these auctions, a large number of (identical) items are to be allocated to the largest submitted bids, where the price of each of the winning bids is equal to the bid itself. In this work, we study the problem of optimizing bidding strategies from the perspective of a single bidder. Effective bidding in pay-as-bid (PAB) auctions is complex due to the combinatorial nature of the action space. We show that a utility decoupling trick enables a polynomial time algorithm to solve the offline problem where competing bids are known in advance. Leveraging this structure, we design efficient algorithms for the online problem under both full information and bandit feedback settings that achieve an upper bound on regret of O(M √T log T) and O(M T^frac23 √log T) respectively, where M is the number of units demanded by the bidder and T is the total number of auctions. We accompany these results with a regret lower bound of Omega(M√T) for the full information setting and Omega (M2/3T2/3) for the bandit setting. We also present additional findings on the characterization of PAB equilibria. While the Nash equilibria of PAB auctions possess nice properties such as winning bid uniformity and high welfare & revenue, they are not guaranteed under no regret learning dynamics. Nevertheless, our simulations suggest these properties hold anyways, regardless of Nash equilibrium existence. Compared to its uniform price counterpart, the PAB dynamics converge faster and achieve higher revenue, making PAB appealing whenever revenue holds significant social value.