On imitation dynamics in potential population games

arXiv:1709.04748v1 [] 13 Sep 2017

Lorenzo Zino, Giacomo Como, and Fabio Fagnani

Abstract— Imitation dynamics for population games are studied and their asymptotic properties analyzed. In the considered
class of imitation dynamics —that encompass the replicator
equation as well as other models previously considered in
evolutionary biology— players have no global information
about the game structure, and all they know is their own current
utility and the one of fellow players contacted through pairwise
interactions. For potential population games, global asymptotic
stability of the set of Nash equilibria of the sub-game restricted
to the support of the initial population configuration is proved.
These results strengthen (from local to global asymptotic
stability) existing ones and generalize them to a broader class
of dynamics. The developed techniques highlight a certain
structure of the problem and suggest possible generalizations
from the fully mixed population case to imitation dynamics
whereby agents interact on complex communication networks.

I. I NTRODUCTION
Imitation dynamics provide a powerful game-theoretic
paradigm used to model the evolution of behaviors and
strategies in social, economic, and biological systems [1],
[2], [3]. The assumption beyond these models is that individuals interact in a fully mixed population having no
global information about the structure of the game they are
playing. Players just measure their own current utility and, by
contacting other individuals, they get aware of the the action
currently played by them and of the associated utility. Then,
in order to increase their utility, players may revise their
action and adopt the one of the contected fellow players.
We focus on the asymptotic behavior of such imitation
dynamics. Available result in this area can be found in [4],
[5], [6], [7]. In particular, [7] contains a study of local
stability and instability for the different kinds of rest points of
such dynamics. These results, however, deal only with local
stability, therefore one can not conclude global asymptotic
stability. Indeed, only for specific dynamics, such as the
replicator equation, and for some specific classes of games, a
global analysis has been carried on [8], [9], [10], [11], [12].
This work contributes to expanding the state of the art
on the analysis of the asymptotic behavior of imitation
dynamics. For the important class of potential population
games, we obtain a global convergence result, Theorem 6,
that is stronger and more general than the results presented
in the literature. Another novelty of this work consists in the
definition of imitation dynamics, that is more general than
the classical one [7].
The authors are with the “Lagrange” Department of Mathematical Sciences, Politecnico di Torino, 10129 Torino, Italy {lorenzo.zino,

The paper is organized as follows. Section II is devoted
to the introduction of population games and to the definition
of the class of imitation dynamics. Both these concepts are
presented along with some explanatory examples. Thereafter,
the main results on the asymptotic behavior of the imitation
dynamics are presented and proved in Section III. Examples
of the use of these results will then be presented in Section
IV. Finally, Section V discusses some future research lines.
Before moving to the next section, let us define the
following notation: δ (i) denotes a vector of all zeros but a 1 in
the ith position. We denote the sets of reals and nonnegative
reals by R and R+ = {x ∈ R : x ≥ 0}, respectively.
II. P OPULATION G AMES AND I MITATION DYNAMICS
Throughout the paper we study imitation dynamics in
continuous population games. In such setting, a continuum
of players of total unitary mass choose actions from a finite
set A and the reward ri (x) of all those players playing
action i ∈ A is a function of the empirical distribution x
of the actions played
P across the population. Formally, let
:
X = x ∈ RA
+
i∈A xi = 1 be the unitary simplex over
the action set A and refer to vectors x ∈ X as configurations
of the population. If the population is in configuration x ∈ X ,
then a fraction xi of the players is playing action i, for i ∈ A.
Let r : X → RA be reward vector function whose entries
ri (x) represent the reward received by any player playing
action i ∈ A when the population is in configuration x ∈ X .
Throughout, we assume the reward vector function r(x) to
be Lipschitz-continuous over the configuration space X . Let
X
r∗ (x) := max ri (x) ,
r(x) :=
xi ri (x)
i∈A

i∈A

stand for the maximum and, respectively, the average rewards
in a configuration x ∈ X . Then, the set of Nash equilibria
of the considered continuous population game is denoted by
N = {x ∈ X : xi > 0 ⇒ ri (x) = r∗ (x)} .

(1)

As is known, every continuous population game admits a
Nash equilibrium [7, Theorem 2.1.1], so N is never empty.
Example 1 (Linear reward population games): A class of
continuous population games is the one where the rewards
are linear functions of the configuration, i.e., when
r(x) = Rx ,

(2)

giacomo.como, fabio.fagnani}@polito.it
L. Zino is also with the “Peano” Department of Mathematics, Università
di Torino, 10123 Torino, Italy lorenzo.zino@unito.it
G. Como is also with the Department of Automatic Control, Lund University, 22100 Lund, Sweden giacomo.como@control.lth.se

for some reward matrix R ∈ RA×A . Linear reward population games have a standard interpretation in terms of
symmetric 2-player games [1] played by each player against

the average population [13]. Population games with binary
action space A = {1, 2} and linear reward function (2) with


a b
R=
(3)
c d
can be grouped in the following three classes:
(i) for a > c and d > b, one has binary coordination games
[14], [15] (such as the stag hunt game [16]), where the
set of Nash equilibria N = {δ (1) , δ (2) , x} comprises the
two pure configurations and the interior point x̄ with
x̄1 = 1 − x̄2 = (d − b)/(a − c + d − b) ;
(ii) for a < c and d < b, one has anti-coordination games
(including hawk-dove game [17], [18]), where the only
Nash equilibrium is the interior point x̄ as above;
(iii) for other cases of the parameters (e.g., in the Prisoner’s
dilemma [15]), there is one of the two actions i that is
(possibly weakly) dominating the other one j, and the
pure configuration δ (i) is the only Nash equilibrium.
Larger action spaces admit no as simple classifications.
In this paper, we are concerned with imitation dynamics
arising when players in the population modify their actions
in response to pairwise interactions [3]. We assume that the
population is fully mixed so that any pairs of players in
the population meet with the same frequency [19]. Upon a
possible renormalization, the overall frequency of pairwise
interactions between agents playing actions i and j can
then be assumed equal to the product xi xj of the fraction
of players currently playing actions i and j, respectively.
When two players meet, they communicate to each other the
action they are playing and the rewards they are respectively
getting. Then, depending on the difference between the two
rewards and possibly other factors, each interacting player
either keeps playing the same action he/she is playing, or
updates his/her action to the one of the other player.
Definition 1 (Imitation dynamics): A
(deterministic,
continuous-time) imitation dynamics for a continuous
population game with action set A and reward function
vector r(x) is the system of ordinary differential equations
X
ẋi = xi
xj (fji (x) − fij (x)) i ∈ A ,
(4)
j∈A

where, for i, j ∈ A, the function fij (x) is Lipschitzcontinuous on the configuration space X and such that
sgn (fij (x) − fji (x)) = sgn (rj (x) − ri (x)) , x ∈ X . (5)
Equivalently, the imitation dynamics (4) may be rewritten as
ẋ = diag (x)(F T (x) − F (x))x ,

(6)

where F (x) = (fij (x))i,j is a matrix-valued function on X .
Observe that, in order to satisfy (5), the functions fij s
should clearly depend on the difference between the rewards
ri (x) − rj (x) in such a way that fij (x) = fji (x), for every
configuration x such that ri (x) = rj (x). In principle, these
functions can possibly depend on the whole configuration x

in a non-trivial way. However, while our results hold true
in such greater generality, we are mostly concerned with the
case where the functions fij (x) only depend on the rewards’
differences ri (x) − rj (x), possibly in a different way for
each different pair of actions i, j ∈ A. In fact, in this case,
the considered imitation dynamics model makes minimal
assumptions on the amount of information available to the
players, i.e., they only know their own current action, the
one of the other player met, and difference of their respective
current rewards. In particular, players need not to know any
other information about the game they are engaged in, such
as, e.g., the current configuration of the population, the form
of the reward functions, or even the whole action space.
Remark 1: This class of imitation dynamics generalize the
ones considered in many papers [7], which satisfy
ri (x) ≥ rj (x) ⇐⇒ fki (x) − fik (x) ≥ fkj (x) − fjk (x) ,
(7)
for every i, j, k ∈ A. In fact, it is straightforward to check
that (7) is in general more restrictive than (5), that is obtained
from (7) in the case k = j. Notably, (7) induces an ordering
of the actions such that, when comparing two of them, the
one with the larger reward should always result the more
appealing to any third party, quite a restrictive condition that
is not required in our more general formulation. Example 3,
which follows, is a concrete example of a realistic situation
in which our relaxed condition (5) holds and (7) does not.
We now present two examples of imitation dynamics.
Example 2 (Replicator Dynamics): In the case when
1
(rj (x) − ri (x)) ,
2

i, j ∈ A ,

or, equivalently, F (x) = 12 1rT (x) − r(x)1T , the imitation dynamics (4) reduces to the replicator equation
fij (x) =

ẋi = xi (ri (x) − r(x)) ,

i ∈ A.

(8)

Hence, imitation dynamics encompass and generalize the
replicator equation, for which an extensive analysis has been
developed, see, e.g., [1], [13], [20], [21].
Example 3 (Stochastic Imitation Dynamics): Let
1
1
+ arctan(Kij (rj (x) − ri (x))) ,
(9)
2 π
for i, j ∈ A, where Ki,j > 0. Such [0, 1]-valued functions
fij (x) have an immediate interpretation as probabilities that
players playing action i switch to action j when observing
others playing such action j. Therefore these dynamics
might be used when modeling mean-filed limits of stochastic
imitation dynamics [22]. If the positive constants Kij are
not all the same, the associated imitation dynamics may not
satisfy (7), but still fit in our framework.
fij (x) =

We now move on to discussing some general properties of
imitation dynamics in continuous population games. To this
aim, we first introduce some more notions related to Nash
equilibria. For a nonempty subset of actions S ⊆ A, let
XS = {x ∈ X : xi = 0, ∀ i ∈ A \ S}

be the subset of configurations supported on S and let
NS = {x ∈ XS : xi > 0 ⇒ ri (x) ≥ rj (x), ∀ j ∈ S} (10)
be the set of Nash equilibria of the population game restricted
to S. Clearly, XA = X and NA = N . Finally, we define the
set of critical configurations as
[
Z=
NS .
(11)
∅6=S⊆A

Observe that Z includes the set of Nash equilibria N and
can equivalently be characterized as
Z = {x ∈ X : xi > 0 ⇒ ri (x) = r(x)} .

(12)

Remark 2: The set Z always includes the vertices δ (i) , i ∈
A, of the simplex X . In fact, in the case when |A| = 2, the
set of critical configurations consists just of the two vertices
of X and the possible interior Nash equilibria of the game.
For |A| ≥ 3, the set of critical configurations Z includes,
besides vertices of X and Nash equilibria of the game, all
Nash equilibria of the sub-games obtained by restricting the
action set to a non-trivial action subset S ⊆ A.
Some basic properties of the imitation dynamics (4) are
gathered in the following Lemma. These results are already
proven in [7] under the more restrictive condition on the
dynamics. For the proof in our more general setting is
included in the Appendix.
Lemma 2: For any imitation dynamics (4) satisfying (5):
(i) if x(0) ∈ XS for some nonempty subset of actions S ⊆
A, then x(t) ∈ XS for all t ≥ 0;
(ii) if xi (0) > 0 for some i ∈ A, then xi (t) > 0 for t ≥ 0;
(iii) every restricted Nash equilibrium x ∈ Z is a rest point.
III. A SYMPTOTIC B EHAVIOR OF I MITATION DYNAMICS
FOR P OTENTIAL P OPULATION G AMES
The main results of this work deal with the global asymptotic behavior of the imitation dynamics (4) for potential
population games. Therefore, before presenting these results,
we briefly introduce the notion of potential game [23] in the
context of continuous population games.
Definition 3: A population game with action set A and
Lipschitz-continuous reward function vector r : X → RA
is a potential population game if there exists a potential
function Φ : X → R that is continuous on X , continuously
differentiable in its interior, with gradient ∇Φ(x) extendable
by continuity to the boundary of X , and such that
∂
∂
rj (x) − ri (x) =
Φ(x) −
Φ(x) ,
∂xj
∂xi

[7], is thus generalized in the following result, whose proof
is reported in the Appendix.
Lemma 4: Let r : X → RA be the reward function vector
of a potential population game with potential Φ : X → R.
Then, every imitation dynamics (4) satisfying (5) is such that
Φ̇(x) = ∇Φ(x) · ẋ ≥ 0 ,

An intuitive consequence of Lemma 4 and point (iii) of
Lemma 2 is that every imitation dynamics in a potential
continuous population game has ω-limit set coinciding with
the set of critical configurations Z. As we shall see, our
main result, beyond formally proving this intuitive statement,
consists in a significant refinement of it.
Observe that, from (1) and (12), the set B := Z \ N of
critical configurations that are not Nash equilibria satisfies
B = {x ∈ X : xi > 0 ⇒ ri (x) = r(x) < r∗ (x)} .

(15)

In other terms, critical configurations x that are not Nash
equilibria have the property that all actions played by a
non-zero fraction of players in the population (i.e., those
i ∈ A such that xi > 0) give the same average reward
(ri (x) = r(x)), that is strictly less than the maximum
reward (r(x) < r∗ (x)). This implies that r∗ (x) is necessarily
achieved by some action that is not adopted by anyone, i.e.,
r(x) < r∗ (x) = rj (x) for some j ∈ A such that xj = 0.
Notice that, in particular, B is a subset of the boundary of
X , since critical configurations that are not Nash equilibria
necessarily have at least one zero entry. The following
result states that, in potential population games, every such
configuration x ∈ B has an interior neighborhood in X where
the potential is strictly larger than in x. This result is the main
novelty of this work, being the key Lemma to prove global
asymptotic stability results for the imitation dynamics.
Lemma 5: Let r : X → RA be the reward function vector
of a potential population game with potential Φ : X → R.
Let B = Z \ N be the set of critical configurations that are
not Nash equilibria. Then, for every x ∈ B, there exists some
ε > 0 such that Φ(x) > Φ(x̄) for all x ∈ X such that
X
||x − x̄|| < ε
and
xi > 0 . (16)
i∈A:ri (x)=r∗ (x)

Proof: For x̄ ∈ B, let I := {i ∈ A : ri (x) = r∗ (x)}
and J = A \ I = {i ∈ A : ri (x) < r∗ (x)} . From (13),
m := min

∂Φ(x̄)
∂Φ(x̄)
− max
= r∗ (x̄) − max rj (x̄) > 0 .
j∈J
j∈J
∂xi
∂xj

By continuity of ∇Φ(x), there exists ε > 0 such that

for i, j ∈ A, and almost every x ∈ X .
The asymptotic analysis of imitative dynamics for potential population games begins by proving that the potential
function Φ(x) is never decreasing along trajectories of the
imitation dynamics (4) and it is strictly increasing whenever
x does not belong to the set Z of critical configurations. This
result, already known for more specific classes of dynamics

(14)

with equality if and only if x ∈ Z, as defined in (11).

i∈I

(13)

for all x ∈ X ,

min
i∈I

∂Φ(x)
∂Φ(x)
m
− max
≥
,
j∈J
∂xi
∂xj
2

(17)

for every x ∈ X such that ||x−x|| < ε. Then, fix any x ∈ X
satisfying (16), let z = x − x, and observe that
X
X
a :=
zi = −
zj > 0 .
(18)
i∈I

j∈J

It then follows from (17) and (18) that, for every point
t ∈ [0, 1] ,

y(t) = x + tz ,

along the segment joining x and x, one has that
X
X
∂
∂
∇Φ(y(t)) · z =
zi
Φ(y(t)) −
zj
Φ(y(t))
∂xi
∂xj
i∈I
j∈J
∂
∂
≥ a min
Φ(y(t)) − a max
Φ(y(t))
i∈I ∂xi
j∈J ∂xj
am
≥
,
2
so that
Z 1
am
(∇Φ(y(t)) · z) dt ≥ Φ(x)+
Φ(x) = Φ(x)+
> Φ(x).
2
0
In order to understand the novelty of this result we
consider that in [7], where the stability of points in Z is
analyzed for a subclass of imitation dynamics, it is proven
that all the points in B are unstable, whereas a subset of the
points in N , coinciding with the local maximizers of Φ are
stable. However, these two results deal with local stability
and their mere combination is not sufficient to prove global
asymptotic stability. On the contrary, our characterization of
the instability of the rest points in B through the analysis
of the value of the potential function in their neighborhood,
paves the way for our main result, which characterizes the
global asymptotic behavior of solutions of a broad class of
imitation dynamics in potential population games.
Theorem 6: Consider a potential population game with
action set A and configuration space X . Let (x(t))t≥0 be
a solution of some imitation dynamics (4) satisfying (5) and
S = {i ∈ A : xi (0) > 0}
be the support of the initial configuration. Then,
lim dist(x(t), NS ) = 0 .

t→+∞

In particular, if xi (0) > 0 for every i ∈ A, then x(t)
converges to the set N of Nash equilibria.
Proof: By Lemma 2 part (i) there is no loss of generality in assuming that S = A, i.e., xi (0) > 0 for every i ∈ A.
Let r(x) be the reward vector function of the considered
population game and let Φ(x) be a potential. Observe that
Φ(x) is continuous over the compact configuration space X ,
so that
∆ = max Φ(x) − min Φ(x) < +∞ .
x∈X

x∈X

Then, for every t ≥ 0 we have that
Z t
Φ̇(x(s))ds = Φ(x(t)) − Φ(x(0)) ≤ ∆ < +∞
0

Since Φ̇(x) ≥ 0 for every x ∈ X by Lemma 4, the above
implies that
lim Φ̇(x(t)) = 0 .
t→+∞

Then, continuity of Φ̇(x) and the second part of Lemma 4
imply that x(t) converges to the set Z, as t grows.

We are now left with proving that every solution x(t) of
an imitation dynamics with xi (0) > 0 for every i ∈ A
approaches the subset N ⊆ Z of Nash equilibria. By
contradiction, let us assume that ∃ ε > 0 such that ∀ t∗ > 0
there exists some t ≥ t∗ such that dist(x(t), N ) ≥ ε.
Since x(t) approaches Z as t grows large, this implies
that for every ε > 0 and every large enough t∗ there
exists t ≥ t∗ such that dist(x(t), B) < ε. It follows that
there exists a sequence of times t1 ≤ t2 ≤ . . . such that
n→+∞
dist(x(tn ), B) −→ 0. Since the configuration space X is
compact, we may extract a converging subsequence x(tnk )
with limit x ∈ B. Now, observe that Lemma 2 part (ii)
implies that xi (t) > 0 for every action i ∈ A. Then, Lemma
5 implies that there exists k0 ≥ 1 such that
Φ(x(tk )) > Φ(x) ,

∀k ≥ k0 .

Hence, the fact that Φ(x(tk )) is never decreasing as stated
in Lemma 4, would lead to
Φ(x) = lim Φ(x(tnk )) ≥ Φ(x(tnk0 )) > Φ(x) ,
k→+∞

a contradiction. Hence, lim dist(x(t), N ) = 0.
t→+∞

IV. E XAMPLES
In this section we present some applications of the results
from Section III. For the imitation dynamics from Example
9 (with all Kij sampled from independently and uniformly
from [0, 1]), we compare the analytical results obtained
from Theorem 6 with some numerical simulations of the
dynamics, in order to corroborate our theoretical results.
A. Linear reward population games
We present some examples of binary games as in Example
1 and of pure coordination games.
Example 4 (Binary linear reward games): First of all, it
is straightforward to prove that all binary games are potential
games. In fact, from a 2 × 2 reward matrix R, as defined in
(3), we can immediately obtain a potential function, that is

1
φ(x) =
(a − c)x21 + (d − b)x22 .
(19)
2
Notice that is not true that a generic linear reward game is
potential, for example a ternary game such as Rock-ScissorsPaper is known to be not a potential game [7].
In the following, three short examples of binary linear
potential population games will be presented. Let us consider
the following three reward matrices:






10 0
0 7
2 0
R(1) =
R(2) =
R(3) =
,
8 7
2 6
3 1
(20)
Matrix R(1) leads to a coordination game. Trajectories converge to one of the three Nash equilibria: the global minimum
of the potential function, attained in an interior point x̄, and
the two vertices of the simplex. Moreover, from Lemma 4,
we deduce that all trajectories with x1 (0) < x̄1 converge to
(0, 1), all trajectories with x1 (0) > x̄1 converge to (1, 0),
whereas x̄ is an unstable equilibrium.

Φ(x)

Φ(x)

Φ(x)

x1

x1
(a) Coordination

(b) Anti-coordination

x1
(c) Dominated action

Fig. 1: Potentials of the games from Example 4. Crosses
are Nash equilibria, circles are Nash equilibria for restricted
games.

x1

x1

(a) Coordination

time
(b) Anti-coordination

time
(c) Dominated action

Fig. 2: Trajectories of the imitation dynamics (9) for the
games from Example 4. Solid lines are asymptotically stable
equilibria, dotted lines are unstable.

Matrix R(2) leads to an anti-coordination game, where
the Nash equilibrium x̄ is unique and it is an interior point.
Therefore, if the support of the initial condition is A, then
Theorem 6 guarantees convergence to it.
Matrix R(3) leads to a game with a dominated action. In
this case, the potential is a monotone increasing function
in x2 . Therefore its maximum is attained in δ (2) , that is the
only Nash equilibrium. Theorem 6 guarantees all trajectories
with x2 (0) > 0 to converge to it. Fig. 1 shows the plot of
the potential functions of the three games and Fig. 2 shows
examples of trajectories of the imitation dynamics (9).
Example 5 (Pure coordination games): Another class of
potential games are the linear reward pure coordination
games [14], in which the reward matrix R is a diagonal
positive (entry-wise) matrix. It is straightforward to check
that a potential function is given by

and the three minima on the boundary of X :
(c, 0, 1)
(b, 1, 0)
(0, c, b)
, x̄(2) =
, x̄(3) =
.
b+c
c+1
b+1
Through Lemma 4 we conclude that x̄ is an unstable node,
the three points on the boundaries x̄(1) , x̄(2) , and x̄(3) are
saddle points, whose stable manifolds actually divide the
basins of attraction of the three asymptotically stable nodes
δ (1) , δ (2) , δ (3) . Fig. 3 shows two examples of potential and
velocity plots of the imitation dynamics (9) for these games.
x̄(1) =

B. Congestion games
Another important class of potential games are congestion games [24], [23]. Let A = {1, . . . , l} be a set of
resources and A ∈ {0, 1}l×m be the adjacency matrix
of a bipartite graph connecting agents with resources. Let
us introduce l continuous functions, collected in a vector
ψ(·) = (ψ1 (·), . . . , ψl (·)), where the generic ψk (y) is the
reward for agents that use resource k, when the resource
is used by a fraction y of agents. The reward vector functions for these games are simply r(x) = AT ψ(Ax) and a
straightforward computation shows that congestion games
are always potential games, with

m

Φ(x) =

1X
Rii x2i .
2 i=1

(b) b = 0.2, c = 5

Fig. 3: Potential of the pure coordination games from Example 5 and velocity plot of imitation dynamics (9) from
Example 3 for them. The unstable nodes and the saddle
points are denoted by white circles.

x1
time

(a) b = 2, c = 3

(21)

Being Φ(x) convex, its minimum is attained in an interior
point x̄, and all the vertices of the simplex are local maxima
of the potential function. All the other critical points are
minima of the potential subject to belong to the boundaries.
All of these points are Nash equilibria. Therefore Theorem
6 guarantees asymptotic convergence to them. In the ternary
case |A| = 3, a complete analysis can be carried out. Without
any loss in generality, we can set R11 = 1 and name R22 =b
and R33 = c. Then, analyzing Φ(x) = 21 x21 + bx22 + cx23 ,
we explicitly compute the seven Nash equilibria: δ (1) , δ (2) ,
and δ (3) , the global minimum of the potential


c
b
bc
x̄ =
,
,
,
b + c + bc b + c + bc b + c + bc

Φ(x) =

k=l
X

Ψk ((Ax)k ),

(22)

k=1

where Ψk is an anti-derivative of ψk .
Often, the functions ψk s represent a cost for the use of
the resources, so they are monotone decreasing functions. In
this case, the potential function Φ(x) is concave, possessing
a global maximum x̄, that is the only Nash equilibrium of
the game. Depending on A, x̄ can be an interior point,
or it can belong to the boundary of the simplex. As the
other critical points are considered, δ (i) are minima of the
potential, whereas local maxima are present on the boundary,
that are Nash equilibria for restricted games. Theorem 6
guarantees therefore that trajectories with x(0) > 0 (entrywise) converge to x̄, that is an asymptotically stable node.
The Nash equilibria of the restricted games are saddle points
(i.e., stable on the respective boundaries) and the vertices that

(a) Ex. 6

(b) (24) from Ex. 7

(c) (25) from Ex. 7

Fig. 4: Potential of the congestion games from Example 6
(with m = 3, c1 = 1, c2 = 2, and c3 = 3) and from Example
7, respectively, and velocity plot of imitation dynamics (9)
from Example (3) for them. The unstable nodes are denoted
by white circles, saddle points by gray circles, and black
circles denote the only asymptotically stable equilibrium.

are not in one of the previous set are unstable nodes. Fig.
4 shows the velocity plots of the imitation dynamics for the
following examples of congestion games.
Example 6 (Exponential costs game): Let A = I and let
the cost be ψi (xi ) = exp(c1 x1 ), for P
ci > 0. Then, the
m
maximum of the potential Φ(x) = − i=1 c1i exp(−ci xi )
is achieved in an interior point x̄, that is the unique Nash
equilibrium of the game.
Example 7 (Dominated strategy): We construct now two
examples of congestion games in which the Nash equilibrium
of the dynamics is on the boundary. Let l = 2, ψi (y) = −y,
and let us consider the following two adjacency matrices:




1 0 1
1 1 1
A1 =
A2 =
.
(23)
0 1 1
0 1 1
The potential functions are, respectively:

1
(x1 + x3 )2 + (x2 + x3 )2
(24)
2
1
(25)
Φ2 (x) = − (x2 + x3 )2 .
2
As A1 is considered, the Nash equilibrium of the dynamics
is in x̄ = (1/2, 1/2, 0), whereas A2 has its Nash equilibrium
in the vertex δ (1) .
Φ1 (x) = −

V. C ONCLUSION AND F URTHER W ORK
In this work we analyzed the asymptotic behavior of
imitation dynamics in potential population games, proving
convergence of the dynamics to the set of Nash equilibria of
the sub-game restricted to the set of actions used in the initial
configuration of the population. This results strengthen the
state of the art, both ensuring global stability to the Nash
equilibria, and generalizing the result to a class of dynamics
that encompasses the replicator dynamics and the class of
imitation dynamics considered in many previous works.
The main research lines arising from this work point in
two directions. On the one hand, taking advantage on the
techniques developed in this work, our analysis has to be
extended to the case in which the population is not fully
mixed and agents interact on a non-complete communication
network, similar to what have been done for other learning
mechanisms, such as the replicator and logit choice [25],

[12], or to cases in which the learning process interacts
with the dynamics of a physical system [26]. On the other
hand, stochasticity in the revising of the agent’s opinion
should be included into the imitation dynamics. This leads
to model imitation dynamics with Markovian stochastic
processes, paving the way for the study of several interesting
open problems in the relationships between the asymptotic
behavior of the new stochastic process and the one of the
deterministic process analyzed in this work.
R EFERENCES
[1] J. W. Weibull, Evolutionary game theory. MIT Press, 1995.
[2] J. Björnerstedt and J. W. Weibull, “Nash equilibrium and evolution by
imitation,” in The Rational Foundations of Economic Behavior, 1996,
pp. 155–171.
[3] J. Hofbauer and K. Sigmund, “Evolutionary game dynamics,” Bulletin
(New Series) of the American Mathematical Society, vol. 40, no. 4,
pp. 479–519, 2003.
[4] J. H. Nachbar, ““Evolutionary” selection dynamics in games: Convergence and limit properties,” International Journal of Game Theory,
vol. 19, no. 1, pp. 59–89, mar 1990.
[5] J. Hofbauer, “From Nash and Brown to Maynard Smith: Equilibria,
Dynamics and ESS,” Selection, vol. 1, no. 1, pp. 81–88, 2000.
[6] W. H. Sandholm, “Potential Games with Continuous Player Sets,”
Journal of Economic Theory, vol. 97, no. 1, pp. 81–108, mar 2001.
[7] ——, Population Games and Evolutionary Dynamics. Cambridge
University Press, 2010, pp. 153–164, 221–275.
[8] I. M. Bomze, “Regularity versus Degeneracy in Dynamics, Games,
and Optimization: A Unified Approach to Different Aspects,” SIAM
Review, vol. 44, no. 3, pp. 394–414, jan 2002.
[9] J. S. Shamma and G. Arslan, “Dynamic fictitious play, dynamic
gradient play, and distributed convergence to Nash equilibria,” IEEE
Transactions on Automatic Control, vol. 50, no. 3, pp. 312–327, 2005.
[10] M. J. Fox and J. S. Shamma, “Population games, stable games, and
passivity,” in Proceedings of the IEEE Conference on Decision and
Control. IEEE, dec 2012, pp. 7445–7450.
[11] R. Cressman and Y. Tao, “The replicator equation and other game
dynamics,” Proceedings of the National Academy of Sciences of the
United States of America, vol. 111, pp. 10 810–7, 2014.
[12] J. Barreiro-Gomez, G. Obando, and N. Quijano, “Distributed Population Dynamics: Optimization and Control Applications,” IEEE
Transactions on Systems, Man, and Cybernetics: Systems, vol. 47,
no. 2, pp. 304 – 314, 2016.
[13] J. Hofbauer and K. Sigmund, Evolutionary games and population
dynamics. Cambridge University Press, 1998.
[14] R. W. Cooper, Coordination Games. Complementarity and Macroeconomics. Cambridge University Press, 1999.
[15] D. Easley and J. Kleinberg, Networks, crowds, and markets: reasoning
about a highly connected world. Cambridge University Press, 2010.
[16] B. Skyrms, “The Stag Hunt and the Evolution of Social Structure,”
Cambridge University Press, vol. 1, pp. 1–147, 2004.
[17] A. Rapoport and A. M. Chammah, “The Game of Chicken,” American
Behavioral Scientist, vol. 10, no. 3, pp. 10–28, nov 1966.
[18] R. Sugden, The Economics of Rights, Co-operation and Welfare.
London: Palgrave Macmillan UK, 1986, vol. 97.
[19] T. G. Kurtz, Approximation of Population Processes. Philadelphia,
PA: SIAM, 1981, vol. 36.
[20] P. D. Taylor and L. B. Jonker, “Evolutionarily stable strategies and
game dynamics,” Mathematical Biosciences, vol. 40, no. 1-2, pp. 145–
156, jul 1978.
[21] P. Schuster and K. Sigmund, “Replicator dynamics,” Journal of
Theoretical Biology, vol. 100, no. 3, pp. 533–538, feb 1983.
[22] M. Benaim and J. W. Weibull, “Deterministic Approximation of
Stochastic Evolution in Games,” Econometrica, vol. 71, no. 3, pp.
873–903, may 2003.
[23] D. Monderer and L. S. Shapley, “Potential Games,” Games and
Economic Behavior, vol. 14, no. 1, pp. 124–143, may 1996.
[24] R. W. Rosenthal, “A class of games possessing pure-strategy Nash
equilibria,” International Journal of Game Theory, vol. 2, no. 1, pp.
65–67, dec 1973.

[25] J. R. Marden and J. S. Shamma, “Revisiting log-linear learning:
Asynchrony, completeness and payoff-based implementation,” Games
and Economic Behavior, vol. 75, no. 2, pp. 788–808, jul 2012.
[26] G. Como, K. Savla, D. Acemoglu, M. A. Dahleh, and E. Frazzoli,
“Stability analysis of transportation networks with multiscale driver
decisions,” SIAM Journal on Control and Optimization, vol. 51, no. 1,
pp. 230–252, 2013.

A PPENDIX
Lemma 2: For any imitation dynamics (4) satisfying (5):
(i) if x(0) ∈ XS for some nonempty subset of actions S ⊆
A, then x(t) ∈ XS for all t ≥ 0;
(ii) if xi (0) > 0 for some action i ∈ A, then xi (t) > 0 for
every t ≥ 0;
(iii) every restricted Nash equilibrium x ∈ Z is a rest point.
Proof:
(i) It follows from the fact that any solution of (4) with
xi (0) = 0 for some i ∈ A is such that xi (t) = 0,
∀ t ≥ 0.
(ii) Since ẋi (t) ≥ −Ci xi (t), where Ci = |A| max{|ri (x) :
x ∈ X |}, Gronwall’s inequality implies that xi (t) ≥
xi (0)e−Ci t > 0.
(iii) For every x ∈ Z and i, j ∈ A, one has that xi xj (ri (x)−
rj (x)) = 0. Then, (5) implies that xi xj (fij (x) −
fji (x))) = 0.
Lemma 4: Let r : X → RA be the reward function vector
of a potential population game with potential function Φ :
X → R. Then, every imitation dynamics (4) satisfying (5)
is such that
Φ̇(x) = ∇Φ(x) · ẋ ≥ 0 ,

for all x ∈ X ,

(26)

with equality if and only if x ∈ Z, as defined in (11).
Proof: For every x ∈ X , we have
Φ̇(x) = ∇Φ(x) · ẋ
= ∇Φ(x) · diag (x)(F 0 (x) − F (x))x
X ∂Φ(x)
xi xj (fji (x) − fij (x))
∂xi
i,j∈A


∂Φ(x) ∂Φ(x)
1 X
xi xj
−
(fji (x) − fij (x))
=
2
∂xi
∂xj
i,j∈A
1 X
=
xi xj (ri (x) − rj (x)) (fji (x) − fij (x)) ,
2
i,j∈A
(27)
where the last identity follows from (13). It now follows
from property (5) of the imitation dynamics that, ∀ i, j ∈ A,
=

(ri (x) − rj (x)) (fji (x) − fij (x)) ≥ 0 .
Being all entries of a configuration x ∈ X are non-negative,
xi xj (ri (x) − rj (x)) (fji (x) − fij (x)) ≥ 0.
Combining the above with (27), we get that Φ̇(x) ≥ 0 (thus
proving (26)). Finally, Φ̇(x) = 0 if and only if all the terms
xi xj (ri (x) − rj (x)) (fji (x) − fij (x)) = 0 ,

(28)

∀ i, j ∈ A. Using again (5), we have that
(ri (x) − rj (x)) (fji (x) − fij (x)) = 0 ⇐⇒ ri (x) = rj (x).
Then (28) is equivalent to
xi xj (ri (x) − rj (x)) = 0.

(29)

To conclude the proof, we are simply left with showing that a
configuration x ∈ X satisfies (29) if and only if it is critical,
i.e., it belongs to Z. Indeed, if x ∈ NS for some nonempty
subset of actions S ⊆ A, then necessarily ri (x) = rj (x)
for every i, j ∈ A such that xi xj > 0. On the other hand,
for any x ∈ X satisfying (29), it is immediate to verify that
x ∈ NS , where S = {i ∈ A : xi > 0} is its support.

