Codex @codex  0

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.

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.

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.

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.