MatrixGame.optimalRowSet_nonempty
theoremverifiedformalizationimported Lean
MatrixGame.optimalRowSet_nonempty
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open MatrixGame in open Finset BigOperators Set 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.optimalRowSet_nonempty : A.optimalRowSet.Nonempty
- Formalizes
- EconCSLib, `MatrixGame.optimalRowSet_nonempty`
- 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.optimalRowSet_nonempty← MatrixGame.optimalRowSet_nonempty (EconCSLib/GameTheory/StrategicGame/ZeroSum/OptimalStrategySetPolytope.lean:138): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 24
- MatrixGame.minimax_optimal_strategiesExistence of optimal mixed strategies: there exist mixed strategies
xxfor Player I andyyfor Player II and a valuevsuch that: -… - 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.optimalRowSetH-representation of the row-optimal strategy set in the ambient space
I → ℝ: the standard simplex intersected with the finitely many… - MatrixGame.EjExpected payoff when Player I uses
xagainst pure columnj. - MatrixGame.EiExpected payoff when pure row
ifaces Player II's mixed strategyy. - MatrixGame.valueThe value of a matrix game (
sSup-based; needs order completeness). Equal to both maximin and minimax by the minimax theorem… - MatrixGame.maximinThe maximin value: the best guarantee Player I can achieve.
maximin = sup_x inf_j E(x, j) - 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… - 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) - 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. - 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.maximin_le_minimaxMaximin ≤ minimax (always holds, for any matrix game). This is the finite weak-duality inequality.
- MatrixGame.value_eq_maximinMatrixGame.value_eq_maximin
- wsum_pure_applyWeighted sum at a point mass evaluates the chosen coordinate.
- MatrixGame.toMixedProfile_zeroMatrixGame.toMixedProfile_zero
- MatrixGame.toMixedProfile_oneMatrixGame.toMixedProfile_one
- MatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGameMatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGame
- MatrixGame.instFintypeStrategyFinOfNatNatToStrategicGameMatrixGame.instFintypeStrategyFinOfNatNatToStrategicGame
- MatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGameMatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGame
- 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.
- MatrixGame.minimax_optimal_strategiesExistence of optimal mixed strategies: there exist mixed strategies
- Used by 1
- MatrixGame.optimalRowStrategies_image_isPolytopeThe row-optimal strategy set is a nonempty polytope: convex, closed, compact, and nonempty.
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 Set 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 ℝ) intheorem MatrixGame.optimalRowSet_nonempty : A.optimalRowSet.Nonempty := by obtain ⟨xx, yy, v, Hxx, Hyy⟩ := A.minimax_optimal_strategies refine ⟨xx.val, xx.property, ?_⟩ rw [mem_iInter] intro j -- We need: A.value ≤ ∑ i, xx.val i * A.g i j = A.Ej xx j. have hv : v = A.value := by have h_le : v ≤ A.maximin := by have hxx_guarantee : v ≤ A.guarantee_I xx := by show v ≤ Finset.inf' Finset.univ Finset.univ_nonempty (fun j => A.Ej xx j) rw [Finset.le_inf'_iff]; intro j _; exact Hxx j have hg_le : 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 linarith have h_ge_min : A.minimax ≤ v := by have hyy_guarantee : A.guarantee_II yy ≤ v := by show Finset.sup' Finset.univ Finset.univ_nonempty (fun i => A.Ei i yy) ≤ v rw [Finset.sup'_le_iff]; intro i _; exact Hyy i have hg_ge : A.minimax ≤ A.guarantee_II yy := by have hbb : BddBelow (Set.range (A.guarantee_II)) := by obtain ⟨C, hC⟩ := MinimaxLoomis.mu.aux.bddBelow A.g exact ⟨C, by rintro r ⟨z, rfl⟩; exact hC z⟩ exact ciInf_le hbb yy linarith have hmm : A.maximin ≤ A.minimax := A.maximin_le_minimax have : v = A.maximin := by linarith rw [this, ← A.value_eq_maximin] show A.value ≤ ∑ i, xx.val i * A.g i j have h1 : A.value ≤ A.Ej xx j := by rw [← hv]; exact Hxx j exact h1