SPECIAL TIME: 2:30 -- 3:30 pm, Wednesday, Feb 18, 2009

PLACE: CSE 503

SPEAKER: Costis Daskalakis, Microsoft Research and MIT

TITLE: The Structure and Complexity of Nash Equilibria

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 Brouwer
fixed-point computation problem, in a precise technical sense. The
existence of the Nash equilibrium is established via Brouwer's
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 running time
dependence on the approximation guarantee.