EconCSLib.StrategicGame.MatrixGame.disp_Ei_argmin_nonneg
theoremverifiedformalizationimported Lean
For any column-player strategy y, picking the index where y is minimal gives a non-negative row payoff under disp A.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Finset BigOperators in set_option linter.unusedSectionVars false in variable {I : Type} [Fintype I] [Nonempty I] [DecidableEq I] in theorem EconCSLib.StrategicGame.MatrixGame.disp_Ei_argmin_nonneg (A : I → I → ℝ) (hA : IsStochasticMatrix A) (y : stdSimplex ℝ I) : ∃ i, 0 ≤ (⟨disp A⟩ : MatrixGame I I ℝ).Ei i y
- Formalizes
- EconCSLib, `EconCSLib.StrategicGame.MatrixGame.disp_Ei_argmin_nonneg`
- 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.EconCSLib.StrategicGame.MatrixGame.disp_Ei_argmin_nonneg← EconCSLib.StrategicGame.MatrixGame.disp_Ei_argmin_nonneg (EconCSLib/GameTheory/StrategicGame/ZeroSum/StochasticMatrix.lean:127): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- EconCSLib.StrategicGame.IsStochasticMatrixA finite (row-)stochastic matrix: entries are non-negative and each row sums to
1. - MatrixGame.EiExpected payoff when pure row
ifaces Player II's mixed strategyy. - MatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGameMatrixGame.instDecidableEqStrategyFinOfNatNatToStrategicGame
- EconCSLib.StrategicGame.MatrixGame.dispThe displacement matrix
B i j := A i j − [i = j]of a stochastic matrixA. The corresponding matrix game has value0. - 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… - EconCSLib.StrategicGame.MatrixGame.disp_EiRow-side payoff under
disp A:Ei i y = (Ay)_i − y_i. - MatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGameMatrixGame.instNonemptyStrategyFinOfNatNatToStrategicGame
- MatrixGame.instFintypeStrategyFinOfNatNatToStrategicGameMatrixGame.instFintypeStrategyFinOfNatNatToStrategicGame
- EconCSLib.StrategicGame.IsStochasticMatrixA finite (row-)stochastic matrix: entries are non-negative and each row sums to
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 Finset BigOperators inset_option linter.unusedSectionVars false invariable {I : Type} [Fintype I] [Nonempty I] [DecidableEq I] in/-- For any column-player strategy `y`, picking the index where `y` is minimal gives a non-negative row payoff under `disp A`. -/theorem EconCSLib.StrategicGame.MatrixGame.disp_Ei_argmin_nonneg (A : I → I → ℝ) (hA : IsStochasticMatrix A) (y : stdSimplex ℝ I) : ∃ i, 0 ≤ (⟨disp A⟩ : MatrixGame I I ℝ).Ei i y := by -- Pick i₀ = argmin_j y.val j. obtain ⟨i₀, _, hi_min⟩ := Finset.exists_min_image Finset.univ y.val Finset.univ_nonempty -- hi_min : ∀ i ∈ univ, y.val i₀ ≤ y.val i. refine ⟨i₀, ?_⟩ rw [disp_Ei A y i₀] -- (Ay)_{i₀} ≥ y_{i₀} via A_{i₀,j} ≥ 0, y_j ≥ y_{i₀}, ∑ A_{i₀,j} = 1. have hAy_ge : ∑ j, A i₀ j * y.val j ≥ y.val i₀ := by have hge : ∀ j, A i₀ j * y.val i₀ ≤ A i₀ j * y.val j := fun j => mul_le_mul_of_nonneg_left (hi_min j (Finset.mem_univ _)) (hA.nonneg i₀ j) calc y.val i₀ = (∑ j, A i₀ j) * y.val i₀ := by rw [hA.rowSum i₀, one_mul] _ = ∑ j, A i₀ j * y.val i₀ := by rw [Finset.sum_mul] _ ≤ ∑ j, A i₀ j * y.val j := Finset.sum_le_sum (fun j _ => hge j) linarith