A mean-field analysis of two-player zero-sum games

Carles Domingo-Enrich, Samy Jelassi, Arthur Mensch, Grant M. Rotskoff, Joan Bruna

Abstract

Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.

Introduction: Beyond Pure Nash Equilibria

In machine learning, many problems—most notably Generative Adversarial Networks (GANs) and robust optimization—can be framed as a zero-sum game between two players, such as a Generator and a Discriminator. While practitioners often seek a Pure Nash Equilibrium, where each player selects a single optimal strategy, such equilibria frequently do not exist in continuous, non-convex settings.

The alternative is a Mixed Nash Equilibrium (MNE), where players choose a probability distribution over strategies. Although MNEs are guaranteed to exist under broader conditions, finding them in high-dimensional spaces is computationally challenging. Traditional methods like mirror descent suffer from the "curse of dimensionality," failing as the number of parameters grows. This research introduces a scalable framework to identify mixed equilibria without requiring restrictive convexity assumptions.

Methodology: Lifting to Measure Spaces

The core proposal is to "lift" the game from the space of individual strategies to the infinite-dimensional space of probability measures. To make this tractable, measures are represented as sets of particles. The authors analyze two primary dynamics:

  1. Langevin Descent-Ascent (L-DA): Particle positions are updated via gradient descent-ascent with added diffusion (noise). This noise prevents particles from collapsing into suboptimal points.
  2. Wasserstein-Fisher-Rao (WFR) Dynamics: A key contribution of this work, WFR dynamics allow for joint updates of both particle positions and weights.

The theoretical foundation rests on a mean-field analysis. By applying a "law of large numbers" to these particles, the authors demonstrate that as the number of particles $n$ grows, the discrete system converges to a global "mean-field" flow. The Wasserstein-Fisher-Rao metric is utilized to combine the transport geometry of moving mass with the information-theoretic updates of changing mass.

Key Results and Scalability

The effectiveness of these methods was tested on synthetic polynomial games, 2D Gaussian Mixture Models (GMMs), and standard image datasets like MNIST and CIFAR-10.

A critical finding is the robustness of particle-based methods in high dimensions. While mirror descent's performance degrades rapidly as dimensionality increases, L-DA and WFR-DA maintain low Nikaidô-Isoda (NI) errors—a metric indicating proximity to a Nash Equilibrium.

Nikaidô-Isoda error vs. problem dimension for L-DA, WFR-DA, and mirror descent.

In GAN training on CIFAR-10, WFR-DA led to more stable convergence and improved FID scores. By updating both generator weights and parameters, the model effectively handled complex, multi-modal data compared to single-generator baselines.

Insights: Teleportation and Specialization

The WFR approach introduces a "teleportation" effect. In standard transport (Wasserstein) flows, a strategy must move continuously through the parameter space. In WFR, a "bad" strategy can simply have its weight decreased to zero while a "good" strategy's weight increases elsewhere, effectively bypassing barriers in the loss landscape.

Furthermore, when training mixtures of GANs, different generators naturally "specialize" in different modes of the data distribution without explicit labels. This unsupervised clustering allows for better coverage of the target distribution.

Mode recovery in GANs: Multi-generator setups (left) achieve better coverage of the true distribution than single-generator setups (right).

Conclusion and Future Directions

This work provides a strong theoretical and empirical basis for finding mixed equilibria in high-dimensional games. While global convergence is established for Langevin dynamics, future work aims to provide quantitative convergence rates for WFR dynamics. Additionally, while the particle-based approach is effective, the computational overhead of managing large populations of neural networks remains a practical challenge for scaling to even more complex domains.

Summary updated

Abstract

Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs.
BibTeX
@inproceedings{domingoenrich2020mean,
  author = {Carles Domingo-Enrich and Samy Jelassi and Arthur Mensch and Grant M. Rotskoff and Joan Bruna},
  title = {{A mean-field analysis of two-player zero-sum games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=GiN9JRarBB},
}
Figure