Lemma 2.2 — Nash flows are exactly the Wardrop equilibria
ProvedSelfishRouting.Bicriteria.lemma_2_2Consider an instance with edge–route incidence matrix (entries or ), commodities with rates , routes serving commodity , and edge latency functions that are nonnegative, nondecreasing and continuous on . A flow is a Nash flow (Definition 2.1) if and only if it is feasible for and, for every and all with ,
The right-hand side is the Wardrop condition: every route that carries flow has minimum latency among the routes of its commodity. The lemma is the working form of the equilibrium used in every later proof.
Formalization Note. The right-hand side is the published KellyStochasticNetworks.IsWardropEquilibrium, which includes feasibility; the page's "a flow feasible for instance " is therefore on both sides. Routes are arbitrary incidence columns (a generalization of simple paths). The page assumes differentiable latencies; continuity replaces differentiability, as licensed by footnote 3 (p. 7) and §3 (p. 11), which strengthens the statement. Hypotheses on are imposed only on , where edge flows live.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Bicriteria_Model
namespace SelfishRouting.Bicriteria
open KellyStochasticNetworks
/-- Lemma 2.2 (p. 7): Definition 2.1 is equivalent to the Wardrop condition. -/
theorem lemma_2_2 {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 → ℝ) :
IsNashFlow A s ℓ rate x ↔ IsWardropEquilibrium A s ℓ rate x := by sorry
end SelfishRouting.Bicriteria
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.