AFTD Auto-Formalizing Theoretical Domains

saddle_gap_first_payoff_pure_ge_of_sub_ge

theoremverified

For an n-by-n matrix A with nonnegative entries, probability vectors a and b in stdSimplex ℝ (Fin n), and real number v, if Matrix.vecMul a.val A k - Matrix.mulVec A b.val k ≥ v for all k in Fin n, then Matrix.vecMul a.val A k ≥ v for all k in Fin n.

Statement

lemma saddle_gap_first_payoff_pure_ge_of_sub_ge {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (hA_nonneg : ∀ i j, 0 ≤ A i j) (a b : stdSimplex ℝ (Fin n)) (v : ℝ) (h : ∀ k : Fin n, Matrix.vecMul a.val A k - Matrix.mulVec A b.val k ≥ v) (k : Fin n) : Matrix.vecMul a.val A k ≥ v
Source
arXiv:2610.25524 Lemma 4.2
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • saddle_gap_marginal_payoff_boundsLet n be a positive natural number. For any matrix A : Matrix (Fin n) (Fin n) ℝ with non-negative entries and any optimal row strategy σ…

Read back from the Lean

Let $n$ be a natural number. Let $A$ be an $n \times n$ real matrix with non-negative entries ($A_{i, j} \ge 0$ for all $i, j \in \mathrm{Fin}(n)$). Let $a$ and $b$ be vectors in the standard simplex over $\mathrm{Fin}(n)$ (i.e., non-negative real vectors whose entries sum to $1$). Let $v$ be a real number. Assume that for all indices $k' \in \mathrm{Fin}(n)$, the $k'$-th component of $a^\top A - A b$ is at least $v$ (that is, $(a^\top A)_{k'} - (A b)_{k'} \ge v$). Then for any index $k \in \mathrm{Fin}(n)$, the $k$-th component of $a^\top A$ is at least $v$ (that is, $(a^\top A)_k \ge v$).

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 theorem asserts that if the difference between the $k$-th column payoffs $(a A)_k$ and $(A b)_k$ is at least $v$, then $(a A)_k ≥ v$ as well. The proof first establishes that $(A b)_k ≥ 0$ because both the matrix entries and the simplex vector components are nonnegative, so their dot product is a sum of nonnegative products. Combining $(a A)_k - (A b)_k ≥ v$ with $(A b)_k ≥ 0$ via linear arithmetic immediately yields $(a A)_k ≥ v$.

  1. The $k$-th entry of the matrix-vector product $A b$ is nonnegative: $0 ≤ (A b)_k$.

    Expanding the definition of matrix-vector multiplication expresses $(A b)_k$ as the dot product $\sum_{i} A_{k, i} b_i$. Since every entry of the matrix $A$ is nonnegative ($A_{k, i} ≥ 0$) and the vector $b$ belongs to the standard simplex ($b_i ≥ 0$), each summand $A_{k, i} b_i$ is nonnegative by `mul_nonneg`. By `Finset.sum_nonneg`, the sum of these nonnegative terms is nonnegative.

    lines 3–7

    uses Finset.sum_nonneg, mul_nonneg

      have h_nonneg : 0 ≤ Matrix.mulVec A b.val k := by
        simp [Matrix.mulVec, dotProduct]
        apply Finset.sum_nonneg
        intro i _
        exact mul_nonneg (hA_nonneg k i) (b.2.1 i)
  2. The pure column payoff satisfies $(a A)_k ≥ v$.

    Specializing the hypothesis $h$ to index $k$ provides $(a A)_k - (A b)_k ≥ v$. Since $(A b)_k ≥ 0$, linear arithmetic (`linarith`) immediately implies that $(a A)_k ≥ v$.

    lines 8–9

      have hk := h k
      linarith
Finset.sum_nonneg
The sum of a finite set of nonnegative terms is nonnegative.
mul_nonneg
The product of two nonnegative elements is nonnegative.

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

/-- Pure column payoff is at least v when the difference between first and second marginal payoffs is at least v and the matrix is nonnegative. -/lemma saddle_gap_first_payoff_pure_ge_of_sub_ge {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (hA_nonneg : ∀ i j, 0 ≤ A i j) (a b : stdSimplex ℝ (Fin n)) (v : ℝ) (h : ∀ k : Fin n, Matrix.vecMul a.val A k - Matrix.mulVec A b.val k ≥ v) (k : Fin n) : Matrix.vecMul a.val A k ≥ v := by  have h_nonneg : 0 ≤ Matrix.mulVec A b.val k := by    simp [Matrix.mulVec, dotProduct]    apply Finset.sum_nonneg    intro i _    exact mul_nonneg (hA_nonneg k i) (b.2.1 i)  have hk := h k  linarith
See it in the graphDiscuss this resultChallenge it