Complexity in AGT Update: Nash Approximability and Simultaneous Auctions

on YouTube ↗35m

" summary

Survey of computational questions about Nash equilibria and simultaneous auctions, emphasizing recent results on how well Nash equilibria can be approximated algorithmically and the complexity of computing outcomes in simultaneous-auction settings. Discusses algorithmic techniques and hardness results for approximating Nash equilibria and for computing or reasoning about equilibria in simultaneous auctions.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:17Why complexity?
3. 1:52Combinatorial Auctions: Latest Great Idea
4. 6:23What will happen at BNE? (cont.)
5. 9:26Dynamic Mechanism Design
6. 10:28Complexity in Dynamic Mechanisms [PPPR 2016]
7. 13:08Generic Mechanism
8. 14:47Outline
9. 20:22Dealing with the Intractability of Nash: Approximation?
10. 21:18Approximating Nash: Not business as usual
11. 22:39Obstacles to PTAS
12. 25:42A PCP for PPAD?
13. 27:04Etymology: Why PCP?
14. 28:00PCP!
15. 28:51Birthday repetition [AIM 2014]
16. 30:54Soooooo... fifteen years later