symmetric_game_regret_le_sup_sub_inf
For 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 minimum over j of (x ᵥ* A) j.
Statement
lemma symmetric_game_regret_le_sup_sub_inf {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n)) : symmetric_game_regret A x ≤ 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)
- 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… - dotProduct_mulVec_ge_inf'For any strategy x in the standard simplex stdSimplex ℝ (Fin n) and any matrix A, the self-payoff xᵀ A x is at least the minimum over j of…
- symmetric_game_regretFor a positive natural number n, an n-by-n matrix A over ℝ, and a strategy p in
- Used by 1
- 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…
- 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
Read back from the Lean
For every non-zero natural number $n$, every $n \times n$ real matrix $A$, and every element $x$ of the standard simplex over $\mathrm{Fin}(n)$, the symmetric game regret of $A$ and $x$ is less than or equal to the maximum over $i \in \mathrm{Fin}(n)$ of $(A x)_i$ minus the minimum over $j \in \mathrm{Fin}(n)$ of $(x A)_j$ (the vector-matrix product of $x$ and $A$ evaluated at $j$).
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 proof unfolds the definition of symmetric game regret as the difference between the maximum pure row payoff $\max_i (A x)_i$ and the expected payoff $x \cdot (A x)$. By `dotProduct_mulVec_ge_inf'`, this expected payoff is bounded below by the minimum pure column payoff $\min_j (x A)_j$. Linear arithmetic then immediately yields that the regret is at most the maximum pure row payoff minus the minimum pure column payoff.
The symmetric game regret is defined as $\max_i (A x)_i - x \cdot (A x)$, reducing the goal to showing $\max_i (A x)_i - x \cdot (A x) \le \max_i (A x)_i - \min_j (x A)_j$.
Unfolding the definition of `symmetric_game_regret` expresses it directly as the difference between the maximum pure row payoff $\max_i (A x)_i$ and the expected payoff $x \cdot (A x)$.
unfold symmetric_game_regretThe inequality $\max_i (A x)_i - x \cdot (A x) \le \max_i (A x)_i - \min_j (x A)_j$ holds.
By `dotProduct_mulVec_ge_inf'`, the expected payoff $x \cdot (A x)$ is bounded below by the minimum pure column payoff $\min_j (x A)_j$. Because subtracting a larger quantity yields a smaller result, negating this inequality and adding the common term $\max_i (A x)_i$ gives the result, which is closed by linear arithmetic.
uses
dotProduct_mulVec_ge_inf'linarith [dotProduct_mulVec_ge_inf' A x]
dotProduct_mulVec_ge_inf'- For any probability vector $x$ in the standard simplex, the bilinear form $x \cdot (A x)$ is at least the minimum entry of the vector-matrix product $x A$.
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.
/-- Symmetric game regret is bounded by max pure row payoff minus min pure column payoff. -/lemma symmetric_game_regret_le_sup_sub_inf {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n)) : symmetric_game_regret A x ≤ 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) := by unfold symmetric_game_regret linarith [dotProduct_mulVec_ge_inf' A x]