The Price of Anarchy in Auctions

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.

• Publication year

  2016

• Venue

  Journal of Artificial Intelligence Research

• Publication date

  2016-07-26

• Fields of study

  Computer Science, Economics

• Identifiers
  DOI 10.1613/jair.5272arXiv 1607.07684
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Twenty Lectures on Algorithmic Game Theory

  2016cited by this paper
• A duality based unified approach to Bayesian mechanism design

  2016cited by this paper
• Simple Mechanisms for Agents with Complements

  2016cited by this paper
• Best-Response Dynamics in Combinatorial Auctions with Item Bidding

  2016cited by this paper
• Communication Complexity

  2016cited by this paper
• No-Regret Learning in Repeated Bayesian Games

  2015cited by this paper
• Simple Auctions with Simple Strategies

  2015cited by this paper
• Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round

  2015influential reference
• Learning in Auctions: Regret is Hard, Envy is Easy

  2015cited by this paper
• On the Economic Efficiency of the Combinatorial Clock Auction

  2015cited by this paper
• Communication Complexity (for Algorithm Designers)

  2015cited by this paper
• When does the Price of Anarchy tend to 1 in Large Walrasian Auctions and Fisher Markets

  2015cited by this paper
• Smooth Online Mechanisms: A Game-Theoretic Problem in Renewable Energy Markets

  2015cited by this paper
• The price of anarchy in large games

  2015cited by this paper
• Robust Price of Anarchy Bounds via LP and Fenchel Duality

  2015cited by this paper
• Interpolating Between Truthful and non-Truthful Mechanisms for Combinatorial Auctions

  2015cited by this paper
• Learning and Efficiency in Games with Dynamic Population

  2015cited by this paper
• Asymptotically Tight Bounds for Inefficiency in Risk-Averse Selfish Routing

  2015cited by this paper
• Greedy Algorithms Make Efficient Mechanisms

  2015cited by this paper
• Algorithms against Anarchy: Understanding Non-Truthful Mechanisms

  2015influential reference
• On the Efficiency of All-Pay Mechanisms

  2015influential reference
• On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources

  2015cited by this paper
• No-Regret Learning in Bayesian Games

  2015cited by this paper
• Simultaneous bayesian auctions and computational complexity

  2014cited by this paper
• Asymmetric all-pay auctions with interdependent valuations

  2014cited by this paper
• Price of anarchy for auction revenue

  2014influential reference
• Barriers to Near-Optimal Equilibria

  2014influential reference
• Efficiency of Mechanisms in Complex Markets

  2014cited by this paper
• Ranking asymmetric auctions: Filling the gap between a distributional shift and stretch

  2014cited by this paper
• Welfare Guarantees for Proportional Allocations

  2014influential reference
• On the Complexity of Computing an Equilibrium in Combinatorial Auctions

  2014cited by this paper
• Multi-dimensional Virtual Values and Second-degree Price Discrimination

  2014cited by this paper
• Price competition in online combinatorial markets

  2014cited by this paper
• A Unifying Hierarchy of Valuations with Complements and Substitutes

  2014influential reference
• Auctions with unique equilibria

  2013cited by this paper
• Valuation Compressions in VCG-Based Combinatorial Auctions

  2013cited by this paper
• Approximate Mechanism Design without Money

  2013cited by this paper
• Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions

  2013influential reference
• Prior-independent auctions for risk-averse agents

  2013cited by this paper
• On the efficiency of the walrasian mechanism

  2013influential reference
• Communication Complexity of Combinatorial Auctions with Submodular Valuations

  2013cited by this paper
• Efficiency Guarantees in Auctions with Budgets

  2013cited by this paper
• Simultaneous auctions are (almost) efficient

  2012influential reference
• Combinatorial auctions with restricted complements

  2012cited by this paper
• Uniform Price Auctions: Equilibria and Efficiency

  2012cited by this paper
• Mechanism Design without Money

  2012cited by this paper
• Composable and efficient mechanisms

  2012influential reference
• Do Externalities Degrade GSP ’ s Efficiency ?

  2012cited by this paper
• Bayesian Games and the Smoothness Framework

  2012influential reference
• Intrinsic robustness of the price of anarchy

  2012influential reference
• The price of anarchy in games of incomplete information

  2012cited by this paper
• Bayesian sequential auctions

  2012cited by this paper
• Welfare guarantees for combinatorial auctions with item bidding

  2011influential reference
• Optimal Crowdsourcing Contests

  2011cited by this paper
• Robust Predictions in Games with Incomplete Information

  2011cited by this paper
• Correlated Equilibrium in Games with Incomplete Information

  2011cited by this paper
• On the efficiency of equilibria in generalized second price auctions

  2011influential reference
• GSP auctions with correlated types

  2011cited by this paper
• Sequential auctions and externalities

  2011influential reference
• Non-price equilibria in markets of discrete goods

  2011influential reference
• Asymmetric first-price auctions with uniform distributions: analytic solutions to the general case

  2010cited by this paper
• The Submodular Welfare Problem with Demand Queries

  2010influential reference
• Multi-parameter mechanism design and sequential posted pricing

  2010cited by this paper
• Pure and Bayes-Nash Price of Anarchy for Generalized Second Price Auction

  2010influential reference
• Crowdsourcing and all-pay auctions

  2009cited by this paper
• Price of anarchy for greedy auctions

  2009influential reference
• Bayesian Combinatorial Auctions

  2008influential reference
• Asymmetric Auctions

  2007cited by this paper
• Algorithmic Game Theory: Mechanism Design without Money

  2007cited by this paper
• Prediction, learning, and games

  2006influential reference
• All-Pay Auctions - An Experimental Study

  2006cited by this paper
• Approximation algorithms for combinatorial auctions with complement-free bidders

  2005influential reference
• Fictitious play in 2×n games

  2005influential reference
• Efficiency loss in a network resource allocation game: the case of elastic supply

  2004influential reference
• Putting Auction Theory to Work

  2004influential reference
• The Clock-Proxy Auction: A Practical Combinatorial Auction Design

  2004cited by this paper
• EFFICIENCY OF LARGE DOUBLE AUCTIONS

  2003cited by this paper
• The Optimality of a Simple Market Mechanism

  2002cited by this paper
• Efficiency of Large Private Value Auctions

  2001cited by this paper
• Combinatorial auctions with decreasing marginal utilities

  2001cited by this paper
• A simple adaptive procedure leading to correlated equilibrium

  2000cited by this paper
• A Theory of Auctions and Competitive Bidding II

  2000cited by this paper
• Adaptive game playing using multiplicative weights

  1999cited by this paper
• Worst-case Equilibria

  1999cited by this paper
• Auctions of Heterogeneous Objects

  1999influential reference
• The Theory of Learning in Games

  1998cited by this paper
• Fictitious Play Property for Games with Identical Interests

  1996cited by this paper
• Asymmetric All-Pay Auctions with Incomplete Information: The Two-Player Case

  1996cited by this paper
• Gambling in a rigged casino: The adversarial multi-armed bandit problem

  1995cited by this paper
• Convergence to Efficiency in a Simple Market with Incomplete Information

  1994cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• The all-pay auction with complete information

  1990cited by this paper
• The weighted majority algorithm

  1989cited by this paper
• Multi-Item Auctions

  1986cited by this paper
• Optimal Auctions with Risk Averse Buyers

  1984cited by this paper
• Efficient Mechanisms for Bilateral Trading

  1983cited by this paper
• A theory of auctions and competitive bidding

  1982cited by this paper
• Optimal Auction Design

  1981cited by this paper
• An Example of a Multi-Object Auction Game

  1979influential reference
• The assignment game I: The core

  1971cited by this paper

• Tit-for-tat strategies drive growth and inequality in production economies

  2025cites this paper
• Transaction Fee Mechanism Design for Leaderless Blockchain Protocols

  2025influential citation
• Faster Rates for No-Regret Learning in General Games via Cautious Optimism

  2025cites this paper
• Expected Variational Inequalities

  2025influential citation
• Interdisciplinary synergy and integration in auction theory and practice

  2025cites this paper
• The Use of Artificial Intelligence for Auction Design

  2025cites this paper
• Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets

  2025cites this paper
• Game-Theoretic Analysis of MEV Attacks and Mitigation Strategies in Decentralized Finance

  2025cites this paper
• Equilibrium Efficiency and Learning in Budgeted Procurement Marketplaces

  2025cites this paper
• Public Projects with Preferences and Predictions

  2024cites this paper
• Artificial Intelligence for Multi-Unit Auction design

  2024cites this paper
• Games with Payments between Learning Agents

  2024cites this paper
• The Value of Recall in Extensive-Form Games

  2024cites this paper
• An improved bound for the price of anarchy for related machine scheduling

  2024cites this paper
• Price of Anarchy for First Price Auction with Risk-Averse Bidders

  2023influential citation
• q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations

  2023cites this paper
• How Bad is Top-K Recommendation under Competing Content Creators?

  2023cites this paper
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics

  2023cites this paper
• On the optimality of Shapley mechanism for funding public excludable goods under Sybil strategies

  2023cites this paper
• On the Intrinsic Fragility of the Price of Anarchy

  2023cites this paper
• On the Interplay between Social Welfare and Tractability of Equilibria

  2023cites this paper
• Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders

  2023cites this paper
• Efficiency of the Generalized Second-Price Auction for Value Maximizers

  2023cites this paper
• Games and Economic Behavior

  2023influential citation
• Learning in Repeated Multi-Unit Pay-As-Bid Auctions

  2023cites this paper
• Managing Write Access without Token Fees in Leaderless DAG-based Ledgers

  2023influential citation
• Learning and Collusion in Multi-unit Auctions

  2023cites this paper
• Learning Properties in Simulation-Based Games

  2023cites this paper
• A dynamic routing protocol with payments for the Physical Internet: A simulation with learning agents

  2022cites this paper
• Efficiency of Ad Auctions with Price Displaying

  2022cites this paper
• High Welfare Matching Markets via Descending Price

  2022influential citation
• An Algorithmic Introduction to Savings Circles

  2022cites this paper
• Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence

  2022influential citation
• The Price of Stability for First Price Auction

  2022cites this paper
• Towards a Theory of Maximal Extractable Value I: Constant Function Market Makers

  2022cites this paper
• Efficiency of the First-Price Auction in the Autobidding World

  2022cites this paper
• Meta-Learning in Games

  2022cites this paper
• Principal-agent VCG contracts

  2022cites this paper
• Principal-Agent VCG Contracts ∗

  2022cites this paper
• First Price Auction is 1 – 1 /e2 Efficient

  2022influential citation
• Settling the Efficiency of the First-Price Auction

  2022cites this paper
• Denial-of-Service Attack Mitigation in Multi-hop 5G D2D Wireless Communication Networks Employing Double Auction Game

  2022cites this paper
• Auctions between Regret-Minimizing Agents

  2021cites this paper
• Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guarantees

  2021cites this paper
• Corruption in Auctions: Social Welfare Loss in Hybrid Multi-Unit Auctions

  2021cites this paper
• Anarchy in the UJ: Coordination mechanisms for minimizing the number of late jobs

  2021cites this paper
• Revelation gap for pricing from samples

  2021cites this paper
• Equilibria in Auctions with Ad Types

  2021cites this paper
• PoA of Simple Auctions with Interdependent Values

  2021cites this paper
• Capturing Corruption with Hybrid Auctions: Social Welfare Loss in Multi-Unit Auctions

  2021cites this paper
• The Price of Anarchy in ROSCAS with Risk Averse Agents

  2021cites this paper
• Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020

  2021cites this paper
• On the Impact of Information Acquisition and Aftermarkets on Auction Efficiency

  2021influential citation
• Near-Optimal No-Regret Learning in General Games

  2021cites this paper
• Making Auctions Robust to Aftermarkets

  2021cites this paper
• Simple combinatorial auctions with budget constraints

  2020cites this paper
• Simple, Credible, and Approximately-Optimal Auctions

  2020cites this paper
• Simultaneous 2nd Price Item Auctions with No-Underbidding

  2020influential citation
• Complexity Theory, Game Theory, and Economics: The Barbados Lectures

  2020influential citation
• Interconnected pay-as-bid auctions

  2020cites this paper
• The Price of Anarchy of Self-Selection in Tullock Contests

  2020cites this paper
• Democratising blockchain: A minimal agency consensus model

  2020cites this paper
• Mechanism Design for Perturbation Stable Combinatorial Auctions

  2020influential citation
• The Price of Anarchy of Two-Buyer Sequential Multiunit Auctions

  2020cites this paper
• Option values in sequential auctions with time-varying valuations

  2020cites this paper
• Price of Anarchy of Simple Auctions with Interdependent Values

  2020influential citation
• A Bandit Learning Algorithm and Applications to Auction Design

  2020influential citation
• Multi-Item Nontruthful Auctions Achieve Good Revenue

  2020cites this paper
• Simple Mechanisms for Agents with Non-linear Utilities

  2020cites this paper
• Option values in sequential auctions with time-varying valuations

  2020cites this paper
• Algorithmic Game Theory: 13th International Symposium, SAGT 2020, Augsburg, Germany, September 16–18, 2020, Proceedings

  2020cites this paper
• Principal-Agent VCG Contracts

  2019cites this paper
• When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the Price-of-Anarchy

  2019cites this paper
• Complexity-Theoretic Barriers in Economics

  2019cites this paper
• Online Optimisation for Online Learning and Control - From No-Regret to Generalised Error Convergence

  2019cites this paper
• Multi-agent learning for security and sustainability

  2019cites this paper
• Primal-Dual Approaches in Online Algorithms, Algorithmic Game Theory and Online Learning

  2019cites this paper
• Envy, Regret, and Social Welfare Loss

  2019cites this paper
• Proportional Dynamics in Exchange Economies

  2019cites this paper
• Design for Weakly Structured Environments

  2019cites this paper
• A Minimal Agency Scheme for Proof-of-Stake Consensus

  2019cites this paper
• An improved welfare guarantee for first-price auctions

  2018cites this paper
• Procurement with Cost and Non-Cost Attributes: Cost-Sharing Mechanisms

  2018cites this paper
• Pay-as-bid auctions in theory and practice

  2018cites this paper
• An empirical study on computation of exact and approximate equilibria

  2018cites this paper
• Smoothed Efficient Algorithms and Reductions for Network Coordination Games

  2018cites this paper
• Distributed control and game design: From strategic agents to programmable machines

  2018cites this paper
• Approximately Optimal Mechanism Design

  2018influential citation
• The Pareto Frontier of Inefficiency in Mechanism Design

  2018cites this paper
• Nash Equilibrium in Smoothed Polynomial Time for Network Coordination Games

  2018cites this paper
• Distributed resource allocation through utility design - Part I: optimizing the performance certificates via the price of anarchy

  2018cites this paper
• On understanding price-QoS war for competitive market and confused consumers

  2018cites this paper
• A tighter welfare guarantee for first-price auctions

  2018cites this paper
• Space Debris Removal: Learning to Cooperate and the Price of Anarchy

  2018cites this paper
• Revenue Guarantee Equivalence ∗ Dirk Bergemann

  2018cites this paper
• A note on the efficiency of position mechanisms with budget constraints

  2018cites this paper
• Complexity Theory, Game Theory, and Economics

  2018cites this paper
• An End-to-End Argument in Mechanism Design (Prior-Independent Auctions for Budgeted Agents)

  2018cites this paper
• Universal Growth in Production Economies

  2018cites this paper
• Walrasian Dynamics in Multi-unit Markets

  2017cites this paper