AFTD Auto-Formalizing Theoretical Domains

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

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