Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System

James P. Bailey, Georgios Piliouras

Introduction

In classical game theory, the Nash equilibrium is the gold standard for predicting agent behavior. However, in competitive zero-sum environments like Rock-Paper-Scissors or Matching Pennies, simple learning algorithms often fail to converge to these static points. Instead, they exhibit perpetual oscillatory or divergent behavior. This research establishes a formal mathematical bridge between game theory and classical physics, proving that multi-agent learning in zero-sum games is a Hamiltonian system.

The Limitations of Static Equilibrium

Standard learning algorithms, such as Gradient Descent, often cycle or spiral outwards in competitive games. Treating these systems as static is insufficient; just as it would be useless to describe the Earth-Moon system as a single static point, it is often necessary to describe competitive learning through its dynamic trajectories. The authors address the lack of a framework that explains why these non-convergent behaviors occur and how they relate to the fundamental laws of dynamical systems.

Mapping Games to Physics: The Hamiltonian Framework

The researchers focus on a broad class of learning algorithms called Follow-the-Regularized-Leader (FTRL). Their key innovation is the construction of a mapping that translates game-theoretic variables into physical ones, effectively creating a "Rosetta Stone" for competitive learning.

The 'Rosetta Stone' mapping game-theoretic variables to physical ones.

In this framework:

  • Position ($q$): Corresponds to an agent's cumulative strategy over time.
  • Momentum ($p$): Corresponds to the agent's current strategy or payoff vector.
  • Hamiltonian ($H$): Represents a "total energy" function derived from the agents' regularizers.

By applying Hamilton’s equations—the same mathematics used to describe a mass on a spring or a pendulum—the authors prove that the trajectories of agents using FTRL are identical to the trajectories of conservative physical systems.

Key Insights and Results

Conservation of "Game Energy"

In a zero-sum network game, there is a quantity (the Hamiltonian) that remains constant over time. This "energy" is directly related to the Bregman distance between the current strategies and the Nash equilibrium. Because energy is conserved, agents do not "fall into" the Nash equilibrium; instead, they orbit it at a constant "distance" determined by their starting conditions.

Poincaré Recurrence

The paper demonstrates that these systems are Poincaré recurrent. This means that if the system is observed for a sufficiently long period, the agents' strategies will eventually return arbitrarily close to their starting positions, explaining the observed "orbit" phenomenon.

The Discrete-Time Divergence

A crucial insight explains why discrete-time updates (like standard computer implementations of Gradient Descent) often spiral away from equilibrium. The authors show that discrete steps move tangentially to the energy curves, effectively "adding energy" to the system at every step, which leads to divergence.

Conclusion

This work formally proves that FTRL dynamics in two-player and network zero-sum games are Hamiltonian. It establishes that the distance to a fully-mixed Nash equilibrium is time-invariant in continuous time and provides a mathematical explanation for the divergence seen in discrete-time simulations. While the Hamiltonian connection is strongest in zero-sum and coordination games, future work may extend these findings to general-sum games and explore "symplectic integrators" to preserve physical properties in discrete-time implementations.

Summary updated

Abstract

Zero-sum games are natural, if informal, analogues of closed physical systems where no energy/utility can enter or exit. This analogy can be extended even further if we consider zero-sum network (polymatrix) games where multiple agents interact in a closed economy. Typically, (network) zero-sum games are studied from the perspective of Nash equilibria. Nevertheless, this comes in contrast with the way we typically think about closed physical systems, e.g., Earth-moon systems which move perpetually along recurrent trajectories of constant energy. We establish a formal and robust connection between multi-agent systems and Hamiltonian dynamics -- the same dynamics that describe conservative systems in physics. Specifically, we show that no matter the size, or network structure of such closed economies, even if agents use different online learning dynamics from the standard class of Follow-the-Regularized-Leader, they yield Hamiltonian dynamics. This approach generalizes the known connection to Hamiltonians for the special case of replicator dynamics in two agent zero-sum games developed by Hofbauer. Moreover, our results extend beyond zero-sum settings and provide a type of a Rosetta stone (see e.g. Table 1) that helps to translate results and techniques between online optimization, convex analysis, games theory, and physics.
BibTeX
@inproceedings{bailey2019multi,
  author = {James P. Bailey and Georgios Piliouras},
  title = {{Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System}},
  booktitle = {AAMAS},
  year = {2019},
  url = {https://openreview.net/forum?id=PrtXXbOb-sm},
}
Figure