§2.1, p. 5 — the cost of a flow is the edge sum C(f) = Σₑ ℓₑ(fₑ)fₑ
ProvedPoAIndep.Topology.cost_eq_sum_edgesflow-costp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
Let be an instance and let be a flow, that is, a nonnegative assignment of flow to simple source–sink paths of each commodity. The cost of is defined as the total latency , summed over all commodities and paths. Summing over the edges of each path and reversing the order of summation gives the edge form
The edge form is how the cost enters every later argument of the paper: Lemmas 3.5 and 3.7 and Theorem 3.8 all compare flows edge by edge.
Formalization Note. Neither feasibility nor any property of the latency functions is needed. The identity uses that a simple path contains each edge at most once.
Preamble
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
Formal statement
namespace PoAIndep.Topology
theorem cost_eq_sum_edges {V E : Type} [Fintype V] [DecidableEq V] [Fintype E]
[DecidableEq E] (I : Instance V E) (f : Flow I) (hf : IsFlow I f) :
cost I f = ∑ e, I.ℓ e (edgeFlow I f e) * edgeFlow I f e := by sorry
end PoAIndep.Topology
Source
Roughgarden, The price of anarchy is independent of the network topology (journal-version manuscript, Dec. 23, 2002), p. 5, §2.1, third paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.