Coupled Wasserstein Gradient Flows for Min-Max and Cooperative Games

Lauren Conger, Franca Hoffmann, Eric Mazumdar, Lillian J. RatliffarXiv 2024 · DOI · arXiv

Abstract

We propose a framework for two-player infinite-dimensional games with cooperative or competitive structure. These games take the form of coupled partial differential equations in which players optimize over a space of measures, driven by either a gradient descent or gradient descent-ascent in Wasserstein-2 space. We characterize the properties of the Nash equilibrium of the system, and relate it to the steady state of the dynamics. In the min-max setting, we show, under sufficient convexity conditions, that solutions converge exponentially fast and with explicit rate to the unique Nash equilibrium. Similar results are obtained for the cooperative setting. We apply this framework to distribution shift induced by interactions among a strategic population of agents and an algorithm, proving additional convergence results in the timescale-separated setting. We illustrate the performance of our model on (i) real data from an economics study on Colombia census data, (ii) feature modification in loan applications, and (iii) performative prediction. The numerical experiments demonstrate the importance of distribution-level, rather than moment-level, modeling.

Introduction

In many real-world systems, we observe multiple groups interacting dynamically. Consider a machine learning algorithm classifying loan applicants while those applicants strategically modify their behavior to improve their approval odds. This is not a static optimization problem but a game played over distributions of data. Traditional gradient flow theory often focuses on a "single species"—a single distribution evolving to minimize a functional. However, modern strategic environments involve "multi-species" systems where two or more distributions evolve simultaneously, and each player's objective depends on the state of the other.

In these coupled systems, the optimization landscape is constantly shifting. This lack of a static gradient structure can lead to chaotic behavior, such as infinite cycling or "cat-and-mouse" dynamics. This is particularly relevant in strategic distribution shift, where a population reacts to an algorithm (e.g., users changing social media habits to influence an engagement-maximizing AI). This paper introduces a rigorous mathematical framework to determine when these coupled systems settle into a stable Nash equilibrium.

Mathematical Framework

The authors model the evolution of two probability distributions, $\rho$ and $\mu$, as a system of coupled partial differential equations (PDEs).

Wasserstein-2 Gradient Flows

The framework utilizes the Wasserstein-2 ($W_2$) metric, which measures the "work" required to transform one distribution into another. This metric defines the direction of steepest descent (or ascent) in the space of probability measures. The system is analyzed in two primary contexts:

  1. Cooperative Games: Both players minimize a shared energy functional.
  2. Competitive (Min-Max) Games: One player minimizes while the other maximizes a shared functional.

The model incorporates energy functionals consisting of potential terms (external forces), interaction kernels (intra-group dynamics), and entropy (diffusion/spreading). To handle scenarios where one player (e.g., an algorithm) updates significantly faster than the other (e.g., a population), the authors employ $\Gamma$-convergence to analyze timescale-separated dynamics.

Convergence and Nash Equilibria

A central contribution of this work is proving that the steady states of these coupled PDEs correspond exactly to the Nash equilibria of the underlying infinite-dimensional games.

Despite the absence of a global gradient structure in competitive games, the authors prove that the system achieves exponential convergence to a unique Nash equilibrium under the condition of "displacement convex-concave" functionals. By extending classical functional inequalities—such as HWI, log-Sobolev, and Talagrand—to the multi-species setting, they provide explicit rates for this convergence.

The Importance of Distributional Modeling

A key insight of the research is that modeling the entire distribution is often superior to modeling only moments (like the mean). Many existing methods in performative prediction focus on "mean shift" models. However, strategic interactions can cause complex phenomena like mode splitting, where a population divides into distinct subgroups. Mean-based models fail to capture these shifts, whereas the Wasserstein gradient flow framework accounts for the full evolution of the distribution's shape.

Furthermore, the type of interaction between agents (e.g., "repulsive" vs. "swarm-like") significantly impacts the precision of a classifier on specific subpopulations, even if aggregate accuracy remains stable.

Empirical Validation

The framework was validated across three distinct scenarios:

  1. Colombia Census Data (1995–2003): The model analyzed real-world data where local officials misreported poverty indices to help constituents qualify for aid. The framework successfully captured the "sharp drop-off" at the aid threshold and predicted an empirical convergence rate (0.0114) that closely matched the theoretical prediction (0.01).
  2. Loan Application Data: Using a dataset of loan applications, the authors simulated how ineligible agents manipulate features like "age" or "past due counts." The model demonstrated how strategic behavior shifts the distribution of applicants over time.
  3. Performative Prediction: In synthetic experiments, the PDE-based model outperformed state-of-the-art mean-shift methods by accurately accounting for complex changes in the population distribution shape.

Limitations and Future Work

While the framework provides a robust foundation for multi-species games, several challenges remain:

  • Convexity Assumptions: The proofs rely on strong displacement convexity, which may not hold in the complex loss landscapes of deep neural networks.
  • Scaling to N-Players: The current theory is limited to two-player interactions; extending this to $N$-player games is a necessary next step.
  • Smoothness of Potentials: The assumption of smooth, twice-differentiable potentials may need to be relaxed to accommodate non-smooth real-world interactions.
  • Transient Dynamics: While this paper focuses on long-term steady states, the transient behavior—the path taken toward equilibrium—is critical for understanding fairness and subpopulation impacts during the learning process.

Summary updated

Abstract

We propose a framework for two-player infinite-dimensional games with cooperative or competitive structure. These games take the form of coupled partial differential equations in which players optimize over a space of measures, driven by either a gradient descent or gradient descent-ascent in Wasserstein-2 space. We characterize the properties of the Nash equilibrium of the system, and relate it to the steady state of the dynamics. In the min-max setting, we show, under sufficient convexity conditions, that solutions converge exponentially fast and with explicit rate to the unique Nash equilibrium. Similar results are obtained for the cooperative setting. We apply this framework to distribution shift induced by interactions among a strategic population of agents and an algorithm, proving additional convergence results in the timescale-separated setting. We illustrate the performance of our model on (i) real data from an economics study on Colombia census data, (ii) feature modification in loan applications, and (iii) performative prediction. The numerical experiments demonstrate the importance of distribution-level, rather than moment-level, modeling.
BibTeX
@misc{conger2024coupled,
  author = {Lauren Conger and Franca Hoffmann and Eric Mazumdar and Lillian J. Ratliff},
  title = {{Coupled Wasserstein Gradient Flows for Min-Max and Cooperative Games}},
  year = {2024},
  eprint = {2411.07403},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.07403},
}
Figure