Evolutionary Dynamics and Networks

Evolutionary Dynamics

Evolutionary dynamics, also referred to as evolutionary game dynamics, describes how the frequencies of strategies of a game in an infinitely large population of players change with time, while these players interact randomly. While the classical game theory focuses on a single rational individual, who is engaged in a given game with another individual and has to decide between different strategies in order to maximize his payoff, the evolutionary dynamics focuses on the frequencies of strategies within the entire population of individuals playing the game.

Figure 1: Replicator dynamics of the rock-scissors-paper game

Taking a  control engineering perspective on the evolutionary dynamics, we can see that the strategies yielding high payoffs tend to spread, i.e., increase their frequency, within the population, while the payoffs depend on the action of other players and therefore on the frequency of strategies. This feed-back loop is the focus of our interest.

More than a century of research on the evolutionary dynamics falls into three different representations of the dynamics[1]: the quasi-species equation, the replicator equation, and the replicator-mutator equation. The quasi-species equation, the oldest and the simplest of all, describes the evolution of different strategies while assuming that the payoff is constant, i.e., the payoff does not depend on the frequency of strategies. This assumption of constant payoff is taken out in the replicator dynamics. Figure 1 above shows the replicator dynamics for the rock-scissors-paper game [2] where the three strategies cyclically dominate each other.

It should be noted that the replicator dynamics considers only the replication, but not the mutation which is the other important factor that drives evolution. The replicator-mutator equation on the other hand considers both replication and mutation [3]. Figure 2 below shows the replicator-mutator dynamics of a population with 50 strategies. The importance of mutation can be seen by comparing the two plots where a low mutation parameter leads to a complete collapse (all strategies have the same frequency) and a high mutation rate leads to behavioral flocking (a single dominant strategy emerges).

Figure 2: Replicator-mutator dynamics of a population with 50 strategies

Finite Populations: Although the above discussions were on games in infinitely large populations of agents, various frameworks exist to model and explore games in finite populations [10]. A huge importance is given to the concept and computation of fixation probabilities in the context of games in finite populations. In a game between two strategies, C and D (prisoner’s dilemma, C-cooperate D-defect), the fixation probability of C is given by the probability that strategy C will take over the whole population, starting with only one player with strategy C and all the other players playing strategy D. The concept of fixation probability allows biologists to determine how well certain populations are protected from the invasion by mutants.

Evolution and Graphs

Graphs/networks in the context of evolutionary dynamics can be used to represent two different concepts. The first concept that can be represented is the structure of the payoff matrix, where the nodes represent the strategies and the weighted edges represent the payoffs. In [4], the author focuses on a ring-lattice network and analyzes the influence of mutation parameter on the evolutionary dynamics.

Figure 3: Simulated scale-free network with preferential attachment and growth

The second concept  to represent via a graphs is the way each individual in the population interacts with others [5]. All three evolutionary dynamics discussed above assume that every individual in the population is connected to all the other individuals (well-mixed population) and can be expressed using a complete graph. This assumption of well-mixed population is not true in most of the real world evolutionary dynamics and becomes an obstacle in predicting the actual outcome of a evolutionary game. Authors in [6] focus on a population where each individual sits on the node of a k-degree infinite graph, i.e., each individual is connected to k other individuals. Although this move from a complete graph to a k-degree graph brings us somewhat closer, we still have a long walk to make in order to predict real-world evolutionary games. In [7–9] an extensive comparison is done between various network models that can be used to represent a real world network, such as the random network model, the small world model, and the scale-free model. The scale-free model where the degree of the nodes exhibits a power law distribution, is proposed to be the best to represent real-world networks such as the world wide web, joint research venture projects among firms, co-author relationships among academics, trade networks, social networks, and P2P(peer-to-peer). Figure 3 shows a simulated scale-free network of 500 nodes, where the red-nodes have a degree greater than 10.

Above discussed graphs can be used to represent various systems that exist in nature, such as interactions between members of an ecosystem, cellular architectures in various organisms, cultural evolution and the propagation of ideas in a social network [10]. 

Questions to be answered

1. What is the influence of mutation parameter and the payoff matrices (finite dimensional) in the emergence of dominant strategies ?
2. How to incorporate scale-free networks into the evolutionary dynamics ?

References

1. K. M. Page and M. A. Nowak, “Unifying evolutionary dynamics,” J. Theor. Biol., vol. 219, no. 1, pp. 93 – 98, 2002.
2. J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, 1998.
3. N. L. Komarova, “Replicator-mutator equation, universality property and population dynamics
   of learning,” J. Theor. Biol., vol. 230, no. 2, pp. 227 – 239, 2004.
4. R. Olfati-Saber, “Evolutionary dynamics of behavior in social networks,” in Proc. IEEE Conf. Dec. Contr., (New Orleans, LA), pp. 4051–4056, December 2007.
5. E. Lieberman, C. Hauert, and M. A. Nowak, “Evolutionary dynamics on graphs,” Nature, vol. 433, no. 7023, pp. 312–316, 2005.
6. H. Ohtsuki and M. A. Nowak, “The replicator equation on graphs,” J. Theor. Biol., vol. 243, pp. 86–97, 2006.
7. M. O. Jackson and B. W. Rogers, “The strategic formation of large networks: When and why
   do we see power laws and small worlds?,” in Proc. P2P Conf., May 2004.
8. R. Guimera, B. Uzzi, J. Spiro, and L. A. N. Amaral, “Team assembly mechanisms determine
   collaboration network structure and team performance,” Science, vol. 308, no. 5722, pp. 697–702, 2005.
9. A. L. Barabasi, “SOCIOLOGY: Network theory-the emergence of the creative enterprise,”
   Science, vol. 308, no. 5722, pp. 639–641, 2005.
10. M. A. Nowak, Evolutionary dynamics: exploring the equations of life, Harvard University Press, 2006.