Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium

Yuma Fujimoto, Kaito Ariu, Kenshi AbeAAAI 2025 · OpenReview

Abstract

Learning in zero-sum games studies a situation where multiple agents competitively learn their strategy. In such multi-agent learning, we often see that the strategies cycle around their optimum, i.e., Nash equilibrium. When a game periodically varies (called a "periodic" game), however, the Nash equilibrium moves generically. How learning dynamics behave in such periodic games is of interest but still unclear. Interestingly, we discover that the behavior is highly dependent on the relationship between the two speeds at which the game changes and at which players learn. We observe that when these two speeds synchronize, the learning dynamics diverge, and their time-average does not converge. Otherwise, the learning dynamics draw complicated cycles, but their time-average converges. Under some assumptions introduced for the dynamical systems analysis, we prove that this behavior occurs. Furthermore, our experiments observe this behavior even if these assumptions are removed. This study discovers a novel phenomenon, i.e., synchronization, and gains insight widely applicable to learning in periodic games.

Introduction

Multi-agent learning in competitive environments is a cornerstone of game theory and machine learning. In classic zero-sum games, such as Rock-Paper-Scissors, learning algorithms like Gradient Descent-Ascent (GDA) typically result in strategies that cycle around a stable center—the Nash Equilibrium (NE). While the instantaneous strategies do not settle on a single point, their time-average is known to converge to the NE in static settings.

However, the real world is rarely static. Many systems, from daily electricity markets to seasonal trading cycles, exhibit periodic fluctuations. This paper addresses a more realistic and complex scenario: periodic zero-sum games where the Nash Equilibrium itself moves over time. The authors discover a "synchronization" phenomenon where the relationship between the learning speed and the game's frequency determines whether the system remains stable or diverges away from the target equilibrium.

Methodology: Learning as a Dynamical System

The researchers employ dynamical systems analysis to study the trajectories of GDA in periodic games. By representing the learning process as a system of differential equations, they identify two critical parameters:

  1. Natural Frequency ($\alpha$): The internal speed at which players' strategies naturally cycle around the NE.
  2. Game Frequency ($\omega$): The speed at which the game's payoffs (and thus the NE) oscillate.

For $2 \times 2$ matrix games, the authors derive closed-form solutions, revealing a mathematical analogy to a forced pendulum without dissipation. In this analogy, the moving NE acts as an external periodic force pushing the "pendulum" of the learning dynamics. If the push occurs at the right frequency, the amplitude of the swing grows uncontrollably.

The Synchronization Phenomenon

The core finding is that the stability of the learning process depends on the ratio $\alpha/\omega$. When this ratio is an integer (e.g., 1, 2, 3...), the system enters a state of resonance.

Figure 1: Trajectories of learning dynamics in periodic games. (A) 3D trajectories in (x, y, z) space for different learning-to-game frequency ratios. (B) 2D projections onto the strategy plane. When the speeds synchronize (alpha/omega = 1), the dynamics spiral outward and fail to converge.

As shown in Figure 1, when the learning speed matches the game frequency ($\alpha/\omega = 1$), the strategy trajectories spiral outward. This resonance causes the amplitude of the cycles to grow over time, leading to divergence from the average NE. In contrast, when the speeds are mismatched (e.g., $\alpha/\omega = 10$ or $2/3$), the trajectories remain bounded in complex but stable cycles, allowing the time-average to converge.

Key Results and Resonance Peaks

The authors formalize these observations through several theorems, proving that in smooth periodic games, synchronization at integer ratios leads to divergence at a speed proportional to time ($O(t)$).

Figure 4: Resonance effects in 2x2 games. (A) Maximum and minimum strategy values vs. game frequency omega. Divergence (hitting boundaries 0 and 1) occurs at omega = alpha and its subharmonics. (B) The time-average strategy shows a sharp discontinuity and divergence near the synchronization point.

Figure 4 illustrates the quantitative impact of this resonance. In panel A, we see that the strategy values hit the boundaries (0 and 1) precisely when the game frequency $\omega$ aligns with the natural frequency $\alpha$ (here $\alpha=2$) or its subharmonics. Panel B demonstrates that the time-average strategy, which is usually a reliable proxy for the NE, fails to converge and exhibits extreme sensitivity near these synchronization points.

Higher Dimensions and Strategy Boundaries

The phenomenon extends to higher-dimensional games (e.g., $3 \times 3$ and $6 \times 6$). In these cases, the system possesses multiple eigenvalues, each representing a potential resonance frequency. Divergence can be triggered if the game frequency synchronizes with any of these internal frequencies, creating a spectrum of unstable points.

The paper also explores the effect of strategy boundaries—the physical constraint that probabilities must stay between 0 and 1. While these boundaries prevent strategies from diverging to infinity, the underlying "desire" to diverge remains. Interestingly, these constraints can force the time-average to converge, but the resulting average may still differ significantly from the intended Nash Equilibrium.

Conclusion

This study identifies synchronization as a fundamental trigger for divergence in periodic multi-agent learning. The discovery that learning speed must be carefully tuned relative to environmental changes has broad implications for designing robust algorithms in dynamic markets and competitive AI scenarios. Future work will investigate whether these effects persist in general-sum games and how advanced algorithms like Optimistic GDA might mitigate resonance-induced instability.

Summary updated

Abstract

Learning in zero-sum games studies a situation where multiple agents competitively learn their strategy. In such multi-agent learning, we often see that the strategies cycle around their optimum, i.e., Nash equilibrium. When a game periodically varies (called a ``periodic'' game), however, the Nash equilibrium moves generically. How learning dynamics behave in such periodic games is of interest but still unclear. Interestingly, we discover that the behavior is highly dependent on the relationship between the two speeds at which the game changes and at which players learn. We observe that when these two speeds synchronize, the learning dynamics diverge, and their time-average does not converge. Otherwise, the learning dynamics draw complicated cycles, but their time-average converges. Under some assumptions introduced for the dynamical systems analysis, we prove that this behavior occurs. Furthermore, our experiments observe this behavior even if these assumptions are removed. This study discovers a novel phenomenon, i.e., synchronization, and gains insight widely applicable to learning in periodic games.
BibTeX
@inproceedings{fujimoto2025synchronization,
  author = {Yuma Fujimoto and Kaito Ariu and Kenshi Abe},
  title = {{Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=SCX8thzobB},
}
Figure