6  Evolutionary dyanmics

Author

Affiliation

Aditya Mahajan

McGill University

As we saw earlier, one of the interpretations of mixed strategy NE is that it determines the fraction of population playing a certain pure strategy. Maynard Smith and Price (1973) used this interpretation to propose an evolutionary mechanism via which organisms can change their behavior across generations. For a facinating (non-technical) introduction to the area, see Maynard Smith (1982).

The key idea in what is now called evolutionary game theory is that of evolutionarily stable strategies (ESS), which we will discuss here. For detailed treatment of the subject, see Sandholm (2010).

6.1 Evolutionary stable strategies (ESS)

To understand evolutionary stability, consider the variation of Hawk-Dove game shown below.

A variation of the Hawk-Dove game

	$\mathsf{D}$		$\mathsf{H}$
$\mathsf{D}$	$4$	$4$	$2$	$8$
$\mathsf{H}$	$8$	$2$	$1$	$1$

Note that this is a symmetric game. Now suppose that there is a large population comprising of 80% doves and 20% hawks. THus, we are considering the population state \(σ = (0.8, 0.2)\).

We assume that there are repeated interactions between the organisms (or agents) in the population. At state \(σ\) described above, a generic agent will encounter a dove with probability \(0.8\) and a hawk with probability \(0.2\). Thus, if this organism is a dove, his payoff is \[ U(\mathsf{D}, σ) = 0.8 × 4 + 0.2 × 2 = 3.6. \] On the other hand, if this organism is a hawk, then his payoff is \[ U(\mathsf{H}, σ) = 0.8 × 8 + 0.2 × 1 = 6.6. \] The argument of Maynard Smith (1982) is that in this situation, the population of hawks have an evolutionary advantage. So, over time, the fraction of hawks will increase. The population state \(σ^*\) where no trait has an evolutionary advantage is given by \[ U(\mathsf{H}, σ^*) = U(\mathsf{D}, σ^*) \] which is precisely the NE of the game.

Now the key difference in this interpretation from NE is how we determine if an equilibrium is sustainable. To define sustainability, we introduce some notation. Consider a symmetric two player game \(\mathscr{G} = \langle 2, (\ALPHABET S_1, \ALPHABET S_2), (u_1, u_2) \rangle\) where \(\ALPHABET S_1 = \ALPHABET S_2\) and \(u_1(s,t) = u_2(t,s)\) for all \(t, s \in \ALPHABET S_1\). For the ease of notation, we will denote \(\ALPHABET S_1\) and \(\ALPHABET S_2\) simply as \(\ALPHABET S\) (note that this is inconsistent with the notation that we use in general!) and denote the payoff function by \(u \colon \ALPHABET S × \ALPHABET S \to \reals\) where \[ u(s,t) = u_1(s,t) = u_2(t,s). \]

Consider a symmetric mixed strategy \(σ^*\), i.e., we have a large population where \(σ^*(s)\) fraction of the population is of type \(s\), \(s \in \ALPHABET S\).

Now suppose a fraction \(ε\) of the population mutates and starts playing another strategy \(σ\). Thus, the new state of the population is \[ \bar σ_{ε} = (1-ε) σ^* + ε σ \]

Then, the average payoff of a normal player (i.e., the player belonging to the unmutated population) is \[\def\1{\textcolor{red}{σ^*}} U(\1, \bar σ_{ε}) = (1-ε) U(\1, σ^*) + ε U(\1, σ). \] Similarly, the average payoff of a mutated player is \[\def\1{\textcolor{red}{σ}} U(\1, \bar σ_{ε}) = (1-ε) U(\1, σ^*) + ε U(\1, σ). \]

Definition 6.1 A population state \(σ^*\) is said to be evolutionarily stable strategy (ESS) if for all mutations \(σ \in Δ(\ALPHABET S)\), \(σ \neq σ^*\), there exists a \(ε_\circ = ε_\circ(σ) > 0\) such that for all \(ε \in (0, ε_\circ)\) and \(\bar σ_{ε} = (1 -ε) σ^* + ε σ\), we have \[ U(σ^*, \bar σ_{ε}) > U (σ, \bar σ_{ε}). \] i.e., \[\begin{equation}\label{eq:ESS} (1-ε)U(σ^*, σ^*) + ε U(σ^*, σ) > (1-ε)U(σ, σ^*) + ε U(σ, σ). \end{equation}\]

6.2 Relationship between NE and ESS

If we take the limit as \(ε \to 0\) in the definition of ESS, we get that an ESS has be a symmetric NE. Thus, all ESS are NE. We now present an example to show that not all NE are ESS.

Consider the variation of Hawk Dove shown below.

A variation of the Hawk-Dove game

	$\mathsf{D}$		$\mathsf{H}$
$\mathsf{D}$	$4$	$4$	$2$	$2$
$\mathsf{H}$	$2$	$2$	$2$	$2$

This game has two pure strategy NE: \((\mathsf{D}, \mathsf{D})\) and \((\mathsf{H}, \mathsf{H})\). We now check if each of these is ESS.

• Consider the NE \((\mathsf{D}, \mathsf{D})\), i.e., \(σ^* = (1,0)\). Consider a mutation \(σ = (p, 1-p)\), where \(p < 1\). Then, \[\begin{align*} U(σ^*, σ^*) &= 4 & U(σ^*, σ) &= 4p + 2(1-p) = 2p + 2 \\ U(σ, σ^*) &= 2p + 2 & U(σ, σ) &= 4p^2 + 2(1-p^2) = 2p^2 + 2 \end{align*}\] Therefore, \[ U(σ^*, σ_{ε}) = (1-ε)4 + ε(2p + 2) = 4 - 2 ε(1-p) \] and \[ U(σ, σ_{ε}) = (1-ε)(2p+2) + ε(2p^2 + 2) = (2p+2) - 2p ε(1-p). \] Consider \[\begin{align*} U(σ^*, σ_{ε}) - U(σ, σ_{ε}) &= 4 - 2 ε(1-p) - (2p+2) + 2p ε(1-p) \\ &= 2(1 - p - ε(1-p)^2) \\ &= 2(1-p)(1 - ε(1-p)) \end{align*}\] Thus, for any \(p \in [0, 1)\) (note that \(p=1\) is ruled out because the mutation cannot be the same as the normal population), and any \(ε \in (0, 1)\), we have that \[ U(σ^*, σ_{ε}) - U(σ, σ_{ε}) > 0. \] So, \((\mathsf{D}, \mathsf{D})\) is an ESS.

• Consider the NE \((\mathsf{H}, \mathsf{H})\), i.e., \(σ^* = (0, 1)\). Consider a mutation \((p, 1-p)\), where \(p > 0\). Then, \[\begin{align*} U(σ^*, σ^*) &= 2 & U(σ^*, σ) &= 2 \\ U(σ, σ^*) &= 2 & U(σ, σ) &= 4p^2 + 2(1-p^2) = 2p^2 + 2 \end{align*}\] Therefore, \[ U(σ^*, σ_{ε}) = (1-ε)2 + ε2 = 2 \] and \[ U(σ, σ_{ε}) = (1-ε)2 + ε(2p^2 + 2) = 2 - 2 ε p^2 \] Consider \[ U(σ^*, σ_{ε}) - U(σ, σ_{ε}) = 2 - 2 - 2 ε p^2 = -2 ε p^2 \] which is strictly positive for any \(p \in (0, 1]\) (note that \(p = 0\) is ruled out because the mutation cannot be the same as the normal population) and \(ε > 0\), we have \[ U(σ^*, σ_{ε}) - U(σ, σ_{ε}) < 0. \] So, \((\mathsf{H}, \mathsf{H})\) is not an ESS.

6.3 Necessary and sufficient conditions for ESS

Theorem 6.1 A strategy \(σ^*\) is ESS if and only if for every \(σ \neq σ^*\) one of the following conditions is true:

1. \(U(σ^*, σ^*) > U(σ, σ^*)\)

   That is, if a mutation deviates from \(σ^*\) it will lose in its encounters with the normal population

2. \(U(σ^*, σ^*) = U(σ, σ^*)\) and \(U(σ^*, σ) > U(σ,σ)\).

   That is, if the payoff that a mutation receives from encountering the normal population is equal to the payoff that a normal indvidual receives from encountering the normal population, that mutation will receive a smaller payer if it encounters the same mutation than a normal individual will receive in the encounter

Proof

• ESS implies the two conditions: Let \(σ^*\) be an ESS. As argued earlier, this implies that \(σ^*\) is also a NE. Thus, \[ U(σ^*, σ^*) \ge U(σ, σ^*), \quad \forall σ \in Δ(\ALPHABET S). \] We prove the result by contradiction. Suppose that neither of the two conditions hold. Then, there must exist an \(σ \neq σ^*\) such that \[ U(σ^*, σ^*) = U(σ, σ^*) \quad\text{and}\quad U(σ^*, σ) \le U(σ, σ). \] This implies that for any \(ε \in (0,1)\) \[ (1-ε)U(σ^*, σ^*) + ε U(σ^*, σ) \le (1-ε)U(σ, σ^*) + ε U(σ, σ) \] which contradicts the fact that \(σ^*\) is ESS.

• The two conditions imply ESS: Suppose a mutation \(σ\) satisfies condition 1. Let \(D = U(σ^*, σ^*) - U(σ, σ^*)\) and \[ M = \max_{σ,τ} U(σ,τ) - \min_{σ,τ} u(σ,τ). \] Moreover, for any \(ε \in (0,1)\), define \(\bar σ_{ε} = (1-ε) σ^* + ε σ\). Then, \[\begin{align*} U(σ^*, \bar σ_{ε}) - U(σ, \bar σ_{ε}) &= (1-ε) \bigl[ U(σ^*, σ^*) - U(σ, σ^*) \bigr] + ε \bigl[ U(σ^*, σ) - U(σ, σ) \bigr] \\ & \ge (1-ε) D - ε M \end{align*}\] which is positive for \(ε < D/(D+M)\).

  Now suppose a mutation statisfied condition 2. Then, \[\begin{align*} U(σ^*, \bar σ_{ε}) - U(σ, \bar σ_{ε}) &= (1-ε) \underbrace{\bigl[ U(σ^*, σ^*) - U(σ, σ^*) \bigr]}_{=0} + ε \underbrace{\bigl[ U(σ^*, σ) - U(σ, σ) \bigr]}_{> 0} \\ &> 0, \quad \forall ε \in (0,1). \end{align*}\]

Since every mutation must satisfy either condition 1 or 2, we have that the strategy \(σ^*\) is ESS.

Example 6.1 Consider the modified Hawk Dove game shown below.

A variation of the Hawk-Dove game

	$\mathsf{D}$		$\mathsf{H}$
$\mathsf{D}$	$4$	$4$	$2$	$8$
$\mathsf{H}$	$8$	$2$	$1$	$1$

We can verify that the unique NE is \(σ^* = (\tfrac 15, \tfrac 45)\). Is this an ESS?

Solution

Consider a mutation \(σ = (p, 1-p)\). We verify the two sufficient and necessary conditions of Theorem 6.1 separately.

• Check condition 1: Since \(σ^*\) is a NE with support \(\{\mathsf{H}, \mathsf{D}\}\), from irrelevance principle we must have \[ U(\mathsf{H}, σ^*) = U(\mathsf{D}, σ^*). \] This means that for any mixed strategy \(σ\), we will have \[ U(σ, σ^*) = U(σ^*, σ^*). \] So, condition 1 is never satisfied.

• Check condition 2: Since \(U(σ, σ^*) = U(σ^*, σ^*)\), condition 2 is satisfied if \(U(σ^*, σ) > U(σ, σ)\). Observe that \[ U(σ^*, σ) = \frac{4p}{5} + \frac{2(1-p)}{5} + \frac{32p}{5} + \frac{4(1-p)}{5} = \frac{6}{5} + 6p \] and \[ U(σ, σ) = 4p^2 + 2p(1-p) + 8(1-p)p + (1-p)^2 = 1 + 8p - 5p^2 . \] Thus, \[ U(σ^*, σ) - U(σ,σ) = \frac{1}{5} - 2p + 5p^2 = \frac{(1-5p)^2}{5} \] which is non-negative for all \(p \neq \tfrac 15\) (i.e., all \(σ \neq σ^*\)). Thus, condition 2 holds and therefore \(σ^*\) is ESS.

6.4 ESS for arbitrary two player \(2 × 2\) symmeric games

Consider a symmetric two player \(2 × 2\) game.

	$\mathsf{1}$		$\mathsf{2}$
$\mathsf{1}$	$a$	$a$	$b$	$c$
$\mathsf{2}$	$c$	$b$	$d$	$d$

A symmetric mixed strategy \((σ^*, σ^*)\) with \(σ^* = (p, 1-p)\) is a NE if and only if \[ a p + b(1-p) = c p + d (1-p) \implies p = \frac{b - d}{(b+c) - (a+d)}. \] This is a valid probability distribution if either

1. Both numerator and denominator are positive and numerator is less than the denominator

2. Both numerator and denominator are negative and numerator is more than the denominator

Note that there wil also be cases where \(b = d\) or \(a = c\) where there will be multiple equilibria. We do not consider these cases here.

• Case 1: In this case, we have

  • numerator is positive, i.e., \(b > d\)
  • denominator is positive, i.e., \(b+c > a + d\)
  • numerator is less than denominator, i.e., \(c > a\).

  Thus, \[ \bbox[5pt,border: 1px solid]{ b > d \quad\text{and}\quad c > a } \]

• Case 2: In this case, we have

  • numerator is negative, i.e., \(b < d\)
  • denominator is negative, i.e., \(b+c < a + d\)
  • numerator is more than denominator, i.e., \(c < a\).

  Thus, \[ \bbox[5pt,border: 1px solid]{ b < d \quad\text{and}\quad c < a } \]

When is this mixed strategy NE an ESS?

Since \(p \in (0,1)\), for any other \(σ = (q, 1-q)\), we will have \(U(σ, σ^*) = U(σ^*, σ^*)\). So, we only need to check condition 2 of Theorem 6.1. For that mater, consider \[\begin{align*} U(σ, σ^*) - U(σ, σ) &= (p - q) \big[ qa + (1-q) b \bigr] - (p - q) \bigl[ qc + (1-q) d \bigr] \\ &= (p -q) \bigl[ b - d - q( (b+c) - (a+d) ) \bigr] \\ &= (p - q)^2 ( (b+c) - (a+d) ) \end{align*}\] where the last equality uses the fact that \(b-d = p( (b+c) - (a+d) )\).

Thus, in case 1 we have \(U(σ, σ^*) - U(σ, σ)\) and therefore \(σ^*\) is an ESS while in case 2 we have \(U(σ, σ^*) - U(σ, σ) < 0\) and therefore \(σ^*\) is not an ESS.

6.4.0.1 General Hawk Dove game

Consider a general Hawk Dove game

A general Hawk-Dove game

	$\mathsf{D}$		$\mathsf{H}$
$\mathsf{D}$	$\frac{v - c}{2}$	$\frac{v - c}{2}$	$0$	$v$
$\mathsf{H}$	$v$	$0$	$\frac{v}{2}$	$\frac{v}{2}$

where

• \(v\) denotes the value of the resource
• \(c\) denotes the value lost due to fighting.

Characterize all NE of this game and verify if the symmetric NE are ESS.

Solution

We have the following cases.

• If \(\tfrac 12 (v-c) > 0\), then \((\mathsf{H}, \mathsf{H})\) is a NE in strictly dominated strategies (and also an ESS)

• If \(\tfrac 12 (v-c) = 0\), then \((\mathsf{H}, \mathsf{H})\) is a NE in weakly dominated strategies (and not an ESS)

• If \(\tfrac 12 (v-c) < 0\), then \((\mathsf{H}, \mathsf{D})\) and \((\mathsf{D}, \mathsf{H})\) are NE (but they are not symmetric). The symmetric NE in mixed strategies is \(σ^* = (p, 1-p)\) where \[ p = \frac{v - \tfrac 12 v}{v - (v - \frac{1}{2}c)} = \frac{v}{c}. \] Since in this case \(v > \frac 12 v\) and \(0 < \frac 12(v-c)\), we are in case 1 of the general setting and therefore this NE is ESS.

6.4.0.2 Medium Access Control

Consider a Medium Access Control game

Medium access control game

	$\mathsf{T}$		$\mathsf{D}$
$\mathsf{T}$	$ - c$	$ - c$	$v - c$	$0$
$\mathsf{D}$	$0$	$v - c$	$0$	$0$

where

• \(v\) denotes the value of communication
• \(c\) denotes the cost of communication

Assuming \(v > c\), characterize all NE of this game and verify if the symmetric NE are ESS.

Solution

In this case \((\mathsf{T}, \mathsf{D})\) and \((\mathsf{D}, \mathsf{T})\) are pure strategy NE of the game, but they are not symmetric. A symmetric mixed strategy of the form \((σ^*, σ^*)\) with \(σ^* = (p, 1-p)\) is mixed strategy NE where \[ -pc + (v-c)(1-p) = 0 \implies p = 1 - \frac{c}{v}. \] Since, \(v - c > 0\) and \(0 > -c\), we are in case 1 of the general setting and therefore \(σ^*\) is an ESS.

Example 6.2 (Medium Access Control with lost opportiunity cost) Consider a Medium Access Control game

Medium access control game with lost opportunity cost

	$\mathsf{T}$		$\mathsf{D}$
$\mathsf{T}$	$ - c$	$ - c$	$v - c$	$0$
$\mathsf{D}$	$0$	$v - c$	$ - d$	$ - d$

where

• \(v\) denotes the value of communication
• \(c\) denotes the cost of communication
• \(d\) denotes the cost of wasted channel

Assuming \(v > c\), characterize all NE of this game and verify if the symmetric NE are ESS.

Solution

In this case \((\mathsf{T}, \mathsf{D})\) and \((\mathsf{D}, \mathsf{T})\) are pure strategy NE of the game, but they are not symmetric. A symmetric mixed strategy of the form \((σ^*, σ^*)\) with \(σ^* = (p, 1-p)\) is mixed strategy NE where \[ -pc + (v-c)(1-p) = -d(1-p) \implies p = 1 - \frac{c}{v+d}. \] Note that this shows that adding a lost opportunity cost is equivalent to increasing the value of communication

Since, \(v - c > 0 > -d\) and \(0 > -c\), we are in case 1 of the general setting and therefore \(σ^*\) is an ESS.

6.5 A brief overview of evolutionary game theory

So far we have discussed evolutionarily stable equilibrium. In this section we discuss evolutionary game theory which rovides revision protocols that explain how a population state evolves over time to reach an ESS.

Consider a two player symmetric game with finite strategy space. let \(\ALPHABET S_1 = \ALPHABET S_2 = \{1, \dots, m\}\) and define \[ Δ^m = \biggl\{ (p_1, \dots, p_m) \in \reals^{m}_{\ge 0} : \sum_{i=1}^m p_i = 1 \biggr\}. \] For the ease of notation, we will use \(p = (p_1, \dots, p_m)\) (instead of \(σ\) used earlier) to denote a mixed strategy.

The simplest form of revision protocol is called replicator dynamics. Suppose there is a large population of \(N\) agents playing strategy \(p\). Let \(n_i = p_i N\) denote the number of agents playing pure strategy \(i\). Suppose \(r_i\) denotes the rate of change of \(n_i\), i.e., \[ \dot n_i = r_i n_i. \] This implies that \[ \dot N = \sum_{i=1}^m \dot n_i = \sum_{i=1}^m r_i n_i = \bar r N \] where \(\bar r = (r_1 p_1 + \dots + r_m p_m)\).

Recall that \(p_i = n_i/N\). Therefore, \[ \dot p_i = \frac{\dot n_i N - n_i \dot N}{N^2} = \frac{r_i n_i N - n_i \bar r N}{N^2} = p_i(r_i - \bar r). \] Thus, the differential equation \[ \bbox[5pt,border: 1px solid]{ \dot p_i = p_i (r_i - \bar r) } \] tells us how the population state changes over time.

In general the rate \(r_i\) of change of population \(i\) is some function of the population state. Motivated by the theory of evolution, the simplest assumption is that the rate of change equals the fitness function, i.e., \[ r_i = U(i, p). \] This means that \[ \bar r = \sum_{i=1}^m r_i p_i = \sum_{i=1}^m U(i,p) p_i = U(p, p). \] Substituting that back in the above differential equation we get \[ \bbox[5pt,border: 1px solid]{ \dot p_i = p_i \bigl[ U(i,p) - U(p,p) \bigr], \quad i \in \{1, \dots, m\} } \] This differential equation is called replicator dynamics.

An equilibrium point of this dynamics is one where \(\dot p_i = 0\) for all \(i\). This means that for all \(i\) either \(p_i = 0\) or \(U(i,p) = U(p,p)\). Thus, any NE of the game is an equilibrium point of the replicator dynamics. The converse is not true. For example, every pure strategy \(p\) satisfies the replicator dynamics.

6.6 Stability of equilibrium points of replicator dynamics

The next question is whether the equilibrium points of replicator dynamics are stable. Recall that there are three common notions of stability of differential equations. Consider the differential equation \[ \dot x = f(x) \] and let \(x_e\) be an equilibrium point (i.e., \(f(x_e) = 0\)).

• Lyapunov stability: if the intiail state lies in a small neighborhood of \(x_e\), then the trajectory of the differential equation remains in the neighborhood.

• Local asymptotic stability: If the initial state lies in a neighborhood of \(x_e\), then the trajectory of the trajectory of the differential equation converges to \(x_e\).

• Global asymptotic stability: For any initial state, the trajectory of the differential equation converges to \(x_e\).

The main result of replicator dynamics is the following.

Theorem 6.2  

1. An ESS \(p^*\) is locally asymptotically stable equilibrium point of the replicator dyanmics.

2. An ESS \(p^*\) in the interior of \(Δ^m\) is a globally asymptotically stable equilibrium point of the replicator dynamics.

Proof

The proof uses \(V(p) = \prod_{i=1}^m p_i^{p_i^*}\) as a Lyapunov function. See Hofbauer et al. (1979) for details.

6.7 Other evolutionary dynamics

Replicator dynamics are not ideal because they have the following property: if \(p_i = 0\) at some point then \(p_i = 0\) for all times in the future. To avoid this limitation, various other forms of evolutionary dynamics have been proposed in the literature. We list a few of them here:

• Best response dynamics \[ \dot p_i = \BR_i(p) - p_i, \quad i \in \{1, \dots, m\}. \] Since best response is not unique, this gives us a differential inclusion rather than a differential equation.

• Smoothed best response dynamics \[ \dot p_i = \sigma_i(p) - p_i, \quad i \in \{1, \dots, m\} \] where \[ σ_i(p) = \frac{\exp(η U(i,p))}{\sum_{j=1}^m \exp(η U(j,p))} \]

• Brown-von Neumann-Nash (BNN) dynamics: \[ \dot p_i = \hat U_i(p) - p_i \sum_{j=1}^m \hat U_j(p), \quad i \in \{1, \dots, m\} \] where \[ \hat U_i(p) = \max\{ U(i,p) - U(p,p), 0 \} \]

There are various stability results for these dynamics. These results rely on the notion of negative definite games and negative semi-definite games.

6.8 Negative definite and semidefinite games

For the ease of notation, define a \(m × m\) matrix \(Q\) such that \(Q_{ij} = u(i,j)\). Note that \[ U(i,p) = \sum_{j = 1}^m u(i,j) p_j = [Qp]_i \] and \[ U(q,p) = \sum_{i=1}^m q_i U(i,p) = q^\TRANS Q p. \] With this notation, we have the following:

• NE A strategy \(p\) is a NE if for all \(q \in Δ^m\), \[ p^\TRANS Q p \ge q^\TRANS Q p. \]

• ESS: A strategy \(p\) is ESS if for all \(q \in Δ^m\), \(q \neq p\), either of the following hold:

  1. \(p^\TRANS Q p > q^\TRANS Q p\)
  2. \(p^\TRANS Q p = q^\TRANS Q p\) and \(p^\TRANS Q q > q^\TRANS Q q\).

Define the set \(\reals^m_0\) as \(\{ q \in \reals^m : \sum_{i=1}^m q_i = 0 \}\). We say that a (symmetric) game is negative semidefinite if \[ q^\TRANS Q q \le 0, \quad \forall q \in \reals^m_0. \] We say that the game is negative definite if the inequality is strict for all \(q \neq 0\).

Analogously the game is said to be positive semidefinite if \[ q^\TRANS Q q \ge 0, \quad \forall q \in \reals^m_0. \] We say that the game is postiive definite if the inequality is strict for all \(q \neq 0\).

Negative definite/semidefinite games have the following properties:

1. A negative definite game has a unique NE (possibly at the boundary) which is also an ESS.

2. The set of NE of a negative semdefinite game is a convex subset of \(Δ^m\). These NE need not be ESS.

Example 6.3 (A modefied version of rock paper scissors) Consider a variation of rock paper scissors where \[ Q = \MATRIX{0 & -b & a \\ a & 0 & -b \\ -b & a & 0 }, \quad a, b > 0. \] The standard RPS is when \(a = b\). In all cases, it is easy to verify that \(p^* = (\tfrac 13, \tfrac 13, \tfrac 13)\) is the unique NE.

Show the following:

• If \(0 < b < a\), then the game is negative definite.
• If \(0 < a < b\), then the game is positive definite.

Proof

Take a \(q \in \reals^3_0\), i.e., \(q = (q_1, q_2, q_3)\) such that \(q_1 + q_2 + q_3 = 0\). Then, \[ q^\TRANS Q q = (a-b)[q_1q_2 + q_2 q_3 + q_3 q_1). \] Since \((q_1 + q_2)^2 = q_3^2\), we have that \(q_1q_2 = (q_3^2 - q_1^2 - q_2^2)/2\). Symmetric expressions hold for \(q_2q_3\) and \(q_3q_1\). Substituting these in the above equation, we have \[ q^\TRANS Q q = \frac{(b-a)}{2}(q_1^2 + q_2^2 + q_3^2). \] Then the result follows from the definition of positive and negative definite games.

6.9 Evolutionary dynamics and negative definite/semi-definite games

The main results for replicator dynamics is that for negative definite games (which have a unique NE that is also an ESS), the unique NE is globally asymptotically stable equilibrium point of replicator dynamics.

The big advantage of the modified dynamics is that for negative semi-definite games, the convex set of NE is globally asymptotically stable for BR and BNN dynamics.

The smoothed BR dynamics have the advantage that they are always globally asymptotically stable but their equilibrium points are not NE but something called perturbed NE.

See the book Sandholm (2010) for more details on evolutionary dynamics.

The above results imply that for the modified version of rock paper scissors considered in Example 6.3, replicator dynamics will converge for games where \(b < a\) but not when \(b = a\) (in which case the NE is not an ESS). However, BR and BNN dynamics will converge even when \(b = a\). The smoothed BR dynamics converge, but to a perturbed equilibrium point. We verify this numerically.

using DifferentialEquations, Plots

function replicator_dynamics!(dp, p, Q, t)
    dp .= p .* ( Q*p .- p'*Q*p)
end

function BNN_dynamics!(dp, p, Q, t)
    Û = max.(Q*p .- p'Q*p, 0.0)
    dp .= Û - sum(Û) .* p
end

## Modified RPS game
Q(a,b) = [0 -b a; a 0 -b; -b a 0]

## Initial mixed strategy
p0 = [0.3, 0.2, 0.5]

Comparing replicator and BNN dynamics on a negative definite game

This corresponds to the case when \(a > b\). In this case, we expect both dynamics to converge. The numerical solution is as expected.

replicator_trajectory = ODEProblem(replicator_dynamics!, p0, (0.0, 35), Q(2,1)) |> solve
BNN_trajectory        = ODEProblem(BNN_dynamics!,        p0, (0.0, 35), Q(2,1)) |> solve

plot(replicator_trajectory, title="Replicator Dynamics") |> display
plot(BNN_trajectory,        title="BNN Dynamics")        |> display

Comparing replicator and BNN dynamics on a negative semidefinite game

This corresponds to the case when \(a = b\). In this case, we expect replicator dynamics not to converge but BNN to converge.

The numerical solution is as expected: replicator dynamics oscillates around the equilibrium point but BNN dynamics converge. However, the convergence is slow, so we have to solve the ODE for a longer time. I also used a more accurate ODE solver because the default solver was showing some numerical artifacts.

replicator_trajectory = ODEProblem(replicator_dynamics!, p0, (0.0, 75), Q(1,1)) |> solve
BNN_trajectory        = ODEProblem(BNN_dynamics!,        p0, (0.0, 75), Q(1,1)) |> prob -> solve(prob, Vern9())

plot(replicator_trajectory, title="Replicator Dynamics") |> display
plot(BNN_trajectory,        title="BNN Dynamics")        |> display

Comparing replicator and BNN dynamics on a positive definite game

This corresponds to the case when \(a < b\). In this case, we don’t expect either replicator dynamics or BNN to converge. The numerical solution shows that both the dynamics oscillate, but the behavior of replicator dynamics is a bit unexpected.

replicator_trajectory = ODEProblem(replicator_dynamics!, p0, (0.0, 35), Q(1,2)) |> solve
BNN_trajectory        = ODEProblem(BNN_dynamics!,        p0, (0.0, 35), Q(1,2)) |> solve

plot(replicator_trajectory, title="Replicator Dynamics") |> display
plot(BNN_trajectory,        title="BNN Dynamics")        |> display

Note that in the replicator dynamics, the trajectory is oscillating very close to the boundary (because each complenent cyclically gets very close to 1, which corresponds to a corner of the simplex). We can observe this behavior more easily if we solve the ODE for a longer horizon.

replicator_trajectory = ODEProblem(replicator_dynamics!, p0, (0.0, 250), Q(1,2)) |> solve
plot(replicator_trajectory, title="Replicator Dynamics") |> display

Had we zoomed into the plot, say around time \(t=125\), it would appear that the solution has converged because all the components of the state are changing very slowing. But such a conclusion will be mistaken because the state switches after a while. This shows that it is dangerous to infer the convergence of a sequence by looking at the rate ofchange of that sequence!

Exercises

Exercise 6.1 Consider the following two-player symmetric game where \(x\) can be either \(0\), \(1\), or \(2\).

	$\mathsf{A}$		$\mathsf{B}$
$\mathsf{A}$	$1$	$1$	$2$	$x$
$\mathsf{B}$	$x$	$2$	$3$	$3$

1. For each possible value of \(x\), find all NE of the game and check if they are ESS or not.

2. The answer to the previous part suggests that the NE is not ESS when the NE uses a weakly dominated strategy. Prove the following: Suppose that in the game given below \((\mathsf{A}, \mathsf{A})\) is a NE and strategy \(\mathsf{A}\) is weakly dominated. Then \(\mathsf{A}\) is not an ESS.

	$\mathsf{A}$		$\mathsf{B}$
$\mathsf{A}$	$a$	$a$	$b$	$c$
$\mathsf{B}$	$c$	$b$	$d$	$d$

Exercise 6.2 The purpose of this exercise is to develop a method to check if a game is negative definite/semidefinte. This is not the most efficient method numerically, but is the simplest to understand.

Recall the definition of \(\reals^m_0\): \[ \reals^m_0 = \biggl\{ q \in Δ^m : \sum_{i=1}^m q_i = 0 \biggr\}. \] This is a linear subspace of dimension \(m-1\) because \(q_m = -(q_1 + \cdots + q_{m-1})\). A basis of this linear subspace is \[ T = \MATRIX{ I_{(m-1) × (m-1)} \\ -\ONES_{1 \times (m-1) } }_{m \times (m-1)} \] Then any vector \(q \in \reals^m_0\) must be of the form \(T x\), where \(x \in \reals^{m-1}\).

1. Based on the above, argue that a game with matrix \(Q\) is negative definite if and only if \(T^\TRANS Q T\) is a negative definite matrix (i.e., all the eigenvalues are real and negative).

2. Consider the symmetric game in Exercise 5.2, which is repeated below for convenience. Is this game negative definite? (You may use any numerical software to compute the eigenvalues of \(T^\TRANS Q T\), but you should report the eigenvalues in your solution).

	$\mathsf{L}$		$\mathsf{C}$		$\mathsf{R}$
$\mathsf{T}$	$0$	$0$	$5$	$4$	$4$	$5$
$\mathsf{M}$	$4$	$5$	$0$	$0$	$5$	$4$
$\mathsf{B}$	$5$	$4$	$4$	$5$	$0$	$0$

3. Run replicator dynamics and BNN dynamics on this game and describe the behavior (converges and if so to what value, does not converge and oscillates, etc.). Are the results consistent with what we expect from the theory?

Solution

We can verify that this game is negative definite. So, it has a unique Nash equilibrium that is an ESS. Therefore, we expect both replicator dynamics and BNN to converge. This is verified by the following simulation.

Qex = [0 5 4; 4 0 5; 5 4 0]

## Initial mixed strategy
p0 = [0.3, 0.2, 0.5]

replicator_trajectory = ODEProblem(replicator_dynamics!, p0, (0.0, 15), Qex) |> solve
BNN_trajectory        = ODEProblem(BNN_dynamics!,        p0, (0.0, 15), Qex) |> solve

plot(replicator_trajectory, title="Replicator Dynamics") |> display
plot(BNN_trajectory,        title="BNN Dynamics")        |> display

Exercise 6.3 Consider the following symmetric game

	$\mathsf{1}$		$\mathsf{2}$		$\mathsf{3}$
$\mathsf{1}$	$0$	$0$	$6$	$-3$	$-4$	$-1$
$\mathsf{2}$	$-3$	$6$	$0$	$0$	$5$	$3$
$\mathsf{3}$	$-1$	$-4$	$3$	$5$	$0$	$0$

1. Verify that the following are NE in symmetric strategies:

   • \((1, 0, 0)\)
   • \((\tfrac 13, \tfrac 13, \tfrac 13)\)
   • \((\tfrac 45, 0, \tfrac 15)\).

   Verify if each of these are ESS?

2. Is the game negative definite/negative semi-definite?

3. Run replicator dynamics and BNN dynamics starting from the following initial conditions.

   • \(p_0 = [0.5, 0.3, 0.2]\)
   • \(p_0 = [0.5, 0.2, 0.3]\)
   • \(p_0 = [0.3, 0.2, 0.5]\)
   • \(p_0 = [0.2, 0.5, 0.3]\)

   Do the dynamics converge to a NE?

4. In this part, we will check the local stability of the NE \((\tfrac 45, 0, \tfrac 15)\). Pick a small \(ε\), say \(ε = 10^{-6}\) and run replicator dynamics and BNN dynamics starting from the following initial conditions: (Make sure to solve the ODE for a sufficiently long time horizon)

   • \(p_0 = [0.8 - ε, 2ε, 0.2 - ε]\)
   • \(p_0 = [0.8 - ε, =, 0.2 + ε]\)
   • \(p_0 = [0.8 + ε, =, 0.2 - ε]\)

   Do the dynamics converge to a NE?

Solution

We show the output of the two evolutionary dynamics for different initial conditions.

Initial condition \(p_0 = [0.5, 0.3, 0.2]\)

Initial condition \(p_0 = [0.5, 0.2, 0.3]\)

Initial condition \(p_0 = [0.3, 0.2, 0.5]\)

Initial condition \(p_0 = [0.2, 0.5, 0.3]\)

Initial condition \(p_0 = [0.799999, 2.0e-6, 0.199999]\)

Initial condition \(p_0 = [0.799999, 0.0, 0.200001]\)

Initial condition \(p_0 = [0.8000010000000001, 0.0, 0.199999]\)

Hofbauer, J., Schuster, P., and Sigmund, K. 1979. A note on evolutionary stable strategies and game dynamics. Journal of Theoretical Biology 81, 3, 609–612. DOI: 10.1016/0022-5193(79)90058-4.

Maynard Smith, J. 1982. Evolution and the theory of games. Cambridge University Press. DOI: 10.1017/cbo9780511806292.

Maynard Smith, J. and Price, G.R. 1973. The logic of animal conflict. Nature 246, 5427, 15–18. DOI: 10.1038/246015a0.

Sandholm, W.H. 2010. Population games and evolutionary dynamics. MIT Press.