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

Torsten Heinrich, Yoojin Jang, Luca Mungo, Marco Pangallo (marco.pangallo@santannapisa.it), Alex Scott, Bassel Tarbush and Samuel Wiese

Papers from arXiv.org

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.

Date: 2021-01, Revised 2022-11
New Economics Papers: this item is included in nep-exp, nep-gth, nep-mic and nep-spo
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2101.04222 Latest version (application/pdf)

Related works:
Working Paper: Best-Response Dynamics, Playing Sequences, And Convergence To Equilibrium In Random Games (2021)
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:arx:papers:2101.04222

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators (help@arxiv.org).