AFTD Auto-Formalizing Theoretical Domains

MatrixGame.mem_optimalColumnStrategies_iff_E_le

theoremverifiedformalizationimported Lean

A column strategy is optimal iff against every mixed row it caps payoff at the value.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open MatrixGame in
open Finset BigOperators in
set_option linter.unusedSectionVars false in
universe u in
variable {I J : Type u} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in
variable (A : MatrixGame I J ℝ) in
theorem MatrixGame.mem_optimalColumnStrategies_iff_E_le (yy : stdSimplex ℝ J) :
    yy ∈ A.optimalColumnStrategies ↔ ∀ x' : stdSimplex ℝ I, A.E x' yy ≤ A.value
Formalizes
EconCSLib, `MatrixGame.mem_optimalColumnStrategies_iff_E_le`
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 16
  • MatrixGame.value_eq_minimaxMatrixGame.value_eq_minimax
  • MatrixGameA finite two-player zero-sum matrix game. Player I chooses row i : I, Player II chooses column j : J. Payoff to Player I is g i j…
  • MatrixGame.optimalColumnStrategiesThe set of optimal column strategies: mixed strategies that achieve the minimax value.
  • MatrixGame.EExpected payoff when Player I uses mixed strategy x and Player II uses y.
  • MatrixGame.valueThe value of a matrix game (sSup-based; needs order completeness). Equal to both maximin and minimax by the minimax theorem…
  • MatrixGame.guarantee_IIPlayer II's guaranteed loss using mixed strategy y: the maximum expected payoff (for Player I) over all of Player I's pure responses.
  • MatrixGame.EiExpected payoff when pure row i faces Player II's mixed strategy y.
  • wsumWeighted sum of f with weights from a simplex element x. Thin abbrev over Mathlib's finite dot product ⬝ᵥ: definitionally equal,…
  • le_iff_simplex_lef ≤ v pointwise iff every simplex weighted sum is ≤ v.
  • stdSimplex.purePoint-mass simplex element at i₀.
  • wsum_pure_applyWeighted sum at a point mass evaluates the chosen coordinate.
  • MatrixGame.minimaxThe minimax value: the best guarantee Player II can achieve. minimax = inf_y sup_i E(i, y)
  • MinimaxLoomis.mu.auxPlayer II's maximum loss against mixed strategy y: the maximum over pure rows of the expected payoff.
  • MinimaxLoomis.mu.aux.bddBelowmu.aux A is uniformly bounded below on the simplex.
  • stdSimplex.pure_applystdSimplex.pure_apply
  • Loomis.muB.aux.bddBelowmuB.aux A B is bounded below on the simplex.
Used by 4

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen MatrixGame inopen Finset BigOperators inset_option linter.unusedSectionVars false inuniverse u invariable {I J : Type u} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] invariable (A : MatrixGame I J ℝ) in/-- A column strategy is optimal iff against every mixed row it caps payoff at the value. -/theorem MatrixGame.mem_optimalColumnStrategies_iff_E_le (yy : stdSimplex ℝ J) :    yy ∈ A.optimalColumnStrategies ↔ ∀ x' : stdSimplex ℝ I, A.E x' yy ≤ A.value := by  classical  unfold optimalColumnStrategies  simp only [Set.mem_setOf_eq]  constructor  · intro hyy x'    have hi : ∀ i, A.Ei i yy ≤ A.value := by      intro i      have : A.Ei i yy ≤ A.guarantee_II yy :=        Finset.le_sup' (fun i => A.Ei i yy) (Finset.mem_univ i)      linarith [hyy]    have heq : A.E x' yy = wsum x' (fun i => A.Ei i yy) := rfl    rw [heq]    exact (le_iff_simplex_le.mp hi) x'  · intro h    have hi : ∀ i, A.Ei i yy ≤ A.value := by      intro i      have := h (stdSimplex.pure i)      have heq : A.E (stdSimplex.pure i) yy = A.Ei i yy := by        show wsum (stdSimplex.pure i) (fun i' => wsum yy (A.g i')) = wsum yy (A.g i)        rw [wsum_pure_apply]      rwa [heq] at this    have hle : A.guarantee_II yy ≤ A.value := by      show Finset.sup' Finset.univ Finset.univ_nonempty (fun i => A.Ei i yy) ≤ A.value      rw [Finset.sup'_le_iff]; intro i _; exact hi i    have hge : A.value ≤ A.guarantee_II yy := by      have hv := A.value_eq_minimax      have : A.minimax ≤ A.guarantee_II yy :=        ciInf_le (bddBelow_def.2 (by          obtain ⟨C, hC⟩ := MinimaxLoomis.mu.aux.bddBelow A.g          exact ⟨C, by rintro r ⟨z, rfl⟩; exact hC z⟩)) yy      linarith    linarith
See it in the graphDiscuss this resultChallenge it