Memory Asymmetry: A Key to Convergence in Zero-Sum Games

Yuma Fujimoto, Kaito Ariu, Kenshi Abe

Abstract

Learning in games considers how multiple agents maximize their own rewards through repeated games. Memory, the ability of an agent to change their action depending on the history of actions in previous games, is often introduced into learning to explore more clever strategies and discuss the decision-making of real agents like humans. However, such games with memory are hard to analyze because they exhibit complex phenomena like chaotic dynamics or divergence from Nash equilibrium. In particular, how asymmetry in memory capacities between agents affects learning in games is still unclear. In response, this study formulates a gradient ascent algorithm in games with asymmetry memory capacities. To obtain theoretical insights into learning dynamics, we first consider a simple case of zero-sum games. We observe complex behavior, where learning dynamics draw a heteroclinic connection from unstable fixed points to stable ones. Despite this complexity, we analyze learning dynamics and prove local convergence to these stable fixed points, i.e., the Nash equilibria. We identify the mechanism driving this convergence: an agent with a longer memory learns to exploit the other, which in turn endows the other's utility function with strict concavity. We further numerically observe such convergence in various initial strategies, action numbers, and memory lengths. This study reveals a novel phenomenon due to memory asymmetry, providing fundamental strides in learning in games and new insights into computing equilibria.

Introduction

In game theory, the Nash Equilibrium (NE) is the ideal state where no player can improve their payoff by unilaterally changing their strategy. However, reaching this equilibrium through learning is notoriously difficult, especially in zero-sum games where one player's gain is another's loss. Standard learning algorithms, such as gradient ascent or replicator dynamics, typically fail to converge in these scenarios, instead resulting in endless cycles or chaotic divergence.

While researchers have explored adding "memory"—allowing agents to base current moves on past actions—to improve strategy, symmetric memory often exacerbates instability. This paper investigates a novel solution: memory asymmetry. By providing one agent with a longer memory than their opponent, the learning dynamics are pulled toward the Nash Equilibrium through "heteroclinic orbits," effectively stabilizing a system that is otherwise prone to divergence.

Comparison of learning dynamics: no memory (cycles), symmetric memory (chaos), and asymmetric memory (convergence).

Methodology

The researchers formulated a learning framework called Discretized Multi-Memory Gradient Ascent (MMGA). The methodology involves:

  1. Markovian Modeling: The game is treated as a Markov Transition Process. Because memory-based agents base their current moves on previous rounds, the state of the game evolves as a sequence of past actions.
  2. Strategy Representation: The study utilizes "marginalized strategies" to map high-dimensional memory-based strategies back into a simpler space that can be directly compared to the original (no-memory) Nash Equilibrium.
  3. Theoretical Analysis: Focusing on 2-player, 2-action zero-sum games (like Matching Pennies), the authors used linear stability analysis to examine the eigenvalues of the Jacobian matrix, proving the conditions under which the system settles into equilibrium.
  4. Simulations: The theory was validated through numerical simulations on 3-action (Rock-Paper-Scissors) and 4-action games with varying memory lengths.
Schematic representation of the normal-form game with memory-dependent states and transitions.

Key Insights and Results

Exploitation as a Stabilizer

The most counter-intuitive finding of this study is that exploitation leads to stability. When an agent with longer memory learns to exploit an opponent with shorter memory, it effectively "shapes" the opponent's utility function. This exploitation makes the opponent's utility function strictly concave, which naturally pushes them toward their minimax strategy—the Nash Equilibrium.

The Necessity of Asymmetry

In symmetric cases (where both agents have no memory or equal memory), the system typically cycles or diverges into chaos. The difference in memory capacity breaks this symmetry, creating a path to convergence. The paper identifies "heteroclinic connections," where the learning path starts near an unstable fixed point and is directed toward a stable one.

Mathematical and Numerical Validation

  • Stability Proof: The authors proved that the original Nash Equilibrium is divided into stable and unstable regions. If agents enter the stable region, convergence is guaranteed.
  • Local Asymptotic Stability: Theorem 4 in the study demonstrates that for any Nash Equilibrium satisfying a specific exploitation condition, the learning dynamics are locally stable.
  • Broad Applicability: Simulations confirmed that even in complex configurations (e.g., 4-action games or varying memory lengths), agents eventually reached the Nash Equilibrium, though convergence speed decreases as the strategy space expands.

Discussion and Future Work

While this study provides a formal proof for local stability, a mathematical proof for global convergence (starting from any initial strategy) remains an open challenge. Furthermore, the current model assumes a stationary state between updates; rapid strategy changes might yield different dynamics.

Future research could extend these findings to general-sum games, such as the Prisoner's Dilemma, to see if memory asymmetry encourages cooperation. Practically, these insights could improve AI training, such as stabilizing Generative Adversarial Networks (GANs) by intentionally introducing asymmetry between the generator and discriminator.

Summary updated

Abstract

Learning in games considers how multiple agents maximize their own rewards through repeated games. Memory, an ability that an agent changes his/her action depending on the history of actions in previous games, is often introduced into learning to explore more clever strategies and discuss the decision-making of real agents like humans. However, such games with memory are hard to analyze because they exhibit complex phenomena like chaotic dynamics or divergence from Nash equilibrium. In particular, how asymmetry in memory capacities between agents affects learning in games is still unclear. In response, this study formulates a gradient ascent algorithm in games with asymmetry memory capacities. To obtain theoretical insights into learning dynamics, we first consider a simple case of zero-sum games. We observe complex behavior, where learning dynamics draw a heteroclinic connection from unstable fixed points to stable ones. Despite this complexity, we analyze learning dynamics and prove local convergence to these stable fixed points, i.e., the Nash equilibria. We identify the mechanism driving this convergence: an agent with a longer memory learns to exploit the other, which in turn endows the other's utility function with strict concavity. We further numerically observe such convergence in various initial strategies, action numbers, and memory lengths. This study reveals a novel phenomenon due to memory asymmetry, providing fundamental strides in learning in games and new insights into computing equilibria.
BibTeX
@inproceedings{fujimoto2024memory,
  author = {Yuma Fujimoto and Kaito Ariu and Kenshi Abe},
  title = {{Memory Asymmetry: A Key to Convergence in Zero-Sum Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=0t62pZHksn},
}
Figure