Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics
This work addresses a foundational issue in game theory and computational economics by showing that Nash equilibria are incomplete predictors of long-term behavior, which is significant for researchers and practitioners in these fields, though it is incremental in extending impossibility results.
The paper tackles the problem of whether players' behaviors in repeated games converge to Nash equilibria under any dynamics, proving a general impossibility result that some games have starting points that never reach a Nash equilibrium, and a stronger result showing that for ε-approximate Nash equilibria with ε up to 0.09, no dynamics can converge to them in a set of games with positive measure.
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 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 its 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.