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

Area of Science:

• Game Theory
• Computational Economics
• Mathematical Economics

Background:

• The best-response dynamic is a fundamental concept in game theory for analyzing strategic interactions.
• Understanding convergence properties is crucial for predicting outcomes in normal-form games.
• The impact of player action-updating sequences on convergence remains an active area of research.

Purpose of the Study:

• To investigate the performance of the best-response dynamic across all normal-form games.
• To determine the influence of playing sequence on convergence to Nash equilibrium.
• To compare convergence rates under fixed cyclic versus random playing sequences.

Main Methods:

• Analysis using a random games approach.
• Asymptotic analysis of game dynamics.
• Evaluation across all possible normal-form games.

Main Results:

• Convergence to a pure Nash equilibrium is extremely sensitive to the playing sequence.
• With a fixed cyclic playing order, the best-response dynamic converges in a vanishingly small fraction of large games.
• With a random playing sequence, the dynamic converges to a pure Nash equilibrium in almost all large games where one exists.

Conclusions:

• Randomized playing sequences significantly enhance the convergence of the best-response dynamic to Nash equilibria.
• The choice of playing sequence is a critical factor in the stability and predictability of game dynamics.
• These findings have implications for understanding emergent behavior in complex strategic environments.