Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

p. 26 — in a Nash equilibrium every pure strategy earns at most the equilibrium payoff, with equality on the support

Proved
FixpNash.Blocks.support_property

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

game-theorynash-equilibriump2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1support

Let uuu be a finite game in normal form and let xxx be a mixed Nash equilibrium of uuu: each xpx_pxp​ is a probability distribution on SpS_pSp​, and no player can increase their expected payoff by unilaterally switching to another mixed strategy. Write up(x)u_p(x)up​(x) for the expected payoff of player ppp under xxx and up((p:j);x−p)u_p((p{:}j);x_{-p})up​((p:j);x−p​) for the expected payoff of player ppp when they play the pure strategy jjj and the other players play according to xxx. Then for every player ppp and every j∈Spj\in S_pj∈Sp​,

up((p:j);x−p)≤up(x),with equality if xp(j)>0.u_p((p{:}j);x_{-p})\le u_p(x),\qquad\text{with equality if } x_p(j)>0 .up​((p:j);x−p​)≤up​(x),with equality if xp​(j)>0.

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 i′i'i′ avoids the most probable blocks, and that player iii 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 xxx" is read as xp(j)>0x_p(j)>0xp​(j)>0. The quantity up((p:j);x−p)u_p((p{:}j);x_{-p})up​((p:j);x−p​) is DGPNash.NashMap.purePayoff.

Preamble
import Mathlib
import Definitions.Def_agt_games
import Definitions.Def_DGPNash_NashMap_nashMap
Formal statement
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
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 (used in the proof of Lemma 6, p. 24)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me