Theorem 3.2, p. 13 — every coarse correlated equilibrium σ of a game with robust POA ρ(G) satisfies E_{s∼σ}[C(s)] ≤ ρ(G)·C(s*)
ProvedRobustPoA.Static.theorem_3_2Theorem 3.2 (Extension Theorem — Static Version). Let be a cost-minimization game with players , player costs , nonnegative joint cost , and robust price of anarchy
and suppose is -smooth for at least one pair with . Then for every coarse correlated equilibrium of and every outcome of ,
Every price-of-anarchy bound proved by a smoothness argument therefore holds automatically for coarse correlated equilibria, and hence for mixed Nash and correlated equilibria as well as pure ones.
Formalization Note Two hypotheses are made explicit. (1) The joint cost is nonnegative: this is the paper's standing assumption of a nonnegative objective function (§1, p. 2; §2.4, p. 10); without it a negative would reverse the passage to the infimum. Individual costs may be negative. (2) Some smoothness pair with exists, i.e. : on the page the statement is vacuous when . In Lean is an extended-real infimum (EReal), equal to on the empty set, and the expected cost is compared in EReal; since EReal sets , the case , would otherwise claim . Distributions are finitely supported probability weights on outcomes, so distributions with infinite support are not covered.
import Mathlib import Definitions.Def_RobustPoA_Static_Game import Definitions.Def_RobustPoA_Static_Smoothness import Definitions.Def_RobustPoA_Static_Distribution
namespace RobustPoA.Static
theorem theorem_3_2 {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*}
(C : ι → (∀ i, S i) → ℝ)
(hC : ∀ s, 0 ≤ cost C s)
(hsmooth : ∃ lam mu : ℝ, mu < 1 ∧ IsSmooth C lam mu)
(σ : (∀ i, S i) →₀ ℝ) (hσ : IsCCE C σ) (sstar : ∀ i, S i) :
expect σ (cost C) ≤ robustPoA C * cost C sstar := by sorry
end RobustPoA.Static
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.