AFTD Auto-Formalizing Theoretical Domains

symmetric_game_regret_le_sup_sub_inf

theoremverified

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

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.

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

    line 7

      unfold symmetric_game_regret
  2. The 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.

    line 8

    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

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