Research map / Multi-agent systems and games / Games and equilibria
Asymptotic Extinction in Large Coordination Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses a generating-functional (DMFT) analysis of Q-Learning in large random Gaussian coordination games to derive a critical exploration rate for unique fixed point convergence and predict "asymptotic extinction" of actions.
Problem
Q-Learning in large multiplayer coordination games can fail to converge or converge to multiple quantal response equilibria depending on initial conditions; the exploration rate needed for convergence to a unique fixed point and the behaviour of Q-Learning as the number of actions grows are not well
Approach
Extends the generating-functional/DMFT analysis of competitive random games to positive payoff correlation (coordination games), introducing a support-fraction term phi to account for actions that go extinct, yielding a stability criterion and a critical exploration rate T_crit = (Γ̂+1)sqrt(e(p-1)).
Key results
- Theory predicts a stability boundary T_crit = (Γ̂+1)sqrt(e(p-1)); for pure coordination games the critical exploration rate is twice that of p-player zero-sum games in the large-p limit.
- Asymptotic extinction: a non-zero fraction of actions goes extinct in large coordination games; e.g. theoretical extinction rate of 0.74% at Γ=0, T=1.8, p=2.
- Simulations on finite games (p=2,N=50; p=3,N=12; p=5,N=4; 40 games per setting) broadly match the theoretical stability boundary, though theory overestimates T_crit near Γ=0.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the exploration rate T beyond the stability boundary | Q-Learning in coordination games · Large-action games, N → ∞ | extinction rate: decreases drastically | Helped |
| Increase the number of players p or payoff correlation Γ | Q-Learning in coordination games · Critical exploration-rate boundary | critical exploration rate: T_{crit} = (\hat{\Gamma} + 1) \sqrt{e(p-1)} | Hurt |
| Use pure coordination (identical payoffs) rather than p-player zero-sum payoffs | Q-Learning · Large-p games | critical exploration rate: twice | Hurt |
| Use positively aligned payoffs (Γ > 0) | Q-Learning effective dynamics · Large-action coordination games | stable interior fixed-point existence | Hurt |
| Use uncorrelated payoffs (Γ = 0) with T below the stated threshold | Q-Learning effective dynamics · Uncorrelated games | stable interior fixed-point existence: T < \sqrt{3e(p-1)/ 2} | Hurt |
| Compare the theoretical stability boundary with finite-size simulations | Q-Learning · Finite-sized coordination games, especially near Γ = 0 | critical exploration-rate estimate: overestimate | Mixed |
Surprising findings
- For coordination games the theory predicts no stable interior fixed point, only boundary fixed points, so a constant fraction of actions goes extinct even though QRE has full support in finite games.
- The critical exploration rate in pure coordination games is roughly twice that of p-player zero-sum games in the large-p limit.
Limitations
- Theoretical predictions are for the N to infinity limit and overestimate T_crit in finite games, especially near Γ=0.
- Simulation variance is higher for small N; extinction events are extraordinarily rare away from the stability boundary and hard to verify experimentally.
- Analysis restricted to continuous-time Q-Learning with Gaussian payoffs; universality to non-Gaussian payoffs is argued heuristically rather than proven.
Experimental setup
Metrics: proportion of random games converging to a unique fixed poin critical exploration rate T_crit proportion of extinct actions
Builds on: generating functional method for random replicator/Q-learning games quantal response equilibrium Q-learning
Closest papers by meaning
- Bounded Rationality Equilibrium Learning in Mean Field Games (AAAI 2025 · similarity 0.88)
- Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaos (AAAI 2024 · similarity 0.88)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.88)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.88)
- Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularization (ICML 2025 · similarity 0.87)
- A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.