Abstract :

How long does it take a market or, more broadly, a game to reach an equilibrium state? I will present joint work with Paul Goldberg and Christos Papadimitriou, showing that convergence to a Nash equilibrium may take prohibitively long. Since a Nash equilibrium is guaranteed to exist in every game---by Nash's seminal result, NP-completeness does not seem appropriate for characterizing its complexity. Our result is that the Nash equilibrium is as hard computationally as the general Brouwer fixed-point computation problem, in a precise technical sense. The existence of the Nash equilibrium is established via Brouwer fixed-point theorem; hence our result is the computational converse of Nash's theorem.

To alleviate the negative implications of this hardness result for the predictive power of the Nash equilibrium, it is important to study the computation of approximate equilibria: an efficient approximation scheme would imply that games can in principle come arbitrarily close to a Nash equilibrium in a sufficiently large number of game-plays. I will discuss such polynomial-time approximation schemes for special classes of two-player games and describe obstacles towards obtaining a polynomial-time approximation scheme for the general two-player case. I will then turn to a large and important class of multi-player games, called anonymous, in which the players's utilities, although potentially different, do not differentiate among the identities of the other players; examples arise in congestion, social interactions, and certain auction settings. I will present several approaches for approximating multi-player anonymous games with two strategies, culminating in an efficient PTAS with quasi-polynomial dependence on the approximation.

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 EECS faculty at MIT as an Assistant Professor in fall 2009, while spending this year at Microsoft Research-New England.