Theorem 5.2, Part IV, p. 22 — under (RL), every strict Nash equilibrium is asymptotically stable
ProvedReinfRegGames.StrictStable.theorem_5_2_ivLet be a finite game with a finite set of players; player has a finite set of pure strategies and payoff function . A mixed profile is an element of , and is player 's expected payoff (2.1) when the players randomize independently. is the payoff of the pure strategy against (2.2). Every player has a penalty function on in the sense of Definition 2.1 (continuous on the simplex, smooth on the relative interior of every face, -strongly convex), with choice map (2.8). An orbit of (RL) is a pair of trajectories , , , with .
Theorem (Part IV). If is a strict Nash equilibrium of , then is asymptotically stable under (RL): it is Lyapunov stable — for every there is such that every orbit with satisfies for all — and attracting — there is such that every orbit with satisfies
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 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 is existential in Definition 2.1 the class of penalty functions does not depend on this choice, but the constant does. (RL) is encoded in its differential form (3.1): maximizes over the simplex and has right derivative at every (one-sided at ); since is continuous along an orbit, this is equivalent to the integral form (RL) on p. 7. Neighbourhoods of in are encoded by balls of the sup metric on ; every lies in , so these balls intersected with are exactly the relative neighbourhoods, and the "for every neighbourhood there is a neighbourhood " of Definition 5.1 is the equivalent – form. No steepness, no decomposability and no assumption is made (the latter appears only in Part I).
import Mathlib import Definitions.Def_agt_games import Definitions.Def_ReinfRegGames_Extinction_Model import Definitions.Def_ReinfRegGames_StrictStable_Stability
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.