Lemma 5.1, p. 23 — nonnegativity of μ
ProvedRobustPoA.Tight.lemma_5_1congestion-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysmooth-games
Let be a nonempty set of nonnegative, nondecreasing, strictly positive cost functions. For every ,
The lemma fixes the sign of the second smoothness parameter under strict positivity, as used when resourcewise bounds are summed across a game.
Formalization Note Admissibility includes nondecreasing costs at positive loads; the all-zero function is excluded by the standing convention of §5.1.
Preamble
import Definitions.Def_RobustPoA_Tight_Classes
Formal statement
namespace RobustPoA.Tight
/-- Lemma 5.1, p. 23: an admissible smoothness pair for nonempty, strictly positive
cost functions has nonnegative second coordinate. -/
theorem lemma_5_1 (C : Set (ℕ → ℝ)) (hne : C.Nonempty)
(hC : ∀ c ∈ C, IsCostFn c ∧ IsStrictlyPos c)
(p : ℝ × ℝ) (hp : p ∈ smoothParams C) : 0 ≤ p.2 := by sorry
end RobustPoA.Tight
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), Lemma 5.1, p. 23
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.