Identifying the conditions that support cooperation in spatial evolutionary game theory has been the focus of a large body of work. In this paper, the classical Prisoner's Dilemma is adopted as an interaction model; agents are placed on graphs and their interactions are constrained by a graph topology. A simple strategy update mechanism is used where agents copy the best performing strategy of their neighbourhood (including themselves). In this paper, we begin with a fully cooperative population and explore the robustness of the population to the introduction of defectors. We introduce a graph structure that has the property that the initial fully cooperative population is robust to any one perturbation (a change of any cooperator to a defector). We present a proof of this property and specify the necessary constraints on the graph. Furthermore, given the standard game payoffs, we calculate the smallest graph which possesses this property. We present an approach for increasing the size of the graph and we show empirically that this extended graph is robust to an increasing percentage of perturbations. We define a new class of graphs for the purpose of future work.

1. Introduction

Understanding the emergence and robustness of cooperation in environments where agents or individuals are tempted to behave in a non-cooperative manner has been the focus of many studies. The Prisoner's Dilemma is a frequently adopted game to help explore these questions.

In this game, an agent can either cooperate (C) or defect (D), obtaining a payoff that depends on both agents’ choices [1]. The payoffs are as follows: T (temptation to defect, i.e. the payoff for defection when the other player cooperates), R (reward for mutual cooperation), P (punishment for mutual defection) and S (the sucker's payoff for cooperation when their opponent defects). The constraint that T > R > P > S holds, the payoffs can be seen in the payoff matrix in figure 1. Many variants of the Prisoner's Dilemma have been explored including N-player variants [2,3], games with optionality [4,5] and games with non-discrete payoffs allowing partial cooperation and partial defection [6,7].

Spatial game theory involves constraining interactions between agents by adopting some topology which governs which agents can interact together [8]. Agents are placed on nodes in the graph and an edge connecting two nodes indicates that the agents on these nodes can interact with each other [9].

Research over the past years has shown that different topologies governing agent interactions such as lattices [10], scale-free graphs [11–13], small-world graphs [14,15], graphs exhibiting community structure [16] and bipartite graphs [17,18] have a considerable impact on the emergence of cooperation. In much of the research, agents are randomly assigned a strategy and the focus of the research is to explore whether cooperation or defection emerges. An alternative methodology that has gained considerable attention is to seed the population with cooperators and then introduce a defector (or defectors) and analyse the effect on the population. This approach was explored in the seminal paper by Nowak & May [19]. This has parallels with research in the domain of percolation theory [20].

Our game uses synchronous updates, all the players calculate their payoffs and potentially update their strategy at the same time. A player's payoff is calculated as the sum of all payoffs obtained by the player when interacting with their neighbours in the current turn. Players update their strategy by copying the strategy of their best-performing neighbour. This approach is one of several approaches that have been adopted in the literature; others include copying a better performing strategy with a probability proportional to their score and the Fermi–Dirac strategy update approach [21]. Before the start of a simulation we seed the population by setting all the nodes to cooperators, then turning a percentage of them to defectors at random.

The simulation is done using the algorithm specified in Algorithm 1:

In our simulations, we set ‘max time-step’ to be 1000; however, it was never reached as every simulation converged before then. The simulator can be found on GitHub [22].

Our work has a strong relation to the notion of evolutionary amplifiers and suppressors [23]; given an increased payoff due to an advantageous mutation in one of the players in a population the fixation probability of the mutant (the probability that the mutation will spread to the whole population) can be increased in some graphs called amplifiers and decreased in other graphs called suppressors.

There has been extensive work undertaken investigating the effect of topology on the spread of behaviours in spatially organized populations. Early work focused on lattices with more complex graph exhibiting a much wider range of features. The topology described in this paper has some key similarities with existing work—the presence of star-like graphs which have been investigated on their own and which are also a component of comet graph structures [24].

The effect of the topology on the outcome is dependent on the interaction model; much of the recent work adopts an abstract interaction model where mutants who outperform the initial population are considered. In our work, we consider a more complex interaction model (the Prisoner's Dilemma) where the payoff received by an agent is dependent on its neighbours. The increased complexity of this interactions model requires a more complex topology to help maintain robust cooperation.

Subgraphs of our topology, critical node subgraphs, have similar functionality to that of ‘self reinforcing’ structures [25]; they both stop other strategies/conventions from outside the subgraph to spread into the subgraph, but our subgraph differs in the sense that they are also responsible for spreading the cooperation to nodes outside the subgraph, nodes which in their turn spread cooperation further due to the subgraph they belong to; we present proof of this property. Another key feature of the topology presented in this work is that the robustness to perturbations (the introduction of defectors) increases as the graph size increases. While the graph topology shares some ideas with existing approaches, one of the novel aspects of this topology is that it operates with the Prisoner's Dilemma as the interaction model.

The main contributions of this work are: firstly, the introduction of a graph topology that ensures a cooperative population is robust to any one perturbation, and secondly, a means to increase the size of the graph such that it is robust to all single node perturbations and depending on the size of the graph, robust to many node perturbations. We show that the graph can be increased in size indefinitely rendering it more robust as it is extended. We compare the robustness on our graph topology with that of the star graph.

The paper outline is as follows: in §2, we present the graph topology and a sketch for the proof, with the full proof, and associated derived constraints included in appendix A. There are further discussions in appendices B, C and D. In §3, a description of a method to extend the graph while maintaining its functionality is presented. In §4, we empirically test the robustness in graphs of increasing size and show that robustness improves as the graph extends. In §5, we identify by empirical means the payoff vales for which our graph can exist. In §5, we also define a type of graph named ‘Resilient Graphs’ (with our graph belonging to this type), compare them to evolutionary suppressors, and show a resilient graph for defectors; we then discuss the effects of several other update mechanisms on our topology, the star graph and the complete graph, followed by how our topology might be useful for finding resilient graphs in the optional Prisoner's Dilemma interaction model, how sufficiently large random, scale-free or real-world graphs might be modified to contain our topology; we discuss robustness in our topology and other graphs, and we look at the effects on our topology of a more targeted initial perturbation. Finally, in §6, we present conclusions and outline some future research directions.

2. Graph topology

The graph topology presented herein possesses some interesting properties. The general topology has some properties present in many real-world graphs, i.e. the existence of hubs and the existence of many nodes with low degree. The graph is useful for guaranteeing robustness to any single node perturbation (i.e. a cooperator changing to a defector). The basic topology is depicted in figure 2.

With reference to the graph depicted in figure 2, we can identify four different classes of nodes (colour coded in the diagram):

—	The a , a′ and b nodes are minor nodes that have a degree of one. The number of a nodes, a′ nodes and b nodes present is important in determining if the graph is robust to perturbations; their numbers need to satisfy certain requirements to ensure the graph supports a population's robustness to any one perturbation. The graph does not need to be symmetric, the number of a nodes can be different to the number of a′ nodes.
—	The A and A′ nodes are referred to as critical nodes. If, at any stage, a critical node and all its minor nodes are cooperators, then cooperation will spread to all the graph.
—	The two critical nodes are connected via the B node. The constraints on this node guarantee that if it defects, it cannot cause defection to spread to the critical nodes. Moreover, when the B node and its minor nodes cooperate, the B node can cause a critical node that has defected (and all its minor nodes) to cooperate again.
—	The z and z′ nodes are pivotal in allowing cooperation to spread between two large nodes (those nodes with high degree i.e. A, A’ and B) and their minor nodes; we refer to them as enabler nodes.

Given the local topology of these different classes of nodes, these nodes behave differently when a node is perturbed. For each class of node identified, the graph will revert to full cooperation. We quickly enumerate these cases below and include a full proof in appendix A.

—

If one of the critical nodes (A or A′) defects, as seen in figure 3:

Time-step 1: All the minor nodes and the enabler node connected to the initial defector will defect. If the payoff of the other critical node is lower than the initial defector, node B will defect and we continue to Time-step 2 otherwise we jump to Time-step 4.
Time-step 2: The minor b nodes will defect; the other critical node will ensure the B node cooperates again.
Time-step 3: The minor b nodes will cooperate due to the presence of the B node.
Time-step 4: The initial defector and the enabler node connected to it will cooperate due to the presence of the cooperative B node.
Time-step 5: All the minor a or a′ nodes will cooperate again given their connection to the initial defector.

— If the B node defects:

Time-step 1: All the minor b nodes will defect due to the presence of the B node; the B node will cooperate due to the presence of the critical nodes.
Time-step 2: All the minor b nodes will cooperate due to the presence of the cooperative B node.

— If one of the a, a′, b, z or z′ nodes defects, it will revert to cooperation in the following time-step due to their connection to a cooperative large node.

Figure 3. Simulation steps when node A defects. (a) Initial perturbation, (b) time-step 1, (c) time-step 2, (d) time-step 3, (e) time-step 4, (f) time-step 5.

A thorough proof with illustrations is presented in appendix A together with a specification of all the constraints needed on the graph topology. In appendix B, we present additional requirements which are needed to allow a critical node to continue to cooperate if it, and all of its minor nodes, cooperate. The constraints on the graph topology are further examined in appendix C. In appendix D, we show that the smallest such graph structure adopting the classical Prisoner's Dilemma payoffs, (T = 5, R = 3, P = 1 and S = 0), has |a| = |a′| = 16 and |b| = 6.

Below are the list of requirements obtained in appendices A and B:

(1) 2T < R(a + 1) + S
(2) 2T < R(a′+1)+S
(3) 2T < R(b + 3) + S
(4) T(b + 4) < R(a + 1) + S
(5) T(b + 4) < R(a′+1)+S
(6) S × b + 4R > T
(7) R(a′ + 1)+S>P(a + 2)
(8) R(a + 1) + S > P(a′+2)
(9) S(b + 2) + 2R > T
(10) P(a + 1) + T < R(a′+2)
(11) P(a′+1)+T < R(a+2)
(12) P(a + 1) + T < R(b + 2) + 2S
(13) P(a′ + 1) + T < R(b + 2)+2S
(14) T < S × a + 2R
(15) T < S × a′+2R
(16) T + P < R × a + 2S
(17) T + P < R × a′+2S
(18) T(b + 3) + P < R × a + 2S
(19) T(b + 3) + P < R × a′+2S.

3. Extending the graph

We can extend the graph by adding additional nodes and edges to the graph and can possibly modify a graph by removing existing ones. We may wish to consider certain properties of the graph when we decide upon a mechanism to extend the graph.

One relatively straightforward mechanism to extend the graph is by creating additional critical nodes (A) and large nodes (B) and connecting them together in a ‘line’ topology as depicted in figure 4. Note that the minor nodes and the enabler nodes are omitted from the figure as the overall ‘shape’ of the graph is determined by the large nodes. With this ‘line’ topology we can increase the size of the graph indefinitely and we adopt this approach in the next section to show the effects of extending the graph on the robustness of the graph. Given the basic graph structure, the graph is guaranteed to be robust up to any n − 1 perturbations where n is the number of critical nodes present in the graph.

Given the definition of our graph, the number and ratios of minor nodes can be varied while maintaining the core functionality of the graph; we have identified a series of additional methods we can use to grow or extend our graph while maintaining the core functionality. These include:

1.	We can add additional enabler nodes: this may alter the degree distribution of our graph potentially allowing for other payoffs and could make cooperation spread faster in some cases.
2.	We can add edges between minor nodes both connected to the same large node or to different large nodes. This may alter the degree distribution of our structure. It could slow the spread of cooperation. There is a limit to which we can do this before losing the core functionality.
3.	A critical node can be connected to multiple large non-critical nodes (B) (this will need the addition of enabler nodes).
4.	A large non-critical node can be connected to other large non-critical nodes (this will need the addition of enabler nodes).
5.	A large non-critical node can be connected to multiple critical nodes (this will need the addition of enabler nodes).

Given points 3 and 5 above, if we consider a critical node subgraph to be a ‘node’ and the large non-critical node subgraph connecting two critical node subgraphs to be the ‘edge’ between two ‘nodes’, then one can create any undirected ‘graph’ mimicking some of the properties of those actual graph. Examples include fractal graphs and scale-free graphs.

The many ways to grow our topology and their effects on the graph properties and the limit to which we can maintain core functionality will be explored in future work.

4. Robustness

To demonstrate the effects of extending the graph size on the robustness of cooperation to perturbations, we look at four different graphs, all of different size but adopting the same ‘line’ topology. The details of the graph sizes are specified in table 1.

Table 1. Details of the graph sizes.
Collapse
no. of nodes	no. of critical nodes	no. of B nodes	no. of enabler nodes	no. of b nodes	no. of end a nodes	no. of middle a nodes
88	3	2	4	2 × 9	2 × 21	1 × 19
184	6	5	10	5 × 9	2 × 21	4 × 19
376	12	11	22	11 × 9	2 × 21	10 × 19
760	24	23	46	23 × 9	2 × 21	22 × 19

We test the robustness of the graph to perturbations by beginning with a fully cooperative graph and randomly perturbing some nodes (changing a cooperator to a defector). We vary the percentage of nodes to be perturbed and measure the ability of the population to recover to a fully cooperative state.

To demonstrate the effects of extending the graph on the robustness of the graph, we initially look at graphs with 88 nodes of which 3 are critical nodes, then we extend the graph three times: the first one has 184 nodes of which 6 are critical nodes, the second one has 376 nodes of which 12 are critical nodes and the last one has 760 nodes of which 24 are critical nodes. We test the robustness, using classical Prisoner's Dilemma payoffs, for all the four graphs; and as seen in figure 5, increasing the graph significantly increases the robustness of the graph. In the last graph, robustness to perturbations is very high even at 50% perturbations. For all the graphs, we use the line topology.¹

Figure 5. Robustness of graphs to perturbations.

In the figure, we also present the robustness for a star graph, a graph which has one node connected to all the other nodes and all the other nodes having a degree of 1, with 760 nodes. The star graph has an average percentage of cooperators at the end of simulation of approximately 100 − x, where x is the percentage of initial defectors. As we can see, the star graph is outperformed by our topology up to a certain perturbation threshold which increases as the size of our topology increases.

From these results, we can determine that populations become more robust to the introduction of defectors as the graph extends; in particular, the robustness increases as the number of critical nodes increases. The data can be found on GitHub [22].

5. Discussion

For the interaction model and update mechanism adopted in this work, the actual values of the payoffs in the payoff matrix are not important; what is important is the ratios of the payoffs. For example, for the two following sets of payoffs: T = 10, R = 5, P = 2, S = 1 and T = 100, R = 50, P = 20, S = 10, the simulations will behave in exactly the same way. It is not the actual values but the ratios of the payoff that are of importance for the simulations; for instance, in the example above, the ratio T/R = 2 is one of the ratios that will guide the simulation.

In order to identify for which payoff combinations our graph can exist, an empirical investigation is undertaken whereby simulations are run for a large set of payoff ratio values. We have looked at three payoff ratio variables T/R, R/P and P/S and we have explored all payoff ratio values from 1.1 to 9.9 with increments of 0.1. For each set of values, we attempt to find the smallest values for a = a′ and b, the number of minor nodes, for which we can respect all the rules listed in appendix C. We searched up to a maximum value of 20 000 (the largest minimum value of a used in a solution was a = 12 445). The simulations ended up finding a solution to our graph as long as T/R < R/P (this requirement has also been obtained in appendix C).

We have performed similar simulations for the special case of S = 0 for which we only have two payoff ratio variables T/R and R/P. Again the simulations ended up finding a solution to our graph as long as T/R < R/P, but given S = 0 the requirements for our graph also need T/R < 2. Note, we can increase the value of the ratio by adding more enabler nodes.

We introduce the following category of graphs, ‘Resilient Graphs’, a resilient graph is a graph which will support one strategy while hindering all others. Resilient graphs are a more generalized version of suppressors, which make mutants less likely to spread to the whole population. For Resilient Graphs, there is no need to know if a strategy/mutation is advantageous which allows us to look at more complex games. The graph topology presented in this paper is a resilient graph for cooperators participating in the Prisoner's Dilemma with a strategy update mechanism where the best performing player in the neighbourhood is copied.

A simple example for a resilient graph for defectors in the Prisoner's Dilemma interaction model and update mechanism involving copying the best performing player in the neighbourhood is the complete graph. Given a population of n players all of which are defectors and perturbing x (with x < n) of them to become cooperators, then the payoff for any cooperator is R(x − 1) + S(n − x − 1) + S while the payoff for any defector is T(x − 1) + P(n − x − 1) + T, the payoff of cooperators is smaller than that of defectors, making it so all cooperators will revert to being defectors.

While the fixation probability represents the chance that the mutant will spread to the whole population, our robustness measurement, the average percentage of cooperators at the end of simulation given a certain percentage of initial defectors, also takes into consideration outcomes in which the mutation only spreads to a subset of the population, with the graph reaching a stable state in which both the original population type and the mutants exist at the same time. By looking at a percentage of nodes where the strategy is perturbed/mutated we can account for the effects the size of a graph may have on the robustness scores. We can better compare graphs by looking at a variety of perturbation/mutation percentages. It is possible some graphs will perform better when there is a high amount of initial perturbations.

While the structure of a population affects the overall behaviour of that population, the actual effect of the structure is highly dependent on the interaction model and update mechanism used. We will discuss a few of the many possible interaction models and update mechanisms and their effects on our structure, the star graph and the complete graph.

In the update mechanism presented in this paper all nodes update their strategy at the same time (synchronous update). With a different update mechanism which uses asynchronous updates, where only one node updates at a time, the behaviour of the population might change. We will discuss two types of asynchronous updates:

—	When a node updates, all nodes recalculate their payoff: Our topology is still robust to any one perturbation. Eventually, defection spreads enough such that cooperation can spread back. Defection still cannot spread from node B to node A or from node a to node A or from node z to either node A or B. There may be some changes to the overall robustness of the graph, and the graph will take many more turns to stabilize (either to full cooperation or defection). The star topology and the complete graph have the same robustness, but again it will take multiple turns for the population to stabilize.
—	A node recalculates its payoff only when it updates (once initially before comparing with others and once the update finishes): Our topology is still robust to any one perturbation. As in the previous case, defection eventually spreads enough so that cooperation can spread back. As before, defection still cannot spread from node B to node A or from node a to node A or from node z to either node A or B. A defective critical node should maintain a higher payoff for longer (we have to wait for its minor nodes to defect and then it has to update); eventually cooperation will spread once the defected critical node updates to a lower payoff. Again there might be some changes on the overall robustness of the graph and the graph will take many more turns to stabilize. The star topology will obtain the same robustness. For the complete graph robustness stays the same, it is possible for cooperation to spread (for example, after initial perturbation one of cooperators is selected then it will defect, and then if all other defectors are selected one at a time then no defector will have the original payoff which when the next defector is selected may allow the cooperators, who have their original payoff, to have a higher payoff allowing cooperation to spread) but at no point can cooperation spread to more than the original number of cooperators, which means defection will eventually spread to the whole graph.

Given our current interaction model and update mechanism, the payoff of a node is highly dependent on the degree of that node. Generally, as a node's degree increases so does their payoff. It would be interesting to explore an alternative payoff mechanism where we normalize the payoff, by dividing it by the node's degree, resulting in an average interaction payoff. Given this approach, the topology presented in this paper will no longer function in the same manner. For example, if a minor node defects it will always have a payoff of T when the large node it is connected to cooperates. The maximum payoff of this large node is R, which means cooperation cannot spread to the perturbed minor node and in fact it is guaranteed to spread defection. This implies that star graphs or structures containing them are not suitable for maintaining cooperation for this particular interaction model and update mechanism. In the complete graph if we have m defectors and n cooperators the payoff of defectors is (n × T + m × P − P)/(n + m) and that of cooperators is (n × R + m × S − R)/(n + m) given T>R>P>S then the defectors will always have a higher payoff than cooperators.

In the current model, the players have perfect knowledge and behaviour. In an update mechanism that contains noise, this is no longer the case. We discuss two types of noise:

—	Noise giving the player a chance to incorrectly read the payoff obtained by a neighbouring node when it decides how to update: We can no longer guarantee that our structure is fully robust to any one perturbation (for example if B defects, both A and A’ might read its payoff as being larger than theirs, which would allow the defection to spread to them, which eventually would probably make the defection to spread to all nodes). The overall robustness of the graph would also be affected the extent of which is hard to say since the noise will help with the spread of both defection and cooperation. To reduce the effects of the noise on our structure, we could have more minor nodes and enabler nodes. The change in payoff caused by noise will need to be very high to affect the robustness of the star topology (and even higher for larger stars). In a complete graph, it will now be possible for a defector to read a cooperator's payoff as being higher, which will spread cooperation to the defector, at the same time defection will probably spread to the cooperator (and most of all the other cooperators), so on average the robustness of the complete graph should stay the same.
—	Noise giving the player a chance to incorrectly read the strategy of a node (with no change to its payoff): We can no longer guarantee that our structure is fully robust to any one perturbation. In a fully cooperating critical node subgraph, the critical node still cannot be turned to defection; the B nodes will read A nodes as defectors from time to time causing them to defect, minor nodes will turn to the opposite strategy of the critical nodes due to noise which makes the critical node weaker when it cooperates possibly allowing the B node to influence it, it also makes defector critical nodes stronger. It is hard to predict how much this noise will reduce the overall robustness of our structure, but is expected that at all times a fraction of the minor nodes will always be defective due to wrongly perceiving the strategy of their cooperating large nodes. To combat the effect of this noise, we can increase the number of a and b nodes such that the ratio a/b becomes larger making it more difficult for node B to influence node A. On a star graph, the overall robustness of the graph will still mostly depend on whether or not the central node is the initial perturbation, but the robustness will further be reduced since at all times a fraction of the one-degree nodes will defect due to the noise. On the complete graph, a fraction of the nodes will cooperate at all times due to noise, but this is reduced since the perceived cooperator will have the same payoff as the defectors so the selected strategy is randomly selected from one of the defectors or the defectors incorrectly read as cooperators, increasing the overall robustness for cooperation.

As we have discussed above, our structure will still maintain some, or all, of its functionality with some other update mechanisms. Similarly, the structure could perform the same role of promoting cooperation for some other interaction models, or it could be modified slightly or be incorporated as a subgraph of a structure that has that role. For example, we can consider a different interaction model such as the Optional Prisoner’s Dilemma in which the players have a third option, to abstain, which gives both players a payoff of L with R > L > S. In this case, our structure will still work when there are only cooperators and defectors but when we introduce abstainers, it is possible that cooperation would not spread due to the presence of abstainers (for example from a cooperating B node subgraph to an abstaining A node subgraph when L > P), it is possible that a Resilient graph for cooperation for the Optional Prisoner’s Dilemma can be derived by modifying or incorporating our structure.

When looking at sufficiently large random, scale-free or real-world graphs, we would generally find star-like subgraphs in them. Given this, it would be possible to slightly modify graphs such that our graph is present as a subgraph, which would improve the robustness of the whole graph due to the robustness of our subgraph.

One of the reasons it is hard to compare the robustness of two graphs is that this robustness is not only dependent on the interaction model and update mechanism but also on the actual payoffs used. As we have discussed, our structure only functions properly for a certain range of payoffs, whereas, for example, the robustness of a k = 4 lattice graph (a graph in which each node is placed on a grid and it is connected to its four closest neighbours with the nodes on the edges being neighbours with the nodes on the opposite edge), will vary considerably across multiple ranges of payoffs (the behaviour will be different when a defector connected to two cooperators and two defectors has either a higher payoff then a cooperator connected to three cooperators and a defector compared with the case in which it is lower). In general, for sufficiently large graphs our topology should outperform others, for the payoffs in which it functions properly, given the fact that its robustness improves as it grows while that of others should in general stay unchanged.

In our experiments, the initial perturbations are at random. If instead the perturbations were more targeted with higher degree nodes selected more often, then it will lower the robustness of our structure. The exact effects would depend on the strength/precision of targeting; for example, if half the critical nodes are guaranteed to be targeted while all other perturbations are at random, then the robustness of the graph would be very similar to that of random targeting in a graph of half the size. If critical nodes are 20 times more likely to be targeted compared with other nodes, then the robustness of the graph would be very similar to that of random targeting in a graph 20 times smaller. As discussed in the definition of critical nodes, if at any time a critical node and all its minor nodes cooperate, then cooperation will spread from it. Regarding our structure, as seen in figure 2, we showed that it is robust to any one perturbation; when considering two perturbations the graph recovers to full cooperation as long as one of the critical nodes is not perturbed (given the definition of critical nodes and the fact that node B would have a lower payoff then the defected critical nodes). To reduce the effects of more targeted initial perturbations, our structure would be constructed such that the large nodes would have the minimum number of minor nodes, reducing the chance that the large node is targeted; we can also add additional edges between minor nodes making them more likely to be targeted. This targeted perturbation will similarly reduce the robustness of the star graph, while for the complete graph it will have no effect since all nodes in it have the same degree.

6. Conclusion and future work

In this paper, we presented a topology which supports robust cooperation in spatial evolutionary game theory; the classical Prisoner's Dilemma is adopted as an interaction model; agents are placed on graphs and interact with their neighbours. A simple strategy update mechanism is used where agents adopt the best performing strategy of their neighbourhood (including themselves). We showed that the graph is robust to one perturbation (§2), calculated the smallest such graph (appendix B) using the standard payoffs, and showed empirically that the graph is more robust as we extend it (§4).

Future work will examine the ways of extending the presented graph topology and how it affects the graph properties. We will also look at finding resilient graphs for the optional Prisoner's Dilemma in which players can choose to abstain, for weighted graphs, for normalized payoff update mechanism, for other interaction models and other strategy update mechanisms. We will explore the robustness of standard graphs when using the same interaction model and update mechanism as in this paper. Furthermore, for the presented interaction model and update mechanism, we will show graphs in which the spread of cooperation and defection behaves in a manner that mimics logic gates in circuits, these graphs share many topological similarities with the graph presented in this paper. Once Resilient structures have been explored in many interaction models and update mechanisms, we can take a look at what common characteristics these structures have and see if some characteristics are only viable for a subsection of interaction models and update mechanisms.

Data accessibility

Source code for the simulator and related data in the paper is available at: https://doi.org/10.5281/zenodo.4562672.

Authors' contributions

The first author is responsible for all code, for the design of the topology, proof and writing of sections of the paper. The second author contributed to the writing of the paper, the experimental design and advice on the proof in the paper.

Competing interests

We declare we have no competing interests.

Funding

This work was supported by the National University of Ireland Galway College of Engineering and Informatics Postgraduate Research Scholarship.

Appendix A

A.1. Graph structure

Notation:

—	P_x is the payoff of a node x.
—	T, R, S and P refer to the classical payoffs in the classical Prisoner’s Dilemma, i.e. T > R > P > S; The payoffs are positive and real.

Proof.

We can consider several different cases for the single perturbation, i.e. different types of nodes can be perturbed. In other words, the agent located on that node changes from cooperation to defection:

1.	node z or z′
2.	one of the a or a′ nodes
3.	one of the b nodes
4.	node B
5.	node A or A′

Initially, all the nodes are cooperative, as depicted in figure 6 below.

For each case, the figures show how the graph will look like at the end of a time-step, after the update.

Case 1: One of the z or z′ nodes is perturbed

At time-step t₀, the initial node changes to defection (figure 7).

At time-step t₁, the payoff of A (or A′) and B is bigger than that of the defector so the initial defector, i, will copy their strategy and begin to cooperate.

At that moment, we have the following payoffs:

P_{B} = R \times b + R (due to A) + R (due to A^{'}) + R (due to z^{'}) + S (due to z) = R (b + 3) + S

P_{z} = T (due to A) + T (due to B) = 2 T

Similarly for

P_{z^{'}}

P_{A} = R \times a + R (due to B) + S (due to z) = R (a + 1) + S

Similarly for

P_{A^{'}}

This results in the following requirements:

\begin{aligned} P_{z} < P_{A}, P_{z^{'}} < P_{A^{'}} and P_{z} < P_{B} & \Leftrightarrow \\ 2 T < R (a + 1) + S \end{aligned}

A 1

2 T < R (a^{'} + 1) + S

A 2

2 T < R (b + 3) + S .

A 3

Case 2: One of the a or a′ nodes is perturbed

At time-step t₀, the initial node defects (figure 8). Let i be the initial defector.

At time-step t₁, the payoff of A or A′ is bigger than that of the defector i so the defector will copy their strategy and return to a cooperative state.

At the moment, we have the following payoffs:

\begin{aligned} P_{A} & = R (a - 1) + R (due to B) + R (due to z) + S (due to i) \\ = R (a + 1) + S \\ P_{A^{'}} & = R (a^{'} - 1) + R (due to B) + R (due to z^{'}) + S (due to i) \\ = R (a^{'} + 1) + S \\ P_{i} & = T (due to A or A^{'}) = T . \end{aligned}

This results in the following constraints on the graph:

\begin{aligned} P_{i} < P_{A} and P_{i} < P_{A^{'}} \Leftrightarrow \\ T < R (a + 1) + S; Already covered by (A 1) \\ T < R (a^{'} + 1) + S; Already covered by (A 2) . \end{aligned}

Case 3: One of the b nodes is perturbed

At time-step t₀, the initial node, i, defects as shown in figure 9.

At time-step t₁, the payoff of B is bigger than that of the initial defector so the initial defector, i, will return to cooperation by copying the strategy of node B.

At that moment, the following payoffs are rewarded:

\begin{aligned} P_{B} = R (b - 1) + R (due to A) + R (due to z) \\ + R (due to A^{'}) + R (due to z^{'}) + S (due to i) = R (b + 3) + S \end{aligned}

and

P_{i} = T (due to B) = T .

We now have the following constraints:

\begin{aligned} P_{i} < P_{B} \Leftrightarrow \\ T < R (b + 3) + S; previously covered by (A 3), so no addition to the set of constraints . \end{aligned}

Case 4: Node B is perturbed

At time-step t₀, node B defects as depicted in figure 10. Let b_i denote any one of the b nodes.

At time-step t₁, the payoff for A and the payoff for A′ are both bigger than the payoff for node B, so node B will change to cooperation. The payoff of the node B is bigger than the b nodes, so all the b nodes will turn to defection (figure 11).

Figure 11. Case 4: Following time-step t₁.

At that time-step, the following payoffs are rewarded:

\begin{aligned} P_{B} = T \times b + T (due to A) + T (due to A^{'}) + T (due to z) + T (due to z^{'}) = T (b + 4) \\ P_{A} = R \times a + R (due to z) + S (due to B) = R (a + 1) + S . \end{aligned}

Similarly,

\begin{aligned} P_{A^{'}} = R (a^{'} + 1) + S \\ P_{b_{i}} = S (due to B) . \end{aligned}

This gives the following requirements:

\begin{aligned} P_{B} < P_{A} and P_{B} < P_{A^{'}} \Leftrightarrow \\ T (b + 4) < R (a + 1) + S \end{aligned}

A 4

T (b + 4) < R (a^{'} + 1) + S

A 5

\begin{aligned} P_{b_{i}} < P_{B} \Leftrightarrow \\ S < T (b + 4); this is true as S < T and b > 0. \end{aligned}

At time-step t₂, the payoff for B is bigger then the payoff obtained by all the b nodes, so the b nodes will now return to cooperation.

At the moment, we have the following payoffs:

\begin{aligned} P_{B} = S \times b + R (due to A) + R (due to A^{'}) + R (due to z) + R (due to z^{'}) = S \times b + 4 R \\ P_{b_{i}} = T (due to B) . \end{aligned}

We now have the following constraints:

\begin{aligned} P_{B} > P_{b_{i}} \Leftrightarrow \\ S \times b + 4 R > T . \end{aligned}

A 6

Note that the number 4 (in 4R) can be increased by adding more enabler nodes.

Case 5: Node A or A′ is perturbed

At time-step t₀, node A is perturbed and becomes a defector (as depicted in figure 12).

At time-step t₁, the payoff of the initial defector, A (or A′), is bigger than all the nodes connected to it, so all the a (or a′) nodes and the z (or the z′) node will defect and if the payoff of the initial defector is bigger then the other critical node, the B node will defect (figure 13).

Figure 13. Case 5: Following time-step t₁.

At the moment, we have the following payoffs:

\begin{aligned} P_{A} (or P_{A^{'}}) = T \times a (or T \times a^{'}) + T (due to z (or z^{'})) + T (due to B) \\ = T \times (a + 2) (or T \times (a^{'} + 2)) \\ P_{a_{i}} (or P_{a_{i}^{'}}) = S (due to A (or A^{'})) \end{aligned}

P_{z} (or P_{z^{'}}) = R (due to B) + S (due to A (or A^{'})) = R + S .

\begin{aligned} P_{B} = R \times b + R (due to A^{'} (or A)) + R (due to z^{'}) \\ + R (due to z) + S (due to A (or A^{'})) = R (b + 3) + S \\ P_{A^{'}} (or P_{A}) = R \times a^{'} (or R \times a) \\ + R (due to z^{'} (or due to z)) + R (due to B) = R (a^{'} + 2) (or R (a + 2)) . \end{aligned}

We now have the following requirements:

\begin{aligned} P_{A} (or P_{A^{'}}) > P_{a_{i}} (or P_{a_{i}^{'}}) \\ P_{A} (or P_{A^{'}}) > P_{z} (or P_{z^{'}}) \\ P_{A} (or P_{A^{'}}) > P_{B} \Leftrightarrow \\ T (a + 2) (or T (a^{'} + 2)) > S, true as T > S and a and a^{'} > 0 \\ T (a + 2) (or T (a^{'} + 2)) > R + S, true as T > S, T > R and both a and a^{'} > 0 \\ T (a + 2) (or T (a^{'} + 2)) > R (b + 3) + S, true given (A 4), \\ T (a + 2) > R (a + 1) + S and T (b + 4) > R (b + 3) + S . \end{aligned}

If P_A (or $P_{A^{'}}$ ) > $P_{A^{'}}$ (or P_A), we will proceed to time-step t₂, otherwise we will jump straight to time-step t₄.

At time-step t₂, the payoff of node A′ is bigger then the payoff of node B, and the payoff of node A′ is bigger then the payoff of A. Hence, all the b nodes defect, and the B node cooperates (figure 14).

Figure 14. Case 5: Following time-step t₂.

At the moment, we have the following payoffs:

\begin{aligned} P_{B} & = T \times b + P (due to A) + T (due to A^{'}) + P (due to z) + T (due to z^{'}) \\ = T (b + 2) + 2 P \\ P_{A^{'}} & = R \times a^{'} + R (due to z^{'}) + S (due to B) = R (a^{'} + 1) + S \\ P_{A} = P \times a + P (due to z) + P (due to B) = P (a + 2) . \end{aligned}

This results in the following requirements:

\begin{aligned} P_{B} < P_{A^{'}} \Leftrightarrow \\ T (b + 2) + 2 P < R (a^{'} + 1) + S . \end{aligned}

Similarly for A′ as the initial defector

T (b + 2) + 2 P < R (a + 1) + S .

These are already satisfied given (A 4) and (A 5) and given T > P.

\begin{aligned} P_{A^{'}} > P_{A} \Leftrightarrow \\ R (a^{'} + 1) + S > P (a + 2) . \end{aligned}

A 7

Similarly for A′ as the initial defector

R (a + 1) + S > P (a^{'} + 2) .

A 8

At time-step t₃, the payoff of node B is bigger then the payoff of all the b nodes, the payoff of A needs to be smaller than the payoff of A′. All the b nodes will cooperate (figure 15).²^,³

Figure 15. Case 5: Following time-step t₃.

At the moment, we have the following payoffs:

\begin{aligned} P_{B} & = S \times b + R (due to A^{'}) + R (due to z^{'}) + S (due to A) + S (due to z) \\ = S (b + 2) + 2 R \\ P_{b_{i}} & = T (due to B) \\ P_{A^{'}} & = R \times a^{'} + R (due to z^{'}) + R (due to B) = R (a^{'} + 2) \\ P_{A} & = P \times a + P (due to z) + T (due to B) = P (a + 1) + T . \end{aligned}

We now have the following requirements:

\begin{aligned} P_{B} > P_{b_{i}} \Leftrightarrow \\ S (b + 2) + 2 R > T \end{aligned}

A 9

\begin{aligned} P_{A} < P_{A^{'}} \Leftrightarrow \\ P (a + 1) + T < R (a^{'} + 2) . \end{aligned}

A 10

Similarly for A′ as the initial defector

\begin{aligned} P_{A^{'}} < P_{A} \Leftrightarrow \\ P (a^{'} + 1) + T < R (a + 2) . \end{aligned}

A 11

At time-step t₄, the payoffs of node A and z are smaller then the payoff of node B.

The A node and the z node will then cooperate (figure 16).

At that moment, we have the following payoffs:

P_{B} = R \times b + R (due to A^{'}) + R (due to z^{'}) + S (due to A) + S (due to z) = R (b + 2) + 2 S

and

P_{A} = P \times a + P (due to z) + T (due to B) = P (a + 1) + T .

We now have the following requirements:

\begin{aligned} P_{A} < P_{B} \Leftrightarrow \\ P (a + 1) + T < R (b + 2) + 2 S . \end{aligned}

A 12

Similarly for A′ as the initial defector

\begin{aligned} P_{A^{'}} < P_{B} \Leftrightarrow \\ P (a^{'} + 1) + T < R (b + 2) + 2 S . \end{aligned}

A 13

At time-step t₅, the payoff of node A is bigger then the payoff of all the a nodes; all the a nodes will cooperate.

At the moment, we have the following payoffs:

P_{A} = S \times a + R (due to z) + R (due to B) = S \times a + 2 R

and

P_{a_{i}} = T (due to A) .

This results in the following requirements:

\begin{aligned} P_{a_{i}} < P_{A} \Leftrightarrow \\ T < S \times a + 2 R . \end{aligned}

A 14

Similarly for A′ as the initial defector

\begin{aligned} P_{a_{i}^{'}} < P_{A^{'}} \Leftrightarrow \\ T < S \times a^{'} + 2 R . \end{aligned}

A 15

Having considered all the cases and any constraints on the graph, we have the resulting list of constraints/requirements.

(A 1) 2T < R(a + 1) + S
(A 2) 2T < R(a′+1) + S
(A 3) 2T < R(b + 3) + S
(A 4) T(b + 4) < R(a + 1) + S
(A 5) T(b + 4) < R(a′ + 1) + S
(A 6) S × b + 4R > T
(A 7) R(a′ + 1) + S > P(a + 2)
(A 8) R(a + 1) + S > P(a′ + 2)
(A 9) S(b + 2) + 2R > T
(A 10) P(a + 1) + T < R(a′ + 2)
(A 11) P(a′ + 1) + T<R(a + 2)
(A 12) P(a + 1) + T < R(b + 2) + 2S
(A 13) P(a′ + 1) + T<R(b + 2) + 2S
(A 14) T < S × a + 2R
(A 15) T < S × a′ + 2R.

Appendix B

B.1. Extra requirement for the graph

For the definition of the critical nodes, in the case where it and all its minor nodes cooperate, it cannot be influenced to defect, to be fully correct, we need to consider one more scenario; the scenario where both the B node and the enabler node connecting them defect.

Case 6: Node B is perturbed and node z or z′ is perturbed

At time-step t₀, node B and z or z′ defect (figure 17).

At time-step t₁, the payoffs of A and A′ are bigger then the payoff of both node B and z or z′, so node B and z or z′ will cooperate. The payoff of node B is bigger than the b nodes, so all the b nodes will defect.

At the moment, we have the following payoffs:

\begin{aligned} P_{B} & = T \times b + T (due to A) + T (due to A^{'}) + P (due to z) + T (due to z^{'}) \\ = T (b + 3) + P \\ P_{A} & = R \times a + S (due to z) + S (due to B) = R \times a + 2 S \end{aligned}

Similarly for z′ as the initial defector,

P_{A^{'}}

= R(a′+1) + S

P_{b_{i}} = S (due to B)

P_{z} = T (due to A) + P (due to B)

We now have the following requirements:

P_z < P_A ⇔
$T + P < R \times a + 2 S .$ B 1
Similarly for z′ as the initial defector
$P_{z^{'}}, < P_{A^{'}} \Leftrightarrow$
$T + P < R \times a^{'} + 2 S .$ B 2
$P_{b_{i}} < P_{B} \Leftrightarrow$
$S < T (b + 3) + P, true since S < T and b > 0$
P_B < P_A ⇔
$T (b + 3) + P < R \times a + 2 S .$ B 3
Similarly for z′ as the initial defector
$P_{B} < P_{A^{'}} \Leftrightarrow$
$T (b + 3) + P < R \times a^{'} + 2 S .$ B 4

At the next time-step, we will be in the same spot as case 4, time-step t₁.

Appendix C

C.1. Examining the requirements of the Locodi graph

List of requirements:
- (A 1) 2T < R(a + 1) + S
- (A 2) 2T < R(a′+1)+S
- (A 3) 2T < R(b + 3) + S
- (A 4) T(b + 4) < R(a + 1) + S
- (A 5) T(b + 4) < R(a′ + 1)+S
- (A 6) S × b + 4R > T
- (A 7) R(a′+1) + S>P(a + 2)
- (A 8) R(a + 1) + S > P(a′ + 2)
- (A 9) S(b + 2) + 2R > T
- (A 10) P(a + 1) + T < R(a′ + 2)
- (A 11) P(a′ + 1) + T < R(a + 2)
- (A 12) P(a + 1) + T < R(b + 2) + 2S
- (A 13) P(a′ + 1) + T < R(b + 2) + 2S
- (A 14) T < S × a + 2R
- (A 15) T < S × a′+2R
- (B 1) T + P < R × a + 2S
- (B 2) T + P < R × a′+ 2S
- (B 3) T(b + 3) + P < R × a + 2S
- (B 4) T(b + 3) + P < R × a′+2S.

From (A 9):

S(b + 2) + 2R > T ⇔ b > (T − 2R − 2S)/S, if S > 0; if S = 0 ⇔ 2R > T (we can increase the number 2 in 2R by increasing the number of enabler nodes)

From (A 6):

S × b + 4R > T ⇔ b > (T − 4R)/S, if S > 0; if S = 0 ⇔ 4R > T

Note: this is irrelevant due to (A 9) (because both have to be true and (A 6) is always true when (A 9) is true).

From (A 14):

T < S × a + 2R ⇔ a > (T − 2R)/S, if S > 0; if S = 0 ⇔ 2R > T

From (A 15):

T < S × a′ + 2R ⇔ a′> (T − 2R)/S, if S > 0; if S = 0 ⇔ 2R > T

From (A 1), (A 2), (A 7), (A 8), (A 10), (A 11), (B 1) and (B 2):

(A 1): 2T < R(a + 1) + S ⇔
$a > \frac{2 T - S - R}{R}$
(A 2): 2T < R(a′ + 1) + S ⇔
$a^{'} > \frac{2 T - S - R}{R}$
(A 7): R(a′ + 1) + S > P(a + 2) ⇔
$a < \frac{R (a^{'} + 1) + S - 2 P}{P}$
$a^{'} > \frac{P (a + 2) - S - R}{R}$
(A 8): R(a + 1) + S > P(a′ + 2) ⇔
$a^{'} < \frac{R (a + 1) + S - 2 P}{P}$
$a > \frac{P (a^{'} + 2) - S - R}{R}$
(A 10): P(a + 1) + T < R(a′ + 2) ⇔
$a < \frac{R (a^{'} + 2) - T - P}{P}$
$a^{'} > \frac{P (a + 1) + T - 2 R}{R}$
(A 11): P(a′ + 1) + T < R(a + 2) ⇔
$a^{'} < \frac{R (a + 2) - T - P}{P}$
$a > \frac{P (a^{'} + 1) + T - 2 R}{R}$
(B 1): T + P < R × a + 2S ⇔
$a > \frac{T + P - 2 S}{R}$
(B 2): T + P < R × a′ + 2S ⇔
$a^{'} > \frac{T + P - 2 S}{R}$
(A 1), (A 2), (A 7), (A 8), (A 10), (A 11), (B 1) and (B 2): ⇔
$\begin{aligned} \max (\frac{2 T - S - R}{R}, \frac{P (a^{'} + 2) - S - R}{R}, \frac{P (a^{'} + 1) + T - 2 R}{R}, \frac{T + P - 2 S}{R}) < a \\ < \min (\frac{R (a^{'} + 1) + S - 2 P}{P}, \frac{R (a^{'} + 2) - T - P}{P}) \end{aligned}$
$\begin{aligned} max (\frac{2 T - S - R}{R}, \frac{P (a + 2) - S - R}{R}, \frac{P (a + 1) + T - 2 R}{R}, \frac{T + P - 2 S}{R}) < a^{'} \\ < \min (\frac{R (a + 1) + S - 2 P}{P}, \frac{R (a + 2) - T - P}{P}) \end{aligned}$
From (A 3), (A 4), (A 5), (A 12), (A 13), (B 3) and (B 4):(A 3): 2T < R(b + 3) + S ⇔
$b > \frac{2 T - S - 3 R}{R}$
(A 4): T(b + 4) < R(a + 1) + S ⇔
$\begin{aligned} b & < \frac{R (a + 1) + S - 4 T}{T} \\ a & > \frac{T (b + 4) - S - R}{R} \end{aligned}$
(A 5): T(b + 4) < R(a′ + 1) + S ⇔
$\begin{aligned} b & < \frac{R (a^{'} + 1) + S - 4 T}{T} \\ a^{'} & > \frac{T (b + 4) - S - R}{R} \end{aligned}$
(A 12): P(a + 1) + T < R(b + 2) + 2S ⇔
$\begin{aligned} b & > \frac{P (a + 1) + T - 2 S - 2 R}{R} \\ a & < \frac{R (b + 2) + 2 S - T - P}{P} \end{aligned}$
(A 13): P(a′ + 1) + T < R(b + 2) + 2S ⇔
$\begin{aligned} b & > \frac{P (a^{'} + 1) + T - 2 S - 2 R}{R} \\ a^{'} & < \frac{R (b + 2) + 2 S - T - P}{P} \end{aligned}$
(B 3): T(b + 3) + P < R × a + 2S ⇔
$\begin{aligned} b & < \frac{R \times a + 2 S - P - 3 T}{T} \\ a & > \frac{T (b + 3) + P - 2 S}{R} \end{aligned}$
(B 4): T(b + 3) + P < R × a′ + 2S ⇔
$\begin{aligned} b & < \frac{R \times a^{'} + 2 S - P - 3 T}{T} \\ a^{'} & > \frac{T (b + 3) + P - 2 S}{R} \end{aligned}$
(A 3), (A 4), (A 5), (A 12), (A 13), (B 3) and (B 4): ⇔
$\begin{aligned} max (\frac{2 T - S - 3 R}{R}, \frac{P (a + 1) + T - 2 S - 2 R}{R}, \frac{P (a^{'} + 1) + T - 2 S - 2 R}{R}) < b \\ < \min (\frac{R (a + 1) + S - 4 T}{T}, \frac{R (a^{'} + 1) + S - 4 T}{T}, \\ \frac{R \times a + 2 S - P - 3 T}{T}, \frac{R \times a^{'} + 2 S - P - 3 T}{T}) \end{aligned}$
As the values a, b, a′ tend to infinity, we get the following requirement P/R < R/T
$\begin{aligned} max (\frac{T (b + 4) - S - R}{R}, \frac{T (b + 3) + P - 2 S}{R}) < a, a^{'} < \frac{R (b + 2) + 2 S - T - P}{P} \end{aligned}$
Hence, we get the following requirement T/R < R/P which is the same as P/R < R/T.

From P/R < R/T ⇔ P < R²/T and T < R²/P, we have the following relation between payoffs: R²/P > T > R > R²/T > P > S.

Appendix D

D.1. Smallest possible graph (classical Prisoner's Dilemma payoffs) that guarantees robustness to one perturbation

We have enumerated the different cases for each of the different types of perturbation and illustrated how recovery to cooperation occurs. In doing so, we specified the various constraints that need to apply in the graph. These constraints allow us to derive the minimal size of the graph that will guarantee robustness.

We have the following payoffs: T = 5, R = 3, P = 1 and S = 0.
From appendix C, we have: max ((T(b + 4) − S − R)/R, (T(b + 3) + P − 2S)/R) < a, a′ < (R × (b + 2) + 2S − T − P)/P ⇔ max((5 × (b + 4) − 0 − 3)/3, (5 × (b + 3) + 1 − 0)/3) < a, a′ < (3 × (b + 2) + 2 × 0 − 5 − 1)/1 ⇔ (5b + 17)/3 < a, a′ < 3 × b
We need to find the smallest value of b where this is possible: (5b + 17)/3 < 3b ⇔ 5b + 17 < 9b ⇔ 17 < 4b ⇔ b > 4.25, b is a natural number ⇔ b > =5
For b = 5, we have: (5 × 5 + 17)/3 < a, a′ < 3 × 5 ⇔ 14 < a, a′ < 15, a, a′ are natural numbers ⇔ b > 5
For b = 6, we have: (5 × 6 + 17)/3 < a, a′ < 3 × 6 ⇔ 15.(6) < a, a′ < 18 ⇔ smallest value for a, a′ is 16

Final check to verify thata = 16, a′ = 16 andb = 6 respect all the requirements.

(A 1) $2 T < R (a + 1) + S \Leftrightarrow 2 \times 5 < 3 \times (16 + 1) + 0 \Leftrightarrow 10 < 51 (TRUE)$
(A 2) $2 T < R (a^{'} + 1) + S \Leftrightarrow 2 \times 5 < 3 \times (16 + 1) + 0 \Leftrightarrow 10 < 51 (TRUE)$
(A 3) $2 T < R (b + 3) + S \Leftrightarrow 2 \times 5 < 3 \times (6 + 1) + 0 \Leftrightarrow 10 < 21 (TRUE)$
(A 4) $T (b + 4) < R (a + 1) + S \Leftrightarrow 5 \times (6 + 4) < 3 \times (16 + 1) + 0 \Leftrightarrow 50 < 51 (TRUE)$
(A 5) $T (b + 4) < R (a^{'} + 1) + S \Leftrightarrow 5 \times (6 + 4) < 3 \times (16 + 1) + 0 \Leftrightarrow 50 < 51 (TRUE)$
(A 6) $S \times b + 4 R > T \Leftrightarrow 0 \times 6 + 4 \times 3 > 5 \Leftrightarrow 12 > 5 (TRUE)$
(A 7) $R (a^{'} + 1) + S > P (a + 2) \Leftrightarrow 3 \times (16 + 1) + 0 > 16 + 2 \Leftrightarrow 51 > 18 (TRUE)$
(A 8) $R (a + 1) + S > P (a^{'} + 2) \Leftrightarrow 3 \times (16 + 1) + 0 > 16 + 2 \Leftrightarrow 51 > 18 (TRUE)$
(A 9) $S (b + 2) + 2 R > T \Leftrightarrow 0 \times (6 + 2) + 2 \times 3 > 5 \Leftrightarrow 6 > 5 (TRUE)$
(A 10) $P (a + 1) + T < R (a^{'} + 2) \Leftrightarrow 1 \times (16 + 1) + 5 < 3 \times (16 + 2) \Leftrightarrow 22 < 54 (TRUE)$
(A 11) $P (a^{'} + 1) + T < R (a + 2) \Leftrightarrow 1 \times (16 + 1) + 5 < 3 \times (16 + 2) \Leftrightarrow 22 < 54 (TRUE)$
(A 12) $P (a + 1) + T < R (b + 2) + 2 S \Leftrightarrow 1 \times (16 + 1) + 5 < 3 \times (6 + 2) + 2 \times 0 \Leftrightarrow 22 < 24 (TRUE)$
(A 13) $P (a^{'} + 1) + T < R (b + 2) + 2 S \Leftrightarrow 1 \times (16 + 1) + 5 < 3 \times (6 + 2) + 2 \times 0 \Leftrightarrow 22 < 24 (TRUE)$
(A 14) $T < S \times a + 2 R \Leftrightarrow 5 < 0 \times 16 + 2 \times 3 \Leftrightarrow 5 < 6 (TRUE)$
(A 15) $T < S \times a^{'} + 2 R \Leftrightarrow 5 < 0 \times 16 + 2 \times 3 \Leftrightarrow 5 < 6 (TRUE)$
(B 1) $T + P < R \times a + 2 S \Leftrightarrow 5 + 1 < 3 \times 16 + 2 \times 0 \Leftrightarrow 6 < 48 (TRUE)$
(B 2) $T + P < R \times a^{'} + 2 S \Leftrightarrow 5 + 1 < 3 \times 16 + 2 \times 0 \Leftrightarrow 6 < 48 (TRUE)$
(B 3) $T (b + 3) + P < R \times a + 2 S \Leftrightarrow 5 \times (6 + 3) + 1 < 3 \times 16 + 2 \times 0 \Leftrightarrow 46 < 48 (TRUE)$
(B 4) $T (b + 3) + P < R \times a^{'} + 2 S \Leftrightarrow 5 \times (6 + 3) + 1 < 3 \times 16 + 2 \times 0 \Leftrightarrow 46 < 48 (TRUE)$

Since all the requirements are true the smallest graph has a = 16, a′=16 and b = 6.

Footnotes

1 Due to the manner in which the original graph is defined, the result of a simulation is either that all the nodes cooperate or all of them defect, so the results in the figure tell us how likely it is for the graph to fully cooperate given that a certain percentage of the nodes initially perturbed from cooperation to defection.

2 Some of the b nodes may be allowed to have a higher degree; in this case the time-step t₃ will be repeated multiple times, the b nodes need to be set such that all of them will cooperate eventually (the payoff of node B keeps on increasing each time until all the b nodes cooperate).

3 In most cases P_A > P_B; when this happens the process progresses to time-step t₄ at the end of time-step t₃; otherwise if P_B < P_A (when P ≈ 0); the process proceeds to time-step t₅ following time-step t₃.

Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, provided the original author and source are credited.

References

1.
Rapoport A, Chammah AM, Orwant CJ. 1965Prisoner's dilemma: a study in conflict and cooperation, vol. 165. Ann Arbor, MI: University of Michigan press. Crossref, Google Scholar
2.
Yao X, Darwen PJ. 1994An experimental study of N-person iterated prisoner's dilemma games. Informatica 18, 435-450. Google Scholar
3.
Boyd R, Richerson PJ. 1988The evolution of reciprocity in sizable groups. J. Theor. Biol. 132, 337-356. (doi:10.1016/S0022-5193(88)80219-4) Crossref, PubMed, ISI, Google Scholar
4.
Jeong HC, Oh SY, Allen B, Nowak MA. 2014Optional games on cycles and complete graphs. J. Theor. Biol. 356, 98-112. (doi:10.1016/j.jtbi.2014.04.025) Crossref, PubMed, ISI, Google Scholar
5.
Cardinot M, Gibbons M, O’Riordan C, Griffith J. 2016Simulation of an optional strategy in the Prisoner's Dilemma in spatial and non-spatial environments. In From Animals to Animats 14 (SAB 2016) pp. 145–156. Cham, Switzerland: Springer International Publishing. (doi:10.1007/978-3-319-43488-9_14) Google Scholar
6.
Killingback T, Doebeli M. 2002The continuous prisoner's dilemma and the evolution of cooperation through reciprocal altruism with variable investment. Am. Nat. 160, 421-438. (doi:10.1086/342070) Crossref, PubMed, ISI, Google Scholar
7.
Yazar J. 2005Evolutionary learning through replicator dynamics in continuous space games. In Proc. of SPIE, vol. 5803, p. 79. (doi:10.1117/12.604232) Google Scholar
8.
Nowak MA. 2006Evolutionary dynamics. Harvard, MA: Harvard University Press. (doi:10.1017/S0013091508225137) Crossref, Google Scholar
9.
Nowak MA, Tarnita CE, Antal T. 2010Evolutionary dynamics in structured populations. Phil. Trans. R. Soc. B 365, 19-30. (doi:10.1098/rstb.2009.0215) Link, ISI, Google Scholar
10.
Nowak MA, May RM. 1992Evolutionary games and spatial chaos. Nature 359, 826-829. (doi:10.1038/359826a0) Crossref, ISI, Google Scholar
11.
Szolnoki A, Perc M. 2016Leaders should not be conformists in evolutionary social dilemmas. Sci. Rep. 6, 23633. (doi:10.1038/srep23633) Crossref, PubMed, ISI, Google Scholar
12.
Xia CY, Meloni S, Perc M, Moreno Y. 2015Dynamic instability of cooperation due to diverse activity patterns in evolutionary social dilemmas. EPL 109, 58002. (doi:10.1209/0295-5075/109/58002) Crossref, ISI, Google Scholar
13.
Santos FC, Pacheco JM. 2005Scale-free networks provide a unifying framework for the emergence of cooperation. Phys. Rev. Lett. 95, 098104. (doi:10.1103/PhysRevLett.95.098104) Crossref, PubMed, ISI, Google Scholar
14.
Chen X, Wang L. 2008Promotion of cooperation induced by appropriate payoff aspirations in a small-world networked game. Phys. Rev. E 77, 017103. (doi:10.1103/PhysRevE.77.017103) Crossref, ISI, Google Scholar
15.
Fu F, Liu LH, Wang L. 2007Evolutionary Prisoner's Dilemma on heterogeneous Newman-Watts small-world network. Eur. Phys. J. B 56, 367-372. (doi:10.1140/epjb/e2007-00124-5) Crossref, ISI, Google Scholar
16.
O’Riordan C, Cunningham A, Sorensen H. 2008Emergence of cooperation in N-player games on small world networks. In Artificial Life XI: Proc. of the 11th Int. Conf. on the Synthesis and Simulation of Living Systems, Winchester, UK, 5–8 August, pp. 436–442. See http://mitpress.mit.edu/sites/default/files/titles/alife/0262287196chap57.pdf. Google Scholar
17.
Peña J, Rochat Y. 2012Bipartite graphs as models of population structures in evolutionary multiplayer games. PLoS ONE 7, 1-13. (doi:10.1371/journal.pone.0044514) Crossref, ISI, Google Scholar
18.
Gomez-Gardenes J, Romance M, Criado R, Vilone D, Sánchez A. 2011Evolutionary games defined at the network mesoscale: the Public Goods game. Chaos 21, 016113. (doi:10.1063/1.3535579) Crossref, PubMed, ISI, Google Scholar
19.
Nowak MA, May RM. 1993The spatial dilemmas of evolution. Int. J. Bifurcation Chaos 3, 35-78. (doi:10.1142/S0218127493000040) Crossref, ISI, Google Scholar
20.
Chalupa J, Leath PL, Reich GR. 1979Bootstrap percolation on a Bethe lattice. J. Phys. C: Solid State Phys. 12, L31. (doi:10.1088/0022-3719/12/1/008) Crossref, ISI, Google Scholar
21.
Li Y, Jin X, Su X, Kong F, Peng C. 2010Cooperation and charity in spatial public goods game under different strategy update rules. Physica A 389, 1090-1098. (doi:10.1016/j.physa.2009.11.010) Crossref, ISI, Google Scholar
22.
Locodi AM. 2021Data and Code from: Introducing a graph topology for robust cooperation. Zenodo. (doi:10.5281/zenodo.4562672) Google Scholar
23.
Lieberman E, Hauert C, Nowak MA. 2005Evolutionary dynamics on graphs. Nature 433, 312-316. (doi:10.1038/nature03204) Crossref, PubMed, ISI, Google Scholar
24.
Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak MA. 2017Amplification on undirected population structures: comets beat stars. Sci. Rep. 7, 1-8. (doi:10.1038/s41598-017-00107-w) Crossref, PubMed, ISI, Google Scholar
25.
Villatoro D, Sabater-Mir J, Sen S. 2013Robust convention emergence in social networks through self-reinforcing structures dissolution. ACM Trans. Auton. Adapt. Syst. (TAAS) 8, 1-21. (doi:10.1145/2451248.2451250) Crossref, ISI, Google Scholar

Comments

This Issue

May 2021

Volume 8Issue 5

Article Information

PubMed:34035944
Published by:Royal Society
Online ISSN:2054-5703

History:

Manuscript received30/10/2020
Manuscript accepted03/03/2021
Published online05/05/2021

License:

Citations and impact

Keywords

Subjects