saddle_gap_low_value_symmetric_approx_nash
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.
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 ε.
uses
saddle_gap_guarantee_II_le_of_mem_optimalColumnStrategies,le_transhave 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
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 ≤ ε.
uses
saddle_gap_guarantee_II_eq_sup_sub_infrw [saddle_gap_guarantee_II_eq_sup_sub_inf] at h2
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 ≤ ε.
uses
symmetric_game_regret_le_of_sup_sub_inf_leexact 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
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.
/-- 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