System Optimum vs User Equilibrium

Defines the system optimum (SO) flow assignment that minimizes total network travel time, contrasts it with user equilibrium (UE), introduces Wardrop's second principle via the marginal social cost, and uses these to compute the price of anarchy in simple congestion-game examples drawn from air-traffic routing.

Step 1 of 157%

Tutorial

Total Travel Time and the System Optimum

In a user equilibrium (UE), each aircraft picks the route that minimizes its own travel time — no one can shave time off by switching. But UE almost never minimizes the total time aircraft spend in the network.

If route $r$ carries flow $x_r$ with travel time $t_r(x_r),$ the total system travel time is

C(\mathbf{x}) \,=\, \sum_{r} x_r \, t_r(x_r),

measured in aircraft-hours.

A flow assignment $\mathbf{x}$ is a system optimum (SO) if it minimizes $C(\mathbf{x})$ subject to the demand constraint $\sum_r x_r = D.$

UE asks "Is the route I picked best for me?" SO asks "Is this assignment best for everyone?" The two answers usually differ.

For illustration, take two airways with $t_A(x_A) = x_A$ hr and $t_B(x_B) = 1$ hr, demand $D = 1.$ At UE all aircraft use Route A: setting $x_A = 1, x_B = 0$ gives $t_A = 1 = t_B$ — no one can improve by switching. The total system time is

C_{UE} \,=\, 1\cdot 1 + 0\cdot 1 \,=\, 1 \text{ aircraft-hour.}

Could we route the same demand using fewer total aircraft-hours? Yes — we will see how in the next cycle.