Lemma 2.2 — a feasible flow is at Nash equilibrium iff every used path has minimum latency
ProvedSelfishRouting.Linear.lemma_2_2Consider the routing model with routes given by edge incidences, commodities with positive rates , and edge latency functions that are nonnegative, nondecreasing and continuous on . Let be a route flow. Then is at Nash equilibrium (Definition 2.1) if and only if is feasible and for every commodity and routes with ,
The right-hand side is the Wardrop condition. This lemma turns the deviation-based Definition 2.1 into a condition on the latencies at alone, which is what all of the paper's later arguments use.
Formalization Note The right-hand side is the published KellyStochasticNetworks.IsWardropEquilibrium (which includes feasibility). Continuity replaces the paper's differentiability (footnote 3, p. 7, licenses this), which weakens a hypothesis; the latency hypotheses are imposed only on , where flows live. Definition 2.1 is formalized with and (see the definition item). Routes are incidence columns rather than simple paths, a disclosed generalization.
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Linear_Model
namespace SelfishRouting.Linear
open KellyStochasticNetworks
/-- Lemma 2.2 (Roughgarden–Tardos, p. 7): for latencies that are nonnegative, nondecreasing
and continuous on `[0, ∞)`, a flow is at Nash equilibrium (Definition 2.1) if and only if it
is feasible and every route carrying positive flow has latency at most that of any route
serving the same commodity (the Wardrop condition). -/
theorem lemma_2_2 {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 → ℝ) :
SelfishRouting.Bicriteria.IsNashFlow A s ℓ rate x ↔ IsWardropEquilibrium A s ℓ rate x := by sorry
end SelfishRouting.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.