Papers for

online marketplace teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Tight auction efficiency guarantees for bidders with budgets

Tight Liquid Welfare Guarantees for Auctions with Budgets via LP Duality

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

Wed 30 SeptComputer Science and Game Theory
The gist
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.
Open → 2609.39532v1