= Solution
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. If
$$
c_r(y)=\sum_jA_{jr}D_j(y_j),
$$
this means that, for each $s$, some $\lambda_s$ satisfies $c_r(y)\geq\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 potential>
$$
\Phi(x)=\sum_j\int_0^{(Ax)_j}D_j(u)\,du
$$
is <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 $\widetilde x$,
$$
\nabla\Phi(x)\cdot(\widetilde x-x)=\sum_s\sum_{r\in R_s}c_r(Ax)(\widetilde x_r-x_r)\geq0,
$$
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 \b[the equilibrium <throughputs> $y$ are unique]. The mapping $x\mapsto Ax$ need not be injective on $Hx=f$, so \b[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\leq t\leq1/2$,
$$
(x_{11},x_{12},x_{21},x_{22})=(t,\tfrac12-t,\tfrac12-t,t)
$$
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 delay
$$
L(x)=\sum_rx_rc_r(Ax)=\sum_j y_jD_j(y_j).
$$
The average differs only by the fixed total demand $\sum_sf_s$, provided it is positive. Choose any global minimizer $x^*$, which exists by compactness, and write $y^*=Ax^*$. Its first-order route-exchange conditions are the <Wardrop equilibrium> conditions for marginal link costs
$$
m_j^*=D_j(y_j^*)+y_j^*D_j'(y_j^*).
$$
A genuinely traffic-dependent choice guaranteed under exactly the printed hypotheses is the calibrated toll function
$$
\boxed{T_j(u)=y_j^*D_j'(y_j^*)+\varepsilon_j(u-y_j^*)_+^2,\qquad\varepsilon_j>0.}
$$
Here $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^*$ they equal $m_j^*$. Hence $x^*$ is a tolled <Wardrop equilibrium>. The same strictly <convex> <Beckmann potential> argument makes all its equilibrium link loads equal to $y^*$; 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)=uD_j'(u)$, whose perceived-cost primitive is exactly $uD_j(u)$. It implements the optimum directly when the total-delay objective is <convex>, for example when each $uD_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.
Back to article page
