Theorem 5, proof — square-root player-cost bound
ProvedCongestionPoA.AsymMax.combined_boundcongestion-gameinequalityp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
Let be a pure Nash profile and any feasible profile in a finite congestion game with , . For every player ,
This is the intermediate player-cost estimate used to obtain the maximum social-cost upper bound.
Formalization Note The paper prints for identity latencies; the coefficient sum is its affine-latency counterpart.
Preamble
import Definitions.Def_CongestionPoA_AsymMax_Model set_option autoImplicit false
Formal statement
namespace CongestionPoA.AsymMax
/-- Christodoulou and Koutsoupias, STOC 2005, Theorem 5, proof,
combined bound after inequality (1), PDF p. 4. Formalization Note: the
coefficient-weighted sum replaces `|P₁|` for affine latencies, and `i`
is an arbitrary player. -/
theorem combined_bound {ι E : Type*} [Fintype ι] [DecidableEq ι]
[Fintype E] [DecidableEq E]
(G : CongestionGame ι E) (a b : E → ℝ)
(ha : ∀ e, 0 ≤ a e) (hb : ∀ e, 0 ≤ b e)
(hlat : ∀ e n, G.latency e n = a e * n + b e)
(A P : ι → Finset E) (hA : IsPureNash G A) (hP : IsProfile G P)
(i : ι) :
cost G A i ≤ cost G P i +
Real.sqrt ((5 / 2 : ℝ) * (∑ e ∈ P i, a e) * 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. 4, Theorem 5, proof, combined bound
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.