saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies
For a positive natural number n, an n-by-n real matrix A, and a strategy x in stdSimplex ℝ (Fin n), if x is an optimal column strategy in (saddle_gap_game A).optimalColumnStrategies, then Player II's guarantee (saddle_gap_game A).guarantee_II x is at most the value (saddle_gap_game A).value.
Statement
lemma saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies {n : ℕ} [NeZero n]
(A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n))
(hx : x ∈ (saddle_gap_game A).optimalColumnStrategies) :
(saddle_gap_game A).guarantee_II x ≤ (saddle_gap_game A).value- Source
- arXiv:2610.25524, Section 4
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- saddle_gap_gameGiven an n-by-n payoff matrix A, the saddle-gap game S has row player choosing a pair (i, j) in [n]² and column player choosing k in [n],…
- MatrixGame.optimalColumnStrategiesThe set of optimal column strategies: mixed strategies that achieve the minimax value.
- 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.valueThe value of a matrix game (
sSup-based; needs order completeness). Equal to both maximin and minimax by the minimax theorem…
- Used by 1
- saddle_gap_low_value_symmetric_approx_nashLet n be a positive natural number with
[NeZero n]. Let A : Matrix (Fin n) (Fin n) ℝ be an n-by-n real matrix with entries in [0, 1]…
- saddle_gap_low_value_symmetric_approx_nashLet n be a positive natural number with
Read back from the Lean
For any natural number $n$ such that $n \neq 0$ (via [NeZero n]), any $n \times n$ real matrix $A$, and any vector $x$ in the standard simplex stdSimplex ℝ (Fin n), if $x$ belongs to the set of optimal column strategies (saddle_gap_game A).optimalColumnStrategies, then Player II's guarantee (saddle_gap_game A).guarantee_II x is less than or equal to the game's value (saddle_gap_game A).value.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
By definition, the optimal column strategies of a matrix game are precisely those strategies for which Player II's guarantee equals the value of the game. Since x is assumed to be an optimal column strategy, its guarantee is equal to the game's value, which immediately implies the desired inequality.
Player II's guarantee for the strategy x is at most the value of the game.
By definition, the set `optimalColumnStrategies` of a matrix game consists of all column strategies for which Player II's guarantee equals the game's value. Hence the hypothesis `hx` states that `(saddle_gap_game A).guarantee_II x = (saddle_gap_game A).value`. Applying `.le` (which derives an inequality from an equality) yields the desired inequality.
exact hx.le
- The hypothesis `hx` is definitionally an equality: by definition of `MatrixGame.optimalColumnStrategies`, an optimal column strategy is one for which Player II's guarantee equals the game's value. The proof uses dot notation `hx.le` (invoking `Eq.le`) to deduce the inequality `≤` from this equality.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- Player II's guarantee against any optimal column strategy in the saddle-gap game is at most the game's value. -/lemma saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n)) (hx : x ∈ (saddle_gap_game A).optimalColumnStrategies) : (saddle_gap_game A).guarantee_II x ≤ (saddle_gap_game A).value := by exact hx.le