symmetric_game_regret_le_of_sup_sub_inf_le
For a positive natural number n, an n-by-n real matrix A, a strategy x in stdSimplex ℝ (Fin n), and a real number ε, if Finset.univ.sup' Finset.univ_nonempty (fun i => Matrix.mulVec A x.val i) - Finset.univ.inf' Finset.univ_nonempty (fun j => Matrix.vecMul x.val A j) ≤ ε, then symmetric_game_regret A x ≤ ε.
Statement
lemma symmetric_game_regret_le_of_sup_sub_inf_le {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n)) (ε : ℝ) (h : Finset.univ.sup' Finset.univ_nonempty (fun i => Matrix.mulVec A x.val i) - Finset.univ.inf' Finset.univ_nonempty (fun j => Matrix.vecMul x.val A j) ≤ ε) : symmetric_game_regret A x ≤ ε
- Source
- arXiv:2610.25524, Lemma 4.1
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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… - symmetric_game_regret_le_sup_sub_infFor any strategy x in stdSimplex ℝ (Fin n), the regret symmetric_game_regret A x is at most the maximum over i of (A *ᵥ x) i minus the…
- symmetric_game_regretFor a positive natural number n, an n-by-n matrix A over ℝ, and a strategy p in
- 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 non-zero natural number $n$, any $n \times n$ real matrix $A$, any point $x$ in the standard simplex on $\mathrm{Fin}\ n$, and any real number $\varepsilon$, if the maximum over all $i \in \mathrm{Fin}\ n$ of $(A x)_i$ minus the minimum over all $j \in \mathrm{Fin}\ n$ of $(x^\top A)_j$ is at most $\varepsilon$, then the symmetric game regret of $A$ and $x$ is at most $\varepsilon$.
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
The symmetric game regret of a strategy $x$ is known to be bounded above by the difference between the maximum pure row payoff and the minimum pure column payoff. Combining this bound with the hypothesis that the difference is at most $\varepsilon$ by transitivity of inequality immediately yields that the regret is at most $\varepsilon$.
symmetric_game_regret A x ≤ ε
The symmetric game regret of $x$ is bounded above by the difference between the maximum pure row payoff and the minimum pure column payoff (by `symmetric_game_regret_le_sup_sub_inf`). Since this difference is assumed to be at most $\varepsilon$ (hypothesis $h$), transitivity of inequality (`le_trans`) concludes the proof.
uses
le_trans,symmetric_game_regret_le_sup_sub_infexact le_trans (symmetric_game_regret_le_sup_sub_inf A x) h
le_trans- Transitivity of the order relation: if $a \le b$ and $b \le c$, then $a \le c$.
symmetric_game_regret_le_sup_sub_inf- The symmetric game regret of strategy $x$ with matrix $A$ is bounded above by the maximum pure row payoff $\max_i (Ax)_i$ minus the minimum pure column payoff $\min_j (x^T A)_j$.
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 maximum pure row payoff minus minimum pure column payoff is at most ε, then the symmetric game regret is at most ε. -/lemma symmetric_game_regret_le_of_sup_sub_inf_le {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n)) (ε : ℝ) (h : Finset.univ.sup' Finset.univ_nonempty (fun i => Matrix.mulVec A x.val i) - Finset.univ.inf' Finset.univ_nonempty (fun j => Matrix.vecMul x.val A j) ≤ ε) : symmetric_game_regret A x ≤ ε := by exact le_trans (symmetric_game_regret_le_sup_sub_inf A x) h