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.OnlineLearning.finiteUpperValue_bddBelow← OnlineLearning.finiteUpperValue_bddBelow (TCSlib/LearningTheory/Minimax/ConvexMinimaxCore.lean:142): verbatim
- 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
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 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))