Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 5.2, Part IV, p. 23 — a strict equilibrium is a pure profile (α*_1, …, α*_N) with δ_k = min_µ {v_{kα*}(x*) − v_{kµ}(x*)} > 0

Proved
ReinfRegGames.StrictStable.strict_nash_pure

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

learning-in-gamesnash-equilibriump2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strict-equilibrium

Let G\mathcal GG be a finite game with a finite set N\mathcal NN of players; player kkk has a finite set Ak\mathcal A_kAk​ of pure strategies and payoff function uk:∏ℓAℓ→Ru_k:\prod_\ell \mathcal A_\ell\to\mathbb Ruk​:∏ℓ​Aℓ​→R. A mixed profile x=(x1,…,xN)x=(x_1,\dots,x_N)x=(x1​,…,xN​) is an element of X=∏kΔ(Ak)\mathcal X=\prod_k\Delta(\mathcal A_k)X=∏k​Δ(Ak​), and uk(x)u_k(x)uk​(x) is player kkk's expected payoff (2.1) when the players randomize independently. vkα(x)=uk(α;x−k)v_{k\alpha}(x)=u_k(\alpha;x_{-k})vkα​(x)=uk​(α;x−k​) is the payoff of the pure strategy α∈Ak\alpha\in\mathcal A_kα∈Ak​ against x−kx_{-k}x−k​ (2.2).

Let x∗x^*x∗ be a strict Nash equilibrium of G\mathcal GG. Then for every player kkk there is a pure strategy αk∗∈Ak\alpha_k^*\in\mathcal A_kαk∗​∈Ak​ with xk∗=eαk∗x^*_k=e_{\alpha^*_k}xk∗​=eαk∗​​ (the vertex of Δ(Ak)\Delta(\mathcal A_k)Δ(Ak​) at αk∗\alpha^*_kαk∗​), and

vkμ(x∗)<vkαk∗(x∗)for every μ∈Ak∖{αk∗},v_{k\mu}(x^*)<v_{k\alpha^*_k}(x^*)\qquad\text{for every }\mu\in\mathcal A_k\setminus\{\alpha^*_k\},vkμ​(x∗)<vkαk∗​​(x∗)for every μ∈Ak​∖{αk∗​},

so that δk=min⁡μ≠αk∗{vkαk∗(x∗)−vkμ(x∗)}>0\delta_k=\min_{\mu\neq\alpha^*_k}\{v_{k\alpha^*_k}(x^*)-v_{k\mu}(x^*)\}>0δk​=minμ=αk∗​​{vkαk∗​​(x∗)−vkμ​(x∗)}>0.

The proof of Part IV of Theorem 5.2 starts by writing x∗=(α1∗,…,αN∗)x^*=(\alpha^*_1,\dots,\alpha^*_N)x∗=(α1∗​,…,αN∗​) and uses the positive gaps δk\delta_kδk​ to show that the relative scores zkμ=ykμ−ykαk∗z_{k\mu}=y_{k\mu}-y_{k\alpha^*_k}zkμ​=ykμ​−ykαk∗​​ decrease linearly near x∗x^*x∗.

Formalization Note The page asserts both facts in passing ("let x∗=(α1∗,…,αN∗)x^*=(\alpha^*_1,\dots,\alpha^*_N)x∗=(α1∗​,…,αN∗​) be a strict equilibrium", "δk=⋯>0\delta_k=\dots>0δk​=⋯>0"); here they are stated as a lemma about the definition of strict equilibrium, which does not build purity in. The minimum over Ak∖{αk∗}\mathcal A_k\setminus\{\alpha^*_k\}Ak​∖{αk∗​} is stated as a strict inequality for every μ≠αk∗\mu\ne\alpha^*_kμ=αk∗​, which is equivalent on a finite set and avoids an empty minimum when ∣Ak∣=1|\mathcal A_k|=1∣Ak​∣=1.

Preamble
import Mathlib
import Definitions.Def_agt_games
import Definitions.Def_ReinfRegGames_Extinction_Model
import Definitions.Def_ReinfRegGames_StrictStable_Stability
Formal statement
namespace ReinfRegGames.StrictStable

theorem strict_nash_pure {ι : Type*} [Fintype ι] [DecidableEq ι] {A : ι → Type*}
    [∀ k, Fintype (A k)] [∀ k, DecidableEq (A k)]
    (u : ι → (∀ k, A k) → ℝ)
    (xstar : ∀ k, A k → ℝ) (hstrict : IsStrictNash u xstar) :
    ∀ k, ∃ αstar : A k, xstar k = Pi.single αstar 1 ∧
      ∀ μ : A k, μ ≠ αstar → ReinfRegGames.Extinction.payoffVec u xstar k μ < ReinfRegGames.Extinction.payoffVec u xstar k αstar := by sorry

end ReinfRegGames.StrictStable
Source
Mertikopoulos & Sandholm, Learning in games via reinforcement and regularization, arXiv:1407.6267v2, p. 23, proof of Theorem 5.2, Part IV ("let x* = (α*_1, …, α*_N) be a strict equilibrium", "δ_k = min … > 0")
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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