Lemma 1 — lim inf (max V(t) − min U(t))/t ≥ 0
ProvedRobinsonFP.Convergence.lemma1fictitious-playgame-theorymatrix-gamep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix with and let be a vector system for (Definition 1). Then
The gap is, after division by , the difference between the upper and lower estimates of the value produced by the iteration; Lemma 1 says it cannot become negative at a linear rate. Together with Lemma 4 it shows that the gap is .
Formalization Note The lim inf is stated in -form: for every there is with for all integers . This is equivalent to the extended-real lim inf being and needs no boundedness assumption. At Lean's division gives ; this does not affect an eventual statement.
Preamble
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem open Filter Topology
Formal statement
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 297, Lemma 1: `lim inf_{t→∞} (max V(t) − min U(t))/t ≥ 0`, stated in
ε-form: for every `ε > 0`, eventually `(max V(t) − min U(t))/t ≥ −ε`. -/
theorem lemma1 [Nonempty ι] [Nonempty κ] (A : Matrix ι κ ℝ)
(U : ℕ → κ → ℝ) (V : ℕ → ι → ℝ) (hUV : IsVectorSystem A U V) :
∀ ε : ℝ, 0 < ε → ∀ᶠ t : ℕ in atTop, -ε ≤ (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. 297, Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.