§3, proof of THEOREM A, p. 1137 — an invariant q_λ satisfies (3.3) as an equality: λ·v(q_λ, s⁻ⁱ) = 0
ProvedRegretMatching.Approach.blackwell_condition_negOrthantblackwell-approachabilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret-matching
Fix a player and let . Let (all coordinates nonnegative), and let satisfy (3.5) for the matrix with entries off the diagonal and on it:
Then for every the expected vector payoff is orthogonal to :
Here has -coordinate if and otherwise.
This is inequality (3.3) "as an equality", and hence Blackwell's condition (3.2) for the nonpositive orthant , whose support function is on .
Formalization Note. The conclusion is stated as the equality the paper asserts, not the weaker . is EuclideanSpace ℝ L and is its inner product. The profile s stands for ; its -th coordinate is ignored by .
Preamble
import Mathlib import Definitions.Def_RegretMatching_Approach_Setting open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RegretMatching.Approach
theorem blackwell_condition_negOrthant
{ι : Type} [Fintype ι] [DecidableEq ι]
{S : ι → Type} [∀ i, Fintype (S i)] [∀ i, DecidableEq (S i)] [∀ i, Nonempty (S i)]
(u : ι → (∀ i, S i) → ℝ) (i : ι)
(lam : EuclideanSpace ℝ (OffDiag (S i))) (hlam : ∀ l, 0 ≤ lam l)
(q : S i → ℝ) (hq : q ∈ stdSimplex ℝ (S i))
(h35 : ∀ j : S i, ∑ k : S i, q k * lamMat (fun l => lam l) k j
= q j * ∑ k : S i, lamMat (fun l => lam l) j k) :
∀ s : ∀ i, S i, inner ℝ lam (∑ a : S i, q a • vecPay u i a s) = 0 := 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) and (3.5), footnote 17
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.