AFTD Auto-Formalizing Theoretical Domains

ZeroSumGame

structureimported Lean

A finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix $A : \mathrm{Fin}\,M \to \mathrm{Fin}\,N \to \mathbb{R}$ together with proofs that every entry satisfies $0 \le A_{ij} \le 1$. The row player seeks to maximise the payoff; the column player seeks to minimise it.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
structure ZeroSumGame (M N : ℕ)
Defined in
TCSlib, `ZeroSumGame`
Lean proof
By Karim Abdel Sadek, Mark Bedaywi, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Karim Abdel Sadek and Mark Bedaywi. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
none listed
Used by 35
  • OnlineLearning.pureVsPayoff_nonnegNonnegativity of a pure row's expected payoff. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions,…
  • hedgeResponseNat_isBestResponseOnline column response is a best response. Let $G$ be a finite zero-sum game with $M \ge 1$ row actions and $N \ge 1$ column actions, let…
  • pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
  • OnlineLearning.finite_minimax_valueMinimax theorem for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions, whose…
  • prefixPotentialThe prefix potential is the sum of prefix Hedge weights over all rows: \[ \Phi_t \;=\; \sum_{i \in \mathrm{Fin}\,M} w_t(i). \]
  • minimax_approx_theoremApproximate minimax theorem for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$, having at…
  • weak_dualityWeak duality for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N \ge 1$ column…
  • OnlineLearning.finiteLowerValueFor a finite zero-sum game $G$ with $M$ row actions and $N$ column actions, the lower value is…
  • hedgeResponseNatThe sequence of column best responses generated online against Hedge: at time $t$, given the history $a_0, \dots, a_{t-1}$ of prior column…
  • OnlineLearning.finiteLowerValue_bddAboveRow player's guaranteed payoffs are bounded above. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$ column…
  • bestColumnGiven a game $G$ and a mixed row strategy $p$, bestColumn is the pure column $j^* \in \mathrm{Fin}\,N$ that minimises…
  • OnlineLearning.finiteUpperValueThe upper value of $G$ is \[ v^+(G) \;=\; \inf_{q \in \Delta_N}\; \sup_{i \in [M]}\; \mathrm{pureVsPayoff}(G,i,q), \] where the…
  • prefixGameLossGiven a game $G$, a prefix of $t$ column actions, and a row $i$, the prefix cumulative loss of row $i$ is…
  • prefixHedgeMixedStrategy_weight_eq_hedgeDistPrefix Hedge strategy agrees with the abstract Hedge distribution. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions…
  • bestColumn_specOptimality of the column best response. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$ column actions,…
  • prefixHedgeWeight_eq_hedgeWeightPrefix Hedge weight agrees with the induced-loss Hedge weight. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$…
  • OnlineLearning.payoffVsPure_nonnegNonnegativity of the mixed payoff against a pure column. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column…
  • OnlineLearning.pureVsPayoff_le_onePure row payoff against a mixed column is at most one. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column…
  • prefixHedgeWeightThe unnormalised Hedge weight of row $i$ after seeing a prefix of column actions at learning rate $\eta$ is…
  • payoffVsPure_averageStrategyAverage strategy's payoff against a pure column. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column…
  • prefixPotential_eq_potentialPrefix potential equals the induced Hedge potential. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$ having $M$ rows…
  • ZeroSumGame.toLossSeqGiven a game $G$ and a sequence of column responses $j_0, \dots, j_{T-1}$, the induced loss sequence for the row player is…
  • OnlineLearning.finiteUpperValue_bddBelowLower boundedness of the row-supremum values. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column…
  • hedge_constructionHedge yields an approximate minimax pair. Let $G$ be a finite two-player zero-sum game with $M \ge 2$ row actions and $N \ge 1$ column…
  • prefixHedgeWeight_posPositivity of the prefix Hedge weight. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions, let…
  • prefixGameLoss_eq_cumLossPrefix game loss equals induced cumulative loss. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column actions,…
  • prefixHedgeMixedStrategyThe normalised Hedge distribution after a prefix of $t$ column actions is the mixed row strategy with weights…
  • prefixPotential_posPositivity of the prefix potential. Let $G$ be a finite two-player zero-sum game with at least one row action, fix a learning rate…
  • OnlineLearning.payoffVsPure_le_oneExpected payoff against a pure column is at most one. Let $G$ be a finite two-player zero-sum game whose payoff matrix $A$ has every entry…
  • ZeroSumGame.toLossSeq_validValidity of the loss sequence induced by a zero-sum game. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N$ column…
  • regret_to_payoffRegret-to-payoff bridge for zero-sum games. Consider a finite two-player zero-sum game with $M \ge 1$ row actions and $N$ column actions…
  • payoffVsPureGiven a game $G$, a mixed row strategy $p$, and a pure column $j$, the expected payoff against column $j$ is…
  • pureVsPayoff_empiricalStrategyPure-row payoff against the empirical column strategy. Let $G$ be a finite two-player zero-sum game with $M$ row actions and $N \ge 1$…
  • OnlineLearning.finiteLowerValue_le_upperValueWeak duality for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M \geq 1$ row actions and $N \geq 1$ column…
  • approx_minimaxApproximate minimax for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with payoff matrix $A$, having $M \ge 2$ row…

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
/-- A finite two-player zero-sum game with `M` row actions and `N` column actions, given by a payoff matrix with entries in the interval `[0, 1]`. The row player wants larger payoffs; the column player wants smaller payoffs. [CBL06, §7.1]; [FS99, §2]. Deviation: FS99's `M(i, j)` is the row player's loss (row minimizes); here entries are payoffs and the row player maximizes. Entries are in `[0, 1]` as in FS99 (CBL06 allows general bounded payoffs). -/
structure ZeroSumGame (M N : ℕ) where
  payoff : Fin M → Fin N → ℝ
  payoff_nonneg : ∀ i j, 0 ≤ payoff i j
  payoff_le_one : ∀ i j, payoff i j ≤ 1
See it in the graphDiscuss this resultChallenge it