Resolving the iterated prisoner's dilemma: theory and reality

Pairs of unrelated individuals face a prisoner's dilemma if cooperation is the best mutual outcome, but each player does best to defect regardless of his partner's behaviour. Although mutual defection is the only evolutionarily stable strategy in one-shot games, cooperative solutions based on reciprocity can emerge in iterated games. Among the most prominent theoretical solutions are the so-called bookkeeping strategies, such as tit-for-tat, where individuals copy their partner's behaviour in the previous round. However, the lack of empirical data conforming to predicted strategies has prompted the suggestion that the iterated prisoner's dilemma (IPD) is neither a useful nor realistic basis for investigating cooperation. Here, we discuss several recent studies where authors have used the IPD framework to interpret their data. We evaluate the validity of their approach and highlight the diversity of proposed solutions. Strategies based on precise accounting are relatively uncommon, perhaps because the full set of assumptions of the IPD model are rarely satisfied. Instead, animals use a diverse array of strategies that apparently promote cooperation, despite the temptation to cheat. These include both positive and negative reciprocity, as well as long-term mutual investments based on 'friendships'. Although there are various gaps in these studies that remain to be filled, we argue that in most cases, individuals could theoretically benefit from cheating and that cooperation cannot therefore be explained with the concept of positive pseudo-reciprocity. We suggest that by incorporating empirical data into the theoretical framework, we may gain fundamental new insights into the evolution of mutual reciprocal investment in nature.     

The evolution of reciprocity in sizable groups

Recently, several authors have investigated the evolution of reciprocal altruism using the repeated prisoner's dilemma game. These models suggest that natural selection is likely to favor behavioral strategies leading to reciprocal cooperation when pairs of individuals interact repeatedly in potentially cooperative situations. Using the repeated n-person prisoner's dilemma game, we consider whether reciprocal altruism is also likely to evolve when social interactions involve more individuals. We show that the conditions that allow the evolution of reciprocal cooperation become extremely restrictive as group size increases.     

Beyond the prisoner's dilemma: Toward models to discriminate among mechanisms of cooperation in nature

The iterated prisoner's dilemma game, or IPD, has now established itself as the orthodox paradigm for theoretical investigations of the evolution of cooperation; but its scope is restricted to reciprocity, which is only one of three categories of cooperation among unrelated individuals. Even within that category, a cooperative encounter has in general three phases, and the IPD has nothing to say about two of them. To distinguish among mechanisms of cooperation in nature, future theoretical work on the evolution of cooperation must distance itself from economics and develop games as a refinement of ethology's comparative approach.     

Friendship, cliquishness, and the emergence of cooperation

The evolution of cooperation is a central problem in biology and the social sciences. While theoretical work using the iterated prisoner's dilemma (IPD) has shown that cooperation among non-kin can be sustained among reciprocal strategies (i.e. tit-for-tat), these results are sensitive to errors in strategy execution, cyclical invasions by free riders, and the specific ecology of strategies. Moreover, the IPD assumes that a strategy's probability of playing the PD game with other individuals is independent of the decisions made by others. Here, we remove the assumption of independent pairing by studying a more plausible cooperative dilemma in which players can preferentially interact with a limited set of known partners and also deploy longer-term accounting strategies that can counteract the effects of random errors. We show that cooperative strategies readily emerge and persist in a range of noisy environments, with successful cooperative strategies (henceforth, cliquers) maintaining medium-term memories for partners and low thresholds for acceptable cooperation (i.e. forgiveness). The success of these strategies relies on their cliquishness-a propensity to defect with strangers if they already have an adequate number of partners. Notably, this combination of medium-term accounting, forgiveness, and cliquishness fits with empirical studies of friendship and other long-term relationships among humans.     

Human cooperation in social dilemmas: comparing the Snowdrift game with the Prisoner's Dilemma

Explaining the evolution of cooperation among non-relatives is one of the major challenges for evolutionary biology. In this study, we experimentally examined human cooperation in the iterated Snowdrift game (ISD), which has received little attention so far, and compared it with human cooperation in the iterated Prisoner's Dilemma (IPD), which has become the paradigm for the evolution of cooperation. We show that iteration in the ISD leads to consistently higher levels of cooperation than in the IPD. We further demonstrate that the most successful strategies known for the IPD (generous Tit-for-Tat and Pavlov) were also successfully used in the ISD. Interestingly, we found that female players cooperated significantly more often than male players in the IPD but not in the ISD. Moreover, female players in the IPD applied Tit-for-Tat-like or Pavlovian strategies significantly more often than male players, thereby achieving significantly higher pay-offs than male players did. These data demonstrate that the willingness to cooperate does not only depend on the type of the social dilemma, but also on the class of individuals involved. Altogether, our study shows that the ISD can potentially explain high levels of cooperation among non-relatives in humans. In addition, the ISD seems to reflect the social dilemma more realistically than the IPD because individuals obtain immediate direct benefits from the cooperative acts they perform and costs of cooperation are shared between cooperators.     

Maintenance affects the stability of a two-tiered microbial 'food chain'?

Recent studies have shown that constraints on available resources may play an important role in the evolution of cooperation, especially when individuals do not posses the capacity to recognize other individuals, memory or other developed abilities, as it is the case of most unicellular organisms, algae or even plants. We analyze the evolution of cooperation in the case of a limiting resource, which is necessary for reproduction and survival. We show that, if the strategies determine a prisoner's dilemma, the outcome of the interactions may be modified by the limitation of resources allowing cooperators to invade the entire population. Analytic expressions for the region of cooperation are provided. Furthermore we derive expressions for the connection between fitness, as understood in evolutionary game theory, and resource exchanges, which may be of help to link evolutionary game theoretical results with resource based models.     

Simple adaptive strategy wins the prisoner's dilemma

The prisoner's dilemma has become the leading paradigm to explain the evolution of cooperation among selfish individuals. Here, we present an adaptive strategy that implements new mechanisms to process information about past encounters. The history of moves is summarized in an internal state which then determines the subsequent move. This enables the strategy to adjust its decisions to the character of the current opponent and to adapt the most promising strategic behavior. For this reason, we call such strategies Adaptor. Through evolutionary simulations, we demonstrate that the concept of Adaptor leads to strategic patterns that are (a) highly cooperative when playing against kin, (b) stable in a sense that goes far beyond the concept of evolutionary stability, (c) robust to environmental changes, i.e. variations of the parameter values and finally (d) superior in performance to the most prominent strategies in the literature.     

Evolutionary dynamics of the continuous iterated prisoner's dilemma

The iterated prisoner's dilemma (IPD) has been widely used in the biological and social sciences to model dyadic cooperation. While most of this work has focused on the discrete prisoner's dilemma, in which actors choose between cooperation and defection, there has been some analysis of the continuous IPD, in which actors can choose any level of cooperation from zero to one. Here, we analyse a model of the continuous IPD with a limited strategy set, and show that a generous strategy achieves the maximum possible payoff against its own type. While this strategy is stable in a neighborhood of the equilibrium point, the equilibrium point itself is always vulnerable to invasion by uncooperative strategies, and hence subject to eventual destabilization. The presence of noise or errors has no effect on this result. Instead, generosity is favored because of its role in increasing contributions to the most efficient level, rather than in counteracting the corrosiveness of noise. Computer simulation using a single-locus infinite alleles Gaussian mutation model suggest that outcomes ranging from a stable cooperative polymorphism to complete collapse of cooperation are possible depending on the magnitude of the mutational variance. Also, making the cost of helping a convex function of the amount of help provided makes it more difficult for cooperative strategies to invade a non-cooperative equilibrium, and for the cooperative equilibrium to resist destabilization by non-cooperative strategies. Finally, we demonstrate that a much greater degree of assortment is required to destabilize a non-cooperative equilibrium in the continuous IPD than in the discrete IPD. The continuous model outlined here suggests that incremental amounts of cooperation lead to rapid decay of cooperation and thus even a large degree of assortment will not be sufficient to allow cooperation to increase when cooperators are rare. The extreme degree of assortment required to destabilize the non-cooperative equilibrium, as well as the instability of the cooperative equilibrium, may help explain why cooperation in Prisoner's Dilemmas is so rare in nature.     

Whence tit-for-tat?

Summary In theoretical and empirical studies of the evolution of cooperation, the tit-for-tat strategy (i.e. cooperate unless your partner did not cooperate in the previous interaction) is widely considered to be of central importance. Nevertheless, surprisingly little is known about the conditions in which tit-for-tat appears and disappears across generations in a population of interacting individuals. Here, we apply a newly developed classifier-system model (EvA) in addressing this issue when the key features of interactions are caricatured using the iterated prisoner's dilemma game. Our simple representation of behavioural strategies as algorithms composed of two interacting rules allowed us to determine conditions in which tit-for-tat can replace noncooperative strategies and vice versa. Using direct game-theoretic analysis and simulations with the EvA model, we determined that no strategy is evolutionarily stable, but larger population sizes and longer sequences of interactions between individuals can yield transient dominance by tit-for-tat. Genetic drift among behaviourally equivalent strategies is the key mechanism underlying this dominance. Our analysis suggests that tit-for-tat could be important in nature for cognitively simple organisms of limited memory capacity, in strongly kin-selected or group-selected populations, when interaction sequences between individuals are relatively short, in moderate-sized populations of widely interacting individuals and when defectors appear in the population with moderate frequency.     

Spatial effects in social dilemmas

Social dilemmas and the evolutionary conundrum of cooperation are traditionally studied through various kinds of game theoretical models such as the prisoner's dilemma, public goods games, snowdrift games or by-product mutualism. All of them exemplify situations which are characterized by different degrees of conflicting interests between the individuals and the community. In groups of interacting individuals, cooperators produce a common good benefitting the entire group at some cost to themselves, whereas defectors attempt to exploit the resource by avoiding the costly contributions. Based on synergistic or discounted accumulation of cooperative benefits a unifying theoretical framework was recently introduced that encompasses all games that have traditionally been studied separately (Hauert, Michor, Nowak, Doebeli, 2005. Synergy and discounting of cooperation in social dilemmas. J. Theor. Biol., in press.). Within this framework we investigate the effects of spatial structure with limited local interactions on the evolutionary fate of cooperators and defectors. The quantitative effects of space turn out to be quite sensitive to the underlying microscopic update mechanisms but, more general, we demonstrate that in prisoner's dilemma type interactions spatial structure benefits cooperation-although the parameter range is quite limited-whereas in snowdrift type interactions spatial structure may be beneficial too, but often turns out to be detrimental to cooperation.     

Invasion and expansion of cooperators in lattice populations: Prisoner's dilemma vs. snowdrift games

The evolution of cooperation is an enduring conundrum in biology and the social sciences. Two social dilemmas, the prisoner's dilemma and the snowdrift game have emerged as the most promising mathematical metaphors to study cooperation. Spatial structure with limited local interactions has long been identified as a potent promoter of cooperation in the prisoner's dilemma but in the spatial snowdrift game, space may actually enhance or inhibit cooperation. Here we investigate and link the microscopic interaction between individuals to the characteristics of the emerging macroscopic patterns generated by the spatial invasion process of cooperators in a world of defectors. In our simulations, individuals are located on a square lattice with Moore neighborhood and update their strategies by probabilistically imitating the strategies of better performing neighbors. Under sufficiently benign conditions, cooperators can survive in both games. After rapid local equilibration, cooperators expand quadratically until global saturation is reached. Under favorable conditions, cooperators expand as a large contiguous cluster in both games with minor differences concerning the shape of embedded defectors. Under less favorable conditions, however, distinct differences arise. In the prisoner's dilemma, cooperators break up into isolated, compact clusters. The compact clustering reduces exploitation and leads to positive assortment, such that cooperators interact more frequently with other cooperators than with defectors. In contrast, in the snowdrift game, cooperators form small, dendritic clusters, which results in negative assortment and cooperators interact more frequently with defectors than with other cooperators. In order to characterize and quantify the emerging spatial patterns, we introduce a measure for the cluster shape and demonstrate that the macroscopic patterns can be used to determine the characteristics of the underlying microscopic interactions.     

Revisiting “The Evolution of Reciprocity in Sizable Groups”: Continuous reciprocity in the repeated n-person prisoner's dilemma

For many years in evolutionary science, the consensus view has been that while reciprocal altruism can evolve in dyadic interactions, it is unlikely to evolve in sizable groups. This view had been based on studies which have assumed cooperation to be discrete rather than continuous (i.e., individuals can either fully cooperate or else fully defect, but they cannot continuously vary their level of cooperation). In real world cooperation, however, cooperation is often continuous. In this paper, we re-examine the evolution of reciprocity in sizable groups by presenting a model of the n-person prisoner's dilemma that assumes continuous rather than discrete cooperation. This model shows that continuous reciprocity has a dramatically wider basin of attraction than discrete reciprocity, and that this basin's size increases with efficiency of cooperation (marginal per capita return). Further, we find that assortative interaction interacts synergistically with continuous reciprocity to a much greater extent than it does with discrete reciprocity. These results suggest that previous models may have underestimated reciprocity's adaptiveness in groups. However, we also find that the invasion of continuous reciprocators into a population of unconditional defectors becomes realistic only within a narrow parameter space in which the efficiency of cooperation is close to its maximum bound. Therefore our model suggests that continuous reciprocity can evolve in large groups more easily than discrete reciprocity only under unusual circumstances.     

The structure of mutations and the evolution of cooperation

Evolutionary game dynamics in finite populations assumes that all mutations are equally likely, i.e., if there are n strategies a single mutation can result in any strategy with probability 1/n. However, in biological systems it seems natural that not all mutations can arise from a given state. Certain mutations may be far away, or even be unreachable given the current composition of an evolving population. These distances between strategies (or genotypes) define a topology of mutations that so far has been neglected in evolutionary game theory. In this paper we re-evaluate classic results in the evolution of cooperation departing from the assumption of uniform mutations. We examine two cases: the evolution of reciprocal strategies in a repeated prisoner's dilemma, and the evolution of altruistic punishment in a public goods game. In both cases, alternative but reasonable mutation kernels shift known results in the direction of less cooperation. We therefore show that assuming uniform mutations has a substantial impact on the fate of an evolving population. Our results call for a reassessment of the "model-less" approach to mutations in evolutionary dynamics.     

Bipartite graphs as models of population structures in evolutionary multiplayer games

By combining evolutionary game theory and graph theory, "games on graphs" study the evolutionary dynamics of frequency-dependent selection in population structures modeled as geographical or social networks. Networks are usually represented by means of unipartite graphs, and social interactions by two-person games such as the famous prisoner's dilemma. Unipartite graphs have also been used for modeling interactions going beyond pairwise interactions. In this paper, we argue that bipartite graphs are a better alternative to unipartite graphs for describing population structures in evolutionary multiplayer games. To illustrate this point, we make use of bipartite graphs to investigate, by means of computer simulations, the evolution of cooperation under the conventional and the distributed N-person prisoner's dilemma. We show that several implicit assumptions arising from the standard approach based on unipartite graphs (such as the definition of replacement neighborhoods, the intertwining of individual and group diversity, and the large overlap of interaction neighborhoods) can have a large impact on the resulting evolutionary dynamics. Our work provides a clear example of the importance of construction procedures in games on graphs, of the suitability of bigraphs and hypergraphs for computational modeling, and of the importance of concepts from social network analysis such as centrality, centralization and bipartite clustering for the understanding of dynamical processes occurring on networked population structures.     

Complex transition to cooperative behavior in a structured population model

Cooperation plays an important role in the evolution of species and human societies. The understanding of the emergence and persistence of cooperation in those systems is a fascinating and fundamental question. Many mechanisms were extensively studied and proposed as supporting cooperation. The current work addresses the role of migration for the maintenance of cooperation in structured populations. This problem is investigated in an evolutionary perspective through the prisoner's dilemma game paradigm. It is found that migration and structure play an essential role in the evolution of the cooperative behavior. The possible outcomes of the model are extinction of the entire population, dominance of the cooperative strategy and coexistence between cooperators and defectors. The coexistence phase is obtained in the range of large migration rates. It is also verified the existence of a critical level of structuring beyond that cooperation is always likely. In resume, we conclude that the increase in the number of demes as well as in the migration rate favor the fixation of the cooperative behavior.     

Eco-evolutionary feedback and the invasion of cooperation in prisoner's dilemma games

Unveiling the origin and forms of cooperation in nature poses profound challenges in evolutionary ecology. The prisoner's dilemma game is an important metaphor for studying the evolution of cooperation. We here classified potential mechanisms for cooperation evolution into schemes of frequency- and density-dependent selection, and focused on the density-dependent selection in the ecological prisoner's dilemma games. We found that, although assortative encounter is still the necessary condition in ecological games for cooperation evolution, a harsh environment, indicated by a high mortality, can foster the invasion of cooperation. The Hamilton rule provides a fundamental condition for the evolution of cooperation by ensuring an enhanced relatedness between players in low-density populations. Incorporating ecological dynamics into evolutionary games opens up a much wider window for the evolution of cooperation, and exhibits a variety of complex behaviors of dynamics, such as limit and heteroclinic cycles. An alternative evolutionary, or rather succession, sequence was proposed that cooperation first appears in harsh environments, followed by the invasion of defection, which leads to a common catastrophe. The rise of cooperation (and altruism), thus, could be much easier in the density-dependent ecological games than in the classic frequency-dependent evolutionary games.     

Critical dynamics in the evolution of stochastic strategies for the iterated prisoner's dilemma

The observed cooperation on the level of genes, cells, tissues, and individuals has been the object of intense study by evolutionary biologists, mainly because cooperation often flourishes in biological systems in apparent contradiction to the selfish goal of survival inherent in Darwinian evolution. In order to resolve this paradox, evolutionary game theory has focused on the Prisoner's Dilemma (PD), which incorporates the essence of this conflict. Here, we encode strategies for the iterated Prisoner's Dilemma (IPD) in terms of conditional probabilities that represent the response of decision pathways given previous plays. We find that if these stochastic strategies are encoded as genes that undergo Darwinian evolution, the environmental conditions that the strategies are adapting to determine the fixed point of the evolutionary trajectory, which could be either cooperation or defection. A transition between cooperative and defective attractors occurs as a function of different parameters such as mutation rate, replacement rate, and memory, all of which affect a player's ability to predict an opponent's behavior. These results imply that in populations of players that can use previous decisions to plan future ones, cooperation depends critically on whether the players can rely on facing the same strategies that they have adapted to. Defection, on the other hand, is the optimal adaptive response in environments that change so quickly that the information gathered from previous plays cannot usefully be integrated for a response.     

The economic basis of cooperation: tradeoffs between selfishness and generosity

The current study examined the economics of cooperation in controlled-payoffgames by using captive blue jays, Cyanocitta cristata. Thisinvestigation used a special feeding apparatus to test for thestability of cooperative choice in a series of iterated games.The jays experienced experimentally determined game theoreticalpayoff matrices, which determined the distribution of food tothemselves and their opponent, depending on their decision tocooperate or defect. The experiment tested four game matrices,called the cooperate only, defect only, prisoner's dilemma,and opponent control treatments. This study found little cooperationin the defect only and prisoner's dilemma treatments. Cooperationoccurred significantly more often in the opponent control treatment.These findings suggest that the jays attend to short-term consequences;they do not cooperate in the absence of an immediate benefit(defect only), even if a long-term benefit may exist (prisoner'sdilemma). The opponent control treatment suggests that cooperationcan occur when an individual's benefits depend completely onthe actions of others; therefore, generosity is cheap. Thisstudy, therefore, agrees with recent studies in proposing alternativemodels of cooperation.     

Resolution of the stochastic strategy spatial prisoner's dilemma by means of particle swarm optimization

We study the evolution of cooperation among selfish individuals in the stochastic strategy spatial prisoner's dilemma game. We equip players with the particle swarm optimization technique, and find that it may lead to highly cooperative states even if the temptations to defect are strong. The concept of particle swarm optimization was originally introduced within a simple model of social dynamics that can describe the formation of a swarm, i.e., analogous to a swarm of bees searching for a food source. Essentially, particle swarm optimization foresees changes in the velocity profile of each player, such that the best locations are targeted and eventually occupied. In our case, each player keeps track of the highest payoff attained within a local topological neighborhood and its individual highest payoff. Thus, players make use of their own memory that keeps score of the most profitable strategy in previous actions, as well as use of the knowledge gained by the swarm as a whole, to find the best available strategy for themselves and the society. Following extensive simulations of this setup, we find a significant increase in the level of cooperation for a wide range of parameters, and also a full resolution of the prisoner's dilemma. We also demonstrate extreme efficiency of the optimization algorithm when dealing with environments that strongly favor the proliferation of defection, which in turn suggests that swarming could be an important phenomenon by means of which cooperation can be sustained even under highly unfavorable conditions. We thus present an alternative way of understanding the evolution of cooperative behavior and its ubiquitous presence in nature, and we hope that this study will be inspirational for future efforts aimed in this direction.     

Optimality under noise: higher memory strategies for the alternating prisoner's dilemma.

The Alternating Prisoner's Dilemma is a variant of the iterated Prisoner's Dilemma in which the players alternate in the roles of actor and recipient. We searched for strategies which are "optimal" in the Alternating Prisoner's Dilemma with noise (a non-zero probability that a player's decision will be transmitted incorrectly). In order to achieve success against a variety of other strategies, a strategy must be "self-cooperating" (able to achieve mutual cooperation with its clone), "C-exploiting" (able to exploit unconditional cooperators), and "D-unexploitable" (able to resist exploitation by defectors). It must also have high evolutionary "dominance", a general measure of evolutionary performance which considers both resistance to invasion and the ability to invade other strategies. A strategy which meets these optimality criteria can evolve cooperation by invading a population of defectors and establishing a stable cooperative society. Most of the strategies commonly discussed in the Alternating Prisoner's Dilemma literature are low-memory strategies such as Tit For Tat, Pavlov, and Firm But Fair, but none of these strategies can simultaneously meet all of the optimality criteria. However, we discovered a class of higher memory "Firm Pavlov" strategies, which not only meet our stringent optimality criteria, but also achieve remarkable success in round-robin tournaments and evolutionary interactions. These higher memory strategies are friendly enough to cooperate with their clone, pragmatic enough to exploit unconditional cooperators, and wary enough to resist exploitation by defectors: they are truly "optimal under noise" in the Alternating Prisoner's Dilemma.