A pedestrian review of games on structured populations

Abstract

Understanding the mechanisms of evolution of cooperation and its sustenance has gathered momentum since the last few decades of the twentieth century. However, the complete picture is yet to emerge. Evolutionary game theory aims to model evolutionary dynamics in a population by drawing on the principles of game theory. Spatially restricted interactions, such as in ecological systems, are rather common in nature. When interactions among the individuals in a population are structured, the outcome of the game is significantly different from that of a well-mixed population. In this mini-review, targeted towards a very broad audience of all backgrounds, we summarise some of the critical research by evolutionary biologists, computer scientists, mathematicians and physicists on evolutionary games in structured populations. We also discuss the influence of structure on evolutionary games in diverse scenarios ranging from laboratory environments to multiplex networks. Along the way, we also try to harmonise a few conflicting results in the literature.

1 Introduction

Interactions, chiefly cooperative, among single cells give rise to multicellular units, living systems and a plethora of complexity. Cooperative behaviour in the living world can be observed in many life forms ranging from diverse prokaryotic to eukaryotic populations around us. The warning calls from sentinels to alert their meerkat brethren from predators [1], the spirited defence by muskoxen to save their young from the wolves [2], inter-species cooperation among bacteria for their survival and efficient nutrient consumption [3], interactions of microbial communities in the human gut [4] and many actions among humans, societies and indeed nations [5] are a few examples of cooperation. A good number of studies on the emergence of cooperation in games deal with rational agents, who, by definition, act in their own self-interest. Indeed, these agents can choose or modify their interaction strategy depending on their circumstances, opponents and their own prior experience. It is indeed intriguing that despite these agents choosing only those actions which benefit themselves, cooperation often unaccountably arises in the population. Mention must also be made of altruism—which is a term usually reserved for agents whose actions benefit others, even at the cost of their own interest.

Interestingly, cooperative acts are often exploited by free riders according them undue fitness advantages and giving rise to social dilemmas. For example in microbes, free riders or defectors can bypass the expense of metabolic costs for cooperative acts. Naively, one would infer that as a result of competition defectors should always achieve higher reproductive fitness, ultimately emerging superior in the evolutionary run. But then, cooperation still emerges and in fact is rather ubiquitous. How and why this is so remains to be completely solved. Some well-known biologically motivated explanations about the maintenance of cooperation have been offered [6], which are under increasing study of late [7,8,9]. Moreover, there has been some work on “assured fitness returns” model showing how group living evolves over solitary life, independent of genetic relatedness [10].

Towards the latter half of the twentieth century, development of game theory ushered a tremendous change in our understanding of evolutionary processes. The names of William Hamilton and Robert Trivers deserve mention as they were early pioneers in using game theoretical concepts in biology. Smith and Price [11] were the first to introduce game theory into evolutionary dynamics and became pioneers of the area which we now refer to as evolutionary game theory. Significant early contributions to this field were also made by Peter Taylor, Joseph Hofbaur and Karl Sigmund.

There are various schools of thought regarding the driving influence of evolutionary processes. According to “selectionists”, a strategy dependent payoff difference is the main driving force of evolution. Building on this notion, mechanisms such as kin selection [6, 12], reciprocal altruism [13,14,15], punishment [5, 16, 17] and network reciprocity [18, 19] have been somewhat successful in explaining how cooperation can be established. However, these neo-Darwinian approaches still leave unanswered questions. Apart from selectionists, there are “neutralists” who believe that, not only the interaction payoffs, but also the stochasticity in death and birth systems, mutations or fluctuations in genetic material, etc. [20, 21], have significant influence on evolutionary processes. According to them, evolution is a consequence of random fluctuations which is inherent in nature. Stochasticity can inspire systems to select cooperators in spite of their lower fitness advantage, over defectors. There are also some researchers who unify both approaches in terms of the mean extinction time. According to them, if stochasticity of a system is large, evolution is neutral. However, in less stochastic regimes evolution is mainly governed by selection [19].

The outcome of evolutionary games may be decisively altered by the imposition of structure on interactions within a population and is the focal point of this review. In structured populations, spatial factors introduce limitations in interaction between individuals. Furthermore, heterogeneity of connections might prove to be beneficial towards maintenance of cooperation [18], though it depends on a number of conditions [22]. Drawing upon research which considers a constant population [23, 24], some recent works have included growth of the population. One such work observed that a transient but robust increase in cooperation can be found in growing populations [20]. The coupling of demographic noise (arising from inherent stochasticity) and external noise (arising from environmental carrying capacity) significantly changes the fixation probability of mutants in evolutionary games [21]. We discuss all of these and more, in detail in the following sections.

2 Evolutionary game theory

Classical game theory was originally developed to study mathematical models of conflict and cooperation between rational individuals [25]. It was introduced to evolution by Maynard Smith and Price [11], and this successful fusion gave rise to the popular field of evolutionary game theory. Before the application of game theory, evolution was studied as a time-dependent continuous process, where the evolutionary outcome was stochastic. Application of game theory confers the freedom to predict evolutionary outcomes as a steady-state frequency of sub-populations with different strategies, which are selected using the rules of the game. In classical game theory, players are considered as rational individuals and are allowed to chose their own strategy. However, in evolutionary game theory, strategies remain invariant and players are unable to choose them. In game theoretic literature, strategies associated with such mechanisms are sometimes referred to as pure strategies [26]. This “purity” arises because the behaviour of an organism is genetically predetermined and not an available option to be chosen by it at will.

To explain this restriction on strategy, let us present an example from the bacterial domain. Consider two populations of Escherichia coli. One of the two, the mutant population has the capacity to degrade beta-lactam antibiotic due to some additional gene/(s), whereas the native one is sensitive to the said antibiotic. Now, let us place these mutant cells with the native E. coli cells together in an environment laden with a reasonable quantity of beta-lactam antibiotic. Apart from happily thriving, the mutant strain would wittingly or unwittingly help even the native cells to grow because it would degrade the antibiotic for its own survival. This “benign” behaviour of our mutant E. coli and the resultant “cooperation” witnessed in such microbial systems does not really arise out of a surge of altruism or kindness. It is simply because our mutant is genetically programmed to behave as it does. The dynamics of such systems has been studied experimentally [3].

Therefore, unlike classical game theory, there are a few assumptions which are required for evolutionary games. These are as follows:

• Every individual in a genetically homogeneous population is considered to be genetically predetermined to play a single strategy, which is encoded in the organism’s genome.

• As these strategies are pure and genetically predetermined, mixed strategies would be strictly avoided by any individual in such genetically homogeneous populations.

• The population should be large enough.

• There would be some level of genetic, metabolic or physical overlap for mutual interaction.

• All players follow the same strategy update rules.

Considering all of these assumptions, evolutionary games describe the dynamics of a population on evolutionary time scales. In classical game theory, an important concept is the Nash equilibrium [27]. It can be thought of as a stable state of the system attempting to capture the interaction of different participants in a non-cooperative game. If the strategies of the other players remain unchanged, no participant can gain by a unilateral change of strategy.

In evolutionary game theory, instead of using the Nash equilibrium for an equilibrium description, we use evolutionary stable strategies (ESS) [26]. “Evolutionary stability” implies such a genetic composition of a population, which no other mutant genotype can successfully invade by evolutionary processes like natural selection. ESS is always chosen over any other mutant strategy by the process of natural selection. When every individual of a population abides by an evolutionary stable strategy, the strategy of any other mutant cannot subjugate the population by natural selection. One can also encounter genetically heterogeneous populations containing different mutant strains of the same species. Such situations might be handled better by using mixed strategy dynamics, which are just beginning to be explored [28, 29]. In some games like the Hawk-Dove game (not discussed here), the presence of more than one genetically imprinted strategies is also possible [30]. It should be especially noted that incorporation of rationality in a player’s decision-making ability can alter the game outcome significantly [32].

3 Games between two players

Let us consider a two-player game where one of the players, C, always cooperates to produce public goods. The other one, D, uses it without bearing any cost of production and can thus be called a defector. The players will always follow a pure strategy as they are genetically programmed to do so. The outcome of their interactions is represented by the following “payoff” matrix:

$$\begin{aligned} \begin{array}{ l c r } &{} C &{} D \\ C &{} R &{} S \\ D &{} T &{} P \\ \end{array} \end{aligned}$$

Here, the rows represent the payoffs of C and D. From this matrix, we can see that mutual cooperation leads to a payoff, R, for both cooperators. Interaction between a cooperator and a defector results in a payoff, T, for the defector and a payoff, S, for the cooperator. T denotes the payoff for temptation to defect, while S is called the “sucker’s payoff”. If both defect, both will be rewarded a punishment, P.

Let us now think at the level of a population comprising these two types of participants or sub-populations, namely cooperators, C, and defectors, D. The frequency of cooperators is denoted by x. Therefore, the frequency of the defectors is $(1-x)$. As per the selectionist view, we can presume that the expected payoff of a player is the prime measure of its fitness or reproductive ability. Let us denote this fitness or expected payoff by $f_C$ and $f_D$ for cooperators and defectors, respectively.

$$\begin{aligned} f_\mathrm{C}= & {} R x + (1-x)S \end{aligned}$$

(1)

$$\begin{aligned} f_\mathrm{D}= & {} T x + (1-x)P \end{aligned}$$

(2)

We can calculate the average fitness of the population, $\phi$, from Eqs. 1 and 2. Now, the difference between the fitness of an individual cooperator or defector and the average fitness of the population can arguably drive the rate of change in frequency of cooperators or defectors.

$$\begin{aligned} \phi= & {} x f_C + (1-x) f_D \end{aligned}$$

(3)

$$\begin{aligned} {\dot{x}}= & {} (f_C-\phi )x \end{aligned}$$

(4)

Substituting Eq. 3 in Eq. 4 and then using the values of $f_C$ and $f_D$ from Eqs. 1 and 2 in Eq. 4, we get,

$$\begin{aligned} \dot{x}=((R-S-T+P) x-P+S) x(1-x) \end{aligned}$$

(5)

The outcome of this simple nonlinear differential equation depends on the elements of the payoff matrix and the stability of the fixed points indicate the evolutionary stable strategy for the game under consideration. We discuss some cases below:

• If $T> R> P > S$, the overall fitness of D is higher than C. So, in this situation C is always exploited by D. This type of game is called Prisoner’s Dilemma (PD). Here, defection is always the best strategy—irrespective of the strategy of the opponent and selection favours defectors. PD is named after the well-known social dilemma of two prisoners. Instead of cooperating among each other which would be mutually beneficial—both of them tend to defect from one another, due to factors such as enticement by law enforcement.

• If $T < R$ and $P < S$, the situation is exactly opposite to that in Prisoner’s Dilemma. Here cooperators dominate, as their fitness is always higher than defectors. This type of game is known as the Harmony Game. Harmonisation in social structure can emerge due to players helping each other. This game is comparatively lesser studied as there is a tendency for maintenance of cooperation.

• When $T> R> S > P$, then the system will converge to equilibrium at

  $$\begin{aligned} x_\mathrm{eq}=(P-S)/(R-S-T+P) \end{aligned}$$

  (6)

  Under these conditions, both C and D coexist. This type of game is known as the Chicken game or Snowdrift game. Let us picture two drivers heading on a road towards each other from opposite directions. If one of them does not change direction, a crash is very likely to occur. The one who does change direction is supposed to have “chickened” out! Similarly, for the snowdrift (SD) game, imagine two drivers sitting in their own car, which are separated by a pile of snow on a chilly day. Let us presume that neither is driven by kindness or the compulsion to reach his/her destination quickly. Eventually, one of them might do the hard job of shovelling and the “smarter” person just sits in the car, perhaps enjoying some hot coffee over loud music.

• If $T < R$ and $S < P$, then $x_{eq}$ is a point of unstable equilibrium. Such games are known as coordination games. Here, it is beneficial for both players to have the same strategy, as if in coordination.

  Dealing simultaneously with four parameters of a system is obviously non-trivial. Therefore, we may consider $R=1$ and $P=0$ [32]. With this choice, regions representing different games on the $T-S$ plane are shown in Fig. 1.

Fig. 1

Different types of games in T–S plane

4 Structured populations

In unstructured or mixed populations, maintenance of cooperation in social dilemmas can be explained by kin selection [6], direct reciprocity and indirect reciprocity [33]. However, we will soon see that in structured populations, group selection and network reciprocity caused by structural restrictions may lead to significant alterations in the game dynamics. Various types of structures can be used to model populations, most common among them being graphs. It is worthwhile to mention here that throughout this review, we will use the terms graph and network interchangeably. Networks have been used in many contexts ranging from image processing and non-invasive diagnostics to structural optogenetics, intra-protein contacts and fitness landscapes [34,35,36,37,38,39,40]. Below we give a brief introduction to network structures which are commonly used to model evolutionary games on networks. It should be noted that mathematical simplifications such as denoting well-mixed populations by complete graphs might lead to elegant closed form solutions. However, in reality an individual may not interact with all its neighbours at a time. Therefore, studies on more realistic structures are highly desirable.

Lattice: Lattice is an extensively used form of regular graphs and is often also referred to as grid. They possess the simplest of graph topologies. Commonly used examples of lattices include triangular, square or rectangular, hexagonal, and so on. A square lattice is depicted in Fig. 2a. In such regular structures, random long-range connections are absent. It represents a population where each individual can interact only with a finite number of its (usually nearest or nearer) neighbours.

Cycle graph: Cycle graphs also sometimes referred to as circular graphs are exemplified in Fig. 2b. It is a graph that contains a single cycle for a given number of vertices connected in a closed chain. In an undirected cycle graph, every vertex is connected with two of its adjacent vertices, resulting in a degree of 2 for each vertex. This is also a regular structure where long-range connections are absent.

Random regular graph: In a random regular graph, each node is connected with k other randomly selected nodes. This is a “regular” structure since all nodes have the same degree albeit with a random connectivity pattern. Random long-range connections are obviously present in such graphs. It represents a population where each individual interacts with a fixed number of individuals randomly located in the population. A random regular graph with average degree 2 is represented in Fig. 2c.

Complete graph: In a complete graph, each node is connected with every other node as shown in Fig. 2d. The total number of edges in a complete graph is given by $N (N-1)/2$ where N is the total number of nodes. It represents a structure where each individual interacts with every other individual of the population. It can be thought of as the graphical equivalent of a well-mixed population.

Small-world graph: Small-world topology can be generated by various algorithms. In the well-known Watts–Strogatz model, one can start with a regular ring lattice of N nodes with an even mean degree, K, where $N\gg K \gg \ln N \gg 1$. Upon rewiring every edge with a probability above a certain threshold to a randomly chosen node in the network, a small-world network with random, long-range connections can be achieved. A prime feature of a connected SW graph is that one can reach a given node from a randomly selected node by a (rather) small number of hops. A quantity of interest is the ratio of number of closed triplets of vertices in the network to the number of all triplets (open and closed) of vertices. For any SW network, this quantity could be even up to a few orders of magnitude higher than those obtained for randomised versions of the same network. These graphs are obviously not regular and possess a reasonable degree of heterogeneous connectivity. A small-world graph is represented in Fig. 2e.

Scale-free graph: Throughout this review, whenever we mention a “scale-free” graph or network, we strictly mean such graphs which possess a power law degree distribution. Obviously, scale-free networks are characterised by highly heterogeneous connectivities implying a large variation in the degree of nodes. A number of methods can generate scale-free networks [41]. A popular way to generate these networks is through the mechanism of preferential attachment [42, 43]. In the Barabasi–Albert model of network growth [42], one starts with $m_0$ number of nodes. At each time point a new node is attached to the existing m nodes, where $m\le m_0$. Thus, exactly, m number of edges are added to each new vertex, appearing in the graph. The attachment probability depends on the degree of previously existing nodes expressed as $P_i=k_i/\sum _{}^{}k_i$, where $k_i$ is the degree of ith node. In this manner, ‘rich keep getting richer’. In the asymptotic limit, the degree distribution of the network is a power law. In this network structure, a few nodes called “hubs” possess connectivities which are much more than the average degree. A scale-free graph is represented in Fig. 2f.

Fig. 2

Various graph topologies are used to describe structured populations: a lattice, b cycle graph with average degree 2, c random regular network with average degree 2, d a complete graph, e “small-world” network with average degree 6 which was generated from a regular network with rewiring probability 0.1, and f “scale-free” network with average degree 2. Here, scale-free and small-world networks have 512 and 128 nodes, respectively, while all the other networks have 20 nodes

5 Structural restrictions in evolutionary games

Interactions allowed only among neighbouring agents, defined according to a specified connection topology, had been studied early on by some of the pioneers of game theory. Specific mention must be made of Axelrod, who introduced the concept of territoriality as one of the four factors of social structure which helps to maintain cooperation by spatial limitation. Additional mention must be made of the use of agents ‘playing’ with their neighbours on a two-dimensional lattice [44]. Social constrictions like race, sex, colour, etc., which impose specific spatial limitations in social structures and their effects on maintenance of cooperation had also been studied in considerable detail [45].

Spatial restriction inside a population was considered in a seminal work by Nowak and May. Individuals of the population are located on the vertices of a square lattice and are allowed to interact only with their nearest neighbours [32]. Imposition of (structural) restriction on the population leads defectors (but not cooperators) to forgo the luxury of accumulating payoffs from neighbours. Structural restrictions limit the ability of an individual to gain access to the overall strategy distribution in the population. In such situations, the lack of benefit gained by the neighbours of a defector inhibits the formation of clusters. The emergence of such structure has been observed in multiagent simulations in groups of cells having both cooperators and defectors. Such structures depend on the relevant set of biological and physical parameters [46, 47]. Also, it has been observed from computational studies that mobility helps in assorting groups of cooperators in a well-mixed population [48]. In regular network structures, where the degree of all nodes is same, all individuals are allowed to interact with the same number of neighbours. In this scenario, defectors are again winners in the long run. So, although interactions on regular spatial structures create a more comfortable situation for cooperators than those encountered by them in well-mixed populations—it eventually fails to establish cooperation in the long run. The level of restriction varies with the heterogeneity of the network, and graph topology affects the game outcome [49, 50]. In heterogeneous structures, cooperation is maintained better than in regular structures. This assumption works reasonably well in PD [51] and will be discussed in further detail in Sect. 7.

However, in snowdrift games, this scenario is slightly different. Earlier, we saw that the equilibrium frequency of mutual cooperation in snowdrift game in Eq. 6. Denoting the cost to benefit ratio of mutual cooperation as r, we can derive the equilibrium frequency of cooperators from Eq. 6 to be $(1-r)$ in well-mixed populations. It is seen that, for small values of r, cooperator frequency is higher than the equilibrium frequency in snowdrift games. However, it decreases for higher values of r [17]. Under structural restrictions, the game outcome differs in case of SD as compared to PD. Cooperator fraction in a structured population is generally lower than it is in a well-mixed mixed situation [52].

6 Fitness and reproduction

Evolution of a population occurs by an update of the strategy of individuals resulting in an overall change in the respective fraction of sub-populations. The fitness of a player as a function of its accumulated payoff depends on the strategies that its neighbours possess. As the full mechanisms governing evolution are not yet well understood, it is safe to assume that there are many factors ranging from metabolic state of the players to environmental conditions on which a player’s total fitness depends. Keeping this in mind, most researchers assume that the fitness accumulated from the game payoff is a small part of the total fitness [19] which is basically the weak selection process. Indeed, even from the neutralist point of view this is acceptable as weak selection introduces additional stochasticity in the system, which is more realistic [53].

Reproductive prowess is a major driving force of the evolutionary dynamics. In evolutionary game theory, two types of reproductive mechanisms have been thoroughly studied: (1) Moran process [54] and (2) Wright-Fisher process [55]. In Moran process, asynchronous reproduction in a population takes place. Here, at a given time, one individual is selected randomly to reproduce where another individual is chosen to die according to its fitness. Such upgradation promotes cooperation in the snowdrift game for genetically heterogeneous populations following mixed strategies [56]. In the Wright-Fisher model, the mechanism of reproduction is different. Here, all individuals in a population reproduce at the same time and the number of offspring is proportional to their ancestor’s fitness. The next generation is formed by randomly choosing individuals from the set of offspring. Unlike the previous case, here cooperation is opposed in the snowdrift game for genetically heterogeneous populations [56]. In both processes, the population size is maintained constant. However, fitter individuals may fix themselves in the population by growing faster, which results in an expansion of the population. We will discuss this in detail in Sect. 12.

One way to measure whether a mutant is favoured or opposed by natural selection is to calculate the fixation probability of that mutant [19]. Fixation probability is the probability that a single mutant starting from a random position turns the whole population into its own type. If there are N number of individuals in a population, then the fixation probability of a natural mutant is 1 / N, if it is neither favoured nor opposed by natural selection. If the mutation is advantageous, the fixation probability will be greater than 1 / N. However, if the mutant is deleterious, the fixation probability will be less than 1 / N. In a genetically homogeneous well-mixed population of size N, the fixation probability of a certain mutant with relative fitness r can be calculated using the moran process [54]. It is expressed as,

$$\begin{aligned} p^*=\frac{1-\frac{1}{r}}{1-\frac{1}{r^N}} \end{aligned}$$

(7)

There are a number of ways to follow the Moran process. Based on reproduction and updating strategy, these are termed as imitation updating, death–birth updating, birth–death updating. In imitation updating, an individual will imitate the strategy of its fittest neighbour. Death–birth updating occurs, when after the death of an individual, the vacant position in the population is occupied by one of its neighbours—in proportion to their fitness. However, in birth-death updating, the progeny of an individual replaces one of its weaker neighbours.

It was reported that in regularly structured populations [19], the fixation probability of a cooperator mutant in a defector population could be higher than 1 / N. This could happen when the ratio of benefit, b, to cost, c, of an altruistic act is higher than the average number of neighbours, k, i.e. $b/c >k$. However, this simple rule is not always obeyed in more heterogeneous structures like scale-free graphs. From a qualitative point of view, it is clear that if cooperation has to emerge in a low benefit regime, the number of neighbours should decrease. This condition resembles Hamilton’s kin selection rule, $b/c > 1/{\mathcal {R}}$, where ${\mathcal {R}}$ is the genetic relatedness as specified by Hamilton [6]. We could draw an analogy between these two relations. If we consider a high genetic relatedness, then there would be a small number of beneficial neighbours around an individual in a structured population.

Apart from calculating the fixation probability of a single mutant, we can also calculate the probability of strategy upgradation of a single player at a particular time point in an interacting population of two species having different strategies subject to structural restrictions. In regular structures, where all interacting individuals have the same degree, the upgradation probability [57] is expressed as:

$$\begin{aligned} W_{ij}=\frac{1}{1+\exp \left[ -\frac{(\pi _j-\pi _i)}{K}\right] } \end{aligned}$$

(8)

Here, $W_{ij}$ is the probability of imitation of the strategy of the jth individual by the ith individual. If $\pi _j > \pi _i$, then the change of strategy of the ith individual would occur. Here, K is the amplitude of noise due to an irrational choice and 1 / K is the intensity of selection. When $K \rightarrow 0$, the ith individual will change its strategy to that of the jth due to the high intensity of selection. This is basically the “strong selection” process. When $K\rightarrow \infty$ or $1/K \rightarrow 0$, the intensity of selection is very weak and can be compared with “neutral evolutionary drift”. The difference of payoffs then becomes nearly inconsequential in the change of strategies.

In more heterogeneous structures like scale-free graphs, the aforementioned noise varies hugely between individuals due to the heterogeneity of connections. Under this condition, the updating expression [18] becomes,

$$\begin{aligned} W_{ij}=\frac{\pi _j-\pi _i}{{\max (k_i, k_j)\,\varDelta }} \end{aligned}$$

(9)

In Eq. 9, $\varDelta = (T-S)$ for PD, while, for SG, $\varDelta = (T-P)$. $k_i$ and $k_j$ are the degree of the interacting individuals i and j, respectively. Somewhat different from the inclusion of intensity of selection at the time of upgradation, some authors introduce it at the time of mapping the payoff to fitness [19]. According to them, the fitness of individual players accumulated from the game is a linear function of its payoff. If $\pi _i$ is the accumulated payoff of the ith individual, then its fitness is $(1-\omega +\omega \pi _i)$, where $(1-\omega )$ is the baseline fitness of every individual and $\omega$ is the intensity of selection.

7 Cooperation with heterogeneous connectivity

The regularity in the structure of the underlying interaction network affects the outcome of the game. In Sect. 6, we noted the specific conditions for the emergence of cooperation. However, in structures with more heterogeneous connectivity such as scale-free networks, the outcome of the game differs from that of those played on regular structures. It was observed that scale-free topology has some tendency to promote cooperation throughout a broad range of game parameters like temptation in the case of PD or the cost to benefit ratio for SG [18].

Upon an increase in the average number of neighbours, the relative fraction of cooperators decreases [58]. These results seem to be somewhat different from those of Ref. [18] where the cooperator fraction increases with increase in average degree of the scale-free network. At higher degree, there seems to be an emergence of mean field effects due to which the population tends to approach a well-mixed condition. In this scenario, as cooperators are forced to interact with many defectors, their fitness eventually decreases leading to a decrease in cooperator fraction. It has also been observed that the mean clustering coefficient of the network affects the overall cooperator fraction. Scale-free networks with high clustering coefficient helps to increase cooperator fraction than on similar networks with low clustering coefficient and low average degree [58, 59].

To study the effect of graph topology on cooperation, we carried out simulations of Prisoner’s Dilemma (PD) game using the algorithm reported in Ref. [18]. Each network consists of $N=1024$ nodes. With equal probability, half the nodes are randomly chosen as cooperators and the other half as defectors. For each round of the game, t, payoffs of all individuals are determined according to the current strategy of their neighbours. Temptation, or the advantage of defection over cooperation, is represented by b, which is the main game parameter. As discussed in Sect. 2, values of $T=b > 1$, $R=1$ and $P=S=0$ are chosen. After the determination of payoffs in each generation, the strategy of each individual is updated synchronously. For strategy upgradation of an individual, i, one of its random neighbours, j, is selected and their respective payoffs $\pi _i$ and $\pi _j$ compared. Individual i will upgrade its strategy whenever $\pi _j > \pi _i$ with a probability described in Eq. 9, where, $\varDelta = (T-S)$ while $k_i$ and $k_j$ denote the respective degree of i and j. The final number of cooperators are tracked over 1000 generations after a transient time of 10000 generations. The process is repeated for 100 network ensembles at every value of T. The results are plotted in Fig. 3.

The above procedure can also be used to study snowdrift (SD) games, setting $\varDelta = (T-P)$ instead of the choice of $\varDelta = (T-S)$ as used in PD. In the setup of SD, we need to consider $T = b$, where, $b>1$, $R = (b - 1/2)$ and $S=(b-1)$. $P=0$ as in Prisoner’s Dilemma. In SD, we use r, which is the ratio of cost, c to benefit r for mutual cooperation, where, $c = T-R$.

Fig. 3

Figure shows results of simulations on various networks for population size $N = 1024$ for Prisoner’s Dilemma game. Scale-free networks tend to promote cooperation. Inset: notably, cooperator fraction decreases with increase in average degree, k, in scale-free networks

It was observed that the distribution of defectors among high-degree nodes decreases with time. But this effect reduces when the power law degree distribution is replaced by an exponential degree distribution. This inherent tendency of cooperators to occupy hubs could possibly be explained from a closer look at the situation. When a defector is on a hub and surrounded by many cooperator neighbours, it could accumulate payoff from all cooperators and its relative fitness would increase. In this scenario, the defector could exploit any of its cooperator neighbours easily. But this would ultimately lead to an overall decrease in the fitness of hubs as the defectors on hubs would tend to not provide benefits to any of their neighbours. This non-cooperative nature of the defectors restricts them to form clusters in the network. In contrast, when a cooperator occupies a hub, it would tend to increase its own fitness as well as the fitness of all its neighbours. In this scenario, it would be difficult for a defector to replace the cooperator in the hub positions. Then, interconnections between the hubs would ultimately increase the cooperator fraction of the whole population [60].

From the above discussion, it might well seem that networks with heterogeneity are more amenable to the spread of cooperation. However, it should be cautioned that this conclusion should be tempered and largely depends on the interactions at the individual level [22]. In fact, the cooperative advantage of heterogeneous graphs might well be totally lost if instead of accumulating payoffs obtained through game interactions, we were to average them. However, this same difference of procedure does not alter the outcome on homogeneous structures. Again, the rate of game interactions is crucial. Heterogeneous graphs support more cooperation than homogeneous graphs at lower rates. However, at higher rates, it becomes hard to pinpoint the role of heterogeneity in supporting cooperation. Finally, a mutant’s fixation probability is affected by heterogeneity which causes a bias where mutations occur in the population [22].

8 Robustness of cooperation

Emergence and sustenance of cooperation on heterogeneous topologies like scale-free networks does not provide a complete understanding of the evolution of cooperation under diverse real-life conditions. Various kinds of fluctuations are present in a population. In an earlier section, we discussed about the effects of dynamical links in a structured population. Just like alteration of connections, the size of the population is also quite likely to change. Individuals would die due to natural causes, specific ecological interactions and other reasons. Some studies [61, 62] concentrate on the robustness of cooperation in scale-free networks [63]. It has been observed that cooperation can be sustained in PD games on scale-free networks, even after random deletion of a significant number of nodes, which is used to model death. But targeted deletions of hubs in the same setup result in a significant decrease in the cooperator fraction. This indicates that the degree of a node influences its vulnerability. The probability of a node to be removed during an ecological stress is proposed as,

$$\begin{aligned} P(k_i)= \frac{k_i^\alpha }{\sum _{i=1}^{N} k_i^\alpha } \end{aligned}$$

(10)

Here $k_i$ is the degree of $\hbox {i}$th node and $\alpha$ tries to account for the vulnerability in the network. At $\alpha < 0$, lower-degree nodes are more vulnerable, and, $\alpha > 0$, higher-degree nodes are more vulnerable. Thus, $\alpha$ lends clues into the level of cooperation in scale-free networks [61].

9 Participation cost

It has been discussed above how heterogeneous connectivity might promote cooperation under some conditions [18, 22, 64]. However, interaction costs may alter the scenario substantially. Obviously, cooperators having a larger number of interactions bear more costs than cooperators having fewer number of interactions. Sometime back, participation cost was introduced as the temperature of the players [65]. Players having more interactions are considered as “hot” players, whereas players having fewer interactions are considered to be “cold” players. Thus, hotter players are more likely to participate in the game more often than colder players—in a given generation prior to strategy upgradation. Denoting the participation cost for each interaction as x, the payoff matrix becomes,

$$\begin{aligned} \begin{array}{ l c r } &{} C &{} D \\ C &{} (R-x) &{} (S-x) \\ D &{} (T-x) &{} (P-x) \\ \end{array} \end{aligned}$$

This alteration of payoff matrix affects the outcome of the game. It is observed that for various values of the participation cost, overall cooperator fraction is also altered. An inexpensive participation cost hardly affects the overall cooperator fraction. But above a critical level, cold players with any strategy always exploit the hot players. As seen earlier, there is a tendency of cooperators to occupy the hubs. Thus, for higher participation costs, the cooperator fraction decreases [65].

10 Dynamical links

Up until now we have discussed about structures, where the population size as well as links between individuals are static. But in reality, the structure of the population could well evolve with time. Later, we will discuss the effects of population size in terms of birth and death of individuals. In this section, we will concentrate on the dynamical linking patterns among a given number of individuals. In a structured population, as a rule of coevolution, individuals may form new beneficial edges by deleting less beneficial ones. The rule for adaptation of these new links could be strategy independent [66, 67] or could depend on strategy and performance [68, 69]. There are also some works, where adaptation of new links depends on the attractiveness of performers [70] or satisfaction [71]. Additionally, the environment where a game is staged could also be factored in. There are various types of environmental fluctuations due to which ecological interaction patterns are significantly influenced. But many changes due to the environment are random and can cause fluctuations in the interaction structure. It has been observed that significant random fluctuations in a structured population would lead to mean field effects in the overall population, thereby causing it to behave as a well-mixed one [72]. This effect is more pronounced in homogeneous networks but can also be witnessed to a lower degree in heterogeneous topologies like scale-free networks.

11 Teaching ability and ageing of players

We have seen instances of how heterogeneous connectivity might promote cooperation in a given population, under certain conditions [22]. In such scenarios, the idea of an individual’s teaching ability has also been introduced [73]. Obviously, no two individuals within a population are identical and some individuals can possess greater influence to change the strategy of others. Therefore, these influential individuals are better placed to change an opponent’s strategy. As seen earlier, in imitation upgrading—the probability of replacement of the strategy of the ith individual by the strategy of the jth individual is given by Eq. 8. A factor, $w_{ij}$, is now introduced, which intends to account for the strength of influence in Eq. 8. Consequently, Eq. 8 becomes,

$$\begin{aligned} W_{ij}=\frac{w_{ij}}{1+\exp \left[ -\frac{(\pi _j-\pi _i)}{K}\right] } \end{aligned}$$

(11)

In Eq. 11, $w_{ij}=1$ if the interacting players belong to the same group, and, $w_{ij}=w$ if the interacting players belongs to a different group. Here, the value of $w, 0<w<1$, characterises the strength of reduced teaching activity when two different groups of players are interacting.

Players having higher reproductive fitness or influence serve a role similar to that of hubs in scale-free networks [66]. Later, this teaching ability of players was considered to be strategy dependent, i.e. it is different for cooperators and defectors [74]. It was observed that these rules promote cooperation in various types of games on $T-S$ plane [74]. Another influential factor which affects the game dynamics is the ageing of players. Considering a limited interaction time or finite life span of players is obviously more realistic than an infinite lifespan for players. Studies have noted that ageing might play a role in the outcome of evolutionary games [75], but the choosiness of a player has also been emphasised. Later it was observed that age- and memory-dependent change in game rules could result in grouping within populations. As this knowledge is associated with age, it also affects the aforementioned teaching ability of players [76].

12 Growing population and reproduction rate

The aspect of evolutionary games in growing and evolving populations has drawn comparatively lesser attention vis-a-vis evolutionary games in constant populations. A recent study proposed an alternative model for the attachment of new offspring to existing ancestors with a probability [77]. This probability is analogous to the probability of preferential attachment in scale-free networks, but is driven by the payoff of the ancestors instead of their connectivity. At each time step an individual, i, plays with all its neighbours and obtains an accumulated payoff $\pi _i$. N is the total number of existing nodes, $\beta$ the intensity of selection, and $P_i$ the probability of attachment with the ith individual.

$$\begin{aligned} P_i=\frac{e^{\beta \pi _i}}{\sum _{j=1}^{N}e^{\beta \pi _j}} \end{aligned}$$

(12)

However, this scenario is different from the method mentioned in Sect. 10, where individuals change neighbours due to dynamic linking. Here, reproduction rate also has a good influence on the maintenance of cooperation. It has been observed that in a single round of the game, if the number of new individuals increases, the system goes far from steady state and cooperation is increased. This indicates the interdependence between network growth and evolutionary dynamics. In another work [20], the fitness function possessed contribution from two parts: individual fitness and global fitness. Global fitness is related to overall population growth. On the other hand, individual fitness is related to competition between individuals. This approach is actually a combination of population dynamics (where global fitness of the population is considered) and evolutionary game theory (where individual fitness fuels competition). In this model, the initial fluctuation of cooperator fraction is amplified exponentially, which leads to a transient but robust increase in overall cooperation.

13 Influence of structure in experimental conditions

Spatio-temporal interactions between microbial strains in laboratory environments provide us a firm ground to test the consequences of spatial constraints in living systems around us. Such restrictions in the microbial world are inherent in nature. A classic example of spatially distributed microbial communities is witnessed in biofilms [78, 79]. In biofilms, various types of bacteria, fungi or algae are spatially distributed to form well-structured communities, where inter-community interaction and communication can be observed [80]. Intra- and inter-species interaction by quorum sensing and other communication processes result in creation of a well-maintained and stable microbial ecosystem. These ecosystems are robust against external fluctuations. Inside a biofilm structure, cooperation within microbial communities can be observed, where secondary metabolites produced by one kind of cells help others for efficient survival [81].

Again, some strains of E. coli having col plasmid can produce a toxin called colicin, which are potentially toxic for a number of other strains of E. coli. Due to production of such toxins, inter-strain interaction and population dynamics is greatly affected [82, 83]. Interactions between colicin-producing E. coli strains have been experimentally studied. In petri dishes, these interactions produce spatio-temporal patterns [84, 85]. Three kinds of strains, namely (1) colicin-producing, C, (2) colicin-resistant, R, and (3) colicin-sensitive, S, strains were studied. Colicin-producing strains, C, can kill colicin-sensitive strains, S by producing colicin which basically acts as a toxic for S. However, C can be exploited by the colicin-resistant strains, R, due to the higher growth rate of R. On the other hand, colicin-resistant strains, R, can break down colicin molecules from the surroundings upon expenditure of a certain metabolic cost. However, it is exploited by S strains, due to a comparatively slower growth rate. Overall, all strains exhibit a cyclic competition like rock-paper-scissor game, which is represented in Fig. 4. In this game, rock crushes scissor, scissor cuts paper, and paper wraps rock. We discuss this cyclic dominance in the next section. This cyclic dominance can be observed in a petri dish containing agar media in the laboratory. The interacting cells produce boundaries of different domains indicating particular strains. Due to interaction dynamics, the domains invade each others and produce dynamic patterns.

Fig. 4

Cyclic competition in interacting bacterial strains is similar to the rock-paper-scissor game

Spatial influence is also observed in some RNA phages. Bacteriophages are viruses which can multiply only with in their host bacterium as they lack their own replication machinery [86, 87]. While these phages are strongly associated with specific hosts, occasionally two or more closely related phages could share a specific type of host cell. When more than one type of phage tries to grow within a single host cell, they realise spatial restrictions within the cellular boundary. The effects of fitness difference of two distinct phages have been compared [88], when (a) they co-infect a single host or (b) individually infect different hosts. Phages that produce a good amount of phage building blocks using the host machinery are considered as cooperators, while the remaining phages that take far greater advantage of the host machinery, are considered as defectors. Naturally the fitness of defectors is much higher in host cells having more cooperators than in host cells having more defectors. Their fitness and payoff difference resembles the payoff matrix of evolutionary Prisoner’s Dilemma [89].

14 Cyclic dominance

Another challenge of evolutionary game theory is to uncover the causes of maintenance of biodiversity in nature [90]. Coexisting species in diverse habitats interact through exchange of mass and energy resulting in crucial mutual inter-species dependence. Indeed, the extinction of one species may lead to extinction of another. In predator–prey interaction, the decrease in prey frequency leads to a decrease in predator frequency due to scarcity of food. Again, the decrease in predator frequency initially leads to an increase in prey frequency, but subsequently also subjects the prey community to face nutrient limitation. Therefore, in a two-species predator–prey model, a steady state is reached at which both of them coexist. Inclusion of more species in predator–prey model leads to a cyclic dominance between species [91]. Biodiversity not only tries to describe interactions between distinctly related species but also attempts to explain interactions between closely related species caused by mutation in their genome. These mutations can cause new speciation in fluctuating environments [92].

Cyclic dominance between species is a key notion which lends insight into the establishment and sustenance of biodiversity [90, 93]. This scenario can be modelled in the framework of the well-known rock-paper-scissor game. The Californian lizard Uta stansburiana is a reported example which shows such behaviour at the time of reproduction [94,95,96]. This type of behaviour has also been observed in microbes. Some strains of E. coli exhibit this type of interaction which is schematically described in Fig. 4 [84, 85].

In the well-mixed regime, these systems have been modelled extensively using the Lotka–Volterra equation [97,98,99]. Although models in well-mixed regime lend important clues regarding the behaviour of the system, it becomes essential to model such systems incorporating structural restrictions. The experiments discussed in the previous section show that spatial limitations are an essential condition and cannot be ignored, if we aim to get a realistic view of the system. Furthermore, the mean extinction time of species is proportional to the logarithm of the population size in well-mixed regime. But when structure is incorporated, the mean extinction time becomes exponentially proportional to the population size. This, thus implies a long coexistence time for the interacting species [100]. Inclusion of stochasticity between individuals in terms of mobility, asynchronicity in death–birth process and external environmental fluctuations leads the system further from a deterministic extinction point while being attended by an increase in the mean extinction time.

Interested readers can find an exhaustive account of cyclic dominance in evolutionary games in Ref. [101].

15 Games on multilayer networks

Now let us move beyond “simple” networks to “network of networks”, which are often used interchangeably with “multilayer networks”. Three broad categories of such networks are mathematically defined below, namely (a) multiplex networks, an example of which is depicted in Fig. 5, (b) interconnected networks and (c) interdependent networks. Such networks consist of L networks or layers, where $L \ge 2$ networks (or layers). Networks are usually denoted as $G=(V, E)$, where V is the set of nodes and $E \subseteq V \times V$, is the set of edges which connects the set of nodes, V. Generalising our notation to L number of interconnected networks (or layers), we can write $G_L =(V_L, E_L)$. For weighted graphs, this can be further generalised to $G_L =(V_L, E_L, W_L)$, where $W_L$ obviously denotes the set of edge weights. Further, directionality might also become relevant, depending on the problem in question. Let $N_\gamma$ be the number of nodes in network layer, $\gamma$. The combination of nodes of all network layers provides the set of $V_L = \cup _{\gamma =1}^L V_{\gamma }$, where $V_{\gamma } =\{{V_1}^\gamma , . . ., {V_N}{^\gamma } \}$ Here, it should be emphasised that the number of nodes $N_{\gamma }$may not be identical and vary from layer to layer. Indeed, a node in layer, $\gamma$, might have multiple, one or even no partner in layer $\delta$, where obviously, $\gamma , \delta \in \{1, 2, . . ., L\}$ and $\gamma \ne \delta$. The set of connections, $E_L$, mentioned above, can be written further as $E_L = \{ E_{\gamma } \cup E_{\gamma \delta }\}$. Here, $E_{\gamma } \subseteq V_{\gamma } \times V_{\gamma }$ and $E_{\delta } \subseteq V_{\delta } \times V_{\delta }$ denote the set of intra-layer connections in the network layer $\gamma$ and $\delta$, respectively. $E_{\gamma \delta } \subseteq V_{\gamma } \times V_{\delta }$ is the set of inter-layer connections. In the intra-layer adjacency matrix of a graph, $A^{\gamma }$, an existent edge between the ith node and jth node in network layer $\gamma$ can be denoted as $a_{ij}^{\gamma }=1; i,j \in (1, . . . , N_{\gamma }), i\ne j$. The absence of the edge naturally means $a_{ij}^{\gamma }=0$. For the adjacency matrix of inter-layer connections, $A^{\gamma \delta }$, an existent connection from the ith node in layer $\gamma$ to the jth node in layer $\delta$ can be denoted as ${a^{\gamma \delta }_{ij}} = 1, i\in (1, . . . , N_{\gamma }), j \in (1, . . . , N_{\delta })$. Similarly, the absence of this inter-layer connection would mean ${a^{\gamma \delta }_{ij}} = 0$. We can now distinguish between the different subclasses of “multilayer networks” or “network of networks”:

• In multiplex networks, each network (layer) has a fraction of overlapping nodes or even the same set of nodes but the links among them are different. Thus, $V_{\gamma } \cap V_{\delta } = V_L = V, \forall \gamma \ne \delta$.

• In interconnected networks, nodes in different networks (layers) are physically connected and every network generally has different types of nodes. Thus, $V_{\gamma } \cap V_{\delta } = \emptyset , \forall \gamma \ne \delta$.

• In interdependent networks, every network (layer) generally possesses different types of nodes, and there exist links of dependence but not actual physical connections between nodes in different layers. Thus, $V_{\gamma } \cap V_{\delta } = \emptyset , \forall \gamma \ne \delta$.

Fig. 5

Representation of a multiplex network. Of late, games are being widely studied on such networks

Some studies on the problem of Prisoners Dilemma in multilayer networks have been conducted recently. However, there are lots of open problems regarding various aspects of rock-paper-scissors game, ultimatum game, collective-risk social dilemma game, naming game etc., which are yet to be explored in this area. An extensive review on evolutionary games on multilayer networks is available in Ref. [102].

16 Discussion

Network science has witnessed a significant surge of activity in the last two decades. This has propelled research on trying to realistically explain the emergence and sustenance of cooperation by studying evolutionary games on irregular structures. Mathematical simplifications such as denoting well-mixed populations by complete graphs might lead to elegant closed form solutions. However, in reality an individual may not be interacting with all its neighbours simultaneously, even at any given instant. The present report tries to present an account of such possible interactions which have been studied in literature.

A central assumption in evolutionary games is that every individual in a genetically homogeneous population is considered to be genetically predetermined to play a single strategy, which is encoded in the organism’s genome. One can also encounter genetically heterogeneous populations containing different mutant strains of the same species. Such situations might be handled better by using mixed strategy dynamics, which are just beginning to be explored [28,29,30]. It may be especially noted that incorporation of rationality in a player’s decision-making ability alters the game outcome significantly [32].

Furthermore, we need to mention here that the intellectual decision-making capacity of players has a significant influence on the game outcome. Here in this review, we are only considering irrational individuals guided by their genetic makeup. If we focus on cooperation between humans in society, rationality plays an important role [32]. In such cases, imposition of spatial restriction opposes the emergence of cooperation even in Prisoner’s Dilemma [103, 104]. Moreover, the conditional cooperation of rational individuals plays a critical role in the game outcome, where a player wants to cooperate—only when others are cooperating in its neighbourhood [105].

In evolutionary games, cooperation is thought to be enhanced in heterogeneous structures [18], but only under certain conditions [22]. Such theoretical approaches based on game dynamics under structural limitations to describe evolutionary process are somewhat successful in explaining the emergence of cooperative behaviour. In mixed populations, cooperators are usually exploited by defectors. However, some studies show that environmental fluctuations [21] and limited resources [106] can promote cooperation. Thus, quite some ground remains yet to be covered.

Attempts have also been made to describe the conflict between gradualistic evolution and punctuated equilibrium [107] on speciation in terms of evolutionary game dynamics where fixation of a specific mutant in a population has been modelled satisfactorily.

Evolutionary games have traditionally been used to study evolution. However, there are now gradually being used in other contexts, especially in computer science. For example, evolutionary game dynamics with migration has been explored for hybrid power control in wireless communications [108]. Other connections between algorithms, games and evolution are also being explored [109]. This review aims to deliver a pedestrian account of evolutionary games on heterogenous structures. More detailed and formal discussions regarding such games can be found in exhaustive accounts like Ref. [110].

We would like to thank the anonymous referees for their critical comments. It is a pleasure to acknowledge numerous useful discussions with Vishwesha Guttal of Indian Institute of Science, Bengaluru. SS and SG thank Bose Institute, Kolkata, and CSIR, India, respectively, for financial support.