= Solution
Let $R_s$ be the routes serving source-sink pair $s$. The <source-sink route incidence matrix> and <link-route incidence matrix> are
$$
H_{sr}=\mathbf1_{\{r\in R_s\}},\qquad A_{jr}=\mathbf1_{\{j\in r\}}.
$$
Thus $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. Writing
$$
c_r(x)=\sum_jA_{jr}D_j((Ax)_j),
$$
this means that, for each $s$, there is a number $\lambda_s$ with $c_r(x)\geq\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\geq0: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 potential>
$$
\Phi(x)=\sum_j\int_0^{(Ax)_j}D_j(u)\,du
$$
is 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 when
$$
\sum_rc_r(x)(z_r-x_r)\geq0\qquad\text{for every }z\in K.
$$
Indeed 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,
$$
\sum_rc_r(x)(z_r-x_r)=\sum_s\sum_{r\in R_s}(c_r(x)-\lambda_s)z_r\geq0,
$$
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 \b[the equilibrium link throughputs are unique].
\b[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\leq t\leq1/2$, choose
$$
(x_{ac},x_{ad},x_{bc},x_{bd})=(t,1/2-t,1/2-t,t).
$$
Every 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_sf_s>0$. The total delay is $L(x)=\sum_jy_jD_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^*$, with $y^*=Ax^*$. Its differentiable objective satisfies the necessary route-flow inequality
$$
\sum_j\bigl[D_j(y_j^*)+y_j^*D_j'(y_j^*)\bigr](A(z-x^*))_j\geq0\qquad(z\in K).
$$
This 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>:
$$
\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 toll is nonnegative, continuously differentiable and nondecreasing, because $D_j'\geq0$. The perceived cost $\widehat D_j(u)=D_j(u)+T_j(u)$ is strictly increasing. At $y_j^*$ it equals $D_j(y_j^*)+y_j^*D_j'(y_j^*)$, so the displayed necessary inequality makes $x^*$ a <Wardrop equilibrium> for these perceived costs, by the preceding <Beckmann potential> argument. Their strictly increasing costs give unique equilibrium link <throughputs>. Therefore \b[every tolled equilibrium has link loads $y^*$ and minimizes average delay]. Constant tolls $T_j(u)=y_j^*D_j'(y_j^*)$ 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)=uD_j'(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.
Back to article page
