A total variation flow scheme for ergodic mean field games

Dante Kalise, Alessio Oliviero, Domènec Ruiz-BaletarXiv 2024 · DOI · arXiv

TL;DR

This paper introduces a novel "total variation flow" scheme to numerically solve ergodic mean field games, particularly those arising in ecological modeling. By connecting best response dynamics to minimizing movement schemes, they offer a robust method for computing solutions even when traditional variational structures are absent, demonstrating its effectiveness through numerical simulations.

What Problem Does This Paper Address?

Mean Field Games (MFGs) are powerful tools for modeling systems with many interacting agents, finding applications in economics, finance, and ecology. Ergodic MFGs, in particular, describe systems that reach a steady state over time. However, computing solutions for these games, especially those with complex payoff structures or lacking a clear variational formulation, presents a significant numerical challenge. Existing methods often rely on specific variational structures that may not always be present. This paper aims to bridge this gap by developing a general variational approach that can handle a wider class of ergodic MFGs, even when they don't naturally fit existing variational frameworks.

Methods

The core of this work is the development of a "total variation flow" scheme. This approach leverages the concept of "best response dynamics," where agents adjust their strategies based on the current payoff landscape. Instead of tracking individual agent trajectories, the authors simulate this adjustment macroscopically by shifting mass from low-payoff regions to high-payoff regions. This mass-shifting is framed as a minimizing movement scheme using the Total Variation (TV) metric, which penalizes the amount of mass moved rather than the spatial distance. Two algorithms, "Best Response" and "Eikonal-based," are proposed, both utilizing this TV flow principle. The Best Response algorithm focuses on minimizing the income gap, while the Eikonal-based algorithm uses distance to the highest payoff regions. These algorithms are then analyzed theoretically and implemented numerically.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical simulations using synthetic scenarios defined by the problem parameters.

Key Insights and Ideas

  • Total Variation Flow for MFGs: The paper establishes a novel connection between best response dynamics in evolutionary game theory and minimizing movement schemes using the Total Variation metric. This provides a powerful new tool for analyzing and computing solutions for ergodic MFGs.
  • Handling Non-Variational Structures: A key contribution is the development of a method that can compute solutions for ergodic MFGs that may not possess a priori variational structures, broadening the applicability of numerical methods.
  • Best Response as Mass Shifting: The authors frame the update step in their algorithms as a macroscopic mass redistribution from low-income to high-income regions, offering an intuitive interpretation of the dynamics.
  • TV Metric's Role: The use of the Total Variation metric is crucial, allowing for "spatial teleportation" of mass, which is efficient for minimizing income gaps and can lead to exact Nash equilibria in finite time, unlike traditional Wasserstein flows.
  • Eikonal Equation for Optimal Relocation: The Eikonal-based algorithm cleverly uses the Eikonal equation to identify players furthest from the high-payoff regions, ensuring that mass removal has minimal collateral impact on the global peak.

Key Results

  • Theoretical Guarantees: The paper provides theoretical results on the well-posedness of the problem and the convergence of the proposed algorithms to solutions of ergodic MFGs, particularly in the one-dimensional case.
  • Numerical Robustness: The proposed algorithms (Best Response and Eikonal-based) are implemented and tested on various linear and non-linear harvesting mean field games in one and two dimensions.
  • Convergence: Numerical simulations demonstrate that both algorithms successfully converge to approximate Nash equilibria, showing a decrease in the objective functional and convergence of the discrete flow to a gradient flow as the step-size decreases.
  • Efficiency: While Algorithm 4 (Eikonal-based) sometimes requires more iterations than Algorithm 3 (Best Response), both algorithms achieve convergence within a reasonable number of steps for the tested scenarios.

Limitations and Future Work

  • Dimensionality: The analytical framework is primarily developed for the one-dimensional case. Extending the rigorous proofs to higher dimensions (d ≥ 2) is challenging due to the breakdown of certain analytical tools (e.g., Sobolev embedding, Lipschitz continuity of Green's function).
  • Non-Monotone Nonlinearities: The proofs for certain results, particularly those relying on the strong maximum principle, are restricted to models with monotone nonlinearities. Extending these proofs to non-monotone cases, which are relevant in some applications, requires more delicate analysis.
  • Uniqueness of Trajectories: While the paper establishes the existence of a limit curve and its convergence to an equilibrium, the non-uniqueness of geodesics in the space of probability measures with the TV metric poses challenges for proving the strict uniqueness of the continuous TV-flow trajectories.
  • Future Work: The authors suggest exploring the extension of the framework to higher dimensions and non-monotone nonlinearities. They also highlight the open problem of proving the strict uniqueness of TV-flow trajectories.

Summary updated

Abstract

Motivated by recent developments in mean field games in ecology, in this paper we introduce a connection between the best response dynamics in evolutionary game theory, the minimization of the highest income of a game, and minimizing movement schemes. The aim of this work is to develop a variational approach to compute solutions of first order ergodic mean field games that may not possess a priori a variational structure. The study is complemented by a discussion and successful implementation of numerical algorithms, and comparisons between them in a variety of cases.
BibTeX
@misc{kalise2024total,
  author = {Dante Kalise and Alessio Oliviero and Domènec Ruiz-Balet},
  title = {{A total variation flow scheme for ergodic mean field games}},
  year = {2024},
  eprint = {2411.07331},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2411.07331},
}
Figure