The rules of the game. Each individual occupies the vertex of a graph and derives a payoff, P, from interactions with adjacent individuals. A cooperator (blue) pays a cost, c, for each neighbor to receive a benefit, b. A defector (red) pays no cost and provides no benefit. The fitness of a player is given by 1 − w + wP, where w measures the intensity of selection. Strong selection means w = 1. Weak selection means w ≪ 1. For ‘death-birth’ updating, at each time step, a random individual is chosen to die; subsequently the neighbors compete for the empty site proportional to their fitness. In this example, the central vertex will change from a defector to a cooperator with a probability F_C/(F_C +F_D), where the total fitness of all adjacent cooperators and defectors is F_C = 4(1 − w) + (10b − 16c)w and F_D = 4(1 − w) + 3bw, respectively.

Some intuition for games on graphs. (a) For ‘death-birth’ (DB) updating, we must consider a cooperator and a defector competing for an empty site. The pair-approximation calculation shows that for weak selection the cooperator has one more cooperator among its k − 1 other neighbors than the defector. Hence, the cooperator has a higher chance to win the empty site if b/c > k. (b) For ‘birth-death’ (BD) updating, we must consider a cooperator-defector pair competing for the next reproduction event. Again the cooperator has one more cooperator among its k − 1 other neighbors than the defector, but the focal cooperator is also a neighbor of the defector. Hence, both competitors are linked to the same number of cooperators, and therefore the defector has a higher payoff. For BD updating, selection does not favor cooperation. (c) On a cycle (k = 2), the situation is simple. A direct calculation, for weak selection and large population size, leads to the following results. For BD updating, the boundary between a cluster of cooperators and defectors tends to move in favor of defectors. For DB updating, the cooperator cluster expands if b/c > 2. For IM updating, the cooperator cluster expands if b/c > 4.

The simple rule, b/c > k, is in good agreement with numerical simulations. The parameter k denotes the degree of the graph, which is given by the (average) number of neighbors per individual. The first row illustrates the type of graph for (a) k = 2 and (b–e) k = 4. The second and third rows show simulation data for population sizes N = 100 and N = 500. The fixation probability, ρ, of cooperators is determined by the fraction of runs where cooperators reached fixation out of 10⁶ runs under weak selection, w = 0.01. Each type of graph is simulated for different (average) degrees ranging from k = 2 to k = 10. The arrows mark b/c = k. The dotted horizontal line indicates the fixation probability 1/N of neutral evolution. The data suggest that b/c > k is necessary but not sufficient. The discrepancy is larger for non-regular graphs (d,e) with high average degree (k = 10). This is not surprising given that the derivation of the rule is for regular graphs and in the limit N ≫ k. Note that the larger population size, N = 500, gives better agreement.