Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Let S be a finite set, say \(S =\{ 1,\ldots,n\}.\) A rate matrix over S is a n × n matrix L such that L ij  ≥ 0 for i ≠ j and \(\sum _{j}L_{ij} = 0.\) We let R(S) denote the space of such matrices. For \(x \in \mathbb{R}^{n}\) and L ∈ R(S) we let xL denote the vector defined by \((xL)_{i} =\sum _{j}x_{j}L_{ji}.\)

Let

$$\displaystyle{\varDelta =\{ x \in \mathbb{R}^{n}:\: x_{ i} \geq 0,\;\sum _{i}x_{i} = 1\}}$$

be the unit simplex of probabilities over S. In this paper we are interested in ordinary differential equations on Δ having the form

$$\displaystyle{ \frac{dx} {dt} = xL(x):= F(x) }$$
(1)

where \(L:\varDelta \mapsto \mathbf{R}(S)\) is a sufficiently smooth function. Such dynamics occur—through a natural averaging procedure- in models of games describing strategic interactions in a large population of players, as well as in certain models of learning and reinforcement. These models are usually derived from qualitative assumptions describing the “microscopic” behavior of anonymous agents, and it is usually believed or assumed that similar qualitative microscopic behaviors should lead to similar global dynamics. However there is no satisfactory general theory supporting this belief.

To be more precise, under the assumption that L(x) is irreducible, there exists a unique “invariant probability” for L(x), π(x) ∈ Δ characterized by

$$\displaystyle{ \pi (x)L(x) = 0. }$$
(2)

Several models corresponding to different rate functions \(x\mapsto L(x)\) have the same invariant probability function \(x\mapsto \pi (x).\) For instance, to each population game (see Sect. 2.1) which average ODE is given by (1), there is a canonical way to define a learning process (see Sect. 2.2) which average ODE is given by

$$\displaystyle{ \frac{dx} {dt} = -x +\pi (x):= F_{\pi }(x), }$$
(3)

but there is no evidence that the dynamics of (1) and (3) are related in general.

The purpose of this paper is to provide sufficient conditions on π(x) ensuring that (1) has a gradient-like structure. This heavily relies on an idea introduced in [10] where it was shown that the relative entropy between x and π(x) is a strict Lyapounov function for systems of Gibbs type. We extend this idea to other class of systems beyond systems of Gibbs type, including population games and reinforcement process with imitative dynamics, and investigate further dynamics properties.

To give the flavor of the results presented in this paper, let \(\pi:\varDelta \mapsto \dot{\varDelta }\) be a smooth function mapping Δ into its relative interior. Let χ π be the set of vector fields having the form given by (the right hand side of) (1), where for each x, L(x) is irreducible and verifies (2). Note that χ π is a convex set of vector fields on Δ and that \(F_{\pi } \in \chi _{\pi }.\)

Theorem A

For all F ∈ χ π . 

  1. (i)

    Equilibria (respectively non degenerate equilibria) of F coincide with equilibria (respectively non degenerate equilibria) of F π . 

  2. (ii)

    In general, global dynamics of F and F π are “unrelated.” We construct an example for which F π is globally asymptotically stable (every trajectory converge toward a linearly stable equilibrium) while every non equilibrium trajectory for F converge to a limit cycle.

  3. (iii)

    Assume that there exists a C k, k ≥ 1 strictly increasing function \(s: \mathbb{R}\mapsto \mathbb{R}\) such that \(x \in \dot{\varDelta }\mapsto s(( \frac{x_{i}} {\pi _{i}(x)}))_{i\in S}\) is the gradient (or quasi gradient) of some function \(V:\dot{\varDelta } \mapsto \mathbb{R}.\) Then

    1. (a)

      V is a strict Lyapounov function for F (F is gradient-like) and verifies an angle condition,

    2. (b)

      Omega limit sets and chain-transitive sets of F are equilibria,

    3. (c)

      In the real analytic case, every solution to (1) converge toward an equilibrium,

    4. (d)

      In the reversible case, hyperbolic equilibria of F coincide with non degenerate critical points of V and, provided there are finitely many equilibria, F is C 1 close to a gradient vector field for a certain Riemannian metric,

    5. (e)

      The set χ π is not (in general) structurally stable.

Section 2 describes a few examples that motivate this work. Section 3 contains some preliminary results and the main assumptions. Section 4 is devoted to Theorem A, (ii); Sect. 5 to (iii), (a), (b), (c); Sects. 6 and 7 to (iii)(d) and Sect. 8 to (iii)(e). Other results and examples are also discussed in these sections. For instance, in Sect. 6.1, the local dynamics (dynamics in the neighborhood of equilibria) of mean field systems associated to potential games is precisely described in term of Nash equilibria.

2 Motivating Examples

Throughout this section we see S as set of pure strategies. A Markov matrix over S is a n × n matrix K such that K ij  ≥ 0 and \(\sum _{j}K_{ij} = 1.\) We let M(S) denote the sets of such matrices and we assume given a Lipschitz map

$$\displaystyle{K:\varDelta \mapsto \mathbf{M}(S).}$$

For further reference we may call such a map a revision protocol. This terminology is borrowed from [23].

2.1 Population Games

Good references on the subject include [22] and the survey paper [23] from which some of the examples here are borrowed.

Consider a population of N agents, each of whom chooses a strategy in S at discrete times \(k = 1,2,\ldots.\) Depending on the context, an agent can be a player, a set of players, a biological entity, a communication device, etc. The state of the system at time \(k \in \mathbb{N}\) is the vector \(X_{k}^{N} = (X_{k,1}^{N},\ldots X_{k,n}^{N}) \in \varDelta\) where \(NX_{k,i}^{N}\) equals the number of agents having strategy i. The system evolves as follows. Assume that at time k the system is in state \(X_{k}^{N} = x.\) Then an agent is randomly chosen in the population. If the chosen agent is an i−strategist, he/she switches to strategy j with probability K ij (x). This makes \((X_{k}^{N})_{k\geq 1}\) a discrete time Markov chain, which transition probabilities are

$$\displaystyle{\mathbf{P}(X_{k+1}^{N} = x + \frac{1} {N}(e_{j} - e_{i})\vert X_{k}^{N} = x) = x_{ i}K_{ij}(x)}$$

where \((e_{1},\ldots,e_{n})\) is the standard basis of \(\mathbb{R}^{n}.\) Let

$$\displaystyle{ L(x) = -Id + K(x). }$$
(4)

By standard mean-field approximation (see [5, 15] for precise statements, and [22, 23] for discussions in the context of games), the process \(\{(X_{k}^{N})\:: kN \leq T\}\) can be approximated by the solution to (1) (with L(x) given by (4)) with initial condition \(x = X_{0}^{N},\) over the time interval [0, T]. 

2.1.1 Revision Protocols

Assume, as it is often the case in economic or biological applications, that the population game is determined by a continuous Payoff-function \(U:\varDelta \mapsto \mathbb{R}^{n}.\) The quantity U i (x) represents the payoff (utility, fitness) of an i− strategist when the population state is x. 

An attachment-function is a continuous map \(w:\varDelta \mapsto \mathbb{R}_{+}^{n^{2} }.\) The weight w ij (x) can be seen as an a priori attachment of an i−strategist for strategy j. It can also encompasses certain constraints on the strategy sets. For instance w ij (x) = 0 (respectively w ij (x) < < 1) if a move from i to j is forbidden (respectively costly). We call the attachment function imitative if

$$\displaystyle{ w_{ij}(x) = x_{j}\tilde{w}_{ij}(x) }$$
(5)

Most, not to say all, revision protocols in population games fall into one of the two next categories:

  1. (i)

    [Sampling]

    $$\displaystyle{ K_{ij}(x) = \frac{w_{ij}(x)f(U_{j}(x))} {\sum _{k}w_{ik}(x)f(U_{k}(x))} }$$
    (6)

    where f is a non negative increasing function.

  2. (ii)

    [Comparison]

    $$\displaystyle\begin{array}{rcl} K_{ij}(x)& =& w_{ij}(x)g(U_{i}(x),U_{j}(x))\mbox{ for }i\neq j \\ K_{ii}(x)& =& 1 -\sum _{j\neq i}K_{ij}(x) {}\end{array}$$
    (7)

    where g(u, v) is nonnegative, decreasing in u, increasing in v and such that ∑ j ≠ i K ij (x) ≤ 1. 

2.2 Processes with Reinforcement and Adaptive Learning

Suppose now there is only one single agent in the population. In the context of games, one can imagine that this agent consists of a finite set of players and that S is the cartesian product of the strategy sets of the players. let X k  ∈ S denote the strategy of this agent at time k. Let μ k  ∈ Δ denote the empirical occupation measure of (X k ) up to time k. That is

$$\displaystyle{\mu _{k} = \frac{1} {k}\sum _{j=1}^{k}\delta _{ X_{j}}}$$

where \(\delta: S\mapsto \varDelta\) is defined by δ i  = e i . Suppose now that the agent revises her strategies as follows:

$$\displaystyle{\mathbf{P}(X_{k+1} = j\vert X_{0},\ldots,X_{k-1},X_{k} = i) = K_{ij}(\mu _{k}).}$$

The process (X k ) is no longer a Markov process but a process with reinforcement (see [20] for a survey of the literature on the subject). Using tools from stochastic approximation theory, it can be shown (see [1]) that, under certain irreducibility assumptions, the long term behavior of (μ k ) can be precisely related (see [1–3] and the brief discussion preceding Corollary 3) to the long term behavior of the differential equation on Δ

$$\displaystyle{ \frac{dx} {dt} = -x +\pi (x) }$$
(8)

where π(x) ∈ Δ is the invariant probability of K(x). Note that (8) can be rewritten as (1) with \(L_{ij}(x) =\delta _{ij} -\pi _{j}(x).\)

3 Hypotheses, Notation, and Preliminaries

Let L be a rate matrix, as defined in the introduction. Then L is the infinitesimal generator of a continuous time Markov chains on S. A probability π ∈ Δ is called invariant for L if it is invariant for the associated Markov chain, or equivalently

$$\displaystyle{\pi L = 0.}$$

A sufficient condition ensuring that π ∈ Δ is invariant is that L is reversible with respect to π, meaning that

$$\displaystyle{\pi _{i}L_{ij} =\pi _{j}L_{ji}.}$$

The matrix is said irreducible if for all \(i,j \in \{ 1,\ldots,n\}\) there exist some integer k and a sequence of indices \(i = i_{1},i_{2},\ldots,i_{k-1},i_{k} = j\) such that \(L_{i_{l},i_{l+1}}> 0\) for \(l = 1,\ldots,k - 1.\)

An irreducible rate matrix admits a unique invariant probability which can be expressed as a rational function of the coefficients (L ij ) (see e.g. Chapter 6 of [11]).

The relative interior of Δ is the set

$$\displaystyle{\dot{\varDelta }=\{ x \in \varDelta:\: \forall i \in S,\,x_{i}> 0\}.}$$

From now on we assume given a C 1 mapFootnote 1 \(L:\varDelta \mapsto \mathbf{R}(S)\) satisfying the following assumption:

Hypothesis 1 (Standing Assumption)

For all \(x \in \dot{\varDelta },L(x)\) is irreducible.

We sometimes assume

Hypothesis 2 (Occasional Assumption)

For all x ∈ Δ, L(x) is irreducible.

In view of the preceding discussion Hypotheses 1 and 2 imply the following

Lemma 1

There exists a C 1 map \(\pi:\dot{\varDelta } \mapsto \dot{\varDelta }\) such that for all \(x \in \dot{\varDelta },\) y = π(x) is the unique solution to the equation

$$\displaystyle{yL(x) = 0,\;y \in \varDelta.}$$

If L is \(C^{k},C^{\infty }\) or real analytic, the same is true for π. Under Hypothesis 2 , π is defined on all Δ and maps Δ into \(\dot{\varDelta }.\)

We let F π denote the map defined as

$$\displaystyle{ F_{\pi }(x) = -x +\pi (x). }$$
(9)

Throughout, it is implicitly assumed that the domain of F π is \(\dot{\varDelta }\) under Hypothesis 1 and Δ under Hypothesis 2.

We now consider the dynamics induced by (1). Without loss of generality, we may assume that (1) is defined on all \(\mathbb{R}^{n}\) and induces a flow Φ = (Φ t ) leaving Δ positively invariant. Indeed, by convexity of Δ, the retraction \(r: \mathbb{R}^{n}\mapsto \varDelta\) defined by \(r(x) = \mathbf{argmin}_{y\in \varDelta }\|x - y\|\) is Lipschitz so that the differential equation

$$\displaystyle{ \frac{dy} {dt} = yL(r(y)) }$$
(10)

is Lipchitz and sub-linear on all \(\mathbb{R}^{n}.\) By standard results, it then induces a flow \(\varPhi: \mathbb{R} \times \mathbb{R}^{n}\mapsto \mathbb{R}^{n}\) where \(t\mapsto \varPhi (t,y) =\varPhi _{t}(y)\) is the unique solution to (10) with initial condition y. For all x ∈ Δ and t ≥ 0, Φ t (x) ∈ Δ and the map \(t \in \mathbb{R}^{+}\mapsto \varPhi _{t}(x)\) is solution to (1).

In the following we sometime use the notation \(\varPhi _{t}(x) = x(t) = (x_{1}(t),\ldots,x_{n}(t)).\) The tangent space of Δ is the space

$$\displaystyle{T\varDelta =\{ u \in \mathbb{R}^{n}\::\sum _{ i=1}^{n}u_{ i} = 0\}.}$$

Lemma 2

  1. (i)

    There exists α ≥ 0 such that for all x ∈Δ \(x_{i}(t) \geq e^{-\alpha t}x_{i}(0).\) In particular, \(\dot{\varDelta }\) is positively invariant.

  2. (ii)

    If for all x ∈ ∂Δ L(x) is irreducible, then \(\varPhi _{t}(\varDelta ) \subset \dot{\varDelta }\) for all t > 0 and the dynamics (1) admits a global attractor

    $$\displaystyle{A =\bigcap _{t\geq 0}\varPhi _{t}(\varDelta ) \subset \dot{\varDelta }.}$$

Proof

(i) Let \(\alpha =\sup _{x\in \varDelta }- L_{ii}(x).\) For all j ≠ i and x ∈ Δ

$$\displaystyle{\dot{x}_{i} \geq -\alpha x_{i} + x_{j}L_{ji}(x).}$$

Hence

$$\displaystyle{x_{i}(t) \geq e^{-\alpha t}[x_{ i}(0) +\int _{ 0}^{t}e^{\alpha s}x_{ j}(s)L_{ji}(x(s))ds] \geq e^{-\alpha t}x_{ i}(0).}$$

The second inequality is the first statement. From the first inequality and the continuity of L(x(t)) it follows that x i (t) > 0 for all t > 0 whenever that \(x_{j}L_{ji}(x)> 0.\) Let now x ∈ ∂ Δ. Assume without loss of generality that x 1 > 0. By irreducibility there exists a sequence \(1 = i_{1},i_{2},\ldots i_{k} = j\) such that \(L_{i_{l},i_{l+1}}(x)> 0.\) Hence, by continuity, \(L_{i_{l},i_{l+1}}(x(t))> 0\) for all t small enough. It then follows that x j (t) > 0 for all t > 0. ■ 

Remark 1

Assumption 1 is not needed in Lemma 2.

Throughout we let

$$\displaystyle{\mathbf{Eq}(F) =\{ x \in \varDelta \:: F(x) = 0\}}$$

denote the equilibria set of F. Note that in view of the preceding Lemmas

$$\displaystyle{\mathbf{Eq}(F)\cap \dot{\varDelta } =\{ x \in \dot{\varDelta }:\: F_{\pi }(x) = 0\}}$$

and, in case L(x) is irreducible for all x ∈ Δ, \(\mathbf{Eq}(F) \subset \dot{\varDelta }.\)

An equilibrium p is called non degenerate for F provided the Jacobian matrix \(DF(\,p): T\varDelta \mapsto T\varDelta\) is invertible.

Lemma 3

Let \(p \in \mathbf{Eq}(F) \cap \dot{\varDelta }.\) Then p is non degenerate for F if and only if it is non degenerate for F π .

Proof

Let \(L^{T}(x): T\varDelta \mapsto T\varDelta\) be defined by \(L^{T}(x)h = hL(x).\) Then for all \(x \in \dot{\varDelta }\, F(x) = xL(x) = (x -\pi (x))L(x) = L^{T}(x)(x -\pi (x)).\) Hence at every equilibrium \(p \in \dot{\varDelta }\) \(DF(\,p) = -L^{T}(\,p)(DF_{\pi }(\,p)).\) By irreducibility, L T( p) is invertible (see Lemma 8 in the Appendix). Thus DF( p) is invertible if and only if DF π ( p) is invertible. ■ 

4 Dynamics of F and F π are Generally Unrelated

While F and F π have the same equilibria, they may have quite different dynamics as shown by the following example.

Suppose n = 3 so that Δ is the unit simplex in \(\mathbb{R}^{3}.\) Let G be a smooth vector field on Δ such that:

  1. (i)

    G points inward \(\dot{\varDelta }\) on ∂ Δ, 

  2. (ii)

    Every forward trajectory of G converge to \(p = (1/3,1/3,1/3),\)

  3. (iii)

    \(\jmath DG(\,p)\jmath^{-1} = \left (\begin{array}{cc} -\eta &- 1\\ 1 & -\eta \\ \end{array} \right ),\,\eta> 0,\)

    where \(\jmath: T\varDelta \mapsto \mathbb{R}^{2}\) is defined by \(\jmath(u_{1},u_{2},u_{3}) = (u_{1},u_{2}).\)

It is easy to construct such a vector field.

Choose \(\varepsilon> 0\) small enough so that \(\varepsilon G(x) + x\) lies in \(\dot{\varDelta }\) for all x ∈ Δ and set \(\pi (x) =\varepsilon G(x) + x.\) Then, F π and G have the same orbits.

Let W be a 3 × 3 symmetric irreducible matrix with positive off-diagonal entries. Set \(L_{ij}(x) = W_{ij}\pi _{j}(x)\) for i ≠ j and \(L_{ii}(x) = -\sum _{j\neq i}L_{ij}(x).\) The matrix L(x) is an irreducible rate matrix, reversible with respect to π(x). It follows from Lemmas 2 and 3 that F(x) = xL(x) has a global attractor contained in \(\dot{\varDelta }\) and a unique equilibrium given by p. 

Furthermore,

$$\displaystyle{DF(\,p) = -L(\,p)^{T}DF_{\pi }(\,p) = -\varepsilon L(\,p)^{T}DG(\,p) = -\frac{\varepsilon } {3}WDG(\,p)}$$

where the last equality follows from the definition of L and the fact that π( p) = p. To shorten notation, set \(b = \frac{\varepsilon } {3}W_{12},c = \frac{\varepsilon } {3}W_{13}\) and \(d = \frac{\varepsilon } {3}W_{23}.\) Then

$$\displaystyle{\jmath DF(\,p)\jmath^{-1} = \left (\begin{array}{cc} (b + 2c)& c - b \\ d - b &(b + 2d)\\ \end{array} \right )\left (\begin{array}{cc} -\eta &- 1\\ 1 & -\eta \\ \end{array} \right )}$$

The determinant of this matrix is positive and its trace equals

$$\displaystyle{(c - d) - 2\eta (b + c + d).}$$

If one now choose c > d and η small enough, the trace is positive. This makes p linearly unstable. By Poincaré-Bendixson theorem, it follows that every forward trajectory distinct from p converges toward a periodic orbit.

Remark 2

It was pointed out to me by Sylvain Sorin and Josef Hofbauer that this example is reminiscent of the following phenomenon. Consider a population game which revision protocol takes the form

$$\displaystyle{K_{ij}(x) = \frac{x_{j}} {R} \max (0,U_{j}(x) - U_{i}(x))\mbox{ for }i\neq j}$$

(here R is chosen so that \(\sum _{j\neq i}K_{ij}(x) \leq 1\)). This is a particular case of imitative pairwise comparison protocol (see Eq. (7)).

Then, the mean field ode is the classical replicator dynamics (see Example 3.2 in [23]):

$$\displaystyle{ \dot{x_{i}} = x_{i}(U_{i}(x) -\sum _{j\in S}x_{j}U_{j}(x)) }$$
(11)

Here the rate matrix L(x) is not irreducible and its set of invariant probabilities is easily seen to be the Best Reply set

$$\displaystyle{BR(x) = \mathit{conv}(\{e_{i}:\: U_{i}(x) =\max _{j\in S}U_{j}(x)\}).}$$

where conv(A) stands for the convex hull of A. The vector field (9) is not defined but can be replaced by the differential inclusion

$$\displaystyle{ \dot{x} \in -x + BR(x). }$$
(12)

If one assume that \(U_{i}(x) =\sum _{j}U_{ij}x_{j}\) with U the payoff matrix given by a Rock-Paper-Scissors game,

$$\displaystyle{U = \left (\begin{array}{ccc} 0 & - 1& 1\\ 1 & 0 & -1 \\ - 1& 1 & 0\\ \end{array} \right );}$$

Then \(p = (1/3,1/3,1/3)\) is the unique equilibrium of (11) in \(\dot{\varDelta }\) (corresponding to the unique Nash equilibrium of the game) and every solution to (11) with initial condition in \(\dot{\varDelta }\setminus \{\,p\}\) is a periodic orbit. On the other hands, solutions to (12) converge to p. Phase portraits of these dynamics can be found in ([23], Section 5) and a detailed comparison of the replicator and the best reply dynamics is provided in [14].

5 Gradient Like Structure

For \(u,v \in \mathbb{R}^{n}\) we let \(\langle u,v\rangle =\sum _{i}u_{i}v_{i}.\)

A map \(h:\dot{\varDelta } \mapsto \mathbb{R}^{n},\) is called a gradient if there exists a C 1 map \(V:\dot{\varDelta } \mapsto \mathbb{R}\) such that for all \(x \in \dot{\varDelta }\) and u ∈ T Δ

$$\displaystyle{\langle h(x),u\rangle = DV (x).u:=\langle \nabla V (x),u\rangle.}$$

It is called a quasigradient or a α-quasigradient if \(x\mapsto \alpha (x)h(x)\) is a gradient for some continuous map \(\alpha:\dot{\varDelta } \mapsto \mathbb{R}_{+}^{{\ast}}.\) That is

$$\displaystyle{ \alpha (x)\langle h(x),u\rangle =\langle \nabla V (x),u\rangle }$$
(13)

for all \(x \in \dot{\varDelta }\) and u ∈ T Δ. 

Remark 3

If V is the restriction to \(\dot{\varDelta }\) of a C 1 map \(W: \mathbb{R}^{n}\mapsto \mathbb{R},\) then ∇V (x) is the orthogonal projection of ∇W(x) onto T Δ. That is

$$\displaystyle{\nabla V _{i}(x) = \frac{\partial W} {\partial x_{i}} (x) - \frac{1} {n}\sum _{j=1}^{n}\frac{\partial W} {\partial x_{j}} (x),i = 1,\ldots n.}$$

Remark 4

A practical condition ensuring that h is a gradient is that

  1. (a)

    h is the restriction to \(\dot{\varDelta }\) of a C 1 map \(h: \mathbb{R}^{n}\mapsto \mathbb{R}^{n},\)

  2. (b)

    For all \(x \in \dot{\varDelta }\) and \(i,j,k \in \{ 1,\ldots,n\}\)

    $$\displaystyle{\frac{\partial h_{i}} {\partial x_{j}}(x) + \frac{\partial h_{j}} {\partial x_{k}}(x) + \frac{\partial h_{k}} {\partial x_{i}} (x) = \frac{\partial h_{i}} {\partial x_{k}}(x) + \frac{\partial h_{k}} {\partial x_{j}}(x) + \frac{\partial h_{j}} {\partial x_{i}} (x).}$$

    This follows from ([13], Theorem 19.5.5.)

Notation

We use the following convenient notation. If x, y are vectors in \(\mathbb{R}^{n}\) and \(s: \mathbb{R}\mapsto \mathbb{R}\) we let \(x.y \in \mathbb{R}^{n}\) (respectively \(\frac{x} {y}\) and s(x)) be the vector defined by \((xy)_{i} = x_{i}y_{i}\) (respectively \((\frac{x} {y})_{i} = \frac{x_{i}} {y_{i}},s_{i}(x) = s(x_{i})).\)

5.1 Gradient Like Structure

A C 1 map \(V:\dot{\varDelta } \mapsto \mathbb{R}\) is called a strict Lyapounov function for F (or Φ) if for all \(x \in \dot{\varDelta }\)

$$\displaystyle{F(x)\neq 0 \Rightarrow \langle F(x),\nabla V (x)\rangle <0.}$$

Theorem 3

Let \(s:]0,\infty [\mapsto \mathbb{R}\) be a C 1 function with positive derivative and let \(h^{s}:\dot{\varDelta } \mapsto \mathbb{R}^{n}\) be the map defined by

$$\displaystyle{h^{s}(x) = s( \frac{x} {\pi (x)}).}$$

Assume that h s is a α-quasigradient. Then

  1. (i)

    The map V (given by (13) ) is a strict Lyapounov function for F on \(\dot{\varDelta };\)

  2. (ii)

    The critical points of V coincide with \(\mathbf{Eq}(F)\cap \dot{\varDelta };\)

  3. (iii)

    V satisfies the following angle condition : For every compact set \(K \subset \dot{\varDelta }\) there exists c > 0 such that

    $$\displaystyle{\mid \langle \nabla V (x),F(x)\rangle \mid \geq c \parallel \nabla V (x) \parallel \parallel F(x) \parallel }$$

    for all x ∈ K.

Remark 5 (Gibbs Systems)

If π(x) is a Gibbs measure,

$$\displaystyle{ \pi _{\beta,i}(x) = \frac{e^{-(U_{i}^{0}+\beta \sum _{ j}U_{ij}x_{j})}} {Z(x)} }$$
(14)

where U = (U ij ) is a symmetric matrix, β ≥ 0, and

$$\displaystyle{Z(x) =\sum _{j}e^{-(U_{j}^{0}+\beta \sum _{ k}U_{ik}x_{k})},}$$

parts (i) and (ii) of Theorem 3 have been proved in [10], Theorems 5.3 and 5.5. Here s(t) = log(t) and

$$\displaystyle{ V (x) =\sum _{i}x_{i}\log (x_{i}) +\sum _{j}U_{j}^{0}x_{ j} + \frac{\beta } {2}\sum _{ij}U_{ij}x_{i}x_{j}. }$$
(15)

Proof of Theorem 3

Part (i) relies on the following Lemma.

Lemma 4

Let L be an irreducible transition matrix with invariant probability π. Let \(x \in \varDelta,f_{i} = \frac{x_{i}} {\pi _{i}},\,s(\,f)_{i} = s(\,f_{i})\) and \(c_{f} =\inf _{i}s^{{\prime}}(\,f_{i})> 0.\) Then there exists λ(L) > 0 depending continuously on L such that

$$\displaystyle{\langle xL,s(\,f)\rangle \leq -c_{f}\lambda (L)V ar_{\pi }(\,f)}$$

where \(V ar_{\pi }(\,f) =\sum _{i}(\,f_{i} - 1)^{2}\pi _{i} =\sum _{i}\frac{(x_{i}-\pi _{i})^{2}} {\pi _{i}}.\)

The proof of this lemma uses elementary convexity arguments and classical tools from Markov chain theory. It is proved in appendix. Applying this lemma with L = L(x) and π = π(x) gives

$$\displaystyle{\langle F(x),\nabla V (x)\rangle <0}$$

unless x = π(x). 

  1. (ii)

    The set \(\mathbf{Eq}(F)\cap \dot{\varDelta }\) coincides with fixed points of π in \(\dot{\varDelta }.\) Let \(x \in \dot{\varDelta }.\) \(\nabla V (x) = 0 \Leftrightarrow h^{s}(x) \in \mathbb{R}1\) where 1 is the vector which components are all equal to 1. The function s being injective this is equivalent to \(\frac{x_{i}} {\pi _{i}(x)} = \frac{x_{j}} {\pi _{j}(x)}\) for all i, j. That is x = π(x). 

  2. (iii)

    Let \(K \subset \dot{\varDelta }.\) By Lemma 4 (applied with L = L(x) and π = π(x)) and continuity of the maps involved, there exists c > 0 depending on K such that

    $$\displaystyle{\vert \langle \nabla V (x),F(x)\rangle \vert \geq c\sum _{i}(x_{i} -\pi _{i}(x))^{2} = c\|x -\pi (x)\|^{2}.}$$

    To prove the angle condition it then suffices to show that both \(\|F(x)\|\) and \(\|\nabla V (x)\|\) are bounded by some constant times \(\|x -\pi (x)\|.\) Now, \(F(x) = xL(x) = xL(x) -\pi (x)L(x)\) so that

    $$\displaystyle{\|F(x)\| \leq c_{1}\|x -\pi (x)\|}$$

    with \(c_{1} =\sup _{x\in \varDelta }\|L(x)\|.\)

By Lipschitz continuity of s and compactness, there exist \(c_{2},c_{3}> 0\) depending on K such that

$$\displaystyle{\vert s( \frac{x_{i}} {\pi _{i}(x)}) - s(1)\vert \leq c_{2}\vert \frac{x_{i}} {\pi _{i}(x)} - 1\vert \leq c_{3}\vert x_{i} -\pi _{i}(x)\vert.}$$

Thus, for all u ∈ T Δ such that \(\|u\| = 1\)

$$\displaystyle{\langle h^{s}(x),u\rangle =\langle h^{s}(x) - s(1)1,u\rangle \leq \| h^{s}(x) - s(1).1\| \leq c_{ 3}\|x -\pi (x)\|.}$$

This implies that \(\|\nabla V (x)\| \leq c_{3}\|x -\pi (x)\|\) and concludes the proof. ■ 

The following result proves to be useful for certain dynamics leaving invariant the boundary of the simplex. Such dynamics occur in population games using imitative protocols (see Eq. (5)) as well as in certain models of vertex reinforcement (see Example 3 below).

For x ∈ Δ let Supp(x) = { x ∈ Δ : x i  > 0}. 

Proposition 1

Assume that assumptions of Theorem 3 hold. Assume furthermore that

  1. (a)

    For all x ∈Δ

    $$\displaystyle{x_{i} = 0 \Rightarrow L_{ji}(x) = 0}$$

    and the reduced rate matrix \([L_{ij}(x)]_{i,j\in Supp(x)}\) is irreducible

  2. (b)

    The maps \(V:\dot{\varDelta } \mapsto \mathbb{R}^{n}\) and \(\alpha:\dot{\varDelta } \mapsto \mathbb{R}_{+}^{{\ast}}\) (given by Eq. (13)) extend to C 1 (respectively continuous) maps \(V:\varDelta \mapsto \mathbb{R}^{n}\) and \(\alpha:\varDelta \mapsto \mathbb{R}_{+}^{{\ast}}.\)

Then V is strict Lyapounov function for F on Δ.

Proof

Let \(T\varDelta (x) =\{ u \in T\varDelta \:: u_{i} = 0\mbox{ for }i\not\in Supp(x)\}.\) By assumption (a) the map \(x\mapsto \pi (x)\) is defined for all x ∈ Δ continuous in x and \(\pi _{i}(x) = 0 \Leftrightarrow x_{i} = 0.\)

Therefore, using assumption (b), the equation

$$\displaystyle{\forall x \in \dot{\varDelta },\forall u \in T\varDelta \:\alpha (x)\langle h^{s}(x),u\rangle =\langle \nabla V (x),u\rangle }$$

extends to

$$\displaystyle{\forall x \in \varDelta,\forall u \in T\varDelta (x)\:\sum _{i\in Supp(x)}s( \frac{x_{i}} {\pi _{i}(x)})u_{i} =\langle \nabla V (x),u\rangle }$$

Thus

$$\displaystyle{\sum _{i\in Supp(x)}s( \frac{x_{i}} {\pi _{i}(x)})(xL(x))_{i} =\langle \nabla V (x),F(x)\rangle }$$

for all x ∈ Δ. By Lemma 4 the left hand side is nonpositive and zero if and only if x i  = π i (x) for all i ∈ Supp(x). ■ 

Remark 6

Note that under the assumptions of Proposition 1, the angle inequality of Theorem 3 doesn’t hold on the boundary of the simplex

Example 1

Let \(W: \mathbb{R}^{n}\mapsto \mathbb{R}\) be a C k map, k ≥ 1. Suppose that for all \(x \in \dot{\varDelta }\)

$$\displaystyle{\pi _{i}(x) = \frac{f_{i}(x_{i})\psi (\frac{\partial W} {\partial x_{i}} (x))} {\sum _{j=1}^{n}f_{j}(x_{j})\psi (\frac{\partial W} {\partial x_{j}}(x))}}$$

Then, Theorem 3 applies in the following cases:

Case 1 :

\(\psi (u) = e^{-\beta u}\) with β ≥ 0, and f i (t) > 0 for all t > 0. It suffices to choose s(t) = log(t) and

$$\displaystyle{ V (x) =\sum _{ i=1}^{n}x_{ i}\log (x_{i}) -\sum _{i=1}^{n}\int _{ 1}^{x_{i} }\log (\,f_{i}(u))du +\beta W(x) }$$
(16)

Then h s is the gradient of V. 

Case 2 :

\(\psi (u) = u^{\beta },\beta> 0,f_{i}(t) = t\) and \(\frac{\partial W} {\partial x_{i}}> 0\) on {x ∈ Δ:   x i  > 0}. It suffices to choose \(s(t) = -t^{-1/\beta }\) and

$$\displaystyle{V (x) = -W(x).}$$

Then h s is the α-quasigradient of V with

$$\displaystyle{\alpha (x) = [\sum _{j}x_{j}(\frac{\partial W} {\partial x_{j}} )^{\beta })]^{-1/\beta }.}$$

Example 2 (Potential Games)

Examples of applications of Example 1, case 1, are given by Potential Games (see [22] for an comprehensive presentation and motivating examples). We use the notation of Sect. 2. A Potential Game is a game for which the payoff function is such that for all x ∈ Δ

$$\displaystyle{U_{i}(x) = -\frac{\partial W} {\partial x_{i}} (x),i = 1\ldots n}$$

Consider a population game with a revision protocol given by (7). Suppose that the attachment matrix takes the form

$$\displaystyle{w_{ij}(x) = f_{j}(x_{j})\tilde{w}_{ij}(x)}$$

with \(\tilde{w}\) irreducible and symmetric. Let β ≥ 0. Assume furthermore that g(u, v) takes one of the following form:

Pairwise comparison

$$\displaystyle{g(u,v) = \frac{e^{\beta (v-u)}} {1 + e^{\beta (v-u)}}\mbox{ or }g(u,v) =\min (1,e^{\beta (v-u)}),}$$

Imitation driven by dissatisfaction

$$\displaystyle{g(u,v) = e^{-\beta u},}$$

Imitation of success

$$\displaystyle{g(u,v) = e^{\beta v}.}$$

In all these situations, K(x), hence L(x) is reversible with respect to π β (x) with

$$\displaystyle{\pi _{\beta,i}(x) = \frac{f_{i}(x_{i})e^{-\beta \frac{\partial W} {\partial x_{i}}(x)}} {\sum _{j}f_{j}(x_{j})e^{-\beta \frac{\partial W} {\partial x_{j}}(x)}}.}$$

Theorem 3 applies with V given by (16).

Remark 7 (Gibbs Systems, 2)

A particular case of potential games is obtained with \(W(x) = \frac{1} {2}\sum _{ij}U_{ij}x_{i}x_{j}\) with U = (U ij ) symmetric, and \(f_{i}(x) = e^{-U_{i}^{0} }.\) Here payoffs are linear in x: 

$$\displaystyle{U_{i}(x) = -\sum _{j}U_{ij}x_{j}}$$

and we retrieve the situation considered in [10]. See Remark 5.

Example 3 (Vertex Reinforcement)

Let K be the revision protocol defined by

$$\displaystyle{K_{ij}(x) = \frac{A_{ij}x_{j}^{\gamma }} {\sum _{k}A_{ik}x_{k}^{\gamma }}}$$

where A is a matrix with positive entries and γ ≥ 1. For population games (see Sect. 2.1) this gives a simple model of imitation: an agent of type i, when chosen, switches to j with a probability proportional to the (number of agents of type j)γ. For processes with reinforcement (as defined in Sect. 2.2) the probability to jump from i to j at time n is proportional to (the time spent in j up to time n)γ. This later model called a vertex reinforced random walks was introduced by Diaconis and first analyzed in Pemantle [19] (see also [1] and [7] for more references on the subject).

When A is symmetric, K(x) is reversible with respect to

$$\displaystyle{ \pi _{i}(x) = \frac{x_{i}^{\gamma }\sum _{k}A_{ik}x_{k}^{\gamma }} {\sum _{ij}A_{ij}x_{i}^{\gamma }x_{j}^{\gamma }} = \frac{x_{i}\frac{\partial W} {\partial x_{i}} } {\sum _{j}x_{j}\frac{\partial W} {\partial x_{j}}} }$$
(17)

with

$$\displaystyle{ W(x) =\sum _{i,j}A_{ij}x_{i}^{\gamma }x_{ j}^{\gamma } }$$
(18)

We are then in the situation covered by Example 1, case 2, with \(\psi (u) = u,f_{i}(t) = t,s(t) = -\frac{1} {t}\) and \(V = -W.\)

Both Theorem 3 and Proposition 1 apply.

Example 4 (Interacting Urn Processes)

Closely related to vertex reinforced random walks are models of interacting urns (see [6, 8, 24]). For these models \(\pi _{i}(x) = x_{i}\frac{\partial W} {\partial x_{i}}\) for some smooth function W. This is a particular case of Example 1, case 2.

5.2 Limit Sets and Chain Transitive Sets

Using Lasalle’s invariance principle we deduce the following consequences from Theorem 3.

Corollary 1

Assume that assumptions of Theorem 3 hold. Then every omega limit set of Φ contained in \(\dot{\varDelta }\) is a connected subset of \(\mathbf{Eq}(F) \cap \dot{\varDelta }.\)

Combining this results with Lemma 2 (ii) and Proposition 1 gives

Corollary 2

Assume that one of the following condition hold:

  1. (a)

    Assumptions of Theorem 3 and Hypothesis 2 or;

  2. (b)

    Assumptions of Proposition 1 .

Then every omega limit set of Φ is a connected subset of Eq (F).

A set L is called attractor free or internally chain transitive provided it is compact, invariant and Φ | L has no proper attractor. For reinforced random processes like the ones defined in Sect. 2.2, limit sets of (μ n ) are, under suitable assumptions, attractor free sets of the associated mean field Eq. (8) (see [1]). More generally attractor free sets are limit sets of asymptotic pseudo trajectories (see [3]). It is then useful to characterize such sets. Note however that the existence of a strict Lyapounov function, doesn’t ensure in general, that internally chain transitive sets consist of equilibria (see e.g. Remark 6.3 in [2]).

Corollary 3

Assume that assumptions of Theorem 3 hold and that h s is C k for some \(k \geq n - 2 =\dim (T\varDelta ) - 1.\) Then every internally chain transitive set of Φ contained in \(\dot{\varDelta }\) is a connected subset of \(\mathbf{Eq}(F) \cap \dot{\varDelta }.\) If we furthermore assume that L(x) is irreducible for all x ∈Δ, then every internally chain transitive set of Φ is a connected subset of Eq (F)

Proof

Let \(C = \mathbf{Eq}(F)\cap \dot{\varDelta }\) and \(A \subset \dot{\varDelta }\) an attractor free set. By Theorem 3, C coincide with critical points of V. By the assumption V is C k+1 so that by Sard’s theorem (see [12]), V (C) has empty interior. It follows (see e.g. Proposition 6.4 in [2]) that A ⊂ C.   ■ 

5.3 Convergence Toward One Equilibrium

In case equilibria are isolated, Corollary 1 implies that every trajectory bounded away from the boundary converge to an equilibrium and that every trajectory converges in case L(x) is irreducible for all x. However, when equilibria are degenerate, the gradient-like property is not sufficient to ensures convergence. There are known examples of smooth gradient systems which omega limit sets are a continuum of equilibria (see [18]). However, in the real analytic case, gradient like systems which verify an angle condition are known to converge.

Theorem 4

Suppose that assumptions of Theorem 3 hold and that V is real analytic. Then every omega limit set meeting \(\dot{\varDelta }\) reduces to a single point.

Proof

Let p be an omega limit point. If V is real analytic, it satisfies a Lojasiewicz inequality at p in the sense that there exist 0 < η ≤ 1∕2, β > 0 and a neighborhood U( p) of p such that

$$\displaystyle{\vert V (x) - V (\,p)\vert ^{1-\eta }\leq \beta \|\nabla V (x)\|}$$

for all x in a U( p). Such an inequality called a “gradient inequality” was proved by Lojasiewicz [16] and used (by Lojasiewicz again) to show that bounded solutions of real analytic gradient vector fields have finite length, hence converge. When the dynamics is not a gradient, but only gradient like with V as a strict Lyapounov function, the same results holds provided that V satisfies an angle condition:

$$\displaystyle{\langle \nabla V (x),F(x)\rangle \geq c\|F(x)\|\|\nabla V (x)\|}$$

for all x ∈ U( p). This is proved in [9] (see also [17], Theorem 7).  ■ 

Example 5 (Gibbs Systems, 3)

If π is given by (14) with U symmetric, V given by (15) is real analytic so that every solution to (1) converges toward an equilibrium.

6 Equilibria

Recall that point p ∈ Eq(F) is called non degenerate if the jacobian matrix \(DF(\,p): T\varDelta \mapsto T\varDelta\) is invertible. It is called hyperbolic if eigenvalues of DF( p) have non zero real parts. If p is hyperbolic, T Δ admits a splitting

$$\displaystyle{T\varDelta = E_{p}^{u} \oplus E_{ p}^{s}}$$

invariant under DF( p) such that the eigenvalues of \(DF(\,p)\vert _{E_{p}^{s}}\) (respectively \(DF(\,p)\vert _{E_{p}^{u}}\)) have negative (respectively positive) real parts.

Point \(p \in \mathbf{Crit}(V ) =\{ x \in \dot{\varDelta }\:: \nabla (V )(x) = 0\}\) is called non-degenerate if Hess(V )( p) the Hessian or V at p has full rank. In a suitable coordinate systems \(\mathit{Hess}(V )(\,p)(u,u) =\sum _{ i=1}^{n_{+}}u_{i}^{2} -\sum _{j=1}^{n_{-}}u_{j}^{2}\) with \(n_{+} + n_{-} = dim(T\varDelta ) = n - 1.\) The number n − is called the index of p (with respect to V ) and is written Ind( p, V ). 

Proposition 2

Assume that assumptions of Theorem 3 hold. Let \(p \in \mathbf{Eq}(F) \cap \dot{\varDelta }.\) Then

  1. (i)

    Point p is non degenerate if and only if it is a non degenerate critical point of V.

  2. (ii)

    If furthermore L is C 2 and p is hyperbolic,

    $$\displaystyle{\dim (E_{p}^{u}) = \mathbf{Ind}(\,p,V ).}$$

Proof

From Lemma 3, p is non degenerate if and only if DF π ( p) is invertible and (see the proof of Lemma 3)

$$\displaystyle{ DF(\,p) = -L^{T}(\,p)DF_{\pi }(\,p) }$$
(19)

Now, a direction computation (details are left to the reader) of the Hessian of V at x leads to

$$\displaystyle{\langle \mathit{Hess}(V )(x)u,v\rangle =\alpha (x)\langle s^{{\prime}}( \frac{x} {\pi (x)})(u - \frac{x} {\pi (x)}D\pi (x)u,v\rangle _{1/\pi (x)}}$$

where \(\langle u,v\rangle _{1/\pi }\) stands for \(\sum _{i}u_{i}v_{i}\frac{1} {\pi _{i}}.\) Since p = π( p)

$$\displaystyle{ \langle \mathit{Hess}(V )(\,p)u,v\rangle =\alpha (\,p)s^{{\prime}}(1)\langle (I - D\pi (\,p))u,v\rangle _{ 1/p} }$$
(20)

for all u, v ∈ T Δ, This proves that Hess V ( p) is non degenerate if and only if \((I - D\pi (\,p)) = -DF_{\pi }(\,p)\) is non degenerate and concludes the proof of the first part.

We now prove the second part. By the stable manifold theorem, there exists a (local) C 2 manifold \(W_{p}^{s}\) tangent to \(E_{p}^{s}\) at p positively invariant under Φ and such that for all \(x \in W_{p}^{s}\) \(\lim _{t\rightarrow \infty }\varPhi _{t}(x) = p.\) Clearly p is a global minimum of V restricted to W s. For otherwise there would exists \(x \in W_{p}^{s}\) such that

$$\displaystyle{V (\,p)> V (x)>\lim _{t\rightarrow \infty }V (\varPhi _{t}(x)) = V (\,p).}$$

Since p is also a critical point ∇V ( p) = 0. Let \(u \in E_{p}^{s}\) and let \(\gamma:] - 1,1[\mapsto W_{p}^{s}\) be a C 2 path with \(\gamma (0) = p,\dot{\gamma }(0) = u.\) Set h(t) = V (γ(t)). Then \(\dot{h}(0) = 0\) (because p is a critical point of V ) and \(h^{{\prime\prime}}(0) =\langle \mathit{Hess}V (\,p)u,u\rangle\) is non negative because h(t) ≥ h(0). 

On the other hand, by the spectral decomposition of Hess V ( p) we can write \(T\varDelta = E_{V }^{s} \oplus E_{V }^{u}\) with \(\langle \mathit{Hess}V (\,p)u,u\rangle> 0\) (respectively < 0) for all \(u \in E_{V }^{s}\setminus \{0\}\) (respectively \(E_{V }^{u}\setminus \{0\}\)). Thus, \(E_{p}^{s} \cap E_{V }^{u} =\{ 0\}\) and, consequently, \(\dim (E_{p}^{s}) +\dim (E_{V }^{u}) \leq \dim (T\varDelta ).\) Similarly \(\dim (E_{p}^{u}) +\dim (E_{V }^{s}) \leq \dim (T\varDelta ).\) This proves that \(\dim (E_{p}^{u}) =\dim (E_{V }^{u}) = \mathbf{Ind}(\,p,V ).\)  ■ 

Remark 8

This later proposition shows that in the neighborhood of an hyperbolic equilibrium p, \(\dot{x} = F(x)\) and \(\dot{x} = -\nabla V (x)\) are topologically conjugate. Indeed, part (ii) of the proposition implies that the linear flows {e tDF( p)} and {e t Hess(V )( p)} are topologically conjugate (see e.g. Theorem 7.1 in [21]), and by Hartman-Grobman Theorem (see again [21]), nonlinear flows are locally conjugate to their linear parts in the neighborhood of hyperbolic equilibria. However, note that while eigenvalues of Hess(V )( p) are reals there is no evidence that the same is true for DF( p) in general. The next proposition proves that this is the case when L(x) is reversible with respect to π(x). 

Proposition 3

Let \(p \in \mathbf{Eq}(F) \cap \dot{\varDelta }.\) Assume that assumptions of Theorem 3 hold and that L( p) is reversible with respect to π( p) = p. Then there exists a positive definite bilinear form g 0 ( p) on TΔ such that for all u,v ∈ TΔ

$$\displaystyle{g_{0}(\,p)(DF(\,p)u,v) = -\langle \mathit{Hess}(V )(\,p)u,v\rangle }$$

In particular

  1. (i)

    DF( p) has real eigenvalues,

  2. (ii)

    p is hyperbolic for F if and only if it is a non degenerate critical point of V.

Proof

Let \(p \in \mathbf{Eq}(F) \cap \dot{\varDelta }.\) Set L = L( p) and recall that \(L^{T}: T\varDelta \mapsto T\varDelta\) is defined by L T h = hL. Then, by Lemma 8 in the Appendix, − L T is a definite positive operator for the scalar product on T Δ defined by \(\langle u,v\rangle _{1/p} =\sum _{i}u_{i}v_{i} \frac{1} {\,p_{i}}.\) Define now g 0( p) by

$$\displaystyle{ g_{0}(\,p)(u,v) = -\langle (L^{T})^{-1}u,v\rangle _{\frac{ 1} {\,p} }. }$$
(21)

Using (19) and (20) it comes that for all u, v ∈ T Δ

$$\displaystyle{g_{0}(\,p)(DF(\,p)u,v) = -\langle (I - D\pi (\,p))u,v\rangle _{1/p}}$$
$$\displaystyle{= -[\alpha (\,p)s^{{\prime}}(1)]^{-1}\langle \mathit{Hess}(V )(\,p)u,v\rangle.}$$

Replacing g 0( p) by \(\alpha (\,p)s^{{\prime}}(1)g_{0}(\,p)\) proves the result.  ■ 

A useful consequence of this later proposition is that it is usually much easier to verify non degeneracy of equilibria rather than hyperbolicity. Here is an illustration:

Example 6 (Gibbs Systems, 4)

Consider the symmetric Gibbs model analyzed in [10] (see Remark 5 and Example 7). We suppose that the symmetric matrix U = (U ij ) is given and we treat \(U^{0} = (U_{i}^{0})_{i\in S}\) and β as parameters. Let Ξ rev (U 0) denote the set of maps

$$\displaystyle{\mathbb{R}^{+} \times \varDelta \mapsto T\varDelta,}$$
$$\displaystyle{(\beta,x)\mapsto F_{\beta }(x) = xL_{\beta }(x)}$$

such that L β verifies assumption 2, is C 1 in x, and L β (x) is reversible with respect to π β (x) where

$$\displaystyle{\pi _{\beta,i}(x) = \frac{e^{-U_{i}^{0}-\beta \sum _{ j}U_{ij}x_{j}}} {Z(x)}.}$$

Proposition 4

There exists an open and dense set \(\mathcal{G}^{0} \subset \mathbb{R}^{n}\) such that for all \(U^{0} \in \mathcal{G}^{0}\) and \(F \in \varXi _{rev}(U^{0})\)

  1. (i)

    The set \(\{(x,\beta ) \in \varDelta \times \mathbb{R}_{:}^{+}:\: F_{\beta }(x) = 0\}\) is a C ∞ one dimensional submanifold,

  2. (ii)

    There exists an open dense set \(\mathcal{B}^{0} \subset \mathbb{R}^{+}\) containing 0 such that for all \(\beta \in \mathcal{B}^{0}\) equilibria of F β are hyperbolic.

Proof

Let \(H:\dot{\varDelta } \times \mathbb{R}^{n} \times \mathbb{R}^{+}\mapsto T\varDelta\) be defined by \(H(x,U^{0},\beta ) = \nabla V _{U^{0},\beta }(x)\) where \(V _{U^{0},\beta }\) is given by (15). Since \(\frac{\partial H} {\partial U^{0}} (x,U^{0},\beta )\) is the identity map, H is a submersion. Hence, by Thom’s parametrized transversality Theorem (see [12], Chapter 3), there exists an open and dense set \(\mathcal{G}^{0} \in \mathbb{R}^{n}\) such that for all \(U^{0} \in \mathcal{G}^{0},(x,\beta )\mapsto H(x,U^{0},\beta )\) is a submersion. This proves (i). By the same theorem, for all \(\beta \in \mathcal{B}^{0}\) with \(\mathcal{B}^{0}\) open and dense in \(\mathbb{R}^{+},x\mapsto H(x,U^{0},\beta )\) is a submersion, meaning that critical points of \(V _{U^{0},\beta }\) are nondegenerate. By Proposition 3, equilibria of F β are hyperbolic.  ■ 

Remark 9

Other genericity results can be proved, if one fix U 0 or β and treat U as a parameter. Compare to the proof of Theorem 2.10 in [4] in an infinite dimensional setting.

6.1 Equilibria of Potential Games

Consider a population game with C 1 payoff function \(U:\varDelta \mapsto \mathbb{R}^{n}.\) Recall that the game is called a potential game, provided \(U_{i}(x) = -\frac{\partial W} {\partial x_{i}} (x)\) for all x ∈ Δ and some potential \(W: \mathbb{R}^{n}\mapsto \mathbb{R}.\)

Point x ∗ ∈ Δ is called a Nash equilibrium of U if, given the population state x ∗, every agent has interest to play the mixed strategy x ∗. That is

$$\displaystyle{ \forall i \in \{ 1,\ldots,n\}\:U_{i}(x^{{\ast}}) \leq \langle U(x^{{\ast}}),x^{{\ast}}\rangle }$$
(22)

Let

$$\displaystyle{Supp(x^{{\ast}}) =\{ i \in \{ 1,\ldots,n\}:\: x_{ i}^{{\ast}}> 0\}.}$$

It follows from (22) that

$$\displaystyle{\forall i \in Supp(x^{{\ast}})\:U_{ i}(x^{{\ast}}) =\langle U(x^{{\ast}}),x^{{\ast}}\rangle.}$$

We let NE(U) denote the set of Nash equilibria of U. For all β ≥ 0 and x ∈ Δ we let π β (x) ∈ Δ be defined as

$$\displaystyle{ \pi _{\beta,i}(x) = \frac{e^{\beta U_{i}(x)}} {\sum _{j}e^{\beta U_{j}(x)}},\,i = 1,\ldots,n }$$
(23)

and we let χ(β, U) (respectively, χ rev (β, U)) denote the set of all vector fields having the form given by (1) where L(x) is C 1 in x, irreducible and admits π β (x) as invariant (respectively reversible) probability. Recall (see Eq. (9)) that

$$\displaystyle{F_{\pi _{\beta }} = -Id +\pi _{\beta }.}$$

Our aim here is to describe Eq(F) for F ∈ χ(β, U) in term of NE(U) for large β, with a particular emphasis on potential games. Some of the results here are similar to the results obtained in Benaïm and Hirsch (n 2 coordinative games, 2000, unpublished manuscript) for n × 2 pseudo games.

Proposition 5

Let \(\mathcal{N}\) be a neighborhood of NE (U). There exists β 0 ≥ 0 such that for all β ≥β 0 and F ∈χ(β,U)

$$\displaystyle{\mathbf{Eq}(F) \subset \mathcal{N}}$$

Proof

Equilibria of F coincide with equilibria of \(F_{\pi _{\beta }}.\) Let x(β) be such an equilibrium. Then for all i, j

$$\displaystyle{\frac{\log (x_{i}(\beta )) -\log (x_{j}(\beta ))} {\beta } = U_{i}(x(\beta )) - U_{j}(x(\beta )).}$$

Thus for every limit point \(x^{{\ast}} =\lim _{\beta _{k}\rightarrow \infty }x(\beta _{k})\) it follows that

$$\displaystyle{U_{i}(x^{{\ast}}) = U_{ j}(x^{{\ast}})}$$

if i, j ∈ Supp(x ∗) and

$$\displaystyle{U_{i}(x^{{\ast}}) \geq U_{ j}(x^{{\ast}})}$$

if i ∉ Supp(x ∗) and j ∈ Supp(x ∗).   ■ 

Remark 10

Note that Proposition 5 only requires the continuity of U. 

We shall now prove some converse results.

A Nash equilibrium x ∗ is called pure if Supp(x ∗) has cardinal 1 and mixed otherwise. It is called strict if inequality (22) is strict for all i ∉ Supp(x ∗). 

Theorem 5

Let x ∗ be a pure strict Nash equilibrium and \(\mathcal{N}\) a (sufficiently small) neighborhood of x ∗ . Then, there exists β 0 > 0 such that for all β ≥β 0 and F ∈χ(β,U)

  1. (i)

    \(\mathbf{Eq}(F) \cap \mathcal{N} =\{ x_{\beta }^{{\ast}}\}\)

  2. (ii)

    Equilibrium \(x_{\beta }^{{\ast}}\) is linearly stable for \(F_{\pi _{\beta }}.\)

  3. (iii)

    Assume furthermore that the game is a potential game. Then \(x_{\beta }^{{\ast}}\) is linearly stable for F under one of the following conditions:

    1. (a)

      L (hence F) is C 2 and \(x_{\beta }^{{\ast}}\) is hyperbolic for F, or

    2. (b)

      F ∈χ rev (β,U).

Proof

Suppose without loss of generality that \(x_{1}^{{\ast}} = 1\) and \(x_{i}^{{\ast}} = 0\) for i ≠ 1. 

Set \(R_{ij} = U_{j} - U_{i}.\) By assumption and continuity, there exists δ > 0, α > 0 such that for all \(x \in B(x^{{\ast}},\alpha ) =\{ x \in \varDelta \::\| x - x^{{\ast}}\|\leq \alpha \},\)

$$\displaystyle{R_{i1}(x) \geq \delta \mbox{ for }i> 1;}$$
$$\displaystyle{\|R_{ij}(x)\| \geq \delta \mbox{ if }R_{ij}(x^{{\ast}})\neq 0}$$

and

$$\displaystyle{\|R_{ij}(x)\| \leq \delta \mbox{ if }R_{ij}(x^{{\ast}}) = 0.}$$

Thus

$$\displaystyle{1 \geq \pi _{\beta,1}(x) = (1 +\sum _{i>1}e^{-\beta R_{i1}(x)})^{-1} \geq (1 + (n - 1)e^{-\beta \delta })^{-1}.}$$

This implies that π β maps B(x ∗, α) into itself for β large enough. By Brouwer’s Theorem, it then admits a fixed point \(x_{\beta }^{{\ast}}.\) To prove uniqueness and assertion (ii) it suffices to prove that π β restricted to B(x ∗, α) is a contraction. From the expression \(\pi _{\beta,i} = (\sum _{j}e^{\beta R_{ij}})^{-1},\) we get

$$\displaystyle{ \frac{\partial \pi _{\beta,i}} {\partial x_{m}} = -\sum _{j}[\beta e^{\beta R_{ij} }(\sum _{k}e^{\beta R_{ik} })^{-2}\frac{\partial R_{ij}} {\partial x_{m}} ]:=\sum _{j}D_{ij} =\sum _{j\neq i}D_{ij}.}$$

Let j ≠ i. If \(R_{ij}(x^{{\ast}})\neq 0\)

$$\displaystyle{\vert D_{ij}\vert \leq \beta e^{\beta R_{ij} }(1 + e^{\beta R_{ij} })^{-2} \leq \beta \min (e^{\beta R_{ij} },e^{-\beta R_{ij} }) \leq \beta e^{-\beta \delta }.}$$

If R ij (x ∗) = 0. Then i ≠ 1 and

$$\displaystyle{\vert D_{ij}\vert \leq \beta e^{\beta R_{ij} }(e^{\beta R_{i1} })^{-2} =\beta e^{\beta (R_{ij}-2R_{i1})} \leq \beta e^{-\beta \delta }}$$

These inequalities show that \(\|D\pi _{\beta }(x)\| <1\) for all x ∈ B(x ∗, α) and β large enough, proving uniqueness of the equilibrium as well as assertion (ii). The last assertion follows from Propositions 2 and 3.  ■ 

A Nash equilibrium x∗ is called fully mixed if Supp(x ∗) = { 1, …, n} and partially mixed if 1 < card(Supp(x ∗)) < n. 

A fully mixed Nash equilibrium is called non degenerate if for all u ∈ T Δ

$$\displaystyle{\left [\forall w \in T\varDelta \:\langle DU(x^{{\ast}})u,w\rangle = 0\right ] \Rightarrow u = 0.}$$

Let

$$\displaystyle{T\varDelta (x^{{\ast}}) =\{ u \in T\varDelta:\: u_{ i} = 0\mbox{ for }i\not\in Supp(x^{{\ast}})\}.}$$

A partially mixed equilibrium x ∗ is called non degenerate if for all u ∈ T Δ(x ∗)

$$\displaystyle{\left [\forall w \in T\varDelta (x^{{\ast}})\:\langle DU(x^{{\ast}})u,w\rangle = 0\right ] \Rightarrow u = 0,}$$

Lemma 5

Let x ∗ ∈Δ be a mixed equilibria. Assume that Supp(x ∗ ) ={ 1,…,r} for some 1 < r ≤ n and set

$$\displaystyle{x^{{\ast}} = (q_{ 1},\ldots,q_{r-1},1 -\sum _{i=1}^{r-1}q_{ i},0,\ldots,0).}$$

Let, for \(i = 1,\ldots,r - 1,\)

$$\displaystyle\begin{array}{rcl} h_{i}^{r}(x_{ 1},\ldots,x_{r-1},y_{1},\ldots,y_{n-r})& =& U_{i}(x_{1},\ldots,x_{r-1},1 -\sum _{i=1}^{r-1}x_{ i} -\sum _{i=1}^{n-r}y_{ i},y_{1},\ldots,y_{n-r}) {}\\ & -& U_{r}(x_{1},\ldots,x_{r-1},1 -\sum _{i=1}^{r-1}x_{ i} -\sum _{i=1}^{n-r}y_{ i},y_{1},\ldots,y_{n-r}) {}\\ \end{array}$$

Then x ∗ is non degenerate if and only if the \((r - 1) \times (r - 1)\) matrix

$$\displaystyle{\left [\frac{\partial h_{i}^{r}} {\partial x_{j}} ((q,0))\right ]_{i,j=1,\ldots r-1}}$$

is invertible.

Proof

One has

$$\displaystyle{\frac{\partial h_{i}^{r}} {\partial x_{j}} (q,0) = (\frac{\partial U_{i}} {\partial x_{j}} (x^{{\ast}}) -\frac{\partial U_{i}} {\partial x_{r}} (x^{{\ast}})) - (\frac{\partial U_{r}} {\partial x_{j}} (x^{{\ast}}) -\frac{\partial U_{r}} {\partial x_{r}} (x^{{\ast}})).}$$

Let

$$\displaystyle{v = (v_{1},\ldots,v_{r-1},-\sum _{i=1}^{r-1}v_{ i},0,\ldots,0) \in T\varDelta (x^{{\ast}})}$$

and

$$\displaystyle{w = (w_{1},\ldots,w_{r-1},-\sum _{i=1}^{r-1}w_{ i},0,\ldots,0) \in T\varDelta (x^{{\ast}}).}$$

Then it is easily seen that

$$\displaystyle{\sum _{i=1}^{r-1}\sum _{ j=1}^{r-1}\frac{\partial h_{i}^{r}} {\partial x_{j}} (q)v_{i}w_{j} =\langle DU(x^{{\ast}})v,w\rangle.}$$

This proves that x ∗ is non degenerate if and only if \(\left [\frac{\partial h_{i}^{r}} {\partial x_{j}} ((q,0))\right ]_{i,j=1,\ldots r-1}\) is invertible.  ■ 

Theorem 6

Let x ∗ be a non degenerate fully mixed Nash equilibrium for U and \(\mathcal{N}\) a (sufficiently small) neighborhood of x ∗ . Then, there exists β 0 > 0 such that for all β ≥β 0 and F ∈χ(β,U)

$$\displaystyle{\mathbf{Eq}(F) \cap \mathcal{N} =\{ x_{\beta }^{{\ast}}\}.}$$

Assume furthermore that the game is a potential game with potential W. Then \(x_{\beta }^{{\ast}}\) is hyperbolic for F and its unstable manifold (for F) has dimension \(\mathbf{Ind}(x^{{\ast}},W\vert _{\varDelta })\) under one of the following conditions:

  1. (a)

    L (hence F) is C 2 and \(x_{\beta }^{{\ast}}\) is hyperbolic for F, or

  2. (b)

    F ∈χ rev (β,U).

Proof

Set \(T = 1/\beta.\) Equilibria of \(F_{\pi _{\beta }}\) are given by the set of equations

$$\displaystyle{T(\log (x_{i}) -\log (x_{n})) = U_{i}(x) - U_{n}(x),i = 1,\ldots,n - 1}$$

or, with the notation of Lemma 5,

$$\displaystyle{ T(\log (x_{i}) -\log (1 -\sum _{i=1}^{n-1}x_{ i})) = h_{i}^{n}(x_{ 1},\ldots,x_{n-1}),i = 1,\ldots,n - 1. }$$
(24)

Write \(x^{{\ast}} = (q_{1},\ldots,q_{n-1},1 -\sum _{i=1}^{n-1}q_{i}).\) For T = 0, \(q = (q_{1},\ldots,q_{n-1})\) is solution to (24). Hence, by the implicit function theorem (which hypothesis is fulfilled by the non degeneracy of x ∗ and Lemma 5) there exists α 0 > 0, a neighborhood O of q in \((\mathbb{R}_{+}^{{\ast}})^{n-1}\) and a C 1 map \(T \in ] -\alpha _{0},\alpha _{0}[\mapsto q(T) \in O\) such that (T, q(T)) is the unique solution to (24) in \(] -\alpha _{0},\alpha _{0}[\times O.\) This proves the first assertion of the theorem with \(\beta _{0}> 1/\alpha _{0}\) and \(x_{\beta }^{{\ast}} = (q(1/\beta ),1 -\sum _{i=1}^{n-1}q_{i}(1/\beta ))\).

In case, the game is a potential game with potential W, F is gradient-like with Lyapounov function V β given by (16). Since x ∗ is fully mixed, \(\frac{1} {q_{i}} <\infty\) so that \(\|\frac{1} {\beta } \mathit{Hess}V _{\beta }(x_{\beta }^{{\ast}}) -\mathit{Hess}W(x^{{\ast}})\| \rightarrow 0\) as \(\beta \rightarrow \infty.\) In particular, for β large enough \(\mathit{Hess}V _{\beta }(x_{\beta }^{{\ast}})\) is non degenerate, because x ∗ is non degenerate. The last assertion then follows from Propositions 2 and 3.  ■ 

Theorem 7

Let x ∗ be a strict and non degenerate partially mixed Nash equilibrium for U which support has cardinal 1 < r < n. Let \(\mathcal{N}\) be a (sufficiently small) neighborhood of x ∗ . Then, there exists β 0 > 0 such that for all β ≥β 0 and F ∈χ(β,U)

$$\displaystyle{\mathbf{Eq}(F) \cap \mathcal{N} =\{ x_{\beta }^{{\ast}}\}.}$$

Assume furthermore that the game is a potential game with potential W and that one of the following conditions hold:

  1. (a)

    L (hence F) is C 2 and \(x_{\beta }^{{\ast}}\) is hyperbolic for F, or

  2. (b)

    F ∈χ rev (β,U).

Then \(x_{\beta }^{{\ast}}\) is hyperbolic and

$$\displaystyle{k \leq \dim (E_{x_{\beta }^{{\ast}}}^{u}) \leq \min (n - r + k,r - 1).}$$

with \(k = \mathbf{Ind}(x^{{\ast}},W\vert _{\varDelta (x^{{\ast}})})\) and \(\dim (E_{x_{\beta }^{{\ast}}}^{u})\) stands for the dimension of the unstable manifold (for F).

Proof

Assume without loss of generality that \(Supp(x^{{\ast}}) =\{ 1,\ldots,r\}\) and set \(x^{{\ast}} = (q_{1},\ldots,q_{r-1},1 -\sum _{i=1}^{r-1}q_{i},0,\ldots,0).\) Write every element of Δ as \((x_{1},\ldots,x_{r-1},1 -\sum _{i=1}^{r-1}x_{i} -\sum _{i=1}^{n-r}y_{i},y_{1},\ldots y_{n-r})\) and set \(x = (x_{1},\ldots,x_{r-1}),y = (y_{1},\ldots,y_{n-r}).\) Thus, with \(\beta = 1/T,\) equilibria of \(F_{\pi _{\beta }}\) are given by the following system of equations:

$$\displaystyle{ T(\log (x_{i}) -\log (1 -\sum _{i=1}^{r-1}x_{ i} -\sum _{i=1}^{n-r}y_{ i})) = h_{i}^{r}(x,y),i = 1,\ldots r - 1 }$$
(25)

and

$$\displaystyle{ T(\log (y_{i}) -\log (1 -\sum _{i=1}^{r-1}x_{ i} -\sum _{i=1}^{n-r}y_{ i})) = h_{i+r}^{r}(x,y),i = 1\ldots n - r }$$
(26)

where \(h_{i}^{r}\) is defined in Lemma 5. The triplet \((T = 0,x = q,y = 0)\) is solution to (25). Thus by the non degeneracy hypothesis and the implicit function theorem, there exists a smooth map

$$\displaystyle{\hat{x}: \mathcal{O}\mapsto \mathcal{V},(T,y)\mapsto \hat{x}(T,y)}$$

where \(\mathcal{O}\) is a neighborhood of (0, 0) in \(\mathbb{R} \times \mathbb{R}^{n-r}\) and \(\mathcal{V}\) a neighborhood of \(q\) in \(\mathbb{R}^{r-1}\) such that \((T,\hat{x}(T,y),y)\) is solution to (25). Recall that \(0 <\sum _{ i=1}^{r-1}q_{i} <1\) and \(h_{i+r}^{r}(q,0) <0\) for all \(i = 1,\ldots,n - r\) (because x ∗ is strict). Thus, by choosing \(\mathcal{O}\) small enough we can furthermore ensure that

$$\displaystyle{ 0 <1 -\sum _{i=1}^{r-1}\hat{x}_{ i}(T,y) -\sum _{i=1}^{n-r}y_{ i} <1 }$$
(27)

and

$$\displaystyle{ h_{i+r}^{r}(\hat{x}(T,y),y) \leq -\delta <0,i = 1\ldots n - r }$$
(28)

for all \((T,y) \in \mathcal{O}.\)

Now replacing x by \(\hat{x}(T,y)\) in (26) leads to

$$\displaystyle{y_{i} = G_{i}(T,y),i = 1\ldots n - r}$$

where

$$\displaystyle{G_{i}(T,y) = (1 -\sum _{i=1}^{r-1}\hat{x}_{ i}(T,y) -\sum _{i=1}^{n-r}y_{ i})\exp ( \frac{1} {T}h_{i+r}^{r}(\hat{x}(T,y),y)).}$$

Using (27) and (28) we see that α small enough and \(T \leq \frac{\log (1/\alpha )} {\delta }\) G(T, ⋅ ) maps \(\{y \in \mathbb{R}^{n-r}:\: 0 \leq y_{i} \leq \alpha \}\) into itself. By Brouwer’s fixed point theorem, G(T, ⋅ ) admits a fixed point \(\hat{y}(T).\) Furthermore, \(\|D_{y}G(T,y)\| \leq \frac{C} {T}e^{-\delta /T}\) for some constant C making G(T, ⋅ ) a contraction. This implies that \(\hat{y}(T)\) is unique. Finally define \(x_{\beta }^{{\ast}}\) by \(x_{\beta,i}^{{\ast}} =\hat{ x}_{i}(T,\hat{y}(T))\) for 1 ≤ i < r and \(x_{\beta,i+r}^{{\ast}} =\hat{ y}_{i}(T)\) for 1 ≤ 1 ≤ n − r. 

We now prove the last assertions. By assumption, T Δ(x ∗) admits a decomposition \(T\varDelta (x^{{\ast}}) = E_{+} \oplus E_{-}\) with \(\langle \mathit{Hess}(W)(x^{{\ast}})u,u\rangle> 0\) (respectively < 0) for all u ∈ E + (respectively E −) and u ≠ 0. 

Set \(T\varDelta _{s}(x^{{\ast}}) =\{ u \in T\varDelta:\: u_{1} =\ldots = u_{r} = 0\}.\) Then

$$\displaystyle{T\varDelta = E_{+} \oplus E_{-}\oplus T\varDelta _{s}(x^{{\ast}}).}$$

Let now V β be the Lyapounov function given (16). Then for all u ∈ T Δ

$$\displaystyle{Q_{\beta }(u):=\langle \frac{1} {\beta } \mathit{Hess}(V _{\beta })(x_{\beta }^{{\ast}})u,u\rangle =\langle \mathit{Hess}W(x_{\beta }^{{\ast}})u,u\rangle + \frac{1} {\beta } \sum _{i} \frac{1} {x_{\beta,i}^{{\ast}}}u_{i}^{2}.}$$

The construction of \(x_{\beta }^{{\ast}}\) shows that \(\frac{1} {\beta } \frac{1} {x_{\beta,i}^{{\ast}}} \rightarrow 0\) for i ≤ r and \(\frac{1} {\beta } \frac{1} {x_{\beta,i}^{{\ast}}} \rightarrow \infty\) for i > r when \(\beta \rightarrow \infty.\) Thus, for β large enough, Q β is non degenerate, definite positive on E + and \(T\varDelta _{s}(x^{{\ast}}),\) and definite negative on E −. 

This implies that its index is bounded below by \(k =\dim (E_{-})\) and above by \(\min (r - 1,n - r - k).\) This index equals the dimension of the stable manifold by Proposition 2. Under the reversibility assumption hyperbolicity follows from Proposition 3.  ■ 

7 Reversibility and Gradient Structure

Recall that an irreducible rate matrix L is called reversible with respect to \(\pi \in \dot{\varDelta }\) is \(\pi _{i}L_{ij} =\pi _{j}L_{ji}.\) In this case π is the (unique) invariant probability of L. Here we will consider gradient properties of (1) under the assumption that L(x) is reversible.

A C k, k ≥ 0 (Riemannian) metric on \(\dot{\varDelta }\) (or Δ) is a C k map g such that for each x ∈ Δ \(g(x): T\varDelta \times T\varDelta \mapsto \mathbb{R}\) is a definite positive bilinear form. Given a C 1 map \(V:\dot{\varDelta } \mapsto \mathbb{R}\) we let grad g V denote the gradient vector field of V with respect to g. That is

$$\displaystyle{g(x)(grad_{g}V (x),u) =\langle \nabla V (x),u\rangle }$$

for all u ∈ T Δ. 

Proposition 6

Assume that for all \(x \in \dot{\varDelta }\) L(x) is reversible with respect to π(x) and assume that the map \(h:\dot{\varDelta } \mapsto \mathbb{R}^{n},\) defined by

$$\displaystyle{h(x) = \frac{x} {\pi (x)}}$$

is a α-quasigradient. Then there exists a metric g on \(\dot{\varDelta }\) such that for all \(x \in \dot{\varDelta }\) \(F(x) = -grad_{g}V (x).\) If L and α are C k then g is C k .

Proof

The proof is similar to the proof of Proposition 3. Let \(A(x): T\varDelta \mapsto T\varDelta\) be defined by \(A(x)h = -hL(x).\) Then A(x) and L(x) are conjugate by the relation π(x)L(x)h = A(x)π(x)h and A(x) is a definite positive operator for the scalar product on T Δ defined by \(\langle u,v\rangle _{1/\pi (x)} =\sum _{i}u_{i}v_{i} \frac{1} {\pi _{i}(x)}.\) Define now a Riemannian metric on T Δ by

$$\displaystyle{ g_{0}(x)(u,v) =\langle A(x)^{-1}u,v\rangle _{ \frac{ 1} {\pi (x)} }. }$$
(29)

Since \(F(x) = xL(x) = (x -\pi (x))L(x) = A(x)(-x +\pi (x)),\) we get

$$\displaystyle{g_{0}(x)(F(x),u) = -\langle \frac{x} {\pi (x)} - 1,u\rangle = -\langle \frac{x} {\pi (x)},u\rangle.}$$

If \(x\mapsto \frac{x} {\pi (x)}\) is a quasi gradient, this makes F a gradient for the metric g(x) = α(x)g 0(x).   ■ 

Example 7

Suppose that L(x) is reversible with respect to π, independent on x. Then \(x\mapsto \frac{x} {\pi }\) is the gradient of the χ 2 function \(V (x) =\sum _{i}(\frac{x_{i}} {\pi _{i}} - 1)^{2}\pi _{i}.\) Hence \(F(x) = -grad_{g}V (x)\) for some metric g.

Under the weaker assumption that \(x\mapsto s( \frac{x} {\pi (x)})\) is a quasi-gradient for some strictly increasing function s (see Theorem 3) it is no longer true that F is a gradient, but it can be approximated by a gradient. The next Lemma is the key tool. Its proof is identical to the proof of Proposition 3.

Lemma 6

Assume that assumptions of Theorem 3 hold and that for all \(x \in \dot{\varDelta },L(x)\) is reversible with respect to π(x). Then there exists a metric g 0 on \(\dot{\varDelta }\) such that for \(p \in \mathbf{Eq}(F)\cap \dot{\varDelta }\) and u,v ∈ TΔ

$$\displaystyle{g_{0}(\,p)(DF(\,p)u,v) = -\langle \mathit{Hess}(V )(\,p)u,v\rangle.}$$

If, furthermore, L and α (in Eq.  (13) ) are C k then g 0 is C k .

Theorem 8

Assume that

  1. (a)

    Assumptions of Theorem 3 hold with s,α and L C k ,k ≥ 2,

  2. (b)

    For all \(x \in \dot{\varDelta }\) L(x) is reversible with respect to π(x),

  3. (c)

    \(\mathbf{Eq}(F)\cap \dot{\varDelta }\) is finite.

Then for every neighborhood \(\mathcal{U}\) of \(\mathbf{Eq}(F)\cap \dot{\varDelta }\) and every \(\varepsilon> 0\) there exists a C k metric g on \(\dot{\varDelta }\) such that

  1. (i)

    \(-grad_{g}V = F\) on \(\dot{\varDelta }\setminus \mathcal{U}.\)

  2. (ii)

    \(\|-grad_{g}V - F\|_{C^{1},\mathcal{U}}\leq \varepsilon\) where

    $$\displaystyle{\|G\|_{C^{1},\mathcal{U}} =\sup _{x\in \mathcal{U}}\|G(x)\| +\| DG(x)\|.}$$

Proof

Let \(\mathcal{E} =\dot{\varDelta } \cap \mathbf{Eq}(F),\) \(v(x) = d(x,\mathcal{E}) =\min _{p\in \mathcal{E}}\|x - p\|\) and let \(\psi: \mathbb{R}^{+}\mapsto [0,1]\) be a C ∞ function which is 0 on [0, 1], 1 on [3, ∞[ and such that 0 ≤ ψ ′ ≤ 1. Fix \(\varepsilon> 0\) and let \(\lambda (x) =\psi (\frac{v(x)} {\varepsilon } ),\) \(G_{0} = -grad_{g_{0}}V\) where g 0 is given by Lemma 6 and

$$\displaystyle{G(x) = (1 -\lambda (x))G_{0}(x) +\lambda (x)F(x).}$$

Since for all \(p \in \mathcal{E},F(\,p) - G_{0}(\,p) = DF(\,p) - DG_{0}(\,p) = 0\) there exists a constant C > 0 such that

$$\displaystyle{\|G_{0}(x) - F(x)\| \leq Cv(x)^{2},\;\|DG_{ 0}(x) - DF(x)\| \leq Cv(x).}$$

Thus

$$\displaystyle{\|G(x) - F(x)\| = (1 -\lambda (x))\|G_{0}(x) - F(x)\| \leq C(1 -\lambda (x))v(x)^{2} \leq C\varepsilon ^{2}}$$

and

$$\displaystyle{\|DG(x) - DF(x)\| =\| (1 -\lambda (x))(DG_{0}(x) - DF(x)) +\langle \nabla \lambda (x),G_{0}(x) - F(x)\rangle \|}$$
$$\displaystyle{\leq C((1 -\lambda (x))v(x) + \frac{1} {\varepsilon } v(x)^{2}) \leq C\varepsilon.}$$

This shows that G is a C 1 approximation of F which coincides with F on \(\{v(x) \geq 3\varepsilon \}\) and with G 0 on \(\{v(x) \leq \varepsilon \}.\) Furthermore,

$$\displaystyle{\langle \nabla V (x),G(x)\rangle = -(1 -\lambda (x))g_{0}(x)(G_{0}(x),G_{0}(x)) +\lambda (x)\langle \nabla V (x),F(x)\rangle \leq 0}$$

with equality if and only if \(x \in \mathcal{E}.\)

Now, for all \(x \in \dot{\varDelta }\setminus \mathcal{E}\)

$$\displaystyle{T\varDelta = \nabla V (x)^{\perp }\oplus \mathbb{R}G(x)}$$

and the splitting is smooth in x. Hence u ∈ T Δ can be uniquely written as \(u = P_{x}(u) + t_{x}(u)G(x)\) with \(t_{x}(u) \in \mathbb{R}\) and \(P_{x}(u) \in \nabla V (x)^{\perp }.\) Let g be the metric on \(\dot{\varDelta }\setminus \mathcal{E}\) defined by

$$\displaystyle{g(x)(u,v) = g_{0}(P_{x}(u),P_{x}(v)) + t_{x}(u)t_{x}(v)g_{0}(x)(G_{0}(x),G(x)).}$$

Then g coincides with g 0 on \(\{0 <x <v(x) <\varepsilon \}\) so that g can be extended to a C 2 metric on \(\dot{\varDelta }.\) By construction of G and g, \(G = -grad_{g}V.\)  ■ 

8 Questions of Structural Stability

Let \(C_{pos}^{k}(\varDelta,T\varDelta )\) denote the set of C k vector fields \(F:\varDelta \mapsto T\varDelta\) leaving Δ positively invariant.

Two elements \(F,G \in C_{pos}^{k}(\varDelta,T\varDelta )\) are said topologically equivalent if there exists a homeomorphism \(h:\varDelta \mapsto \varDelta\) which takes orbits of F to orbits of G preserving their orientation. A set \(\chi \subset C_{pos}^{k}(\varDelta,T\varDelta )\) is said structurally stable if all its elements are topologically equivalents.

Let \(\pi:\varDelta \mapsto \dot{\varDelta }\) be a smooth function. Assume that π verifies the assumption of Theorem 3 and that F π has non degenerate equilibria. Let χ π, rev denote the convex set of vector fields having the form given by (the right hand side of) (1), where for each x ∈ Δ, L(x) is irreducible and reversible with respect to π(x). By Theorem 3, Proposition 3 and Theorem 8 all the elements of χ π, rev have the same strict Lyapounov function V, hyperbolic equilibria (given by the critical points of V ) and are C 1 close to − grad g V for some metric g. We may then wonder wether χ π, rev is structurally stable. The following construction shows that this is not the case.

8.1 Potential Games are not Structurally Stable

Here Δ stands for the two-dimensional simplex in \(\mathbb{R}^{3}.\) Let

$$\displaystyle{\tilde{\varDelta }=\{ (y_{1},y_{2}) \in \mathbb{R}^{2}\:: y_{ 1},y_{2} \geq 0,\:y_{1} + y_{2} \leq 1\}}$$

and \(\jmath: \mathbb{R}^{3}\mapsto \mathbb{R}^{2}\) be the projection defined by \(\jmath(x_{1},x_{2},x_{3}) = (x_{1},x_{2}).\) Note that \(\jmath\) maps Δ homeomorphically onto \(\tilde{\varDelta }.\)

Let \(\tilde{W}: \mathbb{R}^{2}\mapsto \mathbb{R}\) be a smooth function. Assume that

  1. (a)

    \(-\nabla \tilde{W}\) points inward \(\tilde{\varDelta }\) on \(\partial \tilde{\varDelta };\)

  2. (b)

    The critical set \(crit(\tilde{W}) =\{ y \in \tilde{\varDelta }:\: \nabla \tilde{W}(y) = 0\}\) consist of (finitely many) non degenerate points,

  3. (c)

    For all \(u \in \mathbb{R}\)

    $$\displaystyle{\frac{\partial \tilde{W}} {\partial y_{1}} (u,u) = \frac{\partial \tilde{W}} {\partial y_{2}} (u,u).}$$

    In particular, the diagonal \(D(\tilde{\varDelta }) =\{ (y_{1},y_{2}) \in \tilde{\varDelta }:\: y_{1} = y_{2}\}\) is positively invariant under the dynamics

    $$\displaystyle{ \dot{y} = -\nabla \tilde{W}(y) }$$
    (30)
  4. (c)

    There is a saddle connection contained in \(D(\tilde{\varDelta }),\) meaning that there are two saddle points of \(\tilde{W}\) \(s^{1},s^{2} \in D(\tilde{\varDelta })\) and some (hence every) point \(y \in ]s^{1},s^{2}[\) which α limit set under (30) is s 1 and omega limit set is s 2. 

It is not hard to construct such a map.

Let \(W: \mathbb{R}^{3}\mapsto \mathbb{R}\) be defined by \(W =\tilde{ W}\circ\jmath.\)

Consider now the 3-strategies potential game associated to W. Payoffs are then defined by

$$\displaystyle{U_{i}(x) = -\frac{\partial \tilde{W}} {\partial x_{i}} (x_{1},x_{2}),i = 1,2\mbox{ and }U_{3}(x) = 0.}$$

Using the notation of Sect. 6.1, record that \(F_{\pi _{\beta }} = -Id +\pi _{\beta }\) where π β is defined by (23), and χ rev (β, U) is the set of vector fields given by (1) with L(x) irreducible and reversible with respect to π β (x). 

Proposition 7

For all β > 0 sufficiently large, there exists F ∈χ rev (β,U) (which can be chosen C 1 close to \(F_{\pi _{\beta }}\) ) which is not equivalent to \(F_{\pi _{\beta }}.\)

Proof of Proposition 7

By definition of Nash equilibria (see Sect. 6.1) and condition (a) above, Nash equilibria of U are fully mixed and coincide with critical points of \(\tilde{W}:\)

$$\displaystyle{crit(\tilde{W}) =\jmath(\mathbf{NE}(U)).}$$

Lemma 7

For all \(\varepsilon> 0\) there exists β 0 > 0 such that for all β ≥β 0 and \(F \in \chi _{rev}(\beta,U)\) there is a one to one map

$$\displaystyle{p \in crit(\tilde{W})\mapsto p_{\beta } \in \mathbf{Eq}(F),}$$

such that

  1. (i)

    \(\|p-\jmath(\,p_{\beta })\| \leq \varepsilon,\)

  2. (ii)

    The unstable (respectively stable) manifold of p β has dimension \(\mathbf{Ind}(\,p,\tilde{W},)\) (resp. \(2 -\mathbf{Ind}(\,p,\tilde{W})\) ). In particular, \(s_{\beta }^{1}\) and \(s_{\beta }^{2}\) are saddle points.

  3. (iii)

    \(p \in D(\tilde{\varDelta }) \Leftrightarrow\jmath(\,p_{\beta }) \in D(\tilde{\varDelta })\)

  4. (iv)

    Under the dynamics induced by \(F_{\pi _{\beta }},\) the interval \([s_{\beta }^{1},s_{\beta }^{2}]\) is invariant and for some (hence all) \(q \in ]s_{\beta }^{1},s_{\beta }^{2}[\) the alpha limit (respectively omega limit) set of q equals \(s_{\beta }^{1}\) (respectively \(s_{\beta }^{2}\) ).

Proof

Assertions (i) and (ii) this follows from Propositions 5 and 6.

On \(\jmath^{-1}(D(\tilde{\varDelta })) =\{ (x_{1},x_{1},1 - 2x_{1})\}\) equilibria of \(F_{\pi _{\beta }}\) are given by the implicit equation \(T(\log (x_{1}) -\log (1 - 2x_{1})) = U_{1}(x_{1},x_{1})\) where \(T = 1/\beta.\) Solutions for T = 0 coincide with \(\jmath^{-1}(D(\tilde{\varDelta }) \cap crit(\tilde{W})).\) For T > 0 and small enough, assertion (iii) then follows from the implicit function theorem.

By condition (c), \(\frac{\partial \tilde{W}} {\partial x_{1}} = \frac{\partial \tilde{W}} {\partial x_{2}}\) on \(D(\tilde{\varDelta }).\) Thus \(U_{1}(x) = U_{2}(x)\) (hence \(F_{\pi _{\beta,1}}(x) = F_{\pi _{\beta,2}}(x))\) on \(\jmath^{-1}(D(\tilde{\varDelta }))\) proving invariance of \([s_{\beta }^{1},s_{\beta }^{2}] \subset\jmath^{-1}(D(\tilde{\varDelta })).\) Assertion (iv) follows since, by (iii), there are no equilibria in \(]s_{\beta }^{1},s_{\beta }^{2}[.\)  ■ 

We now construct F ∈ χ rev (β, U). Let L(x) be the rate matrix defined for i ≠ j by

$$\displaystyle{L_{ij}(x) =\pi _{\beta,j}(x)\mbox{ if }i,j\not\in \{1,3\}}$$
$$\displaystyle{L_{13}(x) = (1 + a(x))\pi _{\beta,3}(x)\mbox{ and }L_{31}(x) = (1 + a(x))\pi _{\beta,1}(x)}$$

where \(a:\varDelta \mapsto \mathbb{R}^{+}\) is a smooth function to be defined below. Then Eq. (1) reads

$$\displaystyle\begin{array}{rcl} \dot{x_{1}}& =& (x_{2}\pi _{\beta,1}(x) - x_{1}\pi _{\beta,2}(x)) + (x_{3}\pi _{\beta,1}(x) - x_{1}\pi _{\beta,3}(x))(1 + a(x)), {}\\ \dot{x_{2}}& =& (x_{1}\pi _{\beta,2}(x) - x_{2}\pi _{\beta,1}(x)) + (x_{3}\pi _{\beta,2}(x) - x_{2}\pi _{\beta,3}(x)), {}\\ \dot{x_{3}}& =& -\dot{x_{1}} -\dot{ x_{2}}. {}\\ \end{array}$$

Thus, on \(x_{1} = x_{2},\)

$$\displaystyle{\dot{x_{1}} -\dot{ x_{2}} = [x_{3}\pi _{\beta,1}(x) - x_{1}\pi _{\beta,3}(x)]a(x)}$$
$$\displaystyle{= \frac{a(x)} {Z(x)}(x_{3}e^{\beta U_{1}(x)} - x_{ 1}).}$$

The map \(x\mapsto x_{3}e^{\beta U_{1}(x)} - x_{1}\) vanishes at points \(s_{\beta }^{1},s_{\beta }^{2}\) and has a constant sign over \([s_{\beta }^{1},s_{\beta }^{2}]\) (for otherwise there would exists an equilibrium for F in \(]s_{\beta }^{1},s_{\beta }^{2}[\) contradicting Lemma 7). Let \(p = (s_{\beta }^{1} + s_{\beta }^{2})/2\) and B η be the Euclidean open ball with center p and radius η. Choose η small enough so that

  1. (i)

    \(B_{\eta } \cap [s_{\beta }^{1},s_{\beta }^{2}] =]q^{1},q^{2}[\) with \(s_{\beta }^{1} <q^{1} <q^{2} <s_{\beta }^{2}\) where < stands for the natural ordering on \([s_{\beta }^{1},s_{\beta }^{2}].\)

  2. (ii)

    \(x\mapsto x_{3}\pi _{\beta,1}(x) - x_{1}\pi _{\beta,3}(x)\) has constant sign on B η . 

Let \(x\mapsto a(x)\) be such a = 0 on \(\varDelta \setminus B_{\eta },\) a > 0 on B η and 0 ≤ a ≤ η on Δ. Then, the alpha limit set of q 1 equals \(s_{\beta }^{1},\) for both F and \(F_{\pi _{\beta }}\) but since \(\dot{x_{1}} -\dot{ x_{2}}\) doesn’t vanish on B η the trajectory through q 1 exits B η at a point ≠ q 2 and, consequently, the omega limit set of q 1 for F is distinct from \(s_{\beta }^{2}.\) This proves that F and \(F_{\pi _{\beta }}\) are not equivalent.

8.2 Open Question

The preceding construction shows that χ rev (β, U) is not structurally stable for an arbitrary potential game but this might be the case for particular examples. Consider for example the Gibbs model described in Remark 5. For \(U^{0} \in \mathbb{R}^{n}\) and U = (U ij ) symmetric, let \(\chi _{rev}(\beta,U^{0},U)\) be the set of C 1 vector field given by (1) with L(x) irreducible and reversible with respect to the Gibbs measure (14).

Question

For generic (U 0, U) and β large enough, is \(\chi _{rev}(\beta,U^{0},U)\) structurally stable?