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.MatrixGame.common_guarantee_eq_value← MatrixGame.common_guarantee_eq_value (EconCSLib/GameTheory/StrategicGame/ZeroSum/MatrixGameNash.lean:318): verbatim
- 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 columnj : J. Payoff to Player I isg i j… - MatrixGame.IsPlayerIGuarantee
wis a guarantee for player I when some mixed row strategy achieves expected payoff≥ wagainst every pure column. Equivalent to… - MatrixGame.IsPlayerIIGuarantee
wis a guarantee for player II when some mixed column strategy caps expected payoff≤ wagainst 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
xagainst pure columnj. - MatrixGame.EiExpected payoff when pure row
ifaces Player II's mixed strategyy. - 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.bddAbove
lam.aux Ais 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.bddBelow
mu.aux Ais 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.bddAbove
lamB.aux A Bis bounded above on the simplex (continuous function on a compact set). - Loomis.muB.aux.bddBelow
muB.aux A Bis bounded below on the simplex.
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 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