This article explores how mean field game (MFG) theory can be used to solve the complex decision-making challenges of large-scale agents in a cross-temporal and spatial environment. Traditional methods often encounter dimensionality disasters and conflicts of interest when faced with massive resource allocation, while the equilibrium field game significantly improves computational efficiency by simplifying the interaction between individuals into the interaction between the individual and the average state of the group.
The article focuses on two application cases: the first is the JDRCL framework, which balances platform efficiency and driver fairness in online ride-hailing dispatch; the second is the EMFRL solution, which realizes non-cooperative boundary collaborative control of urban road networks through macroscopic basic diagrams. These models use the coupling of the Hamilton-Jacobi-Bellman equation and the Fokker-Planck equation to prove that distributed decision-making can also achieve a stable state similar to centralized control. All in all, mean field games provide a solid mathematical framework for processing macro-evolution and micro-optimization in big data scenarios such as logistics and transportation.
Total text: 4235 words
Estimated reading time: 8-12 minutes
1. Mean field game
Mean Field Game (MFG) is a mathematical and game theory theory that studies the strategic decision-making of a large number of tiny agents (participants) in competitive or dynamic environments. It combines game theory, stochastic analysis and optimal control theory. In mean field games, the mean field borrows a concept from physics, which means that in a large group, the behavior of a single agent has minimal impact on the entire system. Therefore, when making decisions, each agent no longer responds to the behavior of each other individual individually, but makes optimized decisions based on the overall state probability distribution of the population (i.e., the "mean field"). In the continuous time model, it is usually composed of the coupling of the Hamilton-Jacobi-Bellman equation describing the individual optimal control and the Fokker-Planck equation describing the dynamics of the group aggregate distribution.
Traditional multi-agent models or classical game theory face the "curse of dimensionality" and exponentially increasing computational complexity when dealing with large-scale groups, because it is mathematically and computationally unrealistic to accurately describe the interaction between each pair of individuals. Mean field game theory is specially used to solve the Nash equilibrium solution problem in complex systems containing massive interactive agents, and approximately transforms complex multi-body interaction problems into single-body problems in which individuals interact with the average state of the group. Its advantages mainly include the following points:
-
Computational dimensionality reduction and efficiency:By converting complex inter-individual interactions into responses to the overall mean field, MFG greatly reduces the computational cost of system simulation and strategy solution, making it possible to conduct macroscopic simulations in big data scenarios such as transportation and finance.
-
Taking into account both micro-decision-making and macro-evolution:Compared with pure physical dynamics models, MFG can not only describe the evolution of group status, but also explain how individuals actively optimize their own strategies based on expectations for the future (rational expectations), and has stronger explanatory power.
-
Easy to combine with machine learning:MFG can provide a strict theoretical framework for multi-agent reinforcement learning (MARL). By introducing mean field actions (such as MF-Q algorithm), it can effectively break through the computational bottleneck of classic multi-agent reinforcement learning when the number of agents increases.
2. Temporal and spatial conditioning issues
Inter-temporal regulation refers to the process of allocating and guiding massive resources (such as online ride-hailing, urban traffic flow, logistics distribution, etc.) in a dynamic system with significant spatial distribution and temporal evolution characteristics. It not only focuses on current resource matching, but also emphasizes on optimizing the long-term operating status of the entire system through forward-looking scheduling (such as empty car scheduling for online ride-hailing or traffic control at traffic boundaries).
Conventional solutions to this type of problem are usually based on traditional optimization methods (linear programming, queuing theory, etc.), heuristic algorithms (simulated annealing, neighborhood search, genetic algorithms, etc.) or reinforcement learning algorithms (DQN, A2C, etc.). However, traditional solutions often suffer from the following difficulties:
-
Exponential explosion of state and action space:In real cross-temporal and spatial climate scenarios (such as thousands of online ride-hailing drivers or complex urban road networks), if a centralized decision-maker is used to provide global coordination for all individuals, its state space and action space will expand exponentially with the number of individuals, facing serious "single point failure" risks and incomputability.
-
Deep spatiotemporal coupling effect:Scheduling decisions not only determine current benefits, but also profoundly change the future spatial distribution of resources, thereby affecting future matching potential and efficiency. For example, sending an online ride-hailing car to a certain place to complete an order changes the driver's geographical location, which directly determines his probability of receiving orders in the future.
-
Multi-goal conflict (difficult to balance efficiency and fairness):Dispatch systems often need to simultaneously optimize overall "efficiency" (such as the platform's total transaction volume GMV, total traffic volume on the road network) and individual "fairness" (such as ensuring the bottom line of income for the most vulnerable drivers). However, there are often inherent conflicts between the two. Focusing only on efficiency can easily lead to the marginalization of some individuals and damage the long-term sustainability of the system.
-
Dynamically changing action space:The actions that an agent can perform at different times and spaces change dynamically (for example, the set of available orders faced by online ride-hailing drivers in different grids changes in real time), which brings great challenges to the neural network design and feature representation of the algorithm.
-
Non-cooperative game of heterogeneous agents:Cross-regional scheduling (such as urban traffic boundary control) often involves different stakeholders (such as managers of different regions, internal parking lots, etc.). They lack centralized communication, have inconsistent goals, and work independently to easily fall into a lose-lose situation that is detrimental to the system.
3. Cross-temporal conditioning application scheme based on mean field game
1 · Online ride-hailing platform jointly dispatches orders and dispatches empty cars
(Based on JDRCL framework)
In the online car-hailing system, scheduling not only determines the current order matching (immediate revenue), but also changes the spatial distribution of drivers (future revenue potential). The traditional efficiency-prioritizing algorithm often results in low income for some drivers. To this end, the researchers proposed a constrained multi-objective Markov game (CMOMG) framework - JDRCL (Joint Order Dispatching and Driver Repositioning with Constrained MARL), which jointly optimizes the long-term system total order volume (efficiency) and maximum and minimum fairness (fairness) under the constraints of the scheduling cost budget.
Problem modeling and objective function:
Treat each driver as an independent agent. The framework contains two optimization objectives: one is the overall expected cumulative revenue (GMV) that represents platform efficiency, and the other is the worst expected cumulative revenue among all drivers (Max-min Fairness) that represents fairness. The platform presets the budget constraint B for the total dispatch cost (such as the subsidy for empty truck dispatch).
The core objective function of the problem is formulated as a constrained max-min optimization problem:
Among them:
-
Indicates the long-term expected cumulative return of agent i under the joint strategy π.
-
Represents the long-term expected cumulative scheduling cost of agent j.
-
α It is the adjustment coefficient that balances efficiency and fairness.
Lagrangian dual transformation:
Since it is extremely difficult to directly solve the maximin problem with constraints, JDRCL uses the Lagrange multiplier method to transform the original problem into a Lagrangian maximin unconstrained problem:
Among them, θ is the parameter (main variable) of the policy network, ω∈Δ is the weight vector used to fit the minimization term, and λ is the non-negative dual variable that handles the cost budget constraint.
Core update algorithm and derivation:
The algorithm uses Primal-Dual Iterative Training to alternately update the strategy parameters θ and dual variables λ.
-
Strategy (Actor) parameter update:Maximize the objective function using stochastic gradient ascent. The sample estimation formula of its gradient is derived as:
According to the policy gradient theorem, its core gradient estimation formula is expanded to:
Here, and are the advantage functions of benefits and costs respectively. The physical meaning of this derivation is: the agent will tend to increase the probability of actions that can not only improve the overall global benefit and the benefit of the most vulnerable driver, but also reduce the overall scheduling cost of the system.
-
Dual variable update: Penalize budget overruns via projected gradient descent:
Action space dimensionality reduction:
Since the candidate order pool faced by drivers at different times and locations changes in real time, the action space is extremely large and dynamically variable. In order to solve this problem, JDRCL clusters and groups orders by destination grid, and fixes the output dimension of the policy network to a limited grid category (such as G+9 dimension, that is, G candidate order destination grids and 9 tour neighboring grids). This dimensionality reduction allows the Actor network to efficiently select the optimal action by performing only one forward propagation each time.
2 · Non-cooperative boundary collaborative control of urban road network
(Based on EMFRL scheme)
In urban traffic scheduling, if cross-border intersections (border control units) and internal parking lots in an area are regarded as different stakeholders, they often lack centralized communication and physical connections and have independent decision-making goals. In order to avoid each subject falling into a lose-lose situation due to inconsistent interests, researchers proposed the extended mean field reinforcement learning (EMFRL) method for non-cooperative boundary control.
Introduce the macroscopic basic diagram as the mean field:
Traditional cell transport model (CTM)-based approaches require a central manager to control all flow rates. EMFRL abandoned this centralization assumption and instead introduced the concept of macroscopic basic diagram (MFD) into the CTM model to describe the overall operating status of the regional road network. The relationship between the total boundary flow rate and the vehicle density of the road network reflected by the MFD was used as the prototype of the mean-field action in the mean field theory. Each agent only needs to perceive the macroscopic state of the boundary flow rate reflected by the overall road network to make a local optimal decision.
Core mechanism and FP-HJB equation system:
Finding the Nash equilibrium point in a non-cooperative game is essentially transformed into solving the Bellman Equation for each agent. Under the framework of mean field game theory of continuous time and state, this distributed micro-decision-making and macro-evolution process is mathematically described by a system composed of the famous Fokker-Planck (FP) equation and Hamilton-Jacobi-Bellman (HJB) equation coupling:
-
HJB equation for individual decision-making optimization (inverse evolution):The goal of each local traffic control unit (agent) is to maximize its own utility based on future congestion expectations, and its value function
Satisfy:
Among them, A is the diffusion operator and H is the Hamiltonian, which represents the optimal traffic flow adjustment strategy (feedback control) calculated by the control unit under a given road network vehicle density distribution m (mean field).
-
Fokker-Planck equation of road network macrostate evolution (forward evolution):When all decentralized control units execute the boundary control strategy according to their respective HJB equations, the density distribution of the overall traffic flow in the road network
The evolution of is dominated by the continuity equation:
Here, the flow drift term (macroscopic flow rate) under the action of the optimal control field is reflected. This set of equations rigorously proves mathematically that even in the absence of a central manager, as long as the agent follows the optimal response to the mean field m, the system can converge to a stable macroscopic state that is similar to the performance of centralized control.
Mean field action predictor with specific expression:
-
Introduction of MFAP:In multi-agent reinforcement learning, since the strategies of each agent are constantly updated, the current mean field action and the future mean field action are unstable. The study designed a mean field action predictor (MFAP), which takes the mean field action and environmental information at the previous moment as input, and uses supervised regression to predict the mean field action at the current moment. MFAP will converge synchronously as the agent's strategy approaches the Nash equilibrium.
-
Value Decomposition Network (VDN) and confidence assignment:In order to reduce the error generated when using EMFRL for mean field approximation, the model introduces a VDN structure into the policy neural network, which enhances the specific expression between the same group of agents, allows different intersections and internal nodes to learn differentiated sub-policies, and achieves implicit collaboration without communication.
Machine-translated from the Chinese original 基于平均场博弈的跨时空调度方案 (published 2025-03-06). WeChat original ↗