**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. |