THEOREM 1 — Blackwell's sufficient condition for approachability
ProvedVectorPayoffs.Convex.theorem1approachabilityp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1repeated-gamesvector-payoffs
Let be closed. Suppose that for every there is such that, for a point closest to , the hyperplane through perpendicular to the segment separates from :
Then is approachable with every strategy of I satisfying
being arbitrary if or .
This is the paper's sufficient condition for approachability; together with the minimax theorem it yields the characterization of approachable convex sets (THEOREM 3).
Formalization Note "The closest point" is read as some closest point (for non-convex it need not be unique) and "separates" as weak separation (closed half-space). The map is not assumed measurable; the conclusion is about every (measurable) strategy that agrees with off .
Preamble
import Mathlib import Definitions.Def_VectorPayoffs_Convex_Game open MeasureTheory
Formal statement
namespace VectorPayoffs.Convex
/-- Blackwell (1956), §2, p. 3, THEOREM 1: if every `x ∉ S` admits `p(x) ∈ P` such that the
hyperplane through a closest point `y ∈ S` perpendicular to `xy` separates `x` from `R(p(x))`,
then `S` is approachable with any strategy playing `p(x̄ₙ)` whenever `n > 0` and `x̄ₙ ∉ S`. -/
theorem theorem1 {N r s : ℕ} (G : Game N r s) (S : Set (E N)) (hS : IsClosed S)
(p : E N → Fin r → ℝ)
(hsep : ∀ x ∉ S, p x ∈ stdSimplex ℝ (Fin r) ∧ G.BlackwellCondition S (p x) x)
(f : Strategy N r)
(hf : ∀ n, 1 ≤ n → ∀ h : Fin n → E N, avgHist h ∉ S → f.toFun n h = p (avgHist h)) :
G.ApproachableWith S f := by sorry
end VectorPayoffs.Convex
Source
Blackwell, An analog of the minimax theorem for vector payoffs, Pacific J. Math. 6(1), 1956, p. 3, THEOREM 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.