Abstract

In this paper, the genetic algorithm is used to investigate the evolution of cooperation based upon automata that play in an iterated prisoner’s dilemma tournament. Cooperation evolved from a state of randomness. Furthermore, it is shown that “niceness”, as defined by Robert Axelrod, is unstable in this model, and, contrary to previous speculation, selective pressure is needed to stabilize niceness. A multiprocessing approach also shows that cooperation can spread through migration among multiple evolving populations.

Introduction

Can cooperation evolve in a society of egoists without the existence of a central authority? This an intriguing question because, in nature, we find that evolution rewards the efforts of individuals with selfish motives. With a limited supply of life-sustaining resources available to a population, an organism must compete with others in its population to obtain resources essential to its survival and maximization of reproductive success. Since it is the selfish behavior of the organism that ensures its self-preservation, there is no reason for cooperation to take place. On the other hand, we know that cooperation does indeed take place—ants work together in construction and the gathering of food for the benefit of the colony; people cooperate with one another on a day-to-day basis.

This question—the problem of cooperation—has been investigated in the work of Robert Axelrod (1984). In his work, Axelrod uses a model known as the prisoner’s dilemma game to studying cooperation. Two players take part in the prisoner’s dilemma game. Each player must make a move, either to cooperate or to defect with the opposing player, without knowing what the other player will do. Scoring is calculated as shown in the payoff matrix (Figure 1). It is known by both players that acting selfishly—defecting—yields a higher payoff than cooperating no matter what the other player does, and so the natural decision is to defect. However, it is also known that by cooperating, both players can collectively do better than if both defect, hence the dilemma. Axelrod proposes that for cooperation to take place, a series of games must be played so that players can anticipate future interactions, and base their move decisions upon previous game outcomes. In this model, the iterated prisoner’s dilemma, it becomes rational to cooperate.

To satisfy his interest, namely which strategies were the most effective in the iterated prisoners dilemma game, Axelrod had participants from various disciplines submit hand-crafted computer programs. Each program defined a strategy for playing the game with another program. In a round-robin style tournament, he matched each program submitted with all other programs, and ranked them based upon their scores. In each tournament, the simplest strategy, TIT FOR TAT (in which the first move is to cooperate, and then in each subsequent move to copy the opposing player’s previous move), received the highest scores. Given its success, Axelrod questioned the robustness of the strategy—he wanted to see how well it would do in other environments. Knowing that the success of any particular strategy depends upon the environment with which it interacts, Axelrod devised a set of pseudo-evolutionary experiments in which the frequency of each strategy in a population of strategies was dependent on its success in preceding tournaments. This variation on survival of the fittest is not to be confused with a true evolutionary experiment, since the set-up of the tournaments does not allow for new behavior to emerge. In contrast, it simply allows those more successful to become more frequent.

In this ecological simulation, Axelrod found that those strategies demonstrating a particular behavior known as niceness ultimately dominate a population initially filled with equal proportions of both nice and non-nice strategies. To clarify: A strategy is defined to be nice if in its interaction with any other strategy, it is never the first to defect.

Methods

In Axelrod’s work, he uses hand-crafted programs to play the prisoner’s dilemma game. With the genetic algorithm, however, it would like to be discerned whether or not cooperation can emerge from a state of randomness. Therefore, each individual must begin with randomly composed genetic data that defines a strategy for playing the iterated prisoners dilemma game with other individuals in the population. The genetic algorithm will evolve new generations of individuals with chances of reproduction based upon an individual’s fitness score (where fitness in this case is determined by how well the individual plays the iterated prisoner’s dilemma game against other members of the population.) In the genetic algorithm, individuals in the subsequent generation are created by applying two genetic operators: recombination and mutation. The new individual’s genetic data is defined by recombining the data of their selected parents. Depending upon probability, the genetic data of the new individual may also undergo a small mutation. An in-depth discussion of the genetic algorithm can be found by consulting Goldberg (1989). Furthermore, like the hand-crafted strategies Axelrod uses, individuals must be able to take into account a memory of past interactions with the opposing player when deciding whether to cooperate or defect at any given point in the game. An excellent, uncomplicated way of representing past knowledge is through the use of a state machine.

Unlike a computer, a state machine’s memory capacity is set permanently upon its creation, and cannot be changed throughout its lifetime. This type of machine is known as an automaton. Typically, automata are fed input strings, and based upon each character fed to it, the automaton changes state according to its state transition function. After the entire string has been consumed by the automaton, it is said to be in either a state in which the string is accepted, or in a non-accepting state. Formally, this type of computational device is known as a deterministic finite-state automaton (Lewis and Papadimitriou 1998). We need an automaton that takes a series of cooperate or defect moves and, instead of classifying strings, produces outputs, where the outputs are the corresponding cooperate or defect decisions for the particular strategy.

Single Processor Implementation Results

To investigate the first hypothesis, namely that cooperation can evolve, the program kept track of the total number of cooperate-cooperate moves in each generation for 1000 generations (i.e, the number of times any two individuals in the population cooperate with one another for a single prisoner’s dilemma game in each generation.) It then averaged together these totals, by generation, over 100 trials. Results are shown in Figure 3.

Multiprocessor Implementation Results

In the aforementioned trials, each of which were run on a single processor machine, niceness stabilization did not appear until the malignment process was added to give adequate selective pressure to smart cooperators in the population. So, typically, after a few hundred generations of a trial like those featured in Figure 6, a population would reach a state of stability. However, this was not the case in all trials. Sometimes, niceness remained at zero for the entire trial and never offered any sign of stability. This could have been due to a lack of anything remotely close to niceness in the gene pool. Even despite the randomness and change introduced by mutation and the selective pressure to have a high IQ, if the population lacked the presence of even slightly cooperative individuals, then there may have been nothing present in the gene pool from which niceness could emerge. Suppose that now in a separate, but nearby population, evolution took a different path. In this nearby population, niceness does emerge and reach a state of stability as in some of the more successful trials discussed above. If a small portion of these smart cooperators could migrate into the unsuccessful population, they might provide a basis for cooperation and niceness to emerge there.

To test this hypothesis, a multiprocessing model of the genetic algorithm was used. Processes are communicated with each other through message passing in this algorithm. This procedure was implemented using a message passing library known as MPI (Quinn 2004). Each process ran a separate population. To simulate a migration from one population to another, the migration is encoded in a message. The parallel implementation was configured using a master-slave process model that can be visualized as shown in Figure 7.

Thirteen processes are used in the model. Twelve of the thirteen processes are slave processes, each one dedicated to evolving its own population of individuals with malignment. Each slave can engage in migrations with only two other processes—the neighboring processes on its left and right side. The thirteenth process was the master responsible for controlling the migration of each of the slave processes by sending commands to “do migration”. It was also capable of receiving and reporting statistics from each of the slave processes. Lastly, the master process ensured that each slave process evolved at a fairly consistent rate with the rest of the slaves by enforcing a checkpoint. In the checkpoint, each of the slaves evolves its own process until a specified checkpoint generation number is reached. Once the master knows that each slave process has reached that checkpoint, the command to continue is sent out to the slaves.

Since we are testing mainly whether or not having regular migrations between isolated populations has an effect on the emergence of niceness, two trials, each of 1000 generations, were run. First, a control trial was run in which migration had been disabled in order to determine how the processes in the parallel implementation will fare. This was then compared to a second trial in which migration was enabled. The results of the first trial are tabulated in Table 1. The niceness results for each of the twelve slave processes in our first trial with disabled migration was much like the results from the non-parallel implementation trials. For some of the processes, the conditions were right and niceness emerged. For other processes, niceness simply never emerged.

Discussion

Using the genetic algorithm, this study has shown that cooperation tends to increase from an initially random state in the iterated prisoner’s dilemma game. In this model, niceness was shown to be unstable when left alone—a population of nice but unskilled players can be taken advantage of by any defector through chance. By introducing selective pressure, effects of genetic drift upon IQ were minimized, and niceness was stabilized. In the multiple processor model, this study has shown that cooperation not only tends to increase, but that it also spreads through migration.

It would be interesting to see how results may changed by altering certain parameters that, for the length of this study, have remained constant. For example, what effects would be seen by increasing or decreasing the population size? Also, how would the automata perform if the number of states available with which to make decisions is either increased or decreased? Could the number of states be variable, and could they actually evolve as well? Most interesting, however, would be the results from an implementation that allows future opponents to take into account another player’s reputation from playing others. If players are able to have access to such information, can they use it to make better choices at the time they play with that person?