AFTD Auto-Formalizing Theoretical Domains

symmetric_game_regret_le_of_sup_sub_inf_le

theoremverified

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…
Used by 1

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

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

    line 7

    uses le_trans, symmetric_game_regret_le_sup_sub_inf

      exact 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

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