Simple Mechanisms for a (Sub)Additive Buyer

on YouTube ↗35m

" summary

Shows that for independent-item distributions the better of selling items separately or as one bundle gives a six approximation for additive buyers and a constant‑factor bound for subadditive buyers. Proof uses a core–tail decomposition with cutoffs set at SREV, the marginal mechanism lemma (and an approximate marginal mechanism for subadditive valuations), variance/concentration bounds to make bundling work on the core, and a tail analysis showing SREV controls large items. Requires item independence; arbitrary correlation makes revenue and computation hard (NP‑hard).

AI-written summary · about

" chapters (21)

1. 0:00Intro
2. 1:28Selling separately
3. 3:18Lottery system
4. 4:59Challenges
5. 7:08Positive Results
6. 11:48Intuition
7. 12:14Quartal Decomposition
8. 13:44Proof
9. 16:30Marginal Mechanism Lemma
10. 17:22The Proof
11. 20:44Recap
12. 22:32Assumptions
13. 23:30Examples
14. 24:33Barriers
15. 25:31Impossible Results
16. 26:46Marginal Mechanismlemma
17. 27:45Bounds
18. 28:32Welfare
19. 29:42Srev
20. 30:50Recent work
21. 32:14Open question