Algorithms may not learn to play a unique Nash equilibrium

Takako Fujiwara-Greve, Carsten Krabbe Nielsen

Research output: Contribution to journalArticlepeer-review


There is a widespread hope that, in the near future, algorithms become so sophisticated that “solutions” to most problems are found by machines. In this note, we throw some doubts on this expectation by showing the following impossibility result: given a set of finite-memory, finite-iteration algorithms, a continuum of games exist, whose unique and strict Nash equilibrium cannot be reached from a large set of initial states. A Nash equilibrium is a social solution to conflicts of interest, and hence finite algorithms should not be always relied upon for social problems. Our result also shows how to construct games to deceive a given set of algorithms to be trapped in a cycle without a Nash equilibrium.

Original languageEnglish
Pages (from-to)839-850
Number of pages12
JournalJournal of Computational Social Science
Issue number2
Publication statusPublished - 2021 Nov


  • Algorithm
  • Impossibility
  • Learning
  • Nash equilibrium

ASJC Scopus subject areas

  • Transportation
  • Artificial Intelligence


Dive into the research topics of 'Algorithms may not learn to play a unique Nash equilibrium'. Together they form a unique fingerprint.

Cite this