Fewer Friends, More Cooperation

Cooperation is fundamental to all social and biological systems. If cells did not cooperate, multi-cellular organisms would never have evolved [1]. If people did not cooperate, there would be no nation states [2]. But this wide-scale cooperation is somewhat of a mystery from the perspective of Darwinian evolution, which would seem to favor competition for scarce resources and reproductive success over cooperation. Cooperation incurs a cost to provide a benefit elsewhere. Indeed, a basic finding in agent-based computer simulations with unstructured populations is that evolution favors defection over cooperation [3]. As a result, there has been intensive research into spatially structured populations, attempting to explain the pervasive cooperation seen in nature. Under certain realistic spatial conditions, an agent is more likely to encounter members of its own gene pool than would be expected by chance; and this allows cooperation to evolve [4].

A particularly important study in this tradition is that of Ohtsuki and colleagues [5] at Harvard’s productive Program for Evolutionary Dynamics. Their complex mathematical derivations and computer simulations conveniently conform to a rather simple rule: that evolution favors cooperation if the benefit of receiving cooperation b divided by the cost c of giving it exceeds the average number of neighbors k in the population. Or, b/c > k, exactly parallel to Hamilton’s famous rule where the b/c ratio had to exceed relatedness r in order for cooperation to thrive [6].

Ohtsuki et al.’s simulations find that this rule holds in a wide variety of graph structures: lattices, cycles, random regular graphs, random graphs, and scale-free networks. Square lattices involve either von Neumann (k = 4) or Moore (k = 8) neighbors. Cycles involve a circular arrangement of agents where k = 2. In random regular graphs, the links between agents are random except that every agent has an equal number of links (k). Random graphs are similar except that agents have an average of k links, rather than exactly k. Scale-free networks are hub-like graphs generated according to the method of preferential attachment: an agent links with others in proportion to the other’s connectivity [7].

Similar results obtain for two different reproductive schemes: death-birth and imitation. For death-birth updating, in each time step a random individual is chosen to die, and its neighbors compete for the empty site in proportion to their fitness. At each cycle of imitation updating, a random agent keeps its own strategy or imitates a neighbor’s strategy proportional to their fitness. In all cases, fitness is determined by the outcome of each agent’s interactions with its neighbors.

Death-birth updating: Image from Ohtsuki et al. 2006

In this graph [5], a blue co-operator competes with a red defector for newly-freed location via death-birth updating. The co-operating candidate’s fitness is 2b-4c because it receives cooperation from two neighboring co-operators and gives cooperation to four neighbors. The defecting candidate’s fitness is b because it receives cooperation from one co-operator and gives no cooperation.

For imitation updating, cooperation evolves as long as b/c > k + 2, the plus 2 because each agent is effectively its own neighbor.

The last sentence of the Ohtsuki paper [5] nicely summarizes the results: “The fewer friends I have, the more strongly my fate is bound to theirs.” This derives from the effect of k, which varies from 2-10. As k decreases, it is exceeded by smaller values of the b/c ratio.

In a very crowded literature, this paper is particularly notable for including both simulations and mathematical analysis; in effect, the simulation results provide empirical confirmation of the mathematics. Typical studies use only one of these methods, leaving readers to wonder whether the results would generalize to parameter settings other than those used in simulations, or whether the mathematical analysis was done properly or can predict empirical simulation results. The paper is also notable for including a fairly wide variety of graph structures. More typically, one sees results for only one particular graph, most often a square lattice. In all of these ways, the Ohtsuki et al. paper serves as inspiration for future theoretical work on evolution.

References

1.           Axelrod, R. and W.D. Hamilton, The evolution of cooperation. Science, 1981. 211: p. 1390-1396.

2.           Wedekind, C. and M. Milinski, Cooperation through image scoring in humans. Science, 2000. 228: p. 850-852.

3.           Nowak, M.A., Evolutionary dynamics2006, Cambridge, MA: Harvard University Press.

4.           Lieberman, E., C. Hauert, and M.A. Nowak, Evolutionary dynamics on graphs. Nature, 2005. 433: p. 312-316.

5.           Ohtsuki, H., Hauert, C., Lieberman, E., & Nowak, M. (2006). A simple rule for the evolution of cooperation on graphs and social networks Nature, 441 (7092), 502-505 DOI: 10.1038/nature04605

6.           Hamilton, W.D., The genetical evolution of social behaviour, I. Journal of Theoretical Biology, 1964. 7: p. 1-16.

7.           Santos, F.C. and J.M. Pacheco, Scale-free networks provide a unifying framework for the emergence of cooperation. Physical Review Letters, 2005. 95.

About these ads

About Thomas Shultz
Prof. Dept. of Psychology Assoc. Member, School of Computer Science McGill U

3 Responses to Fewer Friends, More Cooperation

  1. Just a note about the b/c > k and potential relationship to Hamilton’s rule. I might have mentioned this before, but the PD as used in this paper and countless others is in general completely described by a single parameter g = c/b (or equivalently its inverse g^{-1} = b/c. In the Ohtsuki et al. paper (and many others where absolute magnitudes are irrelevant or weak selection is assumed) changing b and c simultaneously while preserving g does not change the dynamics at all. Since we expect any results to depend on the game, we must have g show up in the inequalities. We also know that games on different graphs behave differently, so we should expect a dependence on some graph parameter; in this case they concentrate on the average degree k, and so it shows up in the equation. They get lucky and the equation is the simplest possible b/c - k > 0, and similar results abound because this happens to be the simplest equation that could possibly make sense and not because there is a connection to the ideas behind Hamilton’s rule c/b - r < 0.

    To show a connection to Hamilton's rule one would have to clearly explain how/why 1/k = r, or in words: how does degree of the graph relate to relatedness? One such connection could be that on average one of your neighbours is your clone and the rest are unrelated to you, then if you select a neighbour at random, her relatedness is 1/k. This would work well for the Birth-Death dynamics… but becomes pretty confusing for immitation dynamics, since an agent has a relatedness of 1 to itself. Of course, we have to be careful since with imitation the reproduction and interaction graphs are not the same. You don't interact with yourself, but you can imitate yourself. I don't remember if Ohtsuki et al. discuss this explicitly, but I am sure they are aware of it.

    In general, I think the paper is a very nice result. However, a expect this first-order to fail for certain graphs where we make very bimodal degree distributions with an average at k. I will try to build a counter-example sometime and post it.

  2. Pingback: Some stats on the first 50 posts « Theory, Evolution, and Games Group

  3. Pingback: Pochi ma Buoni ? | Num3ri v 2.0

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 2,076 other followers