§3, proof of THEOREM A, p. 1137, (3.5) — a nonnegative zero-diagonal matrix has an invariant probability vector
ProvedRegretMatching.Approach.exists_invariant_vectorblackwell-approachabilityinvariant-vectorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-matrix
Let be a finite nonempty set and . Let have nonnegative coordinates, and let be the matrix with entries for and for . Then there is a probability vector which is invariant for in the sense of (3.5):
In the proof of Theorem A this supplies the mixed strategy that meets Blackwell's condition for the nonpositive orthant. Taking to be the vector of regrets it also shows that (3.1) has a solution in at every history, so the hypothesis of Theorem A can always be met.
Formalization Note. The statement is for an arbitrary finite nonempty set (in use ). Nonemptiness is needed for to be nonempty.
Preamble
import Mathlib import Definitions.Def_RegretMatching_Approach_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RegretMatching.Approach
theorem exists_invariant_vector
{A : Type} [Fintype A] [DecidableEq A] [Nonempty A]
(lam : OffDiag A → ℝ) (hlam : ∀ l, 0 ≤ lam l) :
∃ q ∈ stdSimplex ℝ A, ∀ j : A,
∑ k : A, q k * lamMat lam k j = q j * ∑ k : A, lamMat lam j k := 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.5); also p. 1133 ('such a vector always exists')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.