§8.1, p. 137 — max_x min_y xᵀMy = min_y max_x xᵀMy
ProvedMatousekLP.ZeroSum.minimax_equalitygame-theoryminimaxp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix of a zero-sum game with . Then
where ranges over the mixed strategies of Alice and over those of Bob. Both outer optima are attained: there is a number that is the largest value of over mixed and the smallest value of over mixed .
This equality is what gives the minimax theorem its name.
Formalization Note Stated as: there is that is the greatest element of and the least element of , over mixed strategies.
Preamble
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game
Formal statement
namespace MatousekLP.ZeroSum
theorem minimax_equality {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) :
∃ v : ℝ, IsGreatest (beta M '' stdSimplex ℝ (Fin m)) v ∧
IsLeast (alpha M '' stdSimplex ℝ (Fin n)) v := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 137, §8.1 (display after Theorem 8.1.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.