Algorithms may not learn to play a unique Nash equilibrium

Carsten Krabbe Nielsen, Takako Fujiwara-Greve

Risultato della ricerca: Contributo in rivistaArticolo in rivista

Abstract

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
DOI
Stato di pubblicazionePubblicato - 2021

Keywords

  • Algorithm
  • Impossibility
  • Nash equilibrium
  • Learning

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

Cita questo