Relation (25), p. 14 — time-averaged smoothness bound
ProvedRobustPoA.Repeated.relation_25p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1price-of-anarchyrepeated-playsmooth-games
In a -smooth cost-minimization game with , let be any outcome sequence and let be a comparison outcome. For every integer ,
This is the average-cost inequality before any no-regret condition is imposed.
Formalization Note The comparison outcome is arbitrary; the paper's preceding setup calls it minimum-cost, but minimality is not used in this relation.
Preamble
import Mathlib import Definitions.Def_RobustPoA_Static_Smoothness import Definitions.Def_RobustPoA_Repeated_Regret
Formal statement
namespace RobustPoA.Repeated
/-- Relation (25), the time average of relation (23). -/
theorem relation_25 {ι : Type*} [Fintype ι] [DecidableEq ι] {S : ι → Type*}
(C : ι → (∀ i, S i) → ℝ) (lam mu : ℝ)
(hsm : RobustPoA.Static.IsSmooth C lam mu) (hmu : mu < 1)
(seq : ℕ → ∀ i, S i) (s' : ∀ i, S i) (T : ℕ) (hT : 1 ≤ T) :
(1 / (T : ℝ)) * ∑ t ∈ Finset.Icc 1 T, RobustPoA.Static.cost C (seq t) ≤
lam / (1 - mu) * RobustPoA.Static.cost C s' +
(1 / (1 - mu)) *
∑ i, ((1 / (T : ℝ)) *
∑ t ∈ Finset.Icc 1 T, delta C s' (seq t) i) := by sorry
end RobustPoA.Repeated
Source
Roughgarden, Intrinsic Robustness of the Price of Anarchy, J. ACM 62(5) (2015), (25), §3.2, p. 14
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.