Theorem 4.1, p. 16 — every ε-coarse correlated equilibrium of a (λ, µ)-smooth game with ε < 1/µ − 1 has E[C(s)] ≤ (1 + ε)λ/(1 − µ(1 + ε))·C(s*)
ProvedRobustPoA.Static.theorem_4_1Theorem 4.1 (Extension Theorem for Approximate Equilibria). Let be a -smooth cost-minimization game with players , player costs and joint cost . Let with . Then for every -coarse correlated equilibrium of and every outcome of ,
The theorem shows that smoothness bounds degrade gracefully with the approximation parameter; at it is the fixed-pair form of Theorem 3.2.
Formalization Note The paper's condition "" is encoded as : the two agree for , the printed form is meaningless at (in Lean would make it , a vacuous hypothesis) and reverses for . The condition is the paper's implicit domain of an approximation parameter. The -coarse correlated equilibrium is the extension of (15) that §4.1 describes as defined "in the same way" as (26). Distributions are finitely supported.
import Mathlib import Definitions.Def_RobustPoA_Static_Game import Definitions.Def_RobustPoA_Static_Smoothness import Definitions.Def_RobustPoA_Static_Distribution
namespace RobustPoA.Static
theorem theorem_4_1 {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*}
(C : ι → (∀ i, S i) → ℝ) (lam mu ε : ℝ)
(hsmooth : IsSmooth C lam mu) (hε : 0 ≤ ε) (hεmu : mu * (1 + ε) < 1)
(σ : (∀ i, S i) →₀ ℝ) (hσ : IsEpsCCE C ε σ) (sstar : ∀ i, S i) :
expect σ (cost C) ≤ (1 + ε) * lam / (1 - mu * (1 + ε)) * cost C sstar := by sorry
end RobustPoA.Static
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.