saddle_gap_guarantee_II_eq_sup_sub_inf
For a positive natural number n with [NeZero n], an n-by-n real matrix A : Matrix (Fin n) (Fin n) ℝ, and a strategy vector x : stdSimplex ℝ (Fin n), Player II's guarantee (saddle_gap_game A).guarantee_II x in the saddle-gap game equals Finset.univ.sup' Finset.univ_nonempty (fun i => Matrix.mulVec A x.val i) - Finset.univ.inf' Finset.univ_nonempty (fun j => Matrix.vecMul x.val A j).
Statement
lemma saddle_gap_guarantee_II_eq_sup_sub_inf {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n)) : (saddle_gap_game A).guarantee_II x = Finset.univ.sup' Finset.univ_nonempty (fun i => Matrix.mulVec A x.val i) - Finset.univ.inf' Finset.univ_nonempty (fun j => Matrix.vecMul x.val A j)
- Source
- arXiv:2610.25524, Eq (4.1)
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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],…
- MatrixGame.guarantee_IIPlayer II's guaranteed loss using mixed strategy
y: the maximum expected payoff (for Player I) over all of Player I's pure responses. - MatrixGame.EiExpected payoff when pure row
ifaces Player II's mixed strategyy. - 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.payoffAgainstRowExpected payoff when pure row
ifaces Player II's mixed strategyy.
- Used by 1
- saddle_gap_low_value_symmetric_approx_nashLet n be a positive natural number with
[NeZero n]. Let A : Matrix (Fin n) (Fin n) ℝ be an n-by-n real matrix with entries in [0, 1]…
- saddle_gap_low_value_symmetric_approx_nashLet n be a positive natural number with
Read back from the Lean
For any non-zero natural number $n$, any $n \times n$ real matrix $A$, and any probability vector $x$ in the standard simplex $\Delta^{\mathrm{Fin}\,n}_{\mathbb{R}}$, the quantity (saddle_gap_game A).guarantee_II x equals the maximum (supremum over $\mathrm{Fin}\,n$) of the entries of the matrix-vector product $A x$ minus the minimum (infimum over $\mathrm{Fin}\,n$) of the entries of the vector-matrix product $x A$.
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
To determine Player II's guarantee against a mixed column strategy x in the saddle-gap game, the proof first calculates the expected payoff of each pure row strategy (i, j) as (A x)_i - (xᵀ A)_j by expanding the payoff definition and using commutativity of multiplication. Player II's guarantee is by definition the supremum of these payoffs over all pairs (i, j). An auxiliary lemma shows that the supremum of f(i) - g(j) over a product of nonempty finite types decouples into sup f - inf g, using antisymmetry and the attainment of the minimum. Applying this decoupling to f(i) = (A x)_i and g(j) = (xᵀ A)_j yields the result.
The supremum of f(p.1) - g(p.2) over the Cartesian product ι × κ is at most sup f - inf g.
By antisymmetry, equality between the supremum and sup f - inf g reduces to two inequalities. For the upper bound, the supremum characterization Finset.sup'_le_iff requires showing f(p.1) - g(p.2) ≤ sup f - inf g for every pair p ∈ ι × κ. For any p, f(p.1) ≤ sup f by Finset.le_sup' and inf g ≤ g(p.2) by Finset.inf'_le. Combining these two inequalities via linear arithmetic (linarith) gives the bound.
uses
le_antisymm,Finset.sup'_le_iff,Finset.le_sup',Finset.mem_univ,Finset.inf'_leapply le_antisymm · rw [Finset.sup'_le_iff] intro p _ have h1 : f p.1 ≤ (Finset.univ : Finset ι).sup' Finset.univ_nonempty f := Finset.le_sup' f (Finset.mem_univ _) have h2 : (Finset.univ : Finset κ).inf' Finset.univ_nonempty g ≤ g p.2 := Finset.inf'_le g (Finset.mem_univ _) linarith
The supremum of f(p.1) - g(p.2) over the Cartesian product ι × κ equals sup f - inf g.
For the reverse inequality, it suffices to show sup f ≤ sup (f(p.1) - g(p.2)) + inf g, which by Finset.sup'_le_iff reduces to showing this bound for f(i) for each i ∈ ι. Since κ is finite and nonempty, g attains its infimum at some j₀ ∈ κ (Finset.exists_mem_eq_inf'). The pair (i, j₀) belongs to ι × κ, so f(i) - g(j₀) is bounded above by the supremum over all pairs (Finset.le_sup'). Rearranging this inequality gives f(i) ≤ sup (f(p.1) - g(p.2)) + inf g. Taking the supremum over i and subtracting inf g completes the proof by antisymmetry.
uses
Finset.sup'_le_iff,Finset.exists_mem_eq_inf',Finset.univ_nonempty,Finset.le_sup',Finset.mem_univ· have key : (Finset.univ : Finset ι).sup' Finset.univ_nonempty f ≤ (Finset.univ : Finset (ι × κ)).sup' Finset.univ_nonempty (fun p => f p.1 - g p.2) + (Finset.univ : Finset κ).inf' Finset.univ_nonempty g := by rw [Finset.sup'_le_iff] intro i _ obtain ⟨j₀, -, hj₀⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := κ)) g have h3 : f i - g j₀ ≤ (Finset.univ : Finset (ι × κ)).sup' Finset.univ_nonempty (fun p => f p.1 - g p.2) := Finset.le_sup' (fun p : ι × κ => f p.1 - g p.2) (Finset.mem_univ (i, j₀)) linarith linarith
For every row pure strategy p = (i, j), the expected payoff against column strategy x in the saddle-gap game equals (A x)_i - (xᵀ A)_j.
Unfolding the definitions, the payoff of row action (i, j) against column pure action k is A i k - A k j. The expected payoff against mixed strategy x is the sum over k of x k * (A i k - A k j). Distributing multiplication over subtraction (mul_sub) and splitting the sum (Finset.sum_sub_distrib) yields ∑ x k * A i k - ∑ x k * A k j. Using commutativity of multiplication (mul_comm) term-by-term via Finset.sum_congr rewrites the first sum as ∑ A i k * x k, which matches the definition of Matrix.mulVec A x i - Matrix.vecMul x A j.
uses
mul_sub,Finset.sum_sub_distrib,Finset.sum_congr,mul_commhave key : ∀ p : Fin n × Fin n, (saddle_gap_game A).Ei p x = Matrix.mulVec A x.val p.1 - Matrix.vecMul x.val A p.2 := by intro p obtain ⟨i, j⟩ := p simp only [MatrixGame.Ei, MatrixGame.payoffAgainstRow, saddle_gap_game, dotProduct, Matrix.mulVec, Matrix.vecMul, mul_sub, Finset.sum_sub_distrib] congr 1 apply Finset.sum_congr rfl intro k _ exact mul_comm (x.val k) (A i k)
Player II's guarantee against column strategy x in the saddle-gap game equals the supremum of the row payoffs minus the infimum of the column payoffs.
Player II's guarantee is defined (MatrixGame.guarantee_II) as the supremum over all pure row choices p of the expected payoff against x. Substituting the formula (A x)_(p.1) - (xᵀ A)_(p.2) from the previous step, the guarantee becomes the supremum of (A x)_(p.1) - (xᵀ A)_(p.2) over Fin n × Fin n. Applying the auxiliary lemma saddle_gap_guarantee_II_eq_sup_sub_inf_aux_sup_prod with f(i) = Matrix.mulVec A x.val i and g(j) = Matrix.vecMul x.val A j evaluates this supremum directly as sup_i (A x)_i - inf_j (xᵀ A)_j.
uses
saddle_gap_guarantee_II_eq_sup_sub_inf_aux_sup_produnfold MatrixGame.guarantee_II simp only [key] exact saddle_gap_guarantee_II_eq_sup_sub_inf_aux_sup_prod (fun i => Matrix.mulVec A x.val i) (fun j => Matrix.vecMul x.val A j)
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Finset.sup'_le_iff- The supremum of a function over a nonempty finite set is at most a if and only if each of its values is at most a.
Finset.le_sup'- The value of a function at any element of a finite set is at most its supremum over that set.
Finset.mem_univ- Every element of a finite type is an element of the universal finset.
Finset.inf'_le- The infimum of a function over a finite set is at most its value at any element of that set.
Finset.exists_mem_eq_inf'- Any function from a nonempty finite set to a linearly ordered type attains its infimum at some element of the set.
Finset.univ_nonempty- The universal finset of a nonempty finite type is nonempty.
mul_sub- Multiplication distributes over subtraction from the left: a * (b - c) = a * b - a * c.
Finset.sum_sub_distrib- The sum of a difference over a finite set equals the difference of the sums.
Finset.sum_congr- Two sums over equal finite sets are equal if their terms are equal at every element.
mul_comm- Multiplication is commutative: a * b = b * a.
saddle_gap_guarantee_II_eq_sup_sub_inf_aux_sup_prod- For functions f and g on nonempty finite types, the supremum of f(p.1) - g(p.2) over the Cartesian product equals the supremum of f minus the infimum of g.
- Linear inequalities in the auxiliary lemma are discharged automatically by linarith.
- The expansion of the expected payoff sum against pure strategies is handled by simp only.
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_guarantee_II_eq_sup_sub_inf_aux_sup_prod {ι κ : Type*} [Fintype ι] [Fintype κ] [Nonempty ι] [Nonempty κ] (f : ι → ℝ) (g : κ → ℝ) : (Finset.univ : Finset (ι × κ)).sup' Finset.univ_nonempty (fun p => f p.1 - g p.2) = (Finset.univ : Finset ι).sup' Finset.univ_nonempty f - (Finset.univ : Finset κ).inf' Finset.univ_nonempty g := by apply le_antisymm · rw [Finset.sup'_le_iff] intro p _ have h1 : f p.1 ≤ (Finset.univ : Finset ι).sup' Finset.univ_nonempty f := Finset.le_sup' f (Finset.mem_univ _) have h2 : (Finset.univ : Finset κ).inf' Finset.univ_nonempty g ≤ g p.2 := Finset.inf'_le g (Finset.mem_univ _) linarith · have key : (Finset.univ : Finset ι).sup' Finset.univ_nonempty f ≤ (Finset.univ : Finset (ι × κ)).sup' Finset.univ_nonempty (fun p => f p.1 - g p.2) + (Finset.univ : Finset κ).inf' Finset.univ_nonempty g := by rw [Finset.sup'_le_iff] intro i _ obtain ⟨j₀, -, hj₀⟩ := Finset.exists_mem_eq_inf' (Finset.univ_nonempty (α := κ)) g have h3 : f i - g j₀ ≤ (Finset.univ : Finset (ι × κ)).sup' Finset.univ_nonempty (fun p => f p.1 - g p.2) := Finset.le_sup' (fun p : ι × κ => f p.1 - g p.2) (Finset.mem_univ (i, j₀)) linarith linarith/-- Player II's guarantee against column strategy x in the saddle-gap game equals the maximum row payoff minus the minimum column payoff. -/lemma saddle_gap_guarantee_II_eq_sup_sub_inf {n : ℕ} [NeZero n] (A : Matrix (Fin n) (Fin n) ℝ) (x : stdSimplex ℝ (Fin n)) : (saddle_gap_game A).guarantee_II x = Finset.univ.sup' Finset.univ_nonempty (fun i => Matrix.mulVec A x.val i) - Finset.univ.inf' Finset.univ_nonempty (fun j => Matrix.vecMul x.val A j) := by have key : ∀ p : Fin n × Fin n, (saddle_gap_game A).Ei p x = Matrix.mulVec A x.val p.1 - Matrix.vecMul x.val A p.2 := by intro p obtain ⟨i, j⟩ := p simp only [MatrixGame.Ei, MatrixGame.payoffAgainstRow, saddle_gap_game, dotProduct, Matrix.mulVec, Matrix.vecMul, mul_sub, Finset.sum_sub_distrib] congr 1 apply Finset.sum_congr rfl intro k _ exact mul_comm (x.val k) (A i k) unfold MatrixGame.guarantee_II simp only [key] exact saddle_gap_guarantee_II_eq_sup_sub_inf_aux_sup_prod (fun i => Matrix.mulVec A x.val i) (fun j => Matrix.vecMul x.val A j)