Research map / Multi-agent systems and games / Games and equilibria
Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium
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.
Shows that in periodic zero-sum matrix games, GDA learning dynamics diverge from Nash equilibrium with non-convergent time-average when the game's oscillation frequency synchronizes with an integer multiple of the learning eigenvalue (alpha/omega in N), and otherwise cycle with convergent time-average.
Problem
Learning dynamics and time-average convergence in zero-sum games whose payoff matrices vary periodically, so the Nash equilibrium moves over time, remain poorly understood.
Approach
Identifies a synchronization phenomenon: when the game's periodic frequency relates to the learning eigenvalue by an integer ratio (alpha/omega in N), GDA dynamics diverge and their time-average fails to converge; otherwise the time-average converges. Proved via dynamical systems analysis for 2x2 smooth periodic games and verified experimentally for larger games and boundary constraints.
Key results
- In 2x2 smooth periodic zero-sum games, the paper proves time-average divergence when alpha/omega is an integer and time-average convergence when alpha/omega is not an integer.
- Experiments on 3x3 and 6x6 games show divergence occurs when alpha^(j)/omega is an integer for some eigenvalue j, and that the phenomenon persists with boundary constraints.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Synchronize the periodic-game frequency with the learning eigenvalue (α/ω = 1) | GDA in eigenvalue-invariant 2×2 periodic games · Periodic matching pennies | distance from Nash equilibrium | Hurt |
| Synchronize the periodic-game frequency with the learning eigenvalue (α/ω = 1) | GDA in eigenvalue-invariant 2×2 periodic games · Periodic matching pennies | time-average convergence | Hurt |
| Use a learning-to-game frequency ratio other than 1 (α/ω ≠ 1) | GDA in eigenvalue-invariant 2×2 periodic games · Periodic matching pennies | time-average convergence | Helped |
| Synchronize a learning eigenvalue with the game frequency (α/ω ∈ ℕ) | GDA in smooth periodic 2×2 games · Smooth periodic 2×2 games | time-average convergence | Hurt |
| Use a learning-to-game frequency ratio that is not an integer (α/ω ∉ ℕ) | GDA in smooth periodic 2×2 games · Smooth periodic 2×2 games | time-average convergence | Helped |
| Synchronize at least one learning eigenvalue with the game frequency (α⁽ʲ⁾/ω ∈ ℕ) | GDA in 3×3 periodic zero-sum games · 3×3 matrix games | distance from Nash equilibrium | Hurt |
| Avoid synchronization with every learning eigenvalue (α⁽ʲ⁾/ω ∉ ℕ) | GDA in 3×3 periodic zero-sum games · 3×3 matrix games | time-average convergence | Helped |
| Synchronize at least one learning eigenvalue with the game frequency (α⁽ʲ⁾/ω ∈ ℕ) | GDA in 6×6 periodic zero-sum games · 6×6 matrix games | distance from Nash equilibrium | Hurt |
| Add a boundary constraint to the strategy spaces | GDA in periodic games · Periodic games with boundary-constrained strategies | time-average convergence | Helped |
| Add a boundary constraint to the strategy spaces | GDA in periodic games · Periodic games with boundary-constrained strategies | oscillation amplitude near synchronization | Mixed |
Surprising findings
- When the integer ratio synchronization occurs, the time-average deviates from the Nash equilibrium of the averaged game even though the trajectory remains bounded only by the boundary constraint in the constrained case.
Limitations
- Theory limited to 2x2 matrix games, smooth periodic payoffs, and no boundary constraint.
- Analysis covers only GDA (FTRL with Euclidean regularizer), not other learning algorithms such as optimistic or extra-gradient methods.
Experimental setup
Metrics: time-average trajectory maximum trajectory value
Builds on: gradient descent-ascent follow the regularized leader
Closest papers by meaning
- Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games (AAAI 2024 · similarity 0.91)
- Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.88)
- Stability of Multi-Agent Learning in Competitive Networks: Delaying the Onset of Chaos (AAAI 2024 · similarity 0.88)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.88)
- The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.88)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.88)
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.