Lemma 4.3(a) — if is a Nash flow for with linear latencies, then is optimal for
ProvedSelfishRouting.Linear.lemma_4_3_alinear-latencyoptimal-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let every edge have a linear latency with , let the rates be positive and the route incidences , and let be a flow at Nash equilibrium for the rates . Then the flow , with , is optimal for the rates :
and is itself feasible for .
This is the first step of the proof of Theorem 4.5: half of a selfish flow is a socially optimal flow for half the traffic.
Formalization Note The rates are and the flow is . 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
/-- Lemma 4.3(a) (p. 15): with linear latencies, if `f` is at Nash equilibrium for the rates
`r`, then `f/2` is optimal for the rates `r/2`. -/
theorem lemma_4_3_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 → ℝ) (hx : SelfishRouting.Bicriteria.IsNashFlow A s (linLatency a b) rate x) :
IsOptimalFlow A s (linLatency a b) (fun i => rate i / 2) (fun r => x r / 2) := 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, Lemma 4.3(a)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.