Claim (3)–(5), §2.1, p. 5 — in a (λ, µ)-smooth game with λ > 0, µ < 1, every pure Nash equilibrium costs at most λ/(1 − µ) times optimal
ProvedRobustPoA.Static.claim_3_5nash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysmooth-games
Let be a cost-minimization game with players , player costs and joint cost . Suppose is -smooth with and , let be a pure Nash equilibrium of , and let be an optimal outcome, i.e. for every outcome . Then
This is the basic smoothness bound on the price of anarchy of pure Nash equilibria; the mission's extension theorems generalize it to coarse correlated and approximate equilibria.
Formalization Note The hypotheses and optimality of are kept exactly as the paper states the claim, although the inequality holds without them.
Preamble
import Mathlib import Definitions.Def_RobustPoA_Static_Game import Definitions.Def_RobustPoA_Static_Smoothness
Formal statement
namespace RobustPoA.Static
theorem claim_3_5 {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*}
(C : ι → (∀ i, S i) → ℝ) (lam mu : ℝ)
(hsmooth : IsSmooth C lam mu) (hlam : 0 < lam) (hmu : mu < 1)
(s : ∀ i, S i) (hs : IsPureNash C s)
(sstar : ∀ i, S i) (hopt : ∀ t : ∀ i, S i, cost C sstar ≤ cost C t) :
cost C s ≤ lam / (1 - mu) * cost C sstar := by sorry
end RobustPoA.Static
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), claim (3)–(5), §2.1, p. 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.