saddle_gap_self_payoff_ge_two_v_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 dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * v.
Statement
lemma saddle_gap_self_payoff_ge_two_v_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) : dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * 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
For any natural number $n$, any $n \times n$ real matrix $A$ (indexed by $\mathrm{Fin}\ n$), if all entries of $A$ are non-negative ($0 \le A_{i,j}$ for all $i, j \in \mathrm{Fin}\ n$), then for any probability distributions $a, b$ in the standard simplex $\mathrm{stdSimplex}\ \mathbb{R}\ (\mathrm{Fin}\ n)$ and any real number $v$, if for every index $k \in \mathrm{Fin}\ n$, the $k$-th component of the vector-matrix product $a^T A$ minus the $k$-th component of the matrix-vector product $A b$ is at least $v$ (that is, $(a^T A)_k - (A b)_k \ge v$), then the quadratic form $a^T A a$ (the dot product of $a$ and $A a$) is at least $2v$.
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 averages the coordinatewise inequality (aᵀ A)ₖ - (A b)ₖ ≥ v against the probability vectors a and b. Weighting by a yields v ≤ aᵀ A a - aᵀ A b, and weighting by b yields v ≤ aᵀ A b - bᵀ A b upon rewriting the cross-terms using the adjoint property of matrix multiplication. Adding these two inequalities cancels the cross-term aᵀ A b, leaving 2v ≤ aᵀ A a - bᵀ A b; since A and b have nonnegative entries, bᵀ A b ≥ 0, which immediately implies aᵀ A a ≥ 2v.
For any probability vector p in the standard simplex, the inner product of p with the marginal difference vector is at least v: v ≤ p ⬝ᵥ (fun k => Matrix.vecMul a.val A k - Matrix.mulVec A b.val k).
Because p is in the standard simplex, its entries are nonnegative and sum to 1. Multiplying the coordinatewise hypothesis (aᵀ A)ₖ - (A b)ₖ ≥ v by pₖ ≥ 0 and summing over all k gives ∑ₖ pₖ v ≤ ∑ₖ pₖ ((aᵀ A)ₖ - (A b)ₖ). Since the coefficients sum to 1, the left-hand sum simplifies to (∑ₖ pₖ) * v = 1 * v = v, matching the definition of the dot product on the right.
uses
Finset.sum_le_sum,mul_le_mul_of_nonneg_left,Finset.sum_mul,one_mulhave h_dot (p : stdSimplex ℝ (Fin n)) : v ≤ dotProduct p.val (fun k => Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) := by have hp_nonneg : ∀ k, 0 ≤ p.val k := p.2.1 have hp_sum : ∑ k, p.val k = 1 := p.2.2 have h1 : ∑ k, p.val k * v ≤ ∑ k, p.val k * (Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) := by apply Finset.sum_le_sum intro k _ exact mul_le_mul_of_nonneg_left (h k) (hp_nonneg k) have h2 : ∑ k, p.val k * v = (∑ k, p.val k) * v := (Finset.sum_mul _ _ _).symm rw [hp_sum, one_mul] at h2 unfold dotProduct linarith
The dot product distributes over the marginal difference: p ⬝ᵥ (aᵀ A - A b) = (p ⬝ᵥ aᵀ A) - (p ⬝ᵥ A b).
The vector fun k => (aᵀ A)ₖ - (A b)ₖ is definitionally equal to the difference of vectors aᵀ A - A b. The dot product distributes over subtraction by dotProduct_sub.
uses
dotProduct_subhave h_sub (p : stdSimplex ℝ (Fin n)) : dotProduct p.val (fun k => Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) = dotProduct p.val (Matrix.vecMul a.val A) - dotProduct p.val (Matrix.mulVec A b.val) := by have : (fun k => Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) = Matrix.vecMul a.val A - Matrix.mulVec A b.val := rfl rw [this] exact dotProduct_sub p.val (Matrix.vecMul a.val A) (Matrix.mulVec A b.val)
Specializing the averaged inequality to a and b yields v ≤ a ⬝ᵥ (aᵀ A) - a ⬝ᵥ (A b) and v ≤ b ⬝ᵥ (aᵀ A) - b ⬝ᵥ (A b).
Applying the general simplex inequality to p = a and p = b, and splitting the dot product via the distributivity lemma, produces lower bounds of v for the evaluated bilinear expressions.
have ha : v ≤ dotProduct a.val (Matrix.vecMul a.val A) - dotProduct a.val (Matrix.mulVec A b.val) := by rw [← h_sub a] exact h_dot a have hb : v ≤ dotProduct b.val (Matrix.vecMul a.val A) - dotProduct b.val (Matrix.mulVec A b.val) := by rw [← h_sub b] exact h_dot b
By adjointness and commutativity, a ⬝ᵥ (aᵀ A) = a ⬝ᵥ (A a) and b ⬝ᵥ (aᵀ A) = a ⬝ᵥ (A b).
Using symmetry of the dot product and the identity (aᵀ A) ⬝ᵥ x = a ⬝ᵥ (A x), we rewrite a ⬝ᵥ (aᵀ A) as a ⬝ᵥ (A a) = aᵀ A a, and b ⬝ᵥ (aᵀ A) as a ⬝ᵥ (A b) = aᵀ A b.
uses
dotProduct_comm,Matrix.dotProduct_mulVechave h_comm1 : dotProduct a.val (Matrix.vecMul a.val A) = dotProduct a.val (Matrix.mulVec A a.val) := by rw [dotProduct_comm] exact (Matrix.dotProduct_mulVec a.val A a.val).symm have h_comm2 : dotProduct b.val (Matrix.vecMul a.val A) = dotProduct a.val (Matrix.mulVec A b.val) := by rw [dotProduct_comm] exact (Matrix.dotProduct_mulVec a.val A b.val).symm
The quadratic form bᵀ A b is nonnegative: 0 ≤ b ⬝ᵥ (A b).
Expanding the definitions, b ⬝ᵥ (A b) = ∑ᵢ bᵢ ∑ⱼ Aᵢⱼ bⱼ. Since every entry Aᵢⱼ ≥ 0 and every component bᵢ, bⱼ ≥ 0, all products and their sums are nonnegative.
uses
Finset.sum_nonneg,mul_nonneghave hb_nonneg : 0 ≤ dotProduct b.val (Matrix.mulVec A b.val) := by unfold dotProduct Matrix.mulVec apply Finset.sum_nonneg intro i _ apply mul_nonneg (b.2.1 i) unfold dotProduct apply Finset.sum_nonneg intro j _ exact mul_nonneg (hA_nonneg i j) (b.2.1 j)
The payoff satisfies a ⬝ᵥ (A a) ≥ 2 * v.
Rewriting with the commutativity identities turns the two bounds into v ≤ aᵀ A a - aᵀ A b and v ≤ aᵀ A b - bᵀ A b. Summing these cancels the cross-term aᵀ A b, giving 2v ≤ aᵀ A a - bᵀ A b. Since bᵀ A b ≥ 0, linear arithmetic concludes aᵀ A a ≥ 2v.
rw [h_comm1] at ha rw [h_comm2] at hb linarith
Finset.sum_le_sum- If each term in a finite sum is bounded by the corresponding term in another sum, then the sum is bounded by the other sum.
mul_le_mul_of_nonneg_left- Multiplication on the left by a nonnegative element preserves inequality: if b ≤ c and 0 ≤ a, then a * b ≤ a * c.
Finset.sum_mul- Multiplication distributes over finite summation from the right: (∑ i, f i) * a = ∑ i, f i * a.
one_mul- One is the left identity for multiplication: 1 * a = a.
dotProduct_sub- The dot product distributes over vector subtraction: u ⬝ᵥ (v - w) = u ⬝ᵥ v - u ⬝ᵥ w.
dotProduct_comm- The dot product is symmetric: v ⬝ᵥ w = w ⬝ᵥ v.
Matrix.dotProduct_mulVec- Adjoint relation between matrix-vector and vector-matrix multiplication: v ⬝ᵥ (A *ᵥ w) = (vᵥ* A) ⬝ᵥ w.
Finset.sum_nonneg- A finite sum of nonnegative terms is nonnegative.
mul_nonneg- The product of two nonnegative numbers 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
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.
/-- Averaging the saddle-gap marginal difference inequality over a and b yields the self-payoff bound aᵀ A a ≥ 2v. -/lemma saddle_gap_self_payoff_ge_two_v_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) : dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * v := by have h_dot (p : stdSimplex ℝ (Fin n)) : v ≤ dotProduct p.val (fun k => Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) := by have hp_nonneg : ∀ k, 0 ≤ p.val k := p.2.1 have hp_sum : ∑ k, p.val k = 1 := p.2.2 have h1 : ∑ k, p.val k * v ≤ ∑ k, p.val k * (Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) := by apply Finset.sum_le_sum intro k _ exact mul_le_mul_of_nonneg_left (h k) (hp_nonneg k) have h2 : ∑ k, p.val k * v = (∑ k, p.val k) * v := (Finset.sum_mul _ _ _).symm rw [hp_sum, one_mul] at h2 unfold dotProduct linarith have h_sub (p : stdSimplex ℝ (Fin n)) : dotProduct p.val (fun k => Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) = dotProduct p.val (Matrix.vecMul a.val A) - dotProduct p.val (Matrix.mulVec A b.val) := by have : (fun k => Matrix.vecMul a.val A k - Matrix.mulVec A b.val k) = Matrix.vecMul a.val A - Matrix.mulVec A b.val := rfl rw [this] exact dotProduct_sub p.val (Matrix.vecMul a.val A) (Matrix.mulVec A b.val) have ha : v ≤ dotProduct a.val (Matrix.vecMul a.val A) - dotProduct a.val (Matrix.mulVec A b.val) := by rw [← h_sub a] exact h_dot a have hb : v ≤ dotProduct b.val (Matrix.vecMul a.val A) - dotProduct b.val (Matrix.mulVec A b.val) := by rw [← h_sub b] exact h_dot b have h_comm1 : dotProduct a.val (Matrix.vecMul a.val A) = dotProduct a.val (Matrix.mulVec A a.val) := by rw [dotProduct_comm] exact (Matrix.dotProduct_mulVec a.val A a.val).symm have h_comm2 : dotProduct b.val (Matrix.vecMul a.val A) = dotProduct a.val (Matrix.mulVec A b.val) := by rw [dotProduct_comm] exact (Matrix.dotProduct_mulVec a.val A b.val).symm have hb_nonneg : 0 ≤ dotProduct b.val (Matrix.mulVec A b.val) := by unfold dotProduct Matrix.mulVec apply Finset.sum_nonneg intro i _ apply mul_nonneg (b.2.1 i) unfold dotProduct apply Finset.sum_nonneg intro j _ exact mul_nonneg (hA_nonneg i j) (b.2.1 j) rw [h_comm1] at ha rw [h_comm2] at hb linarith