Bridging Local Stability and Global Convergence in Games

This direction is split into other directions: global convergence gap. Its last version stays readable and citable here.

Version 1 of 141 papers44 conceptsfrozen 2026-10-04

In single-agent optimization, we are accustomed to the "bowl" intuition: if you drop a marble anywhere on a convex surface, it will eventually roll to the bottom. But in multi-agent systems—like training Generative Adversarial Networks (GANs) or coordinating autonomous vehicles—the landscape is no longer a static bowl. It is a shifting, swirling terrain where one player’s progress can be another’s setback.

The central challenge in this field is a persistent gap between local stability and global convergence. While we have become adept at proving that agents will stay at an equilibrium once they find it, we still struggle to guarantee they will ever find it in the first place.

The Local Success: Basins of Attraction

Most modern breakthroughs in game-theoretic optimization focus on local convergence. The goal is to prove that a Nash Equilibrium (NE) acts as a "sink" or an attractor. If agents are initialized within a specific neighborhood—a "basin of attraction"—their learning dynamics will inevitably pull them toward the equilibrium.

Lars M. Mescheder, Andreas Geiger, and Sebastian Nowozin demonstrated in Which Training Methods for GANs do actually Converge? that many GAN failures stem from a lack of local stability. They showed that even if a Nash Equilibrium exists, standard gradient descent might spiral away from it unless specific regularization is applied.

To fix this, researchers look at the "spectral shape" of the game—the eigenvalues of the Jacobian of the players' update rules. In Accelerating Smooth Games by Manipulating Spectral Shapes, Waïss Azizian and Gauthier Gidel argue that by reshaping these eigenvalues, we can transform a chaotic, oscillating system into one that converges rapidly. Similarly, Eric Mazumdar and Lillian J. Ratliff proved in Local Nash Equilibria are Isolated, Strict Local Nash Equilibria in 'Almost All' Zero-Sum Continuous Games that local equilibria are typically "hyperbolic," meaning they naturally attract gradient-based learners.

The Global Challenge: The Initialization Problem

The "marble in a bowl" intuition fails globally because multi-agent landscapes are rarely convex-concave. They are riddled with cycles, saddle points, and "fake" equilibria.

As Ross Allen and David Fridovich-Keil point out in Second-Order Algorithms for Finding Local Nash Equilibria in Zero-Sum Games, even sophisticated second-order methods that use curvature information are often only guaranteed to work if you start near the solution. If you initialize agents randomly—as is standard in deep learning—they may wander forever in non-convergent cycles or get trapped in sub-optimal regions.

This is the "Global Convergence" problem. Even when an algorithm like Consensus Multiplicative Weights Update (CMWU) by Nelson Vadori and Rahul Savani achieves "last-iterate convergence" (meaning the agents actually settle down rather than just averaging their behavior), that guarantee is often restricted to a local neighborhood.

Mechanisms for Expanding the Basin

To bridge this gap, researchers are developing mechanisms that make the "basin of attraction" larger or more accessible:

  1. Higher-Order Dynamics: In Higher-Order Uncoupled Learning Dynamics and Nash Equilibrium, Sarah Asad Toonsi and Jeff S Shamma show that giving agents "memory" or internal auxiliary states allows them to converge to Nash Equilibria even when they don't know their opponents' payoffs. This added complexity helps dampen the oscillations that usually prevent global convergence.
  2. Particle-Based Methods: Instead of a single point moving through space, Guillaume Wang and Lénaïc Chizat propose using a swarm of particles in An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games. By evolving a distribution of strategies, these methods can bypass some of the local traps that snag individual gradient learners.
  3. Curvature and Manifolds: Sometimes the problem isn't the game, but the geometry of the strategy space. Sixin Zhang explores this in Local convergence of simultaneous min-max algorithms to differential equilibrium on Riemannian manifold, showing how accounting for the "curvature" of the space itself can stabilize training for complex models like Orthogonal GANs.

Why It Matters

The lack of global guarantees isn't just a theoretical nuisance; it’s a practical bottleneck. In ALGAMES: A Fast Solver for Constrained Dynamic Games, Simon Le Cleac’h and Zachary Manchester demonstrate that while we can build incredibly fast solvers for autonomous driving, the absence of global convergence proofs means these systems might still fail in rare, highly constrained "edge cases."

Ultimately, the research direction is moving toward a unified theory where local stability is just the first step. The real goal, as echoed across papers from Panayotis Mertikopoulos to Michael Littman, is to ensure that no matter where a multi-agent system starts, the "physics" of the learning rule will inevitably guide it toward a stable, global equilibrium.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bridging_local_stability_and_global_conv_6134a29e,
  title = {Bridging Local Stability and Global Convergence in Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bridging-local-stability-and-global-convergence-in-games/rdr_6134a29e68644aec94854cea105c9b92},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_bridging_local_stability_and_global_conv_6134a29e_v1,
  title = {Bridging Local Stability and Global Convergence in Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bridging-local-stability-and-global-convergence-in-games/rdr_6134a29e68644aec94854cea105c9b92/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}