AFTD Auto-Formalizing Theoretical Domains

OnlineLearning.finite_minimax_value

theoremverifiedformalizationimported Lean

Minimax theorem for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions, whose payoff matrix $A = (A_{ij})$ satisfies $0 \le A_{ij} \le 1$ for all $i,j$. Suppose $M > 1$ and $N \ge 1$. Then the lower and upper values of $G$ coincide: \[ \sup_{p \in \Delta_M}\; \inf_{j \in [N]}\; \sum_{i} p_i\, A_{ij} \;=\; \inf_{q \in \Delta_N}\; \sup_{i \in [M]}\; \sum_{j} A_{ij}\, q_j, \] where $\Delta_M$ and $\Delta_N$ denote the sets of mixed strategies (probability distributions) over the row and column actions respectively.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
theorem OnlineLearning.finite_minimax_value {M N : ℕ} [NeZero M] [NeZero N]
    (G : ZeroSumGame M N) (hM : 1 < M) :
    finiteLowerValue G = finiteUpperValue G
Formalizes
Minimax theorem for finite zero-sum games, as formalized in TCSlib (`OnlineLearning.finite_minimax_value`)
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 11
  • pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
  • OnlineLearning.finiteLowerValueFor a finite zero-sum game $G$ with $M$ row actions and $N$ column actions, the lower value is…
  • OnlineLearning.finiteLowerValue_bddAboveRow player's guaranteed payoffs are bounded above. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$ column…
  • OnlineLearning.finiteUpperValueThe upper value of $G$ is \[ v^+(G) \;=\; \inf_{q \in \Delta_N}\; \sup_{i \in [M]}\; \mathrm{pureVsPayoff}(G,i,q), \] where the…
  • ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
  • OnlineLearning.mixedStrategyNonemptyThe mixed-strategy space is nonempty whenever the underlying action set is nonempty.
  • OnlineLearning.pureVsPayoff_le_onePure row payoff against a mixed column is at most one. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column…
  • OnlineLearning.finiteUpperValue_bddBelowLower boundedness of the row-supremum values. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column…
  • payoffVsPureGiven a game $G$, a mixed row strategy $p$, and a pure column $j$, the expected payoff against column $j$ is…
  • OnlineLearning.finiteLowerValue_le_upperValueWeak duality for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M \geq 1$ row actions and $N \geq 1$ column…
  • 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 minimax theorem for finite zero-sum games (von Neumann): for a game `G` with at least two row actions, the lower value `sup_p inf_j payoff(p, j)` equals the upper value `inf_q sup_i payoff(i, q)`. [CBL06, Thm 7.1 (finite case)]; [FS99, §5 (proof of the minmax theorem), §6.1]. Deviation: the proof goes through the Hedge-based `approx_minimax`, so it carries the spurious hypothesis `1 < M` (at least two row actions), which the theorem itself does not need; the case `M = 1` is not covered here. **Proof sketch.** By `le_antisymm`. Step 1 (easy direction): the lower value is at most the upper value by `finiteLowerValue_le_upperValue` (weak duality). Step 2 (hard direction): it suffices to show `upper ≤ lower + ε` for every `ε > 0`. Fix `ε`; the ε-approximate saddle point `(p, q)` from `approx_minimax` gives (`hq_le`) `sup_i payoff(i, q) ≤ inf_j payoff(p, j) + ε`. Then `upper ≤ sup_i payoff(i, q)` since the upper value is an infimum over `q` (`h_upper_at_q`), and `inf_j payoff(p, j) ≤ lower` since the lower value is a supremum over `p` (`h_lower_at_p`); chain the three inequalities. -/theorem OnlineLearning.finite_minimax_value {M N : ℕ} [NeZero M] [NeZero N]    (G : ZeroSumGame M N) (hM : 1 < M) :    finiteLowerValue G = finiteUpperValue G := by  apply le_antisymm  -- Step 1: the easy direction is weak duality.  · exact finiteLowerValue_le_upperValue G  -- Step 2: the hard direction by ε-approximation.  · apply le_of_forall_pos_le_add    intro ε hε    -- The approximate minimax theorem gives strategies whose gap is at most    -- `ε`.  Since this works for every positive `ε`, the exact values are equal.    obtain ⟨p, q, hpq⟩ := approx_minimax G hM ε hε    -- `hq_le`: the saddle-point gap bounds the row supremum by the column infimum.    have hq_le :        (⨆ i : Fin M, pureVsPayoff G i q) ≤          (⨅ j : Fin N, payoffVsPure G p j) + ε := by      have hbdd : BddAbove (Set.range (fun i : Fin M => pureVsPayoff G i q)) :=        ⟨1, by rintro _ ⟨i, rfl⟩; exact pureVsPayoff_le_one G i q⟩      apply ciSup_le      intro i      have hle_inf :          pureVsPayoff G i q - ε ≤ ⨅ j : Fin N, payoffVsPure G p j := by        apply le_ciInf        intro j        linarith [hpq i j]      linarith    -- `h_upper_at_q`: the upper value is at most its value at `q`.    have h_upper_at_q :        finiteUpperValue G ≤ ⨆ i : Fin M, pureVsPayoff G i q := by      unfold finiteUpperValue      exact ciInf_le (finiteUpperValue_bddBelow G) q    -- `h_lower_at_p`: the lower value is at least its value at `p`.    have h_lower_at_p :        (⨅ j : Fin N, payoffVsPure G p j) ≤ finiteLowerValue G := by      unfold finiteLowerValue      exact le_ciSup (finiteLowerValue_bddAbove G) p    linarith
See it in the graphDiscuss this resultChallenge it