3 ms·
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-co
by cs702 8y ago
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 https://www.youtube.com/watch?v=TUbfCY_8Dzs
- aw1621107 8y agoHow do PPAD-complete problems relate to P=NP/NP-complete problems/etc., if they do at all? Your description of PPAD-complete problems reminds me a lot of descriptions I've read of NP-related problems, but this is the first time I've heard of the term "PPAD".
- cs702 8y agoVery -- very! -- informally: in PPAD-complete problems, a solution is known to exist (e.g., there is always a Nash equilibrium), but no one knows of an efficient algorithm for finding the solution. In other complexity classes widely believed to be intractable, such as NP-complete, the problems are decision problems that ask a yes/no question, and no one knows of an efficient algorithm for answering the question. By "efficient algorithm," I again mean an algorithm whose running time is bounded by a polynomial function of input or problem size.
- mygo 8y agoso I guess, one way to put it, is to look at the Traveling Salesman Problem? The decision problem asks “given a set of cities is there a tour shorter than length n?”. This is NP-Complete. However the pop culture version of the problem is “given a set of cities, what is a tour of the shortest possible length?”. This would be the PPAD-complete version of the problem, since that solution does exist, it’s just unknown and not known to be tractable within polynomial time? Can the Nash Equilibrium problem have a decision version whose answer is either true or false?
- sometimesijust 8y agoTSP is NP-hard for optimisation version and NP-complete for decision version. Consider how you would test that a minimal solution is minimal vs testing whether a given solution has less than a given cost. PPAD is less complete than these two classes. The decision problem for Nash Equilibria might be, does a second equilibrium exist?
- mygo 8y agoAah gotcha. So you’re saying it’s easier to verify the solution to a Nash equilibrium problem than it is to verify the solution to the TSP optimization problem?