AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
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

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