Lemma 3 — if all rows and columns are eligible in (s, s+t), max V(s+t) − min U(s+t) ≤ 4at
ProvedRobinsonFP.Convergence.lemma3fictitious-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 , then
This bounds the gap between the two estimates of the value after a window in which every pure strategy has been a best reply. It is the case of the proof of Lemma 4 in which no row or column can be deleted.
Formalization Note The paper's is ; we state the lemma for every upper bound on the , which is equivalent (see Lemma 2). The hypothesis that is a vector system, including , is essential and kept.
Preamble
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem
Formal statement
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 299, Lemma 3: if every row and every column is eligible in `(s, s + t)`,
then `max V(s+t) − min U(s+t) ≤ 4at`, for any `a` bounding every `|a_ij|`. -/
theorem lemma3 [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 (V (s + t)) - vmin (U (s + t)) ≤ 4 * a * t := by sorry
end RobinsonFP.Convergence
Source
Robinson, An Iterative Method of Solving a Game, Ann. of Math. 54(2) (1951), p. 299, Lemma 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.