Lemma 8.1.2(ii) — both strategies of a mixed Nash equilibrium are worst-case optimal
ProvedMatousekLP.ZeroSum.nash_worstCaseOptimalgame-theorynash-equilibriump2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix of a zero-sum game, . If the pair of mixed strategies is a mixed Nash equilibrium ( is a best response against and is a best response against ), then is worst-case optimal for Alice and is worst-case optimal for Bob:
Together with the minimax theorem this gives: a pair of mixed strategies is a Nash equilibrium if and only if both strategies are worst-case optimal.
Formalization Note Worst-case optimality of is stated as: is a mixed strategy and for every mixed strategy ; symmetrically for .
Preamble
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game
Formal statement
namespace MatousekLP.ZeroSum
theorem nash_worstCaseOptimal {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) (xt : Fin m → ℝ) (yt : Fin n → ℝ)
(h : IsMixedNash M xt yt) :
IsWorstCaseOptimalAlice M xt ∧ IsWorstCaseOptimalBob M yt := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 136, Lemma 8.1.2(ii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.