Complexity and Algorithmic Game Theory II
summary
Second part of the tutorial presents concrete positive and negative results: deterministic mechanisms that make only value queries need exponentially many queries to guarantee even a 1/√m fraction of optimal welfare, while Bayesian assumptions let one convert any α-approximation algorithm into a truthful mechanism losing only an arbitrarily small ε. The paper gives a black-box reduction using the ellipsoid + Border's theorem toolkit, yields polynomial-time revenue‑optimal mechanisms for additive bidders (Myerson extended to multi-item) and shows simple auctions and posted‑price schemes recover constant fractions in Bayes‑Nash.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 2:02Running Example
- 3:45Obvious Questions
- 5:11Reducing Communication
- 10:35Conflict of Incentives
- 12:45Beijing
- 17:48Algorithms
- 18:58Vickrey Auction
- 20:24Mechanisms
- 31:46Visual Rationality
- 33:46Intuition
- 38:37Results
related talks
20mBeyond Worst-Case Budget-Feasible Mechanism Design
58mLower Bound Issues in Computational Social Choice
01h 02mFine-Grained Counting Complexity I
26mLower Bounds on the Running Time for Scheduling and Packing Problems
20m(Almost) Perfect Discrete Iterative Load Balancing
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
01h 01mExact Algorithms from FPT Algorithms
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)