Lemma 4.3(b) — the marginal cost of a path w.r.t. equals its latency w.r.t. :
ProvedSelfishRouting.Linear.lemma_4_3_blinear-latencymarginal-costp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let every edge have a linear latency , with marginal cost . For every route flow and every route , the marginal cost of increasing the flow on with respect to equals the latency of with respect to :
It connects the marginal costs at the optimal flow of Lemma 4.3(a) with the equilibrium latencies of , and through Lemma 2.3 with the cost .
Formalization Note The page states (b) under the lemma's preamble (" is a flow at Nash equilibrium"). The identity holds edge by edge for every flow, so the formal statement drops the equilibrium hypothesis (and the sign conditions on and the incidence); it is the stronger identity and implies the page's statement.
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(b) (p. 15): with linear latencies, the marginal cost `ℓ*_P(f/2)` of every route
with respect to `f/2` equals its latency `ℓ_P(f)` with respect to `f`. Stated for every flow
`f` (the page's equilibrium hypothesis is not needed). -/
theorem lemma_4_3_b {J R : ℕ} (A : Fin J → Fin R → ℝ) (a b : Fin J → ℝ)
(x : Fin R → ℝ) (r : Fin R) :
SelfishRouting.Bicriteria.pathLatency A (marginalLatency a b) (fun r => x r / 2) r =
SelfishRouting.Bicriteria.pathLatency A (linLatency a b) x r := 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(b)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.