§8.1, p. 137 — the dual of (8.1) has optimal value β(x)
ProvedMatousekLP.ZeroSum.dual81_valuelinear-programminglp-dualityp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix, , and let be a mixed strategy of Alice. The value is the optimal value of the linear program (8.1): minimize subject to , . Its dual is the one-variable program
and its optimal value is again : the number is feasible for this dual program, and every feasible satisfies .
This identity is what allows the maximization of the nonlinear function over Alice's mixed strategies to be written as the linear program (8.2).
Formalization Note "Optimal value" is stated as IsGreatest of the feasible set of the dual program, so the statement includes that the maximum is attained.
Preamble
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game import Definitions.Def_MatousekLP_ZeroSum_GameLP
Formal statement
namespace MatousekLP.ZeroSum
theorem dual81_value {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) (x : Fin m → ℝ) (hx : x ∈ stdSimplex ℝ (Fin m)) :
IsGreatest {x₀ : ℝ | DualLP81Feasible M x x₀} (beta M x) := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 137, §8.1, proof of Theorem 8.1.3 (the dual of the linear program (8.1))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.