Proof of Lemma 7, p. 26 — in every Nash equilibrium of , with
ProvedFixpNash.Bubelis.aux2_strategygame-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the gadget of Lemma 7 for coefficients (no hypothesis on is needed), let be a mixed Nash equilibrium of , and let be the probability the primary player puts on its strategy . Then for every ,
where for all , including .
The strategy of player 2 is thus determined by that of the primary player; this is how the gadget turns the probability into the values of the polynomial .
Formalization Note The exponent is natural-number subtraction, exact since ; Lean's convention is the paper's. The denominator is at least since . The root hypotheses of Lemma 7 are not needed and are omitted.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_FixpNash_Bubelis_Gadget
Formal statement
namespace FixpNash.Bubelis
open Finset
/-- Proof of Lemma 7, p. 26: in every Nash equilibrium `x` of the gadget `G_f`, writing
`ξ = x₁(0)`, player 2 plays `x₂(j) = ξ^(m-j) / ∑_{i=0}^m ξ^i` for every `j = 0, …, m`
(with `ξ^0 = 1`, also for `ξ = 0`). -/
theorem aux2_strategy {m : ℕ} (c : Fin (m + 1) → ℝ) (x : ∀ p, Strat m p → ℝ)
(hx : AGT.IsMixedNash (gadget c) x) (j : Fin (m + 1)) :
x .aux2 j = x .primary 0 ^ (m - (j : ℕ)) / ∑ i ∈ range (m + 1), x .primary 0 ^ i := 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.