Theorem 1 — total-cost bound of 5/2
ProvedCongestionPoA.AsymMax.theorem1_sum_le_five_halvescongestion-gameinequalityp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
In any finite congestion game with nonnegative affine latencies, let be a pure Nash profile and any feasible profile. Then
The paper states this as a bound for average social cost; the same inequality holds for total cost because averaging divides both sides by the number of players. It supplies the total-cost estimate used in Theorem 5.
Formalization Note This local restatement uses this mission's game model. If mission I's version is published first, it may be replaced by a compatible reference after comparison of the definitions.
Preamble
import Definitions.Def_CongestionPoA_AsymMax_Model set_option autoImplicit false
Formal statement
namespace CongestionPoA.AsymMax
/-- Christodoulou and Koutsoupias, STOC 2005, Theorem 1, PDF p. 3;
invoked in Theorem 5's proof, PDF p. 4. Formalization Note: total cost is
`N` times the paper's average cost, and `P` is any feasible profile.
The affine nonnegative latency convention is from Sect. 2, PDF p. 2. -/
theorem theorem1_sum_le_five_halves {ι E : Type*} [Fintype ι] [DecidableEq ι]
[Fintype E] [DecidableEq E]
(G : CongestionGame ι E) (A P : ι → Finset E)
(hlin : IsLinear G) (hA : IsPureNash G A) (hP : IsProfile G P) :
sumCost G A ≤ (5 / 2 : ℝ) * sumCost G P := by sorry
end CongestionPoA.AsymMax
Source
Christodoulou and Koutsoupias, The Price of Anarchy of Finite Congestion Games, STOC 2005, DOI 10.1145/1060590.1060600, PDF p. 3, Theorem 1; invoked PDF p. 4, Theorem 5, proof
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.