Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence
summary
Gradient-based pacing algorithms update a single multiplier per advertiser and, without ever converging to an equilibrium, guarantee expected liquid welfare at least half of optimal liquid welfare (up to sublinear error) across a broad class of auctions including first-price, second-price and GSP, even with arbitrarily correlated values per round. The method uses projected gradient updates with step ~1/√T, gives individual value-maximization guarantees against the best fixed multiplier in hindsight and yields vanishing average regret with a T^{3/4} cumulative bound. No convergence required
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:05What are Repeated Auctions
- 2:30Automated Bidding Agents
- 3:34Theoretical and Practical Questions
- 5:28Related Literature
- 7:30Convergence
- 9:04Model
- 11:05Aggregate Welfare
- 12:37What is Pacing
- 15:29Theorem
- 17:43Individual guarantees
- 20:22Proof
- 23:08Conclusion
related talks
44mOnline Advertisements and Online Algorithms
52mDashboard Mechanisms for Online Marketplaces
44mAdverse Selection and Auction Design for Internet Display Advertising
10mSynchronized Priority Auctions
51mIncentive Auctions and Spectrum Repacking
50mDiversity in Matching Markets
52mOptimal Growth in Two-Sided Markets
49mAlgorithmic Mechanism Design with Investment