Minimax.minimax
theoremverifiedformalizationimported Lean
Ordered-field von Neumann minimax. Every finite two-player zero-sum game over a linearly ordered field has a value and optimal mixed strategies.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators in variable {π : Type*} [Field π] [LinearOrder π] [IsStrictOrderedRing π] in variable {I J : Type*} [Fintype I] [Fintype J] [DecidableEq I] [DecidableEq J] [Nonempty I] [Nonempty J] in theorem Minimax.minimax (A : I β J β π) : β (x : I β π) (y : J β π) (v : π), (β i, 0 β€ x i) β§ (β i, x i = 1) β§ (β j, 0 β€ y j) β§ (β j, y j = 1) β§ (β j, v β€ β i, x i * A i j) β§ (β i, β j, A i j * y j β€ v)
- Formalizes
- EconCSLib, `Minimax.minimax`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.Minimax.minimax← Minimax.minimax (EconCSLib/Math/Minimax/Minimax.lean:170): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Minimax.minimax_posMinimax for a strictly positive game.
- Used by 2
- MatrixGame.exists_mixed_nash_equilibriumMatrix games have a mixed Nash equilibrium β over any linearly ordered field. Packages the field-generic saddle
Minimax.minimaxβ¦ - MatrixGame.minimax_theoremVon Neumann's Minimax Theorem: For any finite matrix game, maximin = minimax. [MSZ 5.11, von Neumann 1928] Proof: the generalβ¦
- MatrixGame.exists_mixed_nash_equilibriumMatrix games have a mixed Nash equilibrium β over any linearly ordered field. Packages the field-generic saddle
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 autoImplicit true inset_option relaxedAutoImplicit true inopen Finset BigOperators invariable {π : Type*} [Field π] [LinearOrder π] [IsStrictOrderedRing π] invariable {I J : Type*} [Fintype I] [Fintype J] [DecidableEq I] [DecidableEq J] [Nonempty I] [Nonempty J] in/-- **Ordered-field von Neumann minimax.** Every finite two-player zero-sum game over a linearly ordered field has a value and optimal mixed strategies. -/theorem Minimax.minimax (A : I β J β π) : β (x : I β π) (y : J β π) (v : π), (β i, 0 β€ x i) β§ (β i, x i = 1) β§ (β j, 0 β€ y j) β§ (β j, y j = 1) β§ (β j, v β€ β i, x i * A i j) β§ (β i, β j, A i j * y j β€ v) := by classical obtain β¨i0β© := βΉNonempty IβΊ; obtain β¨j0β© := βΉNonempty JβΊ set c : π := 1 - Finset.inf' Finset.univ β¨(i0, j0), Finset.mem_univ _β© (fun r : I Γ J => A r.1 r.2) with hc have hApos : β i j, 0 < A i j + c := by intro i j have hle : Finset.inf' Finset.univ β¨(i0, j0), Finset.mem_univ _β© (fun r : I Γ J => A r.1 r.2) β€ A i j := Finset.inf'_le _ (Finset.mem_univ (i, j)) rw [hc]; linarith obtain β¨x, y, v, hxnn, hxsum, hynn, hysum, hxA, hAyβ© := minimax_pos (fun i j => A i j + c) hApos refine β¨x, y, v - c, hxnn, hxsum, hynn, hysum, ?_, ?_β© Β· intro j have h := hxA j rw [show (β i, x i * (A i j + c)) = (β i, x i * A i j) + c from by rw [show (β i, x i * (A i j + c)) = β i, (x i * A i j + x i * c) from Finset.sum_congr rfl (fun i _ => by ring), Finset.sum_add_distrib, β Finset.sum_mul, hxsum, one_mul]] at h linarith Β· intro i have h := hAy i rw [show (β j, (A i j + c) * y j) = (β j, A i j * y j) + c from by rw [show (β j, (A i j + c) * y j) = β j, (A i j * y j + c * y j) from Finset.sum_congr rfl (fun j _ => by ring), Finset.sum_add_distrib, β Finset.mul_sum, hysum, mul_one]] at h linarith