(16:C) — theorem of the alternative for matrices (strict form)
ProvedTheoryOfGames.Minimax.alternative_strictconvexitygame-theoryp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1theorem-of-the-alternative
Let , , , be a real matrix with rows and columns, and let denote the simplex of probability vectors in . Then exactly one of the following holds:
- (16:16:a) there is with
- (16:16:b) there is with
The existence of one of the two alternatives is (16:C); that they exclude each other is the observation stated immediately after it. This is the convexity result from which the book derives the minimax theorem (via (16:F)).
Formalization Note Rows and columns are indexed from (Fin n, Fin m). "Exactly one" is Xor of the two existence statements.
Preamble
import Mathlib
Formal statement
namespace TheoryOfGames.Minimax
/-- (16:C), p. 140, with the observation after it: for a real matrix `a(i, j)` with `n ≥ 1`
rows and `m ≥ 1` columns, exactly one of the following holds: there is `x ∈ S_m` with
`∑_j a(i, j) x_j ≤ 0` for every row `i` (16:16:a), or there is `w ∈ S_n` with
`∑_i a(i, j) w_i > 0` for every column `j` (16:16:b). -/
theorem alternative_strict {n m : ℕ} (hn : 0 < n) (hm : 0 < m) (a : Fin n → Fin m → ℝ) :
Xor (∃ x ∈ stdSimplex ℝ (Fin m), ∀ i, ∑ j, a i j * x j ≤ 0)
(∃ w ∈ stdSimplex ℝ (Fin n), ∀ j, 0 < ∑ i, a i j * w i) := by sorry
end TheoryOfGames.Minimax
Source
von Neumann & Morgenstern, Theory of Games and Economic Behavior (60th-anniversary ed., Princeton 2007), p. 140, (16:C) and the following observation
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.