## Abstract

In this paper, we investigate evolutionary games with the invasion process updating rules on three simple non-directed graphs: the star, the circle and the complete graph. Here, we present an analytical approach and derive the exact solutions of the stochastic evolutionary game dynamics. We present formulae for the fixation probability and also for the speed of the evolutionary process, namely for the mean time to absorption (either mutant fixation or extinction) and then the mean time to mutant fixation. Through numerical examples, we compare the different impact of the population size and the fitness of each type of individual on the above quantities on the three different structures. We do this comparison in two specific cases. Firstly, we consider the case where mutants have fixed fitness *r* and resident individuals have fitness 1. Then, we consider the case where the fitness is not constant but depends on games played among the individuals, and we introduce a ‘hawk–dove’ game as an example.

## 1. Introduction

Evolutionary dynamics models have been mainly studied on homogeneous infinite populations. However, real populations are neither homogeneously mixed nor infinite. In recent years, an interest in the study of evolutionary dynamics on spatial structures has been created. Spatial structures are described by graphs in which each individual is represented by a vertex and the connections between individuals are represented by edges, and we shall henceforth refer to this structure as the population structure. The *fixation probability* is the probability that a mutant introduced into a resident population eventually spreads over the whole population, replacing all resident individuals. In Lieberman *et al.* (2005), it was shown that under the Moran process the fixation probability of a single mutant on a graph where every vertex has the same degree (a regular graph) is given by the Moran probability,
1.1
for *r*≠1 (*P*_{Moran}=1/*N* if *r*=1), where *r* is the mutants’ (relative) fitness, resident individuals have fitness 1 and *N* denotes the population size.

The fixation probability on irregular graphs was considered in Broom & Rychtář (2008), in particular finding analytical expressions for the star and line graphs. It was shown that the fixation probability for a randomly placed advantageous mutant (*r*>1) was larger on both the line and the star than on a regular graph such as the complete graph or the circle.

In this paper, we study the stochastic evolutionary game dynamics of finite populations on three different structures: the star, the circle and the complete graph, all of which are commonly considered structures, in part owing to their symmetry and lack of complexity. The most commonly used evolutionary dynamics on graphs is the invasion process, alternatively known as the birth–death dynamics with selection on the birth, and this is the dynamics that we consider in this paper. In the invasion process, a randomly chosen resident individual is initially replaced by a mutant individual. In each of the next time steps, an individual is selected for reproduction with probability proportional to its fitness, i.e.
1.2
where *f*_{i} denotes the fitness of individual *i*. Then, the chosen individual places its offspring into a connected neighbour that is chosen at random. (Note, however, that for real populations offspring can disperse widely from their parents, and different replacement rules will be worthy of subsequent study.) We consider a general game between mutant and resident individuals with the following payoff matrix:
1.3
Here, *a* and *b* denote the fitness of a mutant when playing against a mutant and a resident individual, respectively, while *c* and *d* denote the fitness of a resident individual when playing against mutants and resident individuals, respectively (for the fixed fitness case of, for example, Lieberman *et al.* (2005), *a*=*b*=*r*,*c*=*d*=1). Suppose that an individual *i* is connected to *M*_{i} mutants and *R*_{i} residents. The fitness of each individual is taken to be the average of the payoffs of games against all of its neighbours, i.e. the fitness of a mutant individual *i* is
1.4
Similarly, the fitness of a resident individual *j* is
1.5

We consider the fixation probability of a mutant introduced into the population of residents, the mean time to absorption (or unconditional fixation time) and the mean fixation time of a mutant (or conditional fixation time) on the three structures. The mean time to absorption is the average number of birth–death events until either one of the two types of individuals is fixed, given that in each time step the number of mutant individuals can increase by one (a mutant replaces a resident), decrease by one (a resident replaces a mutant) or remain the same (a mutant replaces a mutant or a resident replaces a resident). The mean fixation time of either type is the time that it takes for each of the types of individuals to be fixed in the population, conditional on this occurring. It should be noted that here we are counting the number of replacement events and so effectively assuming a constant rate of change with time. In many real populations reproduction happens in a short time interval, so the rate of change in real time will be highly variable (although statements on relative times comparing different structures and parameters are still likely to be valid). Another factor of potential interest, which we only briefly consider, but which we also have derived formulae for, is the mean number of transitions to absorption/fixation, where the number of transitions is defined as in the time, except that events where the mutant population size is unchanged are not counted.

A derivation of the fixation probability of mutants for an infinite well-mixed population can be found in Karlin & Taylor (1975), and this is developed for a finite population size in Nowak (2006) and Traulsen & Hauert (2009). Complete derivations of the mean time to absorption for an infinite well-mixed population can be found in Karlin & Taylor (1975), and general expressions for the times to absorption and fixation for finite well-mixed populations are given in Antal & Scheuring (2006) (see also Traulsen & Hauert 2009).

We note that the solutions of the mean time to absorption and the mean fixation time of mutants have the same behaviour as the individuals’ fitness and the population size vary. However, when mutant individuals become extinct, it usually happens in a short time, so the number of time steps needed for mutants’ fixation in each case is higher; in this paper, we mainly focus on the mean time to absorption. Note that, for two types of individuals, the fixation time of a single individual of either type in a population of the other type is identical (Taylor *et al.* 2006) for the Moran process (e.g. constant fitness on a regular graph, such as the circle or complete graph).

The main emphasis and the main novelty of this paper is the generation of the theoretical formulae for the exact solutions of the fixation probabilities and the fixation times for each case that we consider for the three structures, especially for the star. In general there are relatively few theoretical results of this type on evolutionary processes on graphs; in particular, the absorption and fixation time, the focus of this paper, has rarely been considered.

Through numerical examples we compare the impact that the population size and the individuals’ fitness have on the results of evolutionary dynamics on each of the three structures. In a number of previous papers adaptations of the classical prisoners’ dilemma to graphs have been considered (e.g. Ohtsuki & Nowak (2006*a*) to the circle and Traulsen & Hauert (2009) to the well-mixed population); we focus on the classical hawk–dove game (Maynard Smith 1982). The hawk–dove game is particularly interesting because in the infinite well-mixed population the evolutionary game dynamics yields a mixture of individuals playing hawk or dove, which means, as shown by Antal & Scheuring (2006), in a finite well-mixed population, the fixation of either one of the strategies is very slow. We note that there has also been some discussion of the alternative version of the hawk–dove game, the snowdrift game, in spatial structures (Hauert & Doebeli 2004; Ohtsuki & Nowak 2006*b*); but we describe the game in its classical format, which we believe is a natural step and which will have a wider application than in this paper.

## 2. Formulae for the fixation probability and the mean times of absorption and fixation

For each of the graphs we consider, the star, the circle and the complete graph (figure 1), we present here formulae for the fixation probability, the mean time to absorption (either mutants or residents fixate) and the mean time to mutant fixation. We denote the following terms, which are useful in subsequent calculations,
2.1
and
2.2
being the average payoffs to the mutant (respectively resident) individual that is neighbour to *i* mutants and (*N*−1−*i*) residents (as happens in the centre of the star or anywhere in a complete graph).

### (a) Star

The star is an irregular graph where *n*=*N*−1 vertices, the leaves, are connected with only one vertex, the centre (figure 1*a*). In the invasion process on the star, in each time step either the individual in the centre is replaced by the offspring of one on the leaves or an individual on the leaves is replaced by the offspring of the individual in the centre.

#### (i) Fixation probability

We denote by the fixation probability of *i* mutants on the leaves and a mutant in the centre (no mutant in the centre).

The fixation probabilities and are the solutions of the system
2.3
and
2.4
where, for example, denotes the transition probability from the state at which there are *i* mutants on the leaves and a mutant in the centre to the state at which there are *i* mutants on the leaves and no mutant in the centre.

Based on equations (1.2), (1.4) and (1.5), the transition probabilities are given by
2.5
2.6
2.7
and
2.8
Rearranging equations (2.3) and (2.4) and substituting the transition probabilities (2.5)–(2.8) into these, we obtain
2.9
and
2.10
with boundary conditions and . From the systems (2.9) and (2.10) and the boundary conditions, we find , , , and so on as a function of . Inductively, we obtain the general solution
2.11
where
2.12
Since , we get
2.13
Using equation (2.10), a direct calculation gives that
2.14
where is given by equation (2.13). From equations (2.9), (2.10) and the condition , we get
2.15
and
2.16
The average fixation probability of a single mutant on the star, *ϱ*_{s}, is given by
2.17

We note that in the case where mutant individuals have fixed fitness equal to *r* and resident individuals’ fitness is equal to 1 we recover the formula of the fixation probability from Broom & Rychtář (2008).

#### (ii) Mean time to absorption

The mean time to absorption starting from *i* mutants on the leaves and a mutant (no mutant) in the centre, (), are given by the solutions of the system
2.18
and
2.19
with boundary conditions and . Substituting the transition probabilities into equations (2.18) and (2.19) and rearranging (2.18), we obtain
2.20
and
2.21
where
2.22
and
2.23
Solving inductively the systems (2.20) and (2.21), we get
2.24
Using equation (2.24) and the condition , we obtain
2.25

By equation (2.21), 2.26 where is given by equation (2.24). Using equations (2.20), (2.21) and the condition , we get 2.27 and 2.28

Thus, the average time to absorption starting from a single mutant on the star, *T*_{1(s)}, is given by
2.29

#### (iii) Mean time of fixation of mutant individuals

Following the method of Antal & Scheuring (2006), the average times of mutant fixation, , are given by the solutions of the system
2.30
and
2.31
with boundary conditions and . The systems (2.30) and (2.31) can be solved as similar systems in the previous sections and we get that the average fixation time of a single mutant on the star, *F*_{1(s)}, is given by
2.32
where
2.33

### (b) Circle and complete graph

#### (i) Fixation probability

Any two formations of *i* mutants and *N*−*i* residents on the complete graph are equivalent; the same is true for the circle because the mutants always form a connected segment. Thus, the fixation probability of *i* mutants on a complete graph or a circle is given by the solution of
2.34
with boundary conditions *P*_{0}=0 and *P*_{N}=1, where *p*_{i,j} denotes the transition probability from the state with *i* mutants to the state with *j* mutants. In the case of the complete graph, the transition probabilities are given by
2.35
and
2.36
In the case of the circle, the transition probabilities are the following:
2.37
2.38
2.39
and
2.40
The derivation of the solution to the system (2.34) has been given in Karlin & Taylor (1975) (see also Nowak (2006) or Traulsen & Hauert (2009)) as
2.41
Thus, as in Taylor *et al.* (2004), the fixation probability of *i* mutants on the complete graph, *P*_{i(cg)}, is given by
2.42
The fixation probability of *i* (1≤*i*≤*N*−1) mutants on the circle, *P*_{i(c)}, is given by
2.43
where
Note that the fixation probability on the circle has also been considered for different selection scenarios in Ohtsuki & Nowak (2006*a*).

#### (ii) Mean time to absorption

The mean number of time steps before absorption starting from *i* mutants on a complete graph or a circle, *T*_{i}, is given by the solution of the system
2.44
with boundary conditions that *T*_{0}=0 and *T*_{N}=0. A complete derivation of the solution of equation (2.44) is shown in Traulsen & Hauert (2009).

On the circle we find that the mean time to absorption starting from *i* (1≤*i*≤*N*−1) mutants, *T*_{i(c)}, is given by
2.45
where
2.46
and
2.47

It is straightforward to generate the equivalent expression for the complete graph, which is the simplest case and which we have omitted.

#### (iii) Mean time of fixation of mutant individuals

As in Antal & Scheuring (2006), the mean number of time steps before mutant fixation starting from *i* mutants on a complete graph or a circle, *F*_{i}, is given by the solution of the system
2.48
with boundary conditions *P*_{0}*F*_{0}=0,*P*_{N}*F*_{N}=0. Following the same method as in Antal & Scheuring (2006), we find that the fixation time of *i* (1≤*i*≤*N*−1) mutant individuals on the circle, *F*_{i(c)}, is given by
2.49
where
2.50
and
2.51
The respective formulae for the complete graph can be generated similarly.

## 3. Example games

### (a) The fixed fitness case, *a*=*b*=*r*, *c*=*d*=1

All of the following figures (figures 2–6) were generated by numerical implementation of the above formulae. Although our emphasis is on the hawk–dove game described in the next section, we start by a simpler case where mutant fitness is equal to a constant *r* and resident fitness is equal to 1 and compare the absorption and fixation times of the evolutionary process on the three different structures (the comparison of the fixation probability among the three graphs in this special case has already been considered in Broom & Rychtář (2008)). Many of the observations will then be carried over to the more complicated case of the hawk–dove game.

In the case where mutants are fitter than resident individuals (*r*>1), the increase in the population size increases the time to absorption in all structures; the increase is much faster for the star graph than for the circle or the complete graph. On the star, for large *N*, the mutant is placed on a leaf with very high probability, and a mutant placed on a leaf is quite safe, being killed at each time step with probability of the order of 1/*N*^{2}; this increases the time needed for mutant elimination. For exactly the same reasons, even when all individuals but the last one (which is inevitably on a leaf) are mutants, at each time step the probability of mutant fixation is again of the order of 1/*N*^{2}, which increases the time needed for mutants to fixate.

The number of mutant–mutant and resident–resident replacements before absorption is higher on the circle than on the complete graph. As a result, absorption is reached slower on the circle than on the complete graph (this is in contrast with the mean number of transitions before absorption where the two cases are identical) and as the population size increases, the mean time to absorption increases more on the circle (figure 2*a*). Note that the results for fixation times behave in a similar way.

For a constant population size, the mean time to absorption is an increasing function of *r*∈(0,*r*_{slowest}) and the time then decreases to a constant for *r*>*r*_{slowest}. The constant corresponds to the number of steps needed for absorption given a mutant is selected for reproduction at every time step. Again, the limit is largest for the star (as there the mutant–mutant replacements are most frequent), followed by the circle and then by the complete graph. The value of *r*_{slowest} is different for different structures, but approaches 1 in each case as *N* increases, and this means that absorption times are slowest in the case of random drift for large populations. The results are again similar for the fixation time.

For *r*≈0, on the circle and the complete graph the mean absorption time is around *N*−1 (since a mutant never gives birth, and the probability that it is killed at each time step is 1/(*N*−1)). However, on the star the mean absorption time is much larger, about ((*N*−1)^{3}+1)/*N*, since if the mutant is placed in the centre it is killed immediately, and otherwise it is killed at each step with probability 1/(*N*−1)^{2}; (figure 2*b*).

### (b) The ‘hawk–dove’ game

In this section, we compare the fixation probability and the mean times to absorption and fixation on the three structures when the fitness of individuals is given by the hawk–dove game. We recall that, in the hawk–dove game, we assume a pair of individuals contest a resource of value *V* with two strategies, hawk or dove. When two hawk players meet, they fight for the resource. The fitness of the winner of the game is increased by *V* and the fight costs a value *C* of the fitness of the loser. Thus, the average increase in the fitness of the players is (*V* −*C*)/2. When a hawk meets a dove, the hawk wins and its fitness increases by *V* , while the dove’s is unchanged (increases by 0). When two doves meet, one of them eventually wins, but the loser pays no cost, and thus the average increase of fitness to each is *V*/2. We note that, if *C*<*V* , the hawk is the superior strategy irrespective of what the opponent plays. If *C*>*V* and the population is infinite, there is an evolutionarily stable equilibrium of *V*/*C* hawks and 1−*V*/*C* doves in the population (Maynard Smith 1982).

We will consider the game with the payoff matrix (3.1), which is equivalent to a hawk–dove game with the value of the resource *V* =5, varying fight cost *C* and played in a population with a background fitness *x*=5,
3.1

#### (i) The fixation probability of a mutant hawk

We first consider the case of a single hawk individual introduced into a population of dove residents and study how the fixation probability depends on the graph structure, population size and the fight cost *C*.

On the star, whenever there are at least *N*=5 vertices, an increase in the population size increases the average fixation probability of a randomly placed mutant hawk. This is in contrast to the situation on the circle or complete graph, where the increase in the population size always yields a lower fixation probability (figure 3*a*,*b*). This difference is due to the fact that, on the star, a dove has a higher fitness than a neighbouring hawk in very few cases, moreover only in those where the fixation of the hawk is already very likely (if *N* is not small). Indeed, if a dove is in the centre, then its fitness is no more than *d*=15/2 while the fitness of a hawk on a leaf is *b*=10. If a dove is on a leaf with a hawk in the centre, then the fitness of the dove is *c*=5 while the fitness of the hawk ranges from *b*=10 (with no other hawks in the population, i.e. when there is the highest danger of hawk extinction), continuously going down to almost *a* (if there are hawks on almost all other leaves, i.e. when hawks are almost fixed in the population). Note that, in our example, this argument does not hold for small *N*, and the expected pattern of declining fixation probability with population size happens on the star as well, initially.

On the circle, the larger the population, the smaller the fixation probability of hawks. On the other hand, once the circle is large enough, any further increase in the number of individuals does not have a large effect on the fixation probability of hawks (this is true for each type of graph, but especially for the circle). This is because any transitions are localized on the boundary between the two connected segments, one consisting of hawks and the second one of doves, and the payoffs of the individuals on the boundary do not depend on the population size (except in small circles).

For a constant population size, since the increase in *C* decreases the probability for hawks to increase their number, the fixation probability on all of the three structures decreases. The star again yields the highest probability of fixation (figure 3*c*,*d*). In addition, on the star as the population size becomes large, the fixation probability of a mutant hawk is found to approach *V* (2*V* +3*x*)/2(*V* +*x*)^{2} and thus it becomes independent of the fight cost *C*. This is because when there is a large number of mutant hawks on the star, those on the leaves play only against the central individual, and are fit compared with a resident dove in this position. If extinction happens, it is very likely to happen early on (owing to bad luck) when there are few hawks, and, if there are few hawks, the fitness of all individuals does not depend upon *C* in a large population. Thus, the increase in the population size decreases the effect of the cost, *C*.

Whether the fixation probability of hawks is greater on the circle or on the complete graph depends on *C* (see figure 3*c*,*d*). When *C* is small, hawks do better on the circle than on the complete graph. This is because even when the hawk population is small, competing hawks and doves both gain their fitness from 50 per cent hawks and 50 per cent doves, and this is advantageous to a hawk when *C* is small, when compared with the well-mixed case. When *C* is large, hawks again do better on the circle. Here, the hawk’s chance of fixation in either case is low, and it needs good luck to reach a high proportion in the population. If this occurs, then on the complete graph it must achieve fixation with a fitness derived mainly from contests against hawks, which will be low for large *C*, as opposed to the case on the circle, which is still from 50 per cent hawk and 50 per cent dove contests.

We note that, on the circle, if the population consists of more than one mutant and more than one resident (inevitably each in connected sets), then, if *a*+*b*<*c*+*d*, resident individuals are more favoured to be fixed than mutant individuals. Hence, as seen in figure 3*d*, for *C*>2*V* =10 and large population size, the fixation probability of a mutant on the circle tends to zero. If *C*<2*V* , from equation (2.43) we find that the fixation probability approaches 4(*V* +*x*)(2*V* −*C*)/(11*V*^{2}−5*V**C*+24*V**x*−8*C**x*+16*x*^{2}) with increasing *N*.

On the complete graph, the larger the population size, the smaller the dependence of the fixation probability on the cost of the fight *C*, at least for lower values of this cost. This is because, for smaller *C*, hawks will fixate unless they are eliminated early on, when the population has few hawks; for a sufficiently large population, this is effectively a population of doves, where the value of *C* is irrelevant. We note that *p*_{i,i+1}>*p*_{i,i−1} if and only if *i*−1<*N**V*/*C*. As a result, even in a finite population, there is a tendency for the number of hawks in the population to stay around *N**V*/*C*. Nevertheless, owing to the finite population size, the extinction of either hawks or doves is inevitable and the extinction of doves is more likely if *N**V*/*C* is closer to *N* than to 0, i.e. if *C*<2*V* . Thus, we can see the fixation probability of hawks on the large complete graph being almost a step function with the step occurring at *C*≈2*V* . As *N* becomes large (), if *C*<2*V* , the fixation probability is found to approach *V*/2(*V* +*x*), while if *C*>2*V* it approaches zero.

#### (ii) The fixation probability of a mutant dove

Now, we will consider the case of a single dove introduced into a hawk population. The fixation probability on the star is the lowest of all three structures; this is because hawks do very well on the star as discussed above. When *C* is small, there is almost no difference between the complete graph and a circle in our example, since the payoff advantage of hawk over dove is close to 2.5 for both graphs for all population compositions (figure 4*a*). However, when *C* is large, doves do much better on the complete graph (figure 4*b*). This is because when there are too many hawks in the population, they hurt each other, allowing doves to increase in number and making it very unlikely for doves to become extinct. Note that the advantage of doves on the complete graph increases with the increasing population size (if the population is not too small). On the other hand, an increase in the population size means a significant decrease in the fixation probability of doves on the star. Similar to the hawk invasion case, if the circle is large enough (*N*≥10), the fixation probability of doves on the circle is almost independent of the population size (this is true for each structure, but is particularly marked for the circle, as before). As figure 4*c*,*d* shows, the greater the value of *C*, the higher the probability of dove to take over a population of hawks in all structures.

#### (iii) Mean time to absorption starting from a single hawk in a population of doves

An increase in the population size increases the mean time to absorption in all structures, but this increase is much higher on the star, exactly for the reasons described in the fixed fitness case. Furthermore, we observe that, for small *C*, absorption is faster on the complete graph than on the circle. This is similar to the fixed fitness case, because the number of replacements by the individual of the same type is higher on the circle than on the complete graph (figure 5*a*).

On the complete graph, the increase in *C* decreases the probability of mutant reproduction (when there is more than one mutant) and thus increases the time of their fixation. On the other hand, since *C* matters only when there are enough hawks in the population, the change of *C* does not much affect the probability of hawks being eliminated (especially at the beginning of the invasion). Consequently, for small *N*, the time to absorption increases with the increase in *C* (figure 5*c*). On the other hand, when *N* is large, then, as already described above, there is a certain tendency for the number of hawks to stabilize around *N**V*/*C* and the evolutionary process ends at absorption owing to stochasticity in a finite population, as opposed to the result of evolutionary pressure. Consequently, the process takes the most time when *N**V*/*C* is as far from 0 and *N* as possible, i.e. when *C*=2*V* (figure 5*d*).

On the circle, since mutant fixation depends on the fitness only of the individuals on the boundary between hawk and dove segments, the mean time to mutant fixation is not affected much by the variation of *C*. Consequently, the absorption time is not affected by changing *C*, but there is a clear decrease with *C* for large population sizes for *C*>2*V* , since then we have *a*+*b*<*c*+*d* and thus hawks are significantly more likely to become extinct (which happens relatively fast) rather than fixate; see the results of §3*b*(i).

#### (iv) Mean time to absorption starting from a single dove in a population of hawks

We now study the mean time to absorption in the case where a single dove invades a population of hawks. For *C*<*V* , hawks dominate doves in all structures and the time to absorption is almost just the time to dove elimination. As *N* increases and *C* is constant, the absorption time increases for similar reasons as in the fixed fitness case (figure 6*a*,*b*). When *N* is constant (and relatively small) but *C* increases, the hawks lose their advantage and it thus takes longer to eliminate the doves. When *C* goes over a certain threshold, the fixation time for a complete graph becomes larger than for the circle. As described before, for high *C*, a hawk does better in a population of mainly doves, but a dove does better in a population of mainly hawks, so there is a pressure towards a mixture of the two with *N**V*/*C* hawks in the complete graph; absorption occurs eventually by chance since the population is finite, but it takes longer than on the circle where this pressure does not exist.

Note that on a large star the absorption time is again almost independent of *C*, until *C* approaches 15, i.e. the payoff from the game among hawks is close to zero, when the time starts to increase. One reason for this is that there is suddenly some chance of dove fixation, and there can be a longer battle between doves and hawks before absorption.

For large population sizes, we again see the absorption times on a complete graph peaking at *C*≈2*V* , for the same reasons as in the hawk invasion. Here, we observe that, for *C*≈2*V* , the absorption time on the complete graph becomes larger even than for the slowly evolving star. Because for *C*=2*V* , *a*+*b* becomes smaller than *c*+*d*, there is an important shift of the behaviour of the absorption times on the circle (similar behaviour is naturally observed on the circle for the absorption of a hawk in a large dove population).

## 4. Discussion

In this document, we have studied the stochastic evolutionary game dynamics of finite structured populations. Following the rules of the invasion process, we have investigated the evolutionary process of a mutant individual introduced into a structured resident population as represented by a graph. Here we have considered three simple non-directed graphs: the star, the circle and the complete graph, and we have presented exact solutions for the fixation probability of mutants, the mean time to absorption and the fixation time of mutants on the three structures for general games where the fitness of individuals is not constant but depends on the interactions with other individuals; in particular, the fitness of an individual at each time step has been taken to be the average of the payoffs of games against all of its neighbours. The detailed consideration of the time involved in the evolutionary process is particularly novel.

We have used our solutions to compare the effect of the three population structures on the above quantities for different selection scenarios. Through numerical examples, we have shown how the evolutionary process depends on the payoff matrix, the population size and on the structure of the population. We have first studied the simplest case where each type of individual has constant fitness. We have then adapted the classical hawk–dove game to evolution on graphs. In the fixed fitness case, an advantageous mutant always has a higher probability to fixate on the star than on a regular graph where its fixation probability is given by the Moran probability. In general, fixation probability usually increases with the heterogeneity of the graph (Broom *et al.* 2009). With respect to the fixation time, the complete graph is the quickest of the three graphs for mutant individuals and the star the slowest, and for large population size for each graph times are longest in the case of random drift, where mutant fitness is identical to that of residents. Applying the hawk–dove game on the three structures, we have seen that the variation of the fitness plays a key role in the behaviour of the quantities that we have considered. First of all, we note that the fixation probability (and the mean number of transitions) is no longer the same for all regular graphs with *N* vertices. As shown, there is not a consistent relationship between the three graphs regarding which gives the highest mutant fixation probability and the fastest time to absorption/fixation in this case, since this depends on the payoff matrix, the ‘cost of the fight’ between doves and hawks, *C*, and the size of the population. However, there are certainly features of interest. For example, on the complete graph we observe that values of *V*/*C* that are intermediate between 0 and 1 yield very slow fixation times for large population sizes (which can be slower even than on the star), as selection pressure favours the mixture, and it is only due to the finiteness of the population that the extinction of one type occurs. Indeed, it would be of interest to consider the quasi-stationary distribution of such a population, conditional on such extinctions not occurring (this may resemble more accurately the results of simulations, for instance). For large populations, there is also a step change in the fixation probability of a single hawk at 2*V* as *C* varies, with a significant non-zero probability for *V*/*C*>0.5, and a near zero value otherwise. The circle, which is another regular graph, exhibits different behaviour (although the point where 2*V* =*C* is also important in this case), and figure 3*c*,*d* shows the interesting relationship where low and high values of *C* give higher fixation probabilities on the circle than on the complete graph, with intermediate values higher on the complete graph.

Note that, if we consider an alternative hawk–dove game, results can be significantly different. One obvious difference is that all payoffs must be non-negative, so the range of allowable values of *C* is different. The role of the background fitness is also significant. For example, if we remove the background fitness of 5 (i.e. subtract 5 from every payoff in payoff matrix (3.1)), the decrease in the payoff *a* (increase in *C*) does not affect the fixation probability (and the mean number of transitions) of a mutant on the star. This is due to the fact that, when *c*=0, the payoff *a* has no effect on the transition probabilities. In this case, we find the fixation probability to be *ϱ*_{s}=(*n*^{3}*b*/(*n*^{2}*b*+(*n*−1)*d*)+1)/(*n*+1). Furthermore, in this case, the number of transitions on the star before fixation is generally lower than the other two graphs and the mean time to fixation decreases with *C*.

The study of the evolutionary process of mutant individuals on graphs applying evolutionary game theory will give answers to more realistic scenarios about the effect of the population structure. We are in the process of extending the above work to the investigation of both the fixation probability and the time of mutant fixation under different dynamics and on more complex graphs. This will give insight into the effect of frequency-dependent fitness on these quantities and how the effect of the population structure changes following different dynamics.

## Acknowledgements

The research was supported by an EPSRC research studentship to C.H. and by NSF grant 0634182 to J.R.

## Footnotes

- Received September 18, 2009.
- Accepted November 19, 2009.

- © 2009 The Royal Society