Proof of Lemma 7, p. 26 — if , every Nash equilibrium of has
ProvedFixpNash.Bubelis.aux3_uniformgame-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real polynomial with and which has a unique root in , and let be the gadget of Lemma 7. Suppose . Then in every mixed Nash equilibrium of the auxiliary player 3 plays the uniform strategy:
Together with the strategies of players 1 and 2 forced earlier in the proof, this determines the whole equilibrium, which is the uniqueness half of Lemma 7.
Formalization Note The root is a named parameter with the hypothesis , , and for every root of .
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_Bubelis_Gadget
Formal statement
namespace FixpNash.Bubelis
/-- Proof of Lemma 7, p. 26: let `f` satisfy `f(0) ≤ 0`, `f(1) ≥ 0` and have the unique root `α`
in `[0, 1]`. If `α ≠ 0`, then in every Nash equilibrium `x` of the gadget `G_f` player 3 plays
the uniform strategy `x₃(j) = 1/(m + 1)`, `j = 0, …, m`. -/
theorem aux3_uniform {m : ℕ} (c : Fin (m + 1) → ℝ)
(hf0 : poly c 0 ≤ 0) (hf1 : 0 ≤ poly c 1) (α : ℝ)
(hα : 0 ≤ α ∧ α ≤ 1 ∧ poly c α = 0 ∧
∀ β : ℝ, 0 ≤ β → β ≤ 1 → poly c β = 0 → β = α)
(hα0 : α ≠ 0) (x : ∀ p, Strat m p → ℝ) (hx : AGT.IsMixedNash (gadget c) x)
(j : Fin (m + 1)) :
x .aux3 j = 1 / ((m : ℝ) + 1) := by sorry
end FixpNash.Bubelis
Source
Etessami & Yannakakis, On the complexity of Nash equilibria and other fixed points, author manuscript (SIAM J. Comput. 39 (2010)), proof of Lemma 7, p. 26
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.