Proposition 5.2, p. 24 — γ(C) bounds each game’s robust price of anarchy
ProvedRobustPoA.Tight.proposition_5_2congestion-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysmooth-games
Let be a nonempty set of admissible resource cost functions, and let be any congestion game whose resource costs lie in . Then
where is the best smoothness ratio for that game and is the best ratio from the resourcewise constraints (35). This makes a uniform robust price-of-anarchy bound for the class.
Formalization Note Both values are extended nonnegative reals. The class requires a nonempty strategy set for each player.
Preamble
import Definitions.Def_RobustPoA_Tight_Classes
Formal statement
namespace RobustPoA.Tight
open scoped ENNReal
open CongestionPoA.AsymSum
/-- Proposition 5.2, p. 24: the robust price of anarchy of any game in the class
is bounded by the resourcewise best smoothness ratio. -/
theorem proposition_5_2 (C : Set (ℕ → ℝ)) (hne : C.Nonempty)
(hC : ∀ c ∈ C, IsCostFn c) {k m : ℕ}
(G : CongestionGame (Fin k) (Fin m)) (hG : InClass C G) :
robustPoACG G ≤ gamma C := by sorry
end RobustPoA.Tight
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), Proposition 5.2, p. 24
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.