Semi-Lagrangian Approximation of Master Equations with Individual Noise on Finite Graphs

Abstract

We develop and analyze a fully discrete semi-Lagrangian method for vector master equations associated with mean field games (MFGs) with individual noise on finite graphs. The method discretizes both the characteristic evolution in time and the population variable on the probability simplex. A central challenge is the degeneracy of the transport coefficients near the boundary of the open simplex, where no boundary condition is prescribed. To overcome this difficulty in the analysis, we introduce an interior localization based on exact density characteristics, which keeps numerical arrivals within compact regions of uniform coefficient control. Combined with a closure argument for the coupled numerical recursion, this localization yields local solvability of the updates and quantitative error bounds on compact subsets of the open simplex. Under additional $C^2$-regularity of the exact solution and suitable space--time mesh coupling, these bounds imply first-order accuracy. Furthermore, the density and value trajectories generated by the numerical master feedback converge to the corresponding MFG characteristics at the same rate. In the potential setting, the associated reconstructed density--flux pair is admissible and asymptotically optimal for the planning problem, with an action gap quadratic in the feedback error. Numerical experiments illustrate the convergence rates, feedback responses to population redistribution, and the effects of graph topology.