AFTD Auto-Formalizing Theoretical Domains

MatrixGame.minimax_optimal_strategies

theoremverifiedformalizationimported Lean

Existence of optimal mixed strategies: there exist mixed strategies xx for Player I and yy for Player II and a value v such that: - Player I guarantees at least v: ∀ j, E(xx, j) ≥ v - Player II limits payoff to at most v: ∀ i, E(i, yy) ≤ v [MSZ Theorem 5.11, LRS Theorem 2.3.1]

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open MatrixGame in
open Finset BigOperators Matrix in
variable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] in
variable (A : MatrixGame I J ℝ) in
theorem MatrixGame.minimax_optimal_strategies :
    ∃ (xx : stdSimplex ℝ I) (yy : stdSimplex ℝ J) (v : ℝ),
      (∀ j : J, A.Ej xx j ≥ v) ∧
      (∀ i : I, A.Ei i yy ≤ v)
Formalizes
EconCSLib, `MatrixGame.minimax_optimal_strategies`
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 10
  • Loomis.minmax_from_generalSimplified Loomis as a corollary of the general theorem: the finite von Neumann minimax MinimaxLoomis.lam0 A = MinimaxLoomis.mu0 A…
  • 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.EjExpected payoff when Player I uses x against pure column j.
  • MatrixGame.EiExpected payoff when pure row i faces Player II's mixed strategy y.
  • MinimaxLoomis.lam0Player I's maxmin value (the row player's best guarantee).
  • wsumWeighted sum of f with weights from a simplex element x. Thin abbrev over Mathlib's finite dot product ⬝ᵥ: definitionally equal,…
  • MinimaxLoomis.exists_xx_lam0There exists a mixed strategy xx whose column-payoffs all dominate lam0 A. Compactness + continuity gives a maximiser of lam.aux;…
  • MinimaxLoomis.mu0Player II's minmax value (the column player's best cap).
  • MinimaxLoomis.exists_yy_mu0There exists a mixed strategy yy whose row-payoffs are all dominated by mu0 A.
  • wsum_pure_applyWeighted sum at a point mass evaluates the chosen coordinate.
Used by 2

Lean source view module on GitHub

set_option autoImplicit true inset_option relaxedAutoImplicit true inopen MatrixGame inopen Finset BigOperators Matrix invariable {I J : Type*} [Fintype I] [Fintype J] [Nonempty I] [Nonempty J] invariable (A : MatrixGame I J ℝ) in/-- Existence of optimal mixed strategies: there exist mixed strategies `xx` for Player I and `yy` for Player II and a value `v` such that: - Player I guarantees at least `v`: `∀ j, E(xx, j) ≥ v` - Player II limits payoff to at most `v`: `∀ i, E(i, yy) ≤ v` [MSZ Theorem 5.11, LRS Theorem 2.3.1] -/theorem MatrixGame.minimax_optimal_strategies :    ∃ (xx : stdSimplex ℝ I) (yy : stdSimplex ℝ J) (v : ℝ),      (∀ j : J, A.Ej xx j ≥ v) ∧      (∀ i : I, A.Ei i yy ≤ v) := by  obtain ⟨xx, Hxx⟩ := MinimaxLoomis.exists_xx_lam0 A.g  obtain ⟨yy, Hyy⟩ := MinimaxLoomis.exists_yy_mu0 A.g  refine ⟨xx, yy, MinimaxLoomis.lam0 A.g, ?_, ?_⟩  · -- ∀ j, Ej xx j ≥ lam0 A.g    intro j    -- A.Ej xx j = wsum xx (fun i => A.g i j) by unfolding payoffAgainstColumn.    have : A.Ej xx j = wsum xx (fun i => A.g i j) := rfl    rw [this]; exact Hxx j  · -- ∀ i, Ei i yy ≤ lam0 A.g  (using lam0 = mu0)    intro i    have : A.Ei i yy = wsum yy (fun j => A.g i j) := rfl    rw [this, Loomis.minmax_from_general A.g]    exact Hyy i
See it in the graphDiscuss this resultChallenge it