Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 37 / 2

For a steady flow network, let each origin-destination class $k$ have fixed demand $d_k$. Route flows $h_r\ge 0$ satisfy ${\sum }_{r\in R_k}{h}_r=d_k$. The link flow is $y_j={\sum }_r{A}_{jr}{h}_r$, and a link has continuous travel delay ${\ell }_j(y_j)$. Its route delay is $c_r(h)={\sum }_j{A}_{jr}{\ell }_j(y_j)$.

A Wardrop equilibrium describes nonatomic traffic: each traveler is too small to alter aggregate delays by changing route. For each class there is a minimum delay ${\lambda }_k$ such thatThus all used routes of one class have equal minimum cost, and an unused route cannot offer a shorter trip. The condition concerns private travel time, rather than total network delay.

Equivalently, for every feasible route vector $\tilde{h}$,Indeed, each used route has class minimum cost, so reallocating demand cannot reduce the cost evaluated at the original flows; conversely a positive flow on a non-minimum route gives an improving transfer. This variational inequality form remains meaningful even when route costs are not separable link functions.

When link delays are separable and nondecreasing, Wardrop equilibria minimize the Beckmann potentialover the feasible route-flow polytope. Its derivative with respect to $h_r$ is $c_r(h)$. Since the integrals are convex, the first-order inequality for a global minimum is exactly the Wardrop equilibrium inequality in part (a). Alternatively, the Karush-Kuhn-Tucker conditions equate used-route derivatives to the multiplier for their demand constraint, with larger derivatives on unused routes. Continuity gives existence on the compact feasible set. Strictly increasing link delays give unique link flows, although different route decompositions can still give route-flow nonuniqueness at a Wardrop equilibrium.

The system objective is instead total travel time,For differentiable delays its marginal cost is ${\ell }_j(y_j)+y_j{\ell }_j^{\prime }(y_j)$, not simply ${\ell }_j(y_j)$. Thus an equilibrium optimizing the Beckmann potential generally fails to minimize total delay. A marginal external cost toll $y_j{\ell }_j^{\prime }(y_j)$ makes travelers face the social marginal cost and implements a system optimum under the appropriate convexity assumptions.

These formulations clarify the modeling distinction: nonatomic users optimize their own paths; a planner optimizes total delay. For nonseparable or nonmonotone costs, the variational description can remain applicable while the Beckmann potential argument, existence or uniqueness needs new hypotheses.

Braess paradox is the possibility that adding a route reduces the attainable equilibrium performance, despite enlarging the feasible set for a planner.

Take unit demand from $O$ to $D$. Initially the routes are $O\to U\to D$ and $O\to V\to D$. The links $O\to U$ and $V\to D$ have delay equal to their own flow; $U\to D$ and $O\to V$ have constant delay one. If the upper route has flow $h$, its delay is $h+1$, while the lower delay is $2-h$. The Wardrop equilibrium therefore splits traffic equally and hasNow add a directed zero-delay link $U\to V$. Let upper, lower and middle route flows be $a,b,c$ with $a+b+c=1$. Their delays are respectively $2-b$, $2-a$ and $2-a-b$. If $a>0$, its route would be strictly more expensive than the middle route; likewise $b>0$ is impossible at equilibrium. Hence $a=b=0$, $c=1$. All three routes then have delay two, so this is an equilibrium, andThe cheaper-looking cross-link tempts everyone onto both flow-dependent links. No individual can improve after congestion has built up. A planner could retain the old split and ignore the new link, so the feasible optimum cannot worsen. The paradox concerns selfish equilibrium, not the physical disappearance of the earlier allocation.