On Algorithmic Game Theory I

on YouTube ↗52m

" summary

A brisk history of algorithmic game theory traces pre-’95 links to TCS and Herbert Simon’s bounded rationality, then shifts to concrete complexity results: Nash and market equilibria are PPAD-complete, homotopy and selection procedures are PSPACE-complete, and Smale-style price adjustment can take roughly 2^{1/ε} steps to get ε-close. Practical highlights: VCG preserves complexity, the canonical traffic example gives a price of anarchy = 4/3, some routing instances are unbounded, and economies-of-scale markets create equilibria that are harder than NP to escape.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 1:06Before 1995...
3. 2:26Also before 1995: Computation as a game
4. 7:53Complexity in Cooperative Games
5. 8:30About the same time: complexity of Nash equilibrium?
6. 10:52The Internet changed Computer Science and TCS
7. 11:28Also, the methodological path to AGT: TCS as a Lens
8. 15:10Remember Max?
9. 15:58Algorithmic Mechanism Design!
10. 20:07The new Complexity Theory
11. 21:09Meanwhile: Equilibria can be inefficient!
12. 23:05Measuring the inefficiency: The price of anarchy
13. 23:50How much worse does it get?
14. 24:24But in the Internet flows don't choose routes...
15. 28:57Complexity of Equilibria
16. 29:23Nash is Intractable
17. 29:42PPA... what?
18. 32:22The Nash equilibrium lies at the foundations of modern economic thought
19. 35:55More intractability (price adjustment mechanisms)
20. 37:36Price equilibria in economies with production input
21. 38:54Complexity equilibria
22. 40:44Exact equilibria?
23. 43:28Three nice triess to deal with Nash equilibria
24. 44:36Much harder!

" related talks

• 58mLower Bound Issues in Computational Social ChoiceRolf Niedermeier · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 31mNew Unconditional Lower Bounds for Algorithms and Enumeration ProblemsSerge Gaspers · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 37m"Algorithms" is Not a Four-Letter WordJamis Buck · RubyConf 2011
• 01h 02mFine-Grained Counting Complexity IIRadu-Cristian Curticapean · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 27mOn the Subexponential Time Complexity of the CSPIyad Kanj · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 01h 02mFine-Grained Counting Complexity IHolger Dell · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 20mBeyond Worst-Case Budget-Feasible Mechanism DesignAviad Rubinstein, Junyao Zhao · ITCS 2023
• 26mLower Bounds on the Running Time for Scheduling and Packing ProblemsKlaus Jansen · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms