Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2, p. 13 — every coarse correlated equilibrium σ of a game with robust POA ρ(G) satisfies E_{s∼σ}[C(s)] ≤ ρ(G)·C(s*)

Proved
RobustPoA.Static.theorem_3_2

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

coarse-correlated-equilibriumextension-theoremp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysmooth-games

Theorem 3.2 (Extension Theorem — Static Version). Let GGG be a cost-minimization game with players iii, player costs CiC_iCi​, nonnegative joint cost C(s)=∑iCi(s)≥0C(s) = \sum_i C_i(s) \ge 0C(s)=∑i​Ci​(s)≥0, and robust price of anarchy

ρ(G)=inf⁡{λ1−μ:μ<1, G is (λ,μ)-smooth},\rho(G) = \inf\left\{ \tfrac{\lambda}{1-\mu} : \mu < 1,\ G \text{ is } (\lambda,\mu)\text{-smooth} \right\},ρ(G)=inf{1−μλ​:μ<1, G is (λ,μ)-smooth},

and suppose GGG is (λ,μ)(\lambda,\mu)(λ,μ)-smooth for at least one pair with μ<1\mu < 1μ<1. Then for every coarse correlated equilibrium σ\sigmaσ of GGG and every outcome s∗s^*s∗ of GGG,

Es∼σ[C(s)]≤ρ(G)⋅C(s∗).\mathbf{E}_{s\sim\sigma}[C(s)] \le \rho(G) \cdot C(s^*).Es∼σ​[C(s)]≤ρ(G)⋅C(s∗).

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 C(s∗)C(s^*)C(s∗) would reverse the passage to the infimum. Individual costs CiC_iCi​ may be negative. (2) Some smoothness pair with μ<1\mu < 1μ<1 exists, i.e. ρ(G)<+∞\rho(G) < +\inftyρ(G)<+∞: on the page the statement is vacuous when ρ(G)=+∞\rho(G) = +\inftyρ(G)=+∞. In Lean ρ(G)\rho(G)ρ(G) is an extended-real infimum (EReal), equal to +∞+\infty+∞ on the empty set, and the expected cost is compared in EReal; since EReal sets (+∞)⋅0=0(+\infty)\cdot 0 = 0(+∞)⋅0=0, the case ρ(G)=+∞\rho(G) = +\inftyρ(G)=+∞, C(s∗)=0C(s^*) = 0C(s∗)=0 would otherwise claim E[C]≤0\mathbf{E}[C] \le 0E[C]≤0. Distributions are finitely supported probability weights on outcomes, so distributions with infinite support are not covered.

Preamble
import Mathlib
import Definitions.Def_RobustPoA_Static_Game
import Definitions.Def_RobustPoA_Static_Smoothness
import Definitions.Def_RobustPoA_Static_Distribution
Formal statement
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
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), Theorem 3.2, p. 13
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me