Open AccessIntroducing a graph topology for robust cooperation
Author(s) -
A. M. Locodi,
Colm O’Riordan
Publication year - 2021
Publication title -
royal society open science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.84
H-Index - 51
ISSN - 2054-5703
DOI - 10.1098/rsos.201958
Subject(s) - computer science , graph , theoretical computer science , population , dilemma , graph property , robustness (evolution) , mathematical optimization , topology (electrical circuits) , mathematics , voltage graph , line graph , combinatorics , demography , sociology , biochemistry , chemistry , geometry , gene
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.