|
The Complexity of Nash Equilibria in Large Games Abstract: How credible would the Nash equilibrium be as a framework for behavior prediction, if there were no dynamics by which the game play could converge to such an equilibrium within a non-prohibitively large number of iterations? Motivated by this question we study the computational complexity of the Nash equilibrium. We show first that finding a Nash equilibrium is an intractable problem, which makes 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, which is motivated by simplicial algorithms for the computation of fixed points. In view of this hardness result, we discuss algorithms for computing approximate Nash equilibria and provide efficient algorithms for a large class of multi-player games, called anonymous, in which the players’ utilities, although potentially different, do not differentiate among the identities of the other players. Examples of such games arise in congestion, social interactions, and certain auction settings. This is joint work with Christos Papadimitriou, and partially Paul Goldberg. Biography: 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 California where he completed his doctorate studies in Computer Science at UC Berkeley under the supervision of Professor Christos Papadimitriou. 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. The Game Theory Society honored Costis and his collaborators, Paul Goldberg and Christos Papadimitriou, with the first Game Theory and Computer Science Prize for their work on the Computational Complexity of the Nash equilibrium. Costis was also the recipient of a Microsoft Research Fellowship in honor of Dean Richard Newton, and a UC Regents Fellowship. Costis will join the faculty at MIT as an Assistant Professor in EECS in fall 2009, after spending a year in nearby Microsoft Research New England. |
|
