(3), proof of Lemma 4 — if some row or column is not eligible in (s, s+t*), the gap grows by less than ½εt*
ProvedRobinsonFP.Convergence.eq3Let be a real matrix with , let , and let be a nonnegative integer with the following property: for every submatrix obtained from by deleting one row or one column (and still having at least one row and one column), every vector system for satisfies
Let be a vector system for and a nonnegative integer. If some row or some column of is not eligible in the interval , then
This is the induction step of the proof of Lemma 4: over a window in which some pure strategy is never a best reply, the vector system behaves like one for a smaller matrix, so the gap grows by less than .
Formalization Note The paper chooses for all submatrices of ; we assume the bound only for the submatrices obtained by deleting a single row or a single column, the ones its argument uses, so our statement is at least as strong. The paper writes out the row case only ("Suppose, for example, that the -th row is not eligible", p. 300); the statement covers both cases, as (3) does. Deleting row gives the rows indexed by , and the bound is assumed only when this index set is nonempty, because needs at least one component; an ineligible row forces another row to exist, so nothing is lost.
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 299, display (3) in the proof of Lemma 4: let `t*` be such that every
vector system `(U', V')` of a submatrix `A'` obtained by deleting one row or one column of `A`
satisfies `max V'(t) − min U'(t) < ½εt` for `t ≥ t*`. If some row or some column of `A` is not
eligible in `(s, s + t*)` for the vector system `(U, V)`, then
`max V(s+t*) − min U(s+t*) < max V(s) − min U(s) + ½εt*`. -/
theorem eq3 [DecidableEq ι] [DecidableEq κ] [Nonempty ι] [Nonempty κ] (A : Matrix ι κ ℝ)
(ε : ℝ) (hε : 0 < ε) (tstar : ℕ)
(hrowIH : ∀ k : ι, ∀ (_ : Nonempty {i // i ≠ k}) (U' : ℕ → κ → ℝ)
(V' : ℕ → {i // i ≠ k} → ℝ),
IsVectorSystem (A.submatrix Subtype.val id) U' V' →
∀ t : ℕ, tstar ≤ t → vmax (V' t) - vmin (U' t) < ε / 2 * t)
(hcolIH : ∀ k : κ, ∀ (_ : Nonempty {j // j ≠ k}) (U' : ℕ → {j // j ≠ k} → ℝ)
(V' : ℕ → ι → ℝ),
IsVectorSystem (A.submatrix id Subtype.val) U' V' →
∀ t : ℕ, tstar ≤ t → vmax (V' t) - vmin (U' t) < ε / 2 * t)
(U : ℕ → κ → ℝ) (V : ℕ → ι → ℝ) (hUV : IsVectorSystem A U V) (s : ℕ)
(hnot : (∃ i, ¬ RowEligible V i s (s + tstar)) ∨ (∃ j, ¬ ColEligible U j s (s + tstar))) :
vmax (V (s + tstar)) - vmin (U (s + tstar)) <
vmax (V s) - vmin (U s) + ε / 2 * tstar := by sorry
end RobinsonFP.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.