Monotone inclusion methods for a class of second-order non-potential mean-field games

Introduction

The paper introduces a new algorithm to compute solutions for a system of partial differential equations (PDEs) that models non-cooperative differential games with a continuum of agents. These games are called mean-field games (MFGs). The system characterizes an equilibrium configuration where the variables represent the distribution and optimal cost of the agents over time and space.

The authors observe that under certain conditions, the PDE system can be viewed as a first-order optimality condition for a convex-concave saddle-point problem. They provide a variant of the primal-dual hybrid gradient (PDHG) algorithm to solve the system, extending beyond previous work that focused on potential and separable MFG settings.

Their key observation is that under the Lasry-Lions monotonicity condition, the PDE system can be treated as a primal-dual pair of monotone inclusions, where the monotone maps are not necessarily subdifferential maps. The PDHG variant is then used to solve these monotone inclusions.

The authors claim their methods can handle first-order systems and non-smooth mean-field interactions, unlike some previous approaches that relied on ellipticity assumptions. Numerical experiments support their claim.

Numerical analysis

The section introduces a finite-difference scheme to discretize the mean field game system. It begins by defining uniform space-time grids and establishing periodicity conditions. Difference operators are defined, including forward, backward, and centered difference approximations.

The Hamiltonian H is then discretized to obtain Hh, satisfying key properties like monotonicity, consistency with H, differentiability, convexity, and the Lasry-Lions monotonicity condition. This discretized Hamiltonian preserves the existence and uniqueness of weak solutions.

Next, a discrete energy functional J is formulated using the perspective of the Legendre transform Lh of Hh. J incorporates the running and terminal costs. Key properties of J are established, including that it admits a minimizer under an affine constraint involving the discrete operators A and B.

Conditions are provided ensuring the positivity of the density approximations. The discrete system is then reformulated as a primal-dual monotone inclusion problem involving J and its subdifferential. First-order optimality conditions are derived by considering two convex optimization problems - one over densities with a prescribed initial condition, and another over density-control pairs. Equivalences are shown between the optimality conditions and the discrete mean field game system under appropriate differentiability assumptions on the costs. Finally, the existence of solutions is established by applying Kakutani's fixed point theorem.

A pair of primal-dual monotone inclusions

The provided text discusses a computational method based on the formulation (35) and presents an extension of the celebrated Primal-Dual Hybrid Gradient (PDHG) algorithm to solve it. The key points are:

• The problem (35) is reformulated as a pair of primal-dual monotone inclusions (43), which is shown to admit at least one solution.

• An algorithm (44) based on the PDHG method is derived to solve (43) and hence (35). However, this algorithm may converge slowly for fine grids due to the unbounded nature of the differential operator involved.

• To overcome the grid-dependent convergence rate, a preconditioned version of the algorithm (46) is presented by introducing a suitable inner product that makes the linear operator norm unity.

• Further simplifications are discussed by considering the convex duals of the functions involved, leading to algorithms (51) and (52), where the updates decouple at grid points, except for a space-time PDE solve involving the differential operator.

• The preconditioning approach ensures that the algorithm's convergence rate is independent of the grid size, making it suitable for fine grid simulations.

The text provides the mathematical derivations and algorithmic formulations, focusing on the technical details and computational aspects of solving the problem efficiently and in a grid-size independent manner.

Numerical Experiments

The paper presents two numerical experiments to demonstrate the effectiveness and robustness of the proposed numerical scheme for solving mean-field game models with congestion.

In the first experiment, the convergence of the algorithm is tested. The density evolution starts with four Gaussian distributions and eventually concentrates at the minima of the terminal cost function. The number of iterations required for convergence is shown to be grid-size independent, highlighting the efficiency of the algorithm.

The second experiment explores the impact of the viscosity parameter. As viscosity increases, the solution becomes more diffused or widespread. Importantly, the algorithm remains robust even for small viscosity values, thanks to its variational nature.

The third experiment investigates the effect of the congestion parameter. When the congestion parameter is small, the density exhibits reduced movement. As the congestion parameter approaches zero, the solution behaves similarly to the case without congestion. Again, the algorithm demonstrates robust performance across all cases.