Lyapunov Functions and Stability: KL Divergence for the Replicator Dynamic

Table of Contents

• 1. Introduction
• 2. Lyapunov Stability Theory
  • 2.1 Equilibria and Stability Notions
  • 2.2 Lyapunov Functions and the Direct Method
  • 2.3 LaSalle’s Invariance Principle
• 3. The Replicator Dynamic
  • 3.1 Finite Symmetric Games and the Strategy Simplex
  • 3.2 The Replicator ODE
  • 3.3 Fixed Points
  • 3.4 Evolutionarily Stable Strategies
• 4. KL Divergence as a Lyapunov Function
  • 4.1 Setup and Statement
  • 4.2 Positivity of V
  • 4.3 Computing V-dot along Replicator Trajectories
  • 4.4 Signing V-dot via the ESS Inequality
  • 4.5 Asymptotic Stability Conclusion
• 5. Geometric Interpretation
• 6. References

1. Introduction 🎯

The central question of dynamical systems theory is: given a differential equation \(\dot{x} = f(x)\), do trajectories converge to a specific equilibrium? For nonlinear systems, linearization only tells a local story, and even that fails at non-hyperbolic equilibria. Lyapunov’s direct method sidesteps linearization entirely: rather than solving the ODE, one constructs an energy-like function \(V\) whose value decreases along every trajectory. Existence of such a function implies stability.

This note builds Lyapunov theory from scratch and applies it to a canonical example from evolutionary game theory. The main result we will prove is:

If \(\hat{x}\) is an evolutionarily stable strategy (ESS) of a finite symmetric game, then the relative entropy \(V(x) = D_{\mathrm{KL}}(\hat{x} \| x)\) is a Lyapunov function for the replicator dynamic, and \(\hat{x}\) is asymptotically stable.

The elegance here is not accidental. The KL divergence measures how far the population state \(x\) is from the ESS \(\hat{x}\) in an information-geometric sense — and the replicator dynamic turns out to be gradient flow with respect to the Fisher information metric on the simplex. The ESS condition is precisely the statement that the KL divergence is being minimized.

2. Lyapunov Stability Theory 📐

2.1 Equilibria and Stability Notions

Consider the autonomous ODE

\[\dot{x} = f(x), \qquad x \in \mathbb{R}^n, \quad f: U \to \mathbb{R}^n, \tag{2.1}\]

where \(U \subseteq \mathbb{R}^n\) is open and \(f\) is continuously differentiable. Denote the flow by \(\phi_t(x_0)\), i.e., the unique solution with \(\phi_0(x_0) = x_0\).

Definition 2.1 (Equilibrium). A point \(x^* \in U\) is an equilibrium (or rest point, or fixed point) of (2.1) if \(f(x^*) = 0\).

Without loss of generality, we translate so that \(x^* = 0\). This is purely notational — any equilibrium can be shifted to the origin.

Definition 2.2 (Lyapunov stability). The equilibrium \(x^* = 0\) is Lyapunov stable if for every \(\epsilon > 0\) there exists \(\delta > 0\) such that

\[\|x_0\| < \delta \implies \|\phi_t(x_0)\| < \epsilon \quad \text{for all } t \geq 0.\]

Definition 2.3 (Asymptotic stability). The equilibrium \(x^* = 0\) is asymptotically stable if it is Lyapunov stable and there exists \(\delta > 0\) such that

\[\|x_0\| < \delta \implies \phi_t(x_0) \to 0 \quad \text{as } t \to \infty.\]

Definition 2.4 (Global asymptotic stability). The equilibrium is globally asymptotically stable if it is Lyapunov stable and \(\phi_t(x_0) \to 0\) as \(t \to \infty\) for every \(x_0 \in U\).

2.2 Lyapunov Functions and the Direct Method 🔑

The key idea is to certify stability without solving the ODE. One finds a scalar function \(V\) that acts as a generalized energy: positive away from equilibrium, and non-increasing along trajectories.

Definition 2.5 (Lyapunov function). Let \(U \subseteq \mathbb{R}^n\) be a neighborhood of \(0\). A continuously differentiable function \(V: U \to \mathbb{R}\) is a Lyapunov function for (2.1) at \(x^* = 0\) if: 1. \(V(0) = 0\). 2. \(V(x) > 0\) for all \(x \in U \setminus \{0\}\) (positive definiteness). 3. \(\dot{V}(x) := \nabla V(x) \cdot f(x) \leq 0\) for all \(x \in U\) (non-increasing along trajectories).

If condition (3) holds with strict inequality (\(\dot{V}(x) < 0\) for \(x \neq 0\)), we call \(V\) a strict Lyapunov function.

Theorem 2.6 (Lyapunov’s Direct Method). Let \(V\) be a Lyapunov function for (2.1) on a neighborhood \(U\) of \(0\). 1. If \(\dot{V}(x) \leq 0\) for all \(x \in U\), then \(x^* = 0\) is Lyapunov stable. 2. If \(\dot{V}(x) < 0\) for all \(x \in U \setminus \{0\}\), then \(x^* = 0\) is asymptotically stable.

Proof sketch (Part 1 — Lyapunov stability). Let \(\epsilon > 0\) be small enough that \(B_\epsilon(0) \subseteq U\). Let \(c := \min_{\|x\| = \epsilon} V(x) > 0\) (the minimum over the sphere, which is positive by positive definiteness). The set \(\Omega_c := \{x \in B_\epsilon(0) : V(x) < c\}\) is open, contains \(0\), and is positively invariant: since \(\dot{V} \leq 0\), any trajectory starting in \(\Omega_c\) has non-increasing \(V\), hence can never exit through \(\partial B_\epsilon(0)\) (where \(V \geq c\)). Choose \(\delta\) so that \(B_\delta(0) \subseteq \Omega_c\). Then \(\|x_0\| < \delta\) implies \(\phi_t(x_0)\) stays in \(\Omega_c \subseteq B_\epsilon(0)\) for all \(t \geq 0\). \(\square\)

Proof sketch (Part 2 — asymptotic stability). Lyapunov stability follows from Part 1. For convergence: since \(V\) is non-increasing and bounded below by 0, the limit \(\ell := \lim_{t \to \infty} V(\phi_t(x_0)) \geq 0\) exists. If \(\ell > 0\), then \(\phi_t(x_0)\) stays in the compact region \(\{V \geq \ell\} \cap \overline{B_\epsilon(0)}\) away from \(0\), where \(\dot{V} \leq -\alpha < 0\) for some \(\alpha > 0\) (by compactness and strict negativity). But then \(V(\phi_t(x_0)) \to -\infty\), contradicting \(V \geq 0\). Hence \(\ell = 0\), and positive definiteness forces \(\phi_t(x_0) \to 0\). \(\square\)

2.3 LaSalle’s Invariance Principle 💡

Theorem 2.6 Part 2 requires \(\dot{V} < 0\) everywhere. This is often too strong — the damped oscillator example has \(\dot{V} = 0\) on the entire \(x_1\)-axis. LaSalle’s principle handles this by asking not where \(\dot{V}\) vanishes, but what invariant structure lives in that set.

Definition 2.7 (Positively invariant set). A set \(\Omega\) is positively invariant for (2.1) if \(x_0 \in \Omega \implies \phi_t(x_0) \in \Omega\) for all \(t \geq 0\).

Definition 2.8 (Omega-limit set). The omega-limit set of a point \(x_0\) is \[\omega(x_0) := \bigl\{ y \in \mathbb{R}^n : \exists\, t_k \to \infty \text{ with } \phi_{t_k}(x_0) \to y \bigr\}.\]

Theorem 2.9 (LaSalle’s Invariance Principle). Let \(\Omega \subseteq U\) be a compact, positively invariant set for (2.1). Let \(V: U \to \mathbb{R}\) be \(C^1\) with \(\dot{V}(x) \leq 0\) for all \(x \in \Omega\). Define

\[S := \{x \in \Omega : \dot{V}(x) = 0\}, \qquad M := \text{largest invariant subset of } S.\]

Then every solution starting in \(\Omega\) converges to \(M\) as \(t \to \infty\).

Proof sketch. For \(x_0 \in \Omega\): since \(\dot{V} \leq 0\) on \(\Omega\) and \(\Omega\) is positively invariant, \(V(\phi_t(x_0))\) is non-increasing and bounded below, so \(V(\phi_t(x_0)) \to \ell\) for some \(\ell\). The omega-limit set \(\omega(x_0) \subseteq \Omega\) is non-empty, compact, and invariant (standard ODE theory). On \(\omega(x_0)\), \(V \equiv \ell\) (since \(V\) is continuous and converges to \(\ell\)), so \(\dot{V} \equiv 0\) on \(\omega(x_0)\), meaning \(\omega(x_0) \subseteq S\). Since \(\omega(x_0)\) is invariant and lies in \(S\), it lies in \(M\). \(\square\)

3. The Replicator Dynamic 🧬

3.1 Finite Symmetric Games and the Strategy Simplex

A finite symmetric game is defined by a finite strategy set \(\{1, 2, \ldots, n\}\) and a payoff matrix \(A \in \mathbb{R}^{n \times n}\). The entry \(A_{ij}\) is the payoff to a player using strategy \(i\) against a player using strategy \(j\).

The game is played not between two fixed individuals, but in a large population. At any time, a fraction \(x_i \geq 0\) of the population uses strategy \(i\). The state of the population is a vector

\[x = (x_1, \ldots, x_n) \in \Delta^n,\]

where \(\Delta^n\) is the standard \((n-1)\)-simplex:

\[\Delta^n := \left\{ x \in \mathbb{R}^n : x_i \geq 0 \text{ for all } i, \quad \sum_{i=1}^n x_i = 1 \right\}.\]

The interior is \(\Delta^n_\circ := \{x \in \Delta^n : x_i > 0 \text{ for all } i\}\). We think of \(x\) as a mixed strategy — a probability distribution over the pure strategies.

Definition 3.1 (Fitness). The fitness (expected payoff) of strategy \(i\) against the population \(x\) is

\[f_i(x) := (Ax)_i = \sum_{j=1}^n A_{ij} x_j.\]

The mean fitness of the population is

\[\bar{f}(x) := x \cdot Ax = \sum_{i=1}^n x_i f_i(x) = \sum_{i,j} x_i A_{ij} x_j.\]

3.2 The Replicator ODE

The replicator dynamic models a population that reproduces at a rate proportional to fitness relative to the mean. If strategy \(i\) is above-average, its frequency grows; below-average, it shrinks.

Definition 3.2 (Replicator dynamic). The replicator ODE on \(\Delta^n\) is

\[\dot{x}_i = x_i \bigl( f_i(x) - \bar{f}(x) \bigr) = x_i \bigl( (Ax)_i - x \cdot Ax \bigr), \qquad i = 1, \ldots, n. \tag{3.1}\]

Proposition 3.3 (Simplex invariance). If \(x(0) \in \Delta^n\), then \(x(t) \in \Delta^n\) for all \(t \geq 0\).

Proof. First, \(x_i(0) > 0 \implies x_i(t) > 0\) for all \(t\) (by the ODE: \(\dot{x}_i = x_i g_i\) has solution \(x_i(t) = x_i(0) \exp(\int_0^t g_i(s)\,ds)\), which cannot cross zero). Second, differentiating \(\sum_i x_i\): \[\frac{d}{dt}\sum_i x_i = \sum_i \dot{x}_i = \sum_i x_i (f_i(x) - \bar{f}(x)) = \bar{f}(x) - \bar{f}(x) \cdot 1 = 0.\] So \(\sum_i x_i\) is constant, equaling 1 at \(t=0\). \(\square\)

3.3 Fixed Points

Proposition 3.4 (Fixed points of the replicator dynamic). A state \(x^* \in \Delta^n\) is a fixed point of (3.1) if and only if

\[x_i^* > 0 \implies f_i(x^*) = \bar{f}(x^*).\]

That is: all strategies in the support of \(x^*\) must have equal fitness under \(x^*\).

Proof. \(\dot{x}_i^* = 0\) for all \(i\). If \(x_i^* > 0\), then \((f_i(x^*) - \bar{f}(x^*)) = 0\). If \(x_i^* = 0\), the equation \(\dot{x}_i^* = 0 \cdot (\ldots) = 0\) is automatic regardless of \(f_i\). \(\square\)

3.4 Evolutionarily Stable Strategies

The concept of an evolutionarily stable strategy (ESS) formalizes resistance to invasion by mutants. It is stronger than Nash equilibrium.

Definition 3.5 (ESS — two-condition form). A strategy \(\hat{x} \in \Delta^n\) is an evolutionarily stable strategy if for all \(x \neq \hat{x}\) in a neighborhood of \(\hat{x}\):

1. \(\hat{x} \cdot A\hat{x} \geq x \cdot A\hat{x}\) (Nash condition), and
2. if \(\hat{x} \cdot A\hat{x} = x \cdot A\hat{x}\), then \(\hat{x} \cdot Ax > x \cdot Ax\) (stability condition).

The first condition says \(\hat{x}\) is a best reply to itself. The second says that among best replies to \(\hat{x}\), the strategy \(\hat{x}\) does strictly better against any mutant \(x\) than \(x\) does against itself.

Proposition 3.6 (Interior ESS — one-condition form). If \(\hat{x} \in \Delta^n_\circ\) is an interior point, then \(\hat{x}\) is an ESS if and only if there exists \(\epsilon > 0\) such that for all \(x \in B_\epsilon(\hat{x}) \setminus \{\hat{x}\}\):

\[\hat{x} \cdot Ax > x \cdot Ax. \tag{3.2}\]

Proof sketch. For an interior \(\hat{x}\), condition (1) of Definition 3.5 is equivalent to \(A\hat{x} = \bar{f}(\hat{x}) \mathbf{1}\) (all strategies earn the same fitness at \(\hat{x}\)). Substituting, \(\hat{x} \cdot Ax = \bar{f}(\hat{x})\) for all \(x\), so condition (2) becomes \(\bar{f}(\hat{x}) > x \cdot Ax = \bar{f}(x)\) for nearby \(x \neq \hat{x}\). This is precisely (3.2). \(\square\)

4. KL Divergence as a Lyapunov Function 🔑

4.1 Setup and Statement

We now prove the main result. Fix an interior ESS \(\hat{x} \in \Delta^n_\circ\) of a finite symmetric game with payoff matrix \(A\). Define the candidate Lyapunov function

\[V(x) = D_{\mathrm{KL}}(\hat{x} \| x) := \sum_{i=1}^n \hat{x}_i \log \frac{\hat{x}_i}{x_i}. \tag{4.1}\]

\(V\) is defined on \(\Delta^n_\circ\) (since \(\hat{x}_i > 0\) and we need \(x_i > 0\) for the logarithm).

Theorem 4.1 (KL Lyapunov at an ESS). Let \(\hat{x} \in \Delta^n_\circ\) be an interior ESS. Then \(V(x) = D_{\mathrm{KL}}(\hat{x} \| x)\) is a strict Lyapunov function for the replicator dynamic (3.1) in a neighborhood of \(\hat{x}\). In particular, \(\hat{x}\) is asymptotically stable.

The proof occupies Sections 4.2–4.5, building each piece in turn.

4.2 Positivity of V

Lemma 4.2 (Positivity of KL divergence). \(D_{\mathrm{KL}}(\hat{x} \| x) \geq 0\) for all \(x, \hat{x} \in \Delta^n_\circ\), with equality if and only if \(x = \hat{x}\).

Proof. By Jensen’s inequality and the concavity of \(\log\):

\[-D_{\mathrm{KL}}(\hat{x} \| x) = \sum_i \hat{x}_i \log \frac{x_i}{\hat{x}_i} \leq \log \sum_i \hat{x}_i \cdot \frac{x_i}{\hat{x}_i} = \log \sum_i x_i = \log 1 = 0.\]

Equality in Jensen holds iff \(x_i / \hat{x}_i\) is constant for all \(i\) in the support of \(\hat{x}\). Since \(\sum_i x_i = \sum_i \hat{x}_i = 1\), the constant must be 1, so \(x = \hat{x}\). \(\square\)

This establishes conditions (1) and (2) of Definition 2.5: \(V(\hat{x}) = D_{\mathrm{KL}}(\hat{x} \| \hat{x}) = 0\) and \(V(x) > 0\) for \(x \neq \hat{x}\).

4.3 Computing V-dot along Replicator Trajectories 📐

This is the heart of the proof. We differentiate \(V(x(t)) = \sum_i \hat{x}_i \log(\hat{x}_i / x_i(t))\) with respect to \(t\), using the replicator ODE (3.1).

Computation. Differentiating \(V(x) = \sum_i \hat{x}_i \log \hat{x}_i - \sum_i \hat{x}_i \log x_i\) with respect to \(t\) (the first sum is constant since \(\hat{x}\) is fixed):

\[\dot{V}(x) = -\sum_{i=1}^n \hat{x}_i \cdot \frac{\dot{x}_i}{x_i}. \tag{4.2}\]

Substitute the replicator ODE \(\dot{x}_i = x_i(f_i(x) - \bar{f}(x))\):

\[\dot{V}(x) = -\sum_{i=1}^n \hat{x}_i \cdot \frac{x_i(f_i(x) - \bar{f}(x))}{x_i} = -\sum_{i=1}^n \hat{x}_i \bigl( f_i(x) - \bar{f}(x) \bigr). \tag{4.3}\]

The \(x_i\) in numerator and denominator cancel (this is where positivity \(x_i > 0\) is used). Distributing:

\[\dot{V}(x) = -\sum_{i=1}^n \hat{x}_i f_i(x) + \bar{f}(x) \sum_{i=1}^n \hat{x}_i. \tag{4.4}\]

Since \(\sum_i \hat{x}_i = 1\) and \(\sum_i \hat{x}_i f_i(x) = \hat{x} \cdot Ax\) (by definition of fitness), this simplifies to:

\[\boxed{\dot{V}(x) = \bar{f}(x) - \hat{x} \cdot Ax.} \tag{4.5}\]

4.4 Signing V-dot via the ESS Inequality 🔑

We now use the ESS condition to show \(\dot{V}(x) < 0\) for \(x \neq \hat{x}\) near \(\hat{x}\).

Lemma 4.3. Let \(\hat{x} \in \Delta^n_\circ\) be an interior ESS. Then for all \(x \in B_\epsilon(\hat{x}) \setminus \{\hat{x}\}\):

\[\dot{V}(x) = \bar{f}(x) - \hat{x} \cdot Ax < 0.\]

Proof. By the interior ESS condition (Proposition 3.6, equation (3.2)):

\[\hat{x} \cdot Ax > x \cdot Ax = \bar{f}(x) \qquad \text{for all } x \in B_\epsilon(\hat{x}) \setminus \{\hat{x}\}.\]

Rearranging: \(\bar{f}(x) - \hat{x} \cdot Ax < 0\). By (4.5), this is exactly \(\dot{V}(x) < 0\). \(\square\)

This is the key computation. The ESS inequality says exactly that the KL divergence from \(\hat{x}\) to the current state is being reduced along every nearby trajectory.

4.5 Asymptotic Stability Conclusion

Collecting the pieces:

1. \(V(\hat{x}) = 0\): immediate from \(D_{\mathrm{KL}}(\hat{x} \| \hat{x}) = 0\).
2. \(V(x) > 0\) for \(x \neq \hat{x}\): Lemma 4.2 (non-negativity and equality condition of KL).
3. \(\dot{V}(x) < 0\) for \(x \neq \hat{x}\) near \(\hat{x}\): Lemma 4.3 via the ESS inequality.

By Theorem 2.6 Part 2, the equilibrium \(\hat{x}\) is asymptotically stable. This completes the proof of Theorem 4.1. \(\square\)

5. Geometric Interpretation 🌐

# Continuous-time mirror descent (multiplicative weights)
# x: current population state (probability vector)
# f: fitness vector f_i = (Ax)_i
# eta: step size / learning rate

def mirror_descent_step(x, f, eta):
    log_x_new = [log(x[i]) + eta * f[i] for i in range(n)]
    # project back: normalize in log-space (log-sum-exp)
    log_Z = log_sum_exp(log_x_new)
    return [exp(log_x_new[i] - log_Z) for i in range(n)]

6. References