The Nash equilibrium aspires to model the behavior of rational individuals in situations of conflict. But how plausible would it be, if there were no efficient dynamics by which the game play could converge to such an equilibrium? Motivated by this question we study the computational complexity of the Nash equilibrium. We show that finding a Nash equilibrium is an intractable problem, making it unlikely that there are efficient dynamics for it. Since by Nash's theorem an equilibrium is guaranteed to exist, the Nash equilibrium belongs to the class of problems in NP which always have a solution, and previous work establishes that such problems are unlikely to be NP-complete. We show instead that the problem is as hard as any fixed-point computation problem in a precise technical sense, giving rise to a new complexity landscape inside the class NP. We will assume no background in game theory, or topology. A little background in computational complexity may be helpful.
Constantinos (or Costis) Daskalakis grew up in Athens, Greece, where he received an undergraduate degree in Electrical and Computer Engineering from the National Technical University of Athens. In 2004 he moved to UC Berkeley, California, where he pursued doctorate studies in Computer Science under the supervision of Professor Christos Papadimitriou. In 2008 he moved to Boston, Massachusetts, to spend a year as a postdoctoral researcher at Microsoft Research, New England, and in Summer 2009, he joined the faculty at MIT as an Assistant Professor of Computer Science. Costis was awarded the 2008 ACM Doctoral Dissertation award. He was also awarded, together with Paul Goldberg and Christos Papadimitriou, the first Game Theory and Computer Science Prize by the Game Theory Society. He was the recipient of a Microsoft Research Fellowship in honor of Dean Richard Newton, a UC Regents Fellowship, and a best student paper award at the ACM Conference on Electronic Commerce.
