MFG Math

Mean-Field Game โ€” Backward Induction & Forward Simulation
Setup โ‘  Value Function โ‘ก Backward Induction โ‘ข Forward Simulation โ‘ฃ Fixed-Point Loop Summary Notation

Setup

We model each driver as an agent in a finite-horizon discrete Mean-Field Game. The key objects are:

State
Agent is in zone $z$ at time $t$
Action
$a \in \mathcal{A} = \{\text{accept},\,\text{reject}\}$
Reward
$r(z,a,\mu_t)$ โ€” depends on zone, action, and crowd
Transition
$P(z' \mid z, a)$ โ€” landing zone after action $a$
Horizon
Finite $T$ steps  (one day = 1440 min)
Mean field
$\mu_t(z)$ = fraction of drivers idle in zone $z$ at time $t$

1 Value Function

$V(z,t)$ is the expected total future reward starting from zone $z$ at time $t$, assuming you act optimally and the crowd follows $\mu$.

Terminal condition โ€” no future left at the horizon:

$$V(z,\, T) \;=\; 0$$

Recursive Bellman equation โ€” the value at $t$ is the best Q-value achievable:

$$V(z,\,t) \;=\; \max_{a \in \mathcal{A}} \Bigl[\, r(z,a,\mu_t) \;+\; \sum_{z'} P(z'\mid z,a)\; V(z',t+1) \Bigr]$$

The expression inside the max defines the Q-value:

$$Q(z,a,t) \;=\; r(z,a,\mu_t) \;+\; \sum_{z'} P(z'\mid z,a)\; V(z',t+1)$$

So compactly:

$$V(z,t) \;=\; \max_a\; Q(z,a,t)$$

2 Backward Induction

$V$ is computed by sweeping from $t = T$ back to $t = 0$. Each step uses the already-computed $V(\cdot,\,t+1)$ โ€” you need the future before you can value the present.

t = T : V(z, T) = 0 โ† base case
t = Tโˆ’1: V(z, Tโˆ’1) = maxa Q(z, a, Tโˆ’1) โ† uses V(ยท, T)
t = Tโˆ’2: V(z, Tโˆ’2) = maxa Q(z, a, Tโˆ’2) โ† uses V(ยท, Tโˆ’1)
   โ‹ฎ
t = 0 : V(z, 0) = maxa Q(z, a, 0) โ† uses V(ยท, 1)

The optimal (greedy) policy is extracted at each step:

$$\pi^*(z,t) \;=\; \arg\max_a\; Q(z,a,t)$$

In practice a soft policy replaces the hard argmax for numerical stability โ€” a sigmoid over the Q-value gap:

$$\pi(a = \text{accept} \mid z, t) \;=\; \sigma\!\left(\frac{Q_{\text{accept}} - Q_{\text{reject}}}{\tau}\right)$$

The temperature $\tau$ controls selectivity: $\tau \to 0$ recovers the hard argmax; $\tau \to \infty$ gives a uniform 50/50 policy.

3 Forward Simulation

Given policy $\pi^*$, propagate $\mu$ forward from $t = 0$ to $t = T$:

$$\mu_{t+1}(z') \;=\; \sum_z \mu_t(z) \sum_a \pi^*(a \mid z,t)\; P(z' \mid z,a)$$

In words: the fraction of drivers in zone $z'$ at $t{+}1$ equals the sum over all origin zones $z$ and all actions $a$ of (fraction of drivers there) ร— (probability of choosing $a$) ร— (probability of transitioning to $z'$).

This propagation yields a new implied distribution $\hat{\mu}$ โ€” what the crowd actually looks like when everyone follows $\pi^*$.

4 Fixed-Point Loop

The backward pass assumed $\mu^{(k)}$; the forward pass produced $\hat{\mu}^{(k+1)}$. If they differ, we blend and repeat. A damped update prevents oscillation:

$$\mu^{(k+1)} \;=\; \alpha\,\hat{\mu}^{(k+1)} \;+\; (1-\alpha)\,\mu^{(k)}$$

Iterate until the L1 change falls below tolerance $\varepsilon$:

$$\bigl\|\mu^{(k+1)} - \mu^{(k)}\bigr\|_1 \;<\; \varepsilon$$

At convergence $\mu^* \approx \hat{\mu}^*$ โ€” the distribution each driver assumes is exactly the distribution produced when everyone best-responds to it. This is the Mean-Field Nash Equilibrium.

Phase 1 uses $\alpha = 0.05$, $\varepsilon = 0.01$. Phase 2 uses $\alpha = 0.02$ (smaller, to handle spiky real demand) and $\varepsilon = 1.0$ (calibrated to the integer noise floor of real trip counts).


Summary

$\mu^{(k)}$
assumed crowd
โ†’
backward
$V,\;\pi^*$
best response
โ†’
forward
$\hat{\mu}^{(k+1)}$
implied crowd
โ†’
mix & repeat
$\mu^{(k+1)}$
next iterate

Backward โ€” "what should I do?" given the crowd  ยท  Forward โ€” "what does the crowd do?" given $\pi^*$  ยท  Equilibrium โ€” both answers agree

Notation Reference

SymbolMeaning
$z,\; z'$Current zone and next zone (state space $\mathcal{Z}$)
$t$Discrete time step, $t \in \{0,\ldots,T\}$
$a$Action: accept or reject a ride offer
$\mu_t(z)$Mean field โ€” fraction of idle drivers in zone $z$ at time $t$
$r(z,a,\mu_t)$Instantaneous reward; depends on zone, action, and crowd density
$P(z'\mid z,a)$Transition probability: land in $z'$ from $z$ after action $a$
$V(z,t)$Value function โ€” optimal expected future reward from $(z,t)$
$Q(z,a,t)$Q-value โ€” expected reward of taking action $a$ in $(z,t)$
$\pi^*(z,t)$Optimal policy โ€” action distribution at $(z,t)$
$\hat{\mu}$Implied mean field โ€” distribution produced by forward simulation
$\alpha$Mixing coefficient for damped update
$\varepsilon$L1 convergence tolerance
$\tau$Softmax temperature for the accept/reject policy
$\sigma(\cdot)$Sigmoid function $\sigma(x) = 1/(1+e^{-x})$