A minimizer of is a Wardrop equilibrium
ProvedKellyStochasticNetworks.wardrop_from_minimizerConsider the convex program in the proof of Theorem 4.3:
If is feasible and minimizes this objective over the feasible set, then is a Wardrop equilibrium: every route carrying positive traffic has minimal delay among the routes serving the same source–destination pair.
This is the half of the book's one-to-one correspondence that delivers Theorem 4.3, since the feasible region is convex and compact and the objective is continuous, so a minimizer exists. The mechanism is the first-order conditions: differentiating in identifies the multiplier with the link delay , and differentiating in gives that the multiplier equals the route delay on routes carrying traffic and is a lower bound on the others. Read back, is the minimal delay available to the source–destination pair, which is Definition 4.2.
It is worth being clear about what is not being minimized. The objective is , not the total delay that a planner would want to minimize. Braess's paradox is exactly the gap between the two.
Formalization Note Minimality is stated directly as the defining inequality over the feasible set, so no optimization API is presupposed. The incidence matrix is constrained to have entries or , as in the book's definition for this chapter, and the delay functions are continuous and increasing in the weak sense.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop
namespace KellyStochasticNetworks
theorem wardrop_from_minimizer {J R Sd : ℕ} (A : Fin J → Fin R → ℝ) (s : Fin R → Fin Sd)
(D : Fin J → ℝ → ℝ) (f : Fin Sd → ℝ)
(hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(hD : ∀ j, Continuous (D j)) (hmono : ∀ j, Monotone (D j))
(x : Fin R → ℝ) (hx : x ∈ wardropFeasible s f)
(hmin : ∀ z ∈ wardropFeasible s f, wardropObjective A D x ≤ wardropObjective A D z) :
IsWardropEquilibrium A s D f x := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.