Games on Grids

Abstract: The structure of interaction plays an important role in the outcome of evolutionary games. This study investigates the evolution of stochastic strategies of the prisoner's dilemma played on structures ranging from lattices to small world networks. Strategies and payoffs are analyzed as a function of the network characteristics of the node they are playing on. Nodes with lattice-like neighborhoods tend to perform better than the nodes modified during the rewiring process of the construction of the small-world network.

Abstract: A laboratory experiment has been designed to study coordination and cooperation in games played on local, random and small-world networks. For the coordination game, the results revealed a tendency for coordination on the payoff-dominant equilibrium in all three networks, but the frequency of payoff-dominant choices was significantly higher in small-world networks than in local and random networks. For the prisoner's dilemma game, cooperation was hard to reach on all three networks, with average cooperation lower in small-world networks than in random and local networks. Two graph-theoretic characteristics—clustering coefficient and characteristic path length—exhibited a significant effect on individual behavior, possibly explaining why the small-world network, with its high clustering coefficient and short path length, is the architecture of relations that drive a system towards equilibrium at the quickest pace.

Abstract: 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.

(M. Smith 95) All major transitions in evolution can be reduced to successful resolutions of social dilemmas under Darwinian selection

(Moran 62) process: a focal individual is randomly chosen for reproduction with a probability proportional to its fitness. Another randomly chosen is eliminated and replaced by an offspring of the focal individual. perhaps also choose based on fitness?

(Otsuki 05) process: like Moran but assuming a death-birth instead of a birth-death process.

Spatial structure enables cooperators to thrive by forming clusters and thereby reducing exploitation by defectors.

Each additional benefit may be discounted or synergistically enhanced by a factor w. [Forçando a barra para a cooperação? : Verificar no artigo]

But what of the creatures, such as many invertebrates, that seem to exhibit forms of reciprocal cooperation, even though they often cannot recognize individual players or remember their actions? Or what if future payoffs are heavily discounted? How can altruistic arrangements be established and maintained in these circumstances? One possible solution is that these players find a fixed set of fellow contestants and make sure the game is played largely with them. In general, this selectivity will be hard to attain. But there is one circumstance in which it is not only easy, it is automatic. If the players occupy fixed sites, and if they interact only with close neighbours, there will be no need to recognize and remember, because the other players are fixed by the geometry. Whereas in many of our simulations players always encounter a representative sample of the population, we have also looked specifically at scenarios in which every player interacts only with a few neighbours on a two-dimensional grid. Such “spatial games” are very recent. They give an altogether new twist to the Prisoner's Dilemma.

Abstract: The prisoner’s dilemma (PD) deals with the behavior conflict between two agents, who can either cooperate (cooperators) or defect. If both agents cooperate (defect), they have a unitary (null) payoff. Otherwise the payoff is T for the defector and null for the cooperator. The temptation T to defect is the only free parameter in the model. Here the agents are represented by the cells of a LxL lattice. The agent behaviors are initially randomly distributed according to an initial proportion of cooperators Pc(0). Each agent has no memory of previous behaviors and plays the PD with his/her eight nearest neighbors. At each generation, the considered agent copies the behavior of those who have secured the highest payoff. Once the PD conflict has been established (1<T<2), this system shows that cooperation among agents may emerge even for reasonably high T values giving rise to the well-known strategy: join to conquer, fight to share. Contrary to previous studies, in which the lattice cells are viewed as groups and are allowed to self-interact (inter-group situation), here the cells are viewed as individuals and are not allowed to self-interact (intra-group situation). Although the short time and asymptotic behavior of Pc are similar in both cases, the intermediate behavior is different. Oscillations in the intra-group Pc(t) forbids data collapse. The cooperators clusters geometrical configurations are distinct between inter and intra-group models, which explains the Pc(t) differences.

Abstract: The effect of heterogeneous infuence of different individuals on the maintenance of co-operative behaviour is studied in an evolutionary Prisoner's Dilemma game with players located on the sites of regular small-world networks. The players interacting with their neighbours can either co-operate or defect and update their states by choosing one of the neighbours and adopting its strategy with a probability depending on the payoff difference. The selection of the neighbour obeys a preferential rule: the more influential a neighbour, the larger the probability it is picked. It is found that this simple preferential selection rule can promote continuously the co-operation of the whole population with the strengthening of the disorder of the underlying network.

Abstract: A modified prisoner’s dilemma game is numerically investigated on disordered square lattices characterized by a fi portion of random rewired links with four fixed number of neighbors of each site. The players interacting with their neighbors can either cooperate or defect and update their states by choosing one of the neighboring and adopting its strategy with a probability depending on the payoff difference. The selection of the neighbor obeys a dynamic preferential rule: the more frequency a neighbor’s strategy was adopted in the previous rounds, the larger probability it was picked. It is found that this simple rule can promote greatly the cooperation of the whole population with disordered spatial distribution. Dynamic preferential selection are necessary to describe evolution of a society whose actions may be affected by the results of former actions of the individuals in the society. Thus introducing such selection rule helps to model dynamic aspects of societies.

Abstract: We study evolutionary games on graphs. Each player is represented by a vertex of the graph. The edges denote who meets whom. A player can use any one of n strategies. Players obtain a payoff from interaction with all their immediate neighbors. We consider three different update rules, called ‘birth–death’, ‘death–birth’ and ‘imitation’. A fourth update rule, ‘pairwise comparison’, is shown to be equivalent to birth–death updating in our model. We use pair approximation to describe the evolutionary game dynamics on regular graphs of degree k. In the limit of weak selection, we can derive a differential equation which describes how the average frequency of each strategy on the graph changes over time. Remarkably, this equation is a replicator equation with a transformed payoff matrix. Therefore, moving a game from a well-mixed population (the complete graph) onto a regular graph simply results in a transformation of the payoff matrix. The new payoff matrix is the sum of the original payoff matrix plus another matrix, which describes the local competition of strategies. We discuss the application of our theory to four particular examples, the Prisoner’s Dilemma, the Snow-Drift game, a coordination game and the Rock–Scissors–Paper game.

Bij (the transformation in the payoff matrix) can be calculated because there is a fixed neighbourhood size for all the graph. This work generalizes some works presented in the literature, including Hauert and Doebeli Spatial structure often inhibits the evolution of cooperation in the snowrift game (Nature)

Abstract: To investigate the genotype–phenotype link in a polyclonal cancer cell population, here we introduce evolutionary game theory into our previously developed agent-based brain tumor model. We model the heterogeneous cell population as a mixture of two distinct genotypes: the more proliferative Type A and the more migratory Type B. Our agent-based simulations reveal a phase transition in the tumor’s velocity of spatial expansion linking the tumor fitness to genotypic composition. Specifically, velocity initially falls as rising payoffs reward the interactions among the more stationary Type A cells, but unexpectedly accelerates again when these A–A payoffs increase even further. At this latter accelerating stage, fewer migratory Type B cells appear to confer a competitive advantage in terms of the tumor’s spatial aggression over the overall numerically dominating Type A cells, which in turn leads to an acceleration of the overall tumor dynamics while its surface roughness declines. We discuss potential implications of our findings for cancer research.

Heterogenous cell population as a mixture of two distinct genotypes: the more proliferative (A) and the more migratory (B)

Cells can perform one of these actions: proliferate, invade, or turn quiescent. Both proliferation and migration occur within the same time scale. Cells that do not proliferate or migrate automatically enter a reversible, quiescent state.

At any given time, a lattice site can be either empty or occupied by at most one single tumor cell.

There are two nutrient sources (representing e.g. cerebral blood vessels) at the grid center and in the middle of the northeast quadrant.

Cells that do not proliferate or migrate automatically enter a reversible, quiescent state.

Abstract: We consider the prisoner’s dilemma being played repeatedly on a dynamic network, where agents may choose their actions as well as their co-players. In the course of the evolution of the system, agents act fully rationally and base their decisions only on local information. Individual decisions are made such that links to defecting agents are resolved and that cooperating agents build up links, as new interrelations are established via a process of recommendation. The dynamics introduced thereby leads to periods of growing cooperation and growing total linkage, as well as to periods of increasing defection and decreasing total linkage, quickly following each other if the players are perfectly synchronized. The cyclical behavior is lost and the system is stabilized when agents react ’slower’ to new information. Our results show, that within a fully rational setting in a licentious society, the prisoner’s dilemma leads to overall cooperation and thus loses much of its fatality when a larger range of dynamics of social interaction is taken into account. We also comment on the emergent network structures.

Abstract: We study an evolutionary version of the spatial prisoner’s dilemma game (SPD), where the agents are placed in a random graph. For graphs with fixed connectivity, alpha, we show that for low values of alpha the final density of cooperating agents, Pc depends on the initial conditions. However, if the graphs have large connectivities Pc is independent of the initial conditions. We characterize the phase diagram of the system, using both, extensive numerical simulations and analytical computations. It is shown that two well defined behaviors are present: a Nash equilibrium, where the final density of cooperating agents Pc is constant, and a non-stationary region, where Pc fluctuates in time. Moreover, we study the SPD in Poisson random graphs and find that the phase diagram previously developed looses its meaning. In fact, only one regime may be defined. This regime is characterized by a non stationary final state where the density of cooperating agents varies in time.

Search for models able to account for the complex behaviour in many biological, economical and social systema has lead to an intense research activity in the last years.

Players on nodes playing Prisioner's dilemma against their neighbours. Random Graph 1: Bethe Lattice, sites with fixed and equal number alpha of neighbors. RG 2: Poisson random graph, links distributed with a mean value alpha.

The evolution of cooperation depends on the connectivity and on the game payoff, but it is independent of the initial conditions. Poisson random graphs lead to more cooperation then with graphs of fixed degree.

Abstract: An evolutionary prisoner’s dilemma (PD) game is studied with players located on a hierarchical structure of layered square lattices. The players can follow two strategies D (defector) and C (cooperator) and their income comes from PD games with the “neighbors.” The adoption of one of the neighboring strategies is allowed with a probability dependent on the payoff difference. Monte Carlo simulations are performed to study how the measure of cooperation is affected by the number of hierarchical levels Q and by the temptation to defect. According to the simulations the highest frequency of cooperation can be observed at the top level if the number of hierarchical levels is low. For larger Q, however, the highest frequency of cooperators occurs in the middle layers. The four-level hierarchical structure provides the highest average (total) income for the whole community.

Abstract: The evolutionary origin of inter- and intra-specific cooperation among non-related individuals has been a great challenge for biologists for decades. Recently, the continuous prisoner’s dilemma game has been introduced to study this problem. In function of previous payoffs, individuals can change their cooperative investment iteratively in this model system. Killingback and Doebeli (Am. Nat. 160 (2002) 421–438) have shown analytically that intra-specific cooperation can emerge in this model system from originally non-cooperating individuals living in a non-structured population. However, it is also known froman earlier numerical work that inter-specific cooperation (mutualism) cannot evolve in a very similar model. The only difference here is that cooperation occurs among individuals of different species. Based on the model framework used by Killingback and Doebeli (2002), this Note proves analytically that mutualism indeed cannot emerge in this model system. Since numerical results have revealed that mutualism can evolve in this model system if individuals interact in a spatially structured manner, our work emphasizes indirectly the role of spatial structure of populations in the origin of mutualism.

It is highly improbable that mutualistic interaction would emerge in this model system. We emphasize here that our analysis is restricted only to the large population limit […], which could not exclude the evolution of mutualism in small populations.

On the other side, this letter emphasizes indirectly the important role of spatial structures in the evolution of mutualism.

Abstract: we consider the class of (finite) spatial games. We show that the problem of determining wether there is a Nash Equilibrium in which each player has a payoff of at leas k is NP-Complete as a function of the number of players. When each player has two strategies and the base game is an anti-coordination game, the problem is decidable in polynomial time.

Abstract: Evolutionary game models of cellular interactions have shown that heterogeneity in the cellular genotypic composition is maintained through evolution to stable coexistence of growth-promoting and non-promoting cell types. We generalise these mean-field models and relax the assumption of perfect mixing of cells by instead implementing an individual-based model that includes the stochastic and spatial effects likely to occur in tumours. The scope for coexistence of genotypic strategies changed with the inclusion of explicit space and stochasticity. The spatial models show some interesting deviations from their mean-field counterparts, for example the possibility of altruistic (paracrine) cell strategies to thrive. Such effects can however, be highly sensitive to model implementation and the more realistic models with semi-synchronous and stochastic updating do not show evolution of altruism. We do find some important and consistent differences between the spatial and mean-field models, in particular that the parameter regime for coexistence of growth-promoting and nonpromoting cell types is narrowed. For certain parameters in the model a selective collapse of a generic growth promoter occurs, hence the evolutionary dynamics mimics observable in vivo tumour phenomena such as (therapy induced) relapse behaviour. Our modelling approach differs from many of those previously applied in understanding growth of cancerous tumours in that it attempts to account for natural selection at a cellular level. This study thus points a new direction towards more plausible spatial tumour modelling and the understanding of cancerous growth.

Abstract: The Prisoner’s dilemma is the main game theoretical framework in which the onset and maintainance of cooperation in biological populations is studied. In the spatial version of the model, we study the robustness of cooperation in heterogeneous ecosystems in spatial evolutionary games by considering site diluted lattices. The main result is that, due to disorder, the fraction of cooperators in the population is enhanced. Moreover, the system presents a dynamical transition at P, separating a region with spatial chaos from one with localized, stable groups of cooperators.

We allow that some of the sites may be empty. No empty site will be ever filled. In the simulations, averages are taken from 100 samples.

Abstract: In the ultimatum game, two players are asked to split a certain sum of money. The proposer has to make an offer. If the responder accepts the offer, the money will be shared accordingly. If the responder rejects the offer, both players receive nothing. The rational solution is for the proposer to offer the smallest possible share, and for the responder to accept it. Human players, in contrast, usually prefer fair splits. In this paper, we use evolutionary game theory to analyse the ultimatum game. We first show that in a nonspatial setting, natural selection chooses the unfair, rational solution. In a spatial setting, however, much fairer outcomes evolve.

Players arranged on a two-dimensional square lattice. Each player interacts with his neighbours. Experiments on the UG shed a striking light on our mental equipment for social and economic life. Who do fairness considerations matter more, to many of us, than rational utility maximization? Spatial population structure can have important effects on the evolutionary outcome of the ultimatum game.

Abstract: Using a spatial lattice model of the Iterated Prisoner's Dilemma we studied the evolution of cooperation within the strategy space of all stochastic strategies with a memory of one round. Comparing the spatial model with a randomly mixed model showed that (1) there is more cooperative behaviour in a spatially structured population, (2) PAVLOV and generous variants of it are very successful strategies in the spatial context and (3) in spatially structured populations evolution is much less chaotic than in unstructured populations. In spatially structured populations, generous variants of PAVLOV are found to be very successful strategies in playing the Iterated Prisoner's Dilemma. The main weakness of PAVLOV is that it is exploitable by defective strategies. In a spatial context this disadvantage is much less important than the good error correction of PAVLOV, and especially of generous PAVLOV, because in a spatially structured population successful strategies always build clusters.

pavlov strategy means: “win stay loose shift”. in a Generous strategy there is a minor probability of not defecting even when the strategy forces it.

Abstract: This paper considers complex models arising in sociobiology. These combine genetic and strategic aspects to model the effect of gene-linked strategies on the ability of individuals to survive to maturity, mate and produce offspring. Several important models considered in the literature are generalised and extended to incorporate a spatial aspect. Individuals are allowed to migrate. Contests, e.g. for food or amongst males for females, take place locally. The choice of the point at which the population structure is measured affects the complexity of the equations describing the system, although it is possible to utilise any point in the life cycle. For our spatial models the simplest approach is to measure the population structure immediately after migration. A saddle point method, developed by the authors, has previously been used to obtain results for simple discrete time spatial models. It is utilised here to obtain the speed of first spread of a new gene-linked strategy for the much more complex sociobiological models included in this paper. This demonstrates the wide-ranging applicability and power of the method.

Games against vicinity. The game has two pure strategies s1 and s2. Population: A1A1 (1), A1A2 (2), A2A2 (3). (1) plays s1, (2) plays s2 and (3) plays s1 with probability p and s2 with 1-p. Reaping occours to reduce the population to the carrying capacity of the habitat. A new population is generated and the previous one is removed. There is a probability density function for migration.

Abstract: Interspecific mutualisms are widespread, but how they evolve is not clear. The Iterated Prisoner’s Dilemma is the main theoretical tool to study cooperation, but this model ignores ecological differences between partners and assumes that amounts exchanged cannot themselves evolve. A more realistic model incorporating these features shows that strategies that succeed with fixed exchanges (e.g., Tit-for-Tat) cannot explain mutualism when exchanges vary because the amount exchanged evolves to 0. For mutualism to evolve, increased investments in a partner must yield increased returns, and spatial structure in competitive interactions is required. Under these biologically plausible assumptions, mutualism evolves with surprising ease. This suggests that, contrary to the basic premise of past theoretical analyses, overcoming a potential host’s initial defenses may be a bigger obstacle for mutualism than the subsequent recurrence and spread of noncooperative mutants.

If the players occupy fixed sites, and if they interact only with close neighbours, there will be no need to recognize and remember, because the other players are fixed by the geometry. “spatial games”

grid with cooperators and defectors. the figures have four colours: cooperators, defectors, new cooperators and new defectors (those who changed their strategies in the last round).