AFTD Auto-Formalizing Theoretical Domains

saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies

theoremverified

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

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.

  1. 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.

    line 6

      exact hx.le

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

/-- 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
See it in the graphDiscuss this resultChallenge it