2021/02 | LEM Working Paper Series | ||||||||||||||||
![]() |
|||||||||||||||||
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 |
|||||||||||||||||
Keywords | |||||||||||||||||
![]() |
![]() |
||||||||||||||||
Best-response dynamics; equilibrium convergence; random games; learning models in games.
|
|||||||||||||||||
JEL Classifications | |||||||||||||||||
![]() |
![]() |
||||||||||||||||
C62, C72, C73, D83
|
|||||||||||||||||
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).
|
Downloads
|
![]() ![]() |
|
![]()
|
![]() |