§4.1, p. 16 — every ε-Nash equilibrium of a (λ, µ)-smooth game with ε < 1/µ − 1 costs at most (1 + ε)λ/(1 − µ(1 + ε)) times optimal
ProvedRobustPoA.Static.eps_nash_boundapproximate-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchysmooth-games
Let be a -smooth cost-minimization game with players , player costs and joint cost . Let with , let be an -Nash equilibrium of , and let be an optimal outcome, i.e. for every outcome . Then
This is the approximate-equilibrium version of the pure Nash bound; Theorem 4.1 extends it to -coarse correlated equilibria.
Formalization Note The paper's condition "" is encoded as , which is what the derivation uses: the two agree for , while for the printed form is meaningless (and in Lean would make it ) and for it reverses. The condition is the paper's implicit domain of an approximation parameter. Optimality of is kept as printed, although the bound holds for every outcome .
Preamble
import Mathlib import Definitions.Def_RobustPoA_Static_Game import Definitions.Def_RobustPoA_Static_Smoothness
Formal statement
namespace RobustPoA.Static
theorem eps_nash_bound {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*}
(C : ι → (∀ i, S i) → ℝ) (lam mu ε : ℝ)
(hsmooth : IsSmooth C lam mu) (hε : 0 ≤ ε) (hεmu : mu * (1 + ε) < 1)
(s : ∀ i, S i) (hs : IsEpsNash C ε s)
(sstar : ∀ i, S i) (hopt : ∀ t : ∀ i, S i, cost C sstar ≤ cost C t) :
cost C s ≤ (1 + ε) * lam / (1 - mu * (1 + ε)) * cost C sstar := by sorry
end RobustPoA.Static
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), §4.1, first paragraph of p. 16 (with (26), p. 15)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.