saddle_gap_marginal_payoff_bounds
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 marginalsaddle_gap_first_marginal σinstdSimplex ℝ (Fin n)… - saddle_gap_second_marginalFor σ in the standard simplex
stdSimplex ℝ (Fin n × Fin n), its second marginalsaddle_gap_second_marginal σinstdSimplex ℝ (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
xagainst pure columnj. - MatrixGameA finite two-player zero-sum matrix game. Player I chooses row
i : I, Player II chooses columnj : J. Payoff to Player I isg i j… - MatrixGame.payoffAgainstColumnExpected payoff when Player I uses mixed strategy
xagainst pure columnj.
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.
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.
uses
Fintype.sum_prod_type,mul_sub,Finset.sum_sub_distribdsimp [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]
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.
uses
Finset.sum_mulcongr 1 · congr 1 with i rw [Finset.sum_mul] rfl
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.
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)
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.
uses
saddle_gap_marginal_payoff_bounds_helper_ej,Finset.inf'_le,Finset.mem_univintro 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
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.
uses
saddle_gap_first_payoff_pure_ge_of_sub_gehave 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 h1The 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.
uses
saddle_gap_self_payoff_ge_two_v_of_sub_gehave 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 h1All three payoff bounds hold simultaneously.
We assemble the three established inequalities into a conjunction.
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
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.
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⟩