Lemma 8.1.2(iii) — β(x̃) = α(ỹ) implies a mixed Nash equilibrium
ProvedMatousekLP.ZeroSum.nash_of_beta_eq_alphagame-theorynash-equilibriump2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1zero-sum-games
Let be a real payoff matrix of a zero-sum game, . If mixed strategies of Alice and of Bob satisfy
then is a mixed Nash equilibrium: is a best response against and is a best response against .
This is the step that turns the equality of the optimal values of two dual linear programs into an equilibrium in the proof of the minimax theorem.
Preamble
import Mathlib import Definitions.Def_MatousekLP_ZeroSum_Game
Formal statement
namespace MatousekLP.ZeroSum
theorem nash_of_beta_eq_alpha {m n : ℕ} (hm : 1 ≤ m) (hn : 1 ≤ n)
(M : Matrix (Fin m) (Fin n) ℝ) (xt : Fin m → ℝ) (yt : Fin n → ℝ)
(hx : xt ∈ stdSimplex ℝ (Fin m)) (hy : yt ∈ stdSimplex ℝ (Fin n))
(h : beta M xt = alpha M yt) :
IsMixedNash M xt yt := by sorry
end MatousekLP.ZeroSum
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 136, Lemma 8.1.2(iii)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.