Corollary 4.2 — with latencies , a feasible flow is optimal iff it is at Nash equilibrium
ProvedSelfishRouting.Linear.corollary_4_2linear-latencynash-equilibriumoptimal-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let every edge latency be proportional to its congestion, with , let the rates be positive and the route incidences . Then for every flow feasible for the rates ,
In such networks selfish routing loses nothing: the price of anarchy is exactly .
Formalization Note The latencies are the linear latencies with . "For any rate vector " is the universal quantification over positive rates. Routes are incidence columns (a disclosed generalization).
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Linear_Model import Definitions.Def_SelfishRouting_Linear_LinearLatency
Formal statement
namespace SelfishRouting.Linear
open KellyStochasticNetworks
/-- Corollary 4.2 (p. 15): if every latency is `ℓ_e(x) = a_e x`, then for any rates a feasible
flow is optimal iff it is at Nash equilibrium. -/
theorem corollary_4_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)
(a : Fin J → ℝ) (ha : ∀ j, 0 ≤ a j)
(x : Fin R → ℝ) (hx : x ∈ wardropFeasible s rate) :
IsOptimalFlow A s (linLatency a (fun _ => 0)) rate x ↔
SelfishRouting.Bicriteria.IsNashFlow A s (linLatency a (fun _ => 0)) rate x := by sorry
end SelfishRouting.Linear
Source
Roughgarden & Tardos, How Bad is Selfish Routing?, J. ACM 49(2) (2002), author's manuscript of 5 Dec 2001, p. 15, Corollary 4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.