Evolution

The Game Theory of Life

Applying game theory to the behavior of genes provides a new view of natural selection.

Beatrice the Biologist

Applying game theory to the behavior of genes provides a new view of natural selection.

Comments (13)

print

In what appears to be the first study of its kind, computer scientists report that an algorithm discovered more than 50 years ago in game theory and now widely used in machine learning is mathematically identical to the equations used to describe the distribution of genes within a population of organisms. Researchers may be able to use the algorithm, which is surprisingly simple and powerful, to better understand how natural selection works and how populations maintain their genetic diversity.

By viewing evolution as a repeated game, in which individual players, in this case genes, try to find a strategy that creates the fittest population, researchers found that evolution values both diversity and fitness.

Some biologists say that the findings are too new and theoretical to be of use; researchers don’t yet know how to test the ideas in living organisms. Others say the surprising connection, published Monday in the advance online version of the Proceedings of the National Academy of Sciences, may help scientists understand a puzzling feature of natural selection: The fittest organisms don’t always wipe out their weaker competition. Indeed, as evidenced by the menagerie of life on Earth, genetic diversity reigns.

Multiplicative weights update algorithm.

Wu et al. 2010, International Journal of Computer Vision

The “multiplicative weights update algorithm” is employed in a number of computer science applications, including object recognition, as shown here.

“It’s a very different way to look at selection,” said Stephen Stearns, an evolutionary biologist at Yale University who was not involved in the study. “I always find radically different ways of looking at a problem interesting.”

The algorithm, which has been used to solve problems in linear programming, zero-sum games and a dozen other sophisticated computer science problems, is used to determine how an agent should weigh possible strategies when making a series of decisions. For example, imagine that you have 10 financial experts giving you advice on how to invest your savings. Each day you have to choose to follow one of them. At the start of the investment period, you know nothing about how well each expert performs. But every day, the multiplicative weights update algorithm, as it is called, instructs you to boost the probability of choosing the experts who have given the best advice and decrease it for those who have performed poorly.

“If you do this day after day, at the end of the year, you will do almost as well as if you had followed the best expert from the beginning,” said Christos Papadimitriou, a computer scientist at the University of California, Berkeley. “It’s as if you were omniscient in the beginning, singling out the best expert and following their advice day after day.”

Christos Papdimitriou

Bart Nagel

Christos Papadimitriou, a computer scientist at the University of California, Berkeley, said the algorithm might help explain sexual reproduction.

Papadimitriou and his collaborators came across the connection between game theory and evolution when they were searching for a mathematical explanation of sex, which triggers new genetic diversity by mixing up the chromosomes from each parent. They were working with equations commonly used in population genetics, first developed nearly a century ago, that describe how the frequencies of certain genetic variations change with each generation. For example, plants that flourish in the current climate might dwindle as global warming alters conditions.

When they showed the equations to Umesh Vazirani, a computer scientist at Berkeley, he noticed parallels to a repeated coordination game — a  scenario in game theory in which success depends on the players choosing mutually beneficial options. As an example, consider a situation in which two prisoners are tempted to turn on each other. If one talks, both lose; if neither talks, both win. Neither prisoner knows what the other will do. (This scenario is different than the well-known prisoner’s dilemma.)

Viewing the algorithm through the lens of evolution, genes are the players, and each gene has a number of different strategies in the form of genetic variations, or alleles. One variant of a gene might make a plant tolerate warmer temperatures or drier soil, for instance. The game is played over and over again; at the end of each round, the gene, or player, evaluates how well each of its alleles performed in the current genetic environment and then boosts the weight of the good performers and downsizes the weight of poor performers.

The researchers said the findings will provide a new way to examine the role of sex in evolution. For example, Papadimitriou said he believes that part of its role is to carry out the multiplicative weights update algorithm, though he hasn’t yet proven this mathematically.

Traditional applications of game theory to evolution examine how evolutionary processes shape an individual’s behavior. They have also been used to study the evolution of altruism and other properties. “But here, we’re talking about something completely different,” said Adi Livnat, a biologist at Virginia Polytechnic Institute in Blacksburg, Va., who collaborated on the study.  The new study focuses on genes rather than individual organisms, and on the genetic makeup of the population instead of behavior.

Umesh Vazirani

Peg Skorpinski

Umesh Vazirani, also a computer scientist at Berkeley, first noticed that the equations used in population genetics resemble a powerful algorithm in computer science.

The approach could illuminate a long-standing mystery in population biology. Just as in the financial world, where it’s best to keep a diversified portfolio, Vazirani and his collaborators found that the algorithm values both fitness and diversity. You might be tempted to place all your money on a soaring stock. But if circumstances change and that stock starts to tank, you’re better off having invested in a more balanced selection. Similarly, an organism’s genes may be perfectly tailored to a particular set of environmental conditions, but if those conditions change, a genetically diverse population is more likely to survive. “Evolution is, of course, interested in performance,” Papadimitriou said. “But it’s also interested in hedging its bets, keeping around a lot of genetic diversity because who knows what will come next.”

Evolutionary biologists know that in practice, a genetically diverse population is often more resilient than a homogeneous one because it is better able to respond to changing environments. But they have struggled to explain how such diversity is maintained. In the short term, one would expect diversity to drop as the fittest members of a population spread, knocking out the weaker, genetically dissimilar members. How do long-term needs surmount the short-term pressures?

The findings provide a “speculative suggestion” for how this might happen, though the authors don’t propose a specific mechanism, said Nick Barton, a biologist at the Institute of Science and Technology in Austria who was not involved in the study. “I don’t think it gives us the algorithm that can achieve the diversity we see on Earth in 3.5 billion years, when life first began,” he said.

Stearns and others in the field say it’s too soon to assess how the findings will affect our understanding of evolution. Even though the connection between different fields is interesting, “it does not actually help us understand biological evolution,” said Chris Adami, a physicist and computational biologist at Michigan State University, who was not involved in the study. “Unless such a relationship allows you to say something new either in computer science or biology, it’s just an observation.”

Evolutionary biologists are often skeptical of mathematical insights from outsiders. Although mathematicians and computer scientists regularly publish in the field, biologists disagree over how much their contributions have done to shape it. “I think it will take some time to figure out how the paper plays out,” Stearns said. “If this doesn’t cause any new data to be gathered, then it won’t be very important.” Even if the findings don’t prove relevant in the short-term, they might prove important over the long –term. Sometimes it can take decades before the right technology or approach arises to test a new theory, Stearns said.

Evolution and Entropy

One of the surprising discoveries of Papadimitriou’s study is that natural selection values not just fitness, but also genetic diversity, which in more technical terms is referred to as entropy. This view that evolution optimizes not just mean fitness but mean fitness and entropy is not well known, “but I think it’s a deep observation,” Adami said.

The Berkeley team isn’t the first to highlight the role entropy might play in evolution. But until now, the subject has mainly been of interest to mathematicians rather than biologists. “Applications of entropy in evolution have had a bad name, because they were very ill-defined,” Barton said. “More recently, there have been some interesting, and much sounder, ideas, which make a link between fields that are addressing a similar issue: Statistical physics and evolutionary biology both try to understand the overall properties of a complicated system, independent of the microscopic details.” These more recent results are mathematically sound, but they still don’t connect well with existing biological understanding, he said. “So it’s not clear to biologists how [the results] might help explain their open questions.”

The equations in the study are based on certain assumptions that may limit their applicability to the real world. For example, the equations don’t account for mutations, which would introduce new alleles, or strategies, into the game. (Adding this factor makes the mathematics much more complex.) Some say this simplification is a serious drawback, while others maintain that it is not so important in the short term, when existing variations have the strongest impact. “What happens when you move away from the assumptions?” said Lee Altenberg, a senior fellow at the Konrad Lorenz Institute in Austria. “They have pinned a single point on the map. But to know whether that means anything, you have to start departing from that point.”

One outcome of the analysis is likely to puzzle biologists. According to the standard view of evolution, the further a generation lies in the past, the less impact it has on the present — your ancestors from 1,000 years ago probably had less effect on your fitness than your grandparents. But if the Berkeley team’s insights hold up, “it shows us that every past generation contributes equally to what happens in the next generation,” Stearns said. “That’s an intriguing and wildly implausible claim from the standpoint of regular evolution.” Papadimitriou said his team was also perplexed by that outcome. “It is something that hopefully will make researchers rethink, revisit and interpret,” he said.

“You can’t really test these theorems in relation to real life,” Barton said. “They are tools for getting intuition about how to understand evolution.”

This article was reprinted on TheGuardian.com.

Add a Comment

View Comments (13)

Comments for this entry

  • “You can’t really test these theorems in relation to real life,” Barton said.

    Why not? e.g., fruit flies can have many generations in a relatively short timespan.

  • “Others say the surprising connection … may help scientists understand a puzzling feature of natural selection: The fittest organisms don’t always wipe out their weaker competition. Indeed, as evidenced by the menagerie of life on Earth, genetic diversity reigns.”

    Superficially and short-term, Life may appear to be strictly competitive, thus suggesting that “survival of the fittest” depends upon competitive dominance. In it’s depths and long-term, however, Life depends a great deal upon great diversity united in harmonious cooperation. Until this understanding is embraced and applied in scientific investigation, we will be unable to design and carry out the investigations necessary to more fully reveal the true nature of Nature.

    “Evolution is, of course, interested in performance.”

    What “evolution is interested in” should not always be evaluated by humans according to short-term, fear-based interests (desires) of the human ego. Humans need to evolve beyond this self-centered and self-limiting point of view.

    “Evolutionary biologists know that in practice, a genetically diverse population is often more resilient than a homogeneous one because it is better able to respond to changing environments. But they have struggled to explain how such diversity is maintained. In the short term, one would expect diversity to drop as the fittest members of a population spread, knocking out the weaker, genetically dissimilar members. How do long-term needs surmount the short-term pressures?”

    “Knocking out the weaker” does not allow for the possibility, let alone the probability, that harmonious cooperation may actually provide both short-term and long-term survival advantages. Why is fitness always evaluated according to fear-based rules focused on fitness to compete rather than love-based rules embracing fitness to be cooperative?

    Genes are thought of as cogs, wheels and levers in mechanical systems rather than as aspects of living organisms that include not only their parts and pieces but also the expressions of those parts and pieces. Also, we are much more than genes and the expressions of our genes. We are also cooperative alliances of almost countless micro-organisms who have, in essence, “agreed” to live in some semblance of harmonious cooperation, not only “with” us but, more importantly, “as” us. By numbers, there are more of “them” than “us” – more of those micro-organisms than there are cells we can count as our own that constitute our muscles, bones, organs, nerves, etc.

    Every time we are “surprised” by the results of some investigation into the nature of Nature, this should be regarded as a clue that we need to step back and re-evaluate how we got ourselves into the trap of believing something that has turned out to be untrue, or at least highly questionable.

    “One of the surprising discoveries of Papadimitriou’s study is that natural selection values not just fitness, but also genetic diversity, which in more technical terms is referred to as entropy.”

    Why is genetic diversity not considered an essential aspect of fitness? Genetic diversity greatly enriches the populations of organisms. Individual diversities greatly enrich our experiences of Life – but only when we learn to accept, embrace, appreciate, nurture and honor our individuality. Perhaps it is an error to view entropy as chaotic, unpredictable randomness. Perhaps we should instead learn how to appreciate increased entropy as an increase of freedom, potential and possibility in Life.

  • Why isn’t John Nash mentioned in this article who won the Nobel Prize for his work in this area. Or is this a different Game Theory?

  • Hmm, so are the genes considered just those of single, sterile organisms, or the entire conglomerate that supports organisms? E.g. the gut flora that allows ruminants and termites to digest? The myriad external and internal epithelial flora we humans carry? Are varieties of cooperation included here?

  • The author’s description of the Prisoner’s Dilemma threw me off. If that scenario were true that only one talks and both lose , there would be no dilemma. I think the way it goes is, if neither talk they get a small sentence, but if one talks, he goes free while the other serve a long sentence. If both talk they both get a medium sentence.

    Another part that kind of derails the article for me is this comment; “One of the surprising discoveries of Papadimitriou’s study is that natural selection values not just fitness, but also genetic diversity”. So the surprising thing about natural selection is also the definition of it – that adaptability and diversity are key to survival. That’s surprising? That’s like saying my study of basketball is surprising in that it values hoops instead of oil derricks.

    ALSO, the rest of that quote didn’t sound right, “genetic diversity, which in more technical terms is referred to as entropy.” Is it? As far as I can tell, the effects of entropy can be tracked statistically to provide information that helps describe genetic diversity, but that like saying my medical records are the same as my blood.

    Not meaning to troll. The article makes a nice overall point.

  • This also sounds very much like Bayes Theorem – the best prediction for tomorrow is what happened today… varied slightly

  • This is a very old result, which is periodically re-discovered and re-published in slightly varying forms.

    I first remember reading about it twenty years ago. For a relatively new re-discovery, check out the 2001 paper “Evolution of digital organisms at high mutation rates leads to survival of the flattest” by Claus O. Wilke et al.

  • Thanks for your comments. I asked Nick Barton, a biologist at the Institute of Science and Technology in Austria who is writing a commentary on the paper for PNAS, for his insight on some of these questions.

    1. Q: Why can’t these theorems be tested in real life?
    Barton: The underlying dynamics are simply that each allele grows at a rate given by its fitness relative to the rest of the population. This is true more or less by definition: the empirical questions are about how much heritable variation in fitness there is, and how it acts. Chastain et al. are taking the basic dynamics as given, but formulating them in a different way.

    2. Comment: This is a very old result, which is periodically re-discovered and re-published in slightly varying forms. For a relatively new re-discovery, check out the 2001 paper “Evolution of digital organisms at high mutation rates leads to survival of the flattest” by Claus O. Wilke et al.
    Barton: The idea that the fitness of an allele is an average over the genetic backgrounds in which it finds itself is a very old one (emphasised by Fisher, Dobzhansky, and many others), and was emphasised by Wilke et al. Chastain et al. point out the close parallel with efficient algorithms in computer science.

  • Does this work explain a disadvantage to genetically modified organisms? Do GMO’s have a narrow side to their genetic diversity making them more susceptible to collapse with environmental changes?

  • So, how is this different from the game theory discussed 30 years ago by Richard Dawkins in “The Selfish Gene”? He wrote about how game theory, through repeated game plays, can explain altruism.

  • Dawkins used it to relate the way in which altruistic behaviours develop within the context of Darwinian process.

    Applying game theory in regard to the world’s need and use of variety is paramount in the above use, and this also enforces the idea that wiping out an organism just because it is weaker is not a good idea.

    Game theory helps us to define optimal strategies. The reason behind the choice we make can be 1) to show altruism or 2) to utilize variety. Which do you think it is? Can it be proven?

  • @David:
    from Nick Barton:

    Game theory is a well-established way of understanding interactions between individuals – in evolutionary terms, fitness then depends on the frequencies of the other players in the population. The Chastain et al analysis is much simpler, because fitness depends only on the combination of genes carried by an individual. However, with sexual reproduction, from a gene’s point of view, fitness does depend on the frequencies of other genes. Chastain et al do point out this connection with results from game theory.

  • Nick Barton: “Chastain et al. point out the close parallel with efficient algorithms in computer science.”

    In other words, they aren’t adding anything at all to evolutionary biology that isn’t already known.

Leave a Comment

Your email address will not be published. Your name will appear near your comment. Required *

Quanta Magazine moderates all comments with the goal of facilitating an informed, substantive, civil conversation about the research developments we cover. Comments that are abusive, profane, self-promotional, misleading, incoherent or off-topic will be rejected. We can only accept comments that are written in English.