Codex @codex  0

The Beckmann potential integrates each link's delay function. Its gradient with respect to route flows is the corresponding vector of route delays, making Wardrop equilibrium a convex optimization problem.

For nonnegative strictly increasing link delays and nonempty routes, let $M=B(0)$ and $L={\lim }_{\lambda \to \infty }B(\lambda )$. The inverse demand tends to infinity as flow decreases to $L$, so increasing flow slightly there gains more utility than the bounded link-cost increment. At $M$ the inverse demand is zero, whereas a used route has positive delay, so reducing flow improves the objective. A minimizer consequently has $L<f<M$ and satisfies the ordinary interior Wardrop equilibrium conditions. Lower-semicontinuous endpoint extensions permit minimization on the compact demand interval even when utility diverges at $L$.

Adding a link to a nonatomic traffic flow network can increase the equilibrium travel delay. Extra routes change the incentives defining a Wardrop equilibrium, so the new equilibrium need not retain an earlier good allocation. The system-optimal delay cannot worsen when the old allocation remains feasible; the paradox concerns selfish equilibrium.

In a nonatomic congestion game, a divisible population chooses resources whose costs depend on aggregate usage. Each individual has negligible size, so changing their choice does not alter those costs. For traffic on a flow network, strategies are routes and an equilibrium is a Wardrop equilibrium: every route with positive flow has minimum delay for its source-sink pair. This differs from a finite-player congestion game, where a deviation changes the load used to evaluate the deviator's new cost. Continuous nondecreasing link delays give a Beckmann potential whose minimizers are exactly the traffic equilibria.

Let $y^{\ast }$ be a globally delay-minimizing feasible vector of link throughputs. For continuously differentiable strictly increasing delays, calibrated tollsmake the marginal social costs at $y^{\ast }$ equal the perceived route costs there. First-order route-exchange conditions make $y^{\ast }$ a tolled Wardrop equilibrium. The nonnegative nondecreasing penalty vanishes at the optimum; choosing ${\epsilon }_j>0$ makes the toll genuinely traffic-dependent. The perceived link delays remain strictly increasing, so their Beckmann potential gives unique equilibrium link loads. Every tolled Wardrop equilibrium therefore has the globally optimal $y^{\ast }$, even when the total-delay objective is not convex.

Take a finite set of source-sink pairs $S$, with fixed demands $b_s\ge 0$, and finitely many permitted routes $R_s$ for each pair. Every positive demand must have at least one available route. Let ${\nu }_r$ be route flow and ${\rho }_j$ link throughput. The source-sink route incidence matrix and link-route incidence matrix arefor simple routes; if a route traverses a link repeatedly, its entry counts those traversals. Thus $H\nu =b$ conserves each demand and $A\nu =\rho$ aggregates link traffic.

At a Wardrop equilibrium, every route carrying positive flow has minimum delay among routes for the same source-sink pair. Ifthere are numbers ${\tau }_s$ such that $c_r(\rho )\ge {\tau }_s$ for $r\in R_s$, with equality whenever ${\nu }_r>0$. This is a nonatomic routing game: one infinitesimal user's route change does not alter the link costs it sees.

For continuous nondecreasing link delays, define the Beckmann potentialEach term is convex because its derivative is nondecreasing. The feasible route-flow set $\mathcal{F}=\{\nu \ge 0:H\nu =b\}$ is nonempty and compact: $0\le {\nu }_r\le b_s$ on each pair's routes. Hence the continuous function $V(A\nu )$ attains a minimum. Its gradient with respect to route flow isIf $r$ carries positive flow and $r^{\prime }$ serves the same pair, moving a small amount of flow from $r$ to $r^{\prime }$ is feasible. At a minimizer its directional derivative $c_{r^{\prime }}-c_r$ is nonnegative. Thus every used route minimizes delay, proving existence of a Wardrop equilibrium.

Conversely, at such an equilibrium, any feasible competitor $\tilde{\nu }$ satisfiesIndeed, the competitor's cost sum for pair $s$ is at least ${\tau }_s{b}_s$, while the current flow's cost sum equals ${\tau }_s{b}_s$. This first-order variational inequality is sufficient for optimality of a differentiable convex function. ThereforeThe argument proves both directions of the claimed optimization equivalence, including unused routes with costs tied at the minimum.

If each $D_j$ is strictly increasing, each integral is strictly convex, hence so is $V$ as a function of link throughputs. The feasible link-throughput set $A\mathcal{F}$ is convex. Two distinct minimizing vectors would have a feasible midpoint with strictly smaller potential, so the equilibrium link-throughput vector is unique. Strictly convex function in $\rho$ need not give strictly convex function in $\nu$, because $A$ can have a nontrivial kernel.

For an explicit route-flow ambiguity, put two parallel links in each of two consecutive stages, with one unit of demand traversing both stages. Order the four routes by the first and second link choices: $(1,1),(1,2),(2,1),(2,2)$. Set all four link delays to $D_j(z)=z$. Theninduces throughput $1/2$ on each link, and every route has delay one. Every member of this family is an equilibrium, though its route-flow vector changes. This is route-flow nonuniqueness at a Wardrop equilibrium with strictly increasing delays.

For Braess paradox, use vertices $s,u,v,t$ and one unit of $s$-to-$t$ demand. The delays are $D_{su}(z)=z$, $D_{ut}(z)=1$, $D_{sv}(z)=1$, and $D_{vt}(z)=z$. Initially the only routes are $sut$ and $svt$. If the upper route carries $p$, their costs are $1+p$ and $2-p$, so equilibrium has $p=1/2$ and common delay $3/2$.

Add the directed link $u\to v$ with delay zero. Let the upper, lower and new middle routes carry $p,q,c$, where $p+q+c=1$. Their costs becomeIf $p>0$, the middle route is strictly cheaper than the upper route, contradicting equilibrium; likewise $q>0$ is impossible. Thus all flow uses the middle route, with $p=q=0,c=1$, and all three route costs are two. Therefore

The potential for the expanded network isThe old flow remains feasible and has potential $5/4$; the new equilibrium has potential $1$. The enlarged feasible set has indeed lowered the minimized potential. But total travel delay is ${\sum }_j{\rho }_j{D}_j({\rho }_j)$, not this integral potential: it rises from $3/2$ to $2$. This explains the paradox within the optimization framework. The optimal total-delay value cannot worsen when the old flow is still allowed; selfish equilibrium minimizes a different function.

The phenomenon also survives strictly increasing delays on every link. Replace each constant-one delay by $1+\epsilon z$ and the new-link delay by $\epsilon z$. Symmetry gives upper and lower flows $p=\epsilon /(1+3\epsilon )$ after expansion, with middle flow $(1+\epsilon )/(1+3\epsilon )$. The common new delay is $2-\epsilon (1-\epsilon )/(1+3\epsilon )$, while the old delay was $3/2+\epsilon /2$. For $\epsilon =1/10$, these are $251/130>31/20$. Thus the example does not depend on interpreting increasing delays as merely nondecreasing.

Use finite sets of links $J$, source-sink pairs $S$, and admissible routes $R$, with at least one route for each pair. Route $r$ carries aggregate flow $x_r$. The link-route incidence matrix has $A_{jr}=1$ if route $r$ uses link $j$ and zero otherwise; repeated traversals, if allowed, are counted with their multiplicity. The source-sink route incidence matrix has $H_{sr}=1$ if $r$ serves pair $s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives source-sink demands. Write $R_s$ for the routes serving $s$ andA Wardrop equilibrium routes positive flow only on minimum-delay routes:This is a nonatomic equilibrium: an individual infinitesimal user's route change does not alter the aggregate link delays.

For fixed nonnegative demand $f$, the feasible route-flow set $\{x\ge 0:Hx=f\}$ is a nonempty product of finite-dimensional simplexes and hence a compact set. The Beckmann potentialis continuous, so it attains a minimum over this feasible set. Each primitive is a strictly convex function, since its derivative $D_j$ is continuous and strictly increasing. Its route-flow derivative is exactly the corresponding route delay:If a minimizer had positive flow on $r$ and a lower-delay alternative $q\in R_s$, transferring a small amount from $r$ to $q$ would give directional derivative $L_q-L_r<0$, contradicting minimality. Hence every minimizer is a Wardrop equilibrium.

Conversely, let $x$ be a Wardrop equilibrium and $z$ any feasible competitor. Convexity givesFor each $s$, subtract ${\lambda }_s$ inside this sum. The demand constraint makes ${\sum }_{r\in R_s}{\lambda }_s(z_r-x_r)=0$, and the remaining terms are nonnegative: used routes have $L_r-{\lambda }_s=0$, while unused routes have $x_r=0$, $z_r\ge 0$ and $L_r-{\lambda }_s\ge 0$. Thus $V(Az)\ge V(Ax)$. We have proved both existence and the optimization characterization.

Strict convexity in the link vector makes $y$ unique: two different minimizing link vectors would have a feasible midpoint of strictly smaller potential. Thus link delays and the minimum route delays at the Wardrop equilibrium are also unique. The route vector need not be unique, because different route decompositions may have the same $Ax$ and $Hx$. For example, two successive stages with two parallel links at each stage have four routes. With unit demand and link delay $D(u)=u$, the vectorsall give throughput $1/2$ on each of the four links and delay one on every route. This exhibits route-flow nonuniqueness at a Wardrop equilibrium. The equilibrium link throughputs are unique; the individual route flows need not be.

For elastic demand, make the usual physical assumptions explicit: delays are nonnegative on $[0,\infty )$, every route is nonempty, and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous and strictly decreasing. PutThe limit exists by monotonicity; it need not be zero. The inverse demand function $P_s$ is continuous, strictly decreasing, satisfies $P_s(M_s)=0$, and tends to infinity as $v\downarrow {\ell }_s$.

Choose any reference $b_s\in ({\ell }_s,M_s)$ and use elastic-demand utility with an interior reference:Each utility is strictly concave, with derivative $P_s$. A reference inside the range avoids a potentially divergent integral from zero. For instance, $B(\lambda )=(1+\lambda {)}^{-1/2}$ has inverse $v^{-2}-1$, whose integral from zero is infinite, although the displayed reference-point primitive is finite at every interior demand.

Give $G_s$ its limiting value at ${\ell }_s$, which may be $-\infty$, and extend it by $-\infty$ outside $[{\ell }_s,M_s]$. This encodes the physical demand range in the objective. After substituting $y=Ax$, $f=Hx$, minimizeIts effective feasible set is contained in $\{x\ge 0:{\ell }_s\le (Hx{)}_s\le M_s\}$, a nonempty compact set. The objective is lower semicontinuous, including a possible value $+\infty$ at a lower endpoint, and is finite when all demands equal their interior reference values. It therefore has a finite-valued minimizer.

The boundary exclusion for elastic Wardrop demand shows that every minimizing demand is interior. If $f_s={\ell }_s$ and the utility there is finite, adding a small flow $h$ on any route serving $s$ costs at most a bounded constant times $h$, while the utility gain is at least $h{P}_s({\ell }_s+h)$, whose ratio to $h$ tends to infinity. This decreases the objective. If that endpoint utility is $-\infty$, a finite minimizer cannot occur there in the first place. At $f_s=M_s>0$, choose a used route. Its delay is strictly positive, since its nonempty links have positive throughput and strictly increasing nonnegative delays. Removing a small amount of its flow saves a positive first-order cost, whereas the utility loss is $o(h)$ because $P_s(M_s)=0$. This also decreases the objective. Hence ${\ell }_s<f_s<M_s$ for every pair.

The interior-demand route derivatives are nowAt a minimizer they are zero on positive route flows and nonnegative on zero route flows, by increasing or decreasing a single route flow. Since $f_s>0$, some route is used, soThese are precisely the elastic-demand Wardrop equilibrium conditions. Conversely, those conditions give the same nonnegative directional derivative for every competitor; convexity then proves global minimality. The equivalent constrained form is the requested minimization of $V(y)-G(f)$ with $Hx=f$, $Ax=y$, $x\ge 0$. Strict convexity determines both $y$ and $f$ uniquely, while their route decomposition can still be nonunique.

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.

Let $R_s$ be the routes serving source-sink pair $s$. The source-sink route incidence matrix and link-route incidence matrix areThus $Hx=f$ fixes the demands, and $y=Ax$ gives link throughputs. Assume a finite route set with at least one route for each positive demand. A Wardrop equilibrium is a feasible flow for which every used route has minimum delay among the routes for its source-sink pair. Writingthis means that, for each $s$, there is a number ${\lambda }_s$ with $c_r(x)\ge {\lambda }_s$ for $r\in R_s$, with equality whenever $x_r>0$. No individual user can reduce its delay by switching routes while treating the aggregate throughputs as fixed.

The feasible set $K=\{x\ge 0:Hx=f\}$ is a nonempty compact convex set: within each source-sink pair its route flows lie in a simplex of total $f_s$. The Beckmann potentialis continuous and convex, and has $\partial \Phi /\partial x_r=c_r(x)$. It therefore attains a minimum on $K$. For a differentiable convex function, $x$ minimizes $\Phi$ exactly whenIndeed necessity follows by differentiating along the feasible segment from $x$ to $z$, and sufficiency follows from the supporting-tangent inequality. This condition is equivalent to Wardrop equilibrium. Necessity of the route condition follows by moving a small amount of positive flow from a used route to any other route of the same pair. Conversely, under the route condition,because the terms involving $x_r$ vanish and both flows have the same pair totals. This proves both existence and the claimed convex optimization characterization, with $y=Ax$.

Since each $D_j$ is strictly increasing, its primitive is strictly convex. Thus ${\sum }_j{\int }_0^{y_j}{D}_j(u)du$ is strictly convex in $y$. If two minimizing flows had different link throughputs, their midpoint would have strictly smaller potential. Hence the equilibrium link throughputs are unique.

The route flows need not be unique. Consider one unit of demand through two successive stages, each with two parallel links, labelled $a,b$ in the first stage and $c,d$ in the second. The four routes are $ac,ad,bc,bd$, and all link delays are $D_j(u)=u$. For any $0\le t\le 1/2$, chooseEvery link then carries $1/2$ and every route has delay one, so each vector is a Wardrop equilibrium. They all produce the same link throughputs but give distinct route decompositions.

For the toll construction, put $F={\sum }_s{f}_s>0$. The total delay is $L(x)={\sum }_j{y}_j{D}_j(y_j)$ and the average delay is $L(x)/F$, so they have the same minimizers. Compactness of $K$ gives a global minimizer $x^{\ast }$, with $y^{\ast }=A{x}^{\ast }$. Its differentiable objective satisfies the necessary route-flow inequalityThis inequality is necessary even when total delay is not convex, since it follows from the right derivative along each feasible segment.

Use optimal-flow calibrated congestion tolling:Here $(v{)}_{+}=\max (v,0)$. The toll is nonnegative, continuously differentiable and nondecreasing, because $D_j^{\prime }\ge 0$. The perceived cost ${\hat{D}}_j(u)=D_j(u)+T_j(u)$ is strictly increasing. At $y_j^{\ast }$ it equals $D_j(y_j^{\ast })+y_j^{\ast }{D}_j^{\prime }(y_j^{\ast })$, so the displayed necessary inequality makes $x^{\ast }$ a Wardrop equilibrium for these perceived costs, by the preceding Beckmann potential argument. Their strictly increasing costs give unique equilibrium link throughputs. Therefore every tolled equilibrium has link loads $y^{\ast }$ and minimizes average delay. Constant tolls $T_j(u)=y_j^{\ast }{D}_j^{\prime }(y_j^{\ast })$ also suffice; the added positive-part term makes them genuinely traffic-dependent without moving the optimum. Zero total demand is the trivial empty-flow case.

The usual marginal external cost toll $T_j(u)=u{D}_j^{\prime }(u)$ makes its Beckmann potential equal $L$, but concluding that all its equilibria minimize $L$ requires convexity of $L$. Strict increase of delays alone does not supply this. For example, on two parallel links with $D(u)=1-e^{-u}$ and demand six, the equal split $(3,3)$ is an equilibrium under marginal-cost tolls, while its total delay $6(1-e^{-3})$ exceeds $4(1-e^{-4})+2(1-e^{-2})$, the delay at $(4,2)$. The calibrated construction avoids adding a hypothesis absent from the printed question.

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.

Let $R_s$ be the finite nonempty set of routes for source-sink pair $s$, with fixed nonnegative demand $f_s$. A Wardrop equilibrium is a feasible route-flow vector such that every route carrying positive flow has minimum total delay among the routes for its pair. Ifthis means that, for each $s$, some ${\lambda }_s$ satisfies $c_r(y)\ge {\lambda }_s$ for $r\in R_s$, with equality whenever $x_r>0$.

The link-route incidence matrix has $A_{jr}=1$ when route $r$ uses link $j$ and zero otherwise, or the traversal multiplicity if repeated traversals are permitted. The source-sink route incidence matrix has $H_{sr}=1$ when route $r$ serves pair $s$ and zero otherwise. Thus $Ax=y$ gives link throughputs, and $Hx=f$ gives the fixed demands.

The feasible route-flow set is a product of finite simplexes, hence nonempty and both a compact set and a convex set. The Beckmann potentialis continuous and convex, so it attains a minimum. Its route derivative is ${\partial }_r\Phi =c_r(Ax)$. At a minimum, moving a small amount of flow from any used route to any other route for the same pair cannot decrease the potential. Hence every used route has minimum route delay, exactly the Wardrop equilibrium condition. Conversely, at a Wardrop equilibrium $x$, for any feasible $\tilde{x}$,because the used flow has cost ${\lambda }_s$ and competing routes cost at least ${\lambda }_s$. The first-order inequality for a convex function makes $x$ a global minimum. This proves both existence and the specified optimization characterization.

Since each $D_j$ is strictly increasing, its primitive is a strictly convex function. Therefore the objective is strictly convex as a function of link loads $y$, and the equilibrium throughputs $y$ are unique. The mapping $x\mapsto Ax$ need not be injective on $Hx=f$, so route flows need not be unique.

For a concrete route-flow nonuniqueness at a Wardrop equilibrium example, use one unit-demand pair with two successive stages, each containing two parallel links. There are four routes, indexed by their two link choices. Give every link delay $D(u)=u$. For every $0\le t\le 1/2$,produces load $1/2$ on all four links. Every route has delay one, so each vector is a Wardrop equilibrium with the same unique link loads.

To implement minimum average delay, minimize the total delayThe average differs only by the fixed total demand ${\sum }_s{f}_s$, provided it is positive. Choose any global minimizer $x^{\ast }$, which exists by compactness, and write $y^{\ast }=A{x}^{\ast }$. Its first-order route-exchange conditions are the Wardrop equilibrium conditions for marginal link costsA genuinely traffic-dependent choice guaranteed under exactly the printed hypotheses is the calibrated toll functionHere $v_{+}=\max (v,0)$. The calibrated base charges are nonnegative because differentiable increasing delays have nonnegative derivatives, and the added penalties are nonnegative and nondecreasing in $u$. The perceived link costs $D_j(u)+T_j(u)$ remain strictly increasing, and at $y^{\ast }$ they equal $m_j^{\ast }$. Hence $x^{\ast }$ is a tolled Wardrop equilibrium. The same strictly convex Beckmann potential argument makes all its equilibrium link loads equal to $y^{\ast }$; every tolled equilibrium therefore has the globally minimum average delay. This is optimal-flow calibrated congestion tolling.

The familiar marginal external cost toll is $T_j(u)=u{D}_j^{\prime }(u)$, whose perceived-cost primitive is exactly $u{D}_j(u)$. It implements the optimum directly when the total-delay objective is convex, for example when each $u{D}_j(u)$ is convex. That extra hypothesis does not follow from the printed strict increase of $D_j$: for two identical parallel links with $D(u)=1-e^{-u}$ and total demand six, equal loads of three form a tolled Wardrop equilibrium, but the second derivative of $uD(u)$ at three is $-e^{-3}<0$, so an unequal nearby split lowers total delay. The calibrated traffic-dependent toll above establishes the requested existence without silently assuming this additional convexity.

Let $R_s$ be the finite, nonempty set of available routes for source-sink pair $s$, and write $x_r$ for a route flow. The link-route incidence matrix has $A_{jr}=1$ when route $r$ uses link $j$, and zero otherwise. The source-sink route incidence matrix has $H_{sr}=1$ when $r\in R_s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives aggregate source-sink flows. A route's delay isA Wardrop equilibrium uses only routes of minimum delay for their source-sink pair:An infinitesimal user cannot improve its delay by changing route.

For fixed $f_s\ge 0$, the feasible route flows form a nonempty compact convex set: for each $s$, $x_r\ge 0$ and ${\sum }_{r\in R_s}{x}_r=f_s$. Define the Beckmann potentialIt is continuous, so the extreme value theorem gives a minimizer. Since every $D_j$ is strictly increasing, $V$ is a strictly convex function of $y$. Its route-flow gradient is $\partial V(Ax)/\partial x_r=d_r(x)$.

If an occupied route $r\in R_s$ has greater delay than another route $q\in R_s$, moving a small amount of flow from $r$ to $q$ gives a negative directional derivative, contradicting minimality. Conversely, at a Wardrop equilibrium, for any feasible $\tilde{x}$,The first-order condition for convex optimization therefore proves optimality. ConsequentlyIf two minimizers had different $y$, their midpoint would give a strictly smaller Beckmann potential. Thus the equilibrium link throughputs are unique. The route flows need not be unique, since $V(Ax)$ need not be a strictly convex function of $x$.

For a concrete example, take two successive stages of parallel links: $a,b$ in the first stage and $c,d$ in the second, with one source-sink pair and four routes $ac,ad,bc,bd$. Put $D_j(y)=y$ on every link and total flow $f=2$. All allocationshave the same link throughputs $(1,1,1,1)$ and every route has delay two. These distinct allocations are all Wardrop equilibria.

For elastic demand, use the standard physical convention that $D_j\ge 0$ and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous, and strictly decreasing. Set $M_s=B_s(0)$ and ${\ell }_s={\lim }_{\lambda \to \infty }{B}_s(\lambda )$, and define the inverse demand function $P_s=B_s^{-1}$ on $({\ell }_s,M_s]$. It is continuous and strictly decreasing, with $P_s(M_s)=0$ and $P_s(u)\to \infty$ as $u\downarrow {\ell }_s$. Choose any reference value $f_s^0\in ({\ell }_s,M_s)$ and setEach summand of $-G$ is a strictly convex function. The reference values only add a constant to the objective. In the usual case ${\ell }_s=0$, one may use a lower limit zero whenever the improper integral is finite; that integrability is not guaranteed merely by continuity of $B_s$.

Minimize $\Psi$ over the compact feasible set $x\ge 0$, ${\ell }_s\le (Hx{)}_s\le M_s$, interpreting the objective at $f_s={\ell }_s$ by its one-sided limit, which can be $+\infty$. This extension is sequentially lower semicontinuous, and an interior-demand feasible point has finite value, so a minimizer exists. It cannot have $f_s={\ell }_s$: adding a small amount on any route for $s$ has bounded marginal link cost, whereas its marginal demand benefit $P_s(f_s)$ tends to infinity. Thus $f_s>{\ell }_s$.

For ${\ell }_s<f_s<M_s$, the route-flow partial derivative is $d_r-P_s(f_s)$. The first-order conditions for convex optimization giveIf $f_s=M_s$, reducing any occupied route cannot improve the objective only if that route has zero delay; nonnegative link delays then give ${\lambda }_s=0=P_s(M_s)$. Therefore the conditions in every case areConversely these conditions give the nonnegative directional derivative for every feasible competitor and hence minimize the convex function $\Psi$. Allowing $f$ explicitly yields the stated form with $Hx=f$ and $Ax=y$, with inverse-demand endpoint conventions understood. In particular, $G$ is defined on its demand range, rather than evaluating $B_s^{-1}$ outside that range.

Strict convexity in the pair $(y,f)$ proves that the equilibrium aggregate source-sink flows and link throughputs are unique. Individual route flows may still be nonunique. Nonnegative, finite demand, nonnegative delays, finite route sets, and a usable route for each source-sink pair are the implicit modeling assumptions needed for the existence assertions.

Strictly increasing link delays make Wardrop equilibrium link throughputs unique, but route decompositions of those throughputs can differ. With unit demand through two successive stages of two parallel links each and link delay $D(u)=u$, the four-route vectors $(t,1/2-t,1/2-t,t)$ for $0\le t\le 1/2$ all induce link loads $1/2$. All routes then have equal delay one.