April 1, 2014

Carnival of Evolution #70: the game of evolution


"It's not whether you win or lose, it's how you play the game" -- Grantland Rice, in an oddly prescient and hypothetico-deductive capacity.

This month's Carnival of Evolution (#70) theme will be evolutionary games, broadly defined. Games are generally associated with strategy and intentionality (e.g. having a brain). In fact, formal game theory (the kind developed by John von Neumann and John Nash) arises from the mathematical study of human decision-making and economic theory [1]. However, game theory has also been applied to biological systems such as the dynamically stable behavioral states exhibited by E. coli [2] and viruses [3]. Game theory can also be applied to many proximal animal behaviors. While perhaps not the objects of selection themselves, these proximal behaviors can be better understood in the context of an adaptive game. In this post, I will not advocate for any one approach to evolutionary game theory, but will offer a guided tour exploring the possibilities for this approach. The month's posts will be presented at various points in this discussion.

The outcome of evolutionary games? TOP: tree of life (sensu Woese). BOTTOM: evolution of complexity (sensu Gould).

Game theory traditionally quantifies the outcomes of intentional actions. In evolutionary game theory, we are quantifying the discrete interactions between individuals. This does not require formal cognitive mechanisms, only biological units (e.g. genes, organisms, or even populations) that interact over time. Evolutionary game theory bears a striking conceptual resemblance to population genetics. But instead of using a gene metaphor, the metaphor of strategy is used. When these strategic interactions are shaped by natural selection and population processes, the results are evolutionary dynamics. Evolutionary dynamics shape not only shape microevolution, but have an influence on macroevolution as well.

Early game theory afficionados, in the pursuit of GOFAI.

The month's posts, part 1
In the post "Fixing on the Nitrogen fixation problem" at Mermaid's Tale, Anne Buchanan presents a post on the biology of Nitrogen fixation in plants, and poses it as an long-term scientific research problem with far-reaching consequences. Holly Dunsworth, also writing at Mermaid's Tale, discusses the challenges of teaching evolutionary concepts in her post "Are we removing the wisdom along with the teeth?". John Wilkins from Evolving Thoughts enlightens us about species concepts and the history of biology in "The Origins of Speciation". PZ Myers presents a post at Pharyngula called "Pathways to Sex", which is a comprehensive review on the evolution, diversity, and genetics of sexual dimorphism. Jonathan Richardson highlights a new Trends in Ecology and Evolution paper on the blog Eco-Evo-Evo-Eco (Eco-evolutionary Dynamics). As one of the co-authors, he provides a discussion of local adaptation, or adaptation at very small geographic scales [4].

Examples of evolutionary dynamics. COURTESY: Box 1, Figure 1 in [5].

How does game theory fit into evolutionary theory? Here are some definitions and their broader implications in the context of evolutionary game theory:

Decision: Decision-making is not always a cognitive function. In evolutionary game theory, decision-making can relate to the replication of genes or behaviors, which is a prime imperative of life. Replicator dynamics, then, are the results of making a decision over and over again. After each decision is made, a payoff can be assigned to the outcome. In evolutionary game theory, the payoff (positive or negative) has a fitness consequence. These consequences provide feedback to the player (e.g. organism) to act upon during subsequent decisions.

Outcome of the Hawk-Dove game in terms of population dynamics. COURTESY: Figure 1 in [6]

Strategy Suite: The player (in this case, an organism) must choose a strategy to counter responses by conspecifics, predators/prey, or even environmental stimuli. A pure strategy is a single strategy played at a given time-point. A mixed strategy involves choosing from a number of strategies at a given time point [7]. In the case of an evolutionary stable state (ESS), each player's mixed strategy suite converges to a pure strategy over time [8]. These pure strategies are optimal in the sense that established pure strategies cannot be beaten by upstart strategies that might emerge in a population over time.

Outcome of a mutualistic relationship (legume-bacterium) modeled as a Prisoner's Dilemma game and outcomes shown in terms of population dynamics. COURTESY: Figure 3 in [6]

Strategy as variation: The existence of pure or mixed strategies may be tied to genetic variation. However, the evolution of these strategy suites (e.g. how they are deployed) is a function of natural selection. One example of this is when a strategy becomes evolutionarily stable in a population. Once a given strategy is fixed in the population, natural selection can maintain its dominance, even as lower-frequency mutant strategies emerge [9]. In this sense, strategies behave like loci in population genetics theory.


Maynard-Smith on the origins of Evolutionary Game Theory [10]. COURTESY: Web of Stories.

In evolutionary games, strategies can be defined as heritable phenotypes [11], which range from well-defined behaviors to morphological characters. A strategy is evolutionary feasible if it is either an extant (current existing) variant within a population or a recurring mutant in that population. The strategies themselves can range in frequency from very rare to dominant. A player (organism) may be a carrier for latent strategies. Such strategies may have a low payoff in one environment while having a much higher payoff in another environment.

But how can an organism not "show all of its cards" as it were? According to [12], evolutionary game theory exists of an inner game and an outer game. The inner game is more akin to classical (e.g. economic) game theory where there are payoffs for intentional strategies. However, the evolutionary version also consists of an outer game that is dynamically linked to the inner game. This linkage allows the outer game to take the form of translating these payoffs into changes in phenotypic frequencies. This allows us to bridge proximal and ultimate causes of adaptive change in a population.

The month's posts, part 2
Jeremy Yoder from Nothing in Biology Makes Sense! reviews the Festival of Bad Ad-hoc Hypotheses. In "BAH! This looks amazing", Jeremy introduces us to the quest to discover the best "well-argued and thoroughly researched but completely incorrect evolutionary theory". Then, writing at Molecular Ecologist, Jeremy discusses the occurrence of soft selective sweeps in bacterial populations of the gut. Adam Goldstein of The Shifting Balance of Factors critiques scala naturae views of evolution in "March of Progress, reloaded". Ed Yong from Phenomena  presents a new paper that highlights the role of doublesex, which enables mimicry in the female common mormon butterfly (Papilio polytes). Here's an interview of Baba Brinkman by Kylie Sturgess at CSI's Curiouser and Curiouser blog. Baba Brinkman raps about evolution on a regular basis. You will have to go to the post to find out more. And at the BEACON Center blogDanielle Whittaker introduces us to the work of Tyler Heather, who works on the role of gene-phenotype interactions in the speed of adaptation, and Raffica LaRosa, who measures natural selection in flowers.

 "Time (evolution) is a game played beautifully by children (juveniles)" -- Heraclitus, perhaps anticipating the rise of Evo-Devo

Hawk-Dove Games

Hawk-Dove games are the traditional two-player zero-sum games most people are familiar with. A game with the simplest type of outcome, hawk-dove produces a winner and a loser. Only winning is stable (e.g. winner-take-all), so such games often result in arms races and necessitate conflict. While a pure "hawk" strategy is stable in the short term, it may not be evolutionarily stable.

Illustration of Hawk-Dove dynamics. COURTESY: Evolutionary Game Theory Wikipedia page.

In an evolutionary context, Hawk-Dove can also be characterized as the well-known Red Queen (a special instance of zero-sum game theory) [13]. The Red Queen, which characterizes co-evolutionary arms races, provides a means for the emergence of complex evolutionary dynamics between two species (e.g. players).

The month's posts, part 3
Razib Khan, writing at Unz Review, considers what can be learned from the re-analysis of open-access genome data in a post entitled "Reanalyzing Data: it does a mind good". Lesson: re-analysis is a highly fruitful endeavor. Dan Graur from the Judge Starling tumblr brings us a discussion of the ENCODE project in relation to the gene concept in "Mutons, Cistrons, Recons, and Nuons: News Concerning the Death of “Gene” are Greatly Exaggerated". At Genealogical World of Phylogenetic Networks, David Morrision leads a bibliometrics-based discussion on the emergence and current state of phylogenetics research as a subfield of evolutionary biology in "Has phylogenetics reached its apogee?". Moving from analysis to modeling, Artem Kaznatcheev at the Theory, Evolution, and Games group blog discusses a recent evolutionary-oriented theoretical Computer Science conference in "Computational theories of evolution" and "Algorithmic Darwinism". 
 Two player games with complexity.

Rock-paper-scissor Games

Rock-paper-scissor games are defined by their non-transitive outcomes. In Sinervo and Lively [14], male side-blotched lizard phenotypes give rise to three behavioral strategies. While competitive, these behaviors do not result in a definitive winner. For example, while there is a clearly dominant strategy (blue-throated guarders) that provides the highest payoff, alternate strategies (yellow-throated sneakers and orange-throated usurpers) can also be stable. Rather than converging to a pure strategy where competition would be winner-take-all, multiple strategies can co-exist at varying frequencies indefinitely.

Example of Rock-Scissors-Paper in Side-blotched Lizard. COURTESY: Sinervo Lab (UCSC).

The month's posts, part 4
John Hawks, writing at his weblog, provides information and his own insights on "A new early modern human genome from Siberia", which was isolated and sequenced from a 45,000 year-old femur. Moving from ancient genomics to theory, we have two posts on mechanisms and misunderstandings. The first is Philip Ball's (Homunculus blog) take on the "Molecular mechanisms of evolution". The second is from Larry Moran of Sandwalk blog, who introduces us to "A chemist who doesn't understand evolution". Returning to human evolution, but moving on to analysis, The Olduvai Gorge tumblr site provides a preview of and link to the new article "The Doubly-Conditioned Frequency Spectrum does not distinguish between ancient population structure and hybridisation". The paper itself is a critique of a popular method used in studies of phylodemography.

Prisoner's Dilemma and Snowdrift Games

Most biologists are familiar with the Prisoners' Dilemma (PD) -- in fact, this is the canonical game for demonstrating the evolution of cooperation [15]. A slightly less familiar variant of the PD game is the snowdrift (or cooperation) game. In both PD and snowdrift games, the maximal payoff results from cooperation and coordination between players rather than competition.

Payoff matrix for the PD game using a generic example. A 2x2 payoff matrix. COURTESY: Animalbehavioronline.com

Using the snowdrift game as an example, two players are confronted with the task of clearing away a snowdrift. If completed, the work benefits them both. However, if only one player decides to undertake the task, the second player can benefit without contributing (e.g. free-riding). But since the first player is unlikely to put up with free-riding over repeated plays of the game, the highest payoff for both players over repeated plays is attained from full cooperation in performing the work. As this strategy is replicated over evolutionary time, it becomes the dominant strategy. Thus, players converge upon this pure strategy through the maximization of payoffs [16], and it becomes evolutionarily stable.

The month's posts, part 5
Bjorn Ostman from Pleiotropy presents a review of evolutionary dynamics in holey fitness landscapes. Charles Goodnight from the excellent Evolution in Structured Populations blog gives us three tutorial-esque posts the month: "Mating structure, Interaction structure, and Selection Structure", "Griffing, Associate Effects, and Heritability", and "Measuring the Heritability of Contextual Traits". The population biology preprint blog Haldane's Sieve features a new paper (now accepted at PLoS One) called "The Arrival of the Frequent: how bias in genotype-phenotype maps can steer populations to local optima". Using both simulation and genotype-phenotype maps, this paper demonstrates that as rare variants, the fittest organisms in a population often do not survive to be fixed or otherwise represented at evolutionary timescales. And in the spirit of evolutionary computation, IEEE Spectrum has a feature on how bug-ridden computer code is being refactored and otherwise fixed using genetic algorithms derived from evolutionary theory.
A mans friendships are one of the best measures of his worth” -- Charles Darwin

Stackelberg and Pursuit-Evasion Games

These types of games are not as familiar to biologists. However, in their instantiated form, they appear to be quite useful to the evolution of biological complexity.

Stackelberg (or first-mover) games [17] might explain much about the emergence of evolutionary constraints and biological complexity. One simple example of such a game is the leader-follower game. The leader moves first by choosing from a mixed strategy suite, usually in a way that maximizes the payoff. The second player must then continually respond to the actions of the first move, as they are constrained from using a full set of possible strategies. While the second player gains information from the first-mover's strategy, it only allows them to maximize their payoff from a subset of strategies. This might explain the emergence of symbiotic relationships, or perhaps the emergence of social dominance hierarchies.

Pursuit-evasion (or cops and robbers) games might explain the emergence of predator-prey relationships. As is the case with Stackleberg games, the order in which turns are taken becomes an important determinant of the payoff. In pursuit-evasion, however, the first mover (evader) is constrained by what it takes to successfully avoid the pursuant (second mover) [18]. These types of games are generally zero-sum, although they need not be.

Leader-follower dynamics, presented as an abstract model. COURTESY: Evolutionary Bilevel Optimization.

Predator-prey dynamics in a two-state system. COURTESY: Wolfram Demonstrations Project.

The tic-tac-toe (a.k.a. naughts and crosses) game is an example of how leader-follower dynamics can produce stable equilibria. In tic-tac-toe, there are first movers and second movers. While optimal play by both players will result in a tie, the first move can often win the game if the second mover makes a suboptimal move.

Tic, tac, toe! Sometimes learning how to play games are a matter of life and death.

Games Against Nature

Games against nature are 1-player games where the sole player implements a strategy against a random process. The payoff is determined by how well the intentional player fares against the random process. The obvious extension of this is an organism adapting in the face of natural selection. One example of a game against nature can be found in cellular automata [19]. Cellular automata operate using simple rules imposed of a single cell by both its neighbors and stochastic processes that lead to emergent patterns across a grid of cells. While such games do not rely on competition nor cooperation, they do produce coordinated outcomes. In Conway's Game of Life, each cell is "born" or "killed" based on the states of its neighbors. The result is not a formal payoff matrix, but rather a set of patterns that persist or die off. Unlike zero-sum or conventional cooperation games, the outcome of the game is non-deterministic.

A cellular automata game against nature, played during development.

The month's posts, part 6
Carlos Araya from CEHG Blog reviews the latest findings in the area of experimental evolution in a post called "Dissecting the dynamics of adaptation with experimental evolution". Henry Gee from The End of the Pier Show brings us a paleontologically-inspired tale entitled "Careful with that Amphiooxus, Eugene". Aeon Magazine has a feature this month on selfish gene theory as a takeoff on the blogosphere kerfuffle started by David Dobbs with his article "Die, Selfish Gene, Die!". Their roundtable includes David Dobbs, Robert Sapolsky, Laura Hercher, Karen James, and John Dupre (a writer, a genetic counselor, two biologists, and a philosopher). For further critical assessment of this roundtable, see posts by Jerry Coyne at Why Evolution is True and  Larry Moran of Sandwalk
 
John Conway, on the origins of his "game of life" (a game against nature). COURTESY: Numberphile.

"There are no shortcuts in evolution" -- Louis D. Brandeis, who was not a biologist.

Many modern video games (such as first-person shooter games) are essentially games against nature. In this conception, nature is an artificial agent that presents challenges to a player, which can be overcome through either inherent skill or an adaptive solution. What if we could replace the goal-directed behaviors of a player with evolutionary imperatives?

Evolutionary Simon: a plot device devised for this post, but does the model fit the data?

To model this possibility using a formal game model, I introduce something called Evolutionary Simon. Simon is a programmed board game developed in the 1970s that might also be used to model the proximate effects of behavioral selection. Recall that the Simon game presents a sequence of lighted tiles (e.g. blue, blue, yellow, blue, red, green, red) that is generated by a computer program. The player must then imitate this sequence by pressing the right buttons in the correct order.

So far, this resembles a typical free recall (learning and memory) experiment. Now let us introduce a diversity of players, some with greater innate recall capacity, some with less. This innate capacity is improved upon by getting a correct answer. The payoff matrix for this 3x1 game:

Payoff matrix for Evolutionary Simon game. Payoffs are for strategies employed by a player (top row). ε is used to distinguish minimally correct response from incorrect. 


Incorrect


Partially Correct

Fully Correct

Simon Output


0

(1 – (1/cr)) + ε


1

Players respond to the output using either an entirely inappropriate response, a fully correct response, or a partially correct response (which exposes the limitations of their memory). Partially correct responses (cr) are scored by how many components of the original sequence they were able to recall. For every turn, an agent receives a payoff. The length of a Simon sequence can be used as a source of environmental selection.

In the end, the agents that end up with the largest payoffs over a wide range of generated patterns are the fittest. But we can end up with quite interesting evolutionary dynamics. For example, some agents might receive very high payoffs for specific patterns. And other agents might be able to garner a sizeable payoff for nearly every pattern presented.

The month's posts, part 7
The Cosmos reboot hosted by Neil DeGrasse Tyson is coming along nicely. Despite a few detail-oriented and denialism-related glitches, it has become a great opportunity to make science accessible to a broader audience (episode 2 was exclusively on evolution). I have been providing supplemental references on selected topics from each episode here on Synthetic Daisies. Here are the supplemental readings for the first episode (Section II of "Bits and Starstuff")second episode (Section II of "Futures of More Starstuff"), and third episode (Section II of "Ancien Regimes, Google Grokking, and Starstuff"). Larry Moran at Sandwalk provides his own insights into the factual and conceptual shortcomings of evolution, Cosmos-style. Greg Laden's Blog features a post called "Will Neil DeGrasse Tyson's Cosmos be a turning point in science denialism?", which considers the potential of the Cosmos reboot to combat science denialism. In the spirit of combating bad scientific ideas, Alex B. Berezow at Real Clear Science heeds us to "End the Hype over Epigenetics and Lamarckian Evolution", and does so by highlighting a new paper in Cell [20]. While there have been many interesting recent findings regarding the potential for short-term epigenetic heritability, it is also important to remember why Lamarck fell into disrepute in the first place (HINT: it has to do with long-term mechanisms). And finally, in the spirit of pop-science, here is an infographic from Visual.ly and Juan Martinez on the History of Life 
"Evolution is all about survival of the (your most stable equilibrium here)" -- one possible moral of our story

One lesson learned from modeling evolution as a game is that popular conceptions of evolution such as "survival of the fittest" are fundamentally incorrect. Indeed, modeling mixed strategy intra-specific competition using a rock-paper-scissors game [2] results in a "survival of the weakest". Another lesson is that evolutionary games are more than simply a matter of zero-sum competition or stable cooperation [21]. Despite the metaphor, evolutionary games are more about capturing interactions than direct intentionality. However, contemporary models focus on the role of natural selection in evolution. Yet due to their flexibility, evolutionary games could also be used to model neutral processes and other contributors to evolutionary dynamics.

There are other lessons to be learned as well, including the linkages between micro- and macroevolution and the evolution of sociality. Game-theory models can be combined with other concepts at the intersection of economics and evolutionary biology to understand behavioral signaling and other forms of informative communication. Examples include such as hedging (managing trade-offs), biological markets [22], and handicapping [23]. So is life just one big game? According to game theory and the application of game-inspired models, the answer is "yes".


This month's Carnival is also available in printable form (on Figshare) for teaching purposes. And don't forget to check out next month's Carnival of Evolution. Until then, enjoy this month's posts. And remember, the game is not over until evolution has occurred.


NOTES: 
[1] von Neumann, J. and Morgenstern, O.   Theory of Games and Economic Behavior. Princeton Press (1947) AND Nash, J., Kuhn, J.W., Nasar, S.   The Essential John Nash. Princeton Press (2007).

[2] Kerr, B., Riley, M.A., Feldman, M.W., and Bohannan, B.J.M.   Local dispersal promotes biodiversity in a real-life game of rock–paper–scissors. Nature, 418, 171-174 (2002).

[3] Turner, P.E.   Cheating Viruses and Game Theory. American Scientist, 93(5), 428-435 (2005).

[4] For more information, read the following paper: Richardson, J.L., Urban, M.C., Bolnick, D.I., and Skelly, D.K.   Microgeographic adaptation and the spatial scale of evolution. Trends in Ecology and Evolution, 29(3), 165-176 (2014).


[5] Nowak, M.A. and Sigmund, K.   Evolution of Indirect Reciprocity. Nature, 437, 1291-1298 (2005).

[6] Cowden, C.C.   Game theory, evolutionary stable strategies, and the evolution of biological interactions. Nature Education Knowledge, 3(10), 6 (2012).

[7] Rasmussen, E.   Games and Information. Blackwell Publishing (2006).

[8] Weibull, J.W.   Evolutionary Game Theory. MIT Press (1995) AND Brown, J.S. and Vincent, T.L.   Evolutionary Game Theory, Natural Selection, and Darwinian Dynamics. Cambridge University Press (2005).

[9] Nowak, M.A.   Evolutionary Dynamics: exploring the equations of life. Belknap Press (2006) AND Broom, M. and Rychtar, J.   Game-Theoretical Models in Biology. Chapman-Hall CRC Press (2013).

[10] Maynard-Smith, J. and Price, G.R.   The Logic of Animal Conflict. Nature 246 (5427): 15 (1973).

[11] Brown, J.S.   Fit of form and function, diversity of life, and procession of life as an evolutionary game. In "Adaptationism and Optimality", S.H. Orzack and E. Sober eds., Chapter 4 (1999).

[12] Vincent, T.L. and Brown, J.S.   Evolution of ESS Theory. Annual Review of Ecology and Systematics, 19, 423-443 AND Charlesworth, B.   Optimization Models, Quantitative Genetics, and Mutation. Evolution, 44(3), 520-538 (1990).

[13] Cohen, J. and Newman, C.E.   Host-parasite relations and random zero-sum games: the stabilizing effect of strategy diversification. American Naturalist, 133(4), 533-552 (1989) AND Perc, M. and Szolnoki, A. Coevolutionary games: a mini review. Biosystems, 99, 109-125 (2010).

[14] Sinervo, B. and Lively, C.M.   The rock–paper–scissors game and the evolution of alternative male strategies. Nature, 380, 240-243 (1996).

[15] Brembs, B.   Evolution of Cooperation. Brembs.net Evolution section.

[16] Shutters, S.T.   Punishment, Rational Expectations, and Relative Payoffs in a Networked Prisoners Dilemma. In "Social Computing and Behavioral Modeling", H. Liu, J. Salerno, and M.J. Young (eds.), pgs. 1-8 (2009).

[17] McNamara, J.M., Wilson, E.M.K., and Houston, A.I.   Is it better to give information, receive it, or be ignorant in a two-player game? Behavioral Ecology, 17(3), 441-451 (2006).

[18] Basar, T. and Olsder, G.J.   Dynamic Noncooperative Game Theory. Academic Press (1995).

[19] Sigmund, K.   Games of Life: explorations in ecology, evolution, and behavior. Oxford University Press (1993) AND Wolfram, S.   A New Kind of Science. Wolfram Press (2002).

[20] Heard, E. and Martienssen, R.   Transgenerational Epigenetic Inheritance: myths and mechanisms. Cell, 157(1), 95–109 (2014).

[21] Bendor, J. and Swistak, P.   Types of evolutionary stability and the problem of cooperation. PNAS, 92, 3596-3600 (1995).

[22] Noe, R. and Hammerstein, P.   Biological Markets: supply and demand determine the effect of partner choice in cooperation, mutualism, and mating. Behavioral Ecology and Sociobiology, 35(1), 1-11 (1994).

[23] Grafin, A.   Biological Signals as Handicaps. Journal of Theoretical Biology, 144, 517-546 (1990).

1 comment:

  1. this is good post...

    i like this...

    please can you visit here..

    http://bantalsilikon01.blogspot.com/
    http://bantalkekabumurah.blogspot.com/
    http://bumbupecel1.blogspot.com/
    http://bantalgood.blogspot.com/
    http://bantalsilikonmalang1.blogspot.com/
    http://bantalsilikonmurah.blogspot.com/

    http://marinirseo.blogspot.com/
    http://marinirseo.blogspot.com/
    http://marinirseo.blogspot.com/


    tengs very much...

    ReplyDelete

Printfriendly