Jason Milionis Columbia University jm@cs.columbia.edu Christos Papadimitriou Columbia University christos@columbia.edu Georgios Piliouras SUTD georgios@sutd.edu.sg Kelly Spendlove University of Oxford spendlove@maths.ox.ac.uk 

Abstract 

Under what conditions do the behaviors of players, who play a game repeatedly, converge to a Nash equilibrium? If one assumes that the players’ behavior is a discrete-time or continuous-time rule whereby the current mixed strategy profile is mapped to the next, this becomes a problem in the theory of dynamical systems. We apply this theory, and in particular, the concepts of chain recurrence, attractors, and Conley index, to prove a general impossibility result: there exist games for which any dynamics is bound to have starting points that do not end up at a Nash equilibrium. We also prove a stronger result for 𝜖-approximate Nash equilibria: there are games such that no game dynamics can converge (in an appropriate sense) to 𝜖-Nash equilibria, and in fact, the set of such games has a positive measure. Further numerical results demonstrate that this holds for any 𝜖 between zero and 0.09. Our results establish that, although the notions of Nash equilibria (and their computation-inspired approximations) are universally applicable in all games, they are also fundamentally incomplete as predictors of long-term behavior, regardless of the choice of dynamics.