The Red King effect: When the slowest runner wins the coevolutionary race
See allHide authors and affiliations

Edited by Brian Skyrms, University of California, Irvine, CA, and approved November 12, 2002 (received for review August 16, 2002)
Abstract
Mutualisms provide benefits to those who participate in them. As a mutualism evolves, how will these benefits come to be allocated among the participants? We approach this question by using evolutionary game theory and explore the ways in which the coevolutionary process determines the allocation of benefits in mutualistic interactions. Motivated by the Red Queen theory, which states that coevolutionary processes favor rapid rates of evolution, we pay particular attention to the role of evolutionary rates in the establishment of mutualism and the partitioning of benefits among mutualist partners. We find that, contrary to the Red Queen, in mutualism evolution the slowly evolving species is likely to gain a disproportionate share of the benefits. Moreover, population structure serves to magnify the advantage to the slower species.
When individuals of two different species engage in a mutualistic interaction, both benefit; and yet certain changes in the interaction might offer additional benefits to one species or the other (or even to both). To understand how beneficial interspecific associations evolve and are maintained, we need to answer two basic questions. First, we need to know how interspecific cooperation can persist over evolutionary time, and what keeps the interaction from breaking down as individuals succumb to incentives to “cheat” on their partners. Second, given that cooperation is somehow maintained, we need to know how the resulting benefits will be allotted to the participants. To date, theoretical work on the evolution of mutualism has focused almost exclusively on the former question. In this paper, we use evolutionary game theory to address the latter one: how does the evolutionary process distribute the benefits of mutualism?
In some cases, the mechanics of an interaction may dictate an obvious allocation of benefits. Consider the mutualistic interactions in which a cleaner wrasse Labroides dimidiatus removes parasites from a larger “client” fish (1). In an idealized interaction where there is no potential for cleaners to feed on live tissue or for clients to prey on cleaners (2, 3), the actual allocation of benefits will be relatively straightforward. The wrasse receives access to a ready food source, and the client enjoys a reduced parasite load (4).
In other situations, the mechanics of the interaction fail to single out any one specific way to parcel up the benefits. In the wellstudied antlycaenid butterfly mutualism (5), ants protect caterpillars from parasitoids. As parasitism is a huge contributor to mortality, antassociated caterpillars enjoy enormous increases in survivorship to and during pupation (6). As an incentive for continued protection, the caterpillars take on substantial energetic and fitness costs to provide their ant attendants with sugar and proteinrich exocrine secretions (7, 8). But as a mutualism evolves, how much nutrient provisions will lycaenid caterpillars offer to the ants? And how much should the ants “demand” in return for tending to the caterpillars? No single salient solution stands out, and indeed the level of nutrient provisioning appears to be subject to contextdependent finetuning by the caterpillars (9). Like the aforementioned lycaenids, species ranging from aphids and treehoppers to acacia bushes have developed mutualistic associations with ants in which food is exchanged for defense (10, 11). In each of these systems, similar questions about allocating benefits arise. Other mutualisms that lack an obvious way of parceling up benefits include plant–pollinator interactions, symbioses between insects and gut microbes, and endosymbioses.
In our efforts to understand how the benefits from a mutualism will be allocated, we will pay particular attention to the role of the relative evolutionary rates, and thus the rate of strategy change, of the species involved. Mutualist partners may evolve at different rates for a number of reasons, including differences in generation time, differences in the importance of the interaction, differences in population size, and differences in the amount of segregating genetic variation (12). Analogous asymmetries in the rate of strategy change may also arise when members of one species select strategies by learning instead of by genetic evolution. Whatever the source of asymmetry, differences in evolutionary rates are commonly thought to influence coevolutionary outcomes, though previous work in this area has eschewed mutualism in favor of antagonistic interactions, such as the contests that occur between predator and prey, between host and parasite, or among competitors for a common ecological resource. In these antagonistic relationships, coevolution is typically thought to select for accelerated evolution. Pairs of species become locked into arms races with each rushing to evolve the upper hand in the interaction. As a result of this Red Queen process (13), each species is forced to evolve ever more rapidly just to break even. In the words of Lewis Carroll, “it takes all the running you can do, to keep in the same place.”
Here, we concentrate on mutualism rather than antagonism. Can mutualisms, despite their cooperative elements, also be viewed as evolutionary races to outmaneuver the partner and win a greater share of the surplus? Previous authors have argued that the answer is yes: the Red Queen effect should operate under these circumstances as well (14). Just as antagonists are forced to evolve rapidly to avoid falling behind in the struggle with their competitors, we might expect that mutualists will need to evolve rapidly to avoid being exploited and ultimately parasitized by their partners. In light of these predictions, our results are surprising: we find that in contrast to the Red Queen theory, mutualistic interactions often favor slow rates of evolution.
Methods and Models
Throughout the present paper, we take the common approach (15) of treating mutualism as an evolutionary game in which players evolve strategies according to basic Darwinian (replicator) dynamics (16–18). Because previous studies have concentrated on explaining what factors prevent mutualism from breaking down into parasitism or other forms of exploitation, they have focused on games used to study the evolution of cooperation: the prisoner's dilemma, public goods games, and related scenarios. This body of work has shown how interspecific cooperation can be maintained by mechanisms such as reciprocal altruism (19–21), partner choice (22, 23), byproduct benefits or pseudoreciprocity (19, 24, 25), and various forms of sanctioning and partner control (26, 27).
In the present paper, we focus on a different matter: how the benefits will be distributed, given that mutualism can persist. Therefore, we will use a different class of models. Essentially, we need to select a model and a modeling framework that will allow us to explore the evolution of the individual strategies used in mutualistic interactions. The Nash equilibrium concept will not alone be sufficient; the relevant games of resource division typically have multiple Nash equilibria (28). Thus, we need to work within a dynamic modeling framework that allows us to compare among Nash equilibria. But how to do this? What form should we envision for the coevolutionary process by which these strategies are selected?
Because this space of possible strategies for interspecific interaction is enormous, and because dynamic evolutionary models can be difficult to apply to games with huge strategy spaces, we try to find a simpler discrete model that captures the essence of the problem of interest. Here, we use a oneshot 2 × 2 game. This modeling strategy is sometimes described as a minigames approach (29).
What is the essence of the problem of interest, in our case? We are interested in situations in which multiple Nash equilibria exist, but different players have different preferences over the set of equilibria. Thus, we use not a prisoner's dilemma with one Nash equilibrium, but rather a coordinationtype game with two Nash equilibria and no incentive to defect on a cooperative agreement once established. Each player can make a generous offer or a selfish offer, with the following payoff matrix. If both make selfish offers, the association breaks down and the players fail to generate the benefits that result from mutualism; each gets payoff 0. If one makes a generous offer and the other makes a selfish offer, the selfish player gets 2 units and the generous players gets 1. If both players make generous offers, each gets an amount k of the benefits. When k = 1, the game is in essence a minigame version of the Nash bargaining game (28, 30, 31), with strategies “demand 1” and “demand 2,” and an available total of 3 units. When k = 0, two generous offers leads to a coordination failure as severe as that resulting from two selfish offers: the players suffer a complete loss of the mutualistic benefits and the game is a standard battleofthesexes game. When k = 1.5, the game is a hawk–dove game. We stress that in this game neither strategy precludes mutualistic interaction entirely. Notice that (for k < 2) the equilibria lie on the main diagonal, and the symmetric behaviors on the offdiagonal.
Because we can add an arbitrary constant to any column of player 1's payoff matrix or any row of player 2's payoff matrix without changing the evolutionary dynamics as treated in the next section (18), this game serves as a general model of twobytwo games with two equilibria and symmetry in payoffs between the two players. (Although such changes to the payoff matrix do not alter the local dynamics considered in the section on local dynamics of mutualism, they do alter the degree to which an equilibrium favors one species or the other, and thus they will affect the higherlevel dynamics considered in the section on higherlevel population structure. For this reason we cannot follow the tradition of specifying the game using a payoff matrix with the diagonals normalized to zero.) With this model, we have a simple framework in which to pursue the problem of how the benefits are allocated. Obviously, our general approach could be extended to games with more Nash equilibria, for example n × n games, iterated games, signaling games, and so forth.
In an interspecific mutualism, the participants come from two separate populations of two separate species to engage in pairwise interactions. Thus we assume that the game described above is a twopopulation roleasymmetric game: the row player comes from one species and the column player comes from the other (16, 32).
Local Dynamics of Mutualism
In the Appendix, we derive the equations that describe the changes in strategy frequencies over evolutionary time, i.e., the replicator dynamics, for roleasymmetric games in which the players come from separate populations with evolutionary rates m and n, respectively. Where x is the frequency of selfish players in the species 2 population, y is the frequency of selfish players in the species 1 population, and x and y are the time derivatives, the dynamics for the game considered here are given by 1 We begin by looking at these dynamics when k = 1. Fig. 1 Left shows a set of evolutionary trajectories with strategy frequencies for individuals from species 1 on the y axis and strategy frequencies for individuals from species 2 on the x axis, under replicator dynamics with the two populations evolving at equal rates. With probability 1, the selfish strategy becomes fixed in one population and the generous strategy becomes fixed in the other. That is, almost every evolutionary trajectory ends at one of two dynamically stable equilibria: the upper left corner in which species 1 enjoys a majority of the benefits, or the lower right corner in which species 2 enjoys the majority share. The eventual endpoint is determined by the initial strategy frequencies; the set of all points from which the dynamics lead to a given equilibrium is called the domain of attraction of that equilibrium. The yellow line in Fig. 1 Left shows the separatrix between the two domains of attraction. All trajectories beginning at points on the same side of the yellow line lead to the same equilibrium.
We see from Fig. 1 Left that the ultimate distribution of the rewards from the mutualism will depend on the starting point, i.e., on the initial strategy frequencies in each species. Put simply, to predict with certainty where the system will finish, we need to know where it started. In the absence of such knowledge, one reasonable measure of the chance of reaching each equilibrium is simply the relative size of the corresponding domain of attraction. All else being equal, we might expect that equilibria with large domains of attraction will be reached more often than equilibria with small domains of attraction.
But what factors determine the sizes of the domains of attraction? We can use the replicator equations (Eq. 1) to map out the direction of evolution in each species, i.e., the direction of change of strategy frequencies at each point. We can qualitatively understand these dynamics by dividing the phase space into four regions: one in which evolutionary trajectories move up and to the right, one in which they move up and to the left, one down and to the right, and one down and to the left. The boundaries of these regions (indicated by the gray “crossover lines” in Figs. 1 and 2) are easily computed from the dynamics (Eq. 1) by setting first ẋ and then ẏ to 0 and solving. For the game treated here, these lines will be given by the equations x = (2 − k)/(3 − k) and y = (2 − k)/(3 − k). Fig. 1 shows how these regions shift with changes in the parameter k; the evolutionary rates m and n do not appear in these expressions.
In games of the basic form considered here, the separatrix between domains of attraction always runs from the lower left corner to the upper right one, through the intersection point of the crossover lines. Because the separatrix is composed of integral curves of the vector field corresponding to the replicator equations (Eq. 1), we can always find it by solving these equations with initial conditions arbitrarily close to the intersection of the crossover lines. Although the relative rates of evolution do not affect the position of the gray crossover lines, they do influence the shape of this separatrix, “bending” it as illustrated in Fig. 2. However, the upper left and the lower right quadrants each lie entirely to one side of the separatrix, and therefore changes in evolutionary rate cannot alter the terminus of any evolutionary trajectory beginning in either of these quadrants. Evolutionary rate will only affect the equilibrium reached for trajectories that begin in the lower left and upper right quadrants.
Depending on the payoffs of the game, changes in the shape of the separatrix can increase the domain of attraction around the equilibrium favoring the slower species or the one favoring the faster species. Fig. 2 shows the evolutionary trajectories for the game in which k = 1.5. Here the domain of attraction around the upper left equilibrium increases in size as the relative rate of evolution by species 1 decreases. That is, the slower that species 1 evolves, the higher chance it has of reaching its favored equilibrium. This is the first manifestation of what we call the Red King effect.
In the lower left quadrant, the ultimate resting place depends on which crossover line is reached first. When the horizontal line is reached first, the dynamics lead to the upper left; when the vertical is reached first, the dynamics lead to the lower right. The two species are, in effect, racing to reach the edges of that quadrant. Fast evolution by species 1 corresponds to predominantly vertical motion and thus most trajectories beginning in this quadrant first reach the horizontal crossover line, yielding the equilibrium favorable to species 1. Fast evolution by species 2 corresponds to predominantly horizontal motion, and causes most points in this quadrant to follow trajectories that terminate at the equilibrium favorable to species 2. In the limit as species 2 evolves arbitrarily faster than species 1, all points in the lower left quadrant lead to the equilibrium favorable to species 2.
In the upper right quadrant, the situation is precisely reversed. Again the ultimate resting place depends on which line is crossed first, but here each species does better to lose the race! In the limit as species 2 evolves faster than species 1, all points in the upper right quadrant lead to the equilibrium favorable to species 1.
Thus the effect of evolutionary rate on the size of the domains of attraction depends on the chance that the starting point is in the lower left quadrant versus the upper right quadrant. In effect, the rapidly evolving species “gets” the lower left quadrant and “loses” the upper right one. Fig. 3 summarizes this effect. As an aside, this phenomenon may explain a curious observation reported by Doebeli and Knowlton (20). In their simulations of mutualism evolution, based on an iterated prisoner's dilemma model, they found that the more slowly evolving species received higher payoffs (their figure 3C).
But what determines the quadrant in which the coevolutionary process is likely to begin? For one thing, the regions' sizes will matter. Simple calculations show that the equilibrium favoring the slowerevolving species will have a larger domain of attraction around its favored equilibrium whenever k > 1, whereas the fasterevolving species will have a larger domain of attraction when k < 1.
In this section, we have seen that the ultimate division of a mutualistic surplus depends on (i) the game payoffs, (ii) the evolutionary rates of the species involved, and (iii) the initial distribution of strategies used by each species. As yet, we have said little about the third item. Perhaps certain aspects of a nascent mutualism will tend to bring together players who initially make overly generous offers (favoring fast evolution) or those who make overly selfish ones (favoring slow evolution). Alternatively, higherlevel population structure and the dynamics of mixing or migration may weight some quadrants more highly than others as startingpoints of local coevolutionary interaction. We consider this possibility in the next section.
HigherLevel Population Structure
When potential mutualists come together in a given location, where do their initial strategy choices come from? If strategies are genetically specified or learned from parents, these initial strategies are presumably those that were used in individuals' natal patches. Thus we might do well to consider a higher level of population structure, in which the dynamical process considered in the previous section occurs in parallel in a number of local subpopulations or “patches,” each of which sends out migrants to join existing subpopulations or to found new ones. Such a process can be modeled in a number of different ways. Here we opt to work with a haystacktype model (33–35); other models can be expected to produce similar results. We will find that the higherlevel population structure accentuates the Red King effect, in that it gives rise to local patches that initially begin in the upper right quadrant, exactly where slow evolution is favored.
A basic haystack model works as follows. For each species, the global space is divided into local subpopulations. Each “season” begins with each patch containing a small number of founder individuals from each species. Within each patch during the course of a single season, strategy frequencies change according to the dynamics (Eq. 1), as characterized in the previous section. At the end of the season, the individuals from all patches disperse and new patches are formed of founders chosen at random from the larger ensemble. A new season begins and the process repeats.
We can model the population dynamics within a patch in a number of different ways that are consistent with the local dynamics. One very simple approach would be to assume that the payoff matrix specifies the relative population growth rates per generation. However, this would lead to unchecked exponential growth within each patch within each season.
Here we opt instead to use a model in which population sizes are internally regulated; the results are not appreciably different. We assume that over the course of a single season, each patch reaches some fixed carrying capacity for each species. For the ease of analysis, we will also assume that each season is sufficiently long that every local subpopulation reaches an equilibrium with respect to strategy frequencies. (This assumption is not essential to the dynamics at hand.) The carrying capacity within a patch reflects the “favored” or “disfavored” nature of the equilibrium. That is, the carrying capacity for species 1 is larger in a patch that reaches the equilibrium favored by species 1 than it is in a patch that reaches the equilibrium favored by species 2. Notice that the carrying capacities represent an additional set of assumptions about the ecological process operating within patches, and thus this model requires that we specify the carrying capacity ratios in addition to the payoff matrix which describes the dynamics of strategy frequency change.
The global population dynamics then proceed as follows. Beginning with initial frequencies y and x of individuals playing selfish in species 1 and 2 respectively, new patches with N individuals from each species are formed at random. That is, each new patch has species 1 and species 2 strategy frequencies independently drawn from binomial distributions with means y N and x N, respectively. During each season, strategy frequencies within each patch change according to the local dynamics. All patches end at one of the two equilibria; therefore, the fraction of patches at each equilibrium at the end of a season can be determined directly from the fraction of patches on each side of the separatrix at the start of that season. Final population sizes in each patch depend on which equilibrium is reached. Specifically, we let α be the ratio of the carrying capacity at the favored equilibrium to the carrying capacity at the disfavored equilibrium, for species 1. We let β be the equivalent ratio for species 2. This gives us the global frequencies of each strategy in each species. The starting patch distributions in the next season are then determined by binomial draw from these strategy frequencies. The entire process is then iterated until the global strategy frequencies reach an equilibrium.
Fig. 4 compares the domains of attraction under the local dynamics against the domains of attraction under the higherlevel population dynamics with initial subpopulations formed by random draw from the global strategy frequencies. Because k = 1, the domains of attraction are equal in size under the local dynamics; neither fast nor slow evolution is favored. Nonetheless, the global dynamics give the slowly evolving species a larger domain of attraction around its favored equilibrium.
Why does this happen? First consider the process by which a new patch is formed. Members arrive from other patches. Patches at the equilibrium where species 1 is favored, i.e., those in which species 1 is playing selfishly, have a higher carrying capacity for species 1 and thus produce more species 1 individuals than do patches in which species 2 is favored. Consequently, a majority of the individuals of each species in a newly formed patch are likely to be playing selfishly. That is, each newly formed patch is likely to begin with a set of strategy frequencies belonging to the shaded upper right quadrant in Fig. 3. We know that the local dynamics favor the slowly evolving species in this quadrant, because there both species are selected to “retreat” (evolutionarily) to more generous strategies. Obviously, the fastevolving species will be able to do so more quickly. Ironically this ultimately favors the slowly evolving species, which in turn has no need to retreat to generous behavior, and can instead play selfishly and receive the higher payoffs. Thus in each newly formed patch, the slowly evolving species will have a relative advantage.
We can visualize this argument as follows. If a proportion s of the patches reach the equilibrium that favors species 1, and a proportion 1 − s reach the equilibrium that favors species 2, then at the end of a season the proportion in the global pool of species 1 individuals playing the selfish strategy will be α s/(α s + (1 − s)), and the proportion of species 2 playing the selfish strategy will be β(1 − s)/(β(1 − s) + s). Thus, at the end of a season, the strategy frequencies in the global pool will lie somewhere along the curve depicted in Fig. 5. This curve passes through the upper right quadrant, where slow evolution is favored, and not through the lower left one, where fast evolution is favored.
Viewed in this way, the global dynamics describe a mapping from this path onto itself; each season represents an iteration of this mapping. Fig. 6 depicts this mapping for a case in which k = 1 (and thus the local dynamics favor neither fast nor slow evolution) and in which species 1 evolves 8fold faster than species 2. From this figure, we see that the global dynamics has three equilibria: a stable equilibrium where all subpopulations are at the equilibrium favoring species 1, a stable equilibrium where all subpopulations are at the equilibrium favoring species 2, and an unstable equilibrium where roughly 27% of the subpopulations are at the equilibrium favoring species 2. The domains of attraction of the global dynamics are determined by the location of this unstable equilibrium point. To the left (lower frequencies of subpopulations favoring species 2) the global dynamics will ultimately converge to the first stable equilibrium. To the right, the global dynamics will converge to the second stable equilibrium. Because of these higherlevel dynamics, the slowly evolving species has a substantially larger domain of attraction around its favored equilibrium.
Conclusions
In this paper, we have looked at how the benefits that result from mutualism will be allocated among the participants. We have paid particular attention to the role of evolutionary rate in determining coevolutionary outcomes, and we have described why, contrary to the Red Queen hypothesis, slow evolution may actually lead to favorable outcomes.
Our results make intuitive sense in light of economic bargaining theory. In bargaining games, there may be a strategic advantage to “having one's hands tied” during the bargaining process (36, 37). If a player's options are limited, threats made by this player can become more credible and at the same time threats against this player can be rendered ineffective. Because susceptibility to threats often acts as a major determinant of the strength of one's bargaining position, this is a significant advantage.
The Red King effect described in this paper can be seen as a manifestation of this principle. If we envision the coevolutionary process as an extended negotiation in which the risk of a breakdown of cooperation serves as a threat imposed by one species on another, we might argue that the slowly evolving species has its hands tied in the negotiating process. Fast evolution does not allow a species to outrun a partner, it simply causes this species to yield to whatever threats are made. This is captured by the local dynamics described in the section on the local dynamics of mutualism.
Of course, the initial proposals brought to the bargaining table by the negotiating parties will also have a major impact on the outcome. In the mutualism example considered here, if both species initially ask for more than their share of the proverbial pie, susceptibility to threat will be important. But what will be the initial proposals that the species bring to the table? We have argued that in coevolutionary interactions, population structure bears critically on this question. If new patches are formed by immigrants from other patches, individuals will come together prepared by evolution to pursue a division similar to that which they were receiving in their previous patches. In the section on higherlevel population structure, we show that when the carrying capacity of a patch is affected by the division of the mutualistic surplus, most players entering a new patch will arrive “demanding” more than half of the benefits. This circumstance (when the parties do not initially agree on how to proceed because both expect an allocation that favors them rather than their partner) is when the Red King effect operates. This circumstance is precisely when it pays to evolve slowly.
Acknowledgments
We thank Naomi Pierce and Larry Samuelson for extensive and valuable discussion, and we gratefully acknowledge the assistance provided by Eric Alden Smith and the other participants of the 2002 Dahlem workshop on Genetic and Cultural Evolution of Cooperation. The editor and two anonymous referees greatly improved the manuscript with their helpful suggestions. The Santa Fe Institute provided generous support and hospitality.
Appendix
For a twobytwo roleasymmetric game with moves (U, D) and (L, R) for players 1 and 2, respectively, the basic form of the discretetime replicator dynamics for players coming from separate populations is given below (38). Here, x_{t} is the frequency of L players in population 1 at time t and y_{t} is the frequency of U players in population 2 at t. The function π(D, z) is the payoff to choosing strategy D when a fraction z of the other population plays strategy L. We represent differing evolutionary rates by assuming that during a given timestep, a fraction m of one population and n of the other have fitnesses affected by the payoffs from the interaction: From this, we can derive at least two different continuoustime approximations, which differ by a normalizing factor and can diverge in their dynamic behavior. Weibull (17) and Hofbauer and Sigmund (18) provide detailed discussions of their derivations and differences. Here we consider what would happen in a small timestep, during which only a fraction δ of the players even play the game at all: The timederivatives ẋ and ẏ are lim_{δ→0}[(x_{t+δ} − x_{t})/δ] and lim_{δ→0}[(y_{t+δ} − y_{t})/δ] 2 These are simply the “standard” (i.e., nonnormalized) continuoustime replicator dynamics for a roleasymmetric game (17), weighted by the appropriate evolutionary rates.
Footnotes

↵† To whom correspondence should be addressed. Email: cbergst{at}u.washington.edu.

This paper was submitted directly (Track II) to the PNAS office.
 Received August 16, 2002.
 Copyright © 2003, The National Academy of Sciences
References
 ↵
 Côté I M
 ↵
 ↵
 ↵
 ↵
 Dugatkin L A
 Pierce N E
 ↵
 ↵
 Baylis M,
 Pierce N E
 ↵
 ↵
 Agrawal A A,
 Fordyce J A
 ↵
 Janzen D H
 ↵
 Huxley C R,
 Cutler D F
 Cushman J H,
 Addicott J F
 ↵
 Dawkins R,
 Krebs J R
 ↵
 Van Valen L
 ↵
 ↵
 ↵
 Maynard Smith J
 ↵
 Weibull J W
 ↵
 Hofbauer J,
 Sigmund K
 ↵
 ↵
 Doebeli M,
 Knowlton N
 ↵
 ↵
 ↵
 Ferriere R,
 Bronstein J L,
 Rinaldi S,
 Law R,
 Gauduchon M
 ↵
 ↵
 ↵
 ↵
 West S A,
 Kiers E T,
 Simms E L,
 Denison R F
 ↵
 ↵
 Sigmund K,
 Hauert C,
 Nowak M A
 ↵
 ↵
 Skyrms B
 ↵
 ↵
 ↵
 ↵
 Schelling T C
 ↵
 Osborne M J,
 Rubinstein A
 ↵
 Samuelson L