ZeroSumGame.toLossSeq
defimported Lean
Given a game $G$ and a sequence of column responses $j_0, \dots, j_{T-1}$, the induced loss sequence for the row player is $\ell_t(i) = 1 - A_{i,j_t} \in [0,1]$. This translates a zero-sum game into the abstract loss-sequence framework used by Hedge.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in noncomputable def ZeroSumGame.toLossSeq {M N T : ℕ} (G : ZeroSumGame M N) (colResponse : Fin T → Fin N) : LossSeq M T
- Defined in
- TCSlib, `ZeroSumGame.toLossSeq`
- 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← ZeroSumGame.toLossSeq (TCSlib/LearningTheory/Minimax/HedgeInteraction.lean:67): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 2
- ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
- LossSeqA loss sequence $\ell$ for $N$ experts over $T$ rounds is a function $\ell : \mathrm{Fin}\,T \to \mathrm{Fin}\,N \to \mathbb{R}$,…
- Used by 7
- 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…
- 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…
- 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$…
- 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…
- 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…
- 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,…
- 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…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in /-- The loss sequence induced by a game and a sequence of column actions `j_t`: the loss of row `i` at round `t` is `1 − A(i, j_t)`, so that low loss means high payoff. [FS99, §§2–3 (there `M(i, j)` is already the row player's loss and the row player minimizes)]; [CBL06, proof of Thm 7.1]. Deviation: payoffs/row-maximizer convention, so the Hedge loss is `1 − A(i, j_t)`. -/ noncomputable def ZeroSumGame.toLossSeq {M N T : ℕ} (G : ZeroSumGame M N) (colResponse : Fin T → Fin N) : LossSeq M T := fun t i => 1 - G.payoff i (colResponse t)