The Complexity of Nash Equilibria in Large Games

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.