Theorem (Robinson 1951) — for every vector system, min U(t)/t → v and max V(t)/t → v
ProvedRobinsonFP.Convergence.robinson_theoremLet be a real matrix with , the pay-off matrix of a finite two-person zero-sum game, and let be its value, given by a solution of the game. If is a vector system for (Definition 1), then
This is the convergence of Brown's iterative method (fictitious play) for zero-sum matrix games: when each player in turn plays a best pure reply to the accumulated play of the opponent, the lower and upper estimates of the value obtained from the accumulated payoffs both converge to the value of the game. The statement holds for arbitrary initial vectors with and for every tie-breaking rule.
Formalization Note Rows and columns are indexed by finite nonempty types. The value enters through IsSolution A x y v (probability vectors , with ), as defined on p. 296; a solution exists for every matrix by the minimax theorem (proved on Prove2Me as MatousekLP.ZeroSum.minimax_equality, in another encoding), so the hypothesis is satisfiable. The two limits are stated as Tendsto … atTop (𝓝 v) along . The paper's closing display on p. 301 prints ; the intended reading, confirmed by the statement of the Theorem on p. 297 and the lim sup display just above it, is , which is what is stated here.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_RobinsonFP_Convergence_VectorSystem open Filter Topology
namespace RobinsonFP.Convergence
variable {ι κ : Type*} [Fintype ι] [Fintype κ]
/-- Robinson (1951), p. 297, Theorem: if `(U, V)` is a vector system for `A`, then
`lim_{t→∞} min U(t)/t = lim_{t→∞} max V(t)/t = v`, the value of the game. -/
theorem robinson_theorem [Nonempty ι] [Nonempty κ] (A : Matrix ι κ ℝ)
(U : ℕ → κ → ℝ) (V : ℕ → ι → ℝ) (hUV : IsVectorSystem A U V)
(x : ι → ℝ) (y : κ → ℝ) (v : ℝ) (hsol : IsSolution A x y v) :
Tendsto (fun t : ℕ => vmin (U t) / t) atTop (𝓝 v) ∧
Tendsto (fun t : ℕ => vmax (V t) / t) atTop (𝓝 v) := by sorry
end RobinsonFP.Convergence
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.