ZeroSumGame.toLossSeq_valid
theoremverifiedimported Lean
Validity 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 actions, given by a payoff matrix $A$ whose entries satisfy $0 \le A_{ij} \le 1$, and let $j_0, \dots, j_{T-1}$ be any sequence of column responses. Then the induced loss sequence for the row player, defined by $\ell_t(i) = 1 - A_{i,j_t}$ for each round $t < T$ and row action $i$, is valid: every loss lies in $[0,1]$, i.e. $0 \le \ell_t(i) \le 1$ for all $t$ and $i$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma ZeroSumGame.toLossSeq_valid {M N T : ℕ} (G : ZeroSumGame M N) (colResponse : Fin T → Fin N) : (G.toLossSeq colResponse).Valid
- Source
- TCSlib, `ZeroSumGame.toLossSeq_valid`
- 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.toLossSeq_valid← ZeroSumGame.toLossSeq_valid (TCSlib/LearningTheory/Minimax/HedgeInteraction.lean:74): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
- 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…
- LossSeq.ValidA loss sequence $\ell$ is valid if all individual losses are in $[0,1]$: $\forall t\,i,\; 0 \le \ell_t(i) \le 1$.
- Used by 1
- 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…
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.
set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The loss sequence induced by a game and a column-action sequence is a valid Hedge loss sequence: every loss `1 − A(i, j_t)` lies in `[0, 1]`, because payoffs do. [FS99, §§2–3]; [CBL06, proof of Thm 7.1]. -/lemma ZeroSumGame.toLossSeq_valid {M N T : ℕ} (G : ZeroSumGame M N) (colResponse : Fin T → Fin N) : (G.toLossSeq colResponse).Valid := by -- Payoffs in `[0,1]` make `1 - payoff` a valid Hedge loss. intro t i; simp only [ZeroSumGame.toLossSeq] exact ⟨by linarith [G.payoff_le_one i (colResponse t)], by linarith [G.payoff_nonneg i (colResponse t)]⟩