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.ZeroSumGame← ZeroSumGame (TCSlib/LearningTheory/Minimax/ZeroSumGame.lean:48): verbatim
- 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$,
bestColumnis 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