Proof of Theorem 3.1, first display, p. 13 —
ProvedSelfishRouting.Bicriteria.barCost_sub_cost_lenash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let be a edge–route incidence matrix and edge latency functions that are nonnegative on . Let and be two route flows with nonnegative entries, with edge flows and , and let be the modified latencies built from the edge flows of : for and for . Then
In words: evaluating with the latencies rather than increases its cost by at most . This is the upper half of the proof of Theorem 3.1.
Formalization Note. The statement needs neither equilibrium nor feasibility nor monotonicity of ; only nonnegative route flows, a incidence matrix and on are assumed, so it is slightly more general than the context on the page, where is a Nash flow and is feasible for .
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Bicriteria_Model import Definitions.Def_SelfishRouting_Bicriteria_BarLatency
Formal statement
namespace SelfishRouting.Bicriteria
open KellyStochasticNetworks
/-- Proof of Theorem 3.1, first display (p. 13):
`∑ₑ ℓ̄ₑ(f*ₑ) f*ₑ − C(f*) ≤ C(f)`, where `ℓ̄` is built from the edge flows of `f`. -/
theorem barCost_sub_cost_le {J R : ℕ} (A : Fin J → Fin R → ℝ) (ℓ : Fin J → ℝ → ℝ)
(hA : ∀ j r, A j r = 0 ∨ A j r = 1)
(hℓnn : ∀ j t, 0 ≤ t → 0 ≤ ℓ j t)
(x y : Fin R → ℝ) (hx : ∀ r, 0 ≤ x r) (hy : ∀ r, 0 ≤ y r) :
(∑ j, barLatency ℓ (linkFlow A x) j (linkFlow A y j) * linkFlow A y j) - cost A ℓ y
≤ cost A ℓ x := by sorry
end SelfishRouting.Bicriteria
Source
Roughgarden & Tardos, How Bad is Selfish Routing?, J. ACM 49(2) (2002), author's manuscript of 5 Dec 2001, p. 13, proof of Theorem 3.1, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.