OnlineLearning.finiteLowerValue_le_upperValue
theoremverifiedimported Lean
Weak duality for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M \geq 1$ row actions and $N \geq 1$ column actions, given by a payoff matrix $A_{ij} \in [0,1]$ that the row player seeks to maximise and the column player to minimise. Then the lower value never exceeds the upper value: \[ \sup_{p \in \Delta_M}\; \min_{j}\; \sum_{i} p_i A_{ij} \;\;\leq\;\; \inf_{q \in \Delta_N}\; \max_{i}\; \sum_{j} A_{ij} q_j, \] where $\Delta_M$ and $\Delta_N$ denote the sets of mixed strategies (probability distributions) over the row and column actions, respectively.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open Real Finset BigOperators in lemma OnlineLearning.finiteLowerValue_le_upperValue {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N) : finiteLowerValue G ≤ finiteUpperValue G
- Source
- TCSlib, `OnlineLearning.finiteLowerValue_le_upperValue`
- 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.finiteLowerValue_le_upperValue← OnlineLearning.finiteLowerValue_le_upperValue (TCSlib/LearningTheory/Minimax/ConvexMinimaxCore.lean:153): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- weak_dualityWeak duality for finite zero-sum games. Let $G$ be a finite two-player zero-sum game with $M \ge 1$ row actions and $N \ge 1$ column…
- OnlineLearning.finiteLowerValueFor a finite zero-sum game $G$ with $M$ row actions and $N$ column actions, the lower value is…
- OnlineLearning.finiteUpperValueThe upper value of $G$ is \[ v^+(G) \;=\; \inf_{q \in \Delta_N}\; \sup_{i \in [M]}\; \mathrm{pureVsPayoff}(G,i,q), \] where the…
- ZeroSumGameA finite two-player zero-sum game with $M$ row actions and $N$ column actions is a record consisting of a payoff matrix…
- OnlineLearning.mixedStrategyNonemptyThe mixed-strategy space is nonempty whenever the underlying action set is nonempty.
- 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/-- Weak duality for finite games: the lower value is always at most the upper value. -/lemma OnlineLearning.finiteLowerValue_le_upperValue {M N : ℕ} [NeZero M] [NeZero N] (G : ZeroSumGame M N) : finiteLowerValue G ≤ finiteUpperValue G := by unfold finiteLowerValue finiteUpperValue apply ciSup_le intro p apply le_ciInf intro q exact weak_duality G p q