The Sample Complexity of Revenue Maximization
Talkat Complexity and Simplicity in Economics (Simons Institute workshop, 2015) · 2015-10-12..10-16·
summary
Proposes using the statistical learning notion pseudo-dimension to measure mechanism complexity and shows low pseudo-dimension implies polynomial sample complexity for revenue learning. Gives concrete bounds: VCG with bidder-specific reserves has pseudo-dimension about n log n, multi‑item simple mechanisms scale roughly linearly in K, and sample size scales with that dimension and like 1/ε^2 (and H^2). Learning uses empirical risk minimization over the mechanism class.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:28What Is...Simple?
- 4:27Quantifying Simplicity
- 5:54Simplicity Has Many Forms
- 7:48Related Work
- 10:55Pseudodimension: Examples
- 12:45Pseudodimension: Implications
- 17:50Pseudodimension: Definition
- 24:44Consequences
- 26:26Simplicity-Optimality Trade-Offs
- 28:48Summary
related talks
01h 07mMulti-Dimensional and Non-Linear Mechanism Design and Approximation I
09mMechanism Design Via Machine Learning: Overfitting, Incentives, and Privacy
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
32mLearning Reserve Prices in Second-Price Auctions
29mPure Exploration Problems
01h 11mA Theory of Multi-objective Machine Learning
34mPandora's Box with Correlations: Learning and Approximation
48mOutposts Between Worst- and Average Case Analysis: A Case Study in Auction Design