Let $[0, 1] \subset \mathbb{R}$ be denoted $\mathbb{R}_{[0, 1]}$. Let $[0, \infty) \subset \mathbb{R}$ be denoted $\mathbb{R}_{\geq 0}$.
Let $G$ be a finite, connected graph. Associate with each edge $e_j$ of $G$ a function $l_j: \mathbb{R}_{[0, 1]} \mapsto \mathbb{R}_{\geq 0}$. We assume that $l_j$ are continuous and weakly increasing.
Mark two vertices on it $s$ and $t$, for "source" and "destination" respectively.
Let $\mathcal{P}_{st}$ be the set of paths (sequence of edges) connecting $s$ and $t$. Let $P_{st} = |\mathcal{P}_{st}|$. Let $\mathbf{f} \in \mathbb{R}_{[0, 1]}^{P_{st}}$ be a $P_{st}$-vector, with all elements in $[0, 1] \subset \mathbb{R}$. Let $f_i$ be the $i$th element of $\mathbf{f}$. We say that $\mathbf{f}$ is a flow on $G$ if: $$ \|\mathbf{f}\|_1 = \sum_{i = 1}^{P_{st}} |f_i| = \sum_{i = 1}^{P_{st}} f_i = 1 $$ In other words $\mathbf{f}$ represents the fraction of the total flow, which is assumed to be 1, going through the $i$th path.
Let $e \in G$ be an edge. The induced flow in an edge is: $$F_e = \sum_{i = 1}^{P_{st}} p_i(e)f_i$$
Where $p_i(e) = 0$ if $e \not\in \mathcal{P}_i \in \mathcal{P}_{st}$ ($e$ is not an edge in the path $\mathcal{P}_i$), where $\mathcal{P}_i$ is a path from $s$ to $t$. If $e \in \mathcal{P}_i$, then $p_i(e) = 1$. Thus, $F_e$ is the sum of the fraction of the flow in each path which uses edge $e$.
The latency on an edge $e$ is $L_e(F_e)$.
The latency of a path $\mathcal{P}_i$ is given by: $$ L(\mathcal{P}_i, \mathbf{f}) = \sum_{e \in \mathcal{P}_i} l_e(F_e)$$ In other words, $L(\mathcal{P}_i, \mathbf{f})$ is the sum of the latencies of the edges contained in $\mathcal{P}_i$.
We say that a flow $\tilde{\mathbf{f}}$ is a (Nash) equilibirium flow if: $$ \forall i,j \in \{1, 2, \dots, P_{st}\} | L(\mathcal{P}_i, \tilde{\mathbf{f}}) = L(\mathcal{P}_j, \tilde{\mathbf{f}})$$
The average latency of the network under some flow $\mathbf{f}$ is: $$ L_G(\mathbf{f}) = \sum_{i = 1}^{P_{st}} f_i L(\mathcal{P}_i, \mathbf{f})$$
Note that if $\mathbf{f}$ is an equilibrium flow, then the latency of each path in it is the same; call this latency $L^*$, so the average latency of the network is: $$ L_G(\mathbf{f}) = \sum_{i = 1}^{P_{st}} f_i L(\mathcal{P}_i, \mathbf{f}) = \sum_{i = 1}^{P_{st}} f_i L^* = L^* $$ because $\sum_i f_i = 1$.
Let $\mathbf{g}$ be some other flow. Then the average latency of $G$ due to flow $\mathbf{g}$ under latencies determined by $\mathbf{f}$ is: $$ L_G(\mathbf{g}|L(\mathbf{f})) = \sum_{i = 1}^{P_{st}} g_i L(\mathcal{P}_i, \mathbf{f})$$
Fact: if $\mathbf{f}$ is an equilibrium flow, then: $$ L_G(\mathbf{g}|L(\mathbf{f})) - L_G(\mathbf{f}) \geq 0 $$
I am having trouble proving the above fact. I know that:
$$ L_G(\mathbf{g}|L(\mathbf{f})) - L_G(\mathbf{f}) = L_G(\mathbf{g}|L(\mathbf{f})) - L^* = \left(\sum_{i}g_iL^*\right) - L^*$$ but it is not obvious to me why: $$ \sum_{i} g_i L^* \geq L^*, $$ since $\sum_{i} g_i = 1$.
Yet, I do expect that the latency $L_G(\mathbf{g}|L(\mathbf{f}))$ should be larger than $L^*$, because if I imagine $\mathbf{g}$ to be a perturbation of $\mathbf{f}$, that is I take a tiny bit of flow from one path and add it to the flow of another path, then I would expect that the latency of the perturbed network should be worse, so that the flow I re-allocated would naturally want to go back to its original allocation.
I suspect that I might have defined an equilibrium flow incorrectly? This result is noted in the following sources:
- https://theory.stanford.edu/~tim/papers/optima.pdf (Proposition 2.4)
- https://homes.cs.washington.edu/~karlin/GameTheoryBook.pdf (Ch. 8, Proposition 8.1.6)
In both cases, the results find it obvious to go from the definition of (Wardrop/Nash) equilibrium to the fact that: $$ \sum_{i} g_i L^* \geq L^* $$ However, this is far from obvious to me, perhaps it might be obvious to you?
The condition for a Nash equilibrium flow is not
$$L(\mathcal{P}_i, \tilde{\mathbf{f}}) = L(\mathcal{P}_j, \tilde{\mathbf{f}}).$$ for all $i,j.$ The condition is $$f_i>0\implies L(\mathcal{P}_i, \tilde{\mathbf{f}}) \leq L(\mathcal{P}_j, \tilde{\mathbf{f}})$$ for all $i,j,$ or equivalently $$f_i>0\implies L(\mathcal{P}_i, \tilde{\mathbf{f}}) =\min_jL(\mathcal{P}_j, \tilde{\mathbf{f}})=:L^*$$ for all $i.$
This can be interpreted as saying that no-one can benefit by choosing a different path than the one they are using. Moving to an unused path can still increase latency.
If all the paths are used ($f_i>0$ for all $i$) then you are correct that $L_G(\mathbf{g}|L(\mathbf{f}))=L^*,$ so perturbing the flow does not increase this quantity. $L_G(\mathbf{g}|L(\mathbf{f}))$ is a kind of linear approximation to $L(\mathbf{g})$ for $\mathbf{g}\approx\mathbf{f},$ analogous to a tangent plane for a differentiable function, so you might expect it to have zero slope at a critical point in the interior of its domain. (It's not quite a tangent because it's selfish and ignores the change in $L_e(f_e)$.)
That explains why we get inequalities rather than equalities. The fact can be proved as: \begin{align} L_G(\mathbf{g}|L(\mathbf{f})) &= \sum_{i = 1}^{P_{st}} g_i L(\mathcal{P}_i, \mathbf{f})\\ &\geq \sum_{i = 1}^{P_{st}} g_i L^*\\ &= L^*\\ &= \sum_{i = 1}^{P_{st}} f_i L(\mathcal{P}_i, \mathbf{f})\\ &= L_G(\mathbf{f}). \end{align}