AFTD Auto-Formalizing Theoretical Domains

saddle_gap_low_value_symmetric_approx_nash

theoremverifiedformalization

Let 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] (satisfying ∀ i j, 0 ≤ A i j and ∀ i j, A i j ≤ 1). Let ε be a real number. If x : stdSimplex ℝ (Fin n) is an optimal column strategy for the saddle-gap game (that is, x ∈ (saddle_gap_game A).optimalColumnStrategies) and the value of the saddle-gap game satisfies (saddle_gap_game A).value ≤ ε, then the symmetric game regret of x satisfies symmetric_game_regret A x ≤ ε.

Statement

theorem saddle_gap_low_value_symmetric_approx_nash {n : ℕ} [NeZero n]
    (A : Matrix (Fin n) (Fin n) ℝ)
    (hA_nonneg : ∀ i j, 0 ≤ A i j) (hA_le_one : ∀ i j, A i j ≤ 1)
    (ε : ℝ) (x : stdSimplex ℝ (Fin n))
    (hx : x ∈ (saddle_gap_game A).optimalColumnStrategies)
    (hv : (saddle_gap_game A).value ≤ ε) :
    symmetric_game_regret A x ≤ ε
Formalizes
arXiv:2610.25524 Lemma 4.1
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • 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],…
  • symmetric_game_regretFor a positive natural number n, an n-by-n matrix A over ℝ, and a strategy p in stdSimplex ℝ (Fin n), the symmetric game regret…
  • MatrixGame.optimalColumnStrategiesThe set of optimal column strategies: mixed strategies that achieve the minimax value.
  • MatrixGame.valueThe value of a matrix game (sSup-based; needs order completeness). Equal to both maximin and minimax by the minimax theorem…
  • saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategiesFor 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…
  • saddle_gap_guarantee_II_eq_sup_sub_infFor a positive natural number n with [NeZero n], an n-by-n real matrix A : Matrix (Fin n) (Fin n) ℝ, and a strategy vector x :…
  • symmetric_game_regret_le_of_sup_sub_inf_leFor a positive natural number n, an n-by-n real matrix A, a strategy x in stdSimplex ℝ (Fin n), and a real number ε, if…
  • 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.

Read back from the Lean

Let $n$ be a positive natural number (n : ℕ with [NeZero n]). Let $A$ be an $n \times n$ real matrix (Matrix (Fin n) (Fin n) ℝ) whose entries satisfy $0 \le A_{i, j}$ and $A_{i, j} \le 1$ for all $i, j \in \text{Fin } n$. Let $\varepsilon \in \mathbb{R}$, and let $x$ be a probability vector on $\text{Fin } n$ (an element of stdSimplex ℝ (Fin n)). Assume: 1. $x$ belongs to the optimal column strategies of the zero-sum game saddle_gap_game A (hx : x ∈ (saddle_gap_game A).optimalColumnStrategies); 2. the value of saddle_gap_game A is at most $\varepsilon$ (hv : (saddle_gap_game A).value ≤ ε). Then the symmetric game regret of $x$ with respect to $A$ is at most $\varepsilon$ (symmetric_game_regret A x ≤ ε).

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

To show that an optimal column strategy x in a low-value saddle-gap game achieves symmetric game regret at most ε, the proof bounds Player II's guarantee at x by the value of the game (and hence by ε). It then rewrites this guarantee explicitly as the difference between the maximum component of Ax and the minimum component of xᵀ A. Finally, because this difference upper-bounds the symmetric game regret, the desired bound follows.

  1. Player II's guarantee at strategy x in the saddle-gap game is at most ε.

    Because x is an optimal column strategy for the saddle-gap game, Player II's guarantee at x is at most the game's value by saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies. Combining this with the hypothesis that the game's value is at most ε via transitivity of ≤ (le_trans) establishes that the guarantee is at most ε.

    lines 9–11

    uses saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies, le_trans

      have h1 : (saddle_gap_game A).guarantee_II x ≤ (saddle_gap_game A).value :=
        saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies A x hx
      have h2 : (saddle_gap_game A).guarantee_II x ≤ ε := le_trans h1 hv
  2. The gap max_i (Ax)_i - min_j (xᵀ A)_j is at most ε.

    By saddle_gap_guarantee_II_eq_sup_sub_inf, Player II's guarantee for the saddle-gap game at x is precisely the maximum coordinate of Ax minus the minimum coordinate of xᵀ A. Rewriting the guarantee in the previous bound with this equality yields max_i (Ax)_i - min_j (xᵀ A)_j ≤ ε.

    line 12

    uses saddle_gap_guarantee_II_eq_sup_sub_inf

      rw [saddle_gap_guarantee_II_eq_sup_sub_inf] at h2
  3. The symmetric game regret of x is at most ε.

    The symmetric game regret of x is defined as max_i (Ax)_i - xᵀ A x, which is upper-bounded by max_i (Ax)_i - min_j (xᵀ A)_j since the convex combination xᵀ A x cannot be smaller than the minimum component of xᵀ A. Applying symmetric_game_regret_le_of_sup_sub_inf_le immediately yields symmetric_game_regret A x ≤ ε.

    line 13

    uses symmetric_game_regret_le_of_sup_sub_inf_le

      exact symmetric_game_regret_le_of_sup_sub_inf_le A x ε h2
saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies
An optimal column strategy in the saddle-gap game achieves a Player II guarantee bounded by the game's value.
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
saddle_gap_guarantee_II_eq_sup_sub_inf
For any strategy x, Player II's guarantee in the saddle-gap game equals the maximum component of Ax minus the minimum component of xᵀ A.
symmetric_game_regret_le_of_sup_sub_inf_le
If the difference max_i (Ax)_i - min_j (xᵀ A)_j is at most ε, then the symmetric game regret of x is at most ε.

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

/-- If the saddle-gap game has value at most ε, an optimal column strategy yields a symmetric ε-approximate Nash equilibrium (regret at most ε). -/theorem saddle_gap_low_value_symmetric_approx_nash {n : ℕ} [NeZero n]    (A : Matrix (Fin n) (Fin n) ℝ)    (hA_nonneg : ∀ i j, 0 ≤ A i j) (hA_le_one : ∀ i j, A i j ≤ 1)    (ε : ℝ) (x : stdSimplex ℝ (Fin n))    (hx : x ∈ (saddle_gap_game A).optimalColumnStrategies)    (hv : (saddle_gap_game A).value ≤ ε) :    symmetric_game_regret A x ≤ ε := by  have h1 : (saddle_gap_game A).guarantee_II x ≤ (saddle_gap_game A).value :=    saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies A x hx  have h2 : (saddle_gap_game A).guarantee_II x ≤ ε := le_trans h1 hv  rw [saddle_gap_guarantee_II_eq_sup_sub_inf] at h2  exact symmetric_game_regret_le_of_sup_sub_inf_le A x ε h2
See it in the graphDiscuss this resultChallenge it