Asymptotic Extinction in Large Coordination Games

Desmond Chan, Bart de Keijzer, Tobias Galla, Stefanos Leonardos, Carmine Ventre

Abstract

This study identifies and analyzes the phenomenon of asymptotic extinction in large multi-agent coordination games. By applying tools from statistical physics and dynamical systems, the authors demonstrate that as the action space grows, a constant fraction of possible actions are effectively abandoned by Q-learning agents. The research derives a theoretical "critical exploration rate" ($T_{crit}$) that guarantees convergence to a unique stable equilibrium, providing a roadmap for managing the exploration-exploitation trade-off in complex multi-agent environments.

Introduction: The Challenges of Large-Scale MARL

In Multi-Agent Reinforcement Learning (MARL), agents typically employ Q-learning to navigate strategic environments. However, these systems often suffer from non-convergence (oscillations or chaos) and poor equilibrium selection, where agents settle on sub-optimal outcomes. While these issues are well-documented in competitive zero-sum games, the behavior in large coordination games—where players' interests are aligned—has remained poorly understood. Specifically, it was unclear how many actions remain viable as the number of possible actions ($N$) becomes very large.

Methodology

The authors utilize a sophisticated toolkit to analyze these dynamics:

  • Continuous Q-Learning: Discrete learning steps are modeled as continuous-time differential equations to study long-term stability.
  • Dynamical Mean-Field Theory: Borrowing from disordered systems theory in physics, the authors analyze "typical" game behavior using payoffs drawn from multivariate Gaussian distributions.
  • Alignment Parameter ($\Gamma$): A correlation parameter controls the degree of payoff alignment, ranging from competitive ($\Gamma < 0$) to perfectly coordinated ($\Gamma > 0$).

The Phenomenon of Asymptotic Extinction

A striking insight from this work is that in the large-game limit ($N \to \infty$), a non-zero fraction of actions are played with a frequency of $o(1/N)$. Effectively, these actions "go extinct," mirroring biological evolution where less-fit species are pruned from the population. This suggests that even with high exploration, the equilibrium of a large coordination game naturally pushes toward the boundary of the action simplex.

Empirical validation of asymptotic extinction rates across different action space sizes $N$. The data shows convergence toward the theoretical prediction as $N$ increases.

Stability Thresholds and Scaling Laws

The research successfully maps the "stability boundary" for these games. To the right of this boundary (high exploration $T$), Q-learning always converges to a unique point. To the left (low exploration), the system can fall into multiple fixed points or limit cycles.

Key findings regarding these thresholds include:

  • The Cost of Coordination: In perfectly aligned games, the exploration rate required for stability is roughly twice as high as in zero-sum games.
  • Linear Scaling: The critical exploration rate follows a clean relationship: $T_{crit} \approx (\hat{\Gamma} + 1)\sqrt{e(p-1)}$, where $p$ is the number of players.
Phase diagram for $p=5$ players showing the stability boundary (dashed line) and $\log_{10}$ extinction rates across different values of payoff correlation $\Gamma$ and exploration $T$.

Conclusion and Future Directions

Numerical simulations with up to $N=160$ actions confirm that these theoretical $N \to \infty$ predictions hold remarkably well for finite games. While this work establishes the $T$ required for stability, the authors note that this may not be the same $T$ that maximizes total social welfare. Future research will investigate heterogeneous agents and the optimization of exploration rates for specific objective functions, such as system efficiency or minimum utility.

Summary updated

Abstract

We study the exploration-exploitation trade-off for large multiplayer coordination games where players strategise via Q-Learning, a common learning framework in multi-agent reinforcement learning. Q-Learning is known to have two shortcomings, namely non-convergence and potential equilibrium selection problems, when there are multiple fixed points, called Quantal Response Equilibria (QRE). Furthermore, whilst QRE have full support for finite games, it is not clear how Q-Learning behaves as the game becomes large. In this paper, we characterise the critical exploration rate that guarantees convergence to a unique fixed point, addressing the two shortcomings above. Using a generating-functional method, we show that this rate increases with the number of players and the alignment of their payoffs. For many-player coordination games with perfectly aligned payoffs, this exploration rate is roughly twice that of $p$-player zero-sum games. As for large games, we provide a structural result for QRE, which suggests that as the game size increases, Q-Learning converges to a QRE near the boundary of the simplex of the action space, a phenomenon we term asymptotic extinction, where a constant fraction of the actions are played with zero probability at a rate $o(1/N)$ for an $N$-action game.
BibTeX
@inproceedings{chan2025asymptotic,
  author = {Desmond Chan and Bart de Keijzer and Tobias Galla and Stefanos Leonardos and Carmine Ventre},
  title = {{Asymptotic Extinction in Large Coordination Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33495},
}
Figure