AFTD Auto-Formalizing Theoretical Domains

saddle_gap_marginal_payoff_bounds

theoremverifiedformalization

Let n be a positive natural number. For any matrix A : Matrix (Fin n) (Fin n) ℝ with non-negative entries and any optimal row strategy σ in (saddle_gap_game A).optimalRowStrategies, let a = saddle_gap_first_marginal σ and b = saddle_gap_second_marginal σ in stdSimplex ℝ (Fin n). Then for every k in Fin n, Matrix.vecMul a.val A k - Matrix.mulVec A b.val k ≥ (saddle_gap_game A).value, Matrix.vecMul a.val A k ≥ (saddle_gap_game A).value for all k in Fin n, and dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * (saddle_gap_game A).value.

Statement

theorem saddle_gap_marginal_payoff_bounds {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (hA_nonneg : ∀ i j, 0 ≤ A i j) (σ : stdSimplex ℝ (Fin n × Fin n)) (hσ : σ ∈ (saddle_gap_game A).optimalRowStrategies) : let a := saddle_gap_first_marginal σ; let b := saddle_gap_second_marginal σ; let v := (saddle_gap_game A).value; (∀ 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) ∧ dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * v
Formalizes
arXiv:2610.25524 Lemma 4.2
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 11
  • saddle_gap_gameGiven an n-by-n payoff matrix A, the saddle-gap game S has row player choosing a pair (i, j) in [n]² and column player choosing k in [n],…
  • saddle_gap_first_marginalFor σ in the standard simplex stdSimplex ℝ (Fin n × Fin n), its first marginal saddle_gap_first_marginal σ in stdSimplex ℝ (Fin n)…
  • saddle_gap_second_marginalFor σ in the standard simplex stdSimplex ℝ (Fin n × Fin n), its second marginal saddle_gap_second_marginal σ in stdSimplex ℝ (Fin n)…
  • saddle_gap_first_payoff_pure_ge_of_sub_geFor an n-by-n matrix A with nonnegative entries, probability vectors a and b in stdSimplex ℝ (Fin n), and real number v, if…
  • saddle_gap_self_payoff_ge_two_v_of_sub_geFor an n-by-n matrix A with nonnegative entries, probability vectors a and b in stdSimplex ℝ (Fin n), and real number v, if…
  • MatrixGame.valueThe value of a matrix game (sSup-based; needs order completeness). Equal to both maximin and minimax by the minimax theorem…
  • MatrixGame.optimalRowStrategiesThe set of optimal row strategies: mixed strategies that achieve the maximin value.
  • MatrixGame.guarantee_IPlayer I's guaranteed payoff using mixed strategy x: the minimum expected payoff over all of Player II's pure responses. A finite…
  • MatrixGame.EjExpected payoff when Player I uses x against pure column j.
  • MatrixGameA finite two-player zero-sum matrix game. Player I chooses row i : I, Player II chooses column j : J. Payoff to Player I is g i j…
  • MatrixGame.payoffAgainstColumnExpected payoff when Player I uses mixed strategy x against pure column j.

Read back from the Lean

For any positive natural number $n$ (with typeclass instance NeZero n), any $n \times n$ real matrix $A$, assuming that all entries of $A$ are non-negative ($0 \le A_{i, j}$ for all $i, j \in \mathrm{Fin}\ n$), and for any mixed strategy $\sigma$ in the standard simplex over $\mathrm{Fin}\ n \times \mathrm{Fin}\ n$ that is an optimal row strategy for the matrix game saddle_gap_game A: Let $a$ be the first marginal distribution of $\sigma$ (in the standard simplex over $\mathrm{Fin}\ n$), let $b$ be the second marginal distribution of $\sigma$ (in the standard simplex over $\mathrm{Fin}\ n$), and let $v$ be the value of the matrix game saddle_gap_game A. Then all three of the following hold: 1. For every $k \in \mathrm{Fin}\ n$, $(a^T A)_k - (A b)_k \ge v$; 2. For every $k \in \mathrm{Fin}\ n$, $(a^T A)_k \ge v$; 3. The quadratic form $a^T A a \ge 2v$ (i.e., the dot product of $a$ with $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 theorem establishes three payoff guarantees for the marginal distributions a and b of an optimal mixed strategy σ in the zero-sum saddle-gap game with payoff matrix A_{i,k} - A_{k,j}. A helper lemma first shows by algebraic rearrangement of sums that the expected payoff against column k decomposes as (a A)_k - (A b)_k; row optimality of σ then bounds this quantity below by the game value v for every column k. Combining this difference bound with the non-negativity of A immediately yields both the pure payoff lower bound (a A)_k ≥ v and the quadratic self-payoff bound a · (A a) ≥ 2v via two specialized helper lemmas.

  1. The expected payoff of σ against column k in the saddle-gap game equals the difference of two double sums over row and column indices.

    Unfolding the definitions of expected payoff against pure column k and the saddle-gap game, the payoff is ∑_{(i, j)} σ(i, j) * (A i k - A k j). Rewriting the sum over the product type Fin n × Fin n into iterated sums using Fintype.sum_prod_type, distributing multiplication over subtraction with mul_sub, and splitting the sum with Finset.sum_sub_distrib gives ∑_i ∑_j σ(i, j) * A i k - ∑_i ∑_j σ(i, j) * A k j.

    lines 6–10

    uses Fintype.sum_prod_type, mul_sub, Finset.sum_sub_distrib

      dsimp [MatrixGame.Ej, MatrixGame.payoffAgainstColumn, saddle_gap_game,
             saddle_gap_first_marginal, saddle_gap_second_marginal,
             Matrix.vecMul, Matrix.mulVec, dotProduct]
      rw [Fintype.sum_prod_type]
      simp_rw [mul_sub, Finset.sum_sub_distrib]
  2. The first double sum equals the k-th coordinate of the vector-matrix product a A, where a is the first marginal distribution of σ.

    Factoring the subtraction into two separate goals, we inspect the first term. For each fixed row index i, we factor A i k out of the inner sum over j using Finset.sum_mul to obtain (∑_j σ(i, j)) * A i k, which definitionally equals a_i * A i k and sums to (a A)_k.

    lines 11–14

    uses Finset.sum_mul

      congr 1
      · congr 1 with i
        rw [Finset.sum_mul]
        rfl
  3. The second double sum equals the k-th coordinate of the matrix-vector product A b, completing the helper lemma.

    We interchange the order of summation in the second term via Finset.sum_comm, factor A k j into the inner sum over i with Finset.mul_sum, and commute multiplication using mul_comm. This produces ∑_j A k j * (∑_i σ(i, j)) = (A b)_k, establishing that the expected payoff against column k is (a A)_k - (A b)_k.

    lines 15–20

    uses Finset.sum_comm, Finset.mul_sum, Finset.sum_congr, mul_comm

      · rw [Finset.sum_comm]
        congr 1 with j
        rw [Finset.mul_sum]
        apply Finset.sum_congr rfl
        intro i _
        exact mul_comm (σ (i, j)) (A k j)
  4. For every column action k, (a A)_k - (A b)_k ≥ v, where v is the value of the saddle-gap game.

    Let a and b be the marginals of σ, and v be the game value. Because σ is an optimal row strategy, its guaranteed payoff guarantee_I(σ) equals v. Rewriting (a A)_k - (A b)_k as the expected payoff Ej(σ, k) via the helper lemma and replacing v with guarantee_I(σ), the inequality holds because guarantee_I is defined as the minimum payoff over all columns, and the minimum over a finite set is bounded above by any element by Finset.inf'_le and Finset.mem_univ.

    lines 24–32

    uses saddle_gap_marginal_payoff_bounds_helper_ej, Finset.inf'_le, Finset.mem_univ

      intro a b v
      have h1 : ∀ k : Fin n, Matrix.vecMul a.val A k - Matrix.mulVec A b.val k ≥ v := by
        intro k
        have hopt : (saddle_gap_game A).guarantee_I σ = v := hσ
        rw [← saddle_gap_marginal_payoff_bounds_helper_ej A σ k]
        rw [← hopt]
        dsimp [MatrixGame.guarantee_I]
        apply Finset.inf'_le
        exact Finset.mem_univ k
  5. For every column action k, (a A)_k ≥ v.

    Applying saddle_gap_first_payoff_pure_ge_of_sub_ge to the non-negativity hypothesis hA_nonneg and the lower bound (a A)_k - (A b)_k ≥ v yields (a A)_k ≥ v for every k.

    lines 33–34

    uses saddle_gap_first_payoff_pure_ge_of_sub_ge

      have h2 : ∀ k : Fin n, Matrix.vecMul a.val A k ≥ v :=
        saddle_gap_first_payoff_pure_ge_of_sub_ge A hA_nonneg a b v h1
  6. The quadratic self-payoff satisfies a · (A a) ≥ 2 * v.

    Applying saddle_gap_self_payoff_ge_two_v_of_sub_ge to the non-negativity hypothesis and the difference bound yields a · (A a) ≥ 2 * v.

    lines 35–36

    uses saddle_gap_self_payoff_ge_two_v_of_sub_ge

      have h3 : dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * v :=
        saddle_gap_self_payoff_ge_two_v_of_sub_ge A hA_nonneg a b v h1
  7. All three payoff bounds hold simultaneously.

    We assemble the three established inequalities into a conjunction.

    line 37

      exact ⟨h1, h2, h3⟩
Fintype.sum_prod_type
A sum over a Cartesian product of two finite types equals the iterated sum over each type.
mul_sub
Multiplication distributes over subtraction on the left: a * (b - c) = a * b - a * c.
Finset.sum_sub_distrib
The sum of a difference of functions over a finite set equals the difference of the sums.
Finset.sum_mul
Multiplication distributes over a finite sum on the right: (∑ i ∈ s, f i) * a = ∑ i ∈ s, f i * a.
Finset.sum_comm
The order of summation in a double sum over finite sets can be interchanged.
Finset.mul_sum
Multiplication distributes over a finite sum on the left: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree at every index.
mul_comm
Multiplication in a commutative magma is commutative: a * b = b * a.
saddle_gap_marginal_payoff_bounds_helper_ej
In the saddle-gap game with matrix A, the expected payoff of strategy σ against pure column k equals (a A)_k - (A b)_k, where a and b are the first and second marginals of σ.
Finset.inf'_le
The infimum (minimum) of a function over a nonempty finite set is at most its value at any element of that set.
Finset.mem_univ
Every element of a finite type belongs to its universal set Finset.univ.
saddle_gap_first_payoff_pure_ge_of_sub_ge
For a non-negative matrix A and marginal distributions a and b, if (a A)_k - (A b)_k ≥ v for all k, then (a A)_k ≥ v for all k.
saddle_gap_self_payoff_ge_two_v_of_sub_ge
For a non-negative matrix A and marginal distributions a and b, if (a A)_k - (A b)_k ≥ v for all k, then the self-payoff a · (A a) ≥ 2 * v.

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

lemma saddle_gap_marginal_payoff_bounds_helper_ej {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ)    (σ : stdSimplex ℝ (Fin n × Fin n)) (k : Fin n) :    (saddle_gap_game A).Ej σ k =      Matrix.vecMul (saddle_gap_first_marginal σ).val A k -      Matrix.mulVec A (saddle_gap_second_marginal σ).val k := by  dsimp [MatrixGame.Ej, MatrixGame.payoffAgainstColumn, saddle_gap_game,         saddle_gap_first_marginal, saddle_gap_second_marginal,         Matrix.vecMul, Matrix.mulVec, dotProduct]  rw [Fintype.sum_prod_type]  simp_rw [mul_sub, Finset.sum_sub_distrib]  congr 1  · congr 1 with i    rw [Finset.sum_mul]    rfl  · rw [Finset.sum_comm]    congr 1 with j    rw [Finset.mul_sum]    apply Finset.sum_congr rfl    intro i _    exact mul_comm (σ (i, j)) (A k j)/-- Payoff and self-payoff guarantees from saddle-gap marginal distributions (arXiv:2610.25524 Lemma 4.2). -/theorem saddle_gap_marginal_payoff_bounds {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (hA_nonneg : ∀ i j, 0 ≤ A i j) (σ : stdSimplex ℝ (Fin n × Fin n)) (hσ : σ ∈ (saddle_gap_game A).optimalRowStrategies) : let a := saddle_gap_first_marginal σ; let b := saddle_gap_second_marginal σ; let v := (saddle_gap_game A).value; (∀ 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) ∧ dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * v := by  intro a b v  have h1 : ∀ k : Fin n, Matrix.vecMul a.val A k - Matrix.mulVec A b.val k ≥ v := by    intro k    have hopt : (saddle_gap_game A).guarantee_I σ = v := hσ    rw [← saddle_gap_marginal_payoff_bounds_helper_ej A σ k]    rw [← hopt]    dsimp [MatrixGame.guarantee_I]    apply Finset.inf'_le    exact Finset.mem_univ k  have h2 : ∀ k : Fin n, Matrix.vecMul a.val A k ≥ v :=    saddle_gap_first_payoff_pure_ge_of_sub_ge A hA_nonneg a b v h1  have h3 : dotProduct a.val (Matrix.mulVec A a.val) ≥ 2 * v :=    saddle_gap_self_payoff_ge_two_v_of_sub_ge A hA_nonneg a b v h1  exact ⟨h1, h2, h3⟩
See it in the graphDiscuss this resultChallenge it