# The Price of Anarchy in Auctions

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jul 2016.

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

- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [How Bad is Top-K Recommendation under Competing Content Creators?](https://mlsanity.com/paper/2302.01971/) (2023)
- [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)
- [Faster Rates for No-Regret Learning in General Games via Cautious Optimism](https://mlsanity.com/paper/2503.24340/) (2025)
- [Learning and Collusion in Multi-unit Auctions](https://mlsanity.com/paper/2305.17402/) (2023)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [An Algorithmic Introduction to Savings Circles](https://mlsanity.com/paper/2203.12486/) (2022)
- [Artificial Intelligence for Multi-Unit Auction design](https://mlsanity.com/paper/2404.15633/) (2024)
- [Price of Anarchy of First-Price Auctions in Agentic Markets](https://mlsanity.com/paper/2610.20587/) (2026)

## Abstract (arXiv)

This survey outlines a general and modular theory for proving approximation guarantees for equilibria of auctions in complex settings. This theory complements traditional economic techniques, which generally focus on exact and optimal solutions and are accordingly limited to relatively stylized settings. We highlight three user-friendly analytical tools: smoothness-type inequalities, which immediately yield approximation guarantees for many auction formats of interest in the special case of complete information and deterministic strategies; extension theorems, which extend such guarantees to randomized strategies, no-regret learning outcomes, and incomplete-information settings; and composition theorems, which extend such guarantees from simpler to more complex auctions. Combining these tools yields tight worst-case approximation guarantees for the equilibria of many widely-used auction formats.