Research map / Multi-agent systems and games / Games and equilibria
Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaos
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 statistical-mechanics average-case analysis of Q-Learning dynamics in random competitive network polymatrix games to derive a stability boundary in terms of payoff correlation, exploration rate and number of neighbours, showing stability depends on connectivity rather than total agent count.
Problem
Convergence of multi-agent Q-learning in generic (non-zero-sum) competitive network games is poorly understood, and prior analyses suggest instability grows with total number of agents.
Approach
Parameterise random network polymatrix games by payoff anti-correlation Gamma, derive an effective averaged Q-Learning dynamic via generating functionals in the large-action limit, and obtain a necessary stability condition that depends on the number of neighbours N_0 but not on the total number of agents N.
Key results
- The derived necessary stability condition depends on the number of neighbours N_0 and exploration rate T, and is independent of total agent count N.
- In the ring network, T approx 0.3 suffices for convergence of 50 agents in the Network Sato Game, while the fully connected network needs larger T that grows with N.
- Empirical non-convergence boundaries over random games agree qualitatively with the theoretical boundary; the theory overestimates the unstable region due to finite time horizons (75,000 steps).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a ring network instead of a fully connected network | Q-Learning in the Network Sato Game · Network Sato Game | exploration rate required for convergence: T \approx 0.3 vs. T=1 | Helped |
| Increase the number of agents while keeping ring connectivity fixed | Q-Learning in ring networks · Random finite games | stability boundary | No clear effect |
| Increase the number of agents in a fully connected network | Q-Learning in fully connected networks · Random finite games | non-convergent behavior at low exploration rates | Hurt |
| Decrease payoff anticorrelation, moving Γ from -1 toward 0 | Q-Learning dynamics · Competitive network games | exploration rate required for convergence | Hurt |
| Increase network connectivity | Q-Learning dynamics · Competitive network games | stability | Hurt |
| Keep each agent's neighbor count fixed while increasing total agent count | Q-Learning dynamics · Regular network games | stability boundary | No clear effect |
| Increase exploration rate as payoff anticorrelation decreases | Q-Learning dynamics · Random finite games | convergence to equilibrium | Helped |
| Evaluate the theoretical stability predictions in finite games | Q-Learning dynamics · Random finite games | agreement with predicted stability boundary | Helped |
Surprising findings
- Increasing the number of agents in a ring network does not change the stability boundary, while fully connected networks become less stable as N grows.
Limitations
- Analytic boundary holds exactly only in the limit of large action sets; finite-game predictions are approximate.
- Analysis restricted to regular networks where all agents share the same number of neighbours.
- Empirical non-convergence heuristic may mistake slow convergence for non-convergence and does not formally establish chaos.
Experimental setup
Datasets: randomly generated Gaussian payoff matrices in network games (Network Sato Game)
Benchmarks: Network Sato Game (ring and fully connected networks) random Gaussian network games
Metrics: probability of non-convergence convergence to QRE / stable fixed point
Baselines: fully connected network (N-1 neighbours) two-player game boundary
Builds on: Q-Learning dynamics (continuous-time approximation) Quantal Response Equilibrium generating functional approach for disordered systems Sato-style rock-paper-scissors game prior stability boundary analysis of multi-player games (Galla-Farmer style)
Closest papers by meaning
- The Impact of Exploration on Convergence and Performance of Multi-Agent Q-Learning Dynamics (ICML 2023 · similarity 0.93)
- Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality (NeurIPS 2021 · similarity 0.93)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.90)
- Asymptotic Extinction in Large Coordination Games (AAAI 2025 · similarity 0.88)
- Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium (AAAI 2025 · similarity 0.88)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · 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.