Algorithms may not learn to play a unique Nash equilibrium

Carsten Krabbe Nielsen, Takako Fujiwara-Greve

Research output: Contribution to journalArticle

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.
Original languageEnglish
Pages (from-to)N/A-N/A
JournalJOURNAL OF COMPUTATIONAL SOCIAL SCIENCE
DOIs
Publication statusPublished - 2021

Keywords

  • Algorithm
  • Impossibility
  • Nash equilibrium
  • Learning

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

Cite this