Complementarities between mathematical and computational modeling : the case of the repeated Prisoners' Dilemma

Complementarities between Mathematical and Computational Modeling: The Case of the Repeated Prisoners’ Dilemma Xavier Vilà∗ Universitat Autònoma de Barcelona Abstract We study the properties of the well known Replicator Dynamics when applied to a finitely repeated version of the Prisoners’ Dilemma game. We characterize the behavior of such dynamics under strongly simplifying assumptions (i.e. only 3 strategies are available) and show that the basin of attraction of defection shrinks as the number of repetitions increases. After discussing the difficulties involved in trying to relax the “strongly simplifying assumptions” above, we approach the same model by means of simulations based on genetic algorithms. The resulting simulations describe a behavior of the system very close to the one predicted by the replicator dynamics without imposing any of the assumptions of the mathematical model. Our main conclusion is that mathematical and computational models are good complements for research in social sciences. Indeed, while computational models are extremely useful to extend the scope of the analysis to complex scenarios hard to analyze mathematically, formal models can be useful to verify and to explain the outcomes of computational models. Keywords: Computational Economics, Model-To-Model Analysis, Genetic Algorithms, Evolutionary Game Theory, Prisoners’ Dilemma JEL-Codes: C63, C73 1 Introduction In the growing field of Agent-Based computer simulations applied to social sciences, model replication is considered a key issue. Indeed, asserting whether the observed results of a particular simulation of a model are correct or generalizable is a difficult task when no formal (i.e. mathematical) proof is provided. Only replication, comparison, alignment, and other related techniques can shed some light on the validity of simulations. See Axelrod (1997) for a methodological motivation on this and Hegselmann & Will (2008), Will (2009), and Macy & Sato (2010) for an inspirational debate. The ∗Financial support from grant ECO2008-04756 (Grupo Consolidado-C) from the Spanish Ministry of Science and Innovation and from grant SGR2009-578 of the Generalitat de Catalunya are gratefully acknowledged. Departament d’Economia i d’Història Econòmica and MOVE. Universitat Autònoma de Barcelona. [email protected] 1 2 The Mathematical Model 2 work by Izquierdo et al. (2009), for instance, shows that the alignment of computational and mathematical models can “assist researchers in understanding the dynamics of simulation models” (Izquierdo et al., 2009). Our work contains one such comparison. We put side-by-side two different analysis (mathematical and computational) of the same model: the evolution of strategies in the repeated prisoners’ dilemma. We first consider, based on Imhof et al. (2005), the case in which the evolutionary system is described by a deterministic dynamic system that uses expected values. Using strong simplifying assumptions the model can be solved, and a complete description of how the process behaves is provided. The second approach, based on Miller (1996), is a computational simulation in which finite automata are used to represent the strategies played, and a decentralized adaptive process based on the models of genetic algorithms simulates the stochastic evolutionary process. With this technique we can relax some of the strong assumptions used in the first approach and still obtain the same basic results. We like to think that the limitations of the first approach (mathematical) provide a good motivation for the second approach (Computer-Based simulations). Indeed, although both approaches address the same problem, we show that the use of computational techniques allows us to relax hypothesis and overcome the limitations of the mathematical approach. On the other hand, it is shown that the mathematical model is extremely useful in order to explain the behavior and the causality of the results of the computational model The choice of the repeated prisoners’ dilemma to conduct the experiment described above is not arbitrary. It is a well know and largely studied game, and many things about it have been learned thanks to the tools of formal game theory. But when the game is studied from an evolutionary perspective, the results are not always clear. The findings in Boyd & Lorberbaum (1987) and Binmore & Samuelson (1992), for instance, show that evolutionary stable solutions may fail to exists in many versions of the game. On the other hand, experiments and simulations like those reported in Axelrod (1985), Axelrod & Hamilton (1981), Nowak & Sigmund (1992), or Miller (1996), seem to suggest that Tit-for-tat (and other similar strategies) prevail in most scenarios. Thus, the interest of our research is putting these two approaches, mathematical and computational, side-by-side to achieve a better understanding of the evolutionary behavior of players in the repeated prisoners’ dilemma 2 The Mathematical Model The basic stage game (Prisoners’ Dilemma) that players will play repeatedly is given by C D C 3,3 0,5 D 5,0 1,1 We now consider the repeated version of the game played a finite number of rounds R.In order to have a tractable model, we only consider three possible strategies (as in Imhof et al. (2005)): 2 The Mathematical Model 3 •D: Always defect •C: Always cooperate •T: Tit-for-Tat as they are the three strategies that have deserved a higher attention in almost all the literature dealing with the Repeated Prisoner’s Dilemma from an evolutionary point of view. The fact that we only consider 3 possible strategies clearly imposes a strong restriction to the analysis, as we will discuss later. Given the above, the repeated game can be represented as follows C D T C 3R,3R0,5R3R,3R D 5R,0R,R5+(R−1),(R−1) T 3R,3R(R−1),5+(R−1)3R,3R Thus, for instance, when a D-type strategy meets a T-type strategy, the former gets 5 in the first round and then 1 in each subsequent round (5+(R−1)in total), while the later gets 0 first and then 1 in each subsequent round (R−1 in total). 2.1 The Replicator Dynamics analysis Let pt(C)be the probability that, at time t, a player in this population is an “always cooperate” type, and the same for pt(D)and pt(T). We thus have that pt(C)+ pt(D)+ pt(T) = 1∀t. The replicator dynamics states that the rate of change of such probabilities is a function of the relative performance of each strategy with respect to the average performance of the population. In this sense, given pt(C),pt(D),pt(T), the expected payoff at time tfor each strategy (Etπ(·)) is: Etπ(C) = 3Rpt(C)+0pt(D)+3Rpt(T) = 3R(P t(C)+ pt(T)) Etπ(D) = 5Rpt(C)+Rpt(D)+(5+(R−1))pt(T) Etπ(T) = 3Rpt(C)+(R−1)pt(D)+3Rpt(T) = 3R(P t(C)+ pt(T))+(R−1)pt(D) and thus the average payoff will be: Et¯ π=Etπ(C)pt(C) + Etπ(D)pt(D)+Etπ(T)pt(T) Notice that since pt(C)+ pt(D)+ pt(T) = 1∀tonly two dimensions matter. Hence, the replicator dynamics in this case is given by: ∂pt(C) ∂t=pt(C)(Etπ(C)−Et¯ π) 2 The Mathematical Model 4 ∂pt(D) ∂t=pt(D)(Etπ(D)−Et¯ π) The corresponding vector field showing the trajectories of the system is represented in Figure 1, where the points aand bgiven by a=2R−4 2R−3,b=R−2 R−1 Fig. 1: Vector Field The horizontal and vertical axis in Figure 1 correspond to pt(C)and pt(D)respectively. Thus, the three vertexes of the triangle ((1,0),(0,1),and(0.0)), correspond to the states pt(C) = 1,pt(D) = 1,and pt(T) = 1 respectively. The trajectories that represent the evolution of the system are divided in two areas or basins of attraction, one for Defection and another for Cooperation. Thus, depending on the location in the simplex of the initial probabilities at t=0, (p0(C),p0(D)), the system will evolve according to the corresponding path towards defection (the vertex (0,1)) or cooperation (somewhere along the line (0,0)→(1,0)). It is clear that the basin of attraction of cooperation grows as Rbecomes large. Indeed, we have that a→1 and b→1 as R→∞ Stationary points (rest points) of the system are marked red: 2 The Mathematical Model 5 •(0,1), that corresponds to everybody playing always defect pt(D) = 1, •(0,a), which is a singular point, •all the points in the line that goes from (0,0)to (1,0)that correspond to points with no defectants, that is, pt(D) = 0 and pt(C)+ pt(T) = 1. Notice that only the point (0,1)corresponding to pt(D) = 1 is asymptotically stable in the sense that if the system is slightly perturbed away from (0,1),any trajectory will bring it back to the same point. The singular point (0,a), which is not asymptotically stable, can only be reached if the system starts somewhere in the line that goes from (0,a)to (b,0),which occurs with zero probability. Finally, points in the line (0,0)→ (1,0)are stationary but not stable. An important result is that the relative size of these basins of attraction depends on the number of repetition R.That is, if the system starts at random, the probability of reaching the point (0,1)(p(0,1), everybody defecting) or the line (0,0)→(1,0) (p((0,0)→(1,0)), everybody cooperating) depends on R. p((0,0)→(1,0)) = (2R−4 2R−3)(R−2 R−1) p(0,1) = 1−(2R−4 2R−3)(R−2 R−1) Thus, we can compute the expected per-round payoff (E¯ π) as a function of R. E¯ π= (2R−4 2R−3)(R−2 R−1)·3+(1−(2R−4 2R−3)(R−2 R−1))·1 Figure 2 shows the behavior of such expected per-round payoff as a function of R. We observe that it grows rapidly as the number of repetitions (R) increases. In fact, E¯ π→3 as R→∞ 3 The Computational Model 6 Fig. 2: Expected Payoff as a function of R 3 The Computational Model Given the analysis above, the dynamics seem to suggest that there is room for cooperation. At least for a broad range of initial conditions, the trajectories lead to some point in the horizontal axis corresponding to a population consisting of only C and T strategies. Nevertheless, such analysis is extremely partial since we are only considering 3 strategies at a time, namelyC,D, and T. One can easily see that extending this approach (mathematical) to a more general case (with more strategies considered) is a difficult task as it would be extremely difficult to study the behavior of a dynamic system with more than 2 dimension To overcome this limitation, we develop a computer simulation1in which the strategies are represented by finite automata of size four (encoded as binary strings of 0’s and 1’s) and a Genetic Algorithm routine is used to simulate the evolutionary process as in Miller (1996). The algorithm was run for 5000 generations starting from an initial random population of 100 strategies using the standard single-cut crossover operator and with a probability of per-bit mutation of 0.005. In most of the cases, the results of such simulations produce the outcome in Figure 3, in which the evolution of the (per round) average payoff is displayed. 1The software used for this simulation consists of a set of routines written in ANSI C. It is available from http://ideas.repec.org/c/aub/grecss/001.05.html 3 The Computational Model 7 Fig. 3: Evolution of the average per-round payoff when Cooperation is the result Because the final average payoff is 3 we can conclude that all players follow a cooperative strategy. In other cases, though, cooperation is not the final result as the evolution of the average payoff results as in Figure 4, which corresponds to the case of all the players defecting. 3 The Computational Model 8 Fig. 4: Evolution of the average per-round payoff when Defection is the result In both cases, though, the resemblance between the vector field in Figure 1 and the evolution of payoffs in Figures 3 and 4 is very appealing: •When the final result is cooperation (as in Figure 3), both in the replicator dynamic analysis and in the simulations, the evolutionary process seems to favor the growth of Defectant strategies at first, and then these disappear and Cooperative strategies start to replicate to end up with the payoff corresponding to the cooperative behavior. •On the contrary, when the final result is defection (as in Figure 4),the evolution goes “monotonically” towards that point. How often each of these two results occurs in the simulations ? Given that in the mathematical model we have found that the answer to this question depends upon the number of repetitions R, we check whether Ralso has an effect in the computational model. In this sense, Figure 5 complements Figure 2 by showing how the final observed average payoff of the simulations2(the payoff of generation 5000) depends on R. For robustness, we perform such exercise with two different crossover rules (the “canonical” single-cut crossover and a fifty-fifty crossover3) and with no crossover 2For each value of Rwe run 1000 simulations and compute the average payoff of the last generation (5000) 3Fifty-fifty crossover consists of generating new binary strings in such a way that each “locus” of the new string has 0.5 probability of being a copy of the corresponding locus of the “father” string and 0.5 probability of that of the “mather’s” string 4 Conclusions 9 Fig. 5: Expected and observed payoffs as a function of R Figure 5 shows to what extent the behavior of the simulations (curves marked “x” and “*”) resembles what we obtained mathematically in the previous section (“Theoretical” curve). We observe that, as the number of repetitions Rgrows, the higher is the probability of reaching cooperation at the end and hence, the higher is the average payoff, both theoretical and empirically. In this sense, it seems that the use of Genetic Algorithms to simulate the evolutionary process closely matches the behavior predicted by the replicator dynamics while avoiding the strong limitation of considering only 3 possible strategies. To test “how close” these results (mathematical and computational) are, Figures 6 and 7 show how statistically significant is the hypothesis that the mean of the average payoffs of the computational model equals the theoretical expected payoff of the mathematical model. To this purpose the dotted line corresponds to the lower end of a 95% confidence interval We observe that, specially in the case of the “canonical” single-cut crossover and except for a few atypical observations, the results are significantly close. 4 Conclusions We have studied the evolution of strategies in the well known Repeated Prisoner’s Dilemma using two different approaches: one mathematical based on the replicator dynamics and one computational based on genetic algorithms. We show that the results obtained from the two approaches coincide to a great extent in the sense that,