First equality of (22), supp. p. 10 — total expected cost equals the sum of player cost-vector inner products
ProvedRegLearnGames.FirstOrder.social_cost_eq_sum_inneralgorithmic-game-theoryexpected-costp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1smooth-games
Let be mixed profiles in a finite cost game. With the vector of player 's expected cost for each pure strategy against the other players' mixed play,
This identity converts social cost into the quantities controlled by individual regret bounds.
Formalization Note The expectation uses the product distribution of the players' lotteries. The identity holds for any finite horizon, including , when both sums are empty.
Preamble
import Mathlib import Definitions.Def_RegLearnGames_FirstOrder_Setting
Formal statement
namespace RegLearnGames.FirstOrder
open Finset
/-- The first equality in display (22), for the complete time horizon. -/
theorem social_cost_eq_sum_inner {n d : ℕ}
(c : Fin n → (Fin n → Fin d) → ℝ)
(w : ℕ → Fin n → Fin d → ℝ) (T : ℕ)
(hw : ∀ t ∈ Finset.Icc 1 T, AGT.IsMixedProfile (w t)) :
(∑ t ∈ Finset.Icc 1 T, socialCost c (w t)) =
∑ t ∈ Finset.Icc 1 T, ∑ i, (w t i) ⬝ᵥ (costVec c (w t) i) := by sorry
end RegLearnGames.FirstOrder
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, supp. p. 10 (PDF p. 19), first equality of display (22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.