saddle_gap_first_payoff_pure_ge_of_sub_ge
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$.
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.
uses
Finset.sum_nonneg,mul_nonneghave 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)
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$.
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.
- In Lean, the standard simplex `stdSimplex ℝ (Fin n)` is defined as the subtype of vectors with nonnegative entries that sum to 1. The proof directly extracts the nonnegativity of the $i$-th entry of $b$ using `b.2.1 i`.
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.
/-- 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