Theorem 5, proof — weighted load-square bound
ProvedCongestionPoA.AsymMax.cauchy_stepcongestion-gameinequalityp2o-batch-pfp1ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchy
For any pure profile and any finite facility set in a game with nonnegative affine latencies ,
This is the coefficient-weighted form of the Cauchy–Schwarz step in the maximum-cost upper bound. Under identity latencies the coefficient sum is .
Preamble
import Definitions.Def_CongestionPoA_AsymMax_Model set_option autoImplicit false
Formal statement
namespace CongestionPoA.AsymMax
/-- Christodoulou and Koutsoupias, STOC 2005, Theorem 5, proof,
Cauchy–Schwarz step, PDF p. 4. Formalization Note: the paper's `|P₁|` is
the total coefficient weight for affine latencies; `Q` may be any set of
facilities, and the inequality holds for any profile. -/
theorem cauchy_step {ι 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 : ι → Finset E) (Q : Finset E) :
(∑ e ∈ Q, a e * (load A e : ℝ)) ^ 2 ≤
(∑ e ∈ Q, a e) * sumCost G A := 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, Cauchy–Schwarz step
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.