Lemma 2 — if all rows and columns are eligible in (s, s+t), max U − min U ≤ 2at and max V − min V ≤ 2at
ProvedRobinsonFP.Convergence.lemma2fictitious-playgame-theorymatrix-gamep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix with , let be a number with for all , and let be a vector system for . Let be nonnegative integers. If every row and every column of is eligible in the interval (Definition 2), then
Once every row and column has been played during a window of length , the spread of each accumulated payoff vector is at most linear in , whatever the initial vectors were. Lemma 3 combines the two bounds.
Formalization Note The paper states the lemma with ; we state it for every upper bound on the . This contains the paper's statement (take ) and follows from it, since the right-hand side grows with .
Preamble
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem
Formal statement
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 298, Lemma 2: if every row and every column is eligible in `(s, s + t)`,
then `max U(s+t) − min U(s+t) ≤ 2at` and `max V(s+t) − min V(s+t) ≤ 2at`, for any `a` bounding
every `|a_ij|` (in particular `a = max_{i,j} |a_ij|`). -/
theorem lemma2 [Nonempty ι] [Nonempty κ] (A : Matrix ι κ ℝ) (a : ℝ) (ha : ∀ i j, |A i j| ≤ a)
(U : ℕ → κ → ℝ) (V : ℕ → ι → ℝ) (hUV : IsVectorSystem A U V) (s t : ℕ)
(hrow : ∀ i, RowEligible V i s (s + t)) (hcol : ∀ j, ColEligible U j s (s + t)) :
vmax (U (s + t)) - vmin (U (s + t)) ≤ 2 * a * t ∧
vmax (V (s + t)) - vmin (V (s + t)) ≤ 2 * a * t := by sorry
end RobinsonFP.Convergence
Source
Robinson, An Iterative Method of Solving a Game, Ann. of Math. 54(2) (1951), p. 298, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.