p. 26 — in a Nash equilibrium every pure strategy earns at most the equilibrium payoff, with equality on the support
ProvedFixpNash.Blocks.support_propertyLet be a finite game in normal form and let be a mixed Nash equilibrium of : each is a probability distribution on , and no player can increase their expected payoff by unilaterally switching to another mixed strategy. Write for the expected payoff of player under and for the expected payoff of player when they play the pure strategy and the other players play according to . Then for every player and every ,
This is the elementary support characterization of Nash equilibria. Etessami and Yannakakis state it on p. 26 (proof of Lemma 7) for the two players of Bubelis's gadget, and use it twice in the proof of Lemma 6 (p. 24): to show that the matching player avoids the most probable blocks, and that player puts no probability on strategies with a low payoff.
Formalization Note. The paper's sentence speaks of players 2 and 3 of a specific game; the statement here is the same fact for every player of every finite game, which is the form in which the proof of Lemma 6 uses it. "In the support of " is read as . The quantity is DGPNash.NashMap.purePayoff.
import Mathlib import Definitions.Def_agt_games import Definitions.Def_DGPNash_NashMap_nashMap
namespace FixpNash.Blocks
/-- Support property of a mixed Nash equilibrium (Etessami–Yannakakis, p. 26, proof of
Lemma 7; used twice in the proof of Lemma 6, p. 24): in a Nash equilibrium `x` of a finite
game, the expected payoff `u_p((p:j); x_{-p})` of every pure strategy `j` of every player
`p` is at most `p`'s equilibrium payoff, with equality if `j` is in the support of `x`. -/
theorem support_property {ι : Type*} [Fintype ι] [DecidableEq ι]
{S : ι → Type*} [∀ k, Fintype (S k)] [∀ k, DecidableEq (S k)]
(u : ι → (∀ k, S k) → ℝ) (x : ∀ k, S k → ℝ) (hx : AGT.IsMixedNash u x)
(p : ι) (j : S p) :
DGPNash.NashMap.purePayoff u x p j ≤ AGT.expectedPayoff u x p ∧
(0 < x p j → DGPNash.NashMap.purePayoff u x p j = AGT.expectedPayoff u x p) := by sorry
end FixpNash.Blocks
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.