AFTD Auto-Formalizing Theoretical Domains

OnlineLearning.finiteUpperValue_bddBelow

theoremverifiedimported Lean

Lower 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 actions, whose payoff matrix $A$ satisfies $A_{ij} \in [0,1]$ for all $i,j$. For a mixed column strategy $q$ (a probability distribution on the $N$ columns), let \[ v(q) \;=\; \sup_{i}\, \sum_{j} A_{ij}\, q_j \] be the best expected payoff that a single pure row can achieve against $q$. Then the set $\{\, v(q) : q \text{ a mixed column strategy}\,\}$ is bounded below.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open Real Finset BigOperators in
lemma OnlineLearning.finiteUpperValue_bddBelow {M N : ℕ} [NeZero M] (G : ZeroSumGame M N) :
    BddBelow (Set.range fun q : MixedStrategy N => ⨆ i : Fin M, pureVsPayoff G i q)
Source
TCSlib, `OnlineLearning.finiteUpperValue_bddBelow`
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 5
  • 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,…
  • pureVsPayoffGiven a game $G$, a pure row $i$, and a mixed column strategy $q$, the expected payoff of row $i$ against $q$ is…
  • MixedStrategyA mixed strategy over $n$ actions is a record consisting of a weight function $w : \mathrm{Fin}\,n \to \mathbb{R}$ together with…
  • ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
  • 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…
Used by 1
  • 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…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen Real Finset BigOperators in/-- The set of column-induced finite-game upper values is bounded below by zero. -/lemma OnlineLearning.finiteUpperValue_bddBelow {M N : ℕ} [NeZero M] (G : ZeroSumGame M N) :    BddBelow (Set.range fun q : MixedStrategy N => ⨆ i : Fin M, pureVsPayoff G i q) := by  refine ⟨0, ?_⟩  rintro _ ⟨q, rfl⟩  have hbdd : BddAbove (Set.range (fun i : Fin M => pureVsPayoff G i q)) :=    ⟨1, by rintro _ ⟨i, rfl⟩; exact pureVsPayoff_le_one G i q⟩  exact (pureVsPayoff_nonneg G (Classical.choice inferInstance) q).trans    (le_ciSup hbdd (Classical.choice inferInstance))
See it in the graphDiscuss this resultChallenge it