§3, proof of THEOREM A, p. 1137, (3.4a)–(3.4b) — the left side of (3.3) equals Σ_j α(j)uⁱ(j, s⁻ⁱ)
ProvedRegretMatching.Approach.eq_34blackwell-approachabilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret-matching
Fix a player , a vector on , a vector with , and a strategy profile (only matters). Let be the matrix with entries for and on the diagonal, and set
Then the left-hand side of (3.3) can be written as (3.4a):
This identity reduces Blackwell's condition for the nonpositive orthant to the invariance equations (3.5): if the left side vanishes for every .
Formalization Note. It is an algebraic identity: no hypothesis on or is needed. is u i (Function.update s i k), so the -th coordinate of s is ignored.
Preamble
import Mathlib import Definitions.Def_RegretMatching_Approach_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RegretMatching.Approach
theorem eq_34
{ι : Type} [Fintype ι] [DecidableEq ι]
{S : ι → Type} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)] [∀ i, Nonempty (S i)]
(u : ι → (∀ i, S i) → ℝ) (i : ι)
(q : S i → ℝ) (lam : OffDiag (S i) → ℝ) (s : ∀ i, S i) :
∑ l : OffDiag (S i), lam l * q l.1.1 *
(u i (Function.update s i l.1.2) - u i (Function.update s i l.1.1)) =
∑ j : S i, (∑ k : S i, q k * lamMat lam k j - q j * ∑ k : S i, lamMat lam j k) *
u i (Function.update s i j) := by sorry
end RegretMatching.Approach
Source
Hart and Mas-Colell, A simple adaptive procedure leading to correlated equilibrium, Econometrica 68 (2000), p. 1137, proof of THEOREM A, (3.3), (3.4a), (3.4b)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.