Proof of the Theorem, p. 301 — lim sup min U(t)/t ≤ v and lim inf max V(t)/t ≥ v
ProvedRobinsonFP.Convergence.limsup_liminf_valuefictitious-playgame-theorymatrix-gamep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix with , let be a solution of the game with value , and let be a vector system for . Then
The lower estimate cannot exceed the value and the upper estimate cannot fall below it, asymptotically; with the previous step this pins both limits at .
Formalization Note Both are stated together in -form: for every , for all sufficiently large , and . The value is tied to a solution through IsSolution A x y v, exactly as the paper defines it on p. 296; such a solution exists for every matrix by the minimax theorem (proved on Prove2Me as MatousekLP.ZeroSum.minimax_equality, in another encoding).
Preamble
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem open Filter Topology
Formal statement
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 301, proof of the Theorem: `lim sup_{t→∞} min U(t)/t ≤ v` and
`lim inf_{t→∞} max V(t)/t ≥ v`, where `v` is the value of the game, stated in ε-form. -/
theorem limsup_liminf_value [Nonempty ι] [Nonempty κ] (A : Matrix ι κ ℝ)
(U : ℕ → κ → ℝ) (V : ℕ → ι → ℝ) (hUV : IsVectorSystem A U V)
(x : ι → ℝ) (y : κ → ℝ) (v : ℝ) (hsol : IsSolution A x y v) :
∀ ε : ℝ, 0 < ε → ∀ᶠ t : ℕ in atTop,
vmin (U t) / t ≤ v + ε ∧ v - ε ≤ vmax (V t) / t := by sorry
end RobinsonFP.Convergence
Source
Robinson, An Iterative Method of Solving a Game, Ann. of Math. 54(2) (1951), p. 301, proof of the Theorem (second display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.