Lemma 2.3 — the cost of a Nash flow is
ProvedSelfishRouting.Linear.lemma_2_3Under the standing assumptions (0/1 route incidences, positive rates , latencies nonnegative, nondecreasing and continuous on ), let be a flow at Nash equilibrium. Then all - routes carrying positive flow have a common latency , and
This expresses the cost of an equilibrium through one latency per commodity; it is the bridge between equilibrium latencies and costs in the proof of Theorem 4.5.
Formalization Note is stated existentially: there is a function on commodities such that every route with has for the commodity it serves, and . Since and is feasible, each commodity has a used route, so is determined. Continuity replaces differentiability (footnote 3, p. 7); routes are incidence columns (a disclosed generalization).
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Linear_Model
namespace SelfishRouting.Linear
/-- Lemma 2.3 (p. 7): at a Nash flow all used routes of commodity `i` have a common latency
`L i`, and the cost is `C(f) = ∑ᵢ Lᵢ(f) rᵢ`. -/
theorem lemma_2_3 {J R Sd : ℕ} (A : Fin J → Fin R → ℝ) (hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(s : Fin R → Fin Sd) (rate : Fin Sd → ℝ) (hrate : ∀ i, 0 < rate i)
(ℓ : Fin J → ℝ → ℝ) (hℓnn : ∀ j t, 0 ≤ t → 0 ≤ ℓ j t)
(hℓmono : ∀ j, MonotoneOn (ℓ j) (Set.Ici 0))
(hℓcont : ∀ j, ContinuousOn (ℓ j) (Set.Ici 0))
(x : Fin R → ℝ) (hx : SelfishRouting.Bicriteria.IsNashFlow A s ℓ rate x) :
∃ L : Fin Sd → ℝ, (∀ r, 0 < x r → SelfishRouting.Bicriteria.pathLatency A ℓ x r = L (s r)) ∧
SelfishRouting.Bicriteria.cost A ℓ x = ∑ i, L i * rate i := by sorry
end SelfishRouting.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.