Relation (23), p. 13 — one-step smoothness bound with deviation improvements
ProvedRobustPoA.Repeated.relation_23p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchyrepeated-playsmooth-games
Let be a -smooth cost-minimization game with . For any played outcome and comparison outcome , define . Then
This one-step inequality is the input to the time-averaged bound in relation (25).
Formalization Note The paper introduces as a minimum-cost outcome when defining , but the derivation applies to every comparison outcome, as does Theorem 3.3.
Preamble
import Mathlib import Definitions.Def_RobustPoA_Static_Smoothness import Definitions.Def_RobustPoA_Repeated_Regret
Formal statement
namespace RobustPoA.Repeated
/-- Relation (23), allowing any comparison outcome as in the proof of Theorem 3.3. -/
theorem relation_23 {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*}
(C : ι → (∀ i, S i) → ℝ) (lam mu : ℝ)
(hsm : RobustPoA.Static.IsSmooth C lam mu) (hmu : mu < 1) (s s' : ∀ i, S i) :
RobustPoA.Static.cost C s ≤ lam / (1 - mu) * RobustPoA.Static.cost C s' +
(∑ i, delta C s' s i) / (1 - mu) := by sorry
end RobustPoA.Repeated
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), (23), §3.2, p. 13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.