AFTD Auto-Formalizing Theoretical Domains

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.
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

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