Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics

03/26/2022
by   Jason Milionis, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset