AFTD Auto-Formalizing Theoretical Domains

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.
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)
See it in the graphDiscuss this resultChallenge it