Abstract:

Recent results have shown that computing Nash equilibria is an intractable problem. It is not NP-hard, since Nash’s theorem shows that a Nash equilibrium exists in every game, and this makes it unlikely that the problem is NP-hard. Instead, it is as intractable as any fixed-point computation problem in a precise technical sense. In the first part of the talk, we survey results on the complexity of the Nash equilibrium. In view of these results, the credibility of the Nash equilibrium is questioned: how do markets and players converge to equilibria, if finding them is an intractable problem? In the second part of the talk, we discuss ways to go around the computational barrier, such as looking at approximation or special cases of the problem. A particularly promising direction is to develop probabilistic tools to exploit algorithmically the uncertainty and symmetry that is inherent in certain game-theoretic settings. We present recent results in approximating equilibria of anonymous games, and optimally solving multi-dimensional pricing problems.

(Based on joint works with Christos Papadimitriou, Paul Goldberg, Yang Cai)

Bio: Constantinos (or Costis) Daskalakis is an Assistant Professor of EECS at MIT. He completed his undergraduate studies in 2004 at the National Technical University of Athens, and obtained a PhD in Computer Science at UC Berkeley in 2008. He spent the year 2008-2009 in Microsoft Research New England as a postdoctoral researcher, and since 2009 he has been at MIT. His research interests lie in Algorithmic Game Theory and Applied Probability, particularly in computational aspects of markets and the Internet, in social networks, and in computational problems in Biology. Costis has been honored with the Game Theory and Computer Science Prize from the Game Theory Society, the 2008 ACM Doctoral Dissertation Award, the NSF Career Award, a Sloan Foundation Fellowship, and a Microsoft Research Fellowship in honor of Dean Richard Newton.