minimax_approx_theorem
Approximate minimax theorem for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$, having at least two row actions and at least one column action, and suppose every entry satisfies $0 \le A_{ij} \le 1$. Then for every $\varepsilon > 0$ there exist a mixed row strategy $p$ and a mixed column strategy $q$ such that, for every pure row $i$ and every pure column $j$, \[ \sum_{k} p_k \, A_{kj} + \varepsilon \;\ge\; \sum_{\ell} A_{i\ell} \, q_\ell. \] That is, the row player's guaranteed payoff under $p$ against any column falls short of the column player's exposure under $q$ against any row by at most $\varepsilon$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in theorem minimax_approx_theorem {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N) (hM : 1 < M) : ∀ ε : ℝ, 0 < ε → ∃ (p : MixedStrategy M) (q : MixedStrategy N), ∀ (i : Fin M) (j : Fin N), payoffVsPure G p j + ε ≥ pureVsPayoff G i q
- Formalizes
- Approximate minimax theorem for finite zero-sum games, as formalized in TCSlib (`minimax_approx_theorem`)
- Lean proof
- By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.minimax_approx_theorem← minimax_approx_theorem (TCSlib/LearningTheory/Minimax/FiniteMinimax.lean:324): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
- MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
- ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
- payoffVsPureGiven a game $G$, a mixed row strategy $p$, and a pure column $j$, the expected payoff against column $j$ is…
- approx_minimaxApproximate minimax for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$, having $M \ge 2$ row…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The ε-approximate minimax theorem, quantified over all `ε`: for any game `G` with at least two row actions and every `ε > 0`, there exist mixed strategies `p`, `q` with `payoffVsPure G p j + ε ≥ pureVsPayoff G i q` for all pure `i`, `j`. This is `approx_minimax` with `ε` universally quantified. [CBL06, Thm 7.1 (finite case)]; [FS99, §5]. -/theorem minimax_approx_theorem {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N) (hM : 1 < M) : ∀ ε : ℝ, 0 < ε → ∃ (p : MixedStrategy M) (q : MixedStrategy N), ∀ (i : Fin M) (j : Fin N), payoffVsPure G p j + ε ≥ pureVsPayoff G i q := by intro ε hε exact approx_minimax G hM ε hε