Best-Response Dynamics, Playing Sequences, And Convergence To Equilibrium In Random Games

Marco Pangallo (), Torsten Heinrich, Yoojin Jang, Alex Scott, Bassel Tarbush, Samuel Wiese and Luca Mungo

INET Oxford Working Papers from Institute for New Economic Thinking at the Oxford Martin School, University of Oxford

Abstract: We show that the playing sequence–the order in which players update their actions–is a crucial determinant of whether the best-response dynamic converges to a Nash equilibrium. Specifically, we analyze the probability that the best-response dynamic converges to a pure Nash equilibrium in random n-player m-action games under three distinct playing sequences: clockwork sequences (players take turns according to a fixed cyclic order), random sequences, and simultaneous updating by all players. We analytically characterize the convergence properties of the clockwork sequence best-response dynamic. Our key asymptotic result is that this dynamic almost never converges to a pure Nash equilibrium when n and m are large. By contrast, the random sequence best-response dynamic converges almost always to a pure Nash equilibrium when one exists and n and m are large. The clockwork best-response dynamic deserves particular attention: we show through simulation that, compared to random or simultaneous updating, its convergence properties are closest to those exhibited by three popular learning rules that have been calibrated to human game-playing in experiments (reinforcement learning, fictitious play, and replicator dynamics).

Keywords: Best-response dynamics; equilibrium convergence; random games; learning models in games (search for similar items in EconPapers)
JEL-codes: C62 C72 C73 D83 (search for similar items in EconPapers)
Pages: 58 pages
Date: 2021-01
New Economics Papers: this item is included in nep-exp, nep-gth, nep-isf, nep-mic and nep-spo
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.inet.ox.ac.uk/files/paper.pdf (application/pdf)

Related works:
Working Paper: Best-response dynamics, playing sequences, and convergence to equilibrium in random games (2022)
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:amz:wpaper:2021-02

Access Statistics for this paper

More papers in INET Oxford Working Papers from Institute for New Economic Thinking at the Oxford Martin School, University of Oxford Contact information at EDIRC.
Bibliographic data for series maintained by INET Oxford admin team ().