A Unified Duality Theory for Bayesian Mechanism Design
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23
summary
Presents a unified LP duality framework that produces a virtual welfare upper bound for Bayesian mechanisms by constructing an explicit LP duality flow whose node flows correspond to ironing/multipliers. The framework exactly recovers Myerson for single-item auctions, reproduces the Chawla–Hartline–Kleinberg unit-demand bound and the Hart–Nisan additive “sell separately or bundle” ≈6 guarantee, and highlights which relaxed truthfulness constraints (a small set of underreporting constraints) suffice to get tight upper bounds.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:27Background: Single Item, Single Bidder
- 1:59Background: Single Item, Multiple Bidders
- 5:31Summary: Single Item
- 6:12Background: Multiple Items
- 7:20Two Items -Dependency is Necessary!
- 8:38Two Items - Randomization is Necessary!
- 9:33Two Items - Market Research Competition!
- 10:40Two Items - Non-Monotonicity!
- 11:42Summary: Multiple Items
- 12:27What Drives Single-Item Results?
- 14:33Simple Mechanisms often Approximately Optimal
- 18:55Main Result
- 20:38Linear Programming Formulation
- 25:25What are Dual Solutions?
- 29:40Recent Advances