An impossibility theorem in game dynamics

Jason Milionis (), Christos Papadimitriou (), Georgios Piliouras () and Kelly Spendlove ()
Additional contact information
Jason Milionis: a Department of Computer Science , Columbia University , New York , NY 10027
Christos Papadimitriou: a Department of Computer Science , Columbia University , New York , NY 10027
Georgios Piliouras: b Google DeepMind , London EC4A 3TW , United Kingdom
Kelly Spendlove: c Google , Mountain View , CA 94043

Proceedings of the National Academy of Sciences, 2023, vol. 120, issue 41, e2305349120

Abstract:

The Nash equilibrium—a, combination of choices by the players of a game from which no self-interested player would deviate—is the predominant solution concept in game theory. Even though every game has a Nash equilibrium, it is not known whether there are deterministic behaviors of the players who play a game repeatedly that are guaranteed to converge to a Nash equilibrium of the game from all starting points. 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 question becomes a problem in the theory of dynamical systems. We apply this theory, and in particular Conley index theory, to prove a general impossibility result: There exist games, for which all game dynamics fail to converge to Nash equilibria from all starting points. The games which help prove this impossibility result are degenerate, but we conjecture that the same result holds, under computational complexity assumptions, for nondegenerate games. We also prove a stronger impossibility result for the solution concept of approximate Nash equilibria: For a set of games of positive measure, no game dynamics can converge to the set of approximate Nash equilibria for a sufficiently small yet substantial approximation bound. Our results establish that, although the notions of Nash equilibrium and its computation-inspired approximations are universally applicable in all games, they are fundamentally incomplete as predictors of long-term player behavior.

Keywords: game theory; dynamical systems; Nash equilibrium; solution concept (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1073/pnas.2305349120 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nas:journl:v:120:y:2023:p:e2305349120

Access Statistics for this article

More articles in Proceedings of the National Academy of Sciences from Proceedings of the National Academy of Sciences
Bibliographic data for series maintained by PNAS Product Team ().