Minimax.minimax_pos
theoremverifiedformalizationimported Lean
Minimax for a strictly positive game.
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_pos (A : I β J β π) (hA : β i j, 0 < 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_pos`
- 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_pos← Minimax.minimax_pos (EconCSLib/Math/Minimax/Minimax.lean:74): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- Minimax.skew_optimal
SkewSymmetric.optimaltransported to an arbitrary nonempty finite index. - Minimax.sum_blocksSplit a sum over
I β J β Unitinto the three blocks. - Minimax.symMatThe skew-symmetric symmetrisation of a game
AonI β J β Unit. - Minimax.symMat_skewMinimax.symMat_skew
- Minimax.skew_optimal
- Used by 1
- Minimax.minimaxOrdered-field von Neumann minimax. Every finite two-player zero-sum game over a linearly ordered field has a value and optimal mixedβ¦
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/-- **Minimax for a strictly positive game.** -/theorem Minimax.minimax_pos (A : I β J β π) (hA : β i j, 0 < 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 β¨z, hz_nn, hz_sum, hz_colβ© := skew_optimal (symMat A) (symMat_skew A) set p : I β π := fun i => z (Sum.inl i) with hp set q : J β π := fun j => z (Sum.inr (Sum.inl j)) with hq set lam : π := z (Sum.inr (Sum.inr ())) with hlam have hpe : β i, z (Sum.inl i) = p i := fun _ => rfl have hqe : β j, z (Sum.inr (Sum.inl j)) = q j := fun _ => rfl have hle : z (Sum.inr (Sum.inr ())) = lam := rfl have hp_nn : β i, 0 β€ p i := fun i => hz_nn _ have hq_nn : β j, 0 β€ q j := fun j => hz_nn _ have hlam_nn : 0 β€ lam := hz_nn _ -- Column `inl i`: `(A q)_i β€ Ξ»`. have hcolI : β i, (β j, A i j * q j) β€ lam := by intro i have h := hz_col (Sum.inl i) rw [sum_blocks] at h simp only [symMat, hpe, hqe, hle, mul_zero, Finset.sum_const_zero, zero_add, mul_one] at h have hb : (β j, q j * -(A i j)) = -(β j, A i j * q j) := by rw [β Finset.sum_neg_distrib]; exact Finset.sum_congr rfl (fun j _ => by ring) rw [hb] at h; linarith -- Column `inr (inl j)`: `Ξ» β€ (p A)_j`. have hcolJ : β j, lam β€ β i, p i * A i j := by intro j have h := hz_col (Sum.inr (Sum.inl j)) rw [sum_blocks] at h simp only [symMat, hpe, hqe, hle, mul_zero, Finset.sum_const_zero, add_zero, mul_neg_one] at h linarith -- Column `inr (inr ())`: `β p β€ β q`. have hcolU : (β i, p i) β€ β j, q j := by have h := hz_col (Sum.inr (Sum.inr ())) rw [sum_blocks] at h simp only [symMat, hpe, hqe, hle, mul_one, mul_neg_one, mul_zero, add_zero] at h rw [Finset.sum_neg_distrib] at h; linarith -- `β p > 0`. have hsump_pos : 0 < β i, p i := by rcases (Finset.sum_nonneg (fun i _ => hp_nn i)).lt_or_eq with hlt | heq Β· exact hlt Β· exfalso have hp0 : β i, p i = 0 := fun i => (Finset.sum_eq_zero_iff_of_nonneg (fun i _ => hp_nn i)).mp heq.symm i (Finset.mem_univ i) obtain β¨jββ© := βΉNonempty JβΊ have hlam0 : lam β€ 0 := by have hz := hcolJ jβ rw [show (β i, p i * A i jβ) = 0 from Finset.sum_eq_zero (fun i _ => by rw [hp0 i, zero_mul])] at hz exact hz have hlam_eq0 : lam = 0 := le_antisymm hlam0 hlam_nn have hsumq1 : (β j, q j) = 1 := by have hs := hz_sum rw [sum_blocks z] at hs simp only [hpe, hqe, hle] at hs rw [show (β i, p i) = 0 from heq.symm, hlam_eq0] at hs; linarith obtain β¨iββ© := βΉNonempty IβΊ have hAq_pos : 0 < β j, A iβ j * q j := by obtain β¨jβ, -, hjββ© : β j β (Finset.univ : Finset J), 0 < q j := by by_contra hc; push_neg at hc exact one_ne_zero (hsumq1.symm.trans (Finset.sum_eq_zero (fun j hj => le_antisymm (hc j hj) (hq_nn j)))) exact Finset.sum_pos' (fun j _ => mul_nonneg (hA iβ j).le (hq_nn j)) β¨jβ, Finset.mem_univ jβ, mul_pos (hA iβ jβ) hjββ© have := hcolI iβ; linarith -- `β q > 0`. have hsumq_pos : 0 < β j, q j := lt_of_lt_of_le hsump_pos hcolU -- Normalise: `x = p / βp`, `y = q / βq`, value `Ξ» / βp`. refine β¨fun i => p i / (β i, p i), fun j => q j / (β j, q j), lam / (β i, p i), fun i => div_nonneg (hp_nn i) hsump_pos.le, ?_, fun j => div_nonneg (hq_nn j) hsumq_pos.le, ?_, ?_, ?_β© Β· simp only [div_eq_mul_inv]; rw [β Finset.sum_mul] exact mul_inv_cancelβ hsump_pos.ne' Β· simp only [div_eq_mul_inv]; rw [β Finset.sum_mul] exact mul_inv_cancelβ hsumq_pos.ne' Β· intro j have hkey : (β i, p i / (β i, p i) * A i j) = (β i, p i * A i j) / (β i, p i) := by simp only [div_eq_mul_inv]; rw [Finset.sum_mul] exact Finset.sum_congr rfl (fun i _ => by ring) rw [hkey] exact (div_le_div_iffβ hsump_pos hsump_pos).mpr (mul_le_mul_of_nonneg_right (hcolJ j) hsump_pos.le) Β· intro i have hkey : (β j, A i j * (q j / (β j, q j))) = (β j, A i j * q j) / (β j, q j) := by simp only [div_eq_mul_inv]; rw [Finset.sum_mul] exact Finset.sum_congr rfl (fun j _ => by ring) rw [hkey] refine (div_le_div_iffβ hsumq_pos hsump_pos).mpr ?_ calc (β j, A i j * q j) * (β i, p i) β€ lam * (β i, p i) := mul_le_mul_of_nonneg_right (hcolI i) hsump_pos.le _ β€ lam * (β j, q j) := mul_le_mul_of_nonneg_left hcolU hlam_nn