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’ 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 runnnig time dependence on the approximation guarantee.