Chris Cannings: A Life in Games

In the “generalized war of attrition” [9], more general cost and reward functions are allowed than those proposed originally by JMS. For the generalized game with contest time x having reward for winning f(x) and cost of competing g(x), the payoffs can be writtenIn such conflicts under reasonable assumptions about the cost and reward functions, there are either no ESSs or a unique solution, and in this latter case, the formal solution can be provided in closed form. For instance, if the strategy space involves competing without any time limit, the density function for the ESS is given by:Note that in the standard war of attrition, \(f(x) = V\) (a constant) and \(g(x) = x\).

Bishop et al. [11] expanded the conflict to the scenario where rewards varied randomly (the random rewards model) and also when the reward value differed between participants (e.g. when one was hungrier than the other) and/or the rewards progressed or escalated during the conflict; in these models, each opponent is aware of the reward for winning but unaware of the reward to the opponent (other than in distribution). If the reward takes on a series of discrete values, then the willingness to compete for longer increases, with each reward value corresponding to an interval time range which is non-overlapping with the time intervals corresponding to different rewards. One interesting difference with the standard war of attrition was that allowing different rewards for winning for different competitors means that the expected payoff is positive overall (in the war of attrition, the expected payoff is zero meaning that there is no difference in payoff (reward–cost) between strategies). In the random rewards model, the payoff is, on average, higher for the competitor with the highest value attached to the reward.

Bishop et al. [11] also provided a solution to the “graduated risks model” where competitors are willing to graduate the risk to which the conflict escalates, incurring an increased risk of injury (and cost). In this model, the solution depends on whether the cost of being injured exceeds the reward if successful. Of course, if the reward exceeds the cost of injury, then playing the most aggressive strategy is the ESS.

Bishop and Cannings [10] considered ordinal conflicts in which both the cost and the reward of competing were different between competitors. In these conflicts, the generalized war of attrition is further broadened so that both the reward and cost functions can differ between competitors. In these conflicts, the expected payoffs (when the ESS is played) depend only on the reward function and not on the specific form of the cost function.

Haigh and Cannings [69] considered a multiplayer version of the war of attrition. Here individuals choose their waiting time as in the standard game; they considered four scenarios. In the first there was only a single reward, and individuals had to choose a waiting time at the start of the game. In the second, they could update their strategy every time that a player was observed to leave. The third and fourth variants were as for the first two except that there were multiple rewards, and a player received a reward based upon the order in which they left. In the first variant the ESS involved all players choosing a strategy with the following distribution functionwhere m is the number of players. Subsequently, Helgesson and Wennberg [76] proved further results on this model.

Chris did further work on evolutionary game theory on Parker’s model (Cannings [38], see also [124]), where two players choose amounts to pay, and the individual which pays the larger amount wins the reward, but each player also incurs a cost proportional to the amount they chose to pay. This is a variant on the war of attrition with the payoffsChris considered the case where the strategy sets of the players are finite. In general there is no evolutionarily stable strategy in Parker’s model. Using an interesting relationship, involving Dyck words (see e.g. [155]), Chris was able to determine the conditions for all strategies to be present in the stationary distribution of these systems.

One of the key developments that emerged early in the theory of evolutionary games is that of asymmetric games. While Chris did not work on this explicitly, this important work built on his contributions.

The war of attrition and similar models assumed that while there could be differences in the value of the reward for winning, there was no asymmetry in terms of external information prior to or during the contest. However, there are many conflicts which have asymmetries, such as when one of the participants is the current owner of a territory, so that each conflict is between an owner and an intruder. In such scenarios, the nature of the ESS differs with this external information, the asymmetry, assisting in defining the optimal solutions. In such games, there are often two solutions [124], one regarded as common sense in which the owner is willing to remain for longer and an intruder investigates whether the territory can be won with limited expenditure or the inverse solution where the owner retreats when challenged. Hammerstein [71] showed that even a modest modification of the Hawk–Dove game could result in games with two ESS solutions. These two strategies are ESSs but not unexpectedly in the owner–intruder example; the former is the commonest scenario in nature. However, there are real-world examples of the latter (see Parker [124] for examples). It was shown in Selten [145] that for a wide class of such asymmetric games, it was not possible to have mixed ESSs, so that the only ESSs are pure.

Hammerstein and Parker [72] examined the conditions under which multiple ESS solutions might be found. They considered the issue of incomplete information (that is imprecision in for instance the owner–intruder conflict) or scenarios under which fighting approaches were not continuous, e.g. Hawk vs Dove discrete behaviours as compared to the continuous nature of the time choice in the war of attrition. They found that the criteria which allowed such counter-intuitive solutions to be feasible included that the information had to be predominantly correct and that the decision to remain had to be taken early in the conflict with no early opportunity for avoiding the impact of a decision to compete and that behaviours were continuous.

The theory of asymmetric games, in particular in relation to owner–intruder relationships, has been developed in a number of directions. A significant series of papers was by Mesterton-Gibbons, Sherratt and co-workers, who have considered various extensions to the theme, for example in Mesterton-Gibbons et al. [113, 114]. In particular, the study by Gibbons and Sherratt [112] considers the concept of infinite regress previously raised by JMS, where if an owner is displaced by an intruder in an owner–intruder game the roles are then reversed, so that the second ESS described above might lead to an infinite contest. A review of this and other work is presented in Sherratt and Mesterton-Gibbons [146].

While JMS coined the term evolutionarily stable strategy, the implicit assumption was that when the whole population adopted that strategy, such a population could not be invaded by an interloper or a mutation which translated into a different strategy. However, it is not clear that the population dynamics would translate into that ESS being achieved within the population if it did not start with all individuals adopting that strategy. There is a huge literature on evolutionary dynamics considering this and other questions, including a range of different dynamics, and we shall not discuss it here. In particular the most widely used dynamics is the replicator dynamics developed in Taylor and Jonker [158], where the population evolves in continuous time using differential equations. We note that ESSs and stable rest points of the dynamics are not identical (see [78]). While this, and other, continuous-time dynamics are more widely used in the literature, given his interest in genetic models, Chris was more interested in discrete-time dynamics, and a discrete version of the replicator equation appears in Bishop and Cannings [9].

In this discrete-time model, the assumption is made that the fitness of an individual is related to the strategy adopted plus a marginal fitness attributable to all other activities which is constant among community members. The dynamics can then be examined using approaches such as that of Kimura [86] and Kingman [87]. The interests of these investigators were the evolution of allele frequencies; in such a scenario, the payoff matrix A is symmetric (in the genetics example, this represents the fitness of the heterozygote for off-diagonal elements) and it is known that the population evolves to a stable equilibrium if one exists. The dynamic model considers that the representation of a particular type in the population in generation \(G_{n}\) is proportional to the frequency in generation \(G_{n-1}\) multiplied by the fitness of that type compared to the rest of the population. In fact, in this scenario of allele frequency changes, the mean viability increases monotonically from generation to generation towards the asymptotic equilibrium.

Chris had employed such an approach successfully when examining the effect of selection on a multiallelic system when the population was split between multiple niches and mating happened within each niche [36]. Assuming the population is large, Bishop and Cannings [9] showed that for the generalized war of attrition, if there is an ESS, then this strategy is both attainable in a large population and achieved asymptotically. However, in the general setting the mean fitness of the population does not necessarily monotonically increase from generation to generation. Chris was particularly interested in trying to understand the relationship between the ESS and dynamic stability especially in the scenario where the strategy adopted in conflicts was genetically determined. However, it is fair to say that limited progress was made on the overall problem and it remains an interesting, unresolved issue.

One outstanding problem is to consider how the imposition of germline inheritance on conflict behaviour might evolve, as opposed to the phenotypic modelling which had been discussed previously. Hines and Bishop [77] and Cressman and Hines [47] showed that while there were situations in which the ESS was not locally stable, restricting the mode of inheritance by excluding situations which were less biologically plausible such as overdominance, meant that the ESS was locally stable. Some recent works have been carried out on such genetic models in Fishman [56, 57], where a methodology of how to approach these problems was introduced and some analyses for classical games including the Hawk–Dove game and Prisoner’s dilemma are carried out.

There are a number of exclusion rules, most of which appear in Vickers and Cannings [163]. We show the two simplest rules below. The first of these is the most useful and is in fact just an application of the Bishop–Cannings theorem.

Exclusion rule 1 Anti-chain. If \(S_{1} \subseteq S_{2}\), then no pattern can contain both \(S_{1}\) and \(S_{2}\).

Exclusion rule 2 No triangles. If \(Q \subseteq \{4, 5, \ldots , n\}\), \(S_{1}=\{1,2\} \cup Q\), \(S_{2}=\{1,3\} \cup Q\) and \(S_{3}=\{2,3\} \cup Q\), then no pattern can contain \(\{ S_{1}, S_{2}, S_{3} \}\).

All non-obtainable patterns for the case \(n=3\) above can be excluded using these two rules only (the second rule excludes the triangle \(\{(1,2), (1,3), (2,3) \}\)). For \(n=4\) and above we need these two rules, but also others.

There are also a number of construction methods, see Broom et al. [24] (also [26]) and more recently Bomze et al. [15]. The simplest of these from Cannings and Vickers [41] involves the idea of a clique matrix. An \(n \times n\) matrix A is a clique matrix if \(a_{ii}=0\) for all i and \(a_{ij}=a_{ji}=\pm 1\) for all \(i \ne j\). A set of pure strategies S forms a clique if and only if \(a_{ij}=1 \forall i, j \in S\) with \(i \ne j\) and there is no \(k \notin S\) s.t. \(a_{kj}=1 \forall j \in S\).

It is easy to show that there is an ESS of A with support S if and only if S is a clique, and so \(\mathcal {P}(A)\) is simply the set of cliques of A. All attainable patterns for \(n=3\) can be found using cliques, but for larger n we need other construction methods, and cliques fail to find an increasing proportion of them.

Recent work considering a variant of the clique matrix defined above, where \(a_{ij}=a_{ji}=1\) or 0 is given in Wang et al. [168] (see also [74]). Here the precise network was chosen for application motivational reasons, and the payoff matrix corresponds to a graph adjacency matrix where 1(0) represents the presence (absence) of a social link, although we note that this matrix class leads to more complex conditions and thus is less useful for constructing ESS patterns.

The maximum number of ESSs possible for \(n \times n\) matrices was denoted in Broom et al. [23] by \(M_{n}\). In particular they proved that \(M_{n}M_{m} \le M_{n+m}\) and thatfor some \(\gamma \le 2\).

A lower bound for \(\gamma \) of \(30^{1/9} \approx 1.459\) was found in Broom et al. [23]. In fact a value almost as good, \(3^{1/3}\approx 1.442\), can be found using clique matrices. This bound was recently improved on in Bomze et al. [15] to \(15120^{1/24} \approx 1.493\). In that paper the authors build on earlier work Bomze [12, 13] to develop ways to tackle this and related problems (as in Broom et al. [23] the focus was on the standard quadratic optimization problem which has a number of other applications too). They found lower bounds for the maximum number of ESSs for all \(n \le 24\) and also investigated methods for looking for ESSs for larger n more generally. This work was developed further in Bomze and Schachinger [14] in the same issue of dynamic games and applications as this review, and this paper contains a number of interesting analyses.

Upper and lower bounds on the number of ESSs of a given mean support sizewhere \(s_{n}(x)\) is the maximum number of ESSs of mean support size x on an \(n \times n\) matrix, were found in Broom [16]. Here it was shown that \(f(\alpha )\) is continuous on the rational numbers.

The above bounds for \(\gamma \) and \(f(\alpha )\) are still very wide, and it will be a considerable challenge to improve them. Nevertheless, the recent work in Bomze et al. [15] and Bomze and Schachinger [14] is the first significant improvement for many years and hopefully there is more of such improvements to come.

In practice we are unlikely to have a very large number of ESSs of a matrix game, and the question of how many ESSs we would expect to see was considered in Cannings and Vickers [41], when considering randomly generated clique matrices. The same problem for more general matrices was considered in Haigh [67, 68]. We note that here the distribution of the payoffs affects the answer; in Haigh [67] all payoffs were assumed to be i.i.d from a uniform distribution. Large ESSs supports were shown to be very unlikely to occur in Haigh [68].

This problem is significantly complicated by the stability condition required to make a Nash equilibrium into an ESS, and addressing the problem of the number of Nash equilibria that can occur is an easier problem to tackle, as in Han et al. [73] and Duong and Han [50], which both actually considered multiplayer games (as defined in Sect. 5) as well as two-player games. As well as proving general results Duong and Han [50] showed that, under specific distributional and independence assumptions, the probability of an internal equilibrium is simply \(1/2^{n-1}\). This work is part of a series of papers in this area, see Duong and Tran [51] and Duong et al. [52].

Due to its general mathematical formulation on quadratic forms, the study by Broom et al. [23] has been cited in various later mathematical works with no clear biological or game-theoretic connection. A relevant biological connection is in the work of Leinster and Meckes [95]. Here the authors develop a model of biological diversity and use a similarity matrix between the species (values being between 0 and 1, where the similarity of a species to itself is 1). They are interested in maximizing diversity and use a number of entropy measures. Interestingly, the conditions for optimizing entropy closely resemble those for ESSs of symmetric evolutionary games, when the dissimilarity matrix (1 minus the similarity matrix) is used (see e.g. Cannings et al. [44] where such symmetric matrices are considered).

Broom et al. [28] considered the situation of an infinite population, where randomly selected groups of size m play a game where there are n pure strategies available. In the most general case the specific ordering of all players could be important, and there would be a distinct set of payoffs, one to each of the m players, for each ordered strategy selection \(i_{1}i_{2}\ldots i_{m}\). However, they concentrated on symmetric games, where the payoff to any given individual depended only upon its own strategy and the combination of the strategies of the other players, irrespective of their ordering.

Thus, the payoff to an individual playing \(i_{1}\) against players playing \(i_{2}, \ldots , i_{m}\) satisfies \(a_{i_{1}i_{2}\ldots i_{m}}=a_{i_{1}\sigma (i_{2})\ldots \sigma (i_{m})}\) for any permutation \(\sigma \) of the indices \(i_{2},\ldots ,i_{m}\). Matrix games are just a special case of this situation with \(m=2\).

They showed that the Bishop–Cannings theorem fails (i.e. it is possible to have two ESSs where the support of one is a subset of the support of the other) for \(m \ge 3\), that it is not possible to have two ESSs with the same support for \(m=3\), but that this is possible for \(m \ge 4\). They considered in some detail the case with \(n=2\), where they fully categorized the possible sets of ESSs (not just their supports) that could occur for a single game in the generic case; this case was further developed in Pena et al. [131]. In this case the payoffs can be simply denoted \(\alpha _{ij}\) where \(i=1,2\) represents the player’s strategy, and \(j=0,\ldots , m-1\) represents the number of its opponents that play strategy 1, the remaining \(m-1-j\) thus playing strategy 2. Broom et al. [28] showed that for generic games, mixed ESSs are represented by the zeros of the following polynomial where the derivative is less than 0,where \(\beta _{l}=\alpha _{1l}-\alpha _{2l}\). Pure strategy 1 (2) is an ESS if \(\beta _{m-1}>0\) (\(\beta _{0}<0\)).

This work was developed further in Bukowski and Miȩkisz [35] who proved extensions of classical results for matrix games, such as that a strategy p is an ESS if and only if it is locally superior. They also gave the nice example below to illustrate that a game can have more than one ESS with the same support for \(m=4\).

Broom et al. [28] also considered the case with \(n=m=3\), the simplest case where both m and n are greater than two, for the special case of supersymmetric games, where \(a_{i_{1}i_{2}\ldots i_{m}}=a_{\sigma (i_{1})\sigma (i_{2})\ldots \sigma (i_{m})}\) for any permutation \(\sigma \) of the indices \(i_{1}i_{2},\ldots ,i_{m}\), which is the extension to multiple players of the genetics-based model of Cannings et al. [44]. The range of combinations of ESSs that resulted showed the difficulty in dealing with this problem more generally.

Platkowski has written a number of papers on multiplayer evolutionary games [134, 136, 137]. Recently he introduced the idea of evolutionary coalitional games [135], i.e. incorporating classical coalition games into the evolutionary setting, where the population evolves following the replicator dynamics. Here he showed that, contrary to the corresponding evolutionary models in well-mixed populations, cooperation can be supported in the system in the long run. The two-strategy game of Broom et al. [28] was also recently used in laboratory experiments to investigate human cooperative behaviour in Kuzmics and Rodenburger [92].

The stochastic stability for a finite population playing three-player games with two strategies was the subject of a series of papers by Miekisz and co-authors, where they studied this situation for the well-mixed case [85], a spatially structured population [115] and a population where there was an added time delay in the games [116] (see also Miekisz et al. [117] in the same journal issue as this review).

This area was further explored more recently by Gokhale and Traulsen [62, 63], Wu et al. [170], see also Han et al. [73] and Duong and Han [50], as discussed in Sect. 4.4. The study by Gokhale and Traulsen [64] is a good review of work up until 2014. In Gokhale and Traulsen [62], the authors investigated both infinite and finite populations. The question of the number of Nash equilibria (as opposed to ESSs) it was possible to have in a multiplayer game was considered. In general it was shown that the maximum number of internal equilibria possible is \((m-1)^{n-1}\).

The possible emergence of multiplayer games from pairwise ones was considered in Wu et al. [171]. Here the authors considered pairwise games that occurred in sets that broke up at rates that depended upon their composition, and which led to games that were multiplayer in character, with payoff functions as in multiplayer matrix games. These were compared to linear independent combinations of pairwise games to show how multiplayer games might emerge. The effect of a multiplayer game being the result of non-independent pairwise ones is also the subject of Sect. 5.2.

There are also more computational applications for evolutionary games and in particular multiplayer evolutionary games. In Rota Bulo and Pelillo [142] (see also [127]) evolutionary game methodology was applied to the problem of hypergraph clustering, that is the process of finding the most coherent groupings from a set of objects using high-order (i.e. not just pairwise) similarities. Here the authors devised a hypergraph clustering game and showed equivalence between the ESSs of the game (with multiplayer ESSs of level 1 as defined in [28]) and dominant set clusters, an important concept from clustering theory.

The concept of games, including evolutionary games, has been combined with quantum dynamics to give quantum games, [53] with potential applications to evolution at the molecular level. Evolutionary aspects have particularly been considered by Iqbal and colleagues for the two-player and multiplayer settings [45, 80‐82]. See Orlin Grabbe [122] for an introduction to this area.

In Broom et al. [30, 31] the same authors considered pairwise games built into a dependent structure that meant, unlike for standard matrix games, players did not play games independently of their strategy and so a more complex multiplayer contest resulted. The game was built on knockout contests like the Wimbledon tennis tournament (although this involves some non-random element by seeding the leading players) where individuals are randomly paired, but only the “winner” qualifies for the next round, and a similar random draw is carried out between the winning players. This process starts with \(2^{n}\) players and is repeated until a final between two players occurs. An individual receives a reward \(V_{j}\) for being eliminated in the round of \(2^{j}\) players, with the winner receiving \(V_{0}\). Individuals can also receive costs from a contest, depending upon their strategic choice and that of their opponent. The probability of progression also depends upon these choices, and this means that later pairings are depended upon strategy. They considered two versions of the game, where individuals had to play the same pure strategy in every round (the fixed case) and where they could change it , following a (possibly round-dependent) mixed strategy, every round.

An example component game considered was the Hawk–Dove game. Here Hawk versus Hawk contests resulted in a cost of C, and otherwise there were no costs, as standard. Here the reward V was replaced by progression to the next round. Thus Hawks always beat Doves, and contests between individuals playing the same strategy resulted in each progressing with a probability of 1/2. For the fixed strategy case there are fewer Hawks in the population the more rounds there are, as Hawks are more likely to progress to later rounds and have contests against increasingly Hawkish opponents; the distribution of observed contests can also be significantly different from the comparable case with independent contests.

This game was further developed by Broom and Cannings [18] to consider a different type of contest where all players were involved in every round, based upon the “Swiss tournament” common in chess competitions. Individuals should be aggressive in early rounds and, if successful, later rounds. Losers however should become less aggressive, and this nicely mirrors the “loser effect” described in the models below.

Classic models of dominance hierarchy formation consider a series of contests within a group where winning increases the chance of winning another contest (winner effects) and/or losing decreases this chance (loser effects). Various models have considered the evolution of dominance hierarchies under winner and loser effects and in particular whether and how fast a linear hierarchy can be established including Dugatkin [48], Dugatkin and Dugatkin [49], Mesterton-Gibbons and Dugatkin [111] and Kura et al. [89]. In Dugatkin [48] individuals could assess the relative fighting ability of their opponent and concede if it was above a certain threshold. Kura et al. [90] considered an explicitly game-theoretic model where individuals could select their concession threshold strategically. Here a pure strategy solution was found, and this corresponded with fast establishment of a linear hierarchy.

Through a detailed study of data in hens and cichlid fish, Lindquist and Chase [103] (see also [46, 102]) found a dynamic relationship more complex than the linear dominance hierarchies from previous models. They suggested that the outcomes of hierarchies to a great extent depended upon two rules only. Rule 1 was that there were aggressive contests between all pairs of animals, and rule 2 that intransitive configurations of attacks were transformed to transitive ones faster than vice versa, but that there is a continuous dynamic updating.

A model of a population of birds arriving at a nesting area was developed in a further series of papers by Chris and colleagues. Here birds arrived sequentially and had to select one of the nests sites, which varied in quality. Good sites were likely to be contested by later arrivals, so sometimes it was best to select intermediate sites to avoid costly contests. They thus arrived at a set of dependent pairwise contests which combined to be a potentially very complex multiplayer game. Two extremes of birds with great and poor calculating powers were considered in Broom et al. [27, 29], respectively. An interesting situation where birds cooperated by selecting the worst sites and avoiding all conflicts, reminiscent of Tit-for-Tat in the Iterated Prisoner’s Dilemma, occurred in Broom et al. [25].

We shall discuss structured populations in more detail in Sects. 7 and 8. However, it is worth discussing them a little here in connection to multiplayer games. While none of the work below in this section was done by Chris, both structured populations and multiplayer games were a significant interest of his and his ideas influenced some of the work below. The classical game models from previous sections have all relied on the population being unstructured, or well-mixed, with every pair or group of individuals as equally likely to interact as any other of the same size. Populations with structure, based upon an underlying graph representing possible interactions (evolutionary graph theory), were introduced in Lieberman et al. [101]. The early models did not involve games at all, and when games were introduced [119, 121] inevitably these were pairwise, reflecting the edges of the graph. Multiplayer games were introduced on a graph by Santos et al. [144] (see also [99, 100]) where each individual played a multiplayer game involving all of its neighbours (and so if it had k neighbours it would also be involved in k further games centred upon each of them).

For finite structured populations, it is known that when considering the two-player Prisoner’s dilemma, an important property to assess whether cooperation evolves is the structure coefficient. How does this extend to multiplayer games? This question was addressed by McAvoy and Hauert [110] and Pena et al. [132] who considered the specific coefficients to be used; a more general type of structural coefficient is needed here, and typically \(m-1\) are needed for an m player game (see [141]). This has only been developed for specific types of graph so far. Pena et al. [133] consider the concepts of volume order and containment order which can use structure coefficients to assess the relative likelihood of the evolution of cooperation for different structures in a wide class of games.

Multiplayer games, including those with variable size, were introduced with the development of a new modelling framework in Broom and Rychtář [22] (see also [32, 125, 126]). This is a flexible framework with many possibilities, and a range of structures, games and dynamics has been considered. See also Tarnita et al. [157] and Pena and Rochat [130] for alternative ideas. Having variability in group size can have significant effects on the evolution of populations, see Pena and Noldeke [128, 129] and Broom et al. [33]. For instance Pena and Noldeke [128] found conditions on the payoffs for when increased variability would favour, or inhibit, the evolution of cooperation for a specific class of games.

Models of predator–prey interactions are some of the earliest in mathematical biology [105, 167]. These early models were not game-theoretic, but there have been a number of models developed from this classical interaction that have involved strategic behaviour of the predators and/or the prey. An influential model of this type was developed by Marrow et al. [107] (see also [106]) which considered the classic predator–prey population dynamic model, but where there was also a slower evolutionary process affecting the body sizes of both predators and prey.

They considered a polymorphic population with two types of prey, with slightly different body sizes \(s_{1}\) and \(s_{1}+\epsilon _{1}\), and two types of predator, with body sizes \(s_{2}\) and \(s_{2}+\epsilon _{2}\). The population then followed the ecological dynamics below:where \(x_{1} (x_{1}^{\epsilon })\) is the population size of the prey with body size \(s_{1} (s_{1}+\epsilon _{1})\), and \(x_{2} (x_{2}^{\epsilon })\) is the population size of the predator with body size \(s_{2} (s_{2}+\epsilon _{2})\). The r parameters (both positive) represent low density growth, the \(\alpha \)s (negative) are self-limiting parameters for the prey, and the \(\beta \)s (negative) and \(\gamma \)s (positive) are predator–prey interaction terms, where any given predator type is more likely to kill certain types of prey than others.

The result of these ecological dynamics then determined whether the mutant body sizes \(s_{1}+\epsilon _{1}\), \(s_{2}+\epsilon _{2}\) could invade a population \((s_{1},s_{2})\) (we will omit discussions of the conditions here). Thus over time the body sizes within the population would evolve, governed by the predator–prey interactions.

For plausible functional forms for these parameters, Marrow et al. [107] identified ten distinct evolutionary scenarios, including a continuous “red-queen” cycling though the body sizes. This paper demonstrates some of the possibilities of trait evolution and was cited in some of the important early works in the theory of adaptive dynamics (such as [60, 88, 93]), which is a very flexible and general mathematical theory of trait evolution, a discussion of which is beyond the scope of this paper.

A range of later works that considered the evolution of traits in co-evolving populations also cites this paper, and while it is often not the central paper considered, it is touched upon in a number of different approaches and scenarios. These include Mougi and Iwasa [118] which investigates when such oscillatory evolutionary behaviour will and will not occur, and Lion and van Baalen [104] which considers the influence of spatial factors in trait evolution.

Many wasp species are parasitoids which lay their eggs within the larvae of other species, eventually leading to the host’s death. A larva can be parasitized by more than one egg [61], although only one offspring will survive; this is called superparasitism. Commonly females leave a pheromone mark on a host that they have parasitized and so can distinguish hosts that are unparasitized, parasitized by themselves or parasitized by conspecifics [96].

This behaviour was modelled in Haccou et al. [65], who considered a scenario with two parasitizing wasps \(F_{v}\) and \(F_{w}\) at a patch of host larvae. The first female enters a patch of non-parasitized hosts, the second arriving at a random time later. Each host can be in one of the five states: unparasitized, or parasitized by the first only, by the second only, by both (with the offspring of the first the survivor) or by both (with the offspring of the second the survivor). Females can distinguish the states, except the fourth from the fifth. They assumed that females began by parasitizing only unparasitized larvae (a non-superparasitizing female), perhaps switching at some time to both parasitizing and superparasitizing.

Non-superparasitizing females encounter (and parasitize) hosts at rate \(\lambda \). Superparasitizing females encounter hosts at rate \(\mu <\lambda \) and superparasitize if a host contains at least one egg of the other individual; this latest egg is the one to yield an offspring with probability \(\sigma \).

The state of the patch is denoted by the proportions in the different cases u (state 1, unparasitized hosts), v (states 2 and 4, first female’s offspring survives) and w (states 3 and 5, second female’s offspring survives). The female strategy is a choice of leave, parasitize or superparasitize for every potential scenario, as either first or second female. The payoff to \(F_{v} (F_{w})\) is the derivative of v(w) with respect to t. Different trajectories within the region (u, v, w) occur for different strategies. For example when there is only a single superparasitizing female \(F_w\) present, the trajectory followsThere is also a background environmental gain rate \(\gamma \). At any point, the two females choose a strategy based upon how long they should wait, and when one leaves, the reward to the other will suddenly increase. This is equivalent to receiving a reward at that point, and Haccou et al. [65] thus analysed \(F_v\) and \(F_w\) as playing in a generalized war of attrition (see Sect. 2 and [9]).

The asymmetry of this model means that the first female to arrive effectively finds a better quality patch than the second, since there is a patch of completely unparasitized hosts. This led to the prediction that the first female would spend longer in the patch than the second. This prediction was empirically tested in Le Lann et al. [94] who conducted experiments with an aphid parasitoid Aphidius ervi Haliday in a patch of larvae from a grain aphid species Sitobion avenae Fabricius.

Three different scenarios were considered: (a) simultaneous patch exploitation with different arrival times, (b) exploitation of an unexploited patch by a single female, (c) exploitation of a previously exploited patch by a single female. The results found in this paper were entirely consistent with predictions made in Haccou et al. [65]. In particular, in patches where two individuals were present at the same time, the first arriving individual stayed for a longer time; indeed, it was usually the last to leave.

Males can compete with each other directly for mates through fights, as represented by the Hawk–Dove game. However, they can also compete indirectly, and one key way they do this is through sperm competition. A series of sperm competition models was developed by Parker and colleagues (see e.g. [4, 5, 123]). An interesting alternative was developed by Chris and colleagues in Fryer et al. [58, 59], which we describe below.

Consider a population consisting of a proportion f females and \(m=1-f\) males, which participates in two rounds of mating. Males will try to mate in each round, females mate only if receptive, and they may be receptive in either, neither or both rounds (in each round every receptive female will mate). \(f_{ij}\) and \(m_{ij}\) denote the proportion of males and females, respectively, who mate i times in round 1 and j times in round 2 (i, j taking values 0 or 1). The amount of sperm needed to guarantee fertilization is \(\epsilon _{0}\). If two males’ sperm compete for fertilization, any given sperm from the round 2 male is r times more likely to fertilize the female than any given sperm from the round 1 male. The aim was to find the best male strategy s of what proportion of sperm to invest in round 1.

Setting \(f_{1}=f_{10}+f_{11}\), the payoff to an \(s^{*}\) player in a population of s players was given byThey found that, except for non-generic cases, there is always a unique pure ESS value of s. This value was in general at least 1/2 but could be any value up to 1. The value of 1/2 occurred principally when every male mates in the first round, i.e. \(m=f_{1}\). The larger \(m/f_{1}\), the larger s, and it could be that \(s=1\) so all sperm is used in the first round (this occurred more commonly when \(\epsilon _{0}\) was relatively large).

The model of Fryer et al. [59] extended the above analysis to consider a guarding strategy, where instead of attempting to mate in the second round, a male could guard the female that he had mated with in the first round. If another male then attempted to mate with the female, this mating was prevented with probability \(\phi \). They again found a unique ESS for each case, where this could either be monomorphic guarding, a monomorphic population of non-guarders with a single s strategy (as in the original model where guarding was not allowed) or much more rarely a polymorphic mixture of guarding and a range of non-guarding strategies. An interesting recent model [160] made similar predictions to the above and was fitted with some success to data for three species.

In Southwell and Cannings [151], the state evolves over discrete-time steps, so that at each time step, each vertex simultaneously updates to the best response to their neighbours’ strategies.

A best response game on a graph is specified by an undirected graph \(G=(V,E),\) with a vertex set V and an edge set E and an n by n payoff matrix M. Vertices of the graph represent players. A state s of the system, at time step t,  is where each vertex v of G employs some pure strategy s(v) in \(\left\{ 1,\dots ,n\right\} .\) The model update rules are such that, in the state \(s'\) at time step \(t+1,\) a vertex v will employ the pure strategy i in \(\left\{ 1,\dots ,n\right\} \) which would have maximized their total payoff \(\sum _{u:\left\{ u,v\right\} \in E}M_{i,s(u)}\) against the strategy configuration their neighbours used at time step t. In other words, each player simultaneously updates to what they should have chosen against their current surroundings. Best response games of a similar nature were considered earlier in Berninghaus and Schwalbe [6, 7]; however, the study by Southwell and Cannings [151] was the first work to examine the possible dynamics of games with more than two strategies. In Southwell and Cannings [151] a geometric method was used to enumerate the different best response games on various graph structures like the complete graph and the circle. The best response for a particular vertex just depends upon the fraction of its neighbours which are using the different pure strategies. This information can be represented as a point in the \(n-1\)-dimensional strategy simplex using barycentric coordinates. The type of dynamics of a game just depends upon how such discrete points are partitioned into different best response regions (i.e. regions of the strategy simplex which have different pure best responses). By considering the different ways to partition the strategy simplex into convex best response regions with respect to the discrete points (that represent local strategy configurations) Southwell and Cannings [151] were able to enumerate the best response games on simple graph structures like circles and complete graphs. A classification of the dynamics of two-strategy best response games on circle graphs was also given. When there are more than two strategies, best response games on the circle can have complex dynamics. For example, there is a three-strategy game which (when played on the infinite circle/line) corresponds to the chaotic cellular automata rule 90 (see [91, 169]). Similarly complex dynamics have been observed in other types of games upon graphs [120].

Closer study of particular two-strategy best response games on graphs (and generalizations thereof) was carried out by Chris in Cannings [37]. In a majority game a player adopts the same strategy as the majority of its neighbours. The dual idea is the minority game, where a player adopts the same strategy as the minority of its neighbours. In Cannings [37] a combination of simulations and combinatorial methods was used to study such games on complete networks, hypercubes and a certain class of cubic networks. The different attractors of these dynamical systems, and their basins of attraction, were found in many cases. An interesting duality between the dynamics of minority and majority games was also noted. Further work along these lines was done in Haslegrave and Cannings [75] where it is shown that more interesting dynamics can take place when the network holds a single vertex that updates its strategy via different criteria.

The majority game can be thought of as a game on a graph, where matching a neighbour’s strategy provides unit payoff, whereas not matching its strategy provides zero payoff. A generalization of this is where each vertex v gets a payoff for using a strategy i in \(\left\{ 1,\dots ,n\right\} \) that is given by some (player, and strategy-specific) function of the number of neighbours using the same strategy. For such systems, Cannings and Cannings [40] settled the conjecture about the existence of a pure Nash equilibrium, negatively, by demonstrating the existence of such generalized coordination games with three players and three strategies which do not have pure Nash equilibria. This aided wider efforts to classify the game-theoretic properties of generalized network congestion games. These generalized congestion games have found numerous applications, especially for resource sharing in wireless networks [152, 154, 159]. Asynchronous updating is typically assumed in these systems, but results about Nash equilibria are useful irrespective of such details.

We shall start by discussing such games where the vertices on a graph reproduce and die based on their success levels in local interactions (see [147, 150]). As with the best response games, focus was on the deterministic case where the condition of each vertex is updated simultaneously. This allowed the usage of combinatorial methods to gain significant insights.

Such games on growing graphs are specified by an n by n payoff matrix, and a number called the fitness threshold. A system state is an undirected graph, where each vertex is associated with a pure strategy. The system is updated over discrete-time steps. A given update consists of two stages, the reproduction stage and then the killing stage. In the reproduction stage, each vertex simultaneously produces an offspring vertex, with the same strategy as the parent. There are eight possible models for how the connections of the offspring depends upon the parent, as we discuss below. For example, in the \(m=1\) model the offspring just inherit their parent’s neighbourhood (i.e. the offspring are born connected to the same individuals as the parent is connected to). After this reproduction stage, the second part of the update (the killing stage) consists of destroying all vertices that have a total payoff (added up, by playing a game with each neighbour, using their allocated strategies) that is below the fitness threshold.

Each of the eight different reproduction models is specified by three binary numbers \(r_{0},r_{1},r_{2}\) in \(\{0,1\}.\) The parents always retain their pre-existing connections, but the offspring’s connections are specified as follows:The model specified by the binary string \(r_{0},r_{1},r_{2}\) is called model number \(m=r_{0}2^{0}+r_{1}2^{1}+r_{2}2^{2}\). In models with \(m=0,2,4,5,6\) and 7 it is possible to gain significant understanding of the dynamics of general games [147, 150]. However, extremely complex and interesting behaviour can be produced in the \(m=1\) and \(m=3\) models.

One case that was studied in detail [147, 150] is where there is just one strategy, which scores a payoff of \(-1\) against itself, and the fitness threshold is \(-Q.\) In this case an individual survives the killing stage if and only if it has a degree less than Q, and so these systems correspond to a kind of degree capped reproduction where individuals reproduce, but die from overcrowding once they get more than Q neighbours. When reproduction takes place according to the \(m=1\) or \(m=3\) models, these systems can generate complex self-replicating structures.

Figure 1 shows a simple example of a self-replicating structure under the \(m=1\) model with degree cap \(Q=2\). When the degree cap Q is larger, much more interesting dynamics can occur, because the graph can grow larger before the highly connected vertices die. In many cases simple initial graph structures, like two vertices connected by a single edge, evolve to generate large collections of different connected components, which grow, change and self-replicate. For \(Q=8\) the degree capped reproduction model (using reproduction method \(m=1\)) eventually produces 723 different self-replicating structures. More structures are produced for higher-degree cap values, and there are many unanswered questions about these systems. In particular, it is unknown whether systems with a finite degree cap Q can generate connected components of arbitrary size or generate arbitrarily large numbers of non-isomorphic connected components. Studying these questions may give insight into how complex self-replicating structures arise from simple biologically inspired rules. Other types of model where the network structure changes as a result of strategic interaction were considered in Richter [139, 140]. Also, the remarkably complex dynamics observed in Southwell and Cannings [147] inspired the further search for simple network evolution rules inducing complexity [153].

In order to understand the basic network growth processes introduced in Southwell and Cannings [147], a study of the network dynamics under pure reproduction (i.e. with no game-based death) was considered in Southwell and Cannings [148]. In this case many aspects of the dynamics of the degree distribution, chromatic number, diameter, adjacency matrix, etc., can be understood. In most cases the growth dynamics are quite simple and can be expressed by applying graph products. However, in model \(m=3,\) where each vertex is born connected just to its parent and its parent’s neighbours, a complicated degree distribution arises, which was studied more closely in Jordan and Southwell [84]. In addition to studying the dynamics under pure reproduction, there has also been study of the systems where vertices die after they have survived more than a certain number of time steps [149]. The resulting systems could be considered to be a type of graphical generalization of the Leslie population model [97], where not only the number of individuals of different ages is modelled, but also the network structure connecting them. In Jordan [83] a generalization of the reproducing graph model was considered where links are formed at random.

A different type of model of network evolution was considered in Broom and Cannings [19], within which individuals form or break links at random, according to their degree. This forms an interesting model of sociability and behavioural response to epidemics. The basic idea is that each vertex has a pre-allocated minimum and maximum allowed degree. The system evolves via a Markov chain so that, at any given time, a vertex is chosen at random. If the vertex has more links than its maximum allowed degree, then one of its links is deleted randomly. If the vertex has less links than its minimum allowed degree, then a link is formed to a randomly selected unconnected individual. Otherwise no action is taken. Analysis revealed that these systems evolve to a closed class of structures, the minimal set, which Broom and Cannings [19] shows how to find the stationary distribution of, focusing on the special case where the maximum and minimum degrees are the same, i.e. each individual has a unique target.

Later work [20, 21, 39] explored the nature of the minimal set, classifying the vertices into four categories depending upon whether they always achieved their target, were never over target, never under target or could be under or over target. Interestingly, some vertices could be always on target even for a continuously changing process. They also investigated game-theoretic generalizations of this model, where formation and breaking of links also depend upon strategies employed by the vertices. In Broom and Cannings [21] in particular we can see that such games are inherently very complex, even for small populations.