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

Arbeitspapier

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).

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Series: LEM Working Paper Series ; No. 2021/02

Klassifikation und Themen

• Klassifikation: Wirtschaft ; Existence and Stability Conditions of Equilibrium ; Noncooperative Games ; Stochastic and Dynamic Games; Evolutionary Games; Repeated Games ; Search; Learning; Information and Knowledge; Communication; Belief; Unawareness
• Thema: Best-response dynamics ; equilibrium convergence ; random games ; learning models in games

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Heinrich, Torsten ; Jang, Yoojin ; Mungo, Luca ; Pangallo, Marco ; Scott, Alex ; Tarbush, Bassel ; Wiese, Samuel
• Ereignis: Veröffentlichung
• (wer): Scuola Superiore Sant'Anna, Laboratory of Economics and Management (LEM)
• (wo): Pisa
• (wann): 2021

Weitere Informationen

• Handle: http://hdl.handle.net/10419/243498
• Letzte Aktualisierung: 10.03.2025, 11:44 MEZ