AFTD Auto-Formalizing Theoretical Domains

saddle_gap_guarantee_II_eq_sup_sub_inf

theoremverified

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 i faces Player II's mixed strategy y.
  • 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.payoffAgainstRowExpected payoff when pure row i faces Player II's mixed strategy y.
Used by 1

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.

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

    lines 6–13

    uses le_antisymm, Finset.sup'_le_iff, Finset.le_sup', Finset.mem_univ, Finset.inf'_le

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

    lines 14–24

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

    lines 32–41

    uses mul_sub, Finset.sum_sub_distrib, Finset.sum_congr, mul_comm

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

    lines 42–45

    uses saddle_gap_guarantee_II_eq_sup_sub_inf_aux_sup_prod

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

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