Lemma 4.1(b) — optimal flows for linear latencies: on used paths
ProvedSelfishRouting.Linear.lemma_4_1_bLet every edge have a linear latency with , let the rates be positive, and let the route incidences be . Then a flow is (globally) optimal, i.e. feasible with for every feasible , if and only if is feasible and for each commodity and routes with ,
This is the first-order (Karush–Kuhn–Tucker) characterization of the convex quadratic program over feasible flows: a flow is optimal exactly when it is at Nash equilibrium for the marginal costs . Both directions are used in the proof of Theorem 4.5.
Formalization Note "Globally optimal" is optimality over all flows feasible for the same rates, not local optimality. The sums range over the edges with incidence in each route; the page's means . 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(b) (p. 15): with latencies `ℓ_e(x) = a_e x + b_e`, `a_e, b_e ≥ 0`, a flow is
(globally) optimal iff it is feasible and, for every commodity and routes `P, P'` serving it
with `f*_P > 0`, `∑_{e ∈ P} (2 a_e f*_e + b_e) ≤ ∑_{e ∈ P'} (2 a_e f*_e + b_e)`. -/
theorem lemma_4_1_b {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) (xstar : Fin R → ℝ) :
IsOptimalFlow A s (linLatency a b) rate xstar ↔
(xstar ∈ wardropFeasible s rate ∧
∀ P P' : Fin R, s P = s P' → 0 < xstar P →
∑ j ∈ Finset.univ.filter (fun j => A j P = 1), (2 * a j * linkFlow A xstar j + b j) ≤
∑ j ∈ Finset.univ.filter (fun j => A j P' = 1),
(2 * a j * linkFlow A xstar j + b j)) := by sorry
end SelfishRouting.Linear
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.