§8.1, p. 138 — the linear programs (8.2) and (8.4) have the same optimum value
ProvedMatousekLP.ZeroSum.lp82_lp84_same_optimumlinear-programminglp-dualityp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix, . The linear programs (8.2) (maximize subject to , , ) and (8.4) (minimize subject to , , ) are dual to each other, and they have the same optimum value:
- (8.2) has an optimal solution;
- (8.4) has an optimal solution;
- for every optimal solution of (8.2) and every optimal solution of (8.4),
This is the point at which the duality theorem of linear programming enters the proof of the minimax theorem.
Formalization Note "Both programs have the same optimum value" is rendered as the existence of optimal solutions of both programs together with the equality of their objective values; no real supremum over a feasible set is used.
Preamble
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game import Definitions.Def_MatousekLP_ZeroSum_GameLP
Formal statement
namespace MatousekLP.ZeroSum
theorem lp82_lp84_same_optimum {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) :
(∃ (x₀ : ℝ) (x : Fin m → ℝ), LP82Optimal M x₀ x) ∧
(∃ (y₀ : ℝ) (y : Fin n → ℝ), LP84Optimal M y₀ y) ∧
∀ (x₀ : ℝ) (x : Fin m → ℝ) (y₀ : ℝ) (y : Fin n → ℝ),
LP82Optimal M x₀ x → LP84Optimal M y₀ y → x₀ = y₀ := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 138, §8.1, proof of Theorem 8.1.3 ("the two linear programs (8.2) and (8.4) are dual to each other … both programs have the same optimum value")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.