Proof of Lemma 7, p. 26 — in every Nash equilibrium of ,
ProvedFixpNash.Bubelis.primary_payoff_onegame-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial
Let be the gadget of Lemma 7 for coefficients and (no hypothesis on is needed), let be a mixed Nash equilibrium of and . Then the expected payoff of the pure strategy of the primary player, against the strategies of the others, is
Since the pure strategy of player 1 always earns , the sign of decides which strategy the primary player prefers; this is what pins to a root of .
Formalization Note is DGPNash.NashMap.purePayoff (gadget c) x primary 1. The root hypotheses of Lemma 7 are not needed and are omitted.
Preamble
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap 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)`, the expected payoff of the pure strategy 1 of the primary player is
`u₁((1:1); x₋₁) = f(ξ) / ∑_{i=0}^m ξ^i`. -/
theorem primary_payoff_one {m : ℕ} (c : Fin (m + 1) → ℝ) (x : ∀ p, Strat m p → ℝ)
(hx : AGT.IsMixedNash (gadget c) x) :
DGPNash.NashMap.purePayoff (gadget c) x .primary 1 =
poly c (x .primary 0) / ∑ 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.