Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 35 / 2 / c / Solution

Here is an explicit Braess paradox. Use four vertices $s,a,b,t$ and unit demand from $s$ to $t$. The delay on $s\to a$ equals its own link flow, as does the delay on $b\to t$; the delays on $a\to t$ and $s\to b$ are constantly one. Initially the two routes are $s\to a\to t$ and $s\to b\to t$. If the first carries $u$ and the second $1-u$, their delays are $1+u$ and $2-u$. The Wardrop equilibrium has $u=1/2$, so every traveler takes time $3/2$.

Add a directed link $a\to b$ with zero delay. Let the old upper and lower routes carry $a_0,b_0$, and let the new route $s\to a\to b\to t$ carry $z$, with $a_0+b_0+z=1$. Their delays becomeIf $a_0>0$, the upper route is strictly slower than the middle route, contradicting the Wardrop equilibrium condition. Similarly $b_0>0$ is impossible. Thus the new equilibrium has $z=1$, and all three route delays are two. ConsequentlyThis is an incentive effect, not a loss of feasible allocations: the old half-and-half flow remains feasible after adding the link. For completeness, its social optimality can be checked directly. Write $a_0=(1-z)/2+h$, $b_0=(1-z)/2-h$. Total travel time in the enlarged network isIt is minimized at $z=h=0$, giving the original total time $3/2$. The Wardrop equilibrium instead incurs total time two, a factor $4/3$ larger. The Beckmann potential and total-delay objectives differ because an extra traveler ignores the delay their presence imposes on others. More generally, adding routes cannot worsen the optimum of total delay when it leaves the previous feasible flows available, but it can worsen a selfish Wardrop equilibrium.