Introducing a graph topology for robust cooperation

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.