AFTD Auto-Formalizing Theoretical Domains

SkewSymmetric.optimal

theoremverifiedformalizationimported Lean

Skew-symmetric optimal strategy. Every skew-symmetric game has a value-0 optimal mixed strategy.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open EconCSLib.LinearAlgebra in
open Finset BigOperators in
variable {π•œ : Type*} [Field π•œ] [LinearOrder π•œ] [IsStrictOrderedRing π•œ] in
variable {N : β„•} in
theorem SkewSymmetric.optimal [NeZero N] (S : Fin N β†’ Fin N β†’ π•œ) (hS : βˆ€ k l, S k l = - S l k) :
    βˆƒ z : Fin N β†’ π•œ, (βˆ€ k, 0 ≀ z k) ∧ (βˆ‘ k, z k = 1) ∧ (βˆ€ l, 0 ≀ βˆ‘ k, z k * S k l)
Formalizes
EconCSLib, `SkewSymmetric.optimal`
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 9
Used by 1

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen EconCSLib.LinearAlgebra inopen Finset BigOperators invariable {π•œ : Type*} [Field π•œ] [LinearOrder π•œ] [IsStrictOrderedRing π•œ] invariable {N : β„•} in/-- **Skew-symmetric optimal strategy.** Every skew-symmetric game has a value-0 optimal mixed strategy. -/theorem SkewSymmetric.optimal [NeZero N] (S : Fin N β†’ Fin N β†’ π•œ) (hS : βˆ€ k l, S k l = - S l k) :    βˆƒ z : Fin N β†’ π•œ, (βˆ€ k, 0 ≀ z k) ∧ (βˆ‘ k, z k = 1) ∧ (βˆ€ l, 0 ≀ βˆ‘ k, z k * S k l) := by  classical  -- Feasibility of the system, via the Theorem of the Alternative.  have hfeas : IsFeasible (mat S) (rhs (N := N)) := by    by_contra hno    obtain ⟨u, hu_nn, hu_col, hu_pos⟩ :=      (theorem_of_alternative (mat S) (rhs (N := N))).mp hno    -- Block abbreviations.    set w : Fin N β†’ π•œ := fun l => u (Sum.inl l) with hw    have hw_nn : βˆ€ l, 0 ≀ w l := fun l => hu_nn _    have hv_nn : βˆ€ k, 0 ≀ u (Sum.inr (Sum.inl k)) := fun k => hu_nn _    set a0 : π•œ := u (Sum.inr (Sum.inr false)) with ha0    set a1 : π•œ := u (Sum.inr (Sum.inr true)) with ha1    -- ⟨u, b⟩ = a0 - a1 > 0.    have hΞ΄ : 0 < a0 - a1 := by      have h := hu_pos      rw [Fintype.sum_sum_type, Fintype.sum_sum_type, Fintype.sum_bool] at h      simp only [rhs, mul_zero, Finset.sum_const_zero, zero_add, mul_one,        mul_neg, mul_one] at h      linarith    -- Column-`j` condition collapses to `(S w)_j + u(inr inl j) + (a0 - a1) = 0`.    have hcol : βˆ€ j, (βˆ‘ l, S j l * w l) + u (Sum.inr (Sum.inl j)) + (a0 - a1) = 0 := by      intro j      have h := hu_col j      rw [Fintype.sum_sum_type, Fintype.sum_sum_type, Fintype.sum_bool] at h      simp only [mat, mul_ite, mul_one, mul_zero, Finset.sum_ite_eq, Finset.mem_univ,        if_true, mul_neg, hw] at h      -- h : (βˆ‘ l, u (inl l) * S j l) + (u (inr (inl j)) + (a0 + -a1)) = 0      have e : (βˆ‘ l, u (Sum.inl l) * S j l) = βˆ‘ l, S j l * w l := by        refine Finset.sum_congr rfl (fun l _ => ?_); rw [hw]; ring      rw [e] at h; linarith    -- The certificate vector `w` is the bad alternative `S w < 0`.    have hSw : βˆ€ j, (βˆ‘ l, S j l * w l) ≀ -(a0 - a1) := by      intro j; have := hcol j; have := hv_nn j; linarith    -- `w β‰  0`: otherwise `(S w)_j = 0`, contradicting `≀ -(a0-a1) < 0`.    have hw_pos : 0 < βˆ‘ l, w l := by      rcases (Finset.sum_nonneg (fun l _ => hw_nn l)).lt_or_eq with h | h      Β· exact h      Β· exfalso        have hall : βˆ€ l, w l = 0 := fun l =>          (Finset.sum_eq_zero_iff_of_nonneg (fun l _ => hw_nn l)).mp h.symm l (Finset.mem_univ l)        have hj : (βˆ‘ l, S ((0 : Fin N)) l * w l) = 0 := by          apply Finset.sum_eq_zero; intro l _; rw [hall l, mul_zero]        have := hSw (0 : Fin N); rw [hj] at this; linarith    -- Antisymmetry: `wα΅€ S w = 0`.    have hQ0 : (βˆ‘ j, βˆ‘ l, w j * S j l * w l) = 0 := by      have hswap : (βˆ‘ j, βˆ‘ l, w j * S j l * w l)          = βˆ‘ j, βˆ‘ l, w l * S l j * w j := Finset.sum_comm      have hneg : (βˆ‘ j, βˆ‘ l, w l * S l j * w j)          = - βˆ‘ j, βˆ‘ l, w j * S j l * w l := by        rw [← Finset.sum_neg_distrib]        refine Finset.sum_congr rfl (fun j _ => ?_)        rw [← Finset.sum_neg_distrib]        refine Finset.sum_congr rfl (fun l _ => ?_)        rw [hS l j]; ring      have : (βˆ‘ j, βˆ‘ l, w j * S j l * w l)          = - βˆ‘ j, βˆ‘ l, w j * S j l * w l := hswap.trans hneg      linarith    -- But `wα΅€ S w = βˆ‘β±Ό wβ±Ό (Sw)β±Ό ≀ -(a0-a1) Β· βˆ‘w < 0`.    have hQeq : (βˆ‘ j, w j * (βˆ‘ l, S j l * w l)) = βˆ‘ j, βˆ‘ l, w j * S j l * w l := by      refine Finset.sum_congr rfl (fun j _ => ?_)      rw [Finset.mul_sum]; refine Finset.sum_congr rfl (fun l _ => ?_); ring    have hle : (βˆ‘ j, w j * (βˆ‘ l, S j l * w l)) ≀ βˆ‘ j, w j * (-(a0 - a1)) := by      apply Finset.sum_le_sum; intro j _      exact mul_le_mul_of_nonneg_left (hSw j) (hw_nn j)    rw [hQeq, hQ0] at hle    have hrhs : (βˆ‘ j, w j * (-(a0 - a1))) = -(a0 - a1) * βˆ‘ j, w j := by      rw [← Finset.sum_mul]; ring    rw [hrhs] at hle    have : -(a0 - a1) * (βˆ‘ j, w j) < 0 :=      mul_neg_of_neg_of_pos (by linarith) hw_pos    linarith  -- Extract `z` from a feasible point.  obtain ⟨z, hz⟩ := hfeas  refine ⟨z, ?_, ?_, ?_⟩  Β· intro k    have h := hz (Sum.inr (Sum.inl k))    simp only [rhs, rowEval, mat, ite_mul, one_mul, zero_mul,      Finset.sum_ite_eq', Finset.mem_univ, if_true] at h    exact h  Β· have h0 := hz (Sum.inr (Sum.inr false))    have h1 := hz (Sum.inr (Sum.inr true))    simp only [rhs, rowEval, mat, one_mul, neg_one_mul, Finset.sum_neg_distrib] at h0 h1    linarith  Β· intro l    have h := hz (Sum.inl l)    simp only [rhs, rowEval, mat] at h    rw [show (βˆ‘ k, z k * S k l) = βˆ‘ j, S j l * z j from      Finset.sum_congr rfl (fun j _ => by ring)]    exact h
See it in the graphDiscuss this resultChallenge it