Proposition 2.3, p. 6 — the cost of a feasible Nash flow is Σᵢ Lᵢ(f) rᵢ
ProvedPoAIndep.Topology.proposition_2_3nash-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1selfish-routing
The page notes after Proposition 2.2: "if is at Nash equilibrium then all - flow paths (- paths to which assigns a positive amount of flow) have equal latency, say ."
Let be a flow at Nash equilibrium that is feasible for the instance . Then there are numbers such that every path with has latency , and
This expresses the cost of a Nash flow through the common latencies of its commodities; it is the first step in the proof of Lemma 3.7.
Formalization Note. The common latencies , defined in the sentence before the proposition, are carried as an existential witness.
Preamble
import Mathlib import Definitions.Def_PoAIndep_Topology_Model
Formal statement
namespace PoAIndep.Topology
theorem proposition_2_3 {V E : Type} [Fintype V] [DecidableEq V] [Fintype E]
[DecidableEq E] (I : Instance V E) (f : Flow I) (hf : IsFlow I f) (hfeas : IsFeasible I f)
(hnash : IsNashFlow I f) :
∃ Lc : Fin I.k → ℝ, (∀ i P, 0 < f i P → pathLatency I f P = Lc i) ∧
cost I f = ∑ i, Lc i * I.r i := by sorry
end PoAIndep.Topology
Source
Roughgarden, The price of anarchy is independent of the network topology (journal-version manuscript, Dec. 23, 2002), p. 6, Proposition 2.3 (and the sentence defining L_i(f) before it)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.