Excursions in Programming
Mathematica in Education and Research
Vol. 4 No. 4
Fall 1995

Copyright 1996 TELOS/Springer-Verlag

The Evolution of Cooperation 
and
The Spatial Prisoner's Dilemma Game

by
Richard J. Gaylord and Kazume Nishidate

Introduction

Why do individuals, people and animals, help one another? Restated in the terminology of evolutionary biology, what is the survival value of altruism (ie., why does natural selection result in the evolution of cooperative social behavior)?

The question of the origin of cooperative social behavior is not unimportant. Essentially every political philosophy, with the exception of radical libertarianism (anarcho-capitalism), is based on the axiom that it is necessary to have a powerful authoritary, the state, to bring about cooperation between individuals. If it can be shown that social cooperation arises naturally amongst people without being forced upon them, then the rationale often given for government intrusion in the affairs of its citizens becomes less compelling.

What makes the evolution of cooperation between members in a group especially puzzling is that whenever two individuals interact in a single encounter, the rational behavior for each party is to be non-cooperative. This can be shown by a game theoretic analysis of the situation known as the prisoner's dilemma. In an isolated interaction between two individuals, each of whom must choose between two interaction strategies, cooperation and non-cooperation, there are four possible outcomes of the interaction:  a win-win situation arising from both parties (players) cooperating with one another (each player gets a payoff R), a win-lose situation and a lose-win situation in which one of the parties cooperates while the other party does not (the uncooperative player gets a payoff T and the cooperative player gets a payoff S), and a lose-lose situation in which both parties are uncooperative (each player gets a payoff P). If T > R > P > S, it is always in each player's self-interest to be uncooperative.

Several solutions have been proposed to account for what appears to be irrational 'nice guy' behavior between the unrelated individuals in a group (altruism between kinfolk is not unexpected; it can be understood in terms of gene survivability). Mutual aid behavior could be expected if there are repeated encounters between individuals, in each of which, the players choose their strategies based either on the outcomes obtained in previous encounters or in anticipation of future encounters. Cooperation might also arise if natural selection were concerned with the survival of groups rather than individuals.

Recently, it has been suggested [Nowak  and May, 1992-5] that spatial effects alone are sufficient to cause cooperative behavior . Nowak and May use a cellular automaton to model the evolution of cooperation. In their CA, all of the sites of a two-dimensional lattice are occupied by players. The players interact with their nearest neighbor players in a pair-wise manner, over a number of time steps. The interaction  strategies used by the players in each time step is determined as follows: In a given time step, each player interacts with itself and with its eight nearest neighbors (ie., the nine sites in the Moore neighborhood of the player) using either a cooperative strategy (denoted by C) or an un-cooperative strategy (denoted by D). The total payoff to each player resulting from the nine interactions is determined and each player then adapts for the next time step, the strategy of the player in its Moore neighborhood (including itself) who received the highest payoff.

We will develop a program for this 'spatial prisoner's dilemma' cellular automaton.

The Spatial Prisoner's Dilemma CA

The strategy adopted in each time step by a player (ie., the value of each site in the CA lattice), depends on both the total payoff earned by the player as a result of its interactions with its eight nearest neighbor players and the total payoffs earned by the nearest neighbor players as a result of their interactions with their eight nearest neighbor players. Thus, each player's strategy is based the values of the twenty-five neighbors in its 5 by 5 neighborhood . Since each player can have 2 values (C or D), a specification of the CA rules based on enumerating every possible set of values of the 25 neighbor sites would require 2^25 rules. Rather attempting to write down or  generate, these (appoximately) thirty-three million rules for use as 'look-up' tables in the CA program, we will employ a more 'computational' approach to implementing the CA.

The system

The CA employs a  (2 n + 1) by  (2 n + 1) square lattice, with periodic boundary conditions. The lattice sites have values of C or D, representing strategies of cooperation and non-cooperation (defection). The initial distribution of cooperators and defectors needs to be specified. For a random distribution of C's and D's on the lattice, the initial configuration is given by

initConf = Table[{C, D}[[Random[Integer, {1,2}]]], {2n+1}, {2n+1}]

For a single defector amidst a sea of cooperators, initConf is given by

initConf = ReplacePart[Table[C, {2n+1}, {2n+1}], D, {n+1, n+1}]

Playing the game

The prisoner's dilemma 'game' is played over  a number of rounds (ie., time steps), in each of which every prisoner (site) on the lattice interacts with itself and with the eight nearest neighbor sites in its Moore neighborhood.

Each round of interaction proceeds as follows (we will use the symbol 'jail' below to indicate the value of the CA lattice in a given round of play):

In the first stage, each prisoner interacts with the prisoners in its Moore neighborhoods in a pair-wise manner. A 'payoff' value is computed for each interaction as follows:

If the player and its neighbor both cooperate, the player gets a point.

outcome[C, C] = 1

If the player and its neighbor both defect, the player gets nothing.

outcome[C, D] = 0

If the player cooperates and its neighbor defects, the player gets nothing.

outcome[D, D] = 0

If the player defects and its neighbor cooperates, the player gets p points (p >1).

outcome[D, C] = p

Note: These payoff values correspond to using S = P = 0, R = 1, T = p (p > 1) in the prisoner's dilemma. These values are used to simplify the program to using a single payoff parameter value but other payoff values will produce the same results (see computer simulation project #2).

The total payoff for a player in a round is determined by adding together, the nine payoffs resulting from the interactions of the player with each site in its neighborhood (including itself). This is done using the values of the nine players in the Moore neighborhood of a site, the outcome rules and the function

totalPayoffPlayer[x_, a_, b_, c_, d_, e_, f_, g_, h_] := 
        outcome[x, x] + outcome[x, a] + outcome[x, b] + outcome[x, c] + outcome[x, d] +
        outcome[x, e] + outcome[x, f] + outcome[x, g] + outcome[x, h]

The totalPayoffPlayer function needs to be applied to the neighborhood of each player in jail. This is done using the following function:

MooreValues[func_, lat_] :=  
   MapThread[func, {#, RotateRight[#, {0, 1}], RotateRight[#, {1, 0}], RotateRight[#, {0, -1}],
                       RotateRight[#, {-1, 0}], RotateRight[#, {1, 1}], RotateRight[#, {1, -1}],
                       RotateRight[#, {-1, -1}], RotateRight[#, {-1, 1}]}, 2]&[lat]

The MooreValues function applies a function, func, to the nine sites in the Moore neighborhood of each site in the lattice, lat [see Gaylord and Nishidate, 1995]. This can be illustrated by looking at the lattice generated using the MooreValues function with the undefined function, g, and the simple lattice, mat .

(mat = Partition[Range[9], 3]) // MatrixForm

MooreValues[g, mat]

Using the MooreValues function with the totalPayoffPlayer function and the jail lattice produces a square lattice, totalPayoffLat, whose sites have the value of the total payoff earned by the corresponding lattice site in jail.

totalPayoffLat = MooreValues[totalPayoffPlayer, jail]

The player looks at the total payoffs of all of the players in its neighborhood (including itself) and adopts the strategy of the player with the greatest payoff. This is done as follows:

A lattice is created whose site values consist of an ordered pair, {x, y}, where x (a non-negative integer) is the payoff earned by a site, and y (symbol C or D) is the strategy employed by the site to obtain that value.

sitePayoffPairsLat = MapThread[List, {totalPayoffLat, jail}, 2]

The sitePayoffPairsLat lattice is used with the function

BestNbrhdPayoffStrategy[x__] := Last[Sort[{x}]][[2]]

and the MooreValues function.

newStrategyLat = MooreValues[BestNbrhdPayoffStrategy, sitePayoffPairsLat]

The BestNbrhdPayoffStrategy function determines which strategy in the Moore neighborhood of a site earned the greatest payoff. This is done by placing the nine ordered pairs in the neighborhood of a site in sitePayoffPairsLat in a list, sorting the list (so that the ordered pairs appear in order of increasing payoff value), and taking the second component of the last element in the sorted list.

The overall selection of a new strategy can be carried out using the following anonymous function, StrategyDecision, where the # symbol represents the value of the jail in a given time step.

StrategyDecision :=
   (totalPayoffLat = MooreValues[totalPayoffPlayer, #]; 
    sitePayoffPairsLat = MapThread[List, {totalPayoffLat, #}, 2];
    BestNbrhdPayoffStrategy[x__] := Last[Sort[{x}]][[2]]; 
    newStrategyLat = MooreValues[BestNbrhdPayoffStrategy, sitePayoffPairsLat]
    )&

The StrategyDecision is applied repeatedly to jail n times using the NestList function

evolution = NestList[StategyDecision, jail, t]

The program

We'll look at the evolution of a system consisting of a single defector in a sea of collaborators.

SpatialPrisonersDilemma[n_, p_,  t_] :=  
 Module[{initConf, MooreValues, totalPayoffPlayer, outcome, StrategyDecision, totalPayoffLat,
                 sitePayoffPairsLat, BestNbrhdPayoffStrategy, newStrategyLat, evolution}, 

 initConf = ReplacePart[Table[C, {2 n + 1}, {2 n + 1}], D, {n + 1, n + 1}];

 MooreValues[function_, lat_] :=  
   MapThread[function, {#, RotateRight[#, {0, 1}], RotateRight[#, {1, 0}],   
      RotateRight[#, {0, -1}], RotateRight[#, {-1, 0}], RotateRight[#, {1, 1}],
      RotateRight[#, {1, -1}], RotateRight[#, {-1, -1}], RotateRight[#, {-1, 1}]}, 2]&[lat];

  totalPayoffPlayer[x_, a_, b_, c_, d_, e_, f_, g_, h_] := 
      outcome[x, x] + outcome[x, a] + outcome[x, b] + outcome[x, c] + 
      outcome[x, d] + outcome[x, e] + outcome[x, f] + outcome[x, g] + outcome[x, h];

 outcome[C, C] = 1; 
 outcome[C, D] = 0;
 outcome[D, D] = 0; 
 outcome[D, C] = p;  
 
 StrategyDecision :=
   (totalPayoffLat = MooreValues[totalPayoffPlayer, #]; 
    sitePayoffPairsLat = MapThread[List, {totalPayoffLat, #}, 2];
    BestNbrhdPayoffStrategy[x__] := Last[Sort[{x}]][[2]]; 
     newStrategyLat = MooreValues[BestNbrhdPayoffStrategy, sitePayoffPairsLat] )&;

  evolution = NestList[StrategyDecision, initConf, t] 
   ]

Note: It is interesting to do a side-by-side comparision of programs which implement the spatial prisoner's dilemma model in a functional, rule-based style, as done here, and in a procedural style [Lloyd, 1995].

Running the program

In order to visualize the results obtained from running the SpatialPrisonersDilemma program, we can create a RasterArray using a coloring scheme based on the strategy used by each player in both the current round and the previous round. The coloring is done as follows:

If a player is cooperating now and cooperated in the previous step, it is colored blue.
If a player is defecting now and defected in the previous step, it is colored red.
If a player is cooperating and defected in the previous step, it is colored green.
If a player is defecting now and cooperated in the previous step, it is colored yellow.

According to this scheme, geen and yellow cells indicate changes in strategy from one generation to the next, and red and blue indicate cells with unchanged strategies.

The coloring scheme is implemented in the following animation program:

SocialEvolution[lis_] := Module[{picture}, 
   picture = Rest[MapThread[color, {#, RotateRight[#]}&[lis], 3]];
   Map[Show[Graphics[RasterArray[Reverse[#] /. {color[C, C] -> RGBColor[0, 0, 1], color[D, D]  -> RGBColor[1, 0, 0], color[C, D]  -> RGBColor[0, 1, 0], color[D, C]  -> RGBColor[1, 1, 0]}]], AspectRatio -> Automatic, DisplayFunction -> Identity]&, picture]
   ]

A single graphic showing all of the animation cells created with SocialEvolution can be created using

Show[GraphicsArray[Partition[SocialEvolution[lis], r] ]]

An example output is shown below for the case of an initial state of a single defector in a sea of cooperators.

Show[GraphicsArray[
Partition[SocialEvolution[SpatialPrisonersDilemma[25, 1.85,  20]], 5] ]];

For an initial state consisting of a random distribution of cooperators or defectors, cooperators and defectors are found to co-exist in fluctuating chaotic patterns for a range of b values.

Computer Simulation Projects

1. Calculate and plot the frequency of cooperators in the spatial prisoner's dilemma game over time as a function of p, the advantage of defection over cooperation.

2. In addition to 'spatializing' the prisoner's dilemma, other evolutionary games can be given a spatial component by using various payoff values in the program. For example, in the Hawk-Dove game, the payoff for a hawk interacting with another hawk is less than the payoff for a dove interacting with a hawk while the payoff for a dove interacting with a dove is less than the payoff for a hawk interacting with a dove. Modify the outcome rules to implement the spatial Hawk-Dove game and run the resulting program.

3. There are two interaction strategies used in the prisoner's dilemma. A variation of the game is obtained by having three or more strategies. One example of this is the well-known children's game, 'stone-scissors-paper', in which stone beats scissor, scissor beats paper, and paper beats stone. Implement this game and run it to obtain spiral waves, remiscent of excitable media behavior [Gaylord and Wellin, 1995].

4. An interesting way to extend the spatial evolutionary game would be to incorporate diffusive movement by the players. This can be done by combining the random walk CA [Gaylord and Nishidate, 1995] with the spatial prisoner's dilemma CA.

General References

Nowak, Martin A., May, Robert, M., and Sigmund, Karl. "The Arithmetics of Mutual Help". Scientific American, vol. 272, (June) 1995. pp. 76 - 81.

Nowak, Martin A. and May, Robert, M. "Evolutionary Games and Spatial Chaos". Nature, vol. 359, 1992. pp. 826 - 829.

Nowak, Martin A. and May, Robert, M. "The Spatial Dilemma of Evolution". International Journal of Bifurcation and Chaos, vol. 3, 1993. pp. 35 - 78

Nowak, Martin A., Bonhoeffer, Sebastian and May, Robert, M. "More Spatial Games". International Journal of Bifurcation and Chaos, vol. 4, 1994. pp. 33 - 56.

Lloyd, Alun, L. "Computing Bouts ofthe Prisoner's Dilemma"". Scientific American, vol. 272, (June) 1995. pp. 110 - 115.

Gaylord, Richard J. and Nishidate, Kazume. "A Simple Rule-Based Programming Approach to Modeling Complex Random Walk Systems with Cellular Automata", Mathematica in Education and Research, 4(2), xxx (1995).

Gaylord, Richard J. and Wellin, Paul R. "Computer Simulations with Mathematica: Explorations in Complex Physical and Biological Systems", TELOS/Springer-Verlag (1995).