AFTD Auto-Formalizing Theoretical Domains

minimax_approx_theorem

theoremverifiedformalizationimported Lean

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.
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

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ε
See it in the graphDiscuss this resultChallenge it