§2.1, p. 7 — edge form of the cost:
ProvedSelfishRouting.Bicriteria.cost_eq_sum_edgesnetwork-flowsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let be an edge–route incidence matrix, any family of functions , and any vector of route flows, with edge flows . Then the cost can be computed edge by edge:
The paper uses both forms of the cost throughout; in particular the proof of Theorem 3.1 moves between them.
Formalization Note. The identity is pure algebra and holds for any real matrix , any functions and any real ; no hypothesis is assumed.
Preamble
import Mathlib import Definitions.Def_KellyStochasticNetworks_Wardrop import Definitions.Def_SelfishRouting_Bicriteria_Model
Formal statement
namespace SelfishRouting.Bicriteria
open KellyStochasticNetworks
/-- §2.1 (p. 7): the edge form of the cost, `C(f) = ∑ₑ ℓₑ(fₑ) fₑ`. -/
theorem cost_eq_sum_edges {J R : ℕ} (A : Fin J → Fin R → ℝ) (ℓ : Fin J → ℝ → ℝ)
(x : Fin R → ℝ) :
cost A ℓ x = ∑ j, ℓ j (linkFlow A x j) * linkFlow A x j := 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. 7, §2.1 (unnumbered display after the definition of C(f))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.