Tight auction efficiency guarantees for bidders with budgets
Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality
Computer Science and Game Theory
Summary
This paper studies how well auctions work when bidders have limited budgets. The authors create a new approach to analyze auction outcomes by linking them to solutions of a mathematical problem called a linear program. This lets them find exact efficiency limits for many common auction types where bidders face spending caps. Their method also offers fresh insights into auctions without budgets, providing precise lower bounds on how efficient these can be.
What this means in practice
- •For online marketplace teams: Improve auction design to ensure fair efficiency when buyers have limited budgets across various auction formats.
- •For advertising platform engineers: Optimize bidding algorithms for ad slots while accounting for advertisers’ budget limits using tight efficiency bounds.
Authors
Twan Kroll, Guido Schäfer, Artem Tsikiridis
Abstract
We study the efficiency of auctions with budget-constrained bidders and derive tight price of anarchy (PoA) bounds for coarse correlated equilibria (CCE). To this end, we develop a general framework that reduces proving PoA guarantees to finding feasible solutions to the dual of a linear program. The LP is formulated over a small number of per-bidder equilibrium statistics, incorporates constraints implied by the auction setting and equilibrium behavior, and captures a novel smoothness notion tailored to budget-constrained environments; we provide a reduction from classical smoothness to this new notion. Our approach enables simple and tight PoA analyses across a broad range of auction formats. Using our framework, we obtain tight liquid welfare guarantees for simultaneous first-price, second-price, and all-pay auctions, simultaneous auctions with restricted uniform bidding interfaces, discriminatory and uniform price multi-unit auctions, and generalized first-price position auctions. Beyond budget-constrained settings, we derive new lower bounds for the budget-free uniform price auction and generalized second-price auction; in particular, our lower bound for the uniform price auction matches the upper bound of $3.146$ by de Keijzer et al. (2013).