Computational Efficiency Requires Simple Taxation

on YouTube ↗35m

" summary

Main claim: for broad multi-parameter domains the taxation indexing complexity ≤ communication complexity + 1, so the number of different menus a truthful mechanism can present is exponentially bounded by its communication cost. Counterexample: VCG with gross substitutes: polynomial communication, exponential taxation indexing (many gross‑substitute valuations induce distinct menus). Proof sketch: create instances where the other player’s value equals menu prices so the final “positive profit” bit distinguishes transcripts, forcing one transcript per menu. Applications: convert ex‑post Nash to dominant strategies for two players with small blowup; reduce two‑player truthful algorithms to simultaneous protocols.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 0:40The Communication Complexity
3. 1:16The Taxation Principle
4. 2:22The Taxation Complexity
5. 5:36Communication vs. Taxation
6. 6:22Heavy Taxation, Small Communication
7. 7:27Combinatorial Auctions
8. 16:51Applications and Extensions
9. 19:45Proving Impossibilities
10. 24:04Proof of the Main Theorem (tsc+1)
11. 28:26The Fooling Set Argument
12. 31:27Summary