#534 overall
Nash Equilibrium and PPAD Complexity (Constantinos Daskalakis)
MIT
1 recommender · 1 thread · recommended in 1 year, 2018 · score 1.0
An MIT video lecture by Constantinos Daskalakis on his work showing that finding a Nash equilibrium is PPAD-complete, and what that implies about the computational intractability of PPAD problems. It is aimed at readers with computer science or economics backgrounds.
Commenters call it a fantastic, intuitive introduction to Daskalakis's PPAD-completeness result, praising his enthusiasm and clear explanation.
Algorithms & Data Structuresadvancedfreevideo lectures#nash equilibrium#ppad#computational complexity#game theory#daskalakis
Recommendations by year
20062026
For those who don't know, Constantinos Daskalakis, one of the winners profiled, proved that finding a Nash equilibrium (for example, in an economy) is a PPAD-complete problem: if anyone discovers an efficient algorithm for finding Nash equilibria, such an algorithm could be used for efficiently solving all other problems in the PPAD complexity class. PPAD problems are widely considered to be intractable. No algorithm is known for solving them with running time bounded by a polynomial function of input/problem size. The implications in many fields, starting with economics, are clearly significant. Daskalakis's prize is well-deserved.
There is a fantastic introductory MIT video lecture on this work by Daskalakis himself available on YouTube.[a] His enthusiasm and passion in that video lecture are contagious -- matched only by his ability to explain his work in an intuitive manner. Highly recommended for those HNers who have computer-science or economics backgrounds and are interested in computational complexity but are not yet familiar with Daskalakis's work.
[a] https://www.youtube.com/watch?v=TUbfCY_8Dzs