AFTD Auto-Formalizing Theoretical Domains

saddle_gap_self_payoff_ge_two_v_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 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.

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

    lines 3–14

    uses Finset.sum_le_sum, mul_le_mul_of_nonneg_left, Finset.sum_mul, one_mul

      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
  2. 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.

    lines 15–21

    uses dotProduct_sub

      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)
  3. 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.

    lines 22–27

      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
  4. 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.

    lines 28–33

    uses dotProduct_comm, Matrix.dotProduct_mulVec

      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
  5. 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.

    lines 34–42

    uses Finset.sum_nonneg, mul_nonneg

      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)
  6. 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.

    lines 43–45

      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

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