Lemma 4 — there is t₀, uniform over vector systems, with max V(t) − min U(t) < εt for t ≥ t₀
ProvedRobinsonFP.Convergence.lemma4fictitious-playgame-theorymatrix-gamep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix with and let . There is a nonnegative integer , depending only on and , such that every vector system for satisfies
The point is the uniformity: one serves every vector system, whatever its initial vectors and tie-breaking, which is what lets the proof proceed by induction over submatrices. With Lemma 1 it gives .
Formalization Note The order of quantifiers is , as in the paper. The matrix is fixed in the statement; a proof will typically generalize over the index types to run the induction over submatrices.
Preamble
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem
Formal statement
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 299, Lemma 4: for every matrix `A` and `ε > 0` there is `t₀`, depending
only on `A` and `ε`, such that every vector system `(U, V)` for `A` satisfies
`max V(t) − min U(t) < εt` for all `t ≥ t₀`. -/
theorem lemma4 [Nonempty ι] [Nonempty κ] (A : Matrix ι κ ℝ) (ε : ℝ) (hε : 0 < ε) :
∃ t₀ : ℕ, ∀ (U : ℕ → κ → ℝ) (V : ℕ → ι → ℝ), IsVectorSystem A U V →
∀ t : ℕ, t₀ ≤ t → vmax (V t) - vmin (U t) < ε * t := by sorry
end RobinsonFP.Convergence
Source
Robinson, An Iterative Method of Solving a Game, Ann. of Math. 54(2) (1951), p. 299, Lemma 4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.