AFTD Auto-Formalizing Theoretical Domains

MatrixGame.common_guarantee_eq_value

theoremverifiedformalizationimported Lean

Common guarantee gives the value. If both players guarantee the same scalar w, then w equals the game 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.common_guarantee_eq_value (w : ℝ)
    (h1 : A.IsPlayerIGuarantee w) (h2 : A.IsPlayerIIGuarantee w) :
    w = A.value
Formalizes
EconCSLib, `MatrixGame.common_guarantee_eq_value`
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 19
  • MatrixGame.minimax_theoremVon Neumann's Minimax Theorem: For any finite matrix game, maximin = minimax. [MSZ 5.11, von Neumann 1928] Proof: the general…
  • 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.IsPlayerIGuaranteew is a guarantee for player I when some mixed row strategy achieves expected payoff ≥ w against every pure column. Equivalent to…
  • MatrixGame.IsPlayerIIGuaranteew is a guarantee for player II when some mixed column strategy caps expected payoff ≤ w against every pure row. Equivalent to…
  • MatrixGame.valueThe value of a matrix game (sSup-based; needs order completeness). Equal to both maximin and minimax by the minimax theorem…
  • 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.
  • MatrixGame.guarantee_IPlayer I's guaranteed payoff using mixed strategy x: the minimum expected payoff over all of Player II's pure responses. A finite…
  • 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.maximinThe maximin value: the best guarantee Player I can achieve. maximin = sup_x inf_j E(x, j)
  • MinimaxLoomis.lam.auxPlayer I's guaranteed payoff from mixed strategy x: the minimum over pure columns of the expected payoff.
  • MinimaxLoomis.lam.aux.bddAbovelam.aux A is uniformly bounded above on the simplex.
  • 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.
  • MatrixGame.value_eq_maximinMatrixGame.value_eq_maximin
  • wsum_pure_applyWeighted sum at a point mass evaluates the chosen coordinate.
  • Loomis.lamB.aux.bddAbovelamB.aux A B is bounded above on the simplex (continuous function on a compact set).
  • Loomis.muB.aux.bddBelowmuB.aux A B is bounded below on the simplex.

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/-- **Common guarantee gives the value.** If both players guarantee the same scalar `w`, then `w` equals the game value. -/theorem MatrixGame.common_guarantee_eq_value (w : ℝ)    (h1 : A.IsPlayerIGuarantee w) (h2 : A.IsPlayerIIGuarantee w) :    w = A.value := by  obtain ⟨xx, hxx⟩ := h1  obtain ⟨yy, hyy⟩ := h2  have hw_le_GI : w ≤ A.guarantee_I xx := by    show w ≤ Finset.inf' Finset.univ Finset.univ_nonempty (fun j => A.Ej xx j)    rw [Finset.le_inf'_iff]; intro j _; exact hxx j  have hGII_le_w : A.guarantee_II yy ≤ w := by    show Finset.sup' Finset.univ Finset.univ_nonempty (fun i => A.Ei i yy) ≤ w    rw [Finset.sup'_le_iff]; intro i _; exact hyy i  have h_GI_max : A.guarantee_I xx ≤ A.maximin :=    le_ciSup (bddAbove_def.2 (by      obtain ⟨C, hC⟩ := MinimaxLoomis.lam.aux.bddAbove A.g      exact ⟨C, by rintro r ⟨z, rfl⟩; exact hC z⟩)) xx  have h_min_GII : 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  have hvm := A.minimax_theorem  have hvval := A.value_eq_maximin  linarith
See it in the graphDiscuss this resultChallenge it