On Algorithmic Game Theory II
summary
Survey of current problems: internet research concentrates on ad auctions, BGP and net neutrality, and cloud economics with no neat theoretical consensus; a concrete complexity advance shows PPAD-complete hardness for approximating Nash in general multiplayer games (Avad), leaving two‑ or three‑player cases open and linking a new Delta‑Epsilon decision problem to quasi‑polynomial lower bounds. Evolutionary dynamics map to multiplicative weights/replicator dynamics and yield an objective combining entropy and selection‑weighted cumulative fitness. For dynamics, adopt chain recurrent sets as a robust solution concept. Two data results give mechanisms for strategic features and worker effort with Vickrey‑style payments achieving social optimum.
AI-written summary · about
chapters (12)
- 0:00Start
- 2:05Back to our roots
- 12:532. Update on Approximate Nash
- 13:24But how about 2 or 3 players?
- 24:22Social Networks
- 29:25The Theory of Evolution
- 36:18Dual interpretation
- 43:27Recall the BIG questions
- 45:545. Dynamical Systems
- 46:15Can you spot the equilibrium?
- 49:58A hierarchy of equilibrium concepts
- 54:42Chain recurrent sets
related talks
58mLower Bound Issues in Computational Social Choice
20mBeyond Worst-Case Budget-Feasible Mechanism Design
40mResilience of 3-Majority Dynamics to Non-Uniform Schedulers
37m"Algorithms" is Not a Four-Letter Word
01h 02mFine-Grained Counting Complexity I
01h 23mLoad balance and cache affinity: Friends, foes, or frenemies?
32mCompetitive Data Structure Dynamization
41mDistribution shift in ecological data: generalization vs. specialization,