Algorithms may not learn to play a unique Nash equilibrium

Takako Fujiwara-Greve, Carsten Krabbe Nielsen

Risultato della ricerca: Contributo in rivistaArticolo in rivista


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.
Lingua originaleEnglish
pagine (da-a)N/A-N/A
RivistaJournal of Computational Social Science
Stato di pubblicazionePubblicato - 2021


  • Algorithm
  • Impossibility
  • Learning
  • Nash equilibrium


Entra nei temi di ricerca di 'Algorithms may not learn to play a unique Nash equilibrium'. Insieme formano una fingerprint unica.

Cita questo