Theorem 5.8, p. 30, equation (34), p. 23 — congestion games form a tight class
ProvedRobustPoA.Tight.theorem_5_8Fix any nonempty set of nonnegative, nondecreasing resource cost functions, with the irrelevant all-zero function excluded. Let be the class of all finite congestion games whose resource costs lie in . The class is tight:
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 : an empty smoothness-parameter set has infimum , 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.
import Definitions.Def_RobustPoA_Tight_Classes
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.