Learning and Evolution in Games: ESS

Abstract

The ESS concept, developed in the 1970s to predict through static fitness comparisons the evolutionary outcome of individual behaviours in a biological species, emerged as the cornerstone of evolutionary game theory. This theory is now as central to the analysis of strategic interactions in the social and management sciences as in the life sciences. The ESS also addresses stability questions for dynamics describing how individual behaviours evolve over time. Here, we summarize ESS theory as originally developed for symmetric two-player games and then discuss generalizations to population games, extensive form games, games with continuous strategy spaces, asymmetric and bimatrix games.

Introduction

According to John Maynard Smith in his influential book Evolution and the Theory of Games (1982, p.10), an ESS (that is, an evolutionarily stable strategy) is ‘a strategy such that, if all members of the population adopt it, then no mutant strategy could invade the population under the influence of natural selection’. The ESS concept, based on static fitness comparisons, was originally introduced and developed in the biological literature (Maynard Smith and Price 1973) as a means to predict the eventual outcome of evolution for individual behaviours in a single species. It avoids the complicated dynamics of the evolving population that may ultimately depend on spatial, genetic and population size effects.

To illustrate the Maynard Smith (1982) approach, suppose individual fitness is the expected payoff in a random pairwise contest. The ESS strategy p^* must then do at least as well as a mutant strategy p in their most common contests against p^* and, if these contests yield the same payoff, then p^* must do better than p in their rare contests against a mutant. That is, Maynard Smith’s definition applied to a symmetric two-player game says p^* is an ESS if and only if, for all p ≠ p^*,

$$ {\displaystyle \begin{array}{ll}\hfill & (i)\kern1em \pi \left(p,{p}^{\ast}\right)\le \pi \left({p}^{\ast },{p}^{\ast}\right)\kern0.5em \left(\mathrm{equilibrium}\kern0.17em \mathrm{condition}\right)\\ {}& (ii)\kern1.25em \mathrm{if}\pi \left(p,{p}^{\ast}\right)=\pi \left({p}^{\ast },{p}^{\ast}\right),\hfill \\ {}& \kern0.62em \pi \left(p,p\right)<\pi \left({p}^{\ast },p\right)\kern1.25em (stabilitycondition)\hfill \end{array}} $$

(1)

where $\pi \left(p,\widehat{p}\right)$ is the payoff of p against $\widehat{p}$. One reason the ESS concept has proven so durable is that it has equivalent formulations that are equally intuitive (see especially the concepts of invasion barrier and local superiority in Section “Normal Form Games”).

By (1) (i), an ESS is a Nash equilibrium (NE) with the extra refinement condition (ii) that seems heuristically related to dynamic stability. In fact, there is a complex relationship between the static ESS conditions and dynamic stability, as illustrated throughout this article with specific reference to the replicator equation. It is this relationship that formed the initial basis of what has come to be known as ‘evolutionary game theory’.

ESS theory (and evolutionary game theory in general) has been extended to many classes of games besides those based on a symmetric two-player game. This article begins with ESS theory for symmetric normal form games before briefly describing the additional features that arise in each of several types of more general games. The unifying principle of local (or neighborhood) superiority will emerge in the process.

ESS for Symmetric Games

In a symmetric evolutionary game, there is a single set S of pure strategies available to the players, and the payoff to pure strategy e_i is a function π_i of the system’s strategy distribution. In the following subsections we consider two-player symmetric games with S finite in normal and extensive forms (Sections “Normal Form Games” and “Extensive Form Games” respectively) and with S a continuous set (Section “Continuous Strategy Space”).

Normal Form Games

Let S ≡ {e₁, ... , e_n} be the set of pure strategies. A player may also use a mixed strategy p ∈ Δⁿ ≡ {p = (p₁, ... , p_n)| ∑p_i = 1, p_i ≥ 0} where p_i is the proportion of the time this individual uses pure strategy e_i. Pure strategy e_i is identified with the ith unit vector in Δⁿ. The population state is $\widehat{p}\in {\varDelta}^n$ whose components are the current frequencies of strategy use in the population (that is, the strategy distribution). We assume the expected payoff to p is the bilinear function $\pi \left(p,\widehat{p}\right)={\sum}_{i,j=1}^n{p}_i\pi \left({e}_i,{e}_j\right){\widehat{p}}_j$ resulting from random two-player contests.

Suppose the resident population is monomorphic at p^* (that is, all members adopt strategy p^*) and a monomorphic sub-population of mutants using p appears in the system. These mutants will not invade if there is a positive invasion barrier ε₀(p) (Bomze and Pötscher 1989). That is, if the proportion ε of mutants in the system is less than ε₀(p), then the mutants will eventually die out due to their lower replication rate. In mathematical terms, ε = 0 is a (locally) asymptotically stable rest point of the corresponding resident-mutant invasion dynamics. For invasion dynamics based on replication, Bomze and Pötscher show p^* is an ESS (that is, satisfies (1)) if and only if every p ≠ p^* has a positive invasion barrier.

Important and somewhat surprising consequences of an ESS p^* are its asymptotic stability for many evolutionary dynamics beyond these monomorphic resident systems invaded by a single type of mutant. For instance, p^* is asymptotically stable when simultaneously invaded by several types of mutants and when a polymorphic resident system consisting of several (mixed) strategy types whose average strategy is p^* is invaded (see the ‘strong stability’ concept developed in Cressman 1992). In particular, p^* is asymptotically stable for the replicator equation (Taylor and Jonker 1978; Hofbauer et al. 1979; Zeeman 1980)

$$ {\dot{p}}_i={p}_i\left(\pi \left({e}_i,p\right)-\pi \left(p,p\right)\right) $$

(2)

when each individual player is a pure strategist.

Games that have a completely mixed ESS (that is, p^* is in the interior of Δⁿ) enjoy further dynamic stability properties since these games are strictly stable (that is, $\pi \left(p-\widehat{p},p-\widehat{p}\right)<0$ for all $p\ne \widehat{p}$) (Sandholm 2006). The ESS of a strictly stable game is also globally asymptotically stable for the best response dynamics (the continuous-time version of fictitious play) (Hofbauer and Sigmund 1998) and for the Brown–von Neumann–Nash dynamics (related to Nash’s 1951, proof of existence of NE) (Hofbauer and Sigmund 2003).

The preceding two paragraphs provide a strong argument that an ESS will be the ultimate outcome of the evolutionary adjustment process. The proofs of these results use two other equivalent characterizations of an ESS p^* of a symmetric normal form game; namely,

• (a) p^* has a uniform invasion barrier (i.e. ε₀(p) > 0 is independent of p)

• (b) for all p sufficiently close (but not equal) to p^*

$$ \pi \left(p,p\right)<\pi \left({p}^{\ast },p\right). $$

(3)

It is this last characterization, called ‘local superiority’ (Weibull 1995), that proves so useful for other classes of games (see below). Heuristically, (3) suggests p^* will be asymptotically stable since there is an incentive to shift towards p^* whenever the system is slightly perturbed from p^*.

Unfortunately, there are many normal form games that have no ESS. These include most three-strategy games classified by Zeeman (1980) and Bomze (1995). No mixed strategy p^* can be an ESS of a symmetric zero-sum game (that is, $\pi \left(\widehat{p},p\right)=-\pi \left(p,\widehat{p}\right)$ for all p, $\widehat{p}\in {\varDelta}^n$) since π(p^∗, p) = π(p^∗ − p, p) ≤ 0 = π(p, p) for all p ∈ Δⁿ in some direction from p^*. Thus, the classic zero-sum Rock–Scissors–Paper Game in Table 1 has no ESS since its only $\mathrm{NE}\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$ is interior. An early attempt to relax the ESS conditions to rectify this replaces the strict inequality in (1) (ii) by π(p, p) ≤ π(p^*, p). The NE p^* is then called a neutrally stable strategy (NSS) (Maynard Smith 1982, Weibull 1995). The only NE of the Rock–Scissors–Paper Game is a NSS.

The Payoff Matrix for the Rock–Scissors–Paper Game

$$ {\displaystyle \begin{array}{c}\hfill \mathrm{Rock}\hfill \\ {}\hfill \mathrm{Scissors}\hfill \\ {}\hfill \mathrm{Paper}\hfill \end{array}}\left[\begin{array}{ccc}\hfill 0\hfill & \hfill 1\hfill & \hfill -1\hfill \\ {}\hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ {}\hfill 1\hfill & \hfill -1\hfill & \hfill 0\hfill \end{array}\right] $$

Each entry is the payoff to the row player when column players are listed in the same order.

Also, the normal forms of most interesting extensive form games have no ESS, especially when NE outcomes do not specify choices off the equilibrium path and so correspond to NE components. In general, when NE are not isolated, the ESSet introduced by Thomas (1985) is more important. This is a set E of NSS so that (1) (ii) holds for all p^* ∈ E and p ∉ E. An ESSet is a finite union of disjoint NE components, each of which must be an ESSet in its own right. Each ESSet has setwise dynamic stability consequences analogous to an ESS (Cressman 2003). The ES structure of a game refers to its collection of ESSs and ESSets.

There are then several classes of symmetric games that always have an ESSet. Every two-strategy game has an ESSet (Cressman 2003) which generically (that is, unless $\pi \left(\widehat{p},\widehat{p}\right)=\pi \left(p,\widehat{p}\right)$ for all p, $\widehat{p}\in {\varDelta}^2$ is a finite set of ESSs. All games with symmetric payoff function (that is, $\pi \left(\widehat{p},p\right)=\pi \left(p,\widehat{p}\right)$ for all p, $\widehat{p}\in {\varDelta}^n$) have an ESSet corresponding to the set of local maxima of π(p, p) which generically is a set of isolated ESSs). These are called partnership games (Hofbauer and Sigmund 1998) or common interest games (Sandholm 2006).

Symmetric games with payoff, ${\pi}_i\left(\widehat{p}\right)$, of pure strategy e_i nonlinear in the population state $\widehat{p}$ are quite common in biology and in economics (Maynard Smith 1982; Sandholm 2006), where they are called playing-the-field models or population games. With ${\pi}_i\left(p,\widehat{p}\right)={\sum}_i{p}_i{\pi}_i\left(\widehat{p}\right)$, nonlinearity implies (1) is a weaker condition than (3), as examples in Bomze and Pötscher (1989) show. Local superiority (3) is then taken as the operative definition of an ESS p^* (Hofbauer and Sigmund 1998) and it is equivalent to the existence of a uniform invasion barrier for p^*.

Extensive Form Games

The application of ESS theory to finite extensive form games has been less successful (see Fig. 1). Every ESS can have no other realization equivalent strategies in its normal form (van Damme 1991) and so, in particular, must be pervasive strategy (that is, it must reach every information set when played against itself). To ease these problems, Selten (1983) defined a direct ESS in terms of behaviour strategies (that is, strategies that specify the local behaviour at each player information set) as a b^* that satisfies (1) for any other behaviour strategy b. He showed each such b^* is subgame perfect and arises from the backward induction technique applied to the ES structure of the subgames and their corresponding truncations.

Learning and Evolution in Games: ESS, Fig. 1

The extensive form tree of the van Damme example. For the construction of the tree of a symmetric extensive form game, see Selten (1983) or van Damme (1991)

Consider backward induction applied to Fig. 1. Its second-stage subgame ${\displaystyle \begin{array}{c}\hfill \ell \hfill \\ {}\hfill r\hfill \end{array}}\left[\begin{array}{cc}\hfill -5\hfill & \hfill 5\hfill \\ {}\hfill -4\hfill & \hfill 4\hfill \end{array}\right]$ has mixed ESS ${b}_2^{\ast }=\left(\frac{1}{2},\frac{1}{2}\right)$ and, when the second decision point of player 1 is replaced by the payoff 0 from b^*, the truncated single-stage game ${\displaystyle \begin{array}{c}\hfill L\hfill \\ {}\hfill R\hfill \end{array}}\left[\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ {}\hfill 1\hfill & \hfill 0\hfill \end{array}\right]$ also has a mixed ESS ${b}_1^{\ast }=\left(\frac{1}{2},\frac{1}{2}\right)$. Since both stage games have a mixed ESS (and so a unique NE since they are strictly stable), $\left({b}_1^{\ast },{b}_2^{\ast}\right)$ is the only NE of Fig. 1 and it is pervasive. Surprisingly, this example has no direct ESS as Selten originally hoped since $\left({b}_1^{\ast },{b}_2^{\ast}\right)$ can be invaded by the pure strategy that plays Rr (van Damme 1991).

The same technique applied to Fig. 1 with second-stage subgame replaced by ${\displaystyle \begin{array}{c}\hfill \ell \hfill \\ {}\hfill r\hfill \end{array}}\left[\begin{array}{cc}\hfill -1\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill -1\hfill \end{array}\right]$ yields ${b}_2^{\ast }=\left(\frac{1}{2},\frac{1}{2}\right)$ and truncated single-stage game ${\displaystyle \begin{array}{c}\hfill L\hfill \\ {}\hfill R\hfill \end{array}}\left[\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ {}\hfill 1\hfill & \hfill -1/2\hfill \end{array}\right]$ with ${b}_1^{\ast }=\left(\frac{3}{5},\frac{2}{5}\right)$. This is an example of a two-stage War of Attrition with base game $\left[\begin{array}{cc}\hfill 0\hfill & \hfill 1\hfill \\ {}\hfill 1\hfill & \hfill 0\hfill \end{array}\right]$ where a player remains (R) at the first stage in the hope the opponent will leave (L) but incurs a waiting cost of one payoff unit if both players remain. This $\left({b}_1^{\ast },{b}_2^{\ast}\right)$ is a direct ESS since all N-stage War of Attrition games are strictly stable (Cressman 2003).

The examples in the preceding two paragraphs show that, although backward induction determines candidates for the ES structure, it is not useful for determining which candidates are actually direct ESSs. The situation is more discouraging for non-pervasive NE. For example, the only NE outcome of the two-stage repeated Prisoner’s Dilemma game (Nachbar 1992) with cumulative payoffs is mutual defection at each stage. This NE outcome cannot be an isolated behaviour strategy (that is, there is a corresponding NE component) and so there is no direct ESS. Worse, for typical single-stage payoffs such as, ${\displaystyle \begin{array}{c}\hfill \mathrm{Defect}\hfill \\ {}\hfill \mathrm{Cooperate}\hfill \end{array}}\left[\begin{array}{cc}\hfill -1\hfill & \hfill 10\hfill \\ {}\hfill -2\hfill & \hfill 5\hfill \end{array}\right]$ this component does not satisfy setwise extensions of the ESS (for example, it is not an ESSet).

Characterization of NE found by backward induction with respect to dynamically stable rest points of the subgames and their truncations shows more promise. Each direct ESS b^* yields an ESSet in the game’s normal form (Cressman 2003) and so is dynamically stable. Furthermore, for the class of simultaneity games where both players know all player actions at earlier stages, Cressman shows that, if b^* is a pervasive NE, then it is asymptotically stable with respect to the replicator equation if and only if it comes from this backward induction process. In particular, the NE for Fig. 1 and for the N-stage War of Attrition are (globally) asymptotically stable. Although the subgame perfect NE for the N-stage Prisoner’s Dilemma game that defects at each decision point is not asymptotically stable, the eventual outcome of evolution is in the NE component (Nachbar 1992; Cressman 2003).

Continuous Strategy Space

Evolutionary game theory for symmetric games with a continuous set of pure strategies S has been slower to develop. Most recent work examines static payoff comparisons that predict an x^* ∈ S is the evolutionary outcome. There are now fundamental differences between the ESS notion (1) and that of local superiority (3) as well as between invasion by monomorphic mutant sub-populations and the polymorphic model of the replicator equation. Here, we illustrate these differences when S is a subinterval of real numbers and π(x, y) is a continuous payoff function of x , y ∈ S.

First, consider an x^* ∈ S that satisfies (3). In particular,

$$ \pi \left(x,x\right)<\pi \left({x}^{\ast },x\right) $$

(4)

for all x ∈ S sufficiently close (but not equal) to x^*. This is the neighbourhood invader strategy (NIS) condition of Apaloo (1997) that states x^* can invade any nearby monomorphism x. On the other hand, from (1), x^* cannot be invaded by these x if it is a neighbourhood strict NE, that is

$$ \pi \left(x,{x}^{\ast}\right)<\pi \left({x}^{\ast },{x}^{\ast}\right) $$

(5)

for any other x sufficiently close to x^*. Inequalities (4) (5) are independent of each other and combine to assert that x^* strictly dominates x in all these two-strategy games {x^*, x}.

In the polymorphic model, populations are described by a P in the infinite dimensional set Δ(S) of probability distributions with support in S. When the expected payoff π(x, P) is given through random pairwise contests, Cressman (2005) shows that strict domination implies x^* is neighbourhood superior (that is,

$$ \pi \left({x}^{\ast },P\right)>\pi \left(P,P\right) $$

(6)

for all other P ∈ Δ(S) with support sufficiently close to x^*) and conversely, neighbourhood superiority implies weak domination. Furthermore, a neighborhood superior monomorphic population x^* (that is, the Dirac delta probability distribution δx^*) is asymptotically stable for all initial P with support sufficiently close to x (and containing x^*) under the replicator equation. This is now a dynamic on Δ(S) (Oechssler and Riedel 2002) that models the evolution of the population distribution.

In the monomorphic model, the population is a monomorphism x(t) ∈ S at all times. If a nearby mutant strategy y ∈ S can invade x, the whole population is shifted in this direction. This intuition led Eshel (1983) to define a continuously stable strategy (CSS) as a neighbourhood strict NE x^* that satisfies, for all x sufficiently close to x^*,

$$ \pi \left(y,x\right)>\pi \left(x,x\right) $$

(7)

for all y between x^* and x that are sufficiently close to x. Later, Dieckmann and Law (1996) developed the canonical equation of adaptive dynamics to model the evolution of this monomorphism and showed a neighbourhood strict NE x^* is a CSS if and only if it is an asymptotically stable rest point. Cressman (2005) shows x^* is a CSS if and only if it is neighbourhood half-superior (that is, there is a uniform invasion barrier of at least $\frac{1}{2}$ in the two-strategy games {x^*, x}) (see also the half-dominant concept of Morris et al. 1995).

For example, take S = R and payoff function

$$ \pi \left(x,y\right)=-{x}^2+ bxy $$

(8)

that has strict NE x^* = 0 for all values of the fixed parameter b. x^* is a NIS (CSS) if and only if b< 1 (b< 2) (Cressman and Hofbauer, 2005). Thus, there are strict NE when b> 2 that are not ‘evolutionarily stable’.

Asymmetric Games

Following Selten (1980) and van Damme (1991), in a two-player asymmetric game with two roles (or species), pairwise contests may involve players in the same or in opposite roles. First, consider ESS theory when there is a finite set of pure strategies S = {e₁, ... , e_n} and T = {f₁, ... , f_m} for players in role 1 and 2 respectively. Assume payoff to a mixed strategist is given by a bilinear payoff function and let ${\pi}_1\left(p;\widehat{p},\widehat{q}\right)$ be the payoff to a player in role one using p ∈ Δⁿ when the current state of the population in roles 1 and 2 are $\widehat{p}$ and $\widehat{q}$ respectively. Similarly, ${\pi}_2\left(q;\widehat{p},\widehat{q}\right)$ is the payoff to a player in role 2 using q ∈ Δ^m. For a discussion of resident-mutant invasion dynamics, see Cressman (1992), who shows the monomorphism (p^*,q^*) is uninvadable by any other mutant pair (p, q) if and only if it is a two-species ESS, that is, for all (p, q) sufficiently close (but not equal) to (p^*, q^*),

$$ \mathrm{either}\kern0.48em {\pi}_1\left(p;p,q\right)<{\pi}_1\left({p}^{\ast };p,q\right)\kern0.48em \mathrm{or}\kern0.48em {\pi}_2\left(q;p,q\right)<{\pi}_2\left({q}^{\ast };p,q\right). $$

(9)

The ESS condition (9) is the two-role version of local superiority (3) and has an equivalent formulation analogous to (1) (Cressman 1992). This ESS also enjoys similar stability properties to the ESS of Subsection “Normal Form Games” such as its asymptotic stability under the (two-species) replicator equation (Cressman 1992, 2003).

A particularly important class of asymmetric games consists of truly asymmetric games that have no contests between players in the same role (that is, there are no intraspecific contests). These are bimatrix games (that is, given by an n × m matrix whose ijth entry is the pair of payoffs (π₁(e_i, f_j ), π₂(e_i, f_j )) for the interspecific contest between e_i and f_j). The ESS concept is now quite restrictive since Selten (1980) showed that (p^*, q^*) satisfies (9) if and only if it is a strict NE. This is also equivalent to asymptotic stability under the (two-species) replicator equation (Cressman 2003). Standard examples (Cressman 2003), with two strategies for each player include the Buyer–Seller Game that has no ESS since its only NE is in the interior. Another is the Owner–Intruder Game that has two strict NE Maynard Smith (1982) called the bourgeois ESS where the owners defend their territory and the paradoxical ESS where owners retreat.

Asymmetric games with continuous sets of strategies have recently received a great deal of attention (Leimar 2006). For a discussion of neighbourhood (half) superiority conditions that generalize (6) and (7) to two-role truly asymmetric games with continuous payoff functions, see Cressman (2005). He also shows how these conditions are related to NIS and CSS concepts based on (9) and to equilibrium selection results for games with discontinuous payoff functions such as the Nash Demand Game (Binmore et al. 2003).

See Also

• Deterministic Evolutionary Dynamics

• Learning and Evolution in Games: An Overview