Blackwell's Theorem 1 with approximate separation
ProvedVectorPayoffs.Convex.approachable_of_slackWork in the setting of Blackwell's repeated game with vector payoffs: is an matrix of probability distributions on a closed bounded convex set , with means , and for a mixed action of player I
Let , let , and let be a strategy of player I. Write for the average of a history . Suppose that for every and every history with there is a point closest to such that
Then is approachable with : for every there is such that for every strategy of II and every play of the two strategies,
For this is the sufficient condition of Blackwell's THEOREM 1 (where plays and the hyperplane through perpendicular to separates from ). The proof of THEOREM 1 uses the hyperplane condition only through the cross term in the recursion for , which is multiplied by a factor of order , so an error of order is absorbed in the constant of the recursion. The relaxed form is what one needs to build a measurable strategy from a finite net of mixed actions.
Formalization Note The condition is required only for averages lying in (outcomes lie in almost surely, hence so do the averages). "A closest point" is read as some closest point ; the strategy is a measurable strategy in the sense of the definition file, and the quantification over plays is the one of ApproachableWith.
import Mathlib import Definitions.Def_VectorPayoffs_Convex_Game open MeasureTheory
namespace VectorPayoffs.Convex
/-- Blackwell (1956), §2, THEOREM 1 with approximate separation: if the hyperplane condition of
THEOREM 1 holds up to an error `κ / n` at stage `n`, the set `S` is still approachable with `f`. -/
theorem approachable_of_slack {N r s : ℕ} (G : Game N r s) (S : Set (E N)) (κ : ℝ) (hκ : 0 ≤ κ)
(f : Strategy N r)
(hslack : ∀ n, 1 ≤ n → ∀ h : Fin n → E N, avgHist h ∈ G.X → avgHist h ∉ S →
∃ y ∈ S, (∀ z ∈ S, dist (avgHist h) y ≤ dist (avgHist h) z) ∧
∀ w ∈ G.R (f.toFun n h), inner ℝ (avgHist h - y) (w - y) ≤ κ / n) :
G.ApproachableWith S f := by sorry
end VectorPayoffs.Convex