Eq. (8.3) — an optimal solution of (8.2) is a worst-case optimal strategy of Alice
ProvedMatousekLP.ZeroSum.lp82_optimallinear-programmingp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix, , and consider the linear program (8.2)
If is an optimal solution of (8.2), then is a mixed strategy of Alice and
the maximum being over all mixed strategies of Alice. 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 lp82_optimal {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) (x₀ : ℝ) (xt : Fin m → ℝ) (h : LP82Optimal M x₀ xt) :
x₀ = beta M xt ∧ xt ∈ stdSimplex ℝ (Fin m) ∧
∀ x ∈ stdSimplex ℝ (Fin m), beta M x ≤ beta M xt := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 138, Eq. (8.2) and Eq. (8.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.