Best-response dynamics, playing sequences, and convergence to equilibrium in random games

Torsten Heinrich (), Yoojin Jang (), Luca Mungo (), Marco Pangallo (), Alex Scott (), Bassel Tarbush () and Samuel Wiese ()
Additional contact information
Torsten Heinrich: Chemnitz University of Technology
Yoojin Jang: University of Oxford
Luca Mungo: University of Oxford
Marco Pangallo: CENTAI Institute
Alex Scott: University of Oxford
Bassel Tarbush: University of Oxford
Samuel Wiese: University of Oxford

International Journal of Game Theory, 2023, vol. 52, issue 3, No 4, 703-735

Abstract: Abstract We analyze the performance of the best-response dynamic across all normal-form games using a random games approach. The playing sequence—the order in which players update their actions—is essentially irrelevant in determining whether the dynamic converges to a Nash equilibrium in certain classes of games (e.g. in potential games) but, when evaluated across all possible games, convergence to equilibrium depends on the playing sequence in an extreme way. Our main asymptotic result shows that the best-response dynamic converges to a pure Nash equilibrium in a vanishingly small fraction of all (large) games when players take turns according to a fixed cyclic order. By contrast, when the playing sequence is random, the dynamic converges to a pure Nash equilibrium if one exists in almost all (large) games.

Keywords: Best-response dynamics; Equilibrium convergence; Random games (search for similar items in EconPapers)
JEL-codes: C62 C72 C73 D83 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s00182-023-00837-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jogath:v:52:y:2023:i:3:d:10.1007_s00182-023-00837-4

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-023-00837-4

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().