How long does it take to solve a problem on a computer? This seemingly innocuous question, unanswerable in general, lies at the heart of computational complexity theory. With deep roots in mathematics and logic, this area of research seeks to understand the boundary between which problems are efficiently solvable by computer and which are not.
Computational complexity theory is one of the most vibrant and inventive branches of computer science, and Constantinos Daskalakis stands out as one of its brightest young lights. His work has transformed understanding about the computational complexity of a host of fundamental problems in game theory, markets, auctions, and other economic structures. A wideranging curiosity, technical ingenuity, and deep theoretical insight have enabled Daskalakis to bring profound new perspectives on these problems.
Game theory is widely applicable, not only in economics but even in such areas as international relations and biology. Clearly it would be useful to have a way to calculate Nash equilibria efficiently, in order to predict what strategic agents might do. Thus a long line of research began, soon after Nash proved his theorem, in which researchers developed algorithms to calculate Nash equilibria. By the early 2000s, however, none of those algorithms was known to be efficient, and some had been shown to be inefficient. Suspicions arose that the problem of computing a Nash equilibrium might be intractable. And if it is intractable, there would be no reason to expect equilibria would
always be discovered by strategic agents, that is, by human beings with limited brains. Such a conclusion would reduce expectations for how well Nash equilibrium can predict human behavior.
Questions of computational tractability are often viewed in the context of the well known “P versus NP” paradigm, which arose in the 1970s and soon became a central theme of computational complexity theory. Loosely speaking, P stands for the class of problems that are easy to solve by computer, meaning that an efficient algorithm for their solution is known. The class NP by contrast contains problems that are believed to be hard to solve, meaning that, if one is given a proposed solution, there is an efficient way to check it, but no efficient algorithm is known to produce solutions.
Problems in NP derive their hardness from the possibility that a solution might not exist. By contrast, for the problem of computing a Nash equilibrium, Nash’s proof guarantees that a solution exists. For this reason, the Nash equilibrium problem does not fit into the P versus NP paradigm. In 1994, Christos Papadimitriou defined a new complexity class called PPAD, suited to problems like the Nash equilibrium problem, for which solutions
always exist and for which no efficient algorithm is known to compute solutions. PPAD stands for “polynomial parity argument for directed graphs” and refers to a certain standard argument used to prove existence results in combinatorics. The argument is a directed version of a result known as the handshaking lemma. PPAD contains all computational problems whose solution can be shown to exist by using this lemma.
One of the most important problems in PPAD is a computational version of a result from pure mathematics called the Brouwer fixed point theorem. It says that a continuous mapping from a ball to itself cannot displace all points; at least one point must remain fixed under the map. Proved by L.E.J. Brouwer in 1911, this fundamental result is the basis for countless proofs in mathematics—including Nash’s proof of the existence of equilibria. Brouwer’s proof is nonconstructive, meaning that it guarantees the existence
of fixed points but does not show you how to find them. The computational version of the Brouwer fixed point theorem asks for an algorithm for finding fixed points. In his 1994 paper, Papadimitriou showed that this computational version is “PPAD-complete,” meaning that it is in PPAD and any problem in PPAD can be reduced to it, or, in other words, it is exactly as hard as PPAD.
Daskalakis became a PhD student of Papadimitriou and began working on the Nash equilibrium problem. He made a big advance when, together with Papadimitriou and Paul Goldberg, he proved that the Nash equilibrium problem is computationally equivalent to the problem of finding Brouwer fixed points and therefore is also PPAD-complete. In showing that the Nash equilibrium problem is intractable, the work of Daskalakis et al breaks the universality of Nash equilibria: One cannot expect Nash equilibria to always result from interactions among strategic agents, because those agents cannot perform intractable computations. In this practical sense, Nash equilibria do not always exist.
The work also sheds light on why an efficient algorithm for the Nash equilibrium problem had been so elusive. If one looks at the guts of the algorithms people had developed to compute Nash equilibria, one sees the hallmark structure of the PPAD class lurking in the background. The work of Daskalakis et al showed that this structure is unavoidable.
https://www.mathunion.org/fileadmin/IMU/Prizes/Nevanlinna/daskalakis-final.pdf
Constantinos Daskalakis (Greek: Κωνσταντίνος Δασκαλάκης; born 29 April 1981) is a Greek theoretical computer scientist. He is a professor at MIT’s Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory. He was awarded the Rolf Nevanlinna Prize and the Grace Murray Hopper Award in 2018.
After his PhD he spent a year as a postdoctoral researcher in Jennifer Chayes’s group at Microsoft Research, New England.
Daskalakis works on the theory of computation and its interface with game theory, economics, probability theory, statistics and machine learning.
He has resolved long-standing open problems about the computational complexity of the Nash equilibrium, the mathematical structure and computational complexity of multi-item auctions, and the behavior of machine-learning methods such as the expectation–maximization algorithm. He has obtained computationally and statistically efficient methods for statistical hypothesis testing and learning in high-dimensional settings, as well as results characterizing the structure and concentration properties of high-dimensional distributions.
Daskalakis co-authored The Complexity of Computing a Nash Equilibrium with his doctoral advisor Christos Papadimitriou and Paul W. Goldberg, for which they received the 2008 Kalai Game Theory and Computer Science Prize from the Game Theory Society for “the best paper at the interface of game theory and computer science”, in particular “for its key conceptual and technical contributions”; and the outstanding paper prize from the Society for Industrial and Applied Mathematics (SIAM).
He was appointed a tenured Professor at MIT in May 2015.
https://en.wikipedia.org/wiki/Constantinos_Daskalakis
Theoretical Computer Scientist, Modern Mathematics
