Theorem 4, p. 4 — RVU for every player with β ≤ γ/(n−1)² and ‖·‖ = ‖·‖₁ implies Σᵢ rᵢ(T) ≤ αn
ProvedRegLearnGames.TotalRegret.theorem_4Consider an -player game with strategies per player and utilities , played repeatedly: are mixed profiles and is player 's utility vector at time (so is computed from ). Let and with , and fix a horizon . Suppose each player's play satisfies the RVU inequality with these constants and : for every player and every ,
Then for every profile of comparators with each ,
that is, .
The sum of all players' regrets is therefore bounded by a constant independent of ; with Proposition 2 this makes the average welfare converge to within the price of anarchy of the optimum at rate .
Formalization Note The paper's condition is written , which agrees for and avoids division by zero at . The RVU inequality is assumed only on the realized play and for the given horizon, a weaker hypothesis than the paper's "on any sequence of utilities", so the statement is a disclosed strengthening. The bound on is stated for every comparator profile, which is equivalent to bounding the sum of suprema.
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
namespace RegLearnGames.TotalRegret
theorem theorem_4 {n d : ℕ} (u : Fin n → (Fin n → Fin d) → ℝ)
(hu : ∀ i s, u i s ∈ Set.Icc (0 : ℝ) 1)
(w : ℕ → Fin n → Fin d → ℝ) (hw : ∀ t i, w t i ∈ stdSimplex ℝ (Fin d))
(α β γ : ℝ) (hα : 0 < α) (hβ : 0 < β) (hβγ : β ≤ γ)
(hβγn : β * ((n : ℝ) - 1) ^ 2 ≤ γ) (T : ℕ)
(hRVU : ∀ i, ∀ v ∈ stdSimplex ℝ (Fin d),
∑ t ∈ Finset.Icc 1 T, (v - w t i) ⬝ᵥ utilVec u (w t) i ≤
α + β * ∑ t ∈ Finset.Icc 1 T, ‖utilVec u (w t) i - utilVec u (w (t - 1)) i‖ ^ 2
- γ * ∑ t ∈ Finset.Icc 1 T, l1 (w t i - w (t - 1) i) ^ 2)
(wstar : Fin n → Fin d → ℝ) (hwstar : ∀ i, wstar i ∈ stdSimplex ℝ (Fin d)) :
∑ i, ∑ t ∈ Finset.Icc 1 T, (wstar i - w t i) ⬝ᵥ utilVec u (w t) i ≤ α * n := by sorry
end RegLearnGames.TotalRegret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.