Lemma 8.1.2(i) — β(x) ≤ xᵀMy ≤ α(y), hence max β ≤ min α
ProvedMatousekLP.ZeroSum.weak_minimaxgame-theoryp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix of a zero-sum game, , and let and . Then
- for all mixed strategies of Alice and of Bob, that is, ;
- for every two mixed strategies and ,
This is the game-theoretic analogue of weak LP duality; the minimax theorem upgrades part 1 to an equality.
Formalization Note The book's is stated as for all mixed , which is equivalent and does not presuppose that the maximum and minimum exist.
Preamble
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game
Formal statement
namespace MatousekLP.ZeroSum
theorem weak_minimax {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n) (M : Matrix (Fin m) (Fin n) ℝ) :
(∀ x ∈ stdSimplex ℝ (Fin m), ∀ y ∈ stdSimplex ℝ (Fin n), beta M x ≤ alpha M y) ∧
(∀ x ∈ stdSimplex ℝ (Fin m), ∀ y ∈ stdSimplex ℝ (Fin n),
beta M x ≤ payoff M x y ∧ payoff M x y ≤ alpha M y) := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 135, Lemma 8.1.2(i)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.