Welfare Maximization with Limited Interaction: Information and Communication in Economics
summary
Proves a round-vs-communication lower bound for multi-party matching: with B bits per player per round and R fixed rounds any protocol only achieves an approximation no better than about n^{1/5^R} (formalized via an inductive bound on expected matching size). The proof builds a recursive hard distribution of bidder/item blocks with many “fooling” blocks, uses mutual-information bounds, Pinsker and data-processing, and a conditional-decomposition lemma to perform round elimination. Also shows the simple simultaneous protocol that reports random edges gives roughly n^{1/R} upper bounds, so super-constant rounds are necessary.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:28The Economic Calculation Problem (Von Mises. 1920)
- 3:00[DNO 14] Simplest market: unit demand bidders (bipartite matching).
- 4:08Round/CC Tradeoff for Approximate Matchings
- 10:58Round/CC tradeoff apx Matchings
- 12:54A Hard Distribution for r Rounds
- 19:01Important Properties of Construction
- 22:43Main Theorem: E.
- 26:10Direct Sum based Round Elimination
- 31:02Open Problems
related talks
01h 09mInformation Theory in Computational Complexity IV
01h 04mInformation Theory in Computational Complexity I
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
23mHow to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
58mMarkov Chain Mixing Times and Applications III
01h 00mAverage-case Complexity for Polynomials, and All That
26mComplete Problems for Multi-Pseudodeterministic Computations