Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.8, p. 30, equation (34), p. 23 — congestion games form a tight class

Proved
RobustPoA.Tight.theorem_5_8

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

congestion-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysmooth-gamestightness

Fix any nonempty set C\mathcal CC of nonnegative, nondecreasing resource cost functions, with the irrelevant all-zero function excluded. Let G(C)\mathcal G(\mathcal C)G(C) be the class of all finite congestion games whose resource costs lie in C\mathcal CC. The class is tight:

sup⁡G∈G(C)ρpure(G)=inf⁡(λ,μ)∈A(G(C))λ1−μ.\sup_{G\in\mathcal G(\mathcal C)}\rho_{\mathrm{pure}}(G) =\inf_{(\lambda,\mu)\in\mathcal A(\mathcal G(\mathcal C))}\frac{\lambda}{1-\mu}.G∈G(C)sup​ρpure​(G)=(λ,μ)∈A(G(C))inf​1−μλ​.

Thus the best uniform smoothness bound for this game class is attained as a supremal pure-equilibrium inefficiency. Together with the paper's extension theorem, the same worst-case bound applies to broader equilibrium notions.

Formalization Note The supremum ranges over all natural numbers of players and resources. Only feasible profiles enter smoothness and the optimum. Both sides use [0,∞][0,\infty][0,∞]: an empty smoothness-parameter set has infimum +∞+\infty+∞, and a positive equilibrium cost with zero optimum gives infinite POA. Any pair admissible for the whole class has a nonnegative ratio, so the conversion from real to extended nonnegative values does not weaken the equality. The restriction on all-zero functions is the standing convention of §5.1.

Preamble
import Definitions.Def_RobustPoA_Tight_Classes
Formal statement
namespace RobustPoA.Tight

open scoped ENNReal

/-- Theorem 5.8, p. 30, stated as (34), p. 23: for every nonempty class of
nonnegative, nondecreasing, nonzero cost functions, the congestion-game class is tight. -/
theorem theorem_5_8 (C : Set (ℕ → ℝ)) (hne : C.Nonempty)
    (hC : ∀ c ∈ C, IsCostFn c) :
    worstPoA C =
      ⨅ p ∈ classParams C, ENNReal.ofReal (p.1 / (1 - p.2)) := by sorry

end RobustPoA.Tight
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), Theorem 5.8, p. 30; equation (34), p. 23
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