Proof of Theorem 4.5, second display — for linear latencies
ProvedSelfishRouting.Linear.cost_half_flowlinear-latencyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let every edge have a linear latency with and let the route incidences be . For every flow with on every route,
In the proof of Theorem 4.5 this bounds the cost of the first stage, the optimal flow for the rates , from below by a quarter of the equilibrium cost.
Formalization Note Stated as , with no division. The page applies it to a Nash flow; equilibrium is not needed, only nonnegative route flows (so that the edge flows are nonnegative).
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
/-- Proof of Theorem 4.5, second display (p. 17): with linear latencies with `a_e, b_e ≥ 0`,
`C(f/2) ≥ ¼ C(f)` for every flow `f` with nonnegative route flows. -/
theorem cost_half_flow {J R : ℕ} (A : Fin J → Fin R → ℝ) (hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(a b : Fin J → ℝ) (ha : ∀ j, 0 ≤ a j) (hb : ∀ j, 0 ≤ b j)
(x : Fin R → ℝ) (hx : ∀ r, 0 ≤ x r) :
SelfishRouting.Bicriteria.cost A (linLatency a b) x ≤ 4 * SelfishRouting.Bicriteria.cost A (linLatency a b) (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. 17, proof of Theorem 4.5, second display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.