Lemma 4.1(a) — Nash flows for linear latencies: on used paths
ProvedSelfishRouting.Linear.lemma_4_1_aLet every edge have a linear latency with , let the rates be positive, and let the route incidences be . Then a flow is at Nash equilibrium if and only if is feasible and for each commodity and routes with ,
This is Lemma 2.2 specialized to linear latencies, written out in the coefficients; it is used, together with part (b), to show that half of a Nash flow is optimal for half the rates.
Formalization Note The page prints ; since , this means , and the sum ranges over the edges with incidence in route . Feasibility is part of Definition 2.1, so it appears on the right-hand side. The paper states the lemma for linear latencies; is the standing assumption of §4 (p. 14). Routes are incidence columns (a disclosed generalization).
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Linear_Model import Definitions.Def_SelfishRouting_Linear_LinearLatency
namespace SelfishRouting.Linear
open KellyStochasticNetworks
/-- Lemma 4.1(a) (p. 15): with latencies `ℓ_e(x) = a_e x + b_e`, a flow is at Nash equilibrium
iff it is feasible and, for every commodity and routes `P, P'` serving it with `f_P > 0`,
`∑_{e ∈ P} (a_e f_e + b_e) ≤ ∑_{e ∈ P'} (a_e f_e + b_e)`. -/
theorem lemma_4_1_a {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)
(a b : Fin J → ℝ) (ha : ∀ j, 0 ≤ a j) (hb : ∀ j, 0 ≤ b j) (x : Fin R → ℝ) :
SelfishRouting.Bicriteria.IsNashFlow A s (linLatency a b) rate x ↔
(x ∈ wardropFeasible s rate ∧
∀ P P' : Fin R, s P = s P' → 0 < x P →
∑ j ∈ Finset.univ.filter (fun j => A j P = 1), (a j * linkFlow A x j + b j) ≤
∑ j ∈ Finset.univ.filter (fun j => A j P' = 1), (a j * linkFlow A x j + b j)) := by sorry
end SelfishRouting.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.