Outposts Between Worst- and Average Case Analysis: A Case Study in Auction Design
summary
Worst-case analysis gives no guidance for reserve prices, while Bayesian (average-case) theory (Myerson) yields closed-form optimal auctions and in the iid symmetric case the second-price with monopoly reserve is optimal. For asymmetric bidders using each bidder’s monopoly reserve guarantees a 50% approximation to the optimal revenue. Learning from samples requires O(1/ε^k) samples in the iid case (no n dependence) and polynomially many in n and 1/ε in general. The Bulow‑Klemperer result shows adding one extra bidder to a Vickrey auction beats the optimal-knowledge auction.
AI-written summary · about
chapters (33)
- 0:00Introduction
- 1:26Worstcase analysis
- 3:23Average case analysis
- 4:23Hybrid models
- 6:35A simple problem
- 9:22Worst case analysis
- 9:35Single item auctions
- 12:14Bayesian analysis
- 13:54Meyerson solution
- 14:52symmetric solution
- 18:05robustness
- 20:27partial knowledge
- 22:18monopoly prices
- 23:25hybrid model
- 23:51approximation guarantees
- 25:03proof
- 30:44reserve price
- 31:01anonymous reserve price
- 31:46sample knowledge
- 33:11results
- 34:17lower bound
- 35:26unknown distributions
- 37:05limper theorem
- 37:49prior independent auctions
- 38:13lots of distributions
- 38:48prior independent auction
- 39:00auctions on three lines
- 40:04distributions
- 40:35prior independent
- 41:24revenue benchmarks
- 42:45thought experiment
- 43:29benchmark
- 46:00conclusion
related talks
32mLearning Reserve Prices in Second-Price Auctions
01h 07mMulti-Dimensional and Non-Linear Mechanism Design and Approximation I
19mMarket Algorithms for Autobidding
01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
27mEconometrics for Learning Agents
09mMechanism Design Via Machine Learning: Overfitting, Incentives, and Privacy
48mRobust Inference for Games via Theoretical Guarantees
40mOnline Ad Allocation: Robust Optimization for Repeated Auctions