Research map / Multi-agent systems and games / Games and equilibria

Memory Asymmetry Creates Heteroclinic Orbits to Nash Equilibrium in Learning in Zero-Sum Games

AAAI 2024 · Multi-agent systems and games › Games and equilibria · approach: Opponent modeling in competitive games · 1 citations (OpenAlex)

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.

Studies gradient-ascent learning in zero-sum games where one agent has a longer memory than the other, showing heteroclinic dynamics that converge locally to Nash equilibria in two-action games and numerically in larger games.

Problem

Learning dynamics in zero-sum games where agents have memory are complex (chaos, divergence from Nash equilibrium), and the effect of asymmetric memory capacity on convergence to Nash equilibrium is unclear.

Approach

Formulates multi-memory gradient ascent (MMGA) for agents with asymmetric memory lengths; the longer-memory agent learns to exploit the other, which makes the shorter-memory agent's utility strictly concave and induces local convergence to the original Nash equilibrium, unlike cycling or divergence under symmetric memory.

Key results

• In two-action zero-sum games with memory lengths (1,0), the original Nash equilibrium splits into unstable and stable fixed points; the stable ones are locally asymptotically stable when the concavity condition -x̃1x4+x̃2x3>0 holds.
• Numerical simulations show last-iterate convergence to the Nash equilibrium across memory settings (1,0), (2,0), (2,1), and action numbers m=3 (rock-paper-scissors) and m=4, with 50 random initial strategies per case.
• With symmetric no-memory play, learning cycles around the Nash equilibrium; with symmetric one-memory play it diverges, while asymmetry yields convergence.

Measured effects reported in the paper

Surprising findings

• Asymmetric memory alone, without modifying the learning algorithm, yields convergence to Nash equilibrium in zero-sum games where symmetric memory diverges.

Limitations

• Theoretical local convergence proven only for two-action zero-sum games with memory lengths one and zero.
• Extension to general m-action games and longer memories is supported only numerically and by a conjecture.

Experimental setup

Metrics: KL divergence to original Nash equilibrium eigenvalues of the Jacobian (local stability)

Baselines: gradient ascent without memory (normal-form games) symmetric-memory gradient ascent

Builds on: replicator dynamics gradient ascent in games continualized MMGA

Closest papers by meaning

• Synchronization in Learning in Periodic Zero-Sum Games Triggers Divergence from Nash Equilibrium (AAAI 2025 · similarity 0.91)
• Convergence of No-Swap-Regret Dynamics in Self-Play (NeurIPS 2024 · similarity 0.90)
• Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions (NeurIPS 2024 · similarity 0.89)
• No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.88)
• The impact of uncertainty on regularized learning in games (ICML 2025 · similarity 0.88)
• Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.88)