Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.2, Part IV, p. 22 — under (RL), every strict Nash equilibrium is asymptotically stable

Proved
ReinfRegGames.StrictStable.theorem_5_2_iv

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

asymptotic-stabilitylearning-in-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reinforcement-learningstrict-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). Every player kkk has a penalty function hkh_khk​ on Δ(Ak)\Delta(\mathcal A_k)Δ(Ak​) in the sense of Definition 2.1 (continuous on the simplex, smooth on the relative interior of every face, KkK_kKk​-strongly convex), with choice map Qk(yk)=arg⁡max⁡xk∈Δ(Ak){⟨yk∣xk⟩−hk(xk)}Q_k(y_k)=\arg\max_{x_k\in\Delta(\mathcal A_k)}\{\langle y_k|x_k\rangle-h_k(x_k)\}Qk​(yk​)=argmaxxk​∈Δ(Ak​)​{⟨yk​∣xk​⟩−hk​(xk​)} (2.8). An orbit of (RL) is a pair of trajectories y(t)y(t)y(t), x(t)=Q(y(t))x(t)=Q(y(t))x(t)=Q(y(t)), t≥0t\ge0t≥0, with y˙kα=vkα(x)\dot y_{k\alpha}=v_{k\alpha}(x)y˙​kα​=vkα​(x).

Theorem (Part IV). If x∗x^*x∗ is a strict Nash equilibrium of G\mathcal GG, then x∗x^*x∗ is asymptotically stable under (RL): it is Lyapunov stable — for every ε>0\varepsilon>0ε>0 there is δ>0\delta>0δ>0 such that every orbit with ∥x(0)−x∗∥<δ\|x(0)-x^*\|<\delta∥x(0)−x∗∥<δ satisfies ∥x(t)−x∗∥<ε\|x(t)-x^*\|<\varepsilon∥x(t)−x∗∥<ε for all t≥0t\ge0t≥0 — and attracting — there is δ>0\delta>0δ>0 such that every orbit with ∥x(0)−x∗∥<δ\|x(0)-x^*\|<\delta∥x(0)−x∗∥<δ satisfies

lim⁡t→∞x(t)=x∗.\lim_{t\to\infty}x(t)=x^*.t→∞lim​x(t)=x∗.

This is the regularized-learning analogue of the classical fact that strict equilibria are asymptotically stable under the replicator dynamics. It holds for every choice of penalty functions, steep or not; in the steep case x∗x^*x∗ is never reached, while in the nonsteep case (e.g. the projection dynamics) it may be reached in finite time.

Formalization Note The norm in the strong convexity inequality (2.5) is the Euclidean one; the page leaves it unspecified, and since KKK is existential in Definition 2.1 the class of penalty functions does not depend on this choice, but the constant KKK does. (RL) is encoded in its differential form (3.1): xk(t)x_k(t)xk​(t) maximizes ⟨yk(t)∣⋅⟩−hk\langle y_k(t)|\cdot\rangle-h_k⟨yk​(t)∣⋅⟩−hk​ over the simplex and ykαy_{k\alpha}ykα​ has right derivative vkα(x(t))v_{k\alpha}(x(t))vkα​(x(t)) at every t≥0t\ge0t≥0 (one-sided at t=0t=0t=0); since x=Q(y)x=Q(y)x=Q(y) is continuous along an orbit, this is equivalent to the integral form (RL) on p. 7. Neighbourhoods of x∗x^*x∗ in X\mathcal XX are encoded by balls of the sup metric on ∏kRAk\prod_k\mathbb R^{\mathcal A_k}∏k​RAk​; every x(t)x(t)x(t) lies in X\mathcal XX, so these balls intersected with X\mathcal XX are exactly the relative neighbourhoods, and the "for every neighbourhood UUU there is a neighbourhood VVV" of Definition 5.1 is the equivalent ε\varepsilonε–δ\deltaδ form. No steepness, no decomposability and no assumption x∗∈im⁡Qx^*\in\operatorname{im}Qx∗∈imQ is made (the latter appears only in Part I).

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 theorem_5_2_iv {ι : Type*} [Fintype ι] [DecidableEq ι] {A : ι → Type*}
    [∀ k, Fintype (A k)] [∀ k, DecidableEq (A k)]
    (u : ι → (∀ k, A k) → ℝ) (h : ∀ k, (A k → ℝ) → ℝ) (K : ι → ℝ)
    (hpen : ∀ k, ReinfRegGames.Extinction.IsPenalty (h k) (K k))
    (xstar : ∀ k, A k → ℝ) (hstrict : IsStrictNash u xstar) :
    IsAsymptoticallyStable u h xstar := by sorry

end ReinfRegGames.StrictStable
Source
Mertikopoulos & Sandholm, Learning in games via reinforcement and regularization, arXiv:1407.6267v2, p. 22, Theorem 5.2, Part IV (proof pp. 23–24); Definition 5.1, p. 21
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