john hawks weblog

paleoanthropology, genetics and evolution

game theory

  • The game theory exam story

    Thu, 2013-04-25 10:42 -- John Hawks

    UCLA animal behavior professor Peter Nonacs describes his experiment in learning by doing: "Cheating to Learn: How a UCLA professor gamed a game theory midterm".

    So last quarter I had an intriguing thought while preparing my Game Theory lectures. Tests are really just measures of how the Education Game is proceeding. Professors test to measure their success at teaching, and students take tests in order to get a good grade. Might these goals be maximized simultaneously? What if I let the students write their own rules for the test-taking game? Allow them to do everything we would normally call cheating?

    Naturally, nearly the entire class decided to work together.

    This is what I consistently find when I do game theory experiments with my classes. Students who work hard and contribute always tolerate free riders. When I explicitly point out the apparent unfairness of the situation, students sometimes articulate frustration with free riders, but shrug their shoulders. If Nonacs thinks he has taught them something new, he should sit in more classes.

  • Microchimerism and selection

    Sat, 2013-02-09 11:37 -- John Hawks

    A recent article in Scientific American by Robert Martone explains some recent research on how fetal cells become integrated into mothers' brains for the long term: "Scientists Discover Children’s Cells Living in Mothers’ Brains"

    In this new study, scientists observed that microchimeric cells are not only found circulating in the blood, they are also embedded in the brain. They examined the brains of deceased women for the presence of cells containing the male “Y” chromosome. They found such cells in more than 60 percent of the brains and in multiple brain regions. Since Alzheimer’s disease is more common in women who have had multiple pregnancies, they suspected that the number of fetal cells would be greater in women with AD compared to those who had no evidence for neurological disease. The results were precisely the opposite: there were fewer fetal-derived cells in women with Alzheimer’s. The reasons are unclear.

    Sometimes people wonder what HLA is really for. Once in a while, having someone else's cells inside you isn't quite as harmless as the case discussed here. Being able to recognize your own cells may be your only means of defense.

    The kind of microchimerism described here lasts throughout a woman's postreproductive lifespan. The strength of selection varies across this timeframe. It was logical to hypothesize that the cells might have negative side effects on fitness, such as Alzheimer's risk, that manifest late in life. Mothers must suppress their immune responses to some extent during pregnancy, to avoid health risks to the developing embryo and fetus. That suppression cannot be cost-free; if it were, we would expect everybody to tolerate human foreign bodies as well as expectant mothers. Having roaming stem cells integrate themselves into neural tissue must not be good on average; if it were, we would have cells crawling their way into our brains all the time.

    I bet those cells worm their way into the brain so that your mother will love you better. The only thing wrong with that hypothesis is that it can't explain grandmas.

  • A new approach to the Prisoner's Dilemma

    Sun, 2012-07-08 15:31 -- John Hawks

    Daniel Lende has described some evolutionary and anthropological import of a recent paper in PNAS on game theory: "Prisoner’s Dilemma and the Evolution of Inequality – Does Unfairness Triumph After All?".

    The paper, by William Press and Freeman Dyson [1], proves that a range of strategies exist for the classic "iterated Prisoner's Dilemma" game that actually allow one player to dominate and determine the payoffs for the other player over the long term. A long history of theory had argued that symmetrical outcomes were stable because one player could always punish another who was trying to impose an unfair outcome. The difference in the current result comes from the mathematical recognition that one player could completely determine the payoffs for the other, over the long term.

    What is surprising is not that Y can, with X’s connivance, achieve scores in this range, but that X can force any particular score by a fixed strategy p, independent of Y’s strategy q. In other words, there is no need for X to react to Y, except on a timescale of her own choosing. A consequence is that X can simulate or “spoof” any desired fitness landscape for Y that she wants, thereby guiding his evolutionary path. For example, X might condition Y’s score on some arbitrary property of his last 1,000 moves, and thus present him with a simulated fitness landscape that rewards that arbitrary property. (We discuss the issue of timescales further, below.)

    The paper deserves a longer commentary, and Lende has provided an interesting one. After considering some ways in which iterated Prisoner's Dilemma has been applied in evolutionary biology, such as life history theory, he suggests:

    In other words, zero-dimensional strategies are a way to think about facultative adjustments that organisms can make in reproductive and life history strategies.

    As just a thought to throw out there, might zero-dimensional approaches shed new light on the epidemiological transition? Has it made sense, where fitness pay-offs are high for offspring through investment and development, to invest more as a parent and thus set the highest set of pay-offs for a child?

    Much more at the link, which provocatively connects the short-term versus long-term strategy discussion in the paper to the emergence of wealth inequality in complex societies.

    Edge has a question-and-answer post with study author William H. Press: "On 'Iterated Prisoner's Dilemma contains strategies that dominate any evolutionary opponent'". The entire interview is very interesting, here's an excerpt that highlights the connection between the reward-payoff game of Prisoner's Dilemma and actual flesh-and-blood evolution:

    Yes, Virginia, you can fool evolution. People do it all the time, nowadays, with directed evolution experiments that fool microbes into doing unnatural things. The trick is to keep adjusting the environment so that the “more fit” organism is the one that bends most to our (unnatural) goal. So, it’s not a surprise that these tricks exist in principle. What is a surprise is that they are so easily exemplified, mathematically, in a game as simple as Iterated Prisoner’s Dilemma – and that this was mathematically obscure enough to escape notice. Do these tricks exist in all mathematical games? Do they exist in reallife competitive scenarios? When both players have a theory of mind (that is, are not just evolving to maximize their own score), are all games, in some deep way, actually Ultimatum Games? These now seem to be interesting questions.

    Personally, I think the Prisoner's Dilemma has been overemphasized in the discussion of the evolution of human cooperation, as many kinds of social interactions in ancient hunter-gatherers would not have fit that dynamic. Nevertheless, we should revisit the literature and revise the assumption that cooperation emerged according to the Prisoner's Dilemma dynamic. In this regard, the most interesting aspect of Press and Dyson's work may be the clear demonstration that short-term and long-term strategies bear a different relation than traditionally thought. Cognitive resources for individual discrimination, tracking of reputation, and memory of previous interactions have evolved over millions of years in primates, and their elaboration in humans may have happened in a very different context than imagined before last month.


    References

    1. Press WH, Dyson FJ. Iterated Prisoner's Dilemma contains strategies that dominate any evolutionary opponent. Proceedings of the National Academy of Sciences of the United States of America. 2012;109(26):10409-13.
  • Inclusive fitness works

    Wed, 2010-09-01 07:53 -- John Hawks

    I can't believe the amount of attention the paper by Martin Nowak, Corina Tarnita and Edward O. Wilson [1] has gotten. It was in last week's Nature. The basic idea was that the evolution of eusociality in insects could be explained in a different way that the usual explanation, which involves calculating the relatedness of worker insects to their reproductive siblings. Eusociality has been one of the most visible applications of inclusive fitness theory -- that is, the observation that the fitness of a gene that alters behavior may be calculated in terms of its effects on the reproduction and survival of relatives. The paper notes that some aspects of eusociality are not well explained in terms of relatedness, and derives an alternative explanation.

    The weird part of the paper is the way it describes inclusive fitness as some kind of theoretical afterthought, useful only as an ad hoc explanation for eusocial insects. It contrasts the inclusive fitness concept with "standard natural selection" as if it were possible for organisms to erase the fact that they're related to each other! And the authors imply that they have fatally damaged the concept of kin selection.

    It's so contrary to evolutionary theory, that I thought maybe I was missing something. But I've been spending time on another problem this week and haven't had time to follow it up.

    Fortunately, Jerry Coyne and Richard Dawkins have both given the paper some attention, and written notes and reactions to it. First Coyne ("A misguided attack on kin selection") reminds us of why kin selection has been such a successful part of "standard" evolutionary theory for the past fifty years.

    Sex ratio theory, in which mothers produce different proportions of males and females, has been a particularly fruitful area for applying inclusive fitness theory. So has “altruism”—suicidal honeybees are just one example. And so are parental care and aspects thereof, especially parent-offspring conflict, a field brought to life by Bob Trivers using inclusive fitness theory. How else can you explain weaning conflict except by a conflict between the mother’s genetic welfare and that of her offspring?

    I’m baffled not only by Nowak et al.’s apparent and willful ignorance of the literature, but by statements that are just wrong. They flatly assert, for instance, that “inclusive fitness theory” is something different from “standard natural selection theory.” But it’s not: it’s simply a natural extension of population genetics to the situation in which one’s behavior affects related individuals.

    Richard Dawkins has also posted notes about the paper:

    Kin selection is not a subset of group selection, it is a logical consequence of gene selection. And gene selection is (everything that Nowak et al ought to mean by) 'standard natural selection' theory: has been ever since the neo-Darwinian synthesis of the 1930s. Inclusive fitness theory is not some kind of supernumerary excrescence, to be 'resorted to' only if 'standard natural selection theory' is found wanting (Misunderstanding One). On the contrary, inclusive fitness theory is one way of expressing what was logically inherent in the synthesis ever since Fisher and Haldane, but had been largely overlooked because people (with the exception of those two geniuses) didn't think about collateral kin.

    Yes, unless they're going to repeal the Price equation, they'll have to rely on relatedness to explain those phenotypes that never occur in reproductive individuals. As Dawkins puts it, "You have to talk about shared genes in individuals, with conditional phenotypic expression."


    References

    1. Nowak MA, Tarnita CE, Wilson EO. The evolution of eusociality. Nature [Internet]. 2010;466:1057–1062. Available from: http://dx.doi.org/10.1038/nature09205
  • Hangman strategy

    Thu, 2010-08-26 08:30 -- John Hawks

    You may have seen that story about "jazz" being the hardest Hangman word. Personally, I always figure that such a short word is hardly fair, but I'm not that good at Hangman. The inside story of how they figured out the hardest words is kind of interesting -- it involves a guy writing a Mathematica Demonstration to play Hangman and his daughter getting annoyed at never being able to beat the computer and its dictionary.

    (via Chad Orzel)

  • A Snowdrift game version of hunting

    Fri, 2009-06-05 23:39 -- John Hawks

    I want to run through some examples of how we can apply game theory to consider hunting decisions in human groups. First, I describe a simple Snowdrift model applied to hunting. This is part 2 of a series, part 1 introduces the topic of the Snowdrift game.

    A reader sent along a story after reading the first post:

    In reading your snowdrift blog post, I was reminded of an experiment that does not require game theory to understand. You may have heard of it. Two pigs are in a pen. One is dominant. To get food one of them presses a bar, but the food is dispensed at the other side of the pen. If the subdominant pig presses the bar, it gets no reward, as the dominant pig hogs the food, eating it all. The result is that the dominant pig presses the bar while the subdominant pig waits at the food trough. Then the dominant pig rushes over to the trough to push the subdominant pig aside. Both pigs get fed, but the dominant pig does all the work

    It's a great example of asymmetrical rewards. I'll get to those in the next few posts on this topic, because the asymmetries are very important to understanding dynamics in hunter-gatherers. But first, we have to describe the simple symmetrical case, including the algebra defining the evolutionarily stable equilibrium between the two simple strategies.

    Suppose we have two hunters, who will share whatever game either of them kills. A man may choose on a given day to hunt. By hunting, he suffers a cost c and brings back a large fixed benefit b for each man. The two men may both choose to hunt on the same day, resulting in the same benefit b but a lowered cost c∕2 for each man. The two men decide whether to hunt simultaneously and without conferring — that is, there is no information transfer between them that would affect their decisions.

    Here is the payoff matrix of the game for player 1 (choices on left) given the strategy selected by player 2 (on top):

    hunt no hunt
    hunt b - c∕2 b - c
    no hunt b 0

    Given the existence of the two strategies, “hunt” and “no hunt,” the ESS is the ratio at which the two strategies have equal expected returns. If individuals select a strategy and do not vary, the ESS represents the frequency of these variants in the population. If in contrast, individuals can choose to adopt either strategy, then the ESS also will be the optimal proportion of the two strategies in one individual’s repertoire. The two strategies will yield equal payoffs when the ESS satisfies the following equation, where p represents the proportion of “hunt” and 1 - p the proportion of “no hunt”:

    p(b- c∕2)+ (1- p)(b - c) = pb
    (1)

    …which simplifies to p = 2(b - c)(2b - c). That expression is positive where b > c, and approaches unity where c is very small relative to b. If in contrast b c then the scenario is the Prisoner’s Dilemma, where the only ESS is a pure “no hunt” strategy.

    Let’s also look at a slightly different case. As above, each man’s return from hunting will be b regardless of whether one man or both choose to hunt. But in the payoff matrix below, the cost of hunting is also the same whether one man or both choose to hunt. So there is no reduction in the cost of hunting if both men do it.

    hunt no hunt
    hunt b - c b - c
    no hunt b 0

    Now, in this case, the ESS satisfies the equation:

    p(b- c)+ (1- p)(b - c) = pb
    (2)

    Again, p is the frequency of the “hunt” strategy. This simplifies to p = (b-c)∕b, which again yields the Prisoner’s Dilemma when b < c.

    OK, that’s the simple Snowdrift game model, described in the language of hunting instead of winter car accidents. It is quite simplistic in many ways. We might expect real hunters to have successes and costs that vary as stochastic functions of the environment. A real hunter must decide whether to hunt based not only on the odds his companion will hunt, but also upon some appraisal of the companion’s likelihood of success. Men in hunting societies are not paired up by the buddy system, but instead make their decisions about hunting in the context of a larger group’s activities.

    Maybe most confusing, there are two possible kinds of currency in which benefits and costs may be expressed. A benefit from hunting may be most naturally measured in calories. If we average hunting returns across many episodes, then our result would be mean calories per day, or per hour of effort. Likewise, it might seem natural to discuss costs in terms of calories, as we might consider the cost of locomotion or cost of transport associated with foraging.

    But the only currency that matters to evolution is fitness. We cannot assume that maximizing caloric returns will maximize fitness. Transport and locomotor costs may be minor compared to the mortality risk from predation when foraging far from camp. The caloric benefits from hunting matter more to a starving child than to a satiated adult.

    So the measures of costs and benefits that define the ESS should be expressed in terms of fitness. That’s a problem, because fitness outcomes are a lot harder to measure than caloric returns. To figure out caloric expenditure and returns, you can measure oxygen consumption, work out distances, and weigh meat. To measure fitness, you have to record lifetime reproduction. To assess the relationship between caloric returns and fitness, you need a lifetime of caloric returns.

    So far, hunter-gatherer demographic data and hunting returns are both known from a small number of transverse studies. Longitudinal data on hunter-gatherer demography are limited, and mostly known by retrospective methods — that is, informants share their knowledge about the history of their groups. The fitness effects of a single individual’s hunting effort over time are not known.

    If fitness outcomes are hard for the scientist to measure, they are equally hard for a social actor to predict. Even intelligent actors like humans know little about the effects of their actions upon their future reproduction. Men sometimes do poorly with information directly relevant to fitness, like “Is the child mine?” That’s not to say that men may not follow highly sophisticated strategies to allocate hunting effort. But we should develop explanations that do not assume that a man knows the fitness benefits and costs of his choices.

    Next: Life history and asymmetrical strategies

  • Snowdrift games, cooperation, and "tragedy of the commune"

    Tue, 2009-06-02 23:27 -- John Hawks

    It’s the second day of June, which means it’s a good time to consider snowdrifts. OK, maybe not – but at least we’re far enough from winter now that the thought of snowdrifts out the window isn’t enough to give me a chill.

    The Snowdrift Game is a theoretical model of cooperation within the context of game theory. I gave a short introduction to game theory a couple of years ago, focusing on the games of Chicken and the Prisoner’s Dilemma. There are really only two formal varieties of two-player games involving cooperation or defection in the absence of information transfer. When defection is always the optimal strategy, it’s the Prisoner’s Dilemma. When a mixed strategy of cooperation and defection is optimal, it’s Chicken.

    But there are other names for this game. I’m not sure why, exactly—I suppose it’s because teenage boys in dragsters don’t appeal to everybody. One familiar name is the Hawk-Dove game. An individual can adopt two strategies: either attack and fight for a resource, or share equally and retreat when attacked. In the game, fighting carries a high cost (like wrecking your car into somebody) so a mixed strategy is optimal. When hawks are common, it’s better to be a dove and avoid fighting. When doves are common, it’s better to be a hawk because you always win.

    A third name for this game is Snowdrift. Imagine you’re riding in a car that becomes stuck in a snowdrift. You and a fellow passenger share the same interest: you both want the snowdrift to be removed. But who’s going to get out and shovel? It might seem fair just to get out and shovel the snow together—in other words, to cooperate. But what if the other passenger just sits there and refuses to help? If the cost of shoveling is low compared to the benefit of getting out of the drift, it will be in your interest to shovel by yourself. Sure, the other passenger is a freeloader who shares the benefit undeservedly, but so what? If the cost of shoveling was too high for you to bear, you’d have refused to do it, letting both of you freeze there. That would be the Prisoner’s Dilemma. But if the cost of shoveling is low compared to the costs of doing nothing, then a mixed strategy will be optimal. As long as freeloaders aren’t too common, that strategy will pay off. So a population engaged in the Snowdrift game will come to a mixed proportion of shovelers and freeloaders.

    Doebeli et al. (2004) considered the Snowdrift game as a model for the evolution of cooperation. A mixed strategy of cooperation and defection can emerge under a Snowdrift game system of payoffs, which makes it very different from the Prisoner’s Dilemma. Remember that in the Prisoner’s Dilemma, defection always generates a higher payoff than cooperation, regardless of the opponent’s strategy. So stable cooperation can only evolve under a Prisoner’s Dilemma system of payoffs if some kind of information transfer is possible. One example is the Iterated Prisoner’s Dilemma, in which two players encounter each other repeatedly. In this circumstance, one player can punish defection, leading to conditional strategies — the most famous of which is “tit for tat” — that yield a positive payoff for cooperation. It is worth pointing out that the cumulative payoffs under “tit for tat” or other conditional strategies come to approximate the payoffs of the Snowdrift game. The transfer of information changes one payoff structure into another.

    Here, we have unveiled a different paradox of cooperation, which could be termed the ”tragedy of the commune”: In a cooperative system, in which every individual contributes to a common good and benefits from its own investment, selection does not always generate the evolution of uniform and intermediate investment levels but may instead lead to an asymmetric stable state, in which some individuals make high levels of cooperative investment and others invest little or nothing.

    In practice, it is often difficult to determine the payoffs in social interactions and hence to distinguish prisoner’s dilemma and snowdrift interactions [a phage system marks a rare exception, but interestingly, selection turns the prisoner’s dilemma into a snowdrift game (24)]. Nevertheless, the mere existence of high- and low-investing individuals has often been taken as prima facie evidence that the interaction is governed by a prisoner’s dilemma, with some additional mechanism, such as reciprocity, responsible for the co-existence of altruists and nonaltruists. The tragedy of the commune, however, provides a quite different and, in many ways, simpler explanation for the coexistence of high- and low-investing individuals, which potentially applies to a wide range of cooperative and communal enterprises in biological systems (Doebeli et al. 2004:861–862).

    How is this relevant to paleoanthropology? The last paragraph of the paper suggests one way:

    In behavioral ecology, classical examples of cooperation include collective hunting and territory defense in lions (28), predator inspection in sticklebacks (29), and alarm calls in meerkats (30). In theoretical discussions of these examples, the existence of cooperators providing a common good and defectors exploiting it has been assumed a priori. The tragedy of the commune, however, suggests an evolutionary mechanism for the emergence of distinct behavioral patterns with differing degrees of provisions to the common good. This mechanism may also apply to cultural evolution in human societies, in which large differences in cooperative contributions to communal enterprises could give rise to conflicts on the basis of accepted notions of fairness (Doebeli et al. 2004:862).

    Food sharing in human hunter-gatherers includes many asymmetries. For example, hunters differ greatly in their hunting returns and expenditure of effort. Yet good hunters tolerate the presence of poor hunters and share food with them. As with hunting but extended to both men and women, people invest greatly varying degrees of effort into gathering plant foods, with resulting variation in caloric returns. Some of the variation in investment and success is age-related, some is likely directly environmentally induced, and some may reflect frequency-dependent strategies.

    Over the next few days, I’ll be considering human hunting from the perspective of the Snowdrift game. I’ll start with some very simple deterministic models and then try to make them a bit more relevant by considering the effects of stochastic payoffs and asymmetries among players.

    Next: Defining the Snowdrift game for hunting

    References:

       Doebeli M, Hauert C, Killingback T. 2004. The evolutionary origin of cooperators and defectors. Science 306:859–862. doi:10.1126/science.1101456.

  • Thomas Schelling on military strategy and academia

    Sun, 2008-06-22 17:30 -- John Hawks

    Thomas Schelling, on page 8 of his The Strategy of Conflict (Amazon):

    Within the universities, military strategy in this country has been the preoccupation of a small number of historians and political scientists, supported on a scale htat suggests that deterring the Russians from a conquest of Europe is about as important as enforcing the antitrust laws.

    Strategy of Conflict was first published in 1960, and clearly matters changed by the second edition in 1980. By the time I was an undergraduate, I took a course in international politics from an old warhorse of a political scientist, who introduced me to game theory, mutually assured destruction, and the other fundamentals of Schelling's theses.

  • Reviewing frequency-dependent selection on MHC

    Tue, 2007-10-30 15:13 -- John Hawks

    Mystery Rays from Outer Space wrote earlier this month about the pattern of selection on MHC, bringing up the question of whether overdominance (heterozygote advantage) or frequency dependence is the reigning pattern. This post focuses on some evidence supporting the hypothesis of frequency dependence.

    Even on a short scale, alleles appear and disappear at a great rate. My favourite example of this is the map on the right 8 (I liked it so much I scanned it, years ago; I don't have access to the 1996 issues of Science on line. Click on the map for a larger version). This shows what happened to MHC diversity during the peopling of the Americas. You can see new alleles popping up down the migration route -- but the key point I want to make is made by the authors in a different paper: "Although many new HLA-B alleles have been produced in Latin America, their net effect has been to differentiate populations, not to increase allele diversity within a population."

    In other words, rare old MHC alleles are not selected, but disappear, while rare new alleles are selected. This is consistent with the predictions of frequency-dependent selection than of overdominance, I think. But there are also lots of strong arguments for overdominant selection, some of which I'll mention next time around.

    The post is notable for links back into the literature, and it will be interesting to see his next installment. Also in recent weeks he has posted a short review of the MHC molecules, and a look at how the structure of HLA-A2 was worked out.

    That figure shows a little bit of undefined, unresolved mist (in pink) in the middle of the reasonably well-defined HLA-A2 molecule. The location of that little bit of mist, and its very mistiness, were the stunning part of the paper.

    Oh, and a nice little post about MHC and the Tasmanian Devil tumor problem. That's a good one for Halloween.

    (via Sandwalk)

  • Nowak profiled

    Tue, 2007-07-31 21:56 -- John Hawks

    Carl Zimmer's profile of mathematical biologist Martin Nowak is well worth reading. Zimmer does a good job of describing the relevance of Nowak's modeling work, centered on the Prisoner's Dilemma:

    Dr. Nowak and his colleagues found that when they put players into a network, the Prisoner's Dilemma played out differently. Tight clusters of cooperators emerge, and defectors elsewhere in the network are not able to undermine their altruism. "Even if outside our network there are cheaters, we still help each other a lot," Dr. Nowak said. That is not to say that cooperation always emerges. Dr. Nowak identified the conditions when it can arise with a simple equation: B/C>K. That is, cooperation will emerge if the benefit-to-cost (B/C) ratio of cooperation is greater than the average number of neighbors (K).

    "It's the simplest possible thing you could have expected, and it's completely amazing," he said.

    This work branches out into cancer etiology and social dynamics, among other things. My students will be reminded that I think the Prisoner's Dilemma is overrated -- but that's a topic for another day...

    (not via Gene Expression, although Razib got there first!)

Pages

Subscribe to game theory

Neandertals

For years, I've worked on their bones. Now I'm working on their genes. Read more about the science studying these ancient people.

Denisova

From a finger bone of an ancient human came the record of a completely unexpected population. My lab is working on the science of the Denisova genome.

Acceleration

The advent of agriculture caused natural selection to speed up greatly in humans. We're uncovering some of the ways that populations have rapidly changed during the last 10,000 years.

Malapa

Just outside Johannesburg, the Malapa site is producing some of the most exciting finds in human evolution. This site is the headquarters of the Malapa Soft Tissue Project.