arXiv:2609.39532 · v2

Tight Liquid Welfare Guarantees for Auctions with Budgets

首次提交 2026-09-30 19:35

版本更新 2026-11-11 03:49

雷达观测 2026-11-13 10:09

摘要

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 bounding the optimal value 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 first-price auctions in which every bidder scales her values by a single bid multiplier (Deng et al., 2021), discriminatory and uniform price multi-unit auctions, and generalized first-price and second-price position auctions. Beyond budget-constrained settings, we also prove tight bounds for the budget-free uniform price auction and the budget-free generalized second-price auction.