Eq. (8.5) — an optimal solution of (8.4) is a worst-case optimal strategy of Bob
ProvedMatousekLP.ZeroSum.lp84_optimallinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix, , and consider the linear program (8.4)
If is an optimal solution of (8.4), then is a mixed strategy of Bob and
the minimum being over all mixed strategies of Bob. In particular is worst-case optimal.
Formalization Note is stated as for every mixed strategy .
Preamble
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game import Definitions.Def_MatousekLP_ZeroSum_GameLP
Formal statement
namespace MatousekLP.ZeroSum
theorem lp84_optimal {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) (y₀ : ℝ) (yt : Fin n → ℝ) (h : LP84Optimal M y₀ yt) :
y₀ = alpha M yt ∧ yt ∈ stdSimplex ℝ (Fin n) ∧
∀ y ∈ stdSimplex ℝ (Fin n), alpha M yt ≤ alpha M y := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 138, Eq. (8.4) and Eq. (8.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.