saddle_gap_game
def
Given 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], with payoff A_{ik} - A_{kj}.
Statement
def saddle_gap_game {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) : MatrixGame (Fin n × Fin n) (Fin n) ℝ- Defined in
- arXiv:2610.25524 Section 4
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- 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…
- MatrixGameA finite two-player zero-sum matrix game. Player I chooses row
- Used by 4
- 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_guarantee_II_le_of_mem_optimalColumnStrategiesFor a positive natural number n, an n-by-n real matrix A, and a strategy x in
stdSimplex ℝ (Fin n), if x is an optimal column strategy… - 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 σ…
- saddle_gap_guarantee_II_eq_sup_sub_infFor 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 :…
- saddle_gap_low_value_symmetric_approx_nashLet n be a positive natural number with
Read back from the Lean
For any natural number $n$ and any $n \times n$ real matrix $A$, saddle_gap_game A is defined as the matrix game (MatrixGame) with row strategy set $\mathrm{Fin}(n) \times \mathrm{Fin}(n)$, column strategy set $\mathrm{Fin}(n)$, payoff values in $\mathbb{R}$, and payoff function $g$ given by $g(i, j)(k) = A_{i, k} - A_{k, j}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The saddle-gap auxiliary zero-sum matrix game S for a matrix A. -/ def saddle_gap_game {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) : MatrixGame (Fin n × Fin n) (Fin n) ℝ := ⟨fun (i, j) k => A i k - A k j⟩