Complexity and Algorithmic Game Theory I
summary
Surveys computational status of equilibrium concepts and gives concrete results: two‑player zero‑sum games are solvable by linear program / ellipsoid, while two‑player nonzero‑sum Nash is PPAD-complete even though existence is guaranteed via Sperner/Brouwer parity arguments and succinct circuits; additive ε‑Nash admits a n^{log n} quasi‑polynomial algorithm but exact hardness remains; structured classes help: zero‑sum polymatrix games reduce to LPs, anonymous games force either ≤1/ε^3 randomizers or a common mixed strategy, and correlated equilibria are computable via compact/sparse representations.
AI-written summary · about
chapters (21)
- 0:00Intro
- 0:40Motivating Spiel
- 2:38Simple Stochastic Games Shapley'53
- 8:07Normal Form Games
- 9:53von Neumann vs Nash
- 12:52The Pavlovian reaction (cont.)
- 14:13The Non-Constructive Step?
- 15:44Sperner's Lemma
- 26:14The PPAD Class [Papadimitriou'94]
- 27:41The SPERNER problem (precisely)
- 28:41Solving SPERNER
- 29:25Problems in PPAD
- 31:28The Complexity of Nash Equilibrium
- 34:18Approximation
- 38:15Escape 2: Games w/ Special Structure
- 39:27Multiplayer Zero-Sum...what?
- 41:05Zero-Sum Polymatrix Games (cont.)
- 46:34Anonymous Games
- 51:14Escape 3: Alternative Solution Concepts
- 52:28Correlated vs Nash
- 57:49Summary
related talks
58mLower Bound Issues in Computational Social Choice
01h 02mFine-Grained Counting Complexity I
26mLower Bounds on the Running Time for Scheduling and Packing Problems
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
27mOn the Subexponential Time Complexity of the CSP
20mBeyond Worst-Case Budget-Feasible Mechanism Design
40mResilience of 3-Majority Dynamics to Non-Uniform Schedulers
30mLower Bound Results for Hard Problems Related to Finite Automata