Asymptotic Extinction in Large Coordination Games

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

Abstract

We investigate the exploration-exploitation trade-off in large multiplayer coordination games where agents employ Q-Learning. While Q-Learning is a staple of multi-agent reinforcement learning (MARL), it often suffers from non-convergence and equilibrium selection issues in complex payoff landscapes. By applying dynamical mean-field theory from statistical physics, we characterize a critical exploration rate $T_{crit}$ that ensures convergence to a unique Quantal Response Equilibrium (QRE). Our analysis reveals a phenomenon termed "asymptotic extinction," where a constant fraction of actions are played with zero probability as the game size increases.

Introduction

In multi-agent reinforcement learning, the environment is non-stationary because agents' strategies evolve simultaneously. Q-Learning, which balances exploration (trying new actions) and exploitation (choosing high-reward actions), faces significant challenges in coordination games with multiple fixed points. As the number of players ($p$) and actions ($N$) scales, understanding the stability of these systems becomes critical. This study seeks to identify the "tipping point" of exploration required to guarantee a unique, stable equilibrium in high-dimensional action spaces.

Methodology

The research utilizes the generating-functional method, a technique from the physics of disordered systems, to derive the effective dynamics of a "typical" action in the limit of infinite actions ($N \to \infty$). To ensure generalizability, the authors analyze games with payoff matrices drawn from multivariate Gaussian distributions, allowing for the tuning of payoff alignment via a correlation parameter $\Gamma$. Theoretical results are validated against numerical simulations of games with up to $N=320$ actions across varying player counts ($p=2, 3, 5$).

Asymptotic Extinction and Scaling Laws

A primary finding is asymptotic extinction: in the large-action limit, even with exploration, a constant fraction of actions are effectively abandoned, receiving vanishingly small probability ($o(1/N)$). This suggests that large-scale coordination naturally narrows the effective strategy space. Furthermore, the study identifies that the exploration rate $T$ must be rescaled by $\sqrt{N^{p-1}}$ to maintain meaningful learning dynamics as the action space grows.

Figure 1: Empirical Cumulative Density of action probabilities. As the number of actions $N$ increases, the simulation results converge toward the theoretical extinction rate (red dashed line).

Stability and the Critical Exploration Rate

The authors identify a critical exploration rate ($T_{crit}$) above which the system is guaranteed to converge to a unique fixed point. Interestingly, coordination games ($\Gamma > 0$) are harder to stabilize than competitive ones, requiring roughly twice the exploration rate of zero-sum games for perfectly aligned payoffs. In the limit of many players, $T_{crit}$ follows a linear relationship: $T_{crit} \approx (\hat{\Gamma} + 1)\sqrt{e(p-1)}$.

Figure 4: Heatmaps of the $\log_{10}$ extinction rate for different player counts ($p$). The yellow dashed line represents the analytical stability boundary, separating the regime of unique convergence from regions of multiple equilibria or chaos.

Conclusion

This work provides a rigorous framework for understanding Q-Learning in large-scale multi-agent systems. While the theoretical $T_{crit}$ provides a safe bound for convergence, it assumes an infinite action space; in practice, finite-sized games may converge at slightly lower rates. Future research should explore the implications of these exploration rates on social welfare and the total utility achieved by the coordinating agents.

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