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.SkewSymmetric.optimal← SkewSymmetric.optimal (EconCSLib/Math/Minimax/SkewSymmetric.lean:50): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- EconCSLib.LinearAlgebra.HasCertificateExistence of a Farkas certificate.
- SkewSymmetric.RowRow index of the feasibility system
z S β₯ 0, z β₯ 0, β z = 1:inl l= the column constraint(zS)_l β₯ 0;inr (inl k)=z_k β₯ 0;β¦ - SkewSymmetric.matSkewSymmetric.mat
- EconCSLib.LinearAlgebra.IsFeasiblePrimal feasibility of the system
A x β₯ b. - EconCSLib.LinearAlgebra.rowEval_defEconCSLib.LinearAlgebra.rowEval_def
- EconCSLib.LinearAlgebra.rowEvalEvaluate the LHS of row
iof the matrixA : I β Fin n β πat the pointx : Fin n β π. - EconCSLib.LinearAlgebra.IsCertificate
u : I β πis a Farkas certificate of infeasibility ofA x β₯ b. - EconCSLib.LinearAlgebra.theorem_of_alternativeTheorem of the Alternative [MFoGT, Section 2.8, Exercise 7]: for a finite system of weak linear inequalities
A x β₯ bover a linearlyβ¦ - SkewSymmetric.rhsSkewSymmetric.rhs
- Used by 1
- Minimax.skew_optimal
SkewSymmetric.optimaltransported to an arbitrary nonempty finite index.
- Minimax.skew_optimal
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 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