New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Evolutionary dynamics in set structured populations

Communicated by Robert May, University of Oxford, Oxford, United Kingdom, April 2, 2009 (received for review February 8, 2009)
Abstract
Evolutionary dynamics are strongly affected by population structure. The outcome of an evolutionary process in a wellmixed population can be very different from that in a structured population. We introduce a powerful method to study dynamical population structure: evolutionary set theory. The individuals of a population are distributed over sets. Individuals interact with others who are in the same set. Any 2 individuals can have several sets in common. Some sets can be empty, whereas others have many members. Interactions occur in terms of an evolutionary game. The payoff of the game is interpreted as fitness. Both the strategy and the set memberships change under evolutionary updating. Therefore, the population structure itself is a consequence of evolutionary dynamics. We construct a general mathematical approach for studying any evolutionary game in set structured populations. As a particular example, we study the evolution of cooperation and derive precise conditions for cooperators to be selected over defectors.
Human society is organized into sets. We participate in activities or belong to institutions where we meet and interact with other people. Each person belongs to several sets. Such sets can be defined, for example, by working for a particular company, living in a specific location, going to certain restaurants, or holding memberships at clubs. There can be sets within sets. For example, the students of the same university have different majors, take different classes, and compete in different sports. These set memberships determine the structure of human society: they specify who meets whom, and they define the frequency and context of meetings between individuals.
We take a keen interest in the activities of other people and contemplate whether their success is correlated with belonging to particular sets. It is therefore natural to assume that we do not only imitate the behavior of successful individuals, but also try to adopt their set memberships. Therefore, the cultural evolutionary dynamics of human society, which are based on imitation and learning, should include updating of strategic behavior and of set memberships. In the same way as successful strategies spawn imitators, successful sets attract more members. If we allow set associations to change, then the structure of the population itself is not static, but a consequence of evolutionary dynamics.
There have been many attempts to study the effect of population structure on evolutionary and ecological dynamics. These approaches include spatial models in ecology (1–8), viscous populations (9), spatial games (10–15), and games on graphs (16–19).
We see “evolutionary set theory” as a powerful method to study evolutionary dynamics in structured populations in the context where the population structure itself is a consequence of the evolutionary process. Our primary objective is to provide a model for the cultural evolutionary dynamics of human society, but our framework is applicable to genetic evolution of animal populations. For animals, sets can denote living at certain locations or foraging at particular places. Any one individual can belong to several sets. Offspring might inherit the set memberships of their parents. Our model could also be useful for studying dispersal behavior of animals (20, 21).
Let us consider a population of N individuals distributed over M sets (Fig. 1). Individuals interact with others who belong to the same set. If 2 individuals have several sets in common, they interact several times. Interactions lead to payoff from an evolutionary game.
The payoff of the game is interpreted as fitness (22–26). We can consider any evolutionary game, but at first we study the evolution of cooperation. There are 2 strategies: cooperators, C, and defectors, D. Cooperators pay a cost, c, for the other person to receive a benefit, b. Defectors pay no cost and provide no benefit. The resulting payoff matrix represents a simplified Prisoner's Dilemma. The crucial parameter is the benefittocost ratio, b/c. In a wellmixed population, where any 2 individuals interact with equal likelihood, cooperators would be outcompeted by defectors. The key question is whether dynamics on sets can induce a population structure that allows evolution of cooperation.
Individuals update stochastically in discrete time steps. Payoff determines fitness. Successful individuals are more likely to be imitated by others. An imitator picks another individual at random, but proportional to payoff, and adopts his strategy and set associations. Thus, both the strategy and the set memberships are subject to evolutionary updating. Evolutionary set theory is a dynamical graph theory: who interacts with whom changes during the evolutionary process (Fig. 2). For mathematical convenience we consider evolutionary game dynamics in a Wright–Fisher process with constant population size (27). A frequencydependent Moran process (28) or a pairwise comparison process (29), which is more realistic for imitation dynamics among humans, give very similar results, but some aspects of the calculations become more complicated.
The inheritance of the set memberships occurs with mutation rate v: with probability 1 − v, the imitator adopts the parental set memberships, but with probability v a random sample of new sets is chosen. Strategies are inherited subject to a mutation rate, u. Therefore, we have 2 types of mutation rates: a set mutation rate, v, and a strategy mutation rate, u. In the context of cultural evolution, our mutation rates can also be seen as “exploration rates”: occasionally, we explore new strategies and new sets.
We study the mutationselection balance of cooperators versus defectors in a population of size N distributed over M sets. In the supporting information (SI) Appendix, we show that cooperators are more abundant than defectors (for weak selection and large population size) if b/c > (z − h)/(g − h). The term z is the average number of sets 2 randomly chosen individuals have in common. For g we pick 2 random, distinct, individuals in each state; whether they have the same strategy, we add their number of sets to the average, otherwise we add 0; g is the average of this average over the stationary distribution. For understanding h we must pick 3 individuals at random: then h is the average number of sets the first 2 individuals have in common given that there is a nonzero contribution to the average only if the latter 2 share the same strategy. We prove in the SI Appendix that for the limit of weak selection these 3 quantities can be calculated from the stationary distribution of the stochastic process under neutral drift. Our calculation uses arguments from perturbation theory and coalescent theory that were first developed for studying games in phenotype space (30).
Analytical calculations are possible if we assume that each individual belongs to K out of the M sets. We obtain exact results for any choice of population size and mutation rates (see SI Appendix). For large population size N and small strategy mutation rate, u, the critical benefit to cost ratio is given by
Here, we introduced the parameter ν = 2Nv, which denotes an effective set mutation rate scaled with population size: it is twice the expected number of individuals who change their set memberships per evolutionary updating. Eq. 1 describes a Ushaped function of ν. If the set mutation rate is too small, then all individuals belong to the same sets. If the set mutation rate is too large, then the affiliation with individual sets does not persist long enough in time. In both cases, cooperators have difficulties to thrive. But there exists an intermediate optimum set mutation rate which, for K ≪ M is given by ν_{opt} =
Let us generalize the model as follows: As before, defectors always defect, but now cooperators only cooperate, if they have a certain minimum number of sets, L, in common with the other person. If a cooperator meets another person in i sets, then the cooperator cooperates i times if i ≥ L; otherwise cooperation is not triggered. L = 1 brings us back to the previous framework. Large values of L mean that cooperators are more selective in choosing with whom to cooperate. Interestingly, it turns out that this generalization leads to the same results as before, but K is replaced by an “effective number of set memberships,” K*, which does not need to be an integer and can even be <1 (see SI Appendix). In Table 1, we show K* and the minimum b/c ratio for a fixed total number of sets, M, and for any possible values of K and L. For any given number of set memberships, K, larger values of L favor cooperators. We observe that belonging to more sets, K > 1, can facilitate evolution of cooperation, because for given M the smallest minimum b/c ratio is obtained for K = L = M/2.
In Fig. 3, we compare our analytical theory with numerical simulations of the mutationselection process for various parameter choices and intensities of selection. We simulate evolutionary dynamics on sets and measure the frequency of cooperators averaged over many generations. Increasing the benefittocost ratio favors cooperators, and above a critical value they become more abundant than defectors. The theory predicts this critical b/c ratio for the limit of weak selection. We observe that for decreasing selection intensity the numerical results converge to the theoretical prediction.
Our theory can be extended to any evolutionary game. Let A and B denote 2 strategies whose interaction is given by the payoff matrix [(R, S),(T, P)]. We find that selection in set structured populations favors A over B provided σR + S > T + σP. The value of σ is calculated in the SI Appendix. A wellmixed population is given by σ = 1. Larger values of σ signify increasing effects of population structure. We observe that σ is a onehumped function of the set mutation rate, ν. The optimum value of ν, which maximizes σ, is close to
Suppose A and B are 2 Nash equilibrium strategies in a coordination game, defined by R > T and P > S. If R + S < T + P, then B is riskdominant. If R > P then A is Pareto efficient. The wellmixed population chooses risk dominance, but if σ is large enough, then the set structured population chooses the efficient equilibrium. Thus, evolutionary dynamics on sets can select efficient outcomes.
We have introduced a powerful method to study the effect of a dynamical population structure on evolutionary dynamics. We have explored the interaction of 2 types of strategies: unconditional defectors and cooperators who cooperate with others if they are in the same set or, more generally, if they have a certain number of sets in common. Such conditional cooperative behavior is supported by what psychologists call social identity theory (31). According to this idea people treat others more favorably, if they share some social categories (32). Moreover, people are motivated to establish positive characteristics for the groups with whom they identify. This implies that cooperation within sets is more likely than cooperation with individuals from other sets. Social identity theory suggests that preferential cooperation with group members exists. Our results show that it can be adaptive if certain conditions hold. Our approach can also be used to study the dynamics of tag based cooperation (33–35): some of our sets could be seen as labels that help cooperators to identify each other.
In our theory, evolutionary updating includes both the strategic behavior and the set associations. Successful strategies leave more offspring, and successful sets attract more members. We derive an exact analytic theory to describe evolutionary dynamics on sets. This theory is in excellent agreement with numerical simulations. We calculate the minimum benefittocost ratio that is needed for selection to favor cooperators over defectors. The mechanism for the evolution of cooperation (36) that is at work here is similar to spatial selection (10) or graph selection (17). The structure of the population allows cooperators to “cluster” in certain sets. These clusters of cooperators can prevail over defectors. The approach of evolutionary set theory can be applied to any evolutionary game or ecological interaction.
Acknowledgments
This work was supported by the John Templeton Foundation, the National Science Foundation/National Institutes of Health joint program in mathematical biology (National Institutes of Health Grant R01GM078986), the Japan Society for the Promotion of Science, and J. Epstein.
Footnotes
 ^{1}To whom correspondence should be addressed. Email: martin_nowak{at}harvard.edu

Author contributions: C.E.T., T.A., H.O., and M.A.N. performed research and wrote the paper.

The authors declare no conflict of interest.

This article contains supporting information online at www.pnas.org/cgi/content/full/0903019106/DCSupplemental.
References
 ↵
 MacArthur RH,
 Wilson EO
 ↵
 Levins R
 ↵
 Levin SA,
 Paine RT
 ↵
 ↵
 Durrett R,
 Levin SA
 ↵
 ↵
 Tilman D,
 Kareiva P
 ↵
 ↵
 ↵
 ↵
 Killingback T,
 Doebeli M
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 ↵
 Maynard Smith J
 ↵
 Colman AM
 ↵
 Hofbauer J,
 Sigmund K
 ↵
 Cressman R
 ↵
 Nowak MA,
 Sigmund K
 ↵
 ↵
 ↵
 ↵
 Antal T,
 Ohtsuki H,
 Wakeley J,
 Taylor PD,
 Nowak MA
 ↵
 ↵
 Yamagishi T,
 Jin N,
 Kiyonari T
 ↵
 Riolo RL,
 Cohen MD,
 Axelrod R
 ↵
 Traulsen A,
 Claussen JC
 ↵
 ↵
 Nowak MA
Citation Manager Formats
More Articles of This Classification
Biological Sciences
Evolution
Related Content
 No related articles found.
Cited by...
 Stationary frequencies and mixing times for neutral drift processes with spatial structure
 The ecology and evolution of social behavior in microbes
 Computational complexity of ecological and evolutionary spatial dynamics
 Ecological Populations of Bacteria Act as Socially Cohesive Units of Antibiotic Production and Resistance
 Multiple strategies in structured populations
 Human strategy updating in evolutionary games