Computational Evolutionary Game Theory

Motivation: equilibrium without deliberation

Classical game theory asks what rational players would choose. Evolutionary game theory asks which strategies survive when simple organisms reproduce according to their payoffs, or when agents copy whoever did better.

DefinitionThe classical evolutionary setting

An infinite population.
Random pairwise interaction: two organisms drawn uniformly at random play a fixed 2-player symmetric game.
Payoffs are fitness, which changes reproductive success.
Replication: a child is an exact copy of its parent and plays its strategy.
Imitation: after an interaction, the lower-payoff agent may copy the higher-payoff agent’s strategy. This models fads, ideas and innovations spreading.

IntuitionThe central question

Evolutionary models explain how an equilibrium can emerge from simple local rules, but only in the limit of infinite populations and infinite time. Can we say how hard it is to find a stable strategy, how fast simple dynamics get close to equilibrium, and whether stability survives when interactions follow a network instead of random matching?

Two hallmarks of evolutionary models: infinite populations, and simple local update rules (replication, imitation) by which agents learn from their environment.

Direction	Question	Section
CS → EGT	How hard is it to find or recognize an ESS?	The complexity of ESS
EGT → CS	Do imitative dynamics compute a routing equilibrium, and how fast?	Imitative dynamics for selfish routing
hybrid	What is an ESS when organisms interact on a graph?	ESS on graphs

RemarkExistence vs emergence

routing-games shows nonatomic routing has equilibria (via the Beckmann potential). This chapter shows a population of imitating agents actually gets there.

Evolutionarily stable strategies

DefinitionFitness function

$A$ is the common action set and $\Delta(A)$ the mixed strategies. The game is a fitness function $F : \Delta(A)\times\Delta(A)\to\mathbb R$ , where $F(s\mid t)$ is the fitness of an $s$ -player meeting a $t$ -player. The same game is played in every interaction.

Setup. A fraction $1 - \epsilon$ of incumbents play $s$ , and a fraction $\epsilon$ of mutants play $t$ . Under random matching:

Organism	Meets incumbent w.p.	Meets mutant w.p.	Expected fitness
incumbent	$1-\epsilon$	$\epsilon$	$(1-\epsilon)F(s\mid s) + \epsilon F(s\mid t)$
mutant	$1-\epsilon$	$\epsilon$	$(1-\epsilon)F(t\mid s) + \epsilon F(t\mid t)$

DefinitionDefinition 29.1 — evolutionarily stable strategy (ESS)

$s$ is an ESS if for every $t\ne s$ there is an $\epsilon_t > 0$ such that for all $0 < \epsilon < \epsilon_t$ :

(1-\epsilon)F(s\mid s) + \epsilon F(s\mid t) > (1-\epsilon)F(t\mid s) + \epsilon F(t\mid t).

IntuitionNo small invasion can take over

If offspring are proportional to fitness, incumbents out-reproduce any sufficiently small mutant group, so the mutant fraction goes to 0. A continuous-time analysis of the replicator dynamics shows that every ESS is asymptotically stable.

TheoremTwo-condition characterization

Definition 29.1 holds iff for every $t\ne s$ , either

$F(s\mid s) > F(t\mid s)$ , or
$F(s\mid s) = F(t\mid s)$ and $F(s\mid t) > F(t\mid t)$ .

DerivationWhy these two cases

As $\epsilon\to0$ , the comparison is dominated by the $(1-\epsilon)$ terms, $F(s\mid s)$ vs $F(t\mid s)$ . If they differ, the strict inequality decides. If they tie, the $\epsilon$ terms, $F(s\mid t)$ vs $F(t\mid t)$ , decide.

TheoremTheorem 29.2 — ESS is a refinement of Nash

$s$ is an ESS iff

$(s,s)$ is a Nash equilibrium, i.e. $F(s\mid s)\ge F(t\mid s)$ for all $t$ ; and
every alternative best response $t\ne s$ to $s$ satisfies $F(s\mid t) > F(t\mid t)$ .

WarningESS may not exist

ESS is strictly more restrictive than symmetric Nash equilibrium, and not every symmetric 2-player game has an ESS.

Example: Hawks and Doves

ExampleThe game

Two organisms contest a resource worth $V$ . A fight costs the loser $C$ .

	Hawk	Dove
Hawk	$\frac{V-C}{2},\ \frac{V-C}{2}$	$V,\ 0$
Dove	$0,\ V$	$\frac V2,\ \frac V2$

Hawk takes the resource from Dove. Two Doves share it. Two Hawks fight, and each wins with probability $\tfrac12$ .

Dove is never an ESS. $(D,D)$ isn’t Nash: switching to $H$ raises the payoff from $V/2$ to $V$ .

Proof

V > C

: Hawk is an ESS

$F(H\mid H) = (V-C)/2$ . A mutant $t$ playing $H$ with probability $p < 1$ gets $F(t\mid H) = p\,\frac{V-C}{2} + (1-p)\cdot0 < \frac{V-C}{2},$ because $V - C > 0$ . So condition 1 holds for every $t\ne H$ .

∎

Derivation

V\le C

: mixed ESS

p^* = V/C

Against a population playing $H$ with probability $p$ :

Hawk earns $p\frac{V-C}{2} + (1-p)V$ ;
Dove earns $(1-p)\frac V2$ .

Setting them equal gives $\frac V2 = p\frac C2$ , i.e. $p^* = V/C$ . Verifying the second ESS condition is left as an exercise.

As $V\to C$ , $p^*\to1$ , matching the pure Hawk ESS.

IntuitionAggression is limited by the cost of fighting

When fights are cheap relative to the prize, everyone fights. When fights are costly, a stable mix emerges in which fights happen just often enough that being a Hawk and being a Dove pay the same.

The complexity of ESS

TheoremTheorems 29.8–29.9 — ESS is hard

Given a symmetric 2-player game $F$ :

deciding whether $F$ has an ESS is NP-hard and coNP-hard;
deciding whether a given $s$ is an ESS is coNP-hard.

The reduction is from “is the maximum clique of $G$ exactly $k$ ?”, which is both NP-hard and coNP-hard (in fact coD $^p$ -hard, Papadimitriou– Yannakakis).

DefinitionThe reduction $G\mapsto F$

For $G = (V,E)$ with $V = \{1..n\}$ , add a special strategy $0$ :

$F(i,j) = 1$ if $(i,j)\in E$ , else $0$ (for $i\ne j$ );
$F(i,i) = \tfrac12$ ;
$F(0,i) = F(i,0) = 1 - \frac{1}{2k}$ for all $0\le i\le n$ .

$F(s\mid t)$ is the payoff to $s$ against $t$ , and $F(i,j)$ a matrix entry.

IntuitionWhy cliques

An incumbent strategy scores well against itself if the two pure strategies it draws are usually adjacent. Mixing over a clique guarantees this. The diagonal value $\tfrac12$ makes cliques beat dense non-cliques. The constant row and column for strategy $0$ are calibrated to $k$ : strategy $0$ wins exactly when cliques are small.

LemmaLemma 29.3 — cliques maximize self-payoff (Motzkin–Straus)

If $s_0 = 0$ and $k'$ is the maximum clique size of $G$ , then $F(s\mid s)\le1 - \frac{1}{2k'},$ with equality iff $s$ is uniform on a $k'$ -clique.

ProofInduction on non-edges in the support

Base case: the support is a clique of size $k''\le k'$ .

F(s\mid s) = \sum_{i,j}s_is_j - \sum_i\frac{s_i^2}{2} = 1 - \frac{\lVert s\rVert_2^2}{2}\le1 - \frac{1}{2k''}\le1 - \frac{1}{2k'}.

Given $\lVert s\rVert_1 = 1$ , $\lVert s\rVert_2^2$ is minimized uniquely by the uniform distribution. Equality therefore requires uniform $s$ on a clique of size $k'$ . Conversely, uniform on a $k'$ -clique gives $\frac{1}{k'^2}\big(k'^2 - \frac{k'}{2}\big) = 1 - \frac{1}{2k'}$ .

Inductive step. Take non-adjacent $u, v$ in the support. Let $p = \sum_{(u,w)\in E}s_w$ and $q = \sum_{(v,w)\in E}s_w$ , WLOG $p\ge q$ . Move all of $v$ ‘s mass to $u$ : $s'_u = s_u + s_v$ , $s'_v = 0$ . Expanding the terms that involve $u$ and $v$ : $F(s'\mid s') = F(s\mid s) + 2s_v(p - q) + s_us_v > F(s\mid s).$ $s'$ has fewer non-edges in its support, so by induction $F(s'\mid s')\le1 - \frac1{2k'}$ . Hence $F(s\mid s)$ is strictly smaller.

The key step: merging mass across a non-edge always helps. So the maximum is attained only on cliques, and among cliques by the uniform distribution on the largest.

∎

Maximum clique $k'$	ESS of $F$	Lemma
$k' > k$	uniform on a maximum clique	29.4
$k' < k$	pure strategy $0$	29.5
$k' = k$	none	29.6 + 29.7

LemmaLemma 29.4 — big clique ⇒ clique ESS

If $C$ is a clique of size $k' > k$ (take a maximum one) and $s$ is uniform on $C$ , then $s$ is an ESS.

ProofBest responses live on

C

, and

s

beats them there

Step 1: Payoffs against $s$ . $F(s\mid s) = 1 - \frac1{2k'}$ (Lemma 29.3).

$F(0\mid s) = 1 - \frac1{2k} < F(s\mid s)$ , since $k' > k$ .
A vertex $u\notin C$ is adjacent to at most $k'-1$ vertices of $C$ , so $F(u\mid s)\le1 - \frac1{k'} < F(s\mid s)$ .
Each $i\in C$ gets $\frac1{k'}\big((k'-1) + \tfrac12\big) = 1 - \frac1{2k'}$ .

So every best response is supported on $C$ , and $s$ is a best response to itself.

Step 2: Beat alternative best responses. For $t\ne s$ supported on $C$ , Lemma 29.3 gives $F(t\mid t) < 1 - \frac1{2k'}$ (strict, since $t$ isn’t uniform). Meanwhile $F(s\mid t) = 1 - \frac1{2k'}$ , because each $i\in C$ earns $1 - \frac{1}{2k'}$ … against any $t$ on $C$ when averaged by the uniform $s$ : $F(s\mid t) = \frac1{k'}\sum_j t_j(k' - \tfrac12)$ . So $F(s\mid t) > F(t\mid t)$ .

∎

LemmaLemma 29.5 — small cliques ⇒ strategy $0$ is an ESS

If $k' < k$ , the pure strategy $0$ is an ESS.

ProofStrip off the weight on

0

and use Lemma 29.3

Write $c = 1 - \frac1{2k}$ .

Step 1: $0$ is a best response to itself. Column $0$ is constant, so $F(t\mid0) = c = F(0\mid0)$ for every $t$ . All strategies are best responses.

Step 2: Decompose $F(t\mid t)$ . Let $t^*$ be $t$ with its weight on $0$ removed and renormalized. Expanding by whether each draw is $0$ : $F(t\mid t) = c\,(2t_0 - t_0^2) + (1 - t_0)^2F(t^*\mid t^*).$

Step 3: Compare with $F(0\mid t) = c$ . For $t\ne0$ (so $t_0 < 1$ ), $F(0\mid t) > F(t\mid t)$ iff $c > F(t^*\mid t^*)$ . By Lemma 29.3, $F(t^*\mid t^*)\le1 - \frac1{2k'} < 1 - \frac1{2k} = c.$

∎

LemmaLemma 29.6 — cliques of size $\ge k$ break strategy $0$

If $k'\ge k$ , strategy $0$ is not an ESS.

ProofA clique mutant ties or beats

0

Every $t$ is a best response to $0$ . Take $t$ uniform on a maximum clique: $F(t\mid t) = 1 - \frac1{2k'}\ge1 - \frac1{2k} = F(0\mid t)$ . This violates the second condition of Theorem 29.2.

∎

LemmaLemma 29.7 — cliques of size $\le k$ break everything else

If $k'\le k$ , no strategy other than $0$ is an ESS.

NoteLeft as an exercise

The proof follows Lemmas 29.5–29.6.

ProofTheorems 29.8–29.9 from the lemmas

Existence (29.8). By Lemmas 29.4–29.7, $F$ has an ESS iff $k'\ne k$ . Deciding “max clique $= k$ ” is NP-hard and coNP-hard, so is deciding ESS existence.

Recognition (29.9). By Lemmas 29.5–29.6, strategy $0$ is an ESS iff $k' < k$ , which is coNP-hard to decide.

∎

ImportantWhat hardness means for evolution

If finding an ESS is NP-hard for a class of games, a finite population following simple dynamics is unlikely to reach one quickly. This doesn’t invalidate ESS-based models. It says to check tractability for the games a model uses. Hardness also doesn’t directly constrain infinite populations, which is the next section’s setting.

NoteRelated results (chapter notes)

Etessami–Lochbihler: finding an ESS is in $\Sigma_2^P$ ; finding a regular ESS is NP-complete; counting ESS is #P-hard; even approximating an ESS in $p$ -norm needs superpolynomial time unless P = NP.

Imitative dynamics for selfish routing

Setup. This is the single-commodity version of nonatomic routing from routing-games. One unit of flow goes from $s$ to $t$ , split among infinitely many infinitesimal agents.

Symbol	Meaning
$\mathcal P$	$s$ – $t$ paths
$x_p$	fraction of flow on path $p$
$x_e = \sum_{p\ni e}x_p$	edge load
$l_e$	latency: nonnegative, nondecreasing, Lipschitz
$l_p(x) = \sum_{e\in p}l_e(x_e)$	path latency
$\bar l(x) = \sum_p x_pl_p(x)$	average latency

DefinitionImitative dynamics

Each agent starts on some path. Continually, agents are paired at random and compare latencies. The one on the slower path switches to the faster one with probability proportional to the latency difference. This models a source measuring its packets’ delays and rerouting.

DefinitionDefinition 29.10 — Nash (Wardrop) flow

A feasible $x$ is a Nash flow iff for all $p,p'$ with $x_p > 0$ : $l_p(x)\le l_{p'}(x)$ . All used paths have minimal, and hence equal, latency. This is Definition 18.1 with one commodity.

NoteNash flows as ESS

With strictly increasing latencies, Nash flows are essentially ESS. This is stated without proof.

FormulaReplicator / imitation dynamics

x_p' = \underbrace{-x_p\!\!\sum_{q:\,l_q<l_p}\!\!x_q\lambda[l_p - l_q]}_{ \text{leaving }p} + \underbrace{\sum_{q:\,l_q>l_p}\!\!x_px_q\lambda[l_q - l_p]}_{\text{joining }p} = \lambda(x)\,x_p\big[\bar l(x) - l_p(x)\big]. \tag{29.1–29.2}

$\lambda(x)$ absorbs normalization and the pairing rate. For scale-invariance, set $\lambda(x) = \bar l(x)^{-1}$ (a relative rate of change).

DerivationFrom pairwise imitation to (29.2)

An agent on $p$ meets an agent on $q$ with probability $x_q$ , and switches with probability proportional to $l_p - l_q$ if $q$ is faster. The outflow from $p$ is $x_p\sum_{q\text{ faster}}x_q\lambda(l_p - l_q)$ , and the inflow is $\sum_{q\text{ slower}}x_qx_p\lambda(l_q - l_p)$ . Both are captured by the single sum $\sum_q x_px_q\lambda(l_q - l_p)$ , which equals $\lambda x_p(\bar l - l_p)$ using $\sum_q x_q = 1$ .

IntuitionBelow-average paths grow

A path’s share grows at a rate proportional to how much faster than average it is. The same equations also arise from replication, hence the name replicator dynamics.

Convergence to Nash flow

TheoremAsymptotic convergence (Fischer–Vöcking)

From any initial flow with support on all paths, the imitative dynamics converge to a Nash flow as $t\to\infty$ .

NoteProof via Lyapunov’s direct method (outline only)

Choose a potential $\Phi$ that vanishes at the stable point and decreases along trajectories. Lyapunov’s theorems then give convergence from a neighbourhood. Here $\Phi$ measures total latency, is minimized at Nash flows, and strictly decreases at any non-equilibrium flow, so the basin includes every fully supported initial flow. No local-minimum traps. The method gives no convergence time and no recipe for choosing $\Phi$ .

WarningFull support is essential

Imitation can only copy existing strategies. A path with zero flow can never be discovered, however fast it would be.

Time to an approximate equilibrium

WarningEuclidean distance is the wrong yardstick

Suppose an $\epsilon$ fraction uses a path $p$ just below average latency, and the equilibrium needs a large mass on $p$ . By (29.2), $x_p'$ is proportional to $x_p = \epsilon$ , so the flow moves toward $p$ arbitrarily slowly as $\epsilon\to0$ . Convergence in Euclidean distance can take arbitrarily long.

DefinitionDefinition 29.11 — $\epsilon$ -approximate equilibrium

Let $\mathcal P_\epsilon = \{p : l_p(x)\ge(1+\epsilon)\bar l\}$ and $x_\epsilon = \sum_{p\in\mathcal P_\epsilon}x_p$ . Then $x$ is an $\epsilon$ -approximate equilibrium iff $x_\epsilon\le\epsilon$ : at most an $\epsilon$ fraction of agents suffer latency more than a $(1+\epsilon)$ factor above average.

FormulaPotential

\Phi(x) = l^* + \sum_{e\in E}\int_0^{x_e}l_e(u)\,du, \qquad l^* = \min_x \bar l(x). \tag{29.3}

This is the Beckmann potential (18.3) plus the constant $l^*$ , added for the bound.

IntuitionReading the potential

$\int_0^{x_e}l_e$ is the total latency the agents on $e$ would see if inserted one at a time. Summing over edges gives the “arrival-order” latency of the whole flow.

TheoremTheorem 29.12 — convergence time

The imitative dynamics reach an $\epsilon$ -approximate equilibrium within time $O\!\left(\epsilon^{-3}\ln\frac{l_{\max}}{l^*}\right).$

ProofA differential inequality on

\Phi

Step 1: $\Phi$ decreases. By the chain rule and (29.2),

\Phi' = \sum_ex_e'l_e(x_e) = \sum_px_p'l_p = \lambda\sum_px_p(\bar l - l_p)l_p = \lambda\Big[\bar l^2 - \sum_px_pl_p^2\Big]\le0 \tag{29.4}

by Jensen’s inequality ( $\bar l^2 = (\mathbb E\,l_p)^2\le\mathbb E\,l_p^2$ ).

Step 2: Away from equilibrium, it decreases fast. If $x$ isn’t $\epsilon$ -approximate, at least an $\epsilon$ fraction has latency $\ge(1+\epsilon)\bar l$ . For fixed $\bar l$ , $\sum x_pl_p^2$ is smallest when exactly $\epsilon$ mass sits at $(1+\epsilon)\bar l$ and the rest at a common $l'$ . Mean-matching gives $l' = \bar l\,\frac{1 - \epsilon - \epsilon^2}{1 - \epsilon}.$ Substituting,

\bar l^2 - \epsilon(1+\epsilon)^2\bar l^2 - (1-\epsilon)l'^2 = -\frac{\epsilon^3}{1-\epsilon}\,\bar l^2,

so $\Phi'\le -\lambda\,\epsilon^3\bar l^2$ . With $\lambda = \bar l^{-1}$ : $\Phi'\le -c\,\epsilon^3\,\bar l, \tag{29.5}$ where the chapter uses $c = \tfrac12$ (my exact computation allows $c = 1$ ).

Step 3: Relate $\bar l$ to $\Phi$ . By monotonicity, $\bar l = \sum_ex_el_e(x_e)\ge\sum_e\int_0^{x_e}l_e$ (29.6). Also $\bar l\ge l^*$ . Adding the two gives $2\bar l\ge\Phi$ , so $\Phi'\le -\frac{\epsilon^3}{4}\,\Phi.$

Step 4: Integrate. $\Phi(t)\le\Phi(0)\,e^{-\epsilon^3t/4}$ while not at an $\epsilon$ -approximate equilibrium. But $\Phi\ge\Phi^*\ge l^*$ always, and $\Phi(0)\le2l_{\max}$ . So an $\epsilon$ -approximate equilibrium must be reached by

t = 4\epsilon^{-3}\ln\frac{\Phi(0)}{\Phi^*}\le4\epsilon^{-3}\ln \frac{2l_{\max}}{l^*}.

The key step: Jensen turns “an $\epsilon$ fraction is badly off” into a variance term of order $\epsilon^3\bar l^2$ . That forces the potential to decay geometrically until the bad fraction shrinks below $\epsilon$ .

∎

RemarkSame method as congestion control

This is the Lyapunov argument used for primal–dual congestion control in pricing-in-communication-networks, applied now to a population rather than to routers and hosts.

ESS on graphs

The change. Organisms interact only with their neighbours in an undirected graph, not with uniformly random partners. The complete graph recovers the classical model.

IntuitionWhat breaks without symmetry

In the classical model, every mutant set of size $\epsilon$ fares the same, and if one mutant dies, all do. On a network:

Group level: a mutant set with many internal edges may survive (e.g., if $F(t\mid t)$ is large) while a scattered one dies.
Individual level: mutants playing the same strategy can have different fates.

So defining ESS on graphs forces choices the classical model hid.

DefinitionFitness on a graph

$F(u) = \frac{1}{|\Gamma(u)|}\sum_{v\in\Gamma(u)}F(s_u\mid s_v),$ where $\Gamma(u)$ is $u$ ‘s neighbourhood. This is the average payoff against all neighbours, or equivalently the expected payoff against one random neighbour.

“Infinite population” becomes an infinite family of finite graphs $\mathcal G = \{G_n\}$ with $n$ vertices, studied as $n\to\infty$ .

DefinitionDefinition 29.13 — contracting mutant set

Let $|M_n|\ge\epsilon n$ , with mutants playing $t$ and everyone else $s$ . $M_n$ contracts if, for large $n$ , all but $o(n)$ mutants $j$ have an incumbent neighbour $i$ with $F(j) < F(i)$ .

NoteDefinitional choices

Requiring all mutants (rather than all but $o(n)$ ) to have a fitter incumbent neighbour, or requiring more than one fitter neighbour, gives stronger notions for which the results fail (exercise).

DefinitionDefinition 29.14 — $\epsilon'$ -linear mutant family

$\mathcal M = \{M_n\}$ is $\epsilon'$ -linear if some $\epsilon$ with $\epsilon' > \epsilon > 0$ has $\epsilon'n > |M_n| > \epsilon n$ for all large $n$ . Mutants form a small but non-vanishing fraction. This rules out “invasions” that survive only by being a vanishing fraction.

DefinitionDefinition 29.15 — ESS on a graph family

$s$ is an ESS with respect to $F$ and $\mathcal G$ if for every $t\ne s$ there is an $\epsilon_t > 0$ such that every $\epsilon_t$ -linear mutant family playing $t$ contracts for large $n$ .

To violate it, one needs arbitrarily small constant-fraction mutant sets, a linear-size subset of which survives all incumbent encounters. On complete graphs, the definition coincides with the classical one as $n\to\infty$ .

RemarkSmall sets can beat an ESS even classically

Even in the classical model, an $o(n)$ mutant set may be fitter than the incumbents (Vickery noted a constant number can be). ESS only protects against linear-size invasions.

Random graphs, adversarial mutants

TheoremTheorem 29.16 — classical ESS survive on dense random graphs

Let $s$ be a classical ESS of $F$ . Let $G_n\sim G_{n,p}$ (Erdős–Rényi) with $p = \Omega(1/n^c)$ , $0\le c < 1$ . Then with probability 1, $s$ is an ESS with respect to $F$ and $\mathcal G$ , against any adversarially chosen linear mutant family.

TheoremConverse

Taking $c = 0$ gives $p = 1$ , i.e. cliques $K_n$ . There, all incumbents share one fitness and all mutants another, converging to the classical expressions. So an ESS for this family must be a classical ESS.

ImportantRandomizing the graph = randomizing the matching

Classical ESS, and only those, are ESS on random graphs just above the connectivity threshold, for any game and any adversarial mutant placement. With $c = 1 - \gamma$ , graphs have about $n^{1+\gamma}$ edges, barely superlinear. With only linearly many edges, disconnection lets mutant sets survive in isolation. So this is essentially the minimum plausible density.

LemmaLemma 29.17 — most vertices have normal fitness

For almost every $G_{n,p}$ with $(1-\epsilon)n$ incumbents, and constants $0 < \epsilon < 1$ , $0 < \tau < 1/6$ , $0\le c < 1$ :

all but $\frac{24\log n}{\tau^2p}$ incumbents have fitness within $(1\pm\tau)[(1-\epsilon)F(s\mid s) + \epsilon F(s\mid t)]$ ;
all but $\frac{24\log n}{\tau^2p}$ mutants have fitness within $(1\pm\tau)[(1-\epsilon)F(t\mid s) + \epsilon F(t\mid t)]$ .

Since $p = \Omega(n^{-c})$ with $c < 1$ , these exceptions are $o(n)$ .

NoteStated without proof

The chapter omits the proof (a concentration argument).

TheoremTheorem 29.18 — few vertices miss a large set (Bollobás)

If $\delta pn\ge3\log n$ , $C\ge3\log(e/\delta)$ and $C\delta n\to\infty$ , then almost every $G_{n,p}$ has the following property. For every $U$ with $|U| = C/p$ , the set of vertices outside $U$ with no neighbour in $U$ has at most $\delta n$ elements.

ProofTheorem 29.16 (sketch)

Step 1: Set up. Since $s$ is a classical ESS, some $\epsilon_t$ makes incumbents strictly fitter than mutants in the random-matching sense for all $\epsilon < \epsilon_t$ . Fix an $\epsilon_t$ -linear mutant family with $|M_n| = \epsilon n$ . Let $I'$ be the incumbents of normal fitness. By Lemma 29.17, $|I'|\ge(1-\epsilon)n - \frac{24\log n}{\tau^2p}$ .

Step 2: Almost everyone touches a normal incumbent. Let $T_{I'}$ be the vertices outside $I'$ with no neighbour in $I'$ . $|I'|$ is random, so take a union bound over its $O(\log n/(\tau^2p))$ possible values: $\Pr(|T_{I'}|\ge\delta n)\le\sum_i\Pr(|T_{I'}|\ge\delta n,\ |I'| = i).$ Apply Theorem 29.18 with $\delta = n^{-\gamma}$ and $\gamma = (1-c)/2$ . Each term is $\exp(-\Omega(C\delta n))$ , so the sum is $o(1)$ . Hence at most $\delta n = o(n)$ vertices lack a normal-fitness incumbent neighbour.

Step 3: Normal mutants die. A normal-fitness mutant with a normal incumbent neighbour has fitness near the classical mutant value, and the neighbour has fitness near the classical incumbent value. The classical ESS inequality is strict, so for small $\tau$ the incumbent is fitter.

Step 4: Abnormal mutants are few. Lemma 29.17 again: only $o(n)$ mutants have abnormal fitness. Even if all of them survive, all but $o(n)$ mutants have a fitter incumbent neighbour, so $M_n$ contracts.

∎

NoteThe dual result (Kearns–Suri)

If instead the graph is adversarial (subject to density conditions) and the mutants are random, ESS are again preserved.

Future work

NoteFinite populations, bounded convergence

The major open problem: take $n$ agents following imitation or replication and bound the time to (a suitably redefined) equilibrium. That would turn existence and infinite-time convergence into concrete distributed algorithms with guarantees.

First target: the routing model with $n$ agents, with a strongly polynomial convergence bound.
Then: dynamics converging to welfare-maximizing equilibria.
Then: agents on graphs, with topology’s effect on convergence time as well as on equilibria.
If hardness intervenes (as Section 29.2 suggests for some games): approximate equilibria, bounding time spent far from equilibrium, and identifying tractable classes of games.

Quick reference

Object	Statement	Note
Classical model	infinite population, random pairing, symmetric fitness game	replication or imitation
ESS (Def 29.1)	incumbents out-earn every small mutant invasion
Two conditions	$F(s\mid s) > F(t\mid s)$ , or equality and $F(s\mid t) > F(t\mid t)$
Thm 29.2	ESS ⟺ $(s,s)$ Nash + beats alternative best responses	refinement of Nash; may not exist
Replicator stability	every ESS is asymptotically stable
Hawks and Doves	$V > C$ : Hawk; $V\le C$ : Hawk w.p. $V/C$	Dove never ESS
Reduction	adjacency matrix, diagonal $\tfrac12$ , strategy $0$ at $1 - \frac1{2k}$	from “max clique $= k$ “
Lemma 29.3	$F(s\mid s)\le1 - \frac1{2k'}$ ; equality iff uniform on a max clique	Motzkin–Straus
Lemmas 29.4–29.7	ESS iff $k'\ne k$ ; strategy $0$ is an ESS iff $k' < k$
Thm 29.8	ESS existence NP-hard and coNP-hard
Thm 29.9	ESS recognition coNP-hard
Routing dynamics (29.2)	$x_p' = \lambda x_p(\bar l - l_p)$ , $\lambda = 1/\bar l$	below-average paths grow
Nash flow (Def 29.10)	used paths have minimal latency	Wardrop
Lyapunov convergence	full-support flows → Nash flow	no rate
$\epsilon$ -approx (Def 29.11)	$\le\epsilon$ mass with latency $\ge(1+\epsilon)\bar l$	not Euclidean distance
Potential (29.3)	$l^* + \sum_e\int_0^{x_e}l_e$	Beckmann + $l^*$
Thm 29.12	$O(\epsilon^{-3}\ln(l_{\max}/l^*))$	Jensen + $2\bar l\ge\Phi$
Graph fitness	average payoff over neighbours
Contracts (Def 29.13)	all but $o(n)$ mutants have a fitter incumbent neighbour
$\epsilon'$ -linear (Def 29.14)	$\epsilon n < \lvert M_n\rvert < \epsilon'n$
Graph ESS (Def 29.15)	every small linear mutant family contracts	classical on cliques
Thm 29.16	classical ESS ⇒ ESS on $G_{n,p}$ , $p = \Omega(n^{-c})$ , $c < 1$	adversarial mutants
Converse	$c = 0$ (cliques) ⇒ must be classical
Lemma 29.17	abnormal fitness: $O(\log n/(\tau^2p)) = o(n)$ vertices
Thm 29.18	few vertices miss any set of size $C/p$	Bollobás

Facts to keep to hand

ESS is Nash plus a tie-breaker. Being a best response to yourself is Nash. Beating every alternative best response in the mutant–mutant matchup is the extra evolutionary condition. The tie-breaker is what makes ESS sometimes fail to exist, and what makes it hard.
Hardness via Motzkin–Straus. Self-play payoff is a quadratic form maximized uniformly on a maximum clique. Calibrating a constant outside strategy to $k$ turns “max clique $\ne k$ ” into “an ESS exists.”
Imitation computes equilibria. The replicator equation $x_p' \propto x_p(\bar l - l_p)$ is a distributed algorithm. The Beckmann potential is its Lyapunov function, and Jensen’s inequality turns ” $\epsilon$ fraction badly off” into geometric decay at rate $\epsilon^3$ .
Measure approximation by who suffers, not by distance. Small populations on good paths grow slowly under imitation, so Euclidean convergence can take forever. “At most $\epsilon$ mass is $\epsilon$ -worse than average” is reachable in bounded time.
Imitation can’t invent. Convergence needs full initial support. The same limitation appears whenever dynamics only copy existing strategies.
Random graphs just above connectivity are as good as random matching. For every game and every adversarial mutant set, the graph ESS on $G_{n,p}$ with $p = \Omega(n^{-c})$ , $c < 1$ , are exactly the classical ESS. Below that density, isolated mutant pockets can survive.
The same potential appears again. The Beckmann integral certifies existence and uniqueness (routing-games), bounds the price of anarchy, and here bounds the convergence time of imitation. Potential and Lyapunov functions are the shared tool of Part III’s dynamics (network-formation-games, selfish-load-balancing).

References

Nisan, Roughgarden, Tardos, Vazirani, Algorithmic Game Theory — chapter 29 (Suri)