Computational methods for nonlocal mean field games with applications

Siting Liu, Matt Jacobs, Wuchen Li, Levon Nurbekyan, Stanley OsherarXiv 2020 · DOI · arXiv

Abstract

We introduce a novel framework to model and solve mean-field game systems with nonlocal interactions. Our approach relies on kernel-based representations of mean-field interactions and feature-space expansions in the spirit of kernel methods in machine learning. We demonstrate the flexibility of our approach by modeling various interaction scenarios between agents. Additionally, our method yields a computationally efficient saddle-point reformulation of the original problem that is amenable to state-of-the-art convex optimization methods such as the primal-dual hybrid gradient method (PDHG). We also discuss potential applications of our methods to multi-agent trajectory planning problems.

Introduction

Mean Field Games (MFGs) provide a robust mathematical framework for modeling the behavior of massive populations of rational agents, such as bird flocks, traffic flows, or financial markets. In these systems, each individual agent optimizes their path based on the global distribution of the population.

A significant challenge arises in "nonlocal" MFGs, where an agent's decision at position $x$ is influenced by the population density across the entire domain $\Omega$. This interaction is typically expressed as an integral: $\int_{\Omega} K(x, y)\rho(y, t)dy$. Standard numerical methods struggle with these terms because discretizing them creates "fully coupled" systems where every point depends on every other point. This leads to superlinear computational costs and prevents effective parallelization, making large-scale simulations or high-dimensional trajectory planning computationally prohibitive.

The Method of Coefficients

To overcome these limitations, we propose a framework that bridges the gap between partial differential equations (PDEs) and kernel methods in machine learning. The core of our approach is the Method of Coefficients.

Instead of evaluating the interaction integral directly, we expand the interaction kernel $K(x, y)$ into a finite series of basis functions: $$K(x, y) \approx \sum_{i,j=1}^r k_{ij}f_i(x)f_j(y)$$

This reduction transforms the "infinite-dimensional" interaction into a small number ($r$) of time-dependent coefficients. By utilizing Positive Definite Symmetric (PDS) kernels and Reproducing Kernel Hilbert Spaces (RKHS), we can precisely define "features" that represent physical behaviors, such as repulsion or attraction. For example, using a Fourier basis naturally handles periodic environments, while restricting basis functions to specific sub-domains allows for modeling "tribal" behavior where agents only interact with their own group.

Optimization and Efficiency

We reformulate the MFG as a convex-concave saddle-point problem, which allows us to utilize the Primal-Dual Hybrid Gradient (PDHG) algorithm. The primary advantage of this reformulation is that the most computationally expensive parts of the calculation—the proximal steps—remain decoupled.

Because the number of coefficients $r$ is typically much smaller than the grid resolution $N$, the complexity of the interaction term becomes independent of the grid resolution. This allows the algorithm to achieve linear computational complexity relative to the number of grid points, matching the efficiency of local MFG solvers while handling much more complex nonlocal physics. This "grid independence" means researchers can refine spatial meshes for higher accuracy without facing an exponential increase in computational cost.

Numerical Results and Applications

We evaluated the method using synthetic numerical experiments on 2D grids ($64 \times 64$) with 32 time steps. The framework successfully simulated agents navigating through narrow channels and avoiding both static and dynamic rectangular obstacles.

Key observations include:

  • Behavioral Sensitivity: Small changes in kernel parameters (such as variance $\sigma_i$) lead to distinct emergent behaviors, such as horizontally elongated density evolution when repulsion is stronger in one direction.
  • Sub-region Dynamics: The model successfully captured "congestion-blind" behavior at boundaries. By defining kernels that do not cross specific lines, we observed high-density concentrations at boundaries that would be impossible in standard global interaction models.

Conclusion and Future Work

This framework provides a scalable, parallelizable solution for nonlocal MFGs by treating interaction modeling as a feature engineering problem. While currently focused on first-order deterministic systems, future work will extend this to second-order stochastic systems. Additionally, we aim to combine this coefficient method with Lagrangian (particle-based) solvers to address the "curse of dimensionality" in very high-dimensional trajectory planning problems.

Summary updated

Abstract

We introduce a novel framework to model and solve mean-field game systems with nonlocal interactions. Our approach relies on kernel-based representations of mean-field interactions and feature-space expansions in the spirit of kernel methods in machine learning. We demonstrate the flexibility of our approach by modeling various interaction scenarios between agents. Additionally, our method yields a computationally efficient saddle-point reformulation of the original problem that is amenable to state-of-the-art convex optimization methods such as the primal-dual hybrid gradient method (PDHG). We also discuss potential applications of our methods to multi-agent trajectory planning problems.
BibTeX
@misc{liu2020computational,
  author = {Siting Liu and Matt Jacobs and Wuchen Li and Levon Nurbekyan and Stanley Osher},
  title = {{Computational methods for nonlocal mean field games with applications}},
  year = {2020},
  eprint = {2004.12210},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.12210},
}

Loading related content...

Figure