Replicator Equation and the Evolution of Cooperation on Regular Communities

Abstract

Evolutionary graph theory studies evolutionary dynamics of a population which interactions are constrained by a graph structure. The replicator equation is one of the fundamental tools to study frequency-dependent selection in absence of mutations, this work provides the replicator equation for a specific family of graphs, characterized by connected degree-regular communities, using the method of pair approximation. The evolution of cooperation on such graphs is presented as an application of the proposed equation, showing that cooperation is sustainable for given conditions on the connectivity of the graph and on the cooperation cost.

1 Introduction

Evolutionary Game Theory [EGT], introduced by [6] in the context of the study of animal conflict, studies the behaviour of large populations of agents who repeatedly interact strategically.

One of the basic assumptions in the early studies of evolutionary dynamics is that every individual interacts with everyone else in the population with the same probability, or equivalently matching is random. If matching is not random, for example because there is a positive (negative) correlation between the type of the individual and those with whom she interacts, then we say there is positive (negative) assortative matching, due for example to kin selection [3] or to geographic proximity [7]. In this case the focus is not only on individual selection but on group selection, and on the competition among groups whose fitness depends ultimately on the group composition.

Evolutionary Graph Theory [EGrT] takes a different approach, as individuals occupy the nodes of a graph, that determines not only the interactions, but also where a new born offspring will be placed (even if the interaction and the replacement graph do not need to coincide, see for example [11]). The subject of interest of EGrT is to study the impact of the topology on evolutionary dynamics. [5] showed in their seminal paper the role of different topologies in suppressing or amplifying selection. A minimal list of references related to the present work is [10, 12, 13].

One of the problematic aspects of the study of EGrT is its computational complexity. Recently [4] showed that the complexity classes used in computer science to classify problems and the algorithms to solve them can be used to classify some of the problems of interest of EGrT, as the evolutionary processes mimic some aspect of computations. They prove that for some of these problems (for example finding the fixation probability of a structured population) it is not possible to find a solution expressed by equations (unless P=NP).

The contribution of this paper is a replicator equation under different updating rules for a family of complex graphs that are characterized by local degree homogeneity and global degree heterogeneity, that we call a multi-regular graph. The paper is structured as follows: the first part introduces the replicator equation on regular graphs, explaining the result obtained by [10] and showing in some detail how it is derived. Then a new family of graphs is introduced, and using the framework of [10] the replicator equation for these graphs is derived. This equation is then applied to study a simple example of evolution of cooperation on a multi-regular graph. A formula for computing the expected degree distribution of a random multi-regular graph is proposed, and finally an algorithm to generate graphs belonging to this family.

2 Replicator Equation on Regular Graphs

The Replicator Equation is one of the fundamental tools for the study of evolutionary dynamics. Take an evolutionary game with n strategies and a payoff matrix $\varPi$, where $\pi _{ij}$ denotes the payoff that strategy i obtains against strategy j. Say that the frequency of each strategy $i \in n$ is given by $x_i$, where $\sum _{i \in n} x_i=1$. Define as $f_i= \sum _{j \in n}x_j \pi _{ij}$ the fitness of strategy i and as $\phi = \sum _{i \in n} x_if_i$ the average fitness of the population, then the replicator equation is:

$$\begin{aligned} \dot{x}_i= x_i(f_i -\phi ) \text { for } i \in n \end{aligned}$$

(1)

According to this equation the time evolution of the frequency of strategy i in a well-mixed population depends on the relative advantage that i has in term of fitness with respect to the average fitness of the population. It is deterministic, does not consider mutation and assumes a well-mixed population. The trajectory of this equation lies entirely on the $(n-1)$-dimensional unitary simplex.

Reference [10] prove that if the game is played by a population placed on an infinitely large regular graph of degree k, there exist a closed-form solution of the replicator dynamics, which is a simple modification of the usual mean-field equation:

$$\begin{aligned} \dot{x}_i= x_i \Biggl [ \sum _{j=1}^n x_j (\pi _{ij}+b_{ij})- \phi \Biggr ] \end{aligned}$$

(2)

where $\dot{x}_i$ is the derivative of frequency of the i-th strategy with respect to time, $\pi _{ij}$ is the payoff a player with strategy i gets when the other player adopts j, and $\phi = \sum _{ij=1}^n x_i x_j (\pi _{ij}+b_{ij})$. The $b_{ij}$ term is the key parameter that is obtained as a transformation of the initial payoff matrix, depending on the updating rule. The three updating rules considered are “Birth-Death” [BD]: An individual is chosen for reproduction with probability proportional to fitness. The offspring replaces one of the k neighbour chosen at random. “Death-Birth” [DB]: An individual is randomly chosen to die. One of the k neighbours replaces it with probability proportional to their fitness. “Imitation” [IM]: An individual is randomly chosen to update her strategy. She can imitate one of her k neighbours proportional to their fitness. The three corresponding parameters are:

$$\begin{aligned} \begin{aligned}&\text {[BD]:} \quad b_{ij}= \frac{\pi _{ii}+\pi _{ij}-\pi _{ji}-\pi _{jj}}{k-2} \\&\text {[DB]:} \quad b_{ij}= \frac{(k+1)\pi _{ii}+\pi _{ij}-\pi _{ji}-(k+1)\pi _{jj}}{(k+1)(k-2)} \\&\text {[IM]:} \quad b_{ij}= \frac{(k+3)\pi _{ii}+3\pi _{ij}-3\pi _{ji}-(k+3)\pi _{jj}}{(k+3)(k-2)} \end{aligned} \end{aligned}$$

(3)

3 Replicator Equation on Regular Communities

Consider a graph where nodes may have different degrees, but nodes with the same degree tend to be connected together more than with nodes of different degrees. The graph can be hence divided in degree-homogeneous communities, bridged together by few connections. In order to be more rigorous in defining this family of graphs, some preliminary definitions are needed.

Definition 1.

Define as maximal degree-homogeneous vertex subset [DHVS] a subset of vertices with the same degree such that from each vertex in this subset there exist a path to any other vertex in the subset that traverses only vertices in the subset.

A subset of the set of vertices V of the multi-regular graph, $\mathscr {V}(d_i)$ (of degree $d_i$) can be found with the following procedure: pick a vertex of degree $d_i$, add it to $\mathscr {V}(d_i)$. Then add all its neighbours with degree $d_i$. For each neighbour add all its neighbours of degree $d_i$ that are not yet in the vertex subset. Continue until no remaining neighbour of the added vertices has degree $d_i$.

Definition 2.

Define as multi-regular graph G the graph with the following properties:

• 1. the degree of each vertex is some integer $d_i$ where $d_i \in [3, \dots , m]$.

• 2. each of the $d_i$ neighbours of each vertex has degree $d_i$ (interior vertex) or, alternatively

• 3. $d_i- \underline{d_i}$ neighbours (with $1 \le \underline{d_i} < d_i$) have degree $d_i$ and the remaining $d_i-\underline{d_i}$ have degree $d_j \ne d_i$ (frontier vertex).

• 4. each $\mathscr {V}(d_i)$ has a number of vertices $n_i \ge d_i +1$ and $n_i k_i$ even.

• 5. each $\mathscr {V}(d_i)$ has an even number of frontier vertices.

• 6. G is connected.

First of all notice that for each possible degree $d_i$ there can be more than one $\mathscr {V}(d_i)$, the only case in which the $\mathscr {V}(d_i)$ is unique being when there is no other vertex of degree $d_i$ that is not directly connected with any of the vertices in $\mathscr {V}(d_i)$. Clearly different $\mathscr {V}(d_i)$s of the same degree have different vertices because only neighbouring vertices of degree $d_i$ belong to the same DHVS. In plain words each distinct DHVS of degree $d_i$ identifies¹ a connected community of nodes where all vertices have the same degree, but some of these vertices are connected with (at least) one vertex outside that DHVS.

Properties [2] and [3] ensure that each community is degree-regular. Consider that both interior and frontier neighbouring vertices of the same degree $d_i$ belong to the same $\mathscr {V}(d_i)$. The induced subgraph of $\mathscr {V}(d_i)$ is a regular graph of degree $d_i$ provided that we consider also the edges that from the frontier vertices of $\mathscr {V}(d_i)$ goes outside $\mathscr {V}(d_i)$. Properties [5] and [6] ensure that the graph is at least 2-connected, or in general, e-connected with e even. Property [4] simply guarantees the existence of a regular graph of degree $d_i$ on the vertices of $\mathscr {V}(d_i)$.

Fig. 1.

Multi-regular graph with three $\mathscr {V}$ of degrees 3, 4 and 6. The gray vertices are the frontier vertices which create a bridge with an adjacent $\mathscr {V}$ of different degree. The blue vertices are interior vertices.

Now consider the local dynamics on a multi-regular graph. Under the assumption that the strategies of players that are more than one step adjacent do not affect local frequency, the replicator equation on each k-regular subgraph, if in isolation, would be given by Fig. 1. In order to compute the global dynamics it is necessary to take account of the distribution of each class of degree-homogeneous subgraphs of G, by weighting each class-specific replicator equation for the frequency of this class of subgraphs on the entire graph. Call $\mathbb {P}[\mathscr {G}_{d_i}]$ the probability that subgraph belongs to the class of $d_i$-homogeneous subgraphs, the global dynamics on a multi-regular graph is then:

$$\begin{aligned} \begin{aligned} \dot{x}_s=&\frac{\mathbb {E}[\varDelta x_s]}{\varDelta t} \\&= \sum _{d_i \ge 3} \sum _{k_1+\cdots +k_n=d_i} \Bigl [ x_s \Bigl ( \frac{d_i!}{k_1! \cdots k_n!}q_{1|i}^{k_1}\cdots q_{n|i}^{k_n}\varPi _{(s; k_1, \ldots , k_n)} \Bigr ) \Bigr ] \Bigl [ 1-\frac{k_s}{d_i} \Bigr ] \mathbb {P}[\mathscr {G}_{d_i}] \Big / \bar{\varPi } \\&- \sum _{d_i \ge 3} \sum _{\begin{array}{c} k_1+\cdots +k_n=d_i \\ j\ne i \end{array}} \Bigl [ x_j \Bigl ( \frac{d_i!}{k_1! \cdots k_n!}q_{1|j}^{k_1}\cdots q_{n|j}^{k_n}\varPi _{(j; d_1, \ldots ,d_n)} \Bigr ) \Bigr ] \frac{k_s}{d_i} \mathbb {P}[\mathscr {G}_{d_i}] \Big / \bar{\varPi } \\&\approx w \Bigl ( \sum _{d_i \ge 3} \frac{(d_i-2)^2}{d_i-1} \mathbb {P}[\mathscr {G}_{d_i}] \Bigr ) x_s(f_s+\sum _{d_i \ge 3} \sum _j x_j {b_{ij}}({d_i}) \mathbb {P}[\mathscr {G}_{d_i}] - \phi ) \end{aligned} \end{aligned}$$

(4)

Given the graph, hence its degree distribution, the factor $w \Bigl ( \sum _{d_i \ge 3} \frac{(d_i-2)^2}{d_i-1} \mathbb {P}[\mathscr {G}_{d_i}] \Bigr )$ is a constant, and again just represents a change of time scale, so we can rewrite (4) as:

$$\begin{aligned} \dot{x}_s=x_s(f_s+\sum _{d_i \ge 3} \sum _j x_j {b_{ij}}({d_i}) \mathbb {P}[\mathscr {G}_{d_i}] - \phi ) \end{aligned}$$

(5)

Equation (5) is the replicator equation on a multi-regular graph.

4 Generating a Random MR Graph

In this section an algorithm for the construction of a Random Multiregular Graph is proposed. The algorithm is based on a modified version of the pairing model.

Fix the number of vertices to n and let $d_i \ge 3$ the degree. Define as $\mathbb {P}(d_i)$ the fraction of vertices with degree $d_i$. The nearest integer $[n \mathbb {P}(d_i) ]$ is the number of vertices with degree $d_i$; as in the pairing model, assume this number to be even. Define also as r the ratio of vertex degree to vertices with the same degree to vertices with other degrees.

• 1. Create a set of $[n \sum _{d_i} \mathbb {P}(d_i)d_i]$ points.

• 2. Divide them in n buckets in the following way.

  • a. Take $[n bP(d_i)]$ points and put them in $[n bP(d_i)]$ different buckets.

  • b. Add $d_i-1$ points to each of these buckets.

  • c. Repeat the same procedure for all the other $d_i$. In this way for each $d_i$ there will be $[n bP(d_i)]$ buckets with $d_i$ points.

• 3. Pick a random point, say it is in a bucket with $d_i$ points.

• 4. Join it with probability r to a random point among those in one of the $[n bP(d_i)]$ buckets with $d_i$ points, and with probability $1-r$ to any of the other points at random. Continue until a perfect matching is reached.

• 5. Collapse the points, so that each bucket maps onto a single vertex of the original graph. Retain all edges between points as the edges of the corresponding vertices.

• 6. Check if the corresponding graph is simple.

Step 4 can also be changed by joining the picked point with any other point at random. The reason for imposing the ratio of connections with other-degree-vertices is because for some applications could be useful to control the formation of dense degree-homogeneous subgraph with few “bridge” connections with the outside. Here the fraction of frontier vertices is assumed uniform along the subgraphs, while it could be reasonable to make r vary with the degree $d_i$, depending on the models considered. A version of the proposed alogrithm has been implemented in Python, using Network which builds random multi-regular graphs with specified number of frontier vertices, and is presented in the appendix.

5 Evolution of Cooperation

The evolution of cooperation has been largely studied both in EGT and EGrT, [2, 5, 8, 9]. Here we study cooperation with a $2\times 2$ symmetric game, a classical Prisoner’s Dilemma (PD) [1]. The two strategies are Cooperator and Defector, and the game is described by the payoff matrix:

	C	D
C	$b-c$	$-c$
D	b	0

Given that Defector is a strictly dominating strategy, D is a strict NE and an ESS, hence the stationary state of the replicator equation (1) is at a point in which everybody in the population is a defector, as the differential equation:

$$\begin{aligned} \dot{x}_c=x_c (1-x_c) (-c) \end{aligned}$$

(6)

has two fixed points, at $x_c=0$ and $x_c=1$, and since the derivative at $\frac{d\dot{x}_c}{dx}\big |_{x=0}<0$ and $\frac{d\dot{x}_c}{dx}\big |_{x=1}>0$ the only stable equilibrium is where defectors win.

When cooperation is studied on a regular graph interesting novelties emerge [10]: while under BD updating there is no difference with well-mixed populations, under DB updating cooperation is a stable state if $b/c>d$ where d is the degree of the regular graph. Analogously in the case of IM updating cooperation prevails if $b/c>d+2$. In both cases what emerges is that in order to sustain cooperation when agents are highly connected, the benefit/cost ratio has to be very high.

Let’s now examine the replicator equation on a MRG for the above PD: call $x_c$ the frequency of cooperators, $(1-x_c)$ the frequency of defectors. The replicator equation with BD updating is:

$$\begin{aligned} \dot{x}_c=x_c (1-x_c) \Bigl ( \sum _{d_i \ge 3}\frac{-c}{d_i-2}\mathbb {P}[\mathscr {G}_{d_i}] -c\Bigr ) \end{aligned}$$

(7)

so even in the MRG case with BD there is no difference between a well-mixed and a structured population, as here the only stable fixed point is $x_c^*=0$.

Things gets more interesting in the case of DB updating. The replicator equation on MRG is:

$$\begin{aligned} \dot{x}_c=x_c (1-x_c)\Bigl ( \sum _{d_i \ge 3}\frac{d_i(b-c)-2c}{(d_i+1)(d_i-2)}\mathbb {P}[\mathscr {G}_{d_i}] -c \Bigr ) \end{aligned}$$

(8)

The equation above can be rewritten as:

$$\begin{aligned} \dot{x}_c=x_c (1-x_c)\Bigl ( \frac{bf(d_i,\mathbb {P}[\mathscr {G}_{d_i}],b,c) - cg(d_i,\mathbb {P}[\mathscr {G}_{d_i}],b,c)}{\prod _{d_i \ge 3} (d_i+1)(d_i-2)}\Bigr ) \end{aligned}$$

(9)

where f and g are both multivariate polynomials in $d_i$. Cooperation will be sustainable if the inequality $b/c > g/f$ holds, unfortunately finding the roots of the polynomials can be hard, even in the simplest case where there are only two degree homogeneous subgraphs. We find an easy to intertpret upper bound of g / f.

Proposition 1.

Cooperation is sustainable in a Prisoner Dilemma on a multi-regular graph with death-birth updating if the relative benefit of cooperation is greater than the average degree:

$$\begin{aligned} \frac{b}{c}>\sum _{d_i}d_i\mathbb {P}[\mathscr {G}_{d_i}] \end{aligned}$$

(10)

Proof.

We know from (9) that cooperation is sustainable if $b/c>g/f$, as $\frac{d\dot{x}_c}{dx}\big |_{x=1}<0$. We now prove that $\sum _{d_i}d_i\mathbb {P}[\mathscr {G}_{d_i}]$ is an upper bound for g / f. Consider that we can write g / f as:

$$\begin{aligned} \frac{g}{f}= \frac{ \prod _{d_i} (d_i +1)(d_i -2) + \sum _{d_i}(d_i+2)\mathbb {P}[\mathscr {G}_{d_i}]\prod _{d_j\ne d_i} (d_j +1)(d_j -2)}{\sum _{d_i} d_i\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j\ne d_i} (d_j +1)(d_j -2) } \end{aligned}$$

(11)

Now write $A=\sum _{d_i}d_i\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j\ne d_i} (d_j +1)(d_j -2)$ and $B=2\sum _{d_i}\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j\ne d_i} (d_j +1)(d_j -2)$ (both of degree $2(n-1)$), and $C=\prod _{d_i} (d_i +1)(d_i -2)$ (of degree 2n).

The upper bound condition is then:

$$\begin{aligned} \frac{A+B+C}{A} < \sum _{d_i}d_i\mathbb {P}[\mathscr {G}_{d_i}] \end{aligned}$$

(12)

or equivalently:

$$\begin{aligned} A \Bigl ( \sum _{d_i}d_i\mathbb {P}[\mathscr {G}_{d_i}] -1 \Bigr )-B >C \end{aligned}$$

(13)

as $\sum _{d_i}d_i[\mathscr {G}_{d_i}]\ge d_i^{min}$, where $d_i^{min}$ is the lowest degree in the sequence, with equality only in the degenerate case of a regular graph, then $A \Bigl ( \sum _{d_i}d_i[\mathbb {P}\mathscr {G}_{d_i}] -1 \Bigr )\ge (d_i^{min}-1)A$. Hence

$$\begin{aligned} A \Bigl ( \sum _{d_i}d_i\mathbb {P}[\mathscr {G}_{d_i}] -1 \Bigr )-B \ge A(d_i^{min}-1)-B= \sum _{d_i}[(d_i^{min}-1)d_i - 2]\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j\ne d_i} (d_j +1)(d_j -2) \end{aligned}$$

(14)

Also $\sum _{d_i}\mathbb {P}[\mathscr {G}_{d_i}]\prod _{d_j\ne d_i} (d_j +1)(d_j -2) \ge \varPi ^{min}$ where $\varPi ^{min} = \min \limits _{d_i}{\prod _{d_j\ne d_i}} (d_j +1)(d_j -2)$ so clearly:

$$\begin{aligned} \sum _{d_i}[(d_i^{min}-1)d_i - 2]\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j\ne d_i} (d_j +1)(d_j -2) \ge [(d_i^{min}-1)d_i + 2]\varPi ^{min} \end{aligned}$$

(15)

Now rewrite C as $C=\varPi ^{min}(d_i+1)(d_i-2)$, so (13) holds if

$$\begin{aligned} \,[(d_i^{min}-1)d_i - 2]\varPi ^{min} > \varPi ^{min}(d_i+1)(d_i-2) \end{aligned}$$

(16)

given $d_i^{min}d_i > d_i^2$ as long as the graph is MR:

$$\begin{aligned} d_i^{min}d_i -d_i-2 > d_i^2-d_i-2 \end{aligned}$$

(17)

holds for every $d_i$ and this ends the proof.

The RE in the case of IM updating is:

$$\begin{aligned} \dot{x}_c=x_c (1-x_c)\Bigl ( \sum _{d_i \ge 3}\frac{b d_i - c (d_i+ 6)}{(d_i+3)(d_i-2)}\mathbb {P}[\mathscr {G}_{d_i}]\Bigr ) \end{aligned}$$

(18)

We find an equivalent condition for cooperation with IM updating.

Proposition 2.

Cooperation is sustainable in a Prisoner Dilemma on a multi-regular graph with imitation updating if the relative benefit of cooperation respects:

$$\begin{aligned} \frac{b}{c}>\sum _{d_i}(d_i+2)\mathbb {P}[\mathscr {G}_{d_i}] \end{aligned}$$

(19)

Proof.

As above, with $A=\sum _{d_i}d_i\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j\ne d_i} (d_j +3)(d_j -2)$ and $B=6\sum _{d_i}\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j\ne d_i} (d_j +3)(d_j -2)$ and $C=\prod _{d_i} (d_i +3)(d_i -2)$ so that (17) becomes:

$$\begin{aligned} d_i^{min}d_i -d_i-6 > d_i^2-d_i-6 \end{aligned}$$

(20)

always true when graph is MR.

So the higher average connectivity the higher the relative benefit necessary to sustain cooperation, which means that on a MRG cooperation is sustainable as long as highly connected subgraphs are a low fraction of all the subgraphs. Hence we expect that the family of MRGs where $\mathbb {P}[\mathscr {G}_{d}]$ is a power-law distribution should favor cooperation under a relatively low benefit-cost ratio.

Assuming continuity of the degree, if the degree distribution has law $p(d)=(\gamma - 1){d}_{min}^{\gamma -1}d^{-\gamma }$, then cooperation prevails for

$$\begin{aligned} \frac{b}{c} > (\gamma -1){d}_{min}^{\alpha -1}\frac{{d}_{max}^{2-\gamma }- {d}_{min}^{2-\gamma }}{2-\gamma } \end{aligned}$$

(21)

where ${d}_{min}$ and ${d}_{max}$ are the minimum and maximum degree respectively.

As in [10] we also find equilibria in which both cooperators and defectors coexist. Consider for example the Prisoner’s Dilemma in the general form:

	C	D
C	R	S
D	T	P

where $T>R>P>S$. The replicator equation under BD is:

$$\begin{aligned} \dot{x}_c=x_c(1-x_c)\biggl (\frac{x_c \phi - \psi }{\prod _{d_i}(d_i+1)(d_i-2)}\biggr ) \end{aligned}$$

(22)

where

$$\begin{aligned} \begin{aligned} \phi =&(T+S-P-R)\prod _{d_i} (d_i+1)(d_i-2) \\ \psi =&S\prod _{d_i} (d_i+1)(d_i-2) + \sum _{d_i} (S+R(1+d_i)-T) \mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j \ne d_i} (d_j+1)(d_j-2) \\ -&P\prod _{d_i} (d_i+1)\biggl [\prod _{d_i}{(d_i-2)}+\sum _{d_i}\mathbb {P}[\mathscr {G}_{d_i}] \prod _{d_j,d_k \ne d_i}(d_j-2)(d_k-2)\biggr ] \end{aligned} \end{aligned}$$

(23)

Lemma 1.

There exists multi-regular graphs for which the Prisoner’s Dilemma in the general form has a mixed equilibrium.

From (22) it is clear that a mixed equilibrium exists if $0<\psi / \phi < 1$. At this point we are not able to rigorously determine the conditions in terms of degree distribution and payoffs under which there is a mixed equilibrium, but we show its existence with some examples.

Consider as simple example a MRG with degree sequence (3, 4, 9) the RE is:

$$\begin{aligned} \dot{x}_c=x_c(1-x_c)\biggl (\frac{x_c \phi - \psi }{140}\biggr ) \end{aligned}$$

(24)

where $\phi =140(T +S - P - R)$ and $\psi =140 (S-P) + 2\mathbb {P}[\mathscr {G}_{d_9}] (10 R - 10 P - T + S) + 14\mathbb {P}[\mathscr {G}_{d_4}] (5 R - 5 P - T + S) + 35\mathbb {P}[\mathscr {G}_{d_3}] (4 R - 4 P - T + S)$. So we have three equilibria, $x_c^*=0$, $x_c^*=1$ and $x_c^*=\frac{\psi }{\phi }$. Hence we can have an equilibrium where cooperators and defector coexist (Fig. 2). We shall now analyze how this equilibrium varies according to the topology in different PDs in general form (Table 1).

Table 1. Game 1: stable mixed equilibrium

Fig. 2.

Simplex of topologies (a) The vertices are the degenerate case of regular graphs of degree 9 (green), 4 (blue) and 3 (red) respectively. (b) corresponding level of cooperation in equilibrium (y-axis) and average degree (x-axis).

Table 2. Game 2: unstable mixed equilibrium

Table 3. Game 3: both stable and unstable mixed equilibrium

An interesting example is given by (Game 3). In this case depending on the graph topology the mixed equilibrium can be either stable or unstable (Table 2). When the equilibrium is unstable the $x_c^*=1$ is stable, while as the average degree increases towards its maximum the mixed equilibrium becomes stable, even if the cooperation level is decreasing with the connectivity (Table 3). When the average degree approaches 9, so where the graph is almost a regular graph of degree 9, the only stable equilibrium is where defectors win, $x_c^*=0$

6 Conclusions

This paper provides a version of the replicator equation on graphs. A specific graph structure is constructed, called multi-regular graph, that keeps the relevant properties of (local) regularity and connectedness, and the replicator equation for this kind of graph is derived. The extended replicator equation depends on the probability distribution of the degree-homogeneous subgraphs in a multi-regular graph. Following a random regular graph approach we provide a formula for computing these probabilities under random graph formation and an algorithm based on the pairing model for the construction of random MRGs. We then analyze the evolution of cooperation on MRGs, finding a condition for the sustainability of cooperation, and we provide examples of how the degree distribution of the MRG influence the dynamics.