The Frequency of Convergent Games under Best-Response Dynamics

Area of Science:

• Game Theory
• Computational Economics
• Mathematical Economics

Background:

• Normal-form games are fundamental in game theory for modeling strategic interactions.
• Pure strategy Nash equilibria represent stable outcomes where no player benefits from unilaterally changing their strategy.
• Understanding the frequency and convergence of these equilibria is crucial for predicting game outcomes.

Purpose of the Study:

• To calculate the frequency of games with a unique pure strategy Nash equilibrium in an ensemble of n-player, m-strategy normal-form games.
• To investigate the convergence properties of games under best-response dynamics.
• To analyze how the number of players and strategies influences the likelihood of unique versus multiple pure strategy Nash equilibria.

Main Methods:

• Generating random payoff matrices to create an ensemble of normal-form games.
• Analyzing games that converge to a Nash equilibrium under best-response dynamics.
• Utilizing an n-partite graph to represent and analyze the structure of these games.

Main Results:

• The frequency of convergent games with a specific number of pure Nash equilibria approaches zero as the number of players or strategies increases.
• In 2-player games with at least 10 strategies, games with multiple pure strategy Nash equilibria are more likely than those with a unique equilibrium.
• The study demonstrates a novel approach using n-partite graphs for game description.

Conclusions:

• The likelihood of unique pure strategy Nash equilibria diminishes in large, complex games.
• For 2-player games, multiple equilibria become more prevalent as the number of strategies grows.
• The findings offer insights into the distribution and convergence of Nash equilibria in strategic interactions.