Algorithms, games, and evolution

Abstract

Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced the whole of Life as we see it around us. There is a computational way to articulate the same amazement: "What algorithm could possibly achieve all this in a mere three and a half billion years?" In this paper we propose an answer: We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of sex become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known in computer science to be surprisingly powerful and versatile. MWUA maximizes a tradeoff between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution.

Keywords: coordination games; learning algorithms.

Fig. 1.

Equations of population genetics formulated in the 1930s constitute the standard mathematical way of understanding evolution of a species by tracking the frequencies of various genotypes in a large population. In the simple example shown here, a haploid organism with two genetic loci A and B has three alleles in each of its two loci named A1, A2, A3 and B1, B2, B3 for a total of nine genotypes. In A we show the fitness of each genotype, that is, its expected number of offspring. The fitness numbers shown in A are all close to each other, reflecting weak selection, where the individual alleles’ contributions to fitness are typically minuscule. Initially, each genotype occurs in the population with some frequency; in this particular example these numbers are initially equal (B); naturally, their sum over all nine genotypes is 1 (frequencies are truncated to the fourth decimal digit). C shows how the genotype frequencies evolve in the next generation: each individual of a given genotype produces a number of offspring that is proportional to its fitness shown in A, and the resulting offspring inherits the alleles of its parents with equal probability (because we are assuming, crucially, sexual reproduction). The genotype frequencies in the next generation are shown in C, calculated through the standard recurrence equations of population genetics. We also show in the margins of the table the allele frequencies, obtained by adding the genotype frequencies along the corresponding row or column. Ten generations later, the frequencies are as shown in D.

Fig. 2.

A simple coordination game is played by two players: the row player, who chooses a row, and the column player, who chooses a column. After the two players make a choice, they both receive (or both pay, in case of a negative entry) the same amount of money, equal to the number at the chosen row and column (A). Coordination games are the simplest possible kind of a game, one in which the strategic interests of all players are completely aligned—that is to say, there is no conflict at all. They are of interest when it is difficult for the players to know these numbers, or to communicate and agree on a mutually beneficial combination (in this example, third row and second column). Notice that this particular coordination game is closely related to the fitness landscape shown in Fig. 1A: If P is a payoff in this game, the corresponding entry of Fig. 1A is equal to 1 + ε ⋅ P, where ε is a small parameter here taken to be 0.01. Suppose that each of the two players chooses each of the three options with some probability, initially $1/3$ for all (B); in game theory such probabilistic play is called a mixed action. How do we expect these probabilities to change over repeated play? One famous recipe is the MWUA, in which a player “boosts” the probability of each option by multiplying it by 1 + εG, where G is the expected amount of money this option is going to win the player in the current round of play, and ε is the same small parameter as above. For example, the second action of the row player has G equal to 2 (the average of 3, −1, and 4), and so the probability of playing the second row will be multiplied by 1.02. Then these weights are “renormalized” so they add up to 1, yielding the marginal probabilities shown in C. The probabilities after 10 such rounds of play are shown in D. Comparing now the numbers in the margins of Figs. 1D and 2D, we notice that they are essentially the same. This is what we establish mathematically in this paper: the two processes—repeated coordination games played through multiplicative updates, and evolution under weak selection—are essentially identical. This conclusion is of interest because the MWUA is known in computer science to be surprisingly powerful.