# A Note on the Pure Nash Equilibria for Evolutionary Games on Networks

Jean Carlo Moraes The Author is with the Federal University of Rio Grande do
Sul, Porto Alegre, RS Brazil (e-mail: jean.moraes@ufrgs.br). This work was
supported in part by the CAPES/Brazil under Grant CAPES-PRINT7608979, project
88881.309849/2018-1.

###### Abstract

Recently, a new model extending the standard replicator equation to a finite
set of players connected on an arbitrary graph was developed in evolutionary
game dynamics. The players are interpreted as subpopulations of
multipopulations dynamical game and represented as vertices of the graph, and
an edge constitutes the relation among the subpopulations. At each instant,
members of connected vertices of the graph play a 2-player game and collect a
payoff that determines if the chosen strategies will vanish or flourish. The
model describes the game dynamics of a finite set of players connected by a
graph emulating the replicator dynamics. It was proved a relation between the
stability of the mixed equilibrium with the topology of the network. More
specifically, the eigenvalues of the Jacobian matrix of the system evaluated
at the mixed steady state are the eigenvalues of the graph’s adjacency matrix
multiplied by a scalar. This paper studies the pure (strict) Nash equilibria
of these games and how it connects to the network. We present necessary and
sufficient conditions for a pure steady-state in coordination or anti-
coordination game to be a (strict) Nash Equilibrium.

Keywords— Complex networks, evolutionay game theory, pure nash equilibrium,
replicator equation on networked populations

##  1 Introduction

In order to explain the existence of persistent behaviours that animals show
in conflict situations, the evolutionary game theory emerged in the early 70s.
Until then, it was believed that this type of behaviour emerged because it was
beneficial to the species, but this idea goes against the Darwinian thought,
where selection occurs at the individual level, not at the community level.
John Maynard Smith and George Price proposed a solution to this problem by
introducing a type of game that does not require players to be rational, [1].
Evolutionary Game Theory only requires individuals to have a strategy and
nature to have a way to measure the fitness of this strategy against all
others. This strategy is tested through a game, and the payment is its
perpetuation (throughout reproduction, descendants will inherit your
strategy). The success of a strategy depends on its performance against
opposing strategies and on how often these strategies are found in the
population. In the decade that followed the publication of the work of Price
and Smith, there was a continuous growth in the applications of evolutionary
games within biology, [2].

During this same period, Taylor and Jonker modeled the dynamics of the
evolutionary games in the continuous case, with a system of non-linear
differential equations, called replicator equations, and in the discrete case,
with a system of non-linear difference equations, [3]. The replication
equation was used to describe not only biological phenomena, such as mutation
and viral spread [4] but also socioeconomic dynamics, as cooperation [4] and
dissemination of knowledge and wealth in the training of social networks
[5],[6]. In 2015, Madeo and Mocenni introduced a model where they integrate
the multipopulational replicator equation [4] with finite play structure over
a graph [7] [6], [8]. They proved three interesting results: the model
presented is an extension of the replicator equation; for games with two
strategies, the strategy profile is a (strict) Nash equilibrium of the game
and if and only if is an (asymptotically) stable steady states of the system
and, the most surprising, when all players have the same payoff matrices then
the coordinates of the internal equilibrium is independent of the topology of
the network, though the linear stability depends on the eigenvalues of the
adjacency matrix of the network. They were able to connect the stability of
the internal equilibrium with the network’s topology, and therefore give
conditions to have a strict Nash Equilibrium internal to the simplex based on
the network. It was not presented any result of this kind made for the pure
equilibria in general.

In this paper, we present conditions on the network for coordination and anti-
coordination games to (strict) Nash Equilibrium, even in the landscape where
all players may have different payoff matrices. Our results provide many
necessary (and sufficient) conditions for pure equilibria to be a (strict)
Nash Equilibrium. It allows us, in many cases, to reduce considerably the
number of cases to analyse. We will provide an example of a game with 262,144
pure equilibria. Using a combination of the results in the paper, we can
conclude that only 16 can be a strict Nash equilibrium (8 are).

##  2 Evolutionary Game on Networks (EGN)

Consider a finite population of players $V=\\{1,2,...,N\\}$ connected in a
network represented by an undirected graph $G$ with adjacency matrix
$A=\\{a_{v,w}\\}$, where $a_{v,w}=1$ if player $v$ and $w$ are connected and
$a_{v,w}=0$ otherwise. The model developed in [9] consider the interactions as
games played by $N$ individuals as two-person games where an individual of a
sub population $v$ plays against a represent of one of the sub populations $w$
connected to $v$, for simplicity we will say only that $v$ plays against $v$.
We will consider a game with two pure strategies: cooperate (C) and defect
(D). Let the strategy played by player $v$ be denoted by $x_{v}$, where
$x_{v}=1$ if $v$ cooperates and $x_{v}=0$ if $v$ defects. The payoff matrix
for a player $v$ is given by

$B_{v}=\begin{bmatrix}b_{v,C,C}&b_{v,C,D}\\\
b_{v,D,C}&b_{v,D,D}\end{bmatrix}.$

Player $v$ can also play a mixed strategy, in this case, $v$ cooperates with
relative frequency $x_{v}$. Let ${\bf x}=(x_{1},x_{2},...,x_{N})$ be the
strategy profile in the game. Since $x_{v}\in\Delta=[0,1]$ for all $v\in V$,
the strategy set $\mathcal{S}$ is $\Delta^{N}=[0,1]^{N}$. The payoff function
of the two-person game player for player $v$ against a neighbour $w$ is given
by

$\displaystyle\phi(x_{v},x_{w})=$
$\displaystyle\begin{bmatrix}x_{v}&(1-x_{v})\end{bmatrix}B_{v}\begin{bmatrix}x_{w}\\\
1-x_{w}\end{bmatrix}=$ $\displaystyle=$
$\displaystyle(b_{v,C,C}-b_{v,D,C}+b_{v,D,D}-b_{v,C,D})x_{v}x_{w}-$
$\displaystyle-(b_{v,D,D}$ $\displaystyle-
b_{v,C,D})x_{v}+b_{v,D,C}x_{w}+b_{v,D,D}(1-x_{w})$

The payoff of player $v$ over the network is the sum of all the outcomes of
the two-players games played by $v$ against his neighbours:

$\phi_{v}({\bf x})=\sum_{w=1}^{N}a_{v,w}\phi(x_{v},x_{w}).$ (1)

In the $(N,2)$-game case ($N$ players, $2$ strategies), the replicator
equation on graphs, which models the dynamics of an evolutionary game on
networked (EGN) populations, as defined in [9] by the system of $N$
differential equation given by

$\dot{x}_{v}=x_{y}(1-x_{v})f_{v}({\bf x}),\text{for}\,v\in V,$ (2)

where $\displaystyle{f_{v}({\bf x})=\frac{\partial\phi_{v}}{\partial
x_{v}}({\bf x}).}$ If we denote $\sigma_{v,C}=b_{v,C,C}-b_{v,D,C}$ and
$\sigma_{v,D}=b_{v,D,D}-b_{v,C,D}$, then

$\displaystyle f_{v}({\bf x})$
$\displaystyle=\sigma_{v,C}\sum_{w=1}^{N}a_{v,w}x_{w}-\sigma_{v,D}\sum_{w=1}^{N}a_{v,w}(1-x_{w})=$
$\displaystyle=(\sigma_{v,C}+\sigma_{v,D})\sum_{w=1}^{N}a_{v,w}x_{w}-\sigma_{v,D}\sum_{w=1}^{N}a_{v,w}.$

Note that $\sum_{w=1}^{N}a_{v,w}$ is the degree of the vertex $v$. Let us
denote it by $d_{v}$, then equations (2) can be rewritten as

$\dot{x}_{v}=x_{y}(1-x_{v})\bigg{[}(\sigma_{v,C}+\sigma_{v,D})\sum_{w=1}^{N}a_{v,w}x_{w}-\sigma_{v,D}d_{v}\bigg{]}.$
(3)

Given $v\in V$ and ${\bf x}\in\Delta^{N}$ we shall use the notation
$(x_{v},{\bf x_{-v}})$ in order to define Nash Equilibria. The vector ${\bf
x_{-v}}$ is a vector in $\Delta^{N-1}$ which corresponds to the vector ${\bf
x}$ without the component $v$, ${\bf
x_{-v}}=(x_{1},x_{2},...,x_{v-1},x_{v+1},...,x_{N})$. Therefore, for all $v\in
V$ we define $\pi_{v}:\Delta\times\Delta^{N-1}\rightarrow\mathbb{R}_{+}$ as

$\pi_{v}(x_{v},{\bf x_{-v}})=\phi_{v}({\bf x}).$ (4)

A Nash equilibrium NE is a profile of strategies where no player can improve
its payoff unilaterally, i.e., for all players $v$, $\pi_{v}$ cannot be
increased, changing only the strategy $x_{v}$.

$\displaystyle\Theta^{NE}=\\{{\bf x}\in\Delta^{N}:\forall
v\,\phi_{v}(x_{v},{\bf x_{-v}})\geq\phi_{v}(y,{\bf
x_{-v}});\,\forall\,y\in\Delta\\}.$

If for all players $v$ $x_{v}$ is the unique best response to others players’
strategies in that equilibrium ${\bf x_{-v}}$ then ${\bf x}$ is a strict Nash
equilibrium SNE.

$\displaystyle\Theta^{SNE}=\\{{\bf x}\in\Delta^{N}:\forall
v\;\phi_{v}(x_{v},{\bf x_{-v}})>\phi_{v}(y,{\bf x_{-v}});\,\forall
y\in\Delta\\}.$

Following [9], for the EGN model given by (2) these sets can be rewritten as:

$\displaystyle\Theta^{NE}=\bigg{\\{}{\bf x}\in$
$\displaystyle\Delta^{N}:\forall\,v\,\,\Big{(}(x_{v}=0\land f_{v}({\bf x})\leq
0)\,\,\lor$ $\displaystyle(x_{v}=1\land f_{v}({\bf x})\geq
0)\,\,\lor\,\,(f_{v}({\bf x})=0)\Big{)}\bigg{\\}}.$

and

$\displaystyle\Theta^{SNE}=\bigg{\\{}{\bf x}\in$
$\displaystyle\Delta^{N}:\forall\,v\,\,\Big{(}(x_{v}=0\land f_{v}({\bf
x})<0)\,\,\lor$ $\displaystyle(x_{v}=1\land f_{v}({\bf
x})>0)\,\,\lor\,\,(f_{v}({\bf x})=0)\Big{)}\bigg{\\}}.$

The set of steady states, $\Theta^{*}$ of the system of ODEs(2) is the set
that contains all points in $\Delta^{N}$ such that $x_{v}(1-x_{v})f_{v}({\bf
x})=0$ for all $v$ in $V$, therefore:

$\displaystyle\Theta^{*}=\bigg{\\{}{\bf x}\in$
$\displaystyle\Delta^{N}:\forall\,v\,\,\big{(}x_{v}=0\,\lor
x_{v}=1\,\lor\,f_{v}({\bf x})=0\big{)}\bigg{\\}}.$

Looking to the definition $\Theta^{*}$ it is clear that it contains the set
$\Theta^{p}=\\{0,1\\}^{N}$. The elements in $\Theta^{p}$ are called pure
steady states. Among all points in $\Theta^{p}$, we denote two special ones
where we have full cooperation, $\mathbf{x_{FC}}=(1,1,...,1)$, and full
defection, $\mathbf{x_{FD}}=(0,0,...,0)$. We can partition the steady states
set in three subsets: the pure $(\Theta^{p})$, the mixed $(\Theta^{m})$ and
the pure/mixed $(\Theta^{mp})$. Thus,
$\Theta^{*}=\Theta^{p}\cup\Theta^{m}\cup\Theta^{mp}$. The set $\Theta^{m}$
contains all steady states in the interior of the simplex $\Delta^{N}$, so
$\Theta^{m}=(0,1)^{N}\cap\Theta^{*}$. Note that if ${\bf x}\in\Theta^{m}$ then
${\bf x}\in\Theta^{*}$ which implies that $f_{v}({\bf x})=0$ for all $v$ and
therefore ${\bf x}$ is a Nash equilibrium, $\Theta^{m}\subset\Theta^{NE}$. All
the other steady states are classified as pure/mixed.

One of the main results in [9] establish that if $\sigma_{v,C}$ and
$\sigma_{v,D}$ are constant and not zero for all $v$ then there exists
$\mathbf{x^{*}}\in\Theta^{m}$. Moreover, if the adjacency matrix $A$ of the
graph is invertible, then the values of ${\bf x^{*}}$ do not depend on $A$,
but the linear stability depends on the eigenvalues of $A$. In this case, the
topology plays no role in the location of the steady-state, but it does on its
stability. Other result in [9] establishes conditions for a pure steady-state
to be in $\Theta^{NE}$ (and also in $\Theta^{NES})$. These conditions depend
on the mathematical expression that derives from equation (2). Unlike the
result for mixed steady state, in [9] is not provided conditions on the
network that ensures that a point in $\Theta^{p}$ is a NE or SNE. Results for
two special pure equilibrium, $\mathbf{x_{FC}}$ and $\mathbf{x_{FD}}$, are
obtained in [10]. Such a connection for a broader theory may not be possible
since the size of $\Theta^{p}$ can be very large and increases exponentially
when the number of vertices increases. However, in this paper, we provide
results for this question depending on the ratio of neighbours that plays
cooperate and defect, which depends on the network’s topology. This result
allows us, in many situations, to reduce the number of possible (strict) Nash
equilibria. For some network structures, the results allow us to find among
the elements $\Theta^{p}$ all the pure (strict) Nash equilibrium.

##  3 Results for Pure Nash Equilibria

In order to analyse the pure steady states of (2) we shall need the Jacobian
matrix associated with it,

$J_{v,w}(\mathbf{x^{*}})=\begin{cases}(1-2x^{*}_{v})k_{v}({\mathbf{x^{*}}})&\mbox{if
}w=v\\\ x^{*}_{v}(1-x^{*}_{v})(\sigma_{v,C}+\sigma_{v,D})a_{v,w}&\mbox{if
}w\neq v\end{cases}$ (5)

where

$k_{v}({\mathbf{x^{*}}})=\sum_{w=1}^{N}a_{v,w}\bigg{(}\sigma_{v,C}x^{*}_{w}-\sigma_{v,D}(1-x^{*}_{w})\bigg{)}.$
(6)

For ${\mathbf{x}^{*}}\in\Theta^{p}$, we define

$N_{v,C}:=\sum_{u=1}^{N}a_{v,u}x^{*}_{u}\quad\text{and}\quad
N_{v,D}:=\sum_{u=1}^{N}a_{v,u}(1-x^{*}_{u})$ (7)

Note that $N_{v,C}$ is the amount of neighbours of $v$ that cooperates and
$N_{v,D}$ is the amount of neighbours of $v$ that defects. Also important to
note that $N_{v,C}+N_{v,D}=d_{v}$. With these definitions we can state our
main result which will connect the linear stability of a pure steady state
(and the Nash equilibrium) with the ratio
$\displaystyle{R_{v}:=\sigma_{v,C}(\sigma_{v,D}})^{-1}$ and the quantities
$N_{v,C}$ and $N_{v,D}$.

######  Theorem 1.

Let $\mathbf{x^{*}}\in\Theta^{p}$, $\mathbf{x^{*}}$ is a steady state of the
EGN defined (2). Then $\mathbf{x^{*}}$ is a NE iff for each vertex $v$

  * •

that has a coordination payoff matrix, we have

$\displaystyle$$N_{v,D}\leq R_{v}N_{v,C}$$$ if $x^{*}_{v}=1$, $v$ plays
cooperate; (8) $\displaystyle$$N_{v,C}\leq\frac{1}{R_{v}}N_{v,D}$$$ if
$x^{*}_{v}=0$, $v$ plays defect; (9)

  * •

that has a anti-coordination payoff matrix, we have that

$\displaystyle$$N_{v,C}\leq\frac{1}{R_{v}}N_{v,D}$$$ if $x^{*}_{v}=1$, $v$
plays cooperate; (10) $\displaystyle$$N_{v,D}\leq R_{v}N_{v,C}$$$ if
$x^{*}_{v}=0$, $v$ plays defect. (11)

Moreover, $\mathbf{x^{*}}$ is a SNE iff for each vertex $v$

  * •

that has a coordination payoff matrix, we have

$\displaystyle$$N_{v,D}<R_{v}N_{v,C}$$$ if $x^{*}_{v}=1$, $v$ plays cooperate;
(12) $\displaystyle$$N_{v,C}<\frac{1}{R_{v}}N_{v,D}$$$ if $x^{*}_{v}=0$, $v$
plays defect; (13)

  * •

that has a anti-coordination payoff matrix, we have that

$\displaystyle$$N_{v,C}<\frac{1}{R_{v}}N_{v,D}$$$ if $x^{*}_{v}=1$, $v$ plays
cooperate; (14) $\displaystyle$$N_{v,D}<R_{v}N_{v,C}$$$ if $x^{*}_{v}=0$, $v$
plays defect. (15)

###### Proof.

Given $\mathbf{x^{*}}\in\Theta^{p}$, for all $v$ $x_{v}^{*}=0$ or
$x_{v}^{*}=1$, which implies, from (5) that $J_{v,w}(\mathbf{x^{*}})=0$ if
$v\neq w$. Thus, the Jacobian is a diagonal matrix. The elements of diagonal
are its eigenvalues and are given by

$\displaystyle\lambda_{v}$
$\displaystyle=J_{v,v}(\mathbf{x^{*}})=(1-2y^{*}_{v})(\sigma_{v,C}k_{v,C}(\mathbf{x^{*}})-\sigma_{v,D}k_{v,D}(\mathbf{x^{*}}))=$
$\displaystyle=(1-2x^{*}_{v})\bigg{(}\sigma_{v,C}\sum_{u=1}^{N}a_{v,u}x^{*}_{u}-\sigma_{v,D}\sum_{u=1}^{N}a_{v,u}(1-x^{*}_{u})\bigg{)}$

By Theorem 2 in [9], $\mathbf{x^{*}}$ is a SNE (NE) if and only if the
eigenvalues of the Jacobian matrix $J(\mathbf{x^{*}})$ are all less (less or
equal) than zero.

$\displaystyle\lambda_{v}$
$\displaystyle=J_{v,v}(\mathbf{x^{*}})=(1-2x^{*}_{v})\bigg{(}\sigma_{v,C}N_{v,C}-\sigma_{v,D}N_{v,D}\bigg{)}=$
$\displaystyle=\begin{cases}\sigma_{v,C}N_{v,C}-\sigma_{v,D}N_{v,D}&\mbox{if
}x^{*}_{v}=0\\\ \sigma_{v,D}N_{v,D}-\sigma_{v,C}N_{v,C}&\mbox{if
}x^{*}_{v}=1\end{cases}$

Let $\displaystyle{R_{v}:=\frac{\sigma_{v,C}}{\sigma_{v,D}}}$, then we can
write

$\displaystyle\sigma_{v,D}\lambda_{v}=\begin{cases}R_{v}N_{v,C}-N_{v,D}&\mbox{if
}x^{*}_{v}=0\\\ N_{v,D}-R_{v}N_{v,C}&\mbox{if }x^{*}_{v}=1,\end{cases}$

in a short way,

$\sigma_{v,D}\lambda_{v}=(2x_{v}^{*}-1)\big{(}N_{v,D}-R_{v}N_{v,C}\big{)}.$

Therefore,

$\displaystyle\operatorname{sgn}(\lambda_{v})$
$\displaystyle=\operatorname{sgn}(\sigma_{v,D})\operatorname{sgn}(\sigma_{v,D}\lambda_{v})=$
$\displaystyle=\operatorname{sgn}(\sigma_{v,D})\operatorname{sgn}(2x_{v}^{*}-1)\operatorname{sgn}(N_{v,D}-R_{v}N_{v,C})$

If $\operatorname{sgn}(\sigma_{v,D})=\operatorname{sgn}(\sigma_{v,C})>0$, then

$\displaystyle\lambda_{v}<(\leq)\,\,0$
$\displaystyle\iff\operatorname{sgn}(2x^{*}-1)\neq\operatorname{sgn}(N_{v,D}-R_{v}N_{v,C})$
$\displaystyle\iff\begin{cases}N_{v,D}<(\leq)\,\,R_{v}N_{v,C},&\mbox{if
}x^{*}_{v}=1;\\\ N_{v,C}<(\leq)\,\,\frac{1}{R_{v}}N_{v,D},&\mbox{if
}x^{*}_{v}=0;\end{cases}$

In the other hand, if
$\operatorname{sgn}(\sigma_{v,D})=\operatorname{sgn}(\sigma_{v,C})<0$, then

$\displaystyle\lambda_{v}<(\leq)\,\,0$
$\displaystyle\iff\operatorname{sgn}(2x^{*}-1)=\operatorname{sgn}(N_{v,D}-R_{v}N_{v,C})$
$\displaystyle\iff\begin{cases}N_{v,C}<(\leq)\,\,\frac{1}{R_{v}}N_{v,D},&\mbox{if
}x^{*}_{v}=1;\\\ N_{v,D}<(\leq)\,\,R_{v}N_{v,C},&\mbox{if
}x^{*}_{v}=0;\end{cases}$

∎

######  Corollary 1.

Let $\mathbf{x^{*}_{FC}}=(1,1,\dots,1)$, $\mathbf{x^{*}_{FD}}=(0,0,\dots,0)$.
If for all vertices $v$,
$\operatorname{sgn}(\sigma_{v,C})=\operatorname{sgn}(\sigma_{v,D})>0$, then
$\mathbf{x^{*}_{FC}}$ and $\mathbf{x^{*}_{FD}}$ are SNE. In the other hand, if
$\operatorname{sgn}(\sigma_{v,C})=\operatorname{sgn}(\sigma_{v,D})<0$ $\forall
v$, then $\mathbf{x^{*}_{FC}}$ and $\mathbf{x^{*}_{FD}}$ are not NE.

###### Proof.

Since all players cooperate in the steady state $\mathbf{x^{*}_{FC}}$, no
player $v$ has a neighbour that defects, i.e. $N_{v,D}=0\,\,\forall\,v$.
Therefore, (12) is always satisfied and (10) is never satisfied. Analogous,
$N_{v,C}=0\,\forall\,v$ in the steady state $\mathbf{x^{*}_{FD}}$, thus
condition (13) is always satisfied and (11) is never satisfied. Thus,
$\mathbf{x^{*}_{FC}}$ and $\mathbf{x^{*}_{FD}}$ are SNE in coordination games
and it is not a NE in anti-coordination games. ∎

######  Corollary 2.

Let $\mathbf{x^{*}}\in\Theta^{p}$, $\mathbf{x^{*}}$ is a steady state of the
EGN given by (2). If there is a vertex $v$, with
$\operatorname{sgn}(\sigma_{v,C})=\operatorname{sgn}(\sigma_{v,D})>0$, such
that all his neighbours plays a strategy different than him, then
$\mathbf{x^{*}}$ is not a NE.

###### Proof.

Let $\mathbf{x^{*}}\in\Theta^{p}$. Assume $x^{*}_{k}=1$ for some
$k\in\\{1,2,...,N\\}$ and $x^{*}_{l}=0$ for all $l\neq k$, then
$N_{k,C}=0,\,N_{k,D}=d_{k}$ and (8) is not satisfied. Analogous, if
$x^{*}_{k}=0$ for some $k\in\\{1,2,...,N\\}$ and $x^{*}_{l}=1$ for all $l\neq
k$, then $N_{k,D}=0,\,N_{k,C}=d_{k}$ and condition (13) is not satisfied. ∎

An example of the corollary above application is to graphs with leaves (one
vertex link only one other in the graph). If the leaf has a coordination
payoff matrix, it must play the same strategy to its neighbour in a pure
strategy profile. For instance, consider a star graph, where all players have
a coordination payoff matrix, then a $\mathbf{x^{*}_{FC}}$ and
$\mathbf{x^{*}_{FD}}$ are the only pure NE of the game.

######  Corollary 3.

Let $\mathbf{x^{*}}\in\Theta^{p}$, $\mathbf{x^{*}}$ is a steady state of the
EGN. If there is a vertex $v$, such that $\sigma_{v,C}$ and $\sigma_{v,D}$ are
negatives and all his neighbours play the same strategy than him, then
$\mathbf{x^{*}}$ is not a Nash equilibria.

###### Proof.

Let $\operatorname{sgn}(\sigma_{v,C})=\operatorname{sgn}(\sigma_{v,D})<0$,
$\forall v$ and $\mathbf{x^{*}}\in Theta^{p}$. Assume for some
$k\in\\{1,2,...,N\\}$ all neighbours of $k$ plays the same strategy than him.
If $x^{*}_{k}=0$, then $N_{k,D}=d_{k}$ and $N_{k,C}=0$, which implies that
(11) is not satisfied. Analogous, if $y^{*}_{k}=1$, but in this case (10) will
be violated. ∎

For the next two corollaries we will assume that all players have the same
payoff matrix and they are either coordination or anti-coordination type,
i.e., $B_{v}=B$ for all $v\in V$ and
$\operatorname{sgn}(\sigma_{C})=\operatorname{sgn}(\sigma_{D})\neq 0$, where
$\sigma_{C}=b_{11}-b_{12}$ and $\sigma_{D}=b_{22}-b_{21}$. Thus,
$R_{v}=\frac{\sigma_{C}}{\sigma_{D}}=R$ for all $v$. A similar assumption is
made in [9] to show that the stability mixed equilibrium of the EGN depends
only on the adjacency matrix of the graph and also in [10] to obtain
conditions on self-regulation parameters in order to be able to determine if
the mixed equilibrium, $\mathbf{x^{*}_{fc}}$ and $\mathbf{x^{*}_{fd}}$ are NE
for Stag-Hunt Games and Chicken Games. The network structure may have an
important role in the stability of many other pure equilibria of the EGN. A
game with $N$ players has $2^{N}$ equilibria in $\Theta^{p}$. Their analysis
is important to know if subpopulations of cooperators can emerge (and be
stable) in the dynamics of the evolution game.

######  Corollary 4.

Suppose $B_{v}=B$ for all $v\in V$ in a coordination game. If
$R_{v}=R>d_{v}-1$ for all $v\in V$, then $\mathbf{x^{*}_{FC}}$ and
$\mathbf{x^{*}_{FD}}$ are the unique SNE in $\Theta^{p}$.

###### Proof.

Let $\mathbf{x^{*}}\in\Theta^{p}$ such that
$\mathbf{x^{*}}\neq\mathbf{x^{*}_{FC}}$ and
$\mathbf{x^{*}}\neq\mathbf{x^{*}_{FD}}$. Then $\mathbf{x^{*}}$ has at least
one player $k$ that defects and plays against a cooperator. Note that
$\mathbf{x^{*}}$ has at least one player that plays $1$ and one that plays
$0$, otherwise $\mathbf{x^{*}}$ would be $\mathbf{x^{*}_{FC}}$ or
$\mathbf{x^{*}_{FD}}$. Moreover, at least one player $k$ that defects and
plays against a cooperator, if that does not happen, then we would have a
disconnected graph with all cooperators on one side and all defectors on the
other. Since the graph is connected, this does not happen. Then $N_{k,C}\geq
1$ and

$\displaystyle R>d_{k}-1$ $\displaystyle=N_{k,C}+N_{k,D}-1\geq N_{k,D}\iff$
$\displaystyle\iff RN_{k,C}>N_{k,D}.$

Thus, condition (13) is not satisfied. ∎

###  3.1 Independent Dominating Sets

A set $D\subset V$ is a dominating set of a graph $G$ with vertices $V$ if
every vertex in $\in V-D$ is adjacent to a vertex in $D$. A set $D\subset V$
is independent if no two vertices in $D$ are adjacent. An independent
dominating set of a graph $G$ is a set of vertices that are dominating and
independent in $G$, [11],[12], [13]. The following corollary gives conditions
on $R_{v}$’s such that a pure steady-state $\mathbf{x}^{*}$ of the EGN is a
SNE in an anti-coordination if and only if the set of players that cooperates
or the set of players that defects are an independent dominating set of a
graph $G$.

######  Corollary 5.

Consider an EGN over a graph $G$ with all players having a payoff matrix anti-
coordination $B_{v}$. Let $\mathbf{x^{*}}\in\Theta^{p}$,
$\mathcal{D}:=\\{v\,:x^{*}_{v}=0\\}$ and $\mathcal{C}:=\\{v\,:x^{*}_{v}=1\\}.$
Then

  * i)

if $R_{v}>d_{v}-1$ for all $v\in V$, then $\mathbf{x^{*}}$ is a SNE iff
$\mathcal{C}$ is an independent dominant subgraph of $G$.

  * ii)

if $R_{v}^{-1}>d_{v}-1$ for all $v\in V$, then $\mathbf{x^{*}}$ is SNE iff
$\mathcal{D}$ is an independent dominant subgraph of $G$.

###### Proof.

We will start showing _i)_. Assume $R_{v}>d_{v}-1$ for all $v\in V$ and
$\mathbf{x^{*}}\in\Theta^{p}$ is a SNE. First note that, anti-coordination
implies by Corollary 1 that $\mathcal{C}\neq\emptyset$. Now, by Corollary 4, a
player that defects has at least one neighbour that cooperates, so every
vertex in $\in V-\mathcal{C}$ is adjacent to a vertex in $\mathcal{C}$, thus,
$\mathcal{C}$ is dominant. In order to show that $\mathcal{D}$ is independent
we shall prove that for every $v\in\mathcal{C}$, $N_{v,C}=0$, i.e., no
neighbour of $v$ cooperates. Take $v\in\mathcal{C}$, if $d_{v}=1$ then
Corollary 3 implies that $N_{V,D}\geq 1$ and therefore $N_{v,D}=1$ and
$N_{v,C}=0$. If $d_{v}>1$, then $R_{v}>0$, since $R_{v}>d_{v}-1$. Thus
$R_{v}^{-1}<(d_{v}-1)^{-1}$. Since $\mathbf{x^{*}}\in\Theta^{p}$ is a SNE,
then equation (14) implies that $N_{v,C}<R_{v}^{-1}N_{v,D}$, thus

$\displaystyle N_{v,C}<R_{v}^{-1}N_{v,D}$
$\displaystyle<\frac{N_{v,D}}{d_{v}-1}\Rightarrow
N_{v,C}(d_{v}-1)<N_{v,D}\Rightarrow$ $\displaystyle\Rightarrow
d_{v}N_{v,C}<N_{v,D}+N_{v,D}=d_{v}\Rightarrow$ $\displaystyle\Rightarrow
d_{v}N_{v,C}<d_{v}\Rightarrow N_{v,C}<1\Rightarrow$ $\displaystyle\Rightarrow
N_{v,C}=0.$

Therefore $\mathcal{C}$ is independent dominant subgraph of $\mathcal{G}$.

In order to show the the reverse implication assume $\mathcal{C}$ is an
independent dominant set of $G$, then for all $v\in\mathcal{C}$, $N_{v,C}=0$.
Also, again Corollary 3 implies that $N_{V,D}\geq 1$, therefore condition (14)
is easily checked for $v\in\mathcal{C}$ ($x_{v}=1$). Now, if $x^{*}_{v}=0$,
then Corollary 3 implies that $N_{V,C}\geq 1$ which implies $N_{v,D}<d_{v}-1$.
Thus, $R_{v}N_{v,C}>d_{v}-1>N_{v,D}$ which is the condition (15). Both
conditions together ensures that $\mathbf{x^{*}}$ is a SNE. The proof of _ii)_
is analogous. ∎

_Remark:_ In the case that $R_{v}=R$ for all $v\in V$, if $R>\max_{v\in
V}(d_{v}-1)$, then $\mathbf{x^{*}}$ is a SNE iff $\mathcal{C}$ is an
independent dominant set of $G$. Analogous, if $R^{-1}<\max_{v\in
V}(d_{v}-1)$, then $\mathbf{x^{*}}$ is an SNE iff $\mathcal{D}$ is an
independent dominant set of $G$.

##  4 Application

In this section, we will provide some examples to show how helpful can be the
Theorem 1 and the corollaries of the previous section. As argued before, the
graph’s topology can be an essential instrument to determine the SNE (NE) in
$\Theta^{p}$.

###  4.1 Coordination Game and Caterpillar graph

Consider a EGN over a Caterpillar graph $G:=C_{8}(0,1,0,5,0,0,4,0)$. Each
player in the main stalk (players $1$ to $8$) has payoff matrix $B_{cs}$ and
each player in branches (players $9$ to $18$) has payoff matrix $B_{b}$, where

$B_{cs}=\begin{bmatrix}2.1&0\\\ 0&1\end{bmatrix}\quad\text{and}\quad
B_{b}=\begin{bmatrix}3&0\\\ 0&2\end{bmatrix}.$

Fig. 1: Caterpillar graph $C_{8}(0,1,0,5,0,0,4,0)$

Let $R_{cs}:=R_{v}$ for $v\in\\{1,2,...,8\\}$ and $R_{b}:=R_{v}$ for
$v\in\\{9,10,...,18\\}$. Then $R_{cs}=2.1$ and $R_{b}=1.5$. Note that
$\Theta^{p}$ contains $2^{18}=262,144$ pure equilibria. We will use the theory
developed to show that most of them can not be SNE. Assume all players play a
pure strategy, Corollary 2 guarantees that all leaves will play the same
strategy that their neighbour in the main stalk. Therefore, players
$15,16,17,18$ play in agreement with $7$, so does player $8$ which can be
viewed as a leaf of $7$. Analogous, players $10,11,12,13,14$ will agree with
player $4$. The same corollary will also state that in a SNE, players $1,2,9$
plays the same strategy.

Player $3$ always agrees with player $2$. Let us verify that affirmation. Note
that it has only two neighbours: $2$ and $4$. If $4$ defects then:

  * •

$3$ cooperates if $2$ cooperates (since he will benefit more cooperating with
$2$;

  * •

$3$ defects if $2$ defects since both its neighbours defects by Corollary 2.

If $4$ cooperates, then $3$ will cooperate, which implies that $2$ has to
cooperate by Theorem 1. In any way that $4$ plays, $2$ and $3$ will always
agree. Last, players $5$ and $6$ will also play the same strategy. Suppose
they could disagree, then one of them would play cooperate. The other one
would have only two neighbours where at least one of them cooperates. Since
the payoff for cooperating is better than defecting, he would be better at
cooperating in agreement with his neighbour. Therefore we can group the
players in 4 sets: $G_{1}:=\\{1,2,3,9\\}$, $G_{2}:=\\{4,10,11,12,13,14\\}$,
$G_{1}:=\\{5,6\\}$, $G_{1}:=\\{7,8,15,16,17,18\\}$.

Fig. 2: Representation of the 4 sets which among them each player should play
the same strategy.

An $x^{*}\in\Theta^{p}$ only is a SNE if the players in these groups play the
same strategy. Thus, from $262,144$ equilibria in$\Theta^{*}$, only $2^{4}=16$
can be SNE. We use Theorem 1 to verify that among these 16, 8 are, in fact,
SNE. We present all of them in the figure below, where the players (groups) in
yellow cooperates and those in red defects.

Fig. 3: Representation of 8 SNE of the problem. In the left column, it is the
representation in the original graph; in the right column it is presented the
reduced graph with the groups where all players inside it play in agreement.

###  4.2 Anti-Coordination Game in an Erdös-Rényi network

Consider the game over a Erdös-Rényi graph generated with $8$ vertices and
average degree $4$ where all players have the same payoff matrix $B$, let
$R=\sigma_{v,C}/\sigma_{v,D}$, for any player $v$.

Fig. 4: Erdös-Rényi graph with $8$ vertices and average degree $4$.

In the anti-coordination case,
$\operatorname{sgn}(\sigma_{C})=\operatorname{sgn}(\sigma_{D})<0$, Corollary 3
guarantees that if $\mathbf{x^{*}}$ is a SNE then every player has at least
one neighbour that plays a different strategy different than him. Moreover,
note that player 5 is more connected to others than any other player,
$d_{5}=5$. If $R>4$, then by Corollary 5, the SNE of this game are strategies
profiles that the cooperators form an independent dominant set of the graph.
There are $9$ of them, represented in the below.

Fig. 5: The cooperator form an independent dominant graph for SNE for the EGN
over the graph of Figure 4 for $R>4$.

Suppose $R\in(0,\frac{1}{4})$, defectors would be an independent dominant set
of the graph in Figure 4. Moreover, there would be $9$ solutions which would
be the same as in Figure 5 where all cooperator becomes a defector and vice
versa. For $R=2$, there are only 2 SNE among the 256 pure steady states.

Fig. 6: Strict Nash equilibria for the EGN over the graph of Figure 4 for
$R=2$.

For $R$ ranging in $(0,\infty)$, it possible to check the conditions of
Theorem 1 for each one of the $256$ pure steady states. We only need to note
that any change of states must occur in a ratio among degrees of a vertex,
i.e., for a point in the set $\\{\frac{d_{v}}{d_{u}}\,:\,v,u\in V\\}$. If we
order this set as $Ch:=\\{0,\alpha_{1},\alpha_{2},...,\alpha_{l}\\}$, then it
is enough to test for $R\in(0,\alpha_{1})$, any
$R\in(\alpha_{i},\alpha_{i+1})$ for $i=1,2,..l-1$ and $R=\alpha_{i}$ for
$i=1,2,..l$. In our example,
$Ch=\\{0,\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},1,\frac{3}{2},2,3,4\\}$.
The diagram below shows the number of SNE for all values of $R\in(0,\infty)$
of the EGN over the graph of Figure 4. For clarity, the $R$-axis is not on
scale.

Fig. 7: Number of Pure Nash equilibria for $R>0$ of the EGN over the graph of
Figure 4.

## References

  * [1] J. Smith and G. Price, “The logic of animal conflict,” Nature, vol. 246, pp. 15–18, 1973.
  * [2] J. M. Smith, Evolution and the Theory of Games.  Cambridge University Press, 1982.
  * [3] P. D. Taylor and L. B. Jonker, “Evolutionary stable strategies and game dynamics,” Mathematical Biosciences, vol. 40, no. 1, pp. 145–156, 1978\.
  * [4] J. Weibull, Evolutionary Game Theory.  Cambridge University Press, 1995.
  * [5] A. DI MARE and V. LATORA, “Opinion formation models based on game theory,” International Journal of Modern Physics C, vol. 18, no. 09, pp. 1377–1395, 2007.
  * [6] M. O. Jackson and Y. Zenou, “Games on networks,” in Handbook of Game Theory with Economic Applications, vol. 4, ch. 3, pp. 95–163, Elsevier, 2015\.
  * [7] O. H. and N. M., “The replicator equation on graphs,” J Theor Biol., vol. 243, no. 1, pp. 86–97, 2006.
  * [8] W. Maciejewski, F. Fu, and C. Hauert, “Evolutionary game dynamics in populations with heterogenous structures,” PLOS Computational Biology, vol. 10, pp. 1–16, 04 2014.
  * [9] D. Madeo and C. Mocenni, “Game interactions and dynamics on networked populations,” IEEE Transactions on Automatic Control, vol. 60, no. 7, pp. 1801–1810, 2015.
  * [10] D. Madeo and C. Mocenni, “Consensus towards partially cooperative strategies in self-regulated evolutionary games on networks,” Games, vol. 12, no. 3, 2021.
  * [11] C. Berge, The theory of graphs and its applications.  London: Methuen & Co. Ltd., 1962.
  * [12] W. Goddard and M. A. Henning, “Independent domination in graphs: A survey and recent results,” Discrete Mathematics, vol. 313, no. 7, pp. 839–854, 2013\.
  * [13] O. Ore, Theory of graphs, vol. 38.  Providence: Amer. Math. Soc. Transl.,, 1962.