Theorem 8.1.3 — minimax theorem for zero-sum games
ProvedMatousekLP.ZeroSum.minimax_theoremLet be a real payoff matrix of a zero-sum game between Alice ( pure strategies) and Bob ( pure strategies), and let and , the optima being over mixed strategies. Then:
- Alice has a worst-case optimal mixed strategy , i.e. ;
- Bob has a worst-case optimal mixed strategy , i.e. ;
- if is any worst-case optimal mixed strategy of Alice and any worst-case optimal mixed strategy of Bob, then is a mixed Nash equilibrium;
- there is a real number such that for all worst-case optimal mixed strategies of Alice and of Bob
The number is the value of the game. The theorem says that "prepare for the worst" is an optimal policy in a zero-sum game: against a worst-case optimal strategy of the opponent, no player can do better than the value.
Formalization Note The book's clause that worst-case optimal strategies "can be efficiently computed by linear programming" is algorithmic and is not part of the formal statement. Clause 4 expresses "the number is the same for all possible worst-case optimal mixed strategies" as a single chosen before the strategies. The hypotheses are the book's standing assumption of §8.1.
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game
namespace MatousekLP.ZeroSum
theorem minimax_theorem {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) :
(∃ xt : Fin m → ℝ, IsWorstCaseOptimalAlice M xt) ∧
(∃ yt : Fin n → ℝ, IsWorstCaseOptimalBob M yt) ∧
(∀ (xt : Fin m → ℝ) (yt : Fin n → ℝ), IsWorstCaseOptimalAlice M xt →
IsWorstCaseOptimalBob M yt → IsMixedNash M xt yt) ∧
∃ v : ℝ, ∀ (xt : Fin m → ℝ) (yt : Fin n → ℝ), IsWorstCaseOptimalAlice M xt →
IsWorstCaseOptimalBob M yt →
beta M xt = v ∧ payoff M xt yt = v ∧ alpha M yt = v := by sorry
end MatousekLP.ZeroSum
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.