Evolutionary games on graphs and discrete dynamical systems

Abstract

Evolutionary games on graphs play an important role in the study of evolution of cooperation in applied biology. Using rigorous mathematical concepts from a dynamical systems and graph theoretical point of view, we formalize the notions of attractor, update rules and update orders. We prove results on attractors for different utility functions and update orders. For complete graphs we characterize attractors for synchronous and sequential update rules. In other cases (for $k$-regular graphs or for different update orders) we provide sufficient conditions for attractivity of full cooperation and full defection. We construct examples to show that these conditions are not necessary. Finally, by formulating a list of open questions we emphasize the advantages of our rigorous approach.

Keywords::

• evolutionary games on graphs
• discrete dynamical systems
• non-autonomous dynamical systems
• attractors
• cycles
• cooperation
• game theory
• defection

MSC (2010) Classification::

• 05C90
• 37N25
• 37N40
• 91A22

1. Introduction

Game theory was developed in the 1940s as a mathematical tool to study interactions and decisions of rational agents [24]. For a long time it was mainly applied in economics (see, e.g. [8,23] and the references therein). In the 1970s, it was introduced to biology via the concept of biological fitness and natural selection [21] and the evolutionary game theory enabled to study infinite homogeneous populations via replicator equations [12,13]. Recently, dynamics in populations which are finite and spatially structured (the structure being represented by graphs) attracted a lot of attention [26,29]. Evolutionary game theory on graphs has shown that the rate of cooperation strongly depends on the structure of the underlying interaction graph (see, e.g. 111926272829 and numerous following papers). At the same time, a similar problem of equilibria selection in cooperation games via timing structures has attracted a lot of attention, both in microeconomics (e.g. [15,16]) and in macroeconomics (e.g. [17,18]).

Mathematically, evolutionary games on graphs are very complex structures which bring together notions from graph theory, game theory, dynamical systems and stochastic processes. Mathematical techniques which are used are therefore complex and include complex approximative techniques such as pair and diffusion approximation and voter model perturbations [2,4,5] or are limited to special classes of graphs, e.g. cycles [27], stars [3,10] and vertex-transitive graphs [1,6]. Whereas these papers focus mainly on stochastic updating of vertices, the goal of this paper is to study evolutionary games on graphs with various deterministic update rules in the framework of discrete dynamical systems and formalize the notions of (autonomous and non-autonomous) evolutionary games on graphs, attractors, update rules and update orders. Being aware that this approach may look too formal for some, we believe that this approach should help to (i) disclose and answer interesting questions (some of them listed in Section 9), (ii) understand patterns by means of simple examples and counterexamples, (iii) describe analytically dynamics on small graphs (motivated, e.g. by small sizes of agents in cooperation games in macroeconomics [18]) and (iv) bridge a gap between three seemingly separate mathematical areas: graph theory, game theory and dynamical systems.

In Section 2, we introduce, for a given graph and an arbitrary utility function, a new formal notion of an (autonomous) evolutionary game on a graph (Definition 3) and attractors (Definition 5). In our rigorous approach, we are trying to follow the spirit of 1119272829. In Section 3 we introduce two basic utility functions and relate them to the underlying game-theoretical parameters. In Section 4 we characterize the attractivity of full defection (Theorem 9) and full cooperation (Theorem 10) on complete graphs. On $k$-regular graphs we provide only a sufficient condition for attractivity of these states (Theorem 12) and show (in Example 13) that it is not necessary. Section 5 is devoted to the extension of the notion of an evolutionary game on a graph to the realistic situation that the vertices are not all updated at each time step (Definition 14). The new notion of non-autonomous evolutionary game on a graph (Definition 18) has the structure of a general non-autonomous dynamical system (Definition 17). We also introduce attractors and their basins for non-autonomous evolutionary games (Definitions 20 and 21) and relate them to the autonomous case (Remark 23). In Section 6 we provide conditions for attractivity of full defection and full cooperation of non-autonomous evolutionary games. The conditions are sufficient for non-omitting update orders but are also necessary if a sequential update order is considered (Theorem 24). Example 25 shows that in general the conditions are not necessary. In Section 7 we provide a complete characterization of attractors of evolutionary games on complete graphs for synchronous (Theorem 26) and sequential (Theorem 27) update orders. In particular, Theorem 27(c) (together with Example 29) shows the existence of an attractive cycle. In Section 8 we discuss the role of different utility functions on irregular graphs. Finally, Section 9 is devoted to concluding remarks and open questions.

2. Evolutionary games on graphs

We recall some basic definitions from graph theory, see, e.g. [9]. A graph$G=(V,E)$ is a pair consisting of a set of vertices$V$ and a set of edges$E\subseteq \{e\subseteq V:|e|=2\}$. Let $N_k(i)$ denote the $k$-neighbourhood of vertex $i\in V$, i.e. all vertices with the distance exactly $k$ from $i$. Furthermore, let us define

$N_{\le k}(i)={\displaystyle \bigcup _{j=0}^k} N_j(i).$

We utilize basic concepts from dynamical systems theory (see, e.g. [7]).

Definition 1

Taking into account that our state space is discrete, we strip off any topological properties and call a map

$\varphi :\mathbb{N}{}_0\times X\to X$

on an arbitrary set $X$ a dynamical system with discrete one-sided time$\mathbb{N}{}_0$, if it satisfies the semigroup property

$\varphi (0,x)=x\text{and}\varphi (t,\varphi (s,x))=\varphi (t+s,x)\text{for} \text{all}\hspace{0.5em}t,s\in \mathbb{N}{}_0,\hspace{0.5em}x\in X.$

The set $X$ is called the state space and $\varphi (\cdot )=\varphi (1,\cdot ):X\to X$ the corresponding time-1-map.

Any map $\varphi :X\to X$ is the time-1-map of an induced dynamical system with discrete one-sided time $\mathbb{N}{}_0$ which is defined via composition or iteration as follows:

$\mathbb{N}{}_0\times X\to X,(t,x)\mapsto {\varphi }^t(x),$

where ${\varphi }^0= \text{i}d$ and ${\varphi }^t=\varphi \circ \cdots \circ \varphi$. In this paper we describe dynamical systems via their time-1-map.

We will define evolutionary games on graphs as special dynamical systems with the property that a vertex follows a strategy in its one-neighbourhood which currently yields the highest utility. To prepare this definition we introduce for a ‘function on a graph’ the size of the neighbourhood on which its values depend.

Definition 2

Let $M,S$ be arbitrary sets and $G=(V,E)$ a graph. We say that a function $f:S^V\to M^V$ has a dependency radius$r\in \mathbb{N}{}_0$ on $G$ if all values $f_i(x)$ of a component $f_i$ of $f$ depend on a component $x_j$ of the argument $x=(x_1,\dots ,x_{|V|})$ only if the vertex $j\in V$ is in the $r$-neighbourhood of the vertex $i\in V$, i.e. if for each $x,y\in S^V$ and $i,j\in V$ the following implication holds:

$⟨\forall k\in V\setminus \{j\}:x_k=y_k⟩\text{and}⟨f_i(x)\ne f_i(y)⟩\to j\in N_{\le r}(i).$

We are now in a position to formulate evolutionary games on graphs with unconditional imitation update rule as a dynamical system. This update rule goes back to [26] and is also called ‘imitate-the-best’. The basic idea is that at each time step every player determines his/her utility based on his/her strategy and the strategies of his/her neighbours. Based on that, each player adopts the strategy of his/her neighbour with the highest utility (if it is greater than his/her own).

Definition 3

Let $S$ be an arbitrary set. An evolutionary game on $G=(V,E)$ consists of the following two ingredients:

• a utility function on $G=(V,E)$, i.e. a function $u:S^V\to \mathbb{R}{}^V$ which has dependency radius $1$ on $G$,

• the dynamical system$\varphi :S^V\to S^V$ with ${\varphi }_i:= \text{proj}{}_i \circ \varphi :S^V\to S$ given by

  (1) ${\mathrm{phiv;}}_i(x)=\{\begin{array}{cc}{x}_{\text{max}}& \text{if}\hspace{0.5em}|A_i(x)|=1\hspace{0.5em}\text{and}\hspace{0.5em}{A}_i(x)=\{x_{\text{max}}\},\\ x_i& \text{if}\hspace{0.5em}|A_i(x)|>1,\end{array}$(1)
  where the set A_i(x) is defined by
  (2) $A_i(x)=\{x_k:k\in ar\text{g} \text{max}\{u_j(x):j\in N_{\le 1}(i)\left\}\right\}.$(2)

Remark 4

• Typically, $S$ represents the set of strategies (e.g. $C$ and $D$) and the vector $x=(x_1,\dots ,x_{|V|})\in S^V$ the population state (i.e. the spatial distribution of strategies at a given time).

• The cardinality of $A_i(x)$ in (1) is used to ensure that all vertices with the highest utility have the same state. If that is not the case, the vertex preserves its current state. Obviously, this may not be a reasonable approach once the set of strategies $S$ contains more than two strategies and the current state may yield worse payoff than all other strategies.

• An evolutionary game $\varphi$ on $G$ has dependency radius $2$ on $G$.

• Whereas the notion of evolutionary games in biological applications (see, e.g. [27]) sometimes has a probabilistic aspect, our Definition 3 of an evolutionary game is deterministic. Note that, although we do not follow that direction in this paper, in principle it is possible to extend Definition 3 to also incorporate that a vertex follows strategies in its one-neighbourhood with a certain probability.

• Given the fact that each vertex mimics the state of its neighbour with the highest utility, we speak about imitation dynamics. Preserving the deterministic nature, there are various possibilities of defining the dynamics. For example, instead of imitation dynamics ${\varphi }^I:=\varphi$ in (1), we could consider deterministic death–birth dynamics, in which only the vertices with the lowest utility adopt the state of its neighbour with highest utility, i.e.

  ${\displaystyle {\mathrm{phiv;}}_i^{\text{DB}}}(x)=\{\begin{array}{cc}{x}_{\text{max}}& \text{if}\hspace{0.5em}{u}_i(x)={\displaystyle \underset{j\in V}{\text{min}}} u_j(x),|A_i(x)|=1\hspace{0.5em}\text{and}\hspace{0.5em}{A}_i(x)=\{x_{\text{max}}\},\\ x_i& \text{if}\hspace{0.5em}{u}_i(x)>{\displaystyle \underset{j\in V}{\text{min}}} u_j(x)\hspace{0.5em}\text{or}\hspace{0.5em}|A_i(x)|>1.\end{array}$

Alternatively, we could consider deterministic birth–death dynamics in which only vertices in the neighbourhood of vertices with the highest utility are updated, i.e.

${\displaystyle {\mathrm{phiv;}}_i^{\text{BD}}}(x)=\{\begin{array}{cc}{x}_{\text{max}}& \text{if}\hspace{0.5em}|A_i(x)|=1,{\displaystyle \underset{j\in N_1(i)}{\text{max}}} u_j(x)={\displaystyle \underset{j\in V}{\text{max}}} u_j(x)\hspace{0.5em}\text{and}\hspace{0.5em}{A}_i(x)=\{x_{\text{max}}\},\\ x_i& \text{if}\hspace{0.5em}|A_i(x)|>1\hspace{0.5em}\text{or}\hspace{0.5em}{\displaystyle \underset{j\in N_1(i)}{\text{max}}} u_j(x)<{\displaystyle \underset{j\in V}{\text{max}}} u_j(x).\end{array}$

We leave the analysis of such dynamical systems for further research and focus on evolutionary games with imitation dynamics (1).

We define a notion of distance $d$ in the state space $S^V$ by $d:S^V\times S^V\to \mathbb{R}$ with $S\subset \mathbb{R}$ by

$d(x,y):=|\{i\in V:x_i\ne y_i\}|.$

Similarly, the distance of a state $x\in S^V$ from a set of states $B\subset S^V$ will be denoted by $dist:S^V\times 2{}^{S^V}\to \mathbb{R}$ and defined by

$\text{dist}(x,B):=i\text{nf}\{d(x,y):y\in B\}.$

Definition 5

Let $\varphi :S^V\to S^V$ be an evolutionary game on $G=(V,E)$ and $A\subset S^V$invariant under $\varphi$, i.e. $\varphi (A)=A$. Then $A\ne \varnothing$ is called attractor of $\varphi$ if for any $x\in S^V$ with $\text{dist}(x,A)\le 1$ there exists $t\ge 0$ such that ${\varphi }^t(x)\in A$.

If $A=S^V$, we say that $A$ is the trivial attractor, otherwise $A$ is said to be a non-trivial attractor.

Remark 6

If $S$ and $V$ are finite sets, then $d$ generates the discrete topology on $S^V$. With this topology an invariant set $A$ is an attractor if and only if $\text{lim}{}_{t\to \infty } \text{dist}({\varphi }^t(x),A)=0$ for all $x\in S^V$ with $\text{dist}(x,A)\le 1$.

3. Utility function and cooperative games

We discuss cooperative evolutionary games (see, e.g. [25]) with utilities which are implied by a static game (see, e.g. [8] for an introduction to game theory) on a state space $S=\{C,D\}$ consisting of two strategies, each vertex can either cooperate ($C$) or defect ($D$).

Consequently, a player gets $a$ if both he/she and his/her partner cooperate, he/she gets $b$ if he/she cooperates and his/her partner defects, if he/she defects and his/her partner cooperates he/she gets $c$, if both players defect, he/she gets $d$. We focus on cooperation games and therefore make the following assumptions on the parameters $a,b,c,d$:

	(A1) For the sake of brevity, we assume that no two parameters are equal.
	(A2) It is always better if both players cooperate than if they both defect, i.e. $a>d$.
	(A3) If only one cooperates, it is more advantageous to be the defector, i.e. $c>b$.
	(A4) No matter what strategy a player chooses, it is always better for him/her if his/her opponent cooperates, i.e. $a>b$ and $c>d$.
	(A5) $a,c$ are positive, i.e. there is a positive reward for cooperation of the opponent.

Definition 7

We say that a parameter vector $(a,b,c,d)$ is admissible if it satisfies assumptions (A1)–(A5). The set $𝒫\subset \mathbb{R}{}^4$ of all such quadruplets is called the set of admissible parameters.

The set $𝒫$ of admissible parameters splits into four regions corresponding to scenarios which we call Full Cooperation (FC), Hawk and Dove (HD), Stag hunt (SH)3 and Prisoner's dilemma (PD):

$𝒫{}_{\text{FC}}=\{(a,b,c,d)\in \mathbb{R}{}^4:a>c>b>d\},𝒫{}_{\text{HD}}=\{(a,b,c,d)\in \mathbb{R}{}^4:c>a>b>d\},𝒫{}_{\text{SH}}=\{(a,b,c,d)\in \mathbb{R}{}^4:a>c>d>b\},𝒫{}_{\text{PD}}=\{(a,b,c,d)\in \mathbb{R}{}^4:c>a>d>b\}.$

Obviously,

(3) $𝒫=𝒫{}_{\text{FC}}\cup 𝒫{}_{\text{HD}}\cup 𝒫{}_{\text{SH}}\cup 𝒫{}_{\text{PD}}.$(3)

In the case of static games, a (mixed) Nash equilibrium for two-player games is a pair of mixed strategies $({\displaystyle {\sigma }_1^{*}},{\displaystyle {\sigma }_2^{*}})$ such that

$u_1({\displaystyle {\sigma }_1^{*}},{\displaystyle {\sigma }_2^{*}})\ge u_1({\sigma }_1,{\displaystyle {\sigma }_2^{*}}),\text{for} \text{all}\hspace{0.5em}{\sigma }_1\in \Sigma {}_1,u_2({\displaystyle {\sigma }_1^{*}},{\displaystyle {\sigma }_2^{*}})\ge u_2({\displaystyle {\sigma }_1^{*}},{\sigma }_2),\text{for} \text{all}\hspace{0.5em}{\sigma }_2\in \Sigma {}_2,$

where $\Sigma {}_i$ denotes the set of all mixed strategies of player $i$ (see [8] for more details). In the admissible regions the Nash equilibria have the following structure.

Table

	Abbreviation	Scenario	Nash equilibria
$a>c>b>d$	FC	Full cooperation	(C,C)
$c>a>b>d$	HD	Hawk and Dove	(C,D), (D,C) and a mixed equilibrium
$a>c>d>b$	SH	Stag hunt	(C,C), (D,D) and a mixed equilibrium
$c>a>d>b$	PD	Prisoner's dilemma	(D,D)

Note that the mixed Nash equilibrium $(d-b)/((a-c)+(d-b))$ provides the minimal payoff in the SH game and the maximal payoff in the HD game. As we will see, this fact influences the stability of corresponding interior points of, e.g. replicator dynamics, see [12].

There are two natural ways of how to define utilities on evolutionary graphs with $S=\{0,1\}$ (state $1$ corresponds to $C$ and state $0$ to $D$). We could either consider the aggregate utility

(4) ${\displaystyle u_i^A}(t)=a{\displaystyle \sum _{j\in N_1(i)}} s_i{s}_j+b{\displaystyle \sum _{j\in N_1(i)}} s_i(1-s_j)+c{\displaystyle \sum _{j\in N_1(i)}} (1-s_i)s_j+d{\displaystyle \sum _{j\in N_1(i)}} (1-s_i)(1-s_j)$(4)

or the mean utility

(5) ${\displaystyle u_i^M}(t)=\frac{1}{|N_1(i)|}{\displaystyle u_i^A}(t).$(5)

Note that on regular graphs $|N_1(i)|$ is constant and both utilities yield the same evolutionary games. However, on irregular graphs, this is no longer true (see Section 8) and one could argue which utility is more realistic.

Remark 8

Once we consider the mean utility function (or the aggregate utility function on regular graphs) we could, without loss of generality, normalize parameters $a,b,c,d$ so that $\tilde{a}=1$ and $\tilde{d}=0$ by the following map

$\tilde{x}=\frac{x-d}{a-d},\text{for}\hspace{0.5em}x=a,b,c,d.$

Conversely, given normalized values of parameters $\tilde{a},\tilde{b},\tilde{c},\tilde{d}$, we could (for arbitrary $a$ and $d$ such that $a>d$) construct non-normalized values of parameters by

$x=d+(a-d)\tilde{x},\text{for}\hspace{0.5em}x=a,b,c,d.$

This allows us to simplify conditions or plot regions corresponding to various scenarios, cf. Figure 1 where four scenarios are depicted.

Figure 1 Set of admissible parameters and four game-theoretic scenarios, $a=1$ and $d=0$.

4. Evolutionary games on $K_n$

In this section we consider evolutionary games generated by the simplest graphs – complete graphs $K_n$ and regular graphs. Note that evolutionary games on $K_n$ correspond to dynamics of a well-mixed (non-spatial) population. We focus on the attractivity of full defection $(0,0,\dots ,0)$ and full cooperation $(1,1,\dots ,1)$ and its connection to parameters $a,b,c,d$.

Theorem 9

For all admissible $(a,b,c,d)\in 𝒫$ the following two statements are equivalent:

• $\{(0,0,\dots ,0)\}$ is an attractor of the evolutionary game $\varphi$ on $K_n$ with the utility function (4).

• $(a,b,c,d)\in 𝒫$ satisfy

  (6) $b<d\text{or}n<1+\frac{c-d}{b-d}.$(6)

Proof

Choose $x\in S^V=\{0,1\}{}^V$ such that $d(x,(0,0,\dots ,0))=1$. Then there exists a unique $i\in V$ such that $x_i=1$ and $x_j=0$ for all $j\ne i$ (i.e. $i$ is the unique cooperator). Consequently, the utilities are:

$u_i(x)=(n-1)b,u_j(x)=c+(n-2)d.$

$(b)\to (a)$ Inequalities (6) imply that

$u_i(x)-u_j(x)=(n-1)b-c-(n-2)d=n(b-d)-(b-d)-(c-d)<0.$

Therefore, $u_j(x)>u_i(x)$ for all $j\ne i$. Hence, ${\varphi }_j(x)=0$ for all $j\in V$ and $\varphi (x)=(0,0,\dots ,0)$.

$(a)\to (b)\hspace{0.5em}$ Assume that (6) does not hold, i.e.4

$b>d\text{and}n\ge 1+\frac{c-d}{b-d}.$

If $n=1+((c-d)/(b-d))$, then $u_i(x)=u_j(x)$. This implies that ${\varphi }_j(x)=x_j$ and $\varphi (x)=x$. If $n>1+((c-d)/(b-d))$, then $u_i(x)>u_j(x)$. This implies that ${\varphi }_j(x)=1$ and $\varphi (x)=(1,1,\dots ,1)$, which implies that $(0,0,\dots ,0)$ cannot be reached from $x$, since $\varphi ((1,1,\dots ,1))=(1,1,\dots ,1)$. ▪

A similar result could be obtained for the full cooperation state $(1,1,\dots ,1)$.

Theorem 10

For all admissible $(a,b,c,d)\in 𝒫$ the following two statements are equivalent:

• $\{(1,1,\dots ,1)\}$ is an attractor of the evolutionary game $\varphi$ on $K_n$ with the utility function (4).

• $(a,b,c,d)\in 𝒫$ satisfy

  (7) $a>c\text{and}n>1+\frac{a-b}{a-c}.$(7)

Proof

The proof is very similar to the proof of Theorem 9.

$(b)\to (a)\hspace{0.5em}$ Choose $x\in S^V=\{0,1\}{}^V$ such that $d(x,(1,1,\dots ,1))=1$. Then there exists a unique $i\in V$ such that $x_i=0$ and $x_j=1$ for all $j\ne i$ (i.e. $i$ is the unique defector). Consequently, the utilities are:

$u_i(x)=(n-1)c,u_j(x)=b+(n-2)a.$

Then (7) implies that

$u_i(x)-u_j(x)=(n-1)c-b-(n-2)a=-n(a-c)+(a-c)+(a-b)<0.$

Therefore, $u_j(x)>u_i(x)$ for all $j\ne i$. Hence, ${\varphi }_j(x)=1$ for all $j\in V$ and $\varphi (x)=(1,1,\dots ,1)$.

$(a)\to (b)\hspace{0.5em}$ Assume that (7) does not hold, i.e.

$a<c\text{or}n\le 1+\frac{a-b}{a-c}.$

If the equality $n=1+((a-b)/(a-c))$ holds, then $\varphi (x)=x$. Otherwise, $\varphi (x)=(0,0,\dots ,0)$. Consequently, $(1,1,\dots ,1)$ is not attractive. ▪

Remark 11

Theorems 9 and 10 show that attractivity of full defection and full defection is qualitatively different for admissible parameters in the four different regions FC, HD, SH, PD in (3). In the PD case, there is no dependence on $n$ and the values of the parameters. On the other hand, in the other cases different behaviour could occur for different parameter values and in dependence of the size of the graph $n$. Evidently, the richest situation occurs in the FC case in which it is possible that, depending on the parameter, full defection and full cooperation, as well as none of them, or both of them together are attractive, cf. Table 1 and Figure 2.

Table 1 $K_n$ – Connection between graph size, different scenarios and attractivity of states $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$.

	PD	HD	SH	FC
$(0,0,\dots ,0)$ attractive	Always	$n<1+\frac{c-d}{b-d}$	Always	$n<1+\frac{c-d}{b-d}$
$(1,1,\dots ,1)$ attractive	Never	Never	$n>1+\frac{a-b}{a-c}$	$n>1+\frac{a-b}{a-c}$

Figure 2 Attractivity regions of $(0,0,\dots ,0)$ (light grey) and $(1,1,\dots ,1)$ (horizontally hatched) ($a=1$ and $d=0$ are fixed, cf. Remark 8). (a) $n=3$ on the left and (b) $n=5$ on the right.

We observe that in the PD case, $(0,0,\dots ,0)$ is always attractive. Similarly, in the FC case $(1,1,\dots ,1)$ is the unique attractor if and only if $n>1 +m\text{ax}\{((c-d)/(b-d)),((a-b)/(a-c))\}$.

Finally, note that the results are consistent with those for infinite populations studied in the evolutionary game theory [12,25], in which the full cooperation is an evolutionary stable strategy (ESS) if and only if $a>c$ and the full defection is evolutionary stable strategy ESS if and only if $b<d$ (those inequalities are obtained as $n\to \infty )$. Note that for finite complete graphs additional conditions involving the size $n$ are involved (see (6) and (7)). Thus, the parameter region in finite populations is larger for full defection and smaller for full cooperation, see Figure 2.

The ideas from the proofs of Theorems 9 and 10 easily carry over to $k$-regular graphs.

Theorem 12

Let $(a,b,c,d)\in 𝒫$ be admissible and $G$ be a $k$-regular graph, $k\ge 2$.

• If

  (8) $k(b-d)<c-d,$(8)
  holds, then $\{(0,0,\dots ,0)\}$ is an attractor of the evolutionary game $\varphi$ on $G$ with the utility function (4).

• If

  (9) $k(a-c)>a-b,$(9)
  holds, then $\{(1,1,\dots ,1)\}$ is an attractor of the evolutionary game $\varphi$ on $G$ with the utility function (4).

However, the following example shows that (8) and (9) are only sufficient and not necessary for the attractivity of $\{(0,0,\dots ,0)\}$ and $\{(1,1,\dots ,1)\}$ for evolutionary games on $k$-regular graphs.

Example 13

Consider the undirected Cayley graph (see [9, p. 34]) of the Dihedral group of order 24 (as a permutation group on $\text{{1,}\dots ,12\}$, see [14, p. 46] for the notation) with generators

$g_1=(2\hspace{0.5em}12)(3\hspace{0.5em}11)(4\hspace{0.5em}10)(5\hspace{0.5em}9)(6\hspace{0.5em}8),g_2=(1\hspace{0.5em}2)(3\hspace{0.5em}12)(4\hspace{0.5em}11)(5\hspace{0.5em}10)(6\hspace{0.5em}9)(7\hspace{0.5em}8),g_3=(1\hspace{0.5em}4)(2\hspace{0.5em}3)(5\hspace{0.5em}12)(6\hspace{0.5em}11)(7\hspace{0.5em}10)(8\hspace{0.5em}9).$

The graph is depicted in Figure 3. Consider the evolutionary game on G with utility function (4) and parameters $(a,b,c,d)=(1,0.88,\text{1.}74,0)$. Then the following inequalities are fulfilled:

$0\cdot c+3\cdot d=0<1\cdot c+2\cdot d=1.74<0\cdot a+3\cdot b=2.64<1\cdot a+2\cdot b=2.76<2\cdot a+1\cdot b=2.88<3\cdot a+0\cdot b=3<2\cdot c+1\cdot d=3.48<3\cdot c+0\cdot d=5.22.$

Since $G$ is 3-regular, all other parameters that satisfy the same inequalities will lead to the same evolutionary game.

Figure 3 A trajectory of the evolutionary game from Example 13. For possible reproduction we provide its graph 6 notation (see [22]): |WsOPA?OG?[?E@C?o@??@??O?????????s??k?@@_?Cg??KO|.

The initial state with exactly one cooperator, whose position does not matter because the graph is vertex-transitive, reaches $(0,0,\dots ,0)$ after $10$ steps for these parameters (see Figure 3). Therefore $(0,0,\dots ,0)$ is attractive, although (8) is violated.

5. General asynchronous update – non-autonomous evolutionary games

In an evolutionary game all nodes are updated in a synchronous way (i.e. all nodes at each time step), cf. Definition 3. To formulate asynchronous update which is only updating a certain subset of nodes at each time step, we introduce a notion of update order.

Definition 14

A set-valued function $𝒯:\mathbb{N}{}_0\to 2{}^V$ is called update order.

The update order $𝒯$ is called

• non-omitting, if for each vertex $v\in V$ and each $t_0\in \mathbb{N}{}_0$, there exists $t>t_0$ such that $v\in 𝒯(t)$; otherwise $𝒯$ is called omitting,

• periodic, if there exists $T\in \mathbb{N}$ such that $𝒯(t+T)=𝒯(t)$ for each $t\in \mathbb{N}{}_0$,

• synchronous, if $𝒯(t)=V$ for each $t\in N_0$; otherwise $𝒯$ is called asynchronous,

• sequential, if vertices can be ordered so that $𝒯(t)=\{(t+1)(m\text{od} n)\}$.

Remark 15

Obviously, synchronous and sequential update orders are automatically non-omitting and periodic. A periodic update order could be omitting and a non-omitting update order is not necessarily periodic.

Example 16

Let $G$ be a finite graph with $V=\{1,2,\dots ,n\}$, for some $n\in \mathbb{N}$, $n\ge 3$. Then $𝒯:\mathbb{N}{}_0\to 2{}^V$ given by

(10) $Tscr;(t)=\{\begin{array}{cc}\text{{1,2}}& \text{if}\hspace{0.5em}t\hspace{0.5em}is \text{even,}\\ \text{{3,4,}\dots ,n\}& \text{if}\hspace{0.5em}t\hspace{0.5em}is \text{odd,}\end{array}$(10)

is a periodic and non-omitting update order.

Let us define

${\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}:=\{(t,s)\in \mathbb{N}{}_0\times \mathbb{N}{}_0:t\ge s\}.$

Definition 17

A non-autonomous dynamical system (or two-parameter process, or two-parameter semiflow) $\varphi$ is a map

$\varphi :{\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}\times M\to M,$

which satisfies the two-parameter semiflow property

$\varphi (t,t,x)=x,\varphi (t,r,\varphi (r,s,x))=\varphi (t,s,x),$

for all $x\in M$ and $t,r,s\in \mathbb{N}{}_0$ such that $t\ge r\ge s$.

Definition 18

A non-autonomous evolutionary game on $G=(V,E)$ with a utility function $u$ and update order $𝒯:\mathbb{N}{}_0\to 2{}^V$ is the non-autonomous dynamical system $\varphi :{\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}\times S^V\to S^V$ with ${\varphi }_i:= \text{proj}{}_i \circ \varphi :{\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}\times S^V\to S$ defined by

${\mathrm{phiv;}}_i(t+1,t,x)=\{\begin{array}{cc}{x}_{\text{max}}& \text{if}\hspace{0.5em}i\in 𝒯(t),|A_i(x)|=1\hspace{0.5em}\text{and}\hspace{0.5em}{A}_i(x)=\{x_{\text{max}}\},\\ x_i& \text{otherwise,}\end{array}$

where $A_i(x)$ is defined in (2).

Remark 19

Definition 18 is a non-autonomous version of an evolutionary game with imitation dynamics (cf. Remark 4). As in the case of (autonomous) evolutionary games, we could consider alternative definitions of deterministic non-autonomous evolutionary games.

Definition 20

Let $\varphi :{\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}\times S^V\to S^V$ be a non-autonomous evolutionary game on $G=(V,E)$. A set $A\subset \mathbb{N}{}_0\times S^V$ is called attractor of $\varphi$ if

• $A$ is invariant, i.e. for all $(t,t_0)\in {\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}$:

  $\varphi (t,t_0,A(t_0))=A(t),$
  where $A(t):=\{x\in S^V:(t,x)\in A\}$.

• $A$ is attracting, i.e. for any $(t_0,x)\in \mathbb{N}{}_0\times S^V$ with $\text{dist}(x,A(t_0))\le 1$ we have

  ${\displaystyle \underset{t\to \infty }{\text{lim}}} \text{dist}(\varphi (t,t_0,x),A(t))=0.$

Definition 21

The basin of attraction of an invariant set $A\subset \mathbb{N}{}_0\times S^V$ is the set

$B(A):=\{(s,x)\in \mathbb{N}{}_0\times S^V: {\displaystyle \underset{t\to \infty }{\text{lim}}} \text{dist}(\varphi (t,s,x),A(t))=0\}.$

We can make the following simple observation.

Remark 22

Let $\varphi$ be a non-autonomous evolutionary game and $A\subset \mathbb{N}{}_0\times S^V$ be an invariant set such that $A(t)=A(s)$ for all $t,s\in \mathbb{N}{}_0$. If we define

$D_1(A):=\{(t,x)\in \mathbb{N}{}_0\times S^V:\text{dist}(x,A(t))=1\},$

then $A$ is an attractor of a non-autonomous evolutionary game $\varphi :{\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}\times S^V\to S^V$ if and only if $D_1(A)\subset B(A)$.

Remark 23

A non-autonomous evolutionary game $\varphi :{\displaystyle {(\mathbb{N}{}_0)}_{\ge }^2}\times S^V\to S^V$ with synchronous update order $𝒯(t)=V$ induces an associated (autonomous) evolutionary game $\psi :S^V\to S^V$ by setting

(11) $\psi (x):=\varphi (t+1,t,x)\text{for} \text{all}\hspace{0.5em}x\in S^V,$(11)

for an arbitrary $t\in \mathbb{N}{}_0$. $\psi$ in (11) is well-defined because synchronous update order implies that $\varphi (t+1,t,x)=\varphi (s+1,s,x)$ for all $t,s\in \mathbb{N}{}_0$ and $x\in S^V$.

An attractor $A\subset \mathbb{N}{}_0\times S^V$ of $\varphi$ which is time-independent (i.e. $A(t)=A(s)$ for all $t,s\in \mathbb{N}{}_0$) induces an attractor $C:=A(t)$ of $\psi$, because $\text{lim}{}_{t\to \infty } \text{dist}(\varphi (t,t_0,x),A(t))=0$, together with the fact that $\varphi (t,t_0,x)={\psi }^{t-t_0}(x)$, implies that

${\displaystyle \underset{t\to \infty }{\text{lim}}} \text{dist}({\psi }^{t-t_0}(x),C)=0.$

In this situation the domain of attraction $B(A)$ and the set $D_1(A)$ from Remark 22 are also time-independent and we identify them with the sets $\{x\in S^V:(0,x)\in B(A)\}$ and $\{x\in S^V:(0,x)\in D_1(A)\}$. In general, an attractor $A$ of a non-autonomous evolutionary game $\varphi$ can be time dependent, e.g. if $A$ is a periodic orbit $A(t+p)=A(t)$ for all $t\in \mathbb{N}{}_0$ and some natural number $p\ge 2$, which is attractive. If $A\subset \mathbb{N}{}_0\times S^V$ is a time-independent attractor then we say that $A(0)\subset S^V$ is an attractor. If, moreover, $A=\mathbb{N}{}_0\times \{x\}$ then we say that $x$ is an attractor.

6. Non-autonomous evolutionary games on $K_n$

We follow the ideas from Section 4 and study the attractivity of full cooperation $(1,1,\dots ,1)$ and full defection $(0,0,\dots ,0)$ on complete graphs for non-autonomous evolutionary games with the utility function (4).

Theorem 24

Let $\varphi$ be a non-autonomous evolutionary game on $K_n$ with the aggregate utility function (4), $(a,b,c,d)\in 𝒫$ and $𝒯:\mathbb{N}{}_0\to 2{}^V$ be a non-omitting update order. Then,

• if (6) holds, then $(0,0,\dots ,0)$ is an attractor of $\varphi$,

• if (7) holds, then $(1,1,\dots ,1)$ is an attractor of $\varphi$.

Moreover, if $𝒯$ is sequential, then the reverse implications also hold.

Proof

The proof is very similar to the ideas from the proofs of Theorems 9 and 10. To prove statement (i), let us assume that (6) holds and $x\in S^V=\{0,1\}{}^V$ is such that $d(x,(0,0,\dots ,0))=1$. Then there exists a unique $i\in V$ such that $x_i=1$ and $x_j=0$ for all $j\ne i$. The utilities satisfy $u_j(x)>u_i(x)$ for all $j\ne i$. Hence, $\varphi (t+1,t,x)=x$ if $i\notin 𝒯(t)$ and $\varphi (t+1,t,x)=(0,0,\dots ,0)$ if $i\in 𝒯(t)$. Since the update rule is non-omitting, we know that there exists $t\in \mathbb{N}{}_0$ such that $i\in 𝒯(t)$ and consequently for each $s\in \mathbb{N}$ we have

$\varphi (t+s,0,x)=(0,0,\dots ,0).$

The latter statement (ii) is proven in the same way.

Finally, we would like to show that if the update order is sequential, then conditions (6) and (7) are also necessary. Suppose by contradiction that (6) does not hold. Then for each $x\in S^V=\{0,1\}{}^V$ with $d(x,(0,0,\dots ,0))=1$ we have that for each $t\in \mathbb{N}{}_0$

(12) $\varphi (t+1,t,x)\ne (0,0,\dots ,0).$(12)

If $(0,0,\dots ,0)$ is an attractor then there exists $t\in \mathbb{N}$ such that

$\varphi (t,0,x)\ne (0,0,\dots ,0)\text{and}\varphi (t+1,0,x)=(0,0,\dots ,0),$

which implies that

$\varphi (t+1,t,x)=(0,0,\dots ,0),$

a contradiction to (12). ▪

Obviously, if the update order is not non-omitting, the single cooperator need not have a chance to switch and therefore there are no conditions which ensure attractivity of $(0,0,\dots ,0)$ or $(1,1,\dots ,1)$. In the following example we show that for general non-omitting update orders, we cannot reverse the implications, since either (6) or (7) need not be necessary.

Example 25

Let us consider a non-autonomous evolutionary game on $K_n$ with utility function (4) and with non-omitting and periodic update order given by (10) in Example 16. Let us assume that $(a,b,c,d)\in 𝒫$ are such that (6) is not satisfied, i.e.

(13) $(n-1)b>c+(n-2)d,$(13)

but

(14) $a+(n-2)b<2c+(n-3)d,$(14)

(15) $2a+(n-3)b<3c+(n-4)d.$(15)

Condition (13) implies that one cooperator has a higher utility than $(n-1)$ defectors, inequalities (14) and (15) ensure that two (or three) cooperators have lower utility than $(n-2)$ (or $(n-3)$) defectors.

If $x\in S^V=\{0,1\}{}^V$ is such that $d(x,(0,0,\dots ,0))=1$ (i.e. there exists a unique $i\in V$ such that $x_i=1$), then we have two possibilities

• $i\in \{1,2\}$. Since $i\in 𝒯(0)$, we have that

  $\varphi (1,0,x) \stackrel{(13)}{=} (1,1,0,0,\dots ,0),\varphi (2,0,x) \stackrel{(14)}{=} (1,1,0,0,\dots ,0),\varphi (3,0,x) \stackrel{(14)}{=} (0,0,0,0,\dots ,0).$

• $i\in \{3,4,\dots ,n\}$. Then without loss of generality, we can assume that $i=3$. Hence,

  $\varphi (1,0,x) \stackrel{(13)}{=} (1,1,1,0,\dots ,0),\varphi (2,0,x) \stackrel{(15)}{=} (1,1,0,0,\dots ,0),\varphi (3,0,x) \stackrel{(14)}{=} (0,0,0,0,\dots ,0).$

Consequently, we have shown that $(0,0,\dots ,0)$ is an attractor although (6) is not satisfied.

7. Existence of attractors and update orders

In the previous sections we have seen that (6) and (7) are necessary and sufficient for the existence of the attractors $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$ on $K_n$ if the synchronous or sequential update order is considered. In this section we focus on the difference between synchronous and sequential update orders in situations in which those inequalities are not satisfied. We show that the behaviour is no longer identical and that sequential updating offers a more diverse behaviour

First we study the synchronous update order.

Theorem 26

Let $(a,b,c,d)\in 𝒫$. Let us consider the (autonomous) evolutionary game $\varphi$ on $K_n$ with the utility function (4). Then there exists a non-trivial attractor of $\varphi$ if and only if either (6) or (7) holds.

Proof

Obviously, if (6) or (7) holds, then either $(0,0,\dots ,0)$ or $(1,1,\dots ,1)$ are attractors, see Theorems 9 and 10.

Now, let us assume that neither (6) nor (7) holds. Let $x\in S^V$ and $m={\displaystyle {\sum }_{i=1}^n} x_i$. If we denote by $v_1(m)$ ($v_0(m)$) the utilities of vertices with $x_i=1$ ($x_i=0$), we can easily derive that

(16) $v_1(m)-v_0(m)=(m-1)a+(n-m)b-mc-(n-m-1)d=-m((c-a)+(b-d))+n(b-d)-(a-d).$(16)

The simultaneous violation of (6) and (7) implies that $v_1(1)-v_0(1)\ge 0$ and $v_1(n-1)-v_0(n-1)\le 0$. Then (16) implies that $(c-a)+(b-d)>0$ and that there exists $m^{*}\in [1,n-1]$ defined by

(17) $m^{*}:=\frac{n(b-d)-(a-d)}{(c-a)+(b-d)},$(17)

such that $v_1(m^{*})-v_0(m^{*})=0$. Note that $\text{lim}{}_{n\to \infty }(m^{*}/n)=((d-b)/((a-c)+(d-b)))$, i.e. as $n$ tends to infinity $m^{*}/n$ tends to the interior fixed point of the replicator dynamics of HD and SH games (see Section 3).

We consider three invariant sets $\{(0,0,\dots ,0)\}$ and $\{(1,1,\dots ,1)\}$ and $M^{*}$, which is given by

$M^{*}:=\{x\in S^V:{\displaystyle \sum _{i=1}^n} x_i=m^{*}\},$

and is non-empty if and only if $m^{*}\in \mathbb{N}$. The sign of $v_1(m)-v_0(m)$ determines that

• ${\varphi }_i(x)=1$ if $m<m^{*}$,

• ${\varphi }_i(x)=0$ if $m>m^{*}$,

• ${\varphi }_i(x)=x_i$ if $m=m^{*}$.

Therefore, the basins of attraction of these three invariant sets are given by

$B(\{(0,0,\dots ,0)\})=\{(0,0,\dots ,0)\}\cup \{x\in S^V:m^{*}<{\displaystyle \sum _{i=1}^n} x_i<n\},B(\{(1,1,\dots ,1)\})=\{(1,1,\dots ,1)\}\cup \{x\in S^V:0<{\displaystyle \sum _{i=1}^n} x_i<m^{*}\},B(M^{*})=M^{*}.$

Consequently, none of these invariant sets is an attractor (see Remark 22) and there is only the trivial attractor $S^V$. ▪

The fact that $M^{*}$ is not attractive may look surprising. The proof shows that this is caused by the synchronous update order which implies that all vertices update to full cooperation or full defection. Next we provide a characterization of the existence of an attractor for the sequential update order as well.

Theorem 27

Let $(a,b,c,d)\in 𝒫$. Let us consider a non-autonomous evolutionary game $\varphi$ on $K_n$ with the utility function (4) and sequential update order. Then there exists a non-trivial attractor if and only if $(a,b,c,d)$ satisfy either

• inequality (6) or

• inequality (7) or

• $m^{*}\in [2,n-2]$ and $c-a+b-d>0$.

Proof

Using the notation of the proof of Theorem 26 we observe that there exists $\alpha ,\beta \in \mathbb{R}$ such that

(18) $v_1(m)-v_0(m)=\alpha m+\beta .$(18)

Hence, we can distinguish between five cases. Either

• $v_1(1)-v_0(1)<0$ or

• $v_1(1)-v_0(1)\ge 0$ and $v_1(2)-v_0(2)<0$ or

• $v_1(2)-v_0(2)\ge 0$ and $v_1(n-2)-v_0(n-2)\le 0$ or

• $v_1(n-2)-v_0(n-2)>0$ and $v_1(n-1)-v_0(n-1)\le 0$ or

• $v_1(n-1)-v_0(n-1)>0$.

First, we can observe that (i) is satisfied if and only if (6) holds. Then Theorem 24 implies that $(0,0,\dots ,0)$ is attractive. Similarly, (v) is satisfied if and only if (7) holds and Theorem 24 yields that $(1,1,\dots ,1)$ is attractive.

In the remaining three cases (ii)–(iv), equalities (18) and (16) imply that $c-a+b-d>0$, i.e. that there exists $m^{*}\in [-1,n-1]$ given by (17) which satisfies $v_1(m^{*})-v_0(m^{*})=0$.

Let us consider case (iii) first. Inequalities (iii) imply that $m^{*}\in [2,n-2]$ and $c-a+b-d>0$. As in the proof of Theorem 26 we see immediately that $v_1(m)>v_0(m)$ if and only if $0<m<m^{*}$ and that $v_0(m)>v_1(m)$ if and only if $m^{*}<m<n$. Moreover, sequential update order implies that for all $t\in \mathbb{N}{}_0$ we have $𝒯(t)=\{i\}$ for some $i\in V$. This implies that

• if $0<m<m^{*}$, ${\varphi }_i(t+1,t,x)=1$,

• if $m^{*}<m<n$, ${\varphi }_i(t+1,t,x)=0$,

• if $m=m^{*}$, ${\varphi }_i(t+1,t,x)=x_i$.

Consequently, we distinguish between two cases

• if $m^{*}\in \mathbb{N}$. First, we consider $x\in S^V$ such that $1\le {\displaystyle {\sum }_{i=1}^n} x_i=m<m^{*}$. Without loss of generality we can assume that the vertices are numbered so that $x_1=\cdots =x_m=0$. Define

  (19) $A:=\{(t,x)\in \mathbb{N}{}_0\times S^V:{\displaystyle \sum _{i=1}^n} x_i=m^{*}\}.$(19)
  Then
  ${\varphi }_i(i,0,x)=1$
  and thus there exists $x^{*}\in A$ (i.e. ${\displaystyle {\sum }_{i=1}^n} {\displaystyle x_i^{*}}=m^{*}$) so that
  $\varphi (t,0,x)=x^{*},\text{for} \text{all}\hspace{0.5em}t\ge m.$
  Similarly, if $x$ is such that $m^{*}<{\displaystyle {\sum }_{i=1}^n} x_i=m\le n-1$, then the first $(m-m^{*})$ vertices $i$ with $x_i=1$ switch to $x_i=0$. Consequently, the set $A$ is the attractor of $\varphi$.

• if $m^{*}\notin \mathbb{N}$, one could repeat the argument to get that any initial condition reaches a state with ${\displaystyle {\sum }_{i=1}^n} x_i=m^{*}$. If we are at such a state $x$ in time $t$ and $𝒯(t)=\{i\}$ we have that

  ${\varphi }_i(t+1,t,x)=1,$
  independently of $x_i$ at time $t$. This implies that either $x$ remains unchanged or a state with ${\displaystyle {\sum }_{i=1}^n} x_i=m^{*}$ is reached.

Similarly, if we are at a state $x$ with ${\displaystyle {\sum }_{i=1}^n} x_i=m^{*}$ we have ${\varphi }_i(t+1,t,x)=0$, and either $x$ remains unchanged or a state with ${\displaystyle {\sum }_{i=1}^n} x_i=m^{*}$ is reached.

Consequently, we observe that the set

(20) $A=\{(t,x)\in \mathbb{N}{}_0\times S^V:{\displaystyle \sum _{i=1}^n} x_i=m^{*}\hspace{0.5em}\text{or}\hspace{0.5em}{\displaystyle \sum _{i=1}^n} x_i=m^{*}\}$(20)

is an attractor. The fact that the dynamical system always switches from a state with ${\displaystyle {\sum }_{i=1}^n} x_i=m^{*}$ to a state with ${\displaystyle {\sum }_{i=1}^n} x_i=m^{*}$ and the finiteness of the graph implies that $A$ is a union of cycles.

To finish the proof, we consider cases (ii) and (iv), i.e. the situation in which $m^{*}\in [1,2)\cup (n-2,n-1]$ and $c-a+b-d>0$. In this case, the sets given by (19) and (20) are invariant by the same argument as above. However, they are not attractive, since $(0,0,\dots ,0)\notin B(A)$ if $m^{*}\in [1,2)$ and $(1,1,\dots ,1)\notin B(A)$ if $m^{*}\in (n-2,n-1]$ ▪.

Remark 28

To sum up, Theorems 26 and 27 provide a complete characterization of attractors of evolutionary games on $K_n$ with either synchronous or sequential update order. For synchronous update order, there are four possible outcomes:

• only $(0,0,\dots ,0)$ is attractive,

• only $(1,1,\dots ,1)$ is attractive,

• both $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$ are attractive,

• there is no non-trivial attractor.

These four regions correspond to those depicted in Figure 2.

For sequential update order we have another two possibilities which consist of states in which both cooperators and defectors exist together:

• there is an attractive cycle given by (20),

• there is an attractive set of invariant states given by (19).

Analysing the above results, we see that the attracting cycle and the attracting set in which both cooperators and defectors exist together can occur if and only if $(a,b,c,d)\in 𝒫{}_{\text{HD}}\cup 𝒫{}_{\text{FC}}$. $𝒫{}_{\text{FC}}$ is the only region in which all possible scenarios coexist, see Figure 4.

Figure 4 Illustration of Theorem 27 with $a=1$ and $d=0$. Both $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$ are attractive in the horizontally hatched region, $(0,0,\dots ,0)$ in the light grey region, $(1,1,\dots ,1)$ in the dark grey region. In the vertically hatched region, the attractive cycles (20) and attractors (19) occur. There are no non-trivial attractors in the two dotted regions.

Again, note that Theorems 26 and 27 are consistent with the standard evolutionary game theory [13] as $n\to \infty$. Note that both the bistability region (both $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$ are attractive) and the stable coexistence region in the sequential updating converge to $𝒫{}_{\text{SH}}$ and $𝒫{}_{\text{HD}}$, respectively. Note that, in finite populations, they are smaller but overreach to $𝒫{}_{\text{FC}}$ as well, see Figure 4.

We provide a simple example to better illustrate the cycle of length $n(n+1)$ which has been constructed in the proof of Theorem 27.

Example 29

Let us assume that $(a,b,c,d)\in 𝒫{}_{\text{HD}}\cup 𝒫{}_{\text{FC}}$ and $m^{*}\in [2,n-2]$ is such that $m^{*}\notin \mathbb{N}$. Let us consider an evolutionary game on $K_n$ with utility function (4) and sequential update order. We consider the initial condition:

$x=(\stackrel{m^{*}}{1,1,\dots 1},\stackrel{n-m^{*}}{0,0,\dots ,0}).$

Consequently, we derive that (bold numbers indicate the vertex which has just been updated)

$\begin{array}{c}\varphi (1,0,x)=(1,1,\dots 1,0,\text{0,}\dots ,0),\\ \varphi (2,0,x)=(1,1,\dots 1,0,\text{0,}\dots ,0),\\ \dots \\ \varphi (m^{*}\text{,}0,x)=(1,1,\dots 1,0,\text{0,}\dots ,0),\\ \varphi (m^{*}+1,0,x)=(1,1,\dots 1,1,\text{0,}\dots ,0),\\ \varphi (m^{*}+2,0,x)=(1,1,\dots 1,1,\text{0,}\dots ,0),\\ \dots \\ \varphi (n,0,x)=(1,1,\dots 1,1,\text{0,}\dots ,0),\\ \varphi (n+1,0,x)=(0,{\displaystyle \underset{m^{*}}{1,\dots 1,1}},0,\dots ,0).\end{array}$

We repeat this argument to get that

$\begin{array}{c}\varphi (2(n+1),0,x)=(0,0,{\displaystyle \underset{m^{*}}{1,\dots 1,1}},0,\dots ,0),\\ \dots \\ \varphi (p(n+1),0,x)=({\displaystyle \underset{p}{0,0,\dots 0}},{\displaystyle \underset{m^{*}}{1,\dots 1,1}},0,\dots ,0),\\ \dots \\ \varphi (n(n+1),0,x)=(1,1,\dots 1,0,\text{0,}\dots ,0).\end{array}$

8. Irregular graphs – role of utility functions

In this section we study simple irregular graphs – wheels $W_l$, $l\ge 4$, in which a central vertex is connected to all vertices of an $(l-1)$-cycle, see Figure 5. Our focus lies on identifying the importance of different forms of utility functions, e.g. (4), (5) or others. Evolutionary games on regular graphs, which we have considered exclusively so far, are the same for aggregate ${\displaystyle u_i^A}$ and mean ${\displaystyle u_i^M}$ utility functions (see (4) and (5)), since ${\displaystyle u_i^A}$ is just a multiple of ${\displaystyle u_i^M}$ in this case. Straightforwardly, this is no longer true for irregular graphs.

Figure 5 Wheels $W_8$ and $W_{14}$.

First, we study the attractivity of $(1,1,\dots ,1)$.

Theorem 30

Let $(a,b,c,d)\in 𝒫$. Let us consider an evolutionary game $\varphi$ on $W_l$. Then $(1,1,\dots ,1)$ is an attractor if and only if

(21) $\{\begin{array}{cc}clt;\frac{2a+b}{l-1}& if\hspace{0.5em}{\displaystyle u_i^A}\hspace{0.5em}is considered,\\ c<\frac{2a+b}{3}& if\hspace{0.5em}{\displaystyle u_i^M}\hspace{0.5em}is considered.\end{array}$(21)

Proof

Let us number the vertices, so that the central vertex $1$ is connected to peripheral vertices $\text{{2,3,}\dots ,n\}$.

• Let us consider the aggregate utility ${\displaystyle u_i^A}$ first and suppose again that the state $x\in S^V$ is such that ${\displaystyle {\sum }_{i=1}^n} x_i=n-1$.

  • If the central vertex is the single defector, then

    ${\displaystyle u_1^A}=(l-1)c,{\displaystyle u_i^A}=2a+b,i=2,3,\dots ,n.$
    Obviously, the first inequality in (21) is equivalent to ${\displaystyle u_1^A}<{\displaystyle u_i^A}$.

  • If the single defector is a peripheral vertex, we can, without loss of generality, assume that $x=(1,0,1,\dots ,1)$, i.e. vertex $2$ is the single defector. Then, we have that

    ${\displaystyle u_1^A}=(l-2)a+b,{\displaystyle u_2^A}=3c,{\displaystyle u_i^A}=2a+b,i\in N_1(2)\cap \{2,3,\dots ,n\},{\displaystyle u_i^A}=3a,i\notin N_1(2).$
    Then we can bound ${\displaystyle u_2^A}$ by ${\displaystyle u_1^A}$ from above
    ${\displaystyle u_2^A}=3c \stackrel{(21)}{<} 3\frac{2a+b}{l-1} \stackrel{(A5)}{\le } 3\frac{(l-2)a+b}{3}={\displaystyle u_1^A}.$
    Consequently $\varphi (x)=(1,1,\dots ,1)$.

• If the mean utility ${\displaystyle u_i^M}$ is considered instead then

  • If the central vertex is the single defector, we have

    ${\displaystyle u_1^M}=c,{\displaystyle u_i^M}=\frac{2a+b}{3},i=2,3,\dots ,n.$
    The latter inequality in (21) is equivalent to ${\displaystyle u_1^M}<{\displaystyle u_i^M}$.

  • If the single defector is a peripheral vertex, we can again, without loss of generality, assume that $x=(1,0,1,\dots ,1)$. Then, the utilities have the form

    ${\displaystyle u_1^M}=\frac{(l-2)a+b}{l-1},{\displaystyle u_2^M}=c,{\displaystyle u_i^M}=\frac{2a+b}{3},i\in N_1(2)\cap \{2,3,\dots ,n\},{\displaystyle u_j^M}=a,j\notin N_1(2),$
    which immediately implies that ${\displaystyle u_2^M}<{\displaystyle u_i^M}$, for all $i\in N_1(2)$.

Paragraphs 1(a) and 2(a) show that both inequalities in (21) are also necessary. If they are violated, then either $\varphi (x)=x$ (if equalities hold) or ${\varphi }_i(x)=0$ for all $i$ (if reverse inequalities hold), i.e. all vertices switch to defection and $(1,1,\dots ,1)$ cannot be attained. ▪

We can make a few straightforward observations.

Remark 31

The proof could be repeated for non-autonomous evolutionary games with sequential update order.

Note that (A5) was used in the proof. If we do not assume that (A5) holds, i.e. $a$ could be non-positive, then the condition for the aggregate utility would be

$c<m\text{in}\{\frac{2a+b}{l-1},m\text{ax}\{\frac{2a+b}{3},\frac{(l-2)a+b}{3}\left\}\right\}.$

In (21) the former inequality implies the latter. The aggregate utility function favours the vertex with higher degree, whereas the mean utility function eliminates differences resulting from different degrees. More importantly, if we consider the mean utility function the necessary and sufficient condition is independent of the wheel size $l$, whereas with the aggregate utility, the inequality is satisfied only for small wheels. Indeed, we can rewrite the inequality as $l<1+((2a+b)/c)$.

Note that the inequalities in (21) can be satisfied if and only if $c<a$, i.e. $(a,b,c,d)\in 𝒫{}_{\text{SH}}\cap 𝒫{}_{\text{FC}}$.

We can simply formulate a similar result for full defection $(0,0,\dots ,0)$.

Theorem 32

Let $(a,b,c,d)\in 𝒫$. Let us consider an evolutionary game $\varphi$ on $W_l$. Then $(0,0,\dots ,0)$ is an attractor if and only if

(22) $\{\begin{array}{cc}alt;\frac{2d+c}{l-1}& if\hspace{0.5em}{\displaystyle u_i^A}\hspace{0.5em}is considered,\\ a<\frac{2d+c}{3}& if\hspace{0.5em}{\displaystyle u_i^M}\hspace{0.5em}is considered.\end{array}$(22)

9. Open questions

In this paper we define evolutionary games on graphs rigorously as dynamical systems and also state several results on the existence of attractors, their basins of attraction and their relationship to update orders and regularity. Our results lead to many open questions, we list those which we find most interesting to consider as a next step towards the development of a theory of evolutionary games:

	(A) Mixed fixed points: Find sufficient conditions on the graph and admissible parameters $(a,b,c,d)\in 𝒫$ which ensure existence/non-existence of mixed fixed points $x^{*}=({\displaystyle x_1^{*}},\dots ,{\displaystyle x_n^{*}})$, in which cooperators ${\displaystyle x_i^{*}}=1$ and defectors ${\displaystyle x_j^{*}}=0$ coexist for some $i\ne j$.
	(B) Attractors: Construct efficient methods for finding all attractors for a given graph and admissible parameters $(a,b,c,d)\in 𝒫$.
	(C) Maximal number of fixed points: Find the maximal number of fixed points for all connected graphs with $n$ vertices.
	(D) Realization of mixed fixed points: Determine all admissible parameters $(a,b,c,d)\in 𝒫$ for which there exists an evolutionary game on a connected graph with a mixed fixed point.
	(E) Existence of cycles: Determine all admissible parameters $(a,b,c,d)\in 𝒫$ for which there exists (or does not exist) a cycle (of length at least 2) of an evolutionary game with sequential/synchronous update orders.
	(F) Maximal cycle: Find the maximal length of a cycle of an evolutionary game on an arbitrary graph with $n$ vertices.
	(G) Graph properties and evolutionary games: Relate graph features (size, regularity, diameter/girth, connectivity, clique number, etc.) to the properties of evolutionary games on these graphs (existence of attractors, fixed points, cycles, …).
	(H) Different dynamics: In this paper we used imitation dynamics (1). Describe major differences in the case that different deterministic dynamics are used (e.g. birth–death, death–birth, see Remark 4).
	(I) Utility functions: In Section 8 we showed that the aggregate utility function (4) favours vertices with higher degree. Describe this phenomenon precisely and analyse the role of other utility functions. See [20] for the discussion on averaging and accumulation of utility functions in stochastic evolutionary games.
	(J) Non-omitting update orders: Theorem 24 and Example 25 show that conditions (6) and (7) are only sufficient for attractivity of $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$. Find necessary and sufficient conditions for any non-omitting update order.
	(K) Regular graphs: Example 13 showed that (8) and (9) are only sufficient but not necessary for attractivity of $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$. Construct similar counterexamples for arbitrary $k$. Find a necessary and sufficient condition for attractivity of $(0,0,\dots ,0)$ and $(1,1,\dots ,1)$ on $k$-regular graphs.
	(L) Irregular graphs: Identify features of irregular graphs that play an essential role in the dynamics of evolutionary games on them.

Acknowledgements

We thank an anonymous referee for comments which led to an improvement of the paper. We thank Hella Epperlein for her contribution of Example 25.

Additional information

Funding

Disclosure statementNo potential conflict of interest was reported by the authors.This work is partly supported by the German Research Foundation (DFG) through the Cluster of Excellence ‘Center for Advancing Electronics Dresden’ (CfAED). The last author acknowledges the support by the Czech Science Foundation [grant number 201121757].

Notes

^1. Email: [email protected]

^2. Email: [email protected]

^3. Strictly speaking, the SH scenario is usually considered with $a>d>c>b$, we use this notation, since the equilibria share the same structure.

^4. Note that $b=d$ is not admissible.