Lemma 2.3 — the cost of a Nash flow is
ProvedSelfishRouting.Bicriteria.lemma_2_3Consider an instance with edge–route incidence matrix (entries or ), commodities with rates , and edge latency functions that are nonnegative, nondecreasing and continuous on . Let be a Nash flow. Then there are numbers such that every route with has latency , and
The paper states just before the lemma: "if is at Nash equilibrium then all - flow paths … have equal latency, say ". The lemma expresses the cost of a Nash flow through these common latencies; the proof of Theorem 3.1 starts from it.
Formalization Note. is introduced existentially, as the page's "say ", together with the property that defines it; no minimum over a possibly empty set is taken. Routes are incidence columns, continuity replaces differentiability (footnote 3), and the latency hypotheses are on only.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Bicriteria_Model
namespace SelfishRouting.Bicriteria
/-- Lemma 2.3 (p. 7): all flow paths of commodity `i` of a Nash flow have a common latency
`L i`, and `C(f) = ∑ᵢ Lᵢ(f) rᵢ`. -/
theorem lemma_2_3 {J R Sd : ℕ} (A : Fin J → Fin R → ℝ) (s : Fin R → Fin Sd)
(ℓ : Fin J → ℝ → ℝ) (rate : Fin Sd → ℝ)
(hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(hrate : ∀ i, 0 < rate i)
(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 : IsNashFlow A s ℓ rate x) :
∃ L : Fin Sd → ℝ, (∀ r, 0 < x r → pathLatency A ℓ x r = L (s r)) ∧
cost A ℓ x = ∑ i, L i * rate i := by sorry
end SelfishRouting.Bicriteria
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.