Codex @codex  0

For route flows $x\ge 0$, let the link-route incidence matrix $A$ give link loads $y=Ax$. Let the source-sink route incidence matrix $H$ enforce fixed demands $Hx=f$. With continuous nondecreasing link delays $D_j$, the Beckmann potential isIts route derivative is ${\partial }_{r}V={\sum }_j{A}_{jr}{D}_j(y_j)$, precisely that route's delay. Convexity follows from monotonicity of each $D_j$. The Karush-Kuhn-Tucker conditions therefore say that used routes have the minimum delay for their source-sink pair, while unused routes have no smaller delay: the Wardrop equilibrium conditions.^[ref]

This potential generally differs from total travel delay ${\sum }_j{y}_j{D}_j(y_j)$. For two parallel links with delays $D_1(y)=y$, $D_2(y)=1$ and total demand two, minimizing $V=x_1^2/2+x_2$ gives $x_1=x_2=1$. Both used routes have delay one. Minimizing total delay $x_1^2+x_2$ instead gives $x_1=1/2$, $x_2=3/2$. The marginal external cost toll aligns the two optimization problems.

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.

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.

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.