Theorem 4.3 — a Wardrop equilibrium exists
ProvedKellyStochasticNetworks.wardrop_equilibrium_existsModel a road network as a set of directed links. Routes are subsets of links, recorded by a link-route incidence matrix with entries and ; each route serves a single source–destination pair ; and is the flow to be carried between pair . Each link has a delay function , continuous and increasing, and the delay along route at route flows is with .
Suppose every source–destination pair is served by at least one route. Then a Wardrop equilibrium exists: there is a feasible vector of route flows — non-negative, with the flows on the routes serving summing to — such that
Every route actually carrying traffic is, in delay, a shortest route for the traffic it carries, so no driver has an incentive to switch.
Existence is what makes the model describe anything at all. It is not accompanied by a uniqueness claim — the equilibrium route flows need not be unique, though the link loads are — nor by any efficiency claim: Braess's paradox says the equilibrium can be worse for everyone than a routing pattern that a planner could impose.
Formalization Note The two hypotheses beyond the model are exactly what make the feasible set non-empty: each flow requirement is non-negative, and each source–destination pair is served by some route. The equilibrium condition is written as an inequality against every route serving the same pair, which is the displayed minimum with the minimum written out. Delay functions are total and monotone in the weak sense, which excludes the vertical asymptote that Figure 4.5 permits.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop
namespace KellyStochasticNetworks
theorem wardrop_equilibrium_exists {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))
(hf : ∀ σ, 0 ≤ f σ) (hserved : ∀ σ, ∃ r, s r = σ) :
∃ x : Fin R → ℝ, IsWardropEquilibrium A s D f x := by sorry
end KellyStochasticNetworksConfirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.