§8.1, p. 135 — β and α are attained minimum and maximum
ProvedMatousekLP.ZeroSum.minimum_attainedLet be a real payoff matrix with , and let , be the worst-case payoff functions of the zero-sum game . Then for every mixed strategy of Alice the value is attained by some mixed strategy of Bob, and for every mixed strategy of Bob the value is attained by some mixed strategy of Alice:
Precisely: is a lower bound of all values over mixed and equals one of them, and symmetrically for .
This is the book's remark that and are well-defined because the optimization is over compact sets (the simplices of mixed strategies).
Formalization Note and are defined as the real sInf / sSup of the image of the simplex; this theorem is what makes those definitions agree with the book's and . The hypotheses are the book's standing assumption; without them a simplex is empty.
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game
namespace MatousekLP.ZeroSum
theorem minimum_attained {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n) (M : Matrix (Fin m) (Fin n) ℝ) :
(∀ x ∈ stdSimplex ℝ (Fin m),
IsLeast ((fun y => payoff M x y) '' stdSimplex ℝ (Fin n)) (beta M x)) ∧
(∀ y ∈ stdSimplex ℝ (Fin n),
IsGreatest ((fun x => payoff M x y) '' stdSimplex ℝ (Fin m)) (alpha M y)) := by sorry
end MatousekLP.ZeroSum
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.