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

A useful starting model treats a road network as a directed flow network and travelers as a divisible population in a nonatomic congestion game: an individual traveler has negligible effect on link congestion. For each source-sink pair $k$, fix a demand $d_k$ and a finite set ${\mathcal{P}}_k$ of allowed routes. Let $f_p\ge 0$ be the flow on route $p$, with ${\sum }_{p\in {\mathcal{P}}_k}{f}_p=d_k$. The link-route incidence matrix $A$ gives link loads $v=Af$. If link $e$ has delay ${\ell }_e(v_e)$, the route travel time isA Wardrop equilibrium is a feasible route-flow vector for which every used route has minimum travel time among the routes serving the same source-sink pair. Equivalently, there are numbers ${\lambda }_k$ such thatThe condition says that a traveler cannot lower their own delay by changing route. It does not assert that their choice minimizes the total delay experienced by all travelers. At a Wardrop equilibrium, unused routes may have exactly the same delay as used ones.

This static flow network model requires delay to depend on present link load, with each source-sink demand fixed. Models from queueing theory instead describe vehicles or packets as discrete customers whose delay depends on random arrivals, service and accumulated queues; a time-dependent model must also track changes of flow and travel-time propagation. Those models answer different questions from a static Wardrop equilibrium. The static model is nevertheless valuable because its route-choice condition has a precise convex optimization formulation, as developed next.

Assume each link delay ${\ell }_e$ is continuous and nondecreasing. Define the Beckmann potential on feasible route flows byThe integral of a nondecreasing function is convex, so $\Psi$ is a convex function. The chain rule givesAt a minimum, move a small amount of flow from a used route $p$ to any other route $q$ for the same source-sink pair. This is a feasible direction, and its one-sided derivative is $L_q-L_p\ge 0$. Thus every used route has minimum cost, establishing the Wardrop equilibrium conditions.

Conversely, if $f$ satisfies the Wardrop equilibrium conditions, then for any feasible $g$,Here ${\sum }_p{L}_p{f}_p={\lambda }_k{d}_k$ on each pair, whereas ${\sum }_p{L}_p{g}_p\ge {\lambda }_k{d}_k$. The supporting inequality for a convex function then gives $\Psi (g)\ge \Psi (f)$. ThereforeThe feasible route-flow set is compact, and the Beckmann potential is continuous, so a minimizer exists. If each ${\ell }_e$ is strictly increasing, the potential is strictly convex as a function of link loads. Two minimizers with distinct link-load vectors would have a midpoint with strictly smaller potential, a contradiction. Thus equilibrium link loads are unique in this case; route-flow nonuniqueness at a Wardrop equilibrium can still occur because different route decompositions can have the same link loads.

The optimization of selfish route choice must be distinguished from the minimization of total travel timeFor differentiable delays, the marginal social cost on link $e$ is ${\ell }_e(v_e)+v_e{\ell }_e^{\prime }(v_e)$, rather than just ${\ell }_e(v_e)$. The marginal external cost toll ${\tau }_e(v_e)=v_e{\ell }_e^{\prime }(v_e)$ makes each traveler's perceived link cost equal to this derivative. If $D$ is convex, the tolled Wardrop equilibria minimize $D$: the corresponding Beckmann potential is exactly $D$, up to its zero reference value. Convexity of $D$ is an additional assumption and does not follow merely from nondecreasing delays.

An elastic-demand extension assigns pair $k$ an inverse demand function $P_k(d_k)$ and allows demand to vary. Subtracting ${\sum }_k{\int }_0^{d_k}{P}_k(u)du$ from the Beckmann potential produces the optimization formulation: its marginal condition equates minimum route delay with marginal willingness to travel on positive-demand pairs. With decreasing inverse demands, the subtracted utility is concave and the resulting objective remains convex. This explains why both fixed-demand route choice and an elastic-demand Wardrop equilibrium fit a common optimization framework.

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.