Continuous, single-column reading. Equations, tables, proofs, references and appendices stay in document order.
Contents · 74 sections
Preface
Evolutionary game theory replaces the rational player of classical game theory by a population. Strategies are inherited or imitated, payoffs are rates of reproduction or adoption, and the questions change from “what should one do?” to “what persists?”. Alexander’s Element [3] is a compact map of the subject: the static theory of evolutionarily stable strategies and its set-valued refinements; the replicator equation and its relatives; finite populations; and models in which interaction is local. It is written for philosophers, and it is candid about where the models are fragile.
This volume retells that material with one question in mind: which of the constructions are natural, in the technical sense that they commute with the evident maps between games? The answers organize the subject more sharply than we expected.
The replicator equation is a functor from games and payoff-preserving maps to dynamical systems (). Invariance of faces, the lumping of duplicate strategies, and the action of symmetries are three instances of one statement.
Evolutionary stability of a point is not preserved by pulling back along a map that duplicates strategies; evolutionary stability of a set is (). The set-valued refinements that the source surveys are what the point-valued notion is forced to become.
The equilibria of a regular game carry indices that sum to one, the Euler characteristic of the simplex (); behind the number is a homotopy type, the Conley index, and behind recurrent behaviour a decomposition whose obstruction is a first cohomology class ().
A population is an open system, with payoffs as input and a state as output, and a game is a wiring of such systems (). The replicator is one box among several, and the source’s comparison of dynamics is a comparison of boxes.
Local interaction models are natural with respect to coverings of the interaction graph and equivariant under its symmetries (), which accounts for the rotating patterns the source exhibits.
Quantitative statements accompany the qualitative ones throughout: rates of extinction, escape times, eigenvalues, fixation probabilities, thresholds. All of them are recomputed by the companion script.
How much of this is “higher” is assessed in . The short answer: most of it is ordinary category theory; homotopy enters through the index and the Conley index; cohomology enters in degree one; and the compositional structure of is two-dimensional. Nothing here is a new theorem of evolutionary game theory. A companion paper applies the framework to machine learning.
The volume belongs to a series with [22], on classical game theory, [18], on information theory, and [16], on differential topology, and uses each of them once.
Statics
Games, Populations, and the Simplex
Two readings of one object
A point of the simplex Δ(S) over a finite set S of strategies can be read in two ways. It is a mixed strategy: one player randomizing over S. It is also a population state: a large population in which the fraction xs of individuals plays the pure strategy s. The source moves between the readings freely and remarks that the equivalence of two definitions of evolutionary stability rests on their agreement [source, §2.1]. The agreement is a fact about maps, and it is the starting point of this volume.
Let FinStoch be the category of finite sets and stochastic matrices, and let Δ be the finite distribution monad on Set: Δ(S) is the set of probability vectors on S, a function f:S→T induces the pushforward f∗:Δ(S)→Δ(T), (f∗x)t=∑f(s)=txs, and the algebras of Δ are the convex spaces. The real line is a convex space, so:
Proposition 1.1 (Mixed extension). [classical; ]Every function u:S×S→R extends uniquely to a map Δ(S)×Δ(S)→R that is affine in each variable separately. In coordinates, with A=(u(s,s′)), the extension is (x,y)↦xTAy.
Definition 1.2. A symmetric game is a pair (S,A) of a finite set S and a matrix A∈RS×S; the entry Ass′ is the payoff to a player using s against a player using s′. For x,y∈Δ(S) write π(x∣y)=xTAy for the payoff of x against y, and f(y)=Ay for the vector of payoffs of the pure strategies against y.
Biaffinity is what identifies the two readings: the expected payoff against an opponent drawn at random from a population in state y is the payoff against the mixed strategy y, because both are the affine extension of the same function. Whenever the source appeals to “no difference from a mathematical point of view”, it is appealing to .
Maps of games
Definition 1.3. A payoff-preserving mapf:(S,A)→(T,B) is a function f:S→T with Bf(s)f(s′)=Ass′ for all s,s′∈S. Symmetric games and payoff-preserving maps form a category Game.
Three kinds of map generate everything.
An injective f exhibits (S,A) as the subgame of (T,B) on the strategies in its image.
A surjective f exhibits (S,A) as (T,B) with some strategies duplicated: s and s′ with f(s)=f(s′) have equal rows and equal columns in A.
An automorphism of (S,A) is a relabelling of strategies that preserves every payoff.
Proposition 1.4. [observation]For a payoff-preserving f:(S,A)→(T,B) and x,y∈Δ(S), π(f∗x∣f∗y)B=π(x∣y)A,(Bf∗y)f(s)=(Ay)s for every s∈S.
Proof.(Bf∗y)f(s)=∑tBf(s)t∑f(s′)=tys′=∑s′Bf(s)f(s′)ys′=∑s′Ass′ys′. The first identity follows by pairing with x. ◻
So Δ lifts to a functor from Game to convex spaces with a biaffine form, and every construction of this volume can be asked whether it respects that functor.
Example 1.5 (Rock–Paper–Scissors and its relatives). Let S=Z/n with n odd, and let Aij=1 if i−j∈{1,…,2n−1}, −1 if j−i∈{1,…,2n−1} and 0 if i=j. For n=3 this is Rock–Paper–Scissors and for n=5 its five-strategy extension with which the source opens [source, §1.1]. Translation i↦i+1 is a symmetry, so Z/n acts on the game. The subgame of the five-strategy game on {0,1,3} is a copy of Rock–Paper–Scissors, an inclusion in Game; the subgame on {0,1,2} is not, since there 2 beats both others.
A second kind of map acts on payoffs and not on strategies.
Definition 1.6. A column shift replaces A by A+1cT for a vector c∈RS: a constant cs′ is added to every payoff against s′. A rescaling replaces A by λA with λ>0.
A column shift changes π(x∣y) by cTy, which does not depend on x; it changes no comparison between strategies. Every game is a column shift of a unique game with zero diagonal, and the source’s normalization to positive payoffs [source, §4.1] is a column shift by a constant vector.
Equilibria
Definition 1.7. A state x∈Δ(S) is a (symmetric) Nash equilibrium of (S,A) if π(x∣x)≥π(y∣x) for all y∈Δ(S); equivalently, if (Ax)s≤xTAx for all s, with equality for s∈suppx. It is strict if π(x∣x)>π(y∣x) for all y=x, and quasi-strict if (Ax)s<xTAx for all s∈/suppx.
Theorem 1.8. [classical; Nash 1951] Every symmetric game has a symmetric Nash equilibrium. If a finite group G acts on (S,A) by symmetries, the set of Nash equilibria is G-invariant and contains a G-fixed point.
Corollary 1.9. If a group of symmetries acts transitively on S, the uniform state is a Nash equilibrium. In particular the uniform state is an equilibrium of every game of .
How equilibria behave under the maps of is recorded once and used repeatedly.
Proposition 1.10. [observation]Let f:(S,A)→(T,B) be payoff-preserving.
If f is surjective, then x is a Nash equilibrium of (S,A) if and only if f∗x is a Nash equilibrium of (T,B).
If f is injective, then f∗x Nash in (T,B) implies x Nash in (S,A); the converse holds if and only if no strategy outside the image of f earns more than π(x∣x) against f∗x.
Proof. By the pure payoffs against f∗x at strategies in the image of f are the pure payoffs against x, and the mean payoffs agree. The equilibrium condition on T is the equilibrium condition on S together with a condition at strategies outside the image, which is vacuous when f is surjective. ◻
The asymmetry between (a) and (b) recurs at every level of the theory: clone maps are invisible to selection, inclusions are visible exactly through the strategies they omit.
Notes
The distribution monad and convex spaces as its algebras go back to Stone and to Świrszcz; a modern account is in [19]. is from Nash’s paper on non-cooperative games [39]. The category Game is not standard. Categories of games with strategy-changing morphisms appear in the literature on potential games and on open games [21]; those morphisms are richer and are not needed here. The classical theory with rational players is the subject of [22]. The invariance of evolutionary dynamics under column shifts is used systematically in [61, 29].
Exercises
Exercise 1.1. Let yϵ=(1−ϵ)x+ϵμ. Show that π(x∣yϵ)−π(yϵ∣yϵ)=ϵ(π(x∣yϵ)−π(μ∣yϵ)).
Exercise 1.2. Determine the group of symmetries of Rock–Paper–Scissors and of the five-strategy game of .
Exercise 1.3. For the Hawk–Dove game with , find the zero-diagonal normal form under column shifts and read off the equilibria for V<C and for V>C.
Exercise 1.4. Let (S,A) be the Hawk–Dove game with the strategy Dove duplicated. Describe all its Nash equilibria for V<C.
Evolutionary Stability
The invasion form
A Nash equilibrium asks that no deviation does better against the incumbent. In a population that is too weak: a deviation that does equally well against the incumbent is not selected against, and may spread if it does better against itself. The source’s first example [source, §2.1] is the game , in which the second strategy is an equilibrium that the first invades by drift. All of the static theory can be phrased with one function.
Definition 2.1. The invasion form of a state x is the function on Δ(S)Qx(y)=π(x∣y)−π(y∣y), the advantage of x over y in a population in state y.
Definition 2.2. [classical; Maynard Smith and Price 1973; [source, Defs. 1–4]] A state x is
an evolutionarily stable strategy (ESS) if for every μ=x either π(x∣x)>π(μ∣x), or π(x∣x)=π(μ∣x) and π(x∣μ)>π(μ∣μ);
locally superior if Qx(y)>0 for all y=x in a neighbourhood of x;
protected by a uniform invasion barrier if there is ϵˉ>0 such that π(x∣yϵ)>π(μ∣yϵ) for all μ=x and 0<ϵ<ϵˉ, where yϵ=(1−ϵ)x+ϵμ.
Theorem 2.3. [classical; Hofbauer, Schuster and Sigmund 1979; [59]] The three conditions are equivalent.
The source presents the equivalence as evidence that the definition is not arbitrary. In the present language two thirds of it is one line: by , Qx(yϵ)=ϵ(π(x∣yϵ)−π(μ∣yϵ)), so the barrier inequality along the ray from x towards μis local superiority along that ray. What remains is uniformity in μ, which is compactness of the simplex, and the passage from (i) to a neighbourhood, which uses that ϵ↦π(x∣yϵ)−π(μ∣yϵ) is affine with value π(x∣x)−π(μ∣x)≥0 at 0 and slope governed by the second clause of (i).
Example 2.4 (Hawk–Dove). With A as in and V<C, let x=(p,1−p) with p=V/C and y=(q,1−q). The payoff advantage of Hawk over Dove against y is (V−qC)/2, so Qx(y)=(p−q)2V−qC=2C(p−q)2. The mixed state is globally, and not only locally, superior. [S1]
Example 2.5 (Drift). For and x the second pure strategy, Qx(y)=1−(1+q2)=−q2<0 when y plays the first strategy with probability q>0. The equilibrium is not merely not superior; it is inferior to every nearby state. [S4]
Properties
The source collects five facts [source, Thms. 1–5]. Each is a statement about Q.
Theorem 2.6. [classical; Bishop and Cannings 1976; Haigh 1975]
A game need not have an ESS: Rock–Paper–Scissors has none. [S2]
A weakly dominated strategy is not an ESS. [S3]
If x is an ESS and y=x is a Nash equilibrium, then suppy⊆suppx.
A game with n strategies has at most (⌊n/2⌋n) ESS.
An ESS in the interior of the simplex is the only ESS, and it is globally superior.
A quasi-strict equilibrium x is an ESS if and only if zTAz<0 for all z=0 with suppz⊆suppx and ∑szs=0.
Proof. (a) By the uniform state u is an equilibrium, and it is the only one. For a pure strategy e, π(u∣e)=0=π(e∣e) and π(e∣u)=0=π(u∣u), so both clauses of (i) fail. (b) If μ weakly dominates x then π(μ∣x)≥π(x∣x) and π(μ∣μ)≥π(x∣μ), so Qx(μ)≤0 with μ an alternative best reply. (c) If suppy⊆suppx then y is a best reply to x, since every pure strategy in the support of x is. The second clause of (i) gives π(x∣y)>π(y∣y), contradicting that y is an equilibrium. (d) By (c) the supports of distinct ESS form an antichain of subsets of S; apply Sperner’s theorem. (e) If x is interior, every y is a best reply to x, so Qx(y)>0 for all y=x; then no other state is an equilibrium by (c). (f) For y near x write y−x=z+w with z supported in suppx; quasi-strictness makes the first-order term in w strictly positive, and for w=0, Qx(y)=−zTAz because zTAx=0. ◻
Criterion (f) is the one used by the companion script to decide evolutionary stability exactly.
Sets, and why they are forced
A population may be stable as a whole while drifting inside a set of equivalent states. The source surveys Thomas’s evolutionarily stable sets and three variants due to Balkenborg and Schlag [source, §2.3]. We use the following form.
Definition 2.7. [classical; Thomas 1985; [59]] A non-empty closed set L⊆Δ(S) is an evolutionarily stable set if every x∈L has a neighbourhood U with Qx(y)≥0 for all y∈U, and Qx(y)>0 for y∈U∖L.
A one-point set {x} is an evolutionarily stable set exactly when x is an ESS, and every point of an evolutionarily stable set is a Nash equilibrium.
Theorem 2.8 (Stability is a property of sets). [observation]Let f:(S,A)→(T,B) be a payoff-preserving surjection and let L⊆Δ(T) be an evolutionarily stable set. Then f∗−1(L) is an evolutionarily stable set of (S,A). If f is not injective and x is an ESS of (T,B) whose support meets the set of duplicated strategies, then no point of f∗−1(x) is an ESS.
Proof. By , Qσ(μ)=Qf∗σ(f∗μ) for all σ,μ∈Δ(S). Let σ∈f∗−1(L) and let U be the neighbourhood of f∗σ from . Then f∗−1(U) is a neighbourhood of σ on which Qσ≥0, with strict inequality off f∗−1(L); and f∗−1(L) is closed and non-empty. For the second statement, the fibre over x contains a segment through each of its points, on which Qσ vanishes identically. ◻
Example 2.9. Duplicate Dove in the Hawk–Dove game. The fibre over the ESS is the segment L={(p,s,1−p−s)}, and Qσ(μ)=2C(p−μH)2 for σ∈L: zero exactly on L, positive elsewhere. [S6]
explains a development that the source records historically. Duplicating a strategy changes nothing about the biology or the sociology of a model; it is a change of description. A solution concept that is destroyed by it cannot be the right concept, and the least repair is to pass from points to sets. The three variants of Balkenborg and Schlag differ in the order of quantifiers over the neighbourhood (one threshold for each invader, for each incumbent, or for all) and so in how they behave when L is not compact in the relevant topology; for the closed sets of we do not need the distinction.
Relative entropy
The invasion form has a second life. For x,y∈Δ(S) with suppx⊆suppy let D(x∥y)=s∑xslogysxs be the relative entropy. It is the quantity singled out in [18], following Baez and Fritz, as the unique functorial measure of information lost by a stochastic map. In we shall see that along the replicator dynamics dtdD(x∥y(t))=−Qx(y(t)), so that local superiority of x says precisely that relative entropy to x decreases strictly along nearby trajectories. Evolutionary stability is the statement that a population near xgains information aboutx.
Notes
The definition of an ESS is from [36]; the equivalences of are in [30] and [59, Ch. 2]. Parts (c)–(e) of are due to Bishop and Cannings [8], part (f) to Haigh [24]; the sharp maximal number of ESS for given n is a harder problem than the Sperner bound suggests. Evolutionarily stable sets were introduced by Thomas [58] and refined in [7]. The observation that they are the closure of the point concept under duplication of strategies is, as far as we know, not stated in this form in the literature, though it is implicit in the treatment of “clones” in the literature on stability of sets. The characterization of relative entropy is in [5].
Exercises
Exercise 2.1. Show that a strict Nash equilibrium is an ESS, and that in a two-strategy game with A11=A21 and A22=A12 every ESS is either strict or interior.
Exercise 2.2. For the generalized Rock–Paper–Scissors game with payoff a>0 for a win and −b<0 for a loss, show that the uniform state is an ESS if and only if a>b.
Exercise 2.3. Exhibit a game with three strategies and three ESS, attaining the bound of (d).
Exercise 2.4. In the game of the source’s discussion of weak dominance, compute Qx for each pure strategy x and decide which is an ESS.
Dynamics
The Replicator Equation
Derivation as a quotient
Let ns(t)>0 be the number of individuals using strategy s, and suppose each type grows at a per-capita rate equal to its payoff against the current population: n˙s=nsfs(x) with x=n/∣n∣, ∣n∣=∑sns, f(x)=Ax. Differentiating xs=ns/∣n∣ gives the replicator equation [56] x˙s=xs((Ax)s−xTAx),s∈S.
Proposition 1.1. [reformulation; cf. [29]] The growth system on the open cone R>0S is invariant under the scaling action of R>0 up to a change of speed along orbits, and (2) is the vector field it induces on the quotient R>0S/R>0≅intΔ(S). The field extends smoothly to the closed simplex.
The source derives (2) twice, from births and deaths and from imitation [source, §3.2.1–3.2.2]. The first is ; the second is . We write Rep(S,A) for the dynamical system on Δ(S) defined by (2), and Dyn for the category whose objects are compact spaces with a continuous flow and whose morphisms are continuous maps commuting with the flows.
Naturality
Theorem 1.2 (The replicator equation is a functor). [observation]If f:(S,A)→(T,B) is payoff-preserving, then f∗:Δ(S)→Δ(T) maps solutions of Rep(S,A) to solutions of Rep(T,B). Hence Rep:Game→Dyn is a functor.
Proof. Let x(t) solve (2) for A and put y=f∗x. By , (Ax)s=(By)f(s) and xTAx=yTBy. Therefore y˙t=f(s)=t∑xs((Ax)s−xTAx)=(f(s)=t∑xs)((By)t−yTBy)=yt((By)t−yTBy) for t in the image of f, and yt=0 identically otherwise, which also solves the equation. ◻
Three familiar facts are the three generating cases of . [R1]
Corollary 1.3.
Faces are invariant. For every S′⊆S the face Δ(S′) is invariant, and the flow on it is the replicator flow of the subgame. In particular strategies absent initially stay absent.
Clones lump. If strategies are duplicated, the total frequency of each class of duplicates follows the replicator equation of the game without duplicates.
Symmetries act. The group of symmetries of (S,A) acts on Δ(S) by automorphisms of the flow; the fixed-point set of every subgroup is invariant.
On the side of payoffs, (2) depends only on differences (Ax)s−(Ax)s′, so:
Proposition 1.4. [classical; ]A column shift does not change the replicator field, and a rescaling A↦λA multiplies it by λ. The functor Rep factors through games modulo column shifts.
Two strategies
By a two-strategy game may be taken to be . With x the frequency of the first strategy, (2) reads x˙=x(1−x)(a−(a+b)x).
signs of (a,b)
in the source
rest points
behaviour
a>0>b or b>0>a
Prisoner’s Dilemma
0,1
one strategy wins
a,b>0
Hawk–Dove
0,1,a+ba
interior attracts
a,b<0
coordination
0,1,a+ba
interior repels
a=b=0
“game of life”
every point
nothing moves
The drift game of is the boundary case a=0>b: there x˙=x2(1−x) for the invading strategy, and the invader’s frequency passes from x0 to x1 in time x01−x11+logx0(1−x1)x1(1−x0). An invader that is merely not selected against escapes in time of order 1/x0; one that is selected for escapes in time of order log(1/x0). From x0=0.05 to 21 the drift game takes time 20.94. [S4]
Geometry: gradients and entropy
The Shahshahani metric on the open simplex is gx(u,v)=∑susvs/xs for tangent vectors u,v (vectors with ∑sus=0). It is the Fisher information metric of statistics.
Theorem 1.5. [classical; Shahshahani 1979; Kimura 1958] If A is symmetric, (2) is the gradient flow of 21xTAx for the Shahshahani metric, and mean payoff increases at the rate dtdxTAx=2Varx(Ax)=2s∑xs((Ax)s−xTAx)2.
This is Fisher’s fundamental theorem in the form relevant to games in which the two players’ interests coincide. [R2]
Theorem 1.6. [classical; [30, 61]] Along any solution y(t) of (2) in the interior of a face containing suppx, dtdD(x∥y(t))=−Qx(y(t)).
Corollary 1.7. [source, Thm. 6.3] An ESS is asymptotically stable; an interior ESS attracts the whole interior of the simplex. More precisely, if Qx>0 on U∖{x}, every sublevel set {y:D(x∥y)≤c} contained in U lies in the basin of attraction of x. For Hawk–Dove, dtdD(x∥y)=−2C(p−q)2. [R3]
The folk theorem and elimination
Theorem 1.8. [classical; [29]; [source, Thm. 6]] (1) Every Nash equilibrium is a rest point of (2). (2) Every Lyapunov stable rest point is a Nash equilibrium. (3) Every ESS is asymptotically stable. No converse holds.
For (1) see [R7]. A pure state is always a rest point by (a) and need not be an equilibrium. For the failure of the converse of (3) the source gives the game : its only equilibrium is the uniform state, which is asymptotically stable and is not an ESS, since criterion (f) of fails. [R8]
Theorem 1.9 (Elimination, with a rate). [classical; Akin 1980; [source, Thm. 7]] Suppose the pure strategy s is strictly dominated by μ∈Δ(S) with margin δ>0: π(μ∣z)−(Az)s≥δ for all z. Then along every interior solution xs(t)≤∏rxr(0)μrxs(0)e−δt.
Proof.dtd(logxs−∑rμrlogxr)=(Ax)s−π(μ∣x)≤−δ, and ∏rxrμr≤1. ◻
When s is a twin of another strategy s′ with every payoff lowered by δ, the proof gives an identity: log(xs/xs′) decreases at the constant rate δ. [R9] The hypothesis that the solution be interior is the source’s proviso that all strategies be initially present, and by (a) it cannot be dropped.
Cycles
Theorem 1.10. [classical; [29]] Let A be antisymmetric with an interior equilibrium x∗. Then D(x∗∥y) is constant along every interior solution of (2). No interior solution converges to x∗ or to the boundary.
Proof.yTAy=0 and x∗TAy=−yTAx∗=0, so Qx∗≡0; apply . ◻
For Rock–Paper–Scissors this gives the family of closed orbits around the centre. [R4]
Proposition 1.11 (Generalized Rock–Paper–Scissors). [classical; [61]] Let a win pay a>0 and a loss −b<0. The linearization of (2) at the uniform state has eigenvalues λ±=6b−a±i63(a+b). The centre is asymptotically stable and an ESS for a>b, a centre for a=b, and a repeller for a<b, when interior orbits approach the boundary. [R5, R6]
The cases a>b and a<b are the source’s “good” and “bad” versions. By (c) the uniform state is a rest point for every a,b, being the fixed point of the Z/3 of symmetries. For three strategies the possible phase portraits were classified by Zeeman and by Bomze [61, 10]; they are assembled from rest points and cycles. With four strategies the state space is three-dimensional and chaotic attractors occur [4]; the source illustrates one [source, §3.2.5]. Two statements survive chaos.
Theorem 1.12. [classical; [29]] If a solution of (2) stays at a positive distance from the boundary, then every limit point of its time averages T1∫0Tx(t)dt is an interior equilibrium. If the interior equilibrium is unique, the time averages converge to it.
The second surviving statement is the index theorem of the next chapter.
Notes
The replicator equation was introduced in [56] and named in [50]. The standard reference is [29]; [47] treats it within a general theory of population dynamics. is in [52, 1]. The functorial statement is elementary and its three cases are classical; we have not found it stated as a single naturality property. Relative entropy as a Lyapunov function, and the reading of the replicator equation as an information-geometric flow, are developed in [6, 25]. The equivalence of the replicator equation on n strategies with a Lotka–Volterra system in n−1 variables is due to Hofbauer [27].
Exercises
Exercise 1.1. Derive (3) and the escape-time formula for the drift game.
Exercise 1.2. Prove the formula for dtdxTAx in , and show that for general A the rate is 2Covx(Sx,Ax), where S=21(A+AT).
Exercise 1.3. Verify by computing the trace and determinant of the linearization on the tangent space.
Exercise 1.4. A population plays Rock–Paper–Scissors with Rock present in two indistinguishable variants, in initial state (41,41,41,41). Describe the motion of the class frequencies.
Index, Recurrence, and Decomposition
Three questions cannot be answered one equilibrium at a time. How many equilibria can there be, and of what kinds? What replaces an equilibrium when the dynamics cycles? Which part of a game is responsible for the cycling? Each has an answer in which topology does the work.
The index theorem
Write FA for the replicator field. At a rest point x its derivative preserves the tangent space T={v:∑svs=0} of the simplex.
Definition 2.1. A game is regular if every Nash equilibrium is quasi-strict and DxFA∣T is invertible at each. The index of a Nash equilibrium x of a regular game is ind(x)=signdet(−DxFA∣T)∈{+1,−1}.
Regular games are open and dense among all games. An equilibrium at which every eigenvalue of DxFA∣T has negative real part has index +1.
Theorem 2.2 (Index theorem). [classical; Hofbauer and Sigmund; Poincaré–Hopf] For a regular game, xNash∑ind(x)=1.
Sketch. For small ϵ>0 the field FA(x)+ϵ(u−x), with u the uniform state, points strictly inward on the boundary of the simplex. Its rest points converge, as ϵ→0, to the rest points of FA that are saturated, that is, to the Nash equilibria: a rest point with a strategy outside its support that earns more than average is pushed out of the simplex and disappears. Regularity makes the correspondence a bijection that preserves the sign of the determinant. The negative of an inward-pointing field points outward, and by the Poincaré–Hopf theorem the sum of the indices of its zeros is the Euler characteristic of the simplex, which is 1 because the simplex is contractible; see [16, Ch. 7] for the three descriptions of the Euler characteristic used here. ◻
The theorem is checked on four hundred random games with three and four strategies. [I1]
Corollary 2.3. In a regular game: (a) the number of Nash equilibria is odd; (b) every ESS has index +1[I2]; (c) if there are k equilibria of index +1 there are exactly k−1 of index −1; in particular two ESS force a third equilibrium, which is not stable. [I3]
In the coordination game the two conventions have index +1 and the mixed equilibrium, which separates their basins, has index −1. The index theorem is the reason a model with two stable conventions always has a threshold between them. It holds whatever the dynamics does elsewhere, cycles and chaos included.
Recurrence and the Conley index
When trajectories do not converge, the object that plays the part of an equilibrium is a recurrent set.
Definition 2.4. For a flow φ on a compact metric space, an (ϵ,τ)-chain from x to y is a sequence x=x0,…,xk=y with times ti≥τ such that d(φti(xi),xi+1)<ϵ. A point is chain recurrent if for all ϵ,τ there is a chain from it to itself; two chain recurrent points are equivalent if chains run both ways. The classes are the chain components.
Theorem 2.5 (Conley’s decomposition). [classical; Conley 1978] Every flow on a compact metric space has a continuous function that is strictly decreasing along orbits off the chain recurrent set and constant on each chain component. The flow is gradient-like between chain components.
Chain components generalize equilibria in exactly the way the source’s examples require.
Example 2.6. For the Prisoner’s Dilemma the chain components are the two pure states, and All-Defect is the only one that attracts. For a coordination game there are three. For Rock–Paper–Scissors with a=b every state is chain recurrent and the whole simplex is a single chain component: arbitrarily small errors carry the population from any closed orbit to any other, and to the boundary. For a<b the chain components are the centre and the boundary cycle, and the boundary cycle attracts.
Papadimitriou and Piliouras propose the chain components of a learning dynamic, and the sink components among them, as what a game “means” when equilibria do not predict behaviour [44].
To each isolated invariant set Conley attaches more than a number.
Definition 2.7. An index pair for an isolated invariant set K is a pair of compact sets L⊆N such that K is the largest invariant set in N∖L, L is positively invariant in N, and orbits leave N only through L. The Conley index of K is the pointed homotopy type h(K)=[N/L].
Theorem 2.8. [classical; Conley 1978; [46]] The Conley index does not depend on the index pair. It is invariant under continuation: if a family of flows has a common isolating neighbourhood, the index is constant along the family. A hyperbolic rest point with k unstable directions has index the pointed sphere Sk; an attracting closed orbit has the index of a circle with a disjoint base point, whose reduced homology has rank one in degrees 0 and 1. If h(K) is not the homotopy type of a point, K is non-empty.
Remark 2.9 (What is higher here). The index of is the Euler characteristic of the Conley index: an equilibrium with k unstable directions contributes (−1)k. The Conley index remembers k, and for recurrent sets it remembers a homotopy type that no count recovers. Continuation invariance is the precise sense in which a qualitative conclusion drawn from a model survives perturbation of its payoffs: as long as an attractor stays isolated, its index, and hence its existence, persists. An ESS has index S0 and persists under small changes of the game; the family of cycles of Rock–Paper–Scissors at a=b is not isolated and does not.
For computation one discretizes. The invasion graph of a game has the pure strategies as vertices and an edge i→j when Aji>Aii, that is, when j invades a population of i. Its sink strongly connected components are a finite shadow of the attracting chain components. [I7] The Markov–Conley chains of α-Rank [43] are random walks on such graphs, weighted by fixation probabilities; we return to them in .
Decomposition
Every matrix splits as A=S+K with S=21(A+AT) symmetric and K=21(A−AT) antisymmetric: a game of common interest plus a zero-sum game. By the replicator field is the sum of a gradient field and a field that, when K has an interior equilibrium, conserves a relative entropy. Mean payoff obeys dtdxTAx=2Covx(Sx,Ax). [I6]
The antisymmetric part decomposes further, and here the statement is cohomological. Regard an antisymmetric matrix K as a 1-cochain on the complete graph with vertex set S: Kij is the advantage of i over j.
Theorem 2.10 (Hodge decomposition of a zero-sum game). [literature; [31, 13]] Every antisymmetric K decomposes uniquely as Kij=(ri−rj)+Cij,ri=n1∑jKij,∑jCij=0 for all i. The two parts are orthogonal for the Frobenius inner product. The gradient part satisfies the cocycle condition Gij+Gjk+Gki=0 on every triangle, and conversely every antisymmetric matrix satisfying it is a gradient. The cyclic part C has the same curl Kij+Kjk+Kki as K on every triangle.
The converse statement is the vanishing of the first cohomology of the full simplex on S: a closed cochain is exact. [I4, I5] We call τ(K)=∥G∥2/∥K∥2∈[0,1] the transitivity index. Rock–Paper–Scissors has τ=0 and curl ±3; a game of pure rating differences has τ=1; a random antisymmetric game on five strategies had τ=0.56.
Remark 2.11. If only some pairs of strategies are ever compared, the complete graph is replaced by a comparison graph with its triangles, and its first cohomology need not vanish. A third, harmonic, component appears: cyclic advantage around a loop that bounds no triangle, locally consistent and globally not a rating. This is the only place in the volume where a cohomology group is not zero for a trivial reason.
Notes
The index theorem for the replicator equation is in [29, Ch. 13]; the perturbation argument is Hofbauer’s. Conley’s theory is in [14], with an accessible account of the index in [46]. Chain recurrence as a solution concept for games is argued in [44]. The Hodge decomposition of pairwise comparison data is from [31]; its game-theoretic form for general finite games, into potential, harmonic and non-strategic parts, is from [13]; the use of the transitive and cyclic parts in the evaluation of agents is from [11].
Exercises
Exercise 2.1. Compute the index of each equilibrium of the three generic classes of two-strategy games in the table of , and verify .
Exercise 2.2. Show that an antisymmetric K is a gradient if and only if its curl vanishes on all triangles through one fixed vertex.
Exercise 2.3. Compute the Hodge decomposition and the transitivity index of the antisymmetric game on three strategies with K12=1, K23=1, K13=t, as a function of t.
Exercise 2.4. Determine the invasion graph and its sink components for the Hawk–Dove game with V<C. What do they miss?
Revision Protocols, Other Dynamics, and Open Systems
The replicator equation is one dynamic among many. The source derives it a second time from imitation, introduces two rivals, and reports a theorem that separates them [source, §3.2.2, §3.3]. This chapter places all three in one frame and then takes the frame apart into components.
Revision protocols
A population game is a continuous map F:Δ(S)→RS; the linear case F(x)=Ax is the symmetric game (S,A). Following Sandholm [47], a revision protocol is a continuous map ρ:RS×Δ(S)⟶R≥0S×S, where ρij(π,x) is the rate at which a player of strategy i switches to j when payoffs are π and the state is x; the mean dynamic it induces is x˙i=j∑xjρji(F(x),x)−xij∑ρij(F(x),x).
Remark 3.1. [reformulation; cf. [47]] For a fixed population state the matrix ρ is the rate matrix of a continuous-time Markov chain on S, and (4) is its forward equation x˙=xL. A revision protocol is thus a map from states to generators, x↦L(x), and the mean dynamic is x˙=xL(x): a Markov chain whose transition rates depend on its own law. The chain describes one agent; the equation describes the population. This is the sense in which the continuous models of the source are limits of the finite ones of .
Proposition 3.2 (Imitation gives the replicator equation). [classical; [49, 47]] Under pairwise proportional imitation, ρij=xj[πj−πi]+, the mean dynamic is the replicator equation. [O1]
The factor xj is the probability of meeting a j-player; the agent needs to know nothing about the game except what it and the player it meets have earned. Two rivals, the Brown–von Neumann–Nash (BNN) dynamic and the Smith dynamic, dispense with the meeting.
dynamic
protocol ρij
mean dynamic x˙i
replicator
xj[πj−πi]+
xi(πi−πˉ)
BNN
[πj−πˉ]+=:kj
ki−xi∑jkj
Smith
[πj−πi]+
∑j(xj[πi−πj]+−xi[πj−πi]+)
Imitation is natural and innovation is not
Hofbauer and Sandholm isolate four properties of a dynamic x˙=VF(x) [28]; the source states them as the hypotheses of its Theorem 8. Continuity: VF depends continuously on F. Positive correlation: VF(x)⋅F(x)>0 whenever VF(x)=0. Nash stationarity: VF(x)=0 exactly at Nash equilibria. Innovation: if x is not a Nash equilibrium and an unused strategy is a best reply to x, that strategy grows.
continuity
pos. correlation
Nash stationarity
innovation
replicator
yes
yes
no
no
BNN
yes
yes
yes
yes
Smith
yes
yes
yes
yes
At All-Cooperate in the Prisoner’s Dilemma the replicator field vanishes and the other two do not [O2]; at every Nash equilibrium of sixty random games both of the others vanish. [O3]
Theorem 3.3 (Hofbauer–Sandholm). [literature; [28]; source, Theorem 8] For every dynamic satisfying the four properties there is a game with a strictly dominated strategy that survives along solutions from most initial conditions.
The example has the same shape for every such dynamic: a game with a cycle, and a twin of one strategy made slightly worse. In bad Rock–Paper–Scissors (win 1, loss 2) with a twin of Scissors that earns 0.1 less, the twin’s time-averaged share under the Smith dynamic is 0.116; under the replicator equation it is zero, and gives the rate. [O4]
The functor of explains the difference.
Proposition 3.4 (Names and individuals). [observation]
Every imitative protocol ρij=xjr(πi,πj) has a mean dynamic that is natural for all payoff-preserving maps: faces are invariant and clones lump, exactly as in .
A dynamic that is natural for subgame inclusions leaves every face invariant, so every pure state is a rest point. In any game with a pure state that is not a Nash equilibrium it violates Nash stationarity and Innovation.
The Brown–von Neumann–Nash and Smith dynamics are natural for symmetries and for neither of the other two generating cases of : an absent strategy can appear, and duplicating a strategy changes the motion of the class totals. [O7]
Proof. (a) The mean dynamic is x˙i=xi∑jxj(r(πj,πi)−r(πi,πj)). The factor xi gives invariance of faces, and the sum depends on x only through the distribution of payoffs, which is unchanged when clones are merged. (b) is immediate from the definitions. (c) In both protocols the inflow into strategy i does not carry the factor xi. A strategy with two names receives the inflow twice: for Rock–Paper–Scissors with Rock duplicated the discrepancy between the pushed-forward field and the field of the quotient game reached 0.56 for Smith and 0.38 for Brown–von Neumann–Nash over fifty random states. ◻
Remark 3.5. Imitation counts individuals; a direct protocol counts names. Under imitation a strategy is as visible as it is common, so a twin of a strategy that exists is invisible as a separate thing, and a dominated twin dies at the rate of its penalty. Under a direct protocol every name is a candidate at every moment whatever its frequency, so a twin is a second target for switching, and it is replenished each time the cycle makes it nearly optimal. is the price of Nash stationarity: one cannot have both the invariance of and rest points that are exactly the Nash equilibria.
Populations as open systems
In (2) the game and the learning rule are fused. They can be separated.
Definition 3.6. A population box on S is an open dynamical system with input a payoff vector π∈RS, state x∈Δ(S), output the state, and dynamics x˙=V(x,π). The replicator box has Vi=xi(πi−x⋅π).
Proposition 3.7 (The replicator box integrates and normalizes). [classical; ]For any integrable input π(⋅) and interior initial state, the replicator box has the solution x(t)=softmax(logx(0)+∫0tπ(τ)dτ). In the coordinates z=logx modulo constants the box is the integrator z˙=π. [O6]
All the nonlinearity of the replicator equation is in the game and in the readout, the map softmax from RS/R1 onto the open simplex; the box itself is linear. The Lyapunov function of is the Bregman divergence of the convex function whose gradient is this readout.
A game is then a way of closing boxes.
Remark 3.8. [reformulation; cf. [55, 37]] Open dynamical systems are the algebras of an operad of wiring diagrams: a diagram with boxes of given interfaces determines a closed system once each box is filled. A symmetric game is the one-box diagram with feedback through A; a bimatrix game is the two-box diagram; a local-interaction model () has one box per vertex of a graph. Replacing the replicator box by a Smith box changes the dynamics and not the diagram. The statement that the source’s models differ “only in the dynamics” or “only in the interaction structure” is the statement that a model is a pair of a diagram and a filling.
Two populations
For a bimatrix game (A,B) the two-box system with replicator boxes is x˙i=xi((Ay)i−xTAy),y˙j=yj((BTx)j−yTBTx) on Δ(S)×Δ(T). The single-population equation for A is its restriction to the diagonal in the case B=AT: the diagonal is the fixed set of the symmetry exchanging the two boxes.
Theorem 3.9. [classical; [51, 45, 29]] In the two-population replicator dynamics a rest point is asymptotically stable if and only if it is a strict Nash equilibrium. In particular no mixed equilibrium is asymptotically stable.
After a change of velocity the flow in the interior preserves volume, which excludes interior attractors. For the source’s Battle of the Sexes, with payoffs to Row and to Column, the mixed equilibrium (x,y)=(32,31) is a saddle with eigenvalues ±32, and orbits started near it end at one of the two pure equilibria. [O5] The population model selects conventions and never the mixed equilibrium, which is the content of the source’s discussion [source, §3.4].
Notes
Revision protocols and mean dynamics are developed systematically in [47]; proportional imitation is due to Schlag [49] and, in a different form, to Björnerstedt and Weibull [9]. The Brown–von Neumann–Nash dynamic is from [12] and the Smith dynamic from [54]. Elimination of dominated strategies under imitative dynamics is in [38, 48]. For open dynamical systems and wiring diagrams see [55, 37]; for games assembled compositionally from open pieces, [21] and [22].
Exercises
Exercise 3.1. Show that imitation driven by dissatisfaction, ρij=xj(K−πi) with K larger than every payoff, also has the replicator equation as its mean dynamic.
Exercise 3.2. Show directly that the rest points of the Brown–von Neumann–Nash dynamic are exactly the Nash equilibria.
Exercise 3.3. Prove .
Exercise 3.4. Write the two-population replicator equations for the Battle of the Sexes above in the coordinates (x,y), and verify the eigenvalues ±32 at the mixed equilibrium.
Structure
Finite Populations
A real population is finite, and in a finite population chance decides what the differential equation leaves open. The source’s model is the frequency-dependent birth–death process [source, §4.1]. Its analysis is classical, and we shall say plainly at the end how little the categorical language adds to it. What it does add is a precise statement of the one point at which the source draws a conclusion that needs qualifying.
The Moran process
Two strategies A and B have payoffs , all positive. In a population of N with i players of type A, the expected payoffs against a randomly chosen other player are Fi=N−1a(i−1)+b(N−i),Gi=N−1ci+d(N−i−1), and the fitnesses are fi=1−w+wFi, gi=1−w+wGi for an intensity of selection w∈(0,1]. At each step one individual is chosen to reproduce with probability proportional to fitness, and its offspring replaces a uniformly chosen individual. The number of A-players is a Markov chain on {0,…,N}, that is, an endomorphism in FinStoch, with pi+=ifi+(N−i)giifi⋅NN−i,pi−=ifi+(N−i)gi(N−i)gi⋅Ni, and 0 and N absorbing.
Theorem 1.1 (Fixation). [classical; [35, 41]] The probability that a single A-player takes over the population is ρA=(1+k=1∑N−1i=1∏kfigi)−1.
Proof. The probability hi of absorption at N from i is the harmonic function with h0=0, hN=1. Harmonicity gives hi+1−hi=(pi−/pi+)(hi−hi−1)=(gi/fi)(hi−hi−1), and the differences telescope. ◻
For constant fitness r of the mutant relative to the resident this is ρ=(1−r−1)/(1−r−N), and ρ=1/N in the neutral case. [F3]
The source tabulates the fixation probability ρB of a single defector in the Prisoner’s Dilemma a=3, b=1, c=4, d=2 with w=1. The formula above, with self-interaction excluded as in the definition of Fi and Gi, reproduces the table; if a player may meet itself the values differ in the second decimal place at N=10 and have the same limit. [F1]
N
10
102
103
104
105
source
0.34263
0.25879
0.25088
0.25009
0.25001
computed, no self-play
0.34263
0.25879
0.25088
0.25009
not run
computed, self-play
0.30163
0.25500
0.25050
0.25005
not run
Proposition 1.2 (The limit). [classical; ]If B strictly dominates A (c>a and d>b) and w=1, then ρB→1−a/c as N→∞.
Proof. For ρB the ratios in are those of resident to mutant fitness. With j mutants and N→∞ the j-th ratio tends to a/c, and by dominance all ratios are bounded by some θ<1 for large N, uniformly in the composition. Dominated convergence gives ρB−1→∑k≥0(a/c)k=(1−a/c)−1. ◻
With a=3 and c=4 the limit is 41. [F2] The number 1−a/c is the survival probability of a branching process in which each mutant has relative fitness c/a: while mutants are rare they meet only residents, and their lineage either dies out early or escapes.
Two limits that do not commute
The source concludes from ρB→41 that “the replicator dynamics cannot be the limit of the birth-death process”, since under the replicator dynamics any positive fraction of defectors takes over with certainty [source, §4.1]. The observation is correct. The conclusion holds for one order of limits and fails for the other.
Theorem 1.3 (Mean-field limit). [classical; [33, 57]] Fix an initial fractionx0∈(0,1) and a time horizon T, measured in generations of N steps. As N→∞ the frequency of A in the Moran process converges in probability, uniformly on [0,T], to the solution of the adjusted replicator equationx˙=xF(x)+(1−x)G(x)x(1−x)(F(x)−G(x)), with fluctuations of order N−1/2.
The adjusted equation has the same orbits as (3) and a different clock. For a Hawk–Dove game with background fitness the root-mean-square deviation from the solution at T=4 was 0.158, 0.084 and 0.040 at N=50, 200 and 800: it halves when N is quadrupled. [F5]
Remark 1.4 (Which limit). [observation]Write ΦN(x0,t) for the law of the frequency at generation t from initial fraction x0. The replicator dynamics is the limit N→∞ with x0 and t fixed. Fixation of a single mutant is the limit t→∞ first, at x0=1/N, and then N→∞; here the initial fraction tends to zero, the limiting differential equation starts at the rest point x=0 and never leaves, and the outcome is decided in a boundary layer of width O(1/N) where the population is a branching process and not a flow. The two descriptions compose: a defector lineage escapes the layer with probability 1−a/c and, having escaped, is carried to fixation by the flow with probability tending to one. The square commutes for each fixed x0>0 in the Prisoner’s Dilemma and fails along x0=1/N. The replicator dynamics is a limit of the birth–death process, and it is not the limit that computes invasion from one mutant.
Weak selection
Theorem 1.5 (The one-third law). [literature; [42]] For w→0, selection favours the fixation of A, in the sense ρA>1/N, if and only if a(N−2)+b(2N−1)>c(N+1)+d(2N−4). For a coordination game (a>c, d>b) and large N this holds if and only if the unstable equilibrium x∗=(d−b)/(a−c+d−b) of the replicator equation, the frequency of A at the barrier between the two conventions, is below 31.
The condition was confirmed against exact fixation probabilities in 299 random coordination games at N=60. [F4] The constant has a simple origin: to first order in w the advantage h(x)=F−G is weighted by the number of visits that a neutral lineage started from one mutant pays to frequency x, which is proportional to 1−x, and ∫01(αx−β)2(1−x)dx=α/3−β. A convention can thus be invaded by a single mutant, with probability above the neutral one, exactly when its basin under the deterministic dynamics is smaller than a third; the replicator equation alone says only that it cannot be invaded at all.
Rare mutations
Add mutation at a small rate μ. The chain becomes ergodic, and as μ→0 its stationary distribution concentrates on the monomorphic states, where it is the stationary distribution of the embedded chain that jumps from all-i to all-j with probability proportional to the fixation probability ρi→j of a single j-mutant [20]. For large populations and strong selection this chain moves only along the edges of the invasion graph of and its stationary distribution is carried by the sink components: all of Rock–Paper–Scissors, either convention of a coordination game, defection in the Prisoner’s Dilemma. [I7] This is the finite-population counterpart of the chain components of , and it is the construction used to rank learning agents by Markov–Conley chains [43]. Stochastic stability in the sense of [32, 60] is the same idea for best-reply dynamics, where the selected convention is the risk-dominant one.
Remark 1.6 (What the language adds here). Not much. A finite-population model is a morphism in FinStoch; fixation is a harmonic function; the embedded chain is a functor from games to Markov chains that is natural for symmetries and, like the direct protocols of , not for cloning (an example is computed in the companion paper [17]). The content of the chapter is analytic, and the one structural point is .
Notes
The frequency-dependent Moran process and its fixation probabilities are in [42, 41]; the original process is Moran’s [35]. Density-dependent Markov chains and their differential-equation limits are due to Kurtz [33]; the identification of the limit of the Moran process with the adjusted replicator equation is in [57]. The one-third law is from [42]. The small-mutation limit is treated in [20].
Exercises
Exercise 1.1. Show without the formula that neutral fixation has probability 1/N.
Exercise 1.2. Derive ρ=(1−r−1)/(1−r−N) from .
Exercise 1.3. Deduce the large-population form of the one-third law from the inequality in .
Exercise 1.4. For the Prisoner’s Dilemma of the source’s table, show that the fixation probability of a single cooperator is smaller than (3/4)N−1.
Local Interaction
In the last part of the source the population lives on a graph: each player meets only its neighbours and learns only from them [source, §4.2]. The models are simulated, and the source is candid that their behaviour is sensitive to details. This is the chapter in which structure helps most, because a graph has maps, and the maps explain patterns that the simulations display.
The model
Let Γ be a finite graph with vertex set V, and (S,A) a game. A configuration is a map σ:V→S. The score of v is uv(σ)=∑w∼vAσ(v)σ(w). Under imitate-the-best every player simultaneously adopts the strategy of the highest scorer among itself and its neighbours. Ties need a rule, and we take one that uses no labels: a player keeps its strategy if that strategy is among the best, or if the best scorers disagree. This defines a map UΓ:SV⟶SV, a discrete dynamical system on a finite set. Every orbit is eventually periodic, and the questions are which periods occur and why.
Coverings
A coveringp:Γ~→Γ is a graph homomorphism that maps the neighbours of each vertex bijectively onto the neighbours of its image. The ring Ckn covers Cn for n≥3; the infinite line covers every ring; a torus covers a smaller torus; the square lattice covers them all.
Theorem 2.1 (Naturality under coverings). [observation]For a covering p:Γ~→Γ the pullback p∗:SV→SV~, σ↦σ∘p, commutes with the update: UΓ~∘p∗=p∗∘UΓ. Hence Γ↦(SV,UΓ) is a contravariant functor from graphs and coverings to dynamical systems. The same holds for every update rule in which a player’s new strategy is a function of the labelled tree of walks of some fixed length starting at that player; imitate-the-best uses walks of length two.
Proof. Since p is bijective on neighbourhoods, uv~(σ∘p)=up(v~)(σ) for every v~. Applying this at v~ and at each of its neighbours, the pairs (strategy, score) seen by v~ are those seen by p(v~), with multiplicity. The update depends on nothing else. ◻
Corollary 2.2.
Every orbit on Γ lifts to an orbit on every cover. The configurations on the ring Ckn that repeat with spatial period n are exactly the pullbacks of configurations on Cn, and they evolve as they do there. [L2]
The automorphisms of Γ and the symmetries of the game act on SV and commute with UΓ; the fixed set of every group of such symmetries is invariant. [L3]
What happens on a small ring or torus happens on every larger one that covers it, and on the infinite lattice. A phenomenon found in simulation on a 30×30 torus that survives restriction to a 3×3 or 6×6 torus can be analysed there by hand.
Remark 2.3. [literature; [15, 23]] For continuous-time systems on networks this is the theorem of DeVille and Lerman that fibrations of graphs induce maps of dynamical systems, and the invariant subspaces of (b) are the synchrony subspaces of Golubitsky and Stewart. On a Cayley graph the statement that U commutes with translations is half of the Curtis–Hedlund–Lyndon theorem: the continuous translation-equivariant self-maps of SG are exactly the cellular automata [26]. Local-interaction models on lattices are cellular automata whose local rule happens to come from a game.
Why the ring rotates
The source places Rock–Paper–Scissors on a ring of nine players in three clusters, RRRPPPSSS, and observes that each cluster moves one place per generation, for ever [source, §4.2.1]. [L1]
Proposition 2.4. [observation]Let τ be rotation of C9 by three places and c the cyclic relabelling R↦P↦S↦R, which is a symmetry of the game. The configuration σ0=RRRPPPSSS is fixed by the twisted symmetry g:σ↦c∘σ∘τ−1. The set of configurations fixed by g has 27 elements and is invariant under U. Nine of them are the rotations of σ0, on which U acts as rotation by one place, with period nine; the other eighteen are mapped into this orbit by one application of U. [L8]
Proof. Invariance is (b). A fixed configuration is determined by its values on three consecutive vertices, whence 27. For the motion, score a win 1, a loss −1 and a tie 0. A player inside a cluster scores 0; at the boundary between the clusters of R and P the R-player scores −1 and the P-player +1. The losing boundary player sees a neighbour with the top score and adopts its strategy; the winning one keeps its own; the middle player of a cluster sees only its own strategy. Each cluster therefore advances one place into the cluster it beats and retreats one place from the cluster that beats it. The statement about the other eighteen configurations is by enumeration. ◻
The pattern is a discrete rotating wave: a relative equilibrium, fixed by the dynamics up to a symmetry. The twisted symmetry accounts for the shape of the pattern, three clusters in cyclic order, and the local computation for its speed. By (a) the same wave runs on every ring of 9k players, and patterns with clusters of other sizes are waves for other twisted symmetries. Within the symmetric set the wave is the only possible long-run behaviour, which is more than symmetry alone could give. The source remarks that on a ring the only outcomes are cycling and uniformity. With the tie rule adopted here there is a third: the configuration RPSRPSRPS, in which every player beats one neighbour and loses to the other, is a fixed point, since all scores are equal. We found no tie rule stated in the source, and the remark may be correct for the rule used there; the example shows that it depends on one.
Cooperation at the boundary
Now let S={C,D} with the Prisoner’s Dilemma payoffs T>R>P>S (temptation, reward, punishment, sucker). On the simple ring a cluster of cooperators cannot grow. On the 1,2-circulant, where each player has the two nearest players on each side as neighbours, it can [source, §4.2.2].
Proposition 2.5 (Thresholds on the 1,2-circulant). [observation]Consider a run of at least five cooperators next to a run of at least five defectors. Under imitate-the-best the boundary between them
moves into the defectors, one place per round,
if 3R+S>2T+2P;
is stationary
if 3R+S<2T+2P<4R;
moves into the cooperators, two places per round,
if 2T+2P>4R.
Proof. Number the cooperators 1,2,3,… from the boundary and the defectors 0,−1,−2,…. The scores are u1u0=2R+2S,=2T+2P,u2u−1=3R+S,=T+3P,u3u−2=4R,=4P. Defector 0 sees players −2,…,2: the best defector it sees is itself and the best cooperator is player 2, so it switches exactly when 3R+S>2T+2P. Defector −1 sees player 0, who outscores the only cooperator in view, and stays; the remaining defectors see no cooperator. Cooperators 1 and 2 both see defector 0 and cooperator 3, and stay exactly when 4R>2T+2P; cooperator 3 sees only cooperators and player 0 is out of its sight. ◻
With R=1, P=S=0 and T=b the thresholds are b=23 and b=2. Starting from six cooperators among thirty players, the cluster grew by two per round for b=1.1, stayed at six for b=1.7, and vanished in two rounds for b=2.1. [L6] For the source’s matrix (T,R,P,S)=(1.1,1,0,−0.1) the first inequality reads 2.9>2.2, which are the two scores the source quotes for the cooperator and the boundary defector. The simulation then reproduces the rest of the source’s account: the cooperators spread until one defector remains; the lone defector scores 4T=4.4 and converts its four neighbours; the block of five defectors shrinks to three and to one; and the number of defectors cycles 1,5,3 for ever. On the simple ring the same cluster is frozen for this matrix and eroded for the source’s second matrix (1.5,1,0.6,0), as the source states. [L7]
Remark 2.6. The mechanism is visible in the proof: cooperation spreads when the cooperator one step behind the front, who has three cooperating neighbours, outscores the defector at the front, who exploits two. On the simple ring there is no such player. The source’s caution that results of this kind depend on the neighbourhood, the payoffs and the update rule is exactly right, and the proposition says how: through three linear inequalities that change with each of them.
Graphs that amplify and suppress selection
For constant fitness the Moran process can be run on a weighted directed graph: an individual at i, chosen in proportion to fitness, places its offspring at j with probability wij, where W is a stochastic matrix.
Theorem 2.7 (Isothermal theorem). [literature; [34]] The fixation probability of a single mutant of fitness r, placed uniformly at random, equals the Moran value (1−r−1)/(1−r−N) for every r if and only if W is doubly stochastic.
A doubly stochastic matrix is a stochastic map that preserves the uniform distribution, so the isothermal graphs are the endomorphisms of the probability space (V,uniform) in FinStoch. For them the number of mutants is itself a birth–death chain with ratio r (), and structure is invisible to selection: on the complete graph and on the cycle the computed fixation probabilities agree with the Moran value to ten digits. [L4] Other graphs change the balance between selection and drift.
N=6
well-mixed
star
directed line
advantageous mutant, r=1.5
0.3654
0.4432
0.1667
disadvantageous mutant, r=0.7
0.0571
0.0333
0.1667
The star amplifies selection in both directions, and on the directed line only a mutant at the root can take over, so fixation is 1/N whatever the fitness. [L5] The values are exact, from the linear system for the absorption probabilities on all 26 subsets.
Notes
Local-interaction models of this kind go back to Nowak and May [40]; the source’s examples are in the tradition of Skyrms’s and Alexander’s work on the evolution of social structure [53, 2]. Evolutionary graph theory, the isothermal theorem, amplifiers and suppressors are from [34]. The source ends with a simulation of the centipede game on a lattice, in which the socially optimal outcome occurs 13.3 per cent of the time, close to the figure of about 15 per cent in the experiments of McKelvey and Palfrey [source, §4.2.3]; we have not reproduced it, since it depends on the distribution of initial conditions, which the functorial statements above do not see.
Exercises
Exercise 2.1. Show that reduction modulo n is a covering Ckn→Cn for n≥3 and not for n=2.
Exercise 2.2. Verify that the configurations on C9 fixed by the twisted symmetry of number 27, that each uses every strategy exactly three times, and that RPSRPSRPS is a fixed point of U that is not among them.
Exercise 2.3. Repeat the analysis of for the simple ring, and recover the source’s two examples.
Exercise 2.4. Show that for doubly stochastic W the ratio of the probabilities that the number of mutants increases and decreases is r in every state. Why is the star not isothermal?
Assessment
Assessment
What the language did
Five things, in decreasing order of how much they changed our understanding of the source.
It isolated the invariance that separates the dynamics. The replicator equation is natural for all payoff-preserving maps (); the Brown–von Neumann–Nash and Smith dynamics are natural only for symmetries (). The survival of dominated strategies, which the source presents as a surprising theorem about a class of dynamics, becomes the visible cost of giving up naturality for inclusions and clones: a dynamic that sees names instead of individuals keeps reintroducing a bad name.
It showed why stability must be a property of sets. The source moves from evolutionarily stable strategies to evolutionarily stable sets as a refinement motivated by examples. gives a reason that is independent of examples: stability of a point is destroyed by duplicating a strategy, stability of a set is preserved, and no notion that depends on how strategies are named can be the right one.
It explained simulated patterns. The rotating clusters on the ring are forced by a twisted symmetry and a covering (, ); the growth of cooperation on the circulant is three linear inequalities (). Both were found by asking what the maps of the model are.
It separated the game from the learner. Treating a population as an open system (, ) makes “same game, different dynamics” and “same dynamics, different structure” into statements about a diagram and its fillings, and it is the form in which the subject is used in machine learning, as the companion paper [17] develops.
It located a non-commuting square. The source’s claim that the replicator dynamics is not the limit of the birth–death process is a statement about two orders of limits ().
What it did not do
It proved no new theorem of evolutionary game theory. The observations tagged as such are short, and some of them are surely known to people who work with these models, whether or not they are written down in this form. The fixation formulas, the mean-field limit and the one-third law gain nothing from being called morphisms in FinStoch. Chaos in the replicator equation, which the source illustrates with a four-strategy example [source, §3.2.5], is untouched: we have no categorical handle on it beyond the remark that a strange attractor is a chain component with a non-trivial Conley index. Bomze’s classification of the phase portraits for three strategies is likewise only cited. The centipede simulation is not reproduced. And the source’s philosophical conclusion, that these models give how-possibly explanations whose robustness must be argued case by case [source, §5], is one that the present treatment supports in a specific way and does not replace: naturality tells you which features of a model cannot matter, and so narrows the list of those that might.
How much of this is higher
Source
Structure used here
Level
§2 stable strategies and sets
Game; pullback along clone maps
1-categorical
§3.2 replicator dynamics
the functor Rep:Game→Dyn
1-categorical
§3.2.4 stability, cycles
index theorem; Conley index
homotopy types
§3.2.4 Rock–Paper–Scissors
Hodge decomposition
cohomology in degree 1
§3.3 other dynamics
naturality and its failure
1-categorical
§3.3–3.4 dynamics, populations
open systems and wirings
operadic; a double category
§4.1 birth–death process
FinStoch; a non-commuting square
1-categorical
§4.2 local interaction
coverings; equivariance
1-categorical, with groupoids of symmetries
In summary, the subject at the level of the source is mostly ordinary category theory. Three things point beyond it. Games modulo column shifts and positive rescalings form a groupoid over each strategy set, and Rep is invariant along it up to reparametrization of time; treating these equivalences as 2-cells is the natural setting for . The Conley index is a homotopy type, functorial for the inclusions of a Morse decomposition, and its continuation invariance is a statement about families of games. And the first cohomology that vanishes for the complete comparison graph does not vanish for partial comparisons, which is where the decomposition of acquires a harmonic part.
Programme
[programme]Four questions seem worth the effort. (1) Is there a homotopy-invariant of a game, computable from the payoff matrix, that determines the Conley indices of the chain components of its replicator flow, as the index of determines their Euler characteristics? (2) Which dynamics, among those arising from revision protocols, are functors on Game? shows that all imitative ones are; a characterization would say what naturality costs in terms of the properties of . (3) Can the covering functor of be extended from coverings to fibrations and to stochastic update rules, so that it applies to the Moran process on graphs and explains amplifiers as it explains waves? (4) Is there a setting in which the two limits of are the two legs of one universal construction?
Notes
For the source’s own assessment of what evolutionary models explain, see its concluding section. A treatment of classical game theory in the style of this volume is [22]; relative entropy as a functor, used in , is developed in [18]; the index theory used in is in [16].
Toolkit
This appendix collects the general notions used in the text, in the order in which they are needed.
Categories and functors.
A category has objects, morphisms and an associative composition with identities; a functor preserves them. A statement of the form “the construction X↦F(X) is natural” means that F is a functor: every map X→Y of the relevant kind induces a map F(X)→F(Y), compatibly with composition. A group acting on X then acts on F(X), a subobject of X gives an invariant subobject of F(X), and a quotient of X gives a quotient of F(X).
Convex spaces and the distribution monad.
For a finite set S, Δ(S) is the simplex of probability distributions on S. A map f:S→T induces the pushforward f∗:Δ(S)→Δ(T), and Δ is a monad on finite sets whose algebras are convex spaces [19]. A map Δ(S)→R is affine exactly when it is the expectation of a function on S; a payoff is a function on S×S, and its biaffine extension is the mixed extension.
Stochastic maps.
FinStoch is the category of finite sets and stochastic matrices. A Markov chain on a finite set is an endomorphism in it. A state is absorbing if its row is a point mass; a function is harmonic if it is fixed by the matrix acting on functions.
Dynamical systems.
A flow on a compact space X is a continuous action of R; a map of flows is a continuous map commuting with the actions. A rest point is Lyapunov stable if orbits starting near it stay near it and asymptotically stable if in addition they converge to it. A Lyapunov function is a function that decreases along orbits; a strict one certifies asymptotic stability.
Index and Euler characteristic.
For a vector field with non-degenerate zeros on a compact manifold with boundary on which it points outward, the sum over zeros of the sign of the determinant of the derivative is the Euler characteristic (Poincaré–Hopf). A simplex is contractible, so its Euler characteristic is 1.
Cochains on a graph.
A 0-cochain is a function on vertices and a 1-cochain an antisymmetric function on ordered pairs of adjacent vertices. The differential sends r to (i,j)↦ri−rj. A 1-cochain is closed if its sum around every triangle vanishes. On the complete graph every closed 1-cochain is a differential.
Coverings and symmetries.
A covering of graphs is a homomorphism bijective on the neighbourhood of each vertex. An automorphism of a graph is a covering of the graph by itself. A map between dynamical systems on configuration spaces that commutes with the updates sends orbits to orbits, periodic orbits to periodic orbits of period dividing the original, and invariant sets to invariant sets.
Concordance with the Source
The table lists the sections of J. McKenzie Alexander, Evolutionary Game Theory [3], with the place in this volume where their content is treated and the form it takes there. The source was read from a text extraction of its PDF; its definitions and theorems were located by search and read in context, and the remaining text was read selectively, section by section. Figures were not consulted except through their captions and the surrounding discussion.
Source
Here
Form
1.1 Rock, Paper, Scissors (Lizard, Spock)
circulant games; their automorphism groups
1.2–1.3 Game theory; fundamentals
the distribution monad; the category Game; Nash’s theorem for symmetric games
Q=C(p−q)2/2; escape time from a neutrally stable state
2.2 Properties (Theorems 1–5)
stated with proofs or references; the Bishop–Cannings bound
2.3 Evolutionarily stable sets
pullback along clone maps preserves stable sets and destroys stable points
3.1 Introduction
the category Dyn
3.2 Replicator dynamics (Definition 11)
,
quotient of the growth equation; functoriality
3.2.1 Biological derivation
as stated
3.2.2 Cultural derivation
mean dynamic of an imitative revision protocol
3.2.3 Simple games
, two strategies
one normal form with three generic cases
3.2.4 Stability (Theorems 6, 7)
, ,
relative entropy as Lyapunov function; elimination with its rate
3.2.4 Rock–Paper–Scissors variants
, ,
conserved quantity; eigenvalues; cyclic part of a game
3.2.4 Classification for three strategies
cited only
3.2.5 Chaos
not treated
3.3 Other dynamics (Theorem 8)
,
naturality separates imitation from innovation
3.4 Multipopulation games
two boxes and a wiring
4.1 Birth–death process
, ,
the source’s table recomputed; two limits
4.2 Local interaction
functoriality for coverings
4.2.1 Rock–Paper–Scissors on a ring
twisted symmetry; rotating wave
4.2.2 Prisoner’s Dilemma on graphs
thresholds; the source’s run reproduced
4.2.3 Centipede game
, Notes
not reproduced
5 Conclusion
what naturality contributes to robustness
—
, ,
added: index theorem, chain recurrence, Conley index
—
,
added: mean-field limit, one-third law
—
added: isothermal theorem, amplifiers and suppressors
Computations
The script verify-evolutionary-games.py that accompanies this volume uses only the Python standard library, fixes its random seed, and runs in about ten seconds. It performs 42 checks, each printing PASS or FAIL with the computed values, and exits with status zero if and only if all pass. The checks recompute the numerical statements of the text and test finite or numerical instances of the structural ones. They are evidence that the examples are stated correctly; they do not prove the theorems. Differential equations are integrated with a fourth-order Runge–Kutta scheme; fixation probabilities are computed exactly, from the product formula or by solving the linear system for absorption.
Check
What is computed
S1
Hawk–Dove with V=2, C=4: Qx∗(y)=C(p−q)2/2 on a grid of states ()
S2
Rock–Paper–Scissors: the uniform state is the only Nash equilibrium and is not an ESS
S3
the source’s game with a weakly dominated equilibrium strategy: not an ESS ()
S4
drift game: the neutral equilibrium is left by the replicator flow; time from 0.05 to 21 is 20.944
S5
Hawk–Dove with V<C has exactly one ESS, the mixed one
S6
: over the mixed ESS of Hawk–Dove with Dove duplicated, the fibre is a stable set and no point of it is an ESS
R1
on random games: pushforward along a clone surjection and a subgame inclusion carries solutions to solutions
R2
: dtd(mean payoff) =2Var for symmetric matrices
R3
: dtdD(x∗∥x)=−Qx∗(x) along numerical solutions
R4
: the relative entropy to the centre is conserved, drift 1.3×10−15 over time 40
R5
: eigenvalues (b−a)/6±i3(a+b)/6 against a numerical Jacobian
R6
good Rock–Paper–Scissors converges to the centre; bad Rock–Paper–Scissors leaves every compact subset of the interior
R7
every Nash equilibrium of random games is a rest point
R8
the source’s three-strategy game: the unique equilibrium is uniform, asymptotically stable, and not an ESS
R9
: the log-ratio of a dominated twin to its original falls at exactly the penalty
I1
on 400 random games with three or four strategies: indices sum to 1, the number of equilibria is odd
I2
all 590 ESS found (by Haigh’s criterion) have index +1
I3
coordination game: indices +1,+1,−1
I4
: Rock–Paper–Scissors is purely cyclic, a rating difference purely transitive, the parts orthogonal; τ=0.558 for a random game
I5
the gradient part is a cocycle on every triangle; the cyclic part carries all the curl
I6
dtdxTAx=2Covx(Sx,Ax) on random games
I7
sink components of the invasion graph for three standard games; the small-mutation chain concentrates on them
O1
on random games and states
O2
at All-Cooperate the replicator field vanishes and the two direct dynamics do not
O3
both direct dynamics vanish at every Nash equilibrium of sixty random games
O4
: time-averaged share 0.116 of a dominated twin under the Smith dynamic; extinction under the replicator
O5
Battle of the Sexes with two populations: the mixed equilibrium is a rest point, and forty nearby orbits end at the two pure equilibria
O6
against a numerical solution
O7
(c): defect of naturality under cloning, 4×10−17 for the replicator, 0.555 for Smith, 0.380 for Brown–von Neumann–Nash
F1
the source’s table of fixation probabilities, with and without self-interaction
F2
: the limit 1−a/c=41
F3
neutral and constant-fitness fixation
F4
against exact fixation in 299 random coordination games, N=60
F5
: root-mean-square deviation 0.158, 0.084, 0.040 at N=50,200,800
L1
ring of nine: rotation by one place per round, period nine
L2
for C9→C3, all 27 configurations
L3
equivariance under rotations, reflections and relabelling on random configurations; the twisted symmetry fixes the wave
L4
: complete graph and cycle
L5
star and directed line at N=6 (exact)
L6
at b=1.1, 1.7, 2.1
L7
the source’s matrix on the 1,2-circulant and on the ring; the cycle 1,5,3
L8
: all 27 symmetric configurations; a frozen configuration outside them
Two discrepancies with the source were looked for and one convention was found. The source’s fixation table is reproduced to all printed digits only if a player does not interact with itself (F1). No tie rule for imitate-the-best was found in the source; with the rule of its described runs are reproduced (L1, L7), and a frozen configuration exists that its text does not mention (L8).
Solutions to the Exercises
Solutions to all exercises follow, by chapter. Where a solution relies on a computation, the computation is also carried out by verify-evolutionary-games.py.
Chapter 1
1.1. By affineness in the first argument, π(yϵ∣yϵ)=(1−ϵ)π(x∣yϵ)+ϵπ(μ∣yϵ). Subtract from π(x∣yϵ).
1.2. A symmetry is a permutation that preserves who beats whom. For Rock–Paper–Scissors the three rotations do, and a transposition reverses the cycle, so the group is Z/3. For the five-strategy game the translations give Z/5. A symmetry is an automorphism of a tournament, and such groups have odd order, since an involution would exchange two strategies and so reverse the result between them. A subgroup of the symmetric group on five letters of odd order containing a 5-cycle has order 5 or 15, and there is no subgroup of order 15, since it would be cyclic. The group is Z/5.
1.3. Subtract (V−C)/2 from the first column and V/2 from the second: , so a=V/2 and b=(C−V)/2. For V<C both are positive: neither pure state is an equilibrium and the mixed equilibrium has Hawk at frequency a/(a+b)=V/C. For V>C, a>0>b: Hawk strictly dominates and All-Hawk is the only equilibrium.
1.4. By (a) applied to the clone map onto Hawk–Dove, the equilibria are exactly the states whose image is the mixed equilibrium: (V/C,s,1−V/C−s) with 0≤s≤1−V/C. They form a segment.
Chapter 2
2.1. If x is strict, then π(x∣x)>π(y∣x) for y=x, which is the first clause of the definition. In a two-strategy game let x be a pure ESS, say the first strategy. It is an equilibrium, so A11≥A21, and by hypothesis the inequality is strict; then x is strict. An ESS that is not pure is interior.
2.2. The uniform state is an interior equilibrium, so by (f) it is an ESS if and only if zTAz<0 for z=0 with ∑szs=0. Here zTAz=(a−b)(z1z2+z2z3+z3z1) and z1z2+z2z3+z3z1=−21∣z∣2 on that plane, so zTAz=−2a−b∣z∣2, negative exactly when a>b.
2.3. The identity matrix: each pure strategy is a strict equilibrium, hence an ESS, and (13)=3.
2.4. Write y=(1−q,q), with q the weight on the second strategy. For x the first pure strategy, π(x∣y)=1+99q and π(y∣y)=(1−q)(1+99q)+100q2, so Qx(y)=q(1+99q)−100q2=q(1−q)>0 for 0<q<1: an ESS. For x the second, with p=1−q the weight on the first, Qx(y)=−p2<0: not an ESS, although it is an equilibrium.
Chapter 3
3.1. With payoffs and state (x,1−x), the two strategies earn a(1−x) and bx, and x˙=x(1−x)(a(1−x)−bx). For x˙=x2(1−x), partial fractions give ∫x2(1−x)dx=−x1+log1−xx; evaluate between x0 and x1.
3.2.dtdxTAx=x˙T(A+AT)x=2∑sxs((Ax)s−xTAx)(Sx)s=2Covx(Sx,Ax), because ∑sxs((Ax)s−xTAx)=0. For symmetric A this is twice the variance of Ax.
3.3. At the uniform state the linearization on the tangent plane is 31A composed with the projection along 1. In the basis of the two complex eigenvectors of the cyclic shift, A acts by aω+(−b)ωˉ and its conjugate, with ω=e2πi/3, so the eigenvalues are 31(aω−bωˉ) and its conjugate: real part 31⋅2−a+b, imaginary part ±31⋅23(a+b). The trace is (b−a)/3 and the determinant ((b−a)2+3(a+b)2)/36.
3.4. By (b) the class frequencies follow the replicator equation of Rock–Paper–Scissors from the initial state (21,41,41). By they move on the closed curve on which the relative entropy to the centre is constant, equivalently on which the product of the three frequencies equals 321. The two variants of Rock keep equal shares.
Chapter 4
4.1. Let F(x)=x(1−x)(a−(a+b)x); the index at an equilibrium is the sign of −F′. For a>0>b the only equilibrium is x=1, with F′(1)=b<0: index +1. For a,b>0 the only equilibrium is x∗=a/(a+b), with F′(x∗)=−(a+b)x∗(1−x∗)<0: index +1. For a,b<0 the equilibria are 0, 1 and x∗, with F′(0)=a<0, F′(1)=b<0 and F′(x∗)>0: indices +1,+1,−1. The sum is 1 in each case.
4.2. A gradient has zero curl on every triangle. Conversely, if the curl vanishes on triangles through the vertex 0, put ri=Ki0. Then Kij+Kj0+K0i=0 gives Kij=Ki0−Kj0=ri−rj.
4.3. The row means are r=(31+t,0,−31+t), so G12=G23=31+t, G13=32(1+t), and C12=C23=32−t, C13=−32−t. The curl is 2−t, and τ=3(2+t2)2(1+t)2. It equals 1 at t=2, where the game is a rating difference, and 0 at t=−1, which is Rock–Paper–Scissors.
4.4. Dove invades Hawk, since 0>(V−C)/2, and Hawk invades Dove, since V>V/2. The graph is a two-cycle and its only sink component is the whole of it. This records correctly that neither pure state persists, and it misses the outcome: the flow converges to the mixed state, which is not a vertex.
5.2. At a Nash equilibrium no strategy earns more than the mean, so k=0 and the field vanishes. Conversely, let x˙=0 and suppose κ=∑jkj>0. Then xi=ki/κ for all i, so the support of x consists of strategies earning strictly more than the mean, which contradicts ∑ixi(πi−πˉ)=0. Hence k=0, which is the equilibrium condition.
5.3. Let z(t)=logx(0)+∫0tπ and x=softmax(z). Then dtdlogxi=πi−dtdlog∑jezj=πi−∑jxjπj.
5.4. Row’s two strategies earn 2y and 1−y; Column’s earn x and 2(1−x). Hence x˙=x(1−x)(3y−1) and y˙=y(1−y)(3x−2). At (32,31) the Jacobian has zero diagonal and both off-diagonal entries equal to 3⋅92=32; its eigenvalues are ±32.
Chapter 6
6.1. With equal fitnesses the number of A-players is a bounded martingale, so its expectation at absorption equals its initial value: Nρ=1. Alternatively, each of the N initial individuals is equally likely to be the ancestor of the final population.
6.2. Here gi/fi=r−1 for every i, and 1+∑k=1N−1r−k=(1−r−N)/(1−r−1).
6.3. Dividing by N and letting N→∞ gives a+2b>c+2d, that is, a−c>2(d−b). With a>c and d>b this is x∗=(d−b)/((a−c)+(d−b))<31.
6.4. With i cooperators, figi=3(i−1)+(N−i)4i+2(N−i−1)=2i+N−32i+2N−2, which decreases in i and at i=N−1 equals 3N−54N−4>34. The last term of the sum in alone exceeds (4/3)N−1.
Chapter 7
7.1. The neighbours i±1 of i go to (i±1)modn, which are distinct and are the neighbours of imodn when n≥3. For n=2 they coincide, and C2 is in any case a single edge.
7.2. The condition is σ(i+3)=c(σ(i)) for all i. The values at 0,1,2 are free and determine the rest consistently, because c3 is the identity: 27 configurations. Each orbit {i,i+3,i+6} of the rotation carries a, c(a), c2(a), so each strategy occurs once per orbit and three times in all. In RPSRPSRPS every player beats one neighbour and loses to the other, all scores are 0, and under the tie rule nobody changes. It satisfies σ(i+3)=σ(i)=c(σ(i)) and so is not among the 27.
7.3. Number the cooperators 1,2,… and the defectors 0,−1,… from the boundary. The scores are u1=R+S, u2=2R, u0=T+P, u−1=2P. Defector 0 outscores both its neighbours and stays. Cooperator 1 sees defector 0 and cooperator 2, and stays exactly when 2R>T+P. So a cluster never grows; it is frozen if 2R>T+P and loses one player at each end per round if 2R<T+P. For (1.1,1,0,−0.1), 2>1.1: frozen. For (1.5,1,0.6,0), 2<2.1: eroded.
7.4. Let M be the set of mutants and m=∑i,j∈Mwij. The number of mutants increases with probability proportional to r∑i∈M,j∈/Mwij=r(∣M∣−m), using row sums, and decreases with probability proportional to ∑i∈/M,j∈Mwij=∣M∣−m, using column sums, with the same constant. The ratio is r. On the star each leaf sends its offspring to the centre, so the column of the centre sums to N−1 and that of a leaf to 1/(N−1).
References
Entries were assembled from memory, except [43], whose authors, title and venue were checked against the publisher’s page on 17 November 2026. Volume and page numbers in particular should be verified before they are relied on.
References
E. Akin, The Geometry of Population Genetics, Lecture Notes in Biomathematics 31, Springer, 1979.
J. M. Alexander, The Structural Evolution of Morality, Cambridge University Press, 2007.
J. M. Alexander, Evolutionary Game Theory, Elements in Decision Theory and Philosophy, Cambridge University Press, 2023. The source.
A. Arneodo, P. Coullet, C. Tresser, Occurrence of strange attractors in three-dimensional Volterra equations, Phys. Lett. A 79 (1980), 259–263.
J. C. Baez, T. Fritz, A Bayesian characterization of relative entropy, Theory Appl. Categ. 29 (2014), 422–456.
J. C. Baez, B. S. Pollard, Relative entropy in biological systems, Entropy 18 (2016), no. 2, 46.
D. Balkenborg, K. H. Schlag, Evolutionarily stable sets, Internat. J. Game Theory 29 (2001), 571–595.
D. T. Bishop, C. Cannings, Models of animal conflict, Adv. Appl. Probab. 8 (1976), 616–621.
J. Björnerstedt, J. W. Weibull, Nash equilibrium and evolution by imitation, in The Rational Foundations of Economic Behaviour, Macmillan, 1996, 155–171.
I. M. Bomze, Lotka–Volterra equation and replicator dynamics: a two-dimensional classification, Biol. Cybernet. 48 (1983), 201–211.
D. Balduzzi, K. Tuyls, J. Pérolat, T. Graepel, Re-evaluating evaluation, in Advances in Neural Information Processing Systems 31, 2018.
G. W. Brown, J. von Neumann, Solutions of games by differential equations, in Contributions to the Theory of Games I, Ann. of Math. Stud. 24, Princeton University Press, 1950, 73–79.
O. Candogan, I. Menache, A. Ozdaglar, P. A. Parrilo, Flows and decompositions of games: harmonic and potential games, Math. Oper. Res. 36 (2011), 474–503.
C. Conley, Isolated Invariant Sets and the Morse Index, CBMS Regional Conference Series in Mathematics 38, American Mathematical Society, 1978.
L. DeVille, E. Lerman, Modular dynamical systems on networks, J. Eur. Math. Soc. 17 (2015), 2977–3013.
Anonymous, Evolutionary game theory in machine learning and AI: naturality, regret, and recurrence, Higher Categorical Semantics, 2026. Companion paper.
Anonymous, Entropy, Sources, and Channels in Higher Categories, Higher Categorical Semantics, 2026. Companion volume.
T. Fritz, Convex spaces I: definition and examples, preprint, arXiv:0903.5522.
D. Fudenberg, L. A. Imhof, Imitation processes with small mutations, J. Econom. Theory 131 (2006), 251–262.
N. Ghani, J. Hedges, V. Winschel, P. Zahn, Compositional game theory, in LICS 2018, ACM, 2018, 472–481.
Anonymous, Games and Information in Higher Categories, Higher Categorical Semantics, 2026. Companion volume.
M. Golubitsky, I. Stewart, Nonlinear dynamics of networks: the groupoid formalism, Bull. Amer. Math. Soc. 43 (2006), 305–364.
J. Haigh, Game theory and evolution, Adv. Appl. Probab. 7 (1975), 8–11.
M. Harper, Information geometry and evolutionary game theory, preprint, arXiv:0911.1383.
G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320–375.
J. Hofbauer, On the occurrence of limit cycles in the Volterra–Lotka equation, Nonlinear Anal. 5 (1981), 1003–1007.
J. Hofbauer, W. H. Sandholm, Survival of dominated strategies under evolutionary dynamics, Theor. Econ. 6 (2011), 341–377.
J. Hofbauer, K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, 1998.
J. Hofbauer, P. Schuster, K. Sigmund, A note on evolutionary stable strategies and game dynamics, J. Theoret. Biol. 81 (1979), 609–612.
X. Jiang, L.-H. Lim, Y. Yao, Y. Ye, Statistical ranking and combinatorial Hodge theory, Math. Program. 127 (2011), 203–244.
M. Kandori, G. J. Mailath, R. Rob, Learning, mutation, and long run equilibria in games, Econometrica 61 (1993), 29–56.
T. G. Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Probab. 7 (1970), 49–58.
E. Lieberman, C. Hauert, M. A. Nowak, Evolutionary dynamics on graphs, Nature 433 (2005), 312–316.
P. A. P. Moran, Random processes in genetics, Proc. Cambridge Philos. Soc. 54 (1958), 60–71.
J. Maynard Smith, G. R. Price, The logic of animal conflict, Nature 246 (1973), 15–18.
D. J. Myers, Double categories of open dynamical systems (extended abstract), in Applied Category Theory 2020, EPTCS 333, 2021, 154–167.
J. H. Nachbar, “Evolutionary” selection dynamics in games: convergence and limit properties, Internat. J. Game Theory 19 (1990), 59–89.
J. Nash, Non-cooperative games, Ann. of Math. 54 (1951), 286–295.
M. A. Nowak, R. M. May, Evolutionary games and spatial chaos, Nature 359 (1992), 826–829.
M. A. Nowak, Evolutionary Dynamics: Exploring the Equations of Life, Harvard University Press, 2006.
M. A. Nowak, A. Sasaki, C. Taylor, D. Fudenberg, Emergence of cooperation and evolutionary stability in finite populations, Nature 428 (2004), 646–650.
S. Omidshafiei, C. Papadimitriou, G. Piliouras, K. Tuyls, M. Rowland, J.-B. Lespiau, W. M. Czarnecki, M. Lanctot, J. Perolat, R. Munos, α-Rank: multi-agent evaluation by evolution, Sci. Rep. 9 (2019); arXiv:1903.01373.
C. Papadimitriou, G. Piliouras, Game dynamics as the meaning of a game, ACM SIGecom Exchanges 16 (2019), no. 2, 53–63.
K. Ritzberger, J. W. Weibull, Evolutionary selection in normal-form games, Econometrica 63 (1995), 1371–1399.
D. Salamon, Connected simple systems and the Conley index of isolated invariant sets, Trans. Amer. Math. Soc. 291 (1985), 1–41.
W. H. Sandholm, Population Games and Evolutionary Dynamics, MIT Press, 2010.
L. Samuelson, J. Zhang, Evolutionary stability in asymmetric games, J. Econom. Theory 57 (1992), 363–391.
K. H. Schlag, Why imitate, and if so, how? A boundedly rational approach to multi-armed bandits, J. Econom. Theory 78 (1998), 130–156.
P. Schuster, K. Sigmund, Replicator dynamics, J. Theoret. Biol. 100 (1983), 533–538.
R. Selten, A note on evolutionarily stable strategies in asymmetric animal conflicts, J. Theoret. Biol. 84 (1980), 93–101.
S. Shahshahani, A new mathematical framework for the study of linkage and selection, Mem. Amer. Math. Soc. 17 (1979), no. 211.
B. Skyrms, The Stag Hunt and the Evolution of Social Structure, Cambridge University Press, 2004.
M. J. Smith, The stability of a dynamic model of traffic assignment: an application of a method of Lyapunov, Transportation Sci. 18 (1984), 245–252.
P. Schultz, D. I. Spivak, C. Vasilakopoulou, Dynamical systems and sheaves, Appl. Categ. Structures 28 (2020), 1–57.
P. D. Taylor, L. B. Jonker, Evolutionarily stable strategies and game dynamics, Math. Biosci. 40 (1978), 145–156.
A. Traulsen, J. C. Claussen, C. Hauert, Coevolutionary dynamics: from finite to infinite populations, Phys. Rev. Lett. 95 (2005), 238701.
B. Thomas, On evolutionarily stable sets, J. Math. Biol. 22 (1985), 105–115.
J. W. Weibull, Evolutionary Game Theory, MIT Press, 1995.
H. P. Young, The evolution of conventions, Econometrica 61 (1993), 57–84.
E. C. Zeeman, Population dynamics from game theory, in Global Theory of Dynamical Systems, Lecture Notes in Math. 819, Springer, 1980, 471–497.
Complete flattened LaTeX source
\documentclass[11pt,openany]{book}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[sc,osf]{mathpazo}
\linespread{1.05}
\usepackage[scaled=0.9]{helvet}
\usepackage[paperwidth=7in,paperheight=10in,inner=0.95in,outer=0.85in,top=0.95in,bottom=1.0in,headsep=14pt]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools,stmaryrd}
\usepackage{microtype}
\usepackage{xcolor}
\definecolor{accent}{HTML}{7A1F2B}
\definecolor{ink2}{HTML}{4A5560}
\definecolor{fwd}{HTML}{1F4E79}
\definecolor{bwd}{HTML}{A8432C}
\usepackage{tikz,tikz-cd}
\usetikzlibrary{arrows.meta,positioning,calc,decorations.markings,shapes.geometric,backgrounds,fit}
\usepackage{booktabs,array,tabularx,longtable}
\usepackage{enumitem}
\setlist{itemsep=2pt,topsep=4pt}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage[font=small,labelfont={bf,sf},margin=1.5em]{caption}
\usepackage[colorlinks=true,linkcolor=accent,citecolor=accent,urlcolor=accent,
pdftitle={Evolutionary Game Theory in Higher Categories},
pdfauthor={Anonymous},
pdfsubject={A categorical treatment of evolutionary game theory: stability, replicator dynamics, finite populations, local interaction},
pdfkeywords={evolutionary game theory, replicator dynamics, evolutionarily stable strategy, Conley index, Hodge decomposition, Moran process, category theory}]{hyperref}
\usepackage[nameinlink,capitalise,noabbrev]{cleveref}
\titleformat{\chapter}[display]{\normalfont\Large\scshape\color{accent}}{\chaptertitlename\ \thechapter}{4pt}{\normalfont\huge\bfseries\color{black}}
\titlespacing*{\chapter}{0pt}{10pt}{26pt}
\titleformat{\section}{\normalfont\large\bfseries}{\thesection}{0.7em}{}
\titleformat{\subsection}{\normalfont\normalsize\bfseries\itshape}{\thesubsection}{0.7em}{}
\titleformat{\part}[display]{\normalfont\centering\Large\scshape\color{accent}}{\partname\ \thepart}{12pt}{\normalfont\Huge\bfseries\color{black}}
\pagestyle{fancy}\fancyhf{}
\fancyhead[LE]{\small\thepage\quad\textsc{\nouppercase{\leftmark}}}
\fancyhead[RO]{\small\textsc{\nouppercase{\rightmark}}\quad\thepage}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\chaptermark}[1]{\markboth{#1}{#1}}
\renewcommand{\sectionmark}[1]{\markright{\thesection\ \ #1}}
\fancypagestyle{plain}{\fancyhf{}\fancyfoot[C]{\small\thepage}}
\setlength{\headheight}{14pt}
\setcounter{tocdepth}{1}
\setcounter{secnumdepth}{2}
\raggedbottom
\emergencystretch=2em
\tolerance=1200
\hbadness=2000
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[chapter]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{principle}[theorem]{Principle}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{problem}[theorem]{Open Problem}
\newtheorem{exercise}{Exercise}[chapter]
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\crefname{principle}{Principle}{Principles}
\crefname{construction}{Construction}{Constructions}
\crefname{conjecture}{Conjecture}{Conjectures}
\crefname{exercise}{Exercise}{Exercises}
\crefname{problem}{Open Problem}{Open Problems}
\newcommand{\stag}[2]{{\footnotesize\sffamily\upshape\color{#1}[#2]}\enspace\ignorespaces}
\newcommand{\Scl}[1][]{\stag{ink2}{classical\if\relax\detokenize{#1}\relax\else; #1\fi}}
\newcommand{\Sli}[1][]{\stag{fwd}{literature\if\relax\detokenize{#1}\relax\else; #1\fi}}
\newcommand{\Srf}[1][]{\stag{accent}{reformulation\if\relax\detokenize{#1}\relax\else; cf.\ #1\fi}}
\newcommand{\Sob}{\stag{accent}{observation}}
\newcommand{\Spg}{\stag{bwd}{programme}}
\newcommand{\cat}[1]{\mathsf{#1}}
\newcommand{\Set}{\cat{Set}}
\newcommand{\FinSet}{\cat{FinSet}}
\newcommand{\Meas}{\cat{Meas}}
\newcommand{\Stoch}{\cat{Stoch}}
\newcommand{\FinStoch}{\cat{FinStoch}}
\newcommand{\BorelStoch}{\cat{BorelStoch}}
\newcommand{\FinProb}{\cat{FinProb}}
\newcommand{\FinStat}{\cat{FinStat}}
\newcommand{\Krn}{\cat{Krn}}
\newcommand{\Hilb}{\cat{Hilb}}
\newcommand{\Ban}{\cat{Ban}}
\newcommand{\Src}{\cat{Src}}
\newcommand{\Chan}{\cat{Chan}}
\newcommand{\Dyn}{\cat{Dyn}}
\newcommand{\Cat}{\cat{Cat}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\FF}{\mathcal{F}}
\newcommand{\GG}{\mathcal{G}}
\newcommand{\II}{\mathcal{I}}
\newcommand{\Sinf}{\mathcal{S}}
\newcommand{\Qlaw}{\mathcal{Q}}
\newcommand{\Fun}{\mathcal{F}}
\newcommand{\Dist}{\Delta}
\newcommand{\Giry}{\mathcal{G}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Rbar}{\overline{\mathbb{R}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Fp}{\mathbb{F}_p}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Prob}{\mathbb{P}}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\colim}{colim}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Fix}{Fix}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\TV}{TV}
\DeclareMathOperator{\rk}{rk}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\adj}{\dashv}
\newcommand{\iso}{\cong}
\newcommand{\st}{\mid}
\newcommand{\cpy}{\mathrm{copy}}
\newcommand{\del}{\mathrm{del}}
\newcommand{\KL}[2]{D(#1\,\|\,#2)}
\newcommand{\hb}{h}
\newcommand{\AZ}{A^{\Z}}
\newcommand{\BZ}{B^{\Z}}
\newcommand{\term}[1]{\textbf{\itshape #1}}
\newcommand{\Mfd}{\cat{Mfd}}
\newcommand{\Cart}{\cat{Cart}}
\newcommand{\SmSet}{\cat{SmSet}}
\newcommand{\Dflg}{\cat{Dflg}}
\newcommand{\CinfRing}{C^\infty\cat{Ring}}
\newcommand{\DMfd}{\cat{DMfd}}
\newcommand{\Spc}{\mathcal{S}}
\newcommand{\Sp}{\cat{Sp}}
\newcommand{\Cob}{\cat{Cob}}
\newcommand{\Bord}{\cat{Bord}}
\newcommand{\Vect}{\cat{Vect}}
\newcommand{\Top}{\cat{Top}}
\newcommand{\Para}{\cat{Para}}
\DeclareMathOperator{\Diff}{Diff}
\DeclareMathOperator{\Emb}{Emb}
\DeclareMathOperator{\Imm}{Imm}
\DeclareMathOperator{\Map}{Map}
\DeclareMathOperator{\Sing}{Sing}
\DeclareMathOperator{\Fr}{Fr}
\DeclareMathOperator{\Th}{Th}
\DeclareMathOperator{\Gr}{Gr}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\ind}{ind}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\vdim}{vdim}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\grad}{grad}
\DeclareMathOperator{\Tub}{Tub}
\DeclareMathOperator{\Conf}{Conf}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\relu}{ReLU}
\newcommand{\Or}{\mathrm{O}}
\newcommand{\SO}{\mathrm{SO}}
\newcommand{\RP}{\mathbb{RP}}
\newcommand{\CP}{\mathbb{CP}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\trans}{\pitchfork}
\newcommand{\pt}{\mathrm{pt}}
\newcommand{\loss}{\mathcal{L}}
\tikzset{
ogbox/.style={draw, thick, rounded corners=2pt, minimum width=1.25cm, minimum height=1.05cm, fill=black!4},
fw/.style={-{Stealth[length=5pt]}, thick, fwd},
bw/.style={-{Stealth[length=5pt]}, thick, bwd, densely dashed},
dec/.style={circle, fill, inner sep=1.7pt},
nat/.style={circle, draw, thick, fill=white, inner sep=1.7pt},
leaf/.style={inner sep=2pt, font=\small},
lab/.style={font=\small, inner sep=1.5pt},
infoset/.style={densely dashed, thick, accent},
st/.style={circle, draw, thick, fill=white, inner sep=1.6pt},
ty/.style={rectangle, draw, thick, fill=black!8, inner sep=2.6pt},
}
\newcommand{\sol}[1]{\par\medskip\noindent\textbf{#1.}\enspace\ignorespaces}
\newcommand{\bookauthor}{Anonymous}
\newcommand{\DT}[1]{\cite[#1]{DTHC}}
\newcommand{\pay}[2]{\pi(#1\mid #2)}
\renewcommand{\Game}{\cat{Game}}
\newcommand{\Rep}{\mathrm{Rep}}
\providecommand{\Q}{Q}\renewcommand{\Q}{Q}
\providecommand{\one}{\mathbf{1}}\renewcommand{\one}{\mathbf{1}}
\providecommand{\T}{\mathsf{T}}\renewcommand{\T}{\mathsf{T}}
\newcommand{\chk}[1]{{\footnotesize\sffamily\upshape\color{accent}[#1]}}
\newcommand{\src}[1]{{\footnotesize\sffamily\upshape\color{ink2}[source, #1]}}
\providecommand{\ev}{\mathrm{ev}}
\begin{document}
\frontmatter
\begin{titlepage}
\thispagestyle{empty}
\vspace*{1.1in}
\noindent{\Large\scshape\color{accent} Higher Categorical Semantics}\par
\vspace{0.9in}
\noindent{\fontsize{28}{36}\selectfont\bfseries\raggedright Evolutionary Game\\ Theory in Higher\\ Categories\par}
\vspace{0.35in}
\noindent{\Large\itshape Stability, replicators, recurrence,\\[2pt] finite populations and local interaction}\par
\vfill
\noindent\begin{tikzpicture}[x=1cm,y=1cm]
\coordinate (R) at (0,0); \coordinate (P) at (3.2,0); \coordinate (S) at (1.6,2.77);
\draw[black,thick] (R) -- (P) -- (S) -- cycle;
\fill[accent] (1.6,0.92) circle (1.6pt);
\draw[fw] (1.6,0.92) ++(0:0.55) arc (0:300:0.55);
\draw[fw] (1.6,0.92) ++(20:0.95) arc (20:310:0.95);
\node[lab] at (-0.25,-0.2) {$R$}; \node[lab] at (3.45,-0.2) {$P$}; \node[lab] at (1.6,3.0) {$S$};
\node[lab] at (4.6,1.3) {$\longmapsto$};
\node[ogbox] (G) at (6.6,1.3) {$\Rep$};
\node[lab] at (8.6,1.3) {$\Game\to\Dyn$};
\end{tikzpicture}\par
\vspace{0.5in}
\noindent{\large \bookauthor}\par
\vspace{4pt}
\noindent{\small 2026}
\end{titlepage}
\thispagestyle{empty}
\vspace*{\fill}
\noindent{\small
Version 1.0, 17 November 2026.\par\medskip
\noindent This volume is a treatment, in categorical language, of the material surveyed in J.~McKenzie Alexander,
\emph{Evolutionary Game Theory} (Cambridge Elements in Decision Theory and Philosophy, Cambridge University Press,
2023). It reproduces none of that book's text, figures or tables; where a numerical example of the source is
recomputed, this is said. An appendix gives a section-level concordance.\par\medskip
\noindent Every numbered statement carries a status tag: \Scl a classical result; \Sli[source] a result of the cited
literature; \Srf[source] a known result restated in the language of this volume; \Sob an observation of this volume,
proved here; \Spg a proposal. Tags of the form \chk{R4} name a check in the companion script
\texttt{verify-evolutionary-games.py}; tags of the form \src{Thm.~6} point to the source.\par\medskip
\noindent This book was drafted with the assistance of an AI system (Anthropic's Claude), which also wrote and ran the
companion script. The bibliography was assembled from memory and should be checked before it is relied on.}
\clearpage
\chapter*{Preface}
Evolutionary game theory replaces the rational player of classical game theory by a population. Strategies are
inherited or imitated, payoffs are rates of reproduction or adoption, and the questions change from ``what should
one do?'' to ``what persists?''. Alexander's Element \cite{Alex23} is a compact map of the subject: the static
theory of evolutionarily stable strategies and its set-valued refinements; the replicator equation and its
relatives; finite populations; and models in which interaction is local. It is written for philosophers, and it
is candid about where the models are fragile.
This volume retells that material with one question in mind: which of the constructions are \emph{natural}, in
the technical sense that they commute with the evident maps between games? The answers organize the subject
more sharply than we expected.
\begin{itemize}[leftmargin=1.4em]
\item The replicator equation is a functor from games and payoff-preserving maps to dynamical systems
(\Cref{thm:natural}). Invariance of faces, the lumping of duplicate strategies, and the action of symmetries
are three instances of one statement.
\item Evolutionary stability of a \emph{point} is not preserved by pulling back along a map that duplicates
strategies; evolutionary stability of a \emph{set} is (\Cref{thm:esset}). The set-valued refinements that the
source surveys are what the point-valued notion is forced to become.
\item The equilibria of a regular game carry indices that sum to one, the Euler characteristic of the simplex
(\Cref{thm:index}); behind the number is a homotopy type, the Conley index, and behind recurrent behaviour a
decomposition whose obstruction is a first cohomology class (\Cref{ch:index}).
\item A population is an open system, with payoffs as input and a state as output, and a game is a wiring of
such systems (\Cref{ch:protocols}). The replicator is one box among several, and the source's comparison of
dynamics is a comparison of boxes.
\item Local interaction models are natural with respect to coverings of the interaction graph and equivariant
under its symmetries (\Cref{thm:covering}), which accounts for the rotating patterns the source exhibits.
\end{itemize}
Quantitative statements accompany the qualitative ones throughout: rates of extinction, escape times,
eigenvalues, fixation probabilities, thresholds. All of them are recomputed by the companion script.
How much of this is ``higher'' is assessed in \Cref{ch:coda}. The short answer: most of it is ordinary category
theory; homotopy enters through the index and the Conley index; cohomology enters in degree one; and the
compositional structure of \Cref{ch:protocols} is two-dimensional. Nothing here is a new theorem of evolutionary
game theory. A companion paper applies the framework to machine learning.
The volume belongs to a series with \cite{GIHC}, on classical game theory, \cite{ESCHC}, on information theory,
and \cite{DTHC}, on differential topology, and uses each of them once.
\tableofcontents
\mainmatter
\part{Statics}
\chapter{Games, Populations, and the Simplex}\label{ch:games}
\section{Two readings of one object}
A point of the simplex $\Dist(S)$ over a finite set $S$ of strategies can be read in two ways. It is a
\emph{mixed strategy}: one player randomizing over $S$. It is also a \emph{population state}: a large population
in which the fraction $x_s$ of individuals plays the pure strategy $s$. The source moves between the readings
freely and remarks that the equivalence of two definitions of evolutionary stability rests on their agreement
\src{\S2.1}. The agreement is a fact about maps, and it is the starting point of this volume.
Let $\FinStoch$ be the category of finite sets and stochastic matrices, and let $\Dist$ be the finite
distribution monad on $\Set$: $\Dist(S)$ is the set of probability vectors on $S$, a function $f\colon S\to T$
induces the pushforward $f_*\colon\Dist(S)\to\Dist(T)$, $(f_*x)_t=\sum_{f(s)=t}x_s$, and the algebras of $\Dist$ are
the convex spaces. The real line is a convex space, so:
\begin{proposition}[Mixed extension]\label{prop:mixed}
\Scl Every function $u\colon S\times S\to\R$ extends uniquely to a map $\Dist(S)\times\Dist(S)\to\R$ that is affine in
each variable separately. In coordinates, with $A=(u(s,s'))$, the extension is $(x,y)\mapsto x^{\T}Ay$.
\end{proposition}
\begin{definition}\label{def:game}
A \term{symmetric game} is a pair $(S,A)$ of a finite set $S$ and a matrix $A\in\R^{S\times S}$; the entry
$A_{ss'}$ is the payoff to a player using $s$ against a player using $s'$. For $x,y\in\Dist(S)$ write
\[ \pay{x}{y}=x^{\T}Ay \]
for the payoff of $x$ against $y$, and $f(y)=Ay$ for the vector of payoffs of the pure strategies against $y$.
\end{definition}
Biaffinity is what identifies the two readings: the expected payoff against an opponent drawn at random from
a population in state $y$ is the payoff against the mixed strategy $y$, because both are the affine extension
of the same function. Whenever the source appeals to ``no difference from a mathematical point of view'', it
is appealing to \Cref{prop:mixed}.
\section{Maps of games}
\begin{definition}\label{def:map}
A \term{payoff-preserving map} $f\colon(S,A)\to(T,B)$ is a function $f\colon S\to T$ with
$B_{f(s)f(s')}=A_{ss'}$ for all $s,s'\in S$. Symmetric games and payoff-preserving maps form a category $\Game$.
\end{definition}
Three kinds of map generate everything.
\begin{description}[leftmargin=1.4em,style=sameline]
\item[Inclusions.] An injective $f$ exhibits $(S,A)$ as the \emph{subgame} of $(T,B)$ on the strategies in its
image.
\item[Clone maps.] A surjective $f$ exhibits $(S,A)$ as $(T,B)$ with some strategies duplicated: $s$ and $s'$
with $f(s)=f(s')$ have equal rows and equal columns in $A$.
\item[Symmetries.] An automorphism of $(S,A)$ is a relabelling of strategies that preserves every payoff.
\end{description}
\begin{proposition}\label{prop:push}
\Sob For a payoff-preserving $f\colon(S,A)\to(T,B)$ and $x,y\in\Dist(S)$,
\[ \pay{f_*x}{f_*y}_B=\pay{x}{y}_A,\qquad (B f_*y)_{f(s)}=(Ay)_s\ \text{ for every } s\in S. \]
\end{proposition}
\begin{proof}
$(Bf_*y)_{f(s)}=\sum_t B_{f(s)t}\sum_{f(s')=t}y_{s'}=\sum_{s'}B_{f(s)f(s')}y_{s'}=\sum_{s'}A_{ss'}y_{s'}$. The first
identity follows by pairing with $x$.
\end{proof}
So $\Dist$ lifts to a functor from $\Game$ to convex spaces with a biaffine form, and every construction of
this volume can be asked whether it respects that functor.
\begin{example}[Rock--Paper--Scissors and its relatives]\label{ex:rps}
Let $S=\Z/n$ with $n$ odd, and let $A_{ij}=1$ if $i-j\in\{1,\dots,\tfrac{n-1}2\}$, $-1$ if
$j-i\in\{1,\dots,\tfrac{n-1}2\}$ and $0$ if $i=j$. For $n=3$ this is Rock--Paper--Scissors and for $n=5$ its
five-strategy extension with which the source opens \src{\S1.1}. Translation $i\mapsto i+1$ is a symmetry, so
$\Z/n$ acts on the game. The subgame of the five-strategy game on $\{0,1,3\}$ is a copy of
Rock--Paper--Scissors, an inclusion in $\Game$; the subgame on $\{0,1,2\}$ is not, since there $2$ beats both
others.
\end{example}
A second kind of map acts on payoffs and not on strategies.
\begin{definition}
A \term{column shift} replaces $A$ by $A+\one c^{\T}$ for a vector $c\in\R^S$: a constant $c_{s'}$ is added to
every payoff against $s'$. A \term{rescaling} replaces $A$ by $\lambda A$ with $\lambda>0$.
\end{definition}
A column shift changes $\pay{x}{y}$ by $c^{\T}y$, which does not depend on $x$; it changes no comparison
between strategies. Every game is a column shift of a unique game with zero diagonal, and the source's
normalization to positive payoffs \src{\S4.1} is a column shift by a constant vector.
\section{Equilibria}
\begin{definition}
A state $x\in\Dist(S)$ is a \term{(symmetric) Nash equilibrium} of $(S,A)$ if $\pay{x}{x}\ge\pay{y}{x}$ for all
$y\in\Dist(S)$; equivalently, if $(Ax)_s\le x^{\T}Ax$ for all $s$, with equality for $s\in\supp x$. It is
\term{strict} if $\pay{x}{x}>\pay{y}{x}$ for all $y\ne x$, and \term{quasi-strict} if $(Ax)_s<x^{\T}Ax$ for all
$s\notin\supp x$.
\end{definition}
\begin{theorem}\label{thm:nash}
\Scl[Nash 1951] Every symmetric game has a symmetric Nash equilibrium. If a finite group $G$ acts on $(S,A)$ by
symmetries, the set of Nash equilibria is $G$-invariant and contains a $G$-fixed point.
\end{theorem}
\begin{corollary}\label{cor:uniform}
If a group of symmetries acts transitively on $S$, the uniform state is a Nash equilibrium. In particular the
uniform state is an equilibrium of every game of \Cref{ex:rps}.
\end{corollary}
How equilibria behave under the maps of \Cref{def:map} is recorded once and used repeatedly.
\begin{proposition}\label{prop:nashmaps}
\Sob Let $f\colon(S,A)\to(T,B)$ be payoff-preserving.
\begin{enumerate}[label=(\alph*)]
\item If $f$ is surjective, then $x$ is a Nash equilibrium of $(S,A)$ if and only if $f_*x$ is a Nash
equilibrium of $(T,B)$.
\item If $f$ is injective, then $f_*x$ Nash in $(T,B)$ implies $x$ Nash in $(S,A)$; the converse holds if and
only if no strategy outside the image of $f$ earns more than $\pay{x}{x}$ against $f_*x$.
\end{enumerate}
\end{proposition}
\begin{proof}
By \Cref{prop:push} the pure payoffs against $f_*x$ at strategies in the image of $f$ are the pure payoffs
against $x$, and the mean payoffs agree. The equilibrium condition on $T$ is the equilibrium condition on $S$
together with a condition at strategies outside the image, which is vacuous when $f$ is surjective.
\end{proof}
The asymmetry between (a) and (b) recurs at every level of the theory: clone maps are invisible to selection,
inclusions are visible exactly through the strategies they omit.
\section*{Notes}
The distribution monad and convex spaces as its algebras go back to Stone and to \'Swirszcz; a modern account
is in \cite{Fri09}. \Cref{thm:nash} is from Nash's paper on non-cooperative games \cite{Nas51}. The category
$\Game$ is not standard. Categories of games with strategy-changing morphisms appear in the literature on
potential games and on open games \cite{GHWZ18}; those morphisms are richer and are not needed here. The
classical theory with rational players is the subject of \cite{GIHC}. The invariance of evolutionary dynamics
under column shifts is used systematically in \cite{Zee80,HoSi98}.
\section*{Exercises}
\begin{exercise}\label{exer:biaffine}
Let $y_\epsilon=(1-\epsilon)x+\epsilon\mu$. Show that
$\pay{x}{y_\epsilon}-\pay{y_\epsilon}{y_\epsilon}=\epsilon\,\bigl(\pay{x}{y_\epsilon}-\pay{\mu}{y_\epsilon}\bigr)$.
\end{exercise}
\begin{exercise}\label{exer:aut}
Determine the group of symmetries of Rock--Paper--Scissors and of the five-strategy game of \Cref{ex:rps}.
\end{exercise}
\begin{exercise}\label{exer:hd}
For the Hawk--Dove game with $A=\begin{psmallmatrix}(V-C)/2&V\\0&V/2\end{psmallmatrix}$, find the zero-diagonal
normal form under column shifts and read off the equilibria for $V<C$ and for $V>C$.
\end{exercise}
\begin{exercise}\label{exer:clone}
Let $(S,A)$ be the Hawk--Dove game with the strategy Dove duplicated. Describe all its Nash equilibria for
$V<C$.
\end{exercise}
\chapter{Evolutionary Stability}\label{ch:stability}
\section{The invasion form}
A Nash equilibrium asks that no deviation does better against the incumbent. In a population that is too
weak: a deviation that does equally well against the incumbent is not selected against, and may spread if it
does better against itself. The source's first example \src{\S2.1} is the game
$\begin{psmallmatrix}2&1\\1&1\end{psmallmatrix}$, in which the second strategy is an equilibrium that the first
invades by drift. All of the static theory can be phrased with one function.
\begin{definition}\label{def:Q}
The \term{invasion form} of a state $x$ is the function on $\Dist(S)$
\[ \Q_x(y)=\pay{x}{y}-\pay{y}{y}, \]
the advantage of $x$ over $y$ in a population in state $y$.
\end{definition}
\begin{definition}\label{def:ess}
\Scl[Maynard Smith and Price 1973; \src{Defs.~1--4}] A state $x$ is
\begin{enumerate}[label=(\roman*)]
\item an \term{evolutionarily stable strategy} (ESS) if for every $\mu\ne x$ either $\pay{x}{x}>\pay{\mu}{x}$, or
$\pay{x}{x}=\pay{\mu}{x}$ and $\pay{x}{\mu}>\pay{\mu}{\mu}$;
\item \term{locally superior} if $\Q_x(y)>0$ for all $y\ne x$ in a neighbourhood of $x$;
\item protected by a \term{uniform invasion barrier} if there is $\bar\epsilon>0$ such that
$\pay{x}{y_\epsilon}>\pay{\mu}{y_\epsilon}$ for all $\mu\ne x$ and $0<\epsilon<\bar\epsilon$, where
$y_\epsilon=(1-\epsilon)x+\epsilon\mu$.
\end{enumerate}
\end{definition}
\begin{theorem}\label{thm:essequiv}
\Scl[Hofbauer, Schuster and Sigmund 1979; \cite{Wei95}] The three conditions are equivalent.
\end{theorem}
\noindent The source presents the equivalence as evidence that the definition is not arbitrary. In the present
language two thirds of it is one line: by \Cref{exer:biaffine},
\begin{equation}\label{eq:ray}
\Q_x(y_\epsilon)=\epsilon\,\bigl(\pay{x}{y_\epsilon}-\pay{\mu}{y_\epsilon}\bigr),
\end{equation}
so the barrier inequality along the ray from $x$ towards $\mu$ \emph{is} local superiority along that ray. What
remains is uniformity in $\mu$, which is compactness of the simplex, and the passage from (i) to a
neighbourhood, which uses that $\epsilon\mapsto\pay{x}{y_\epsilon}-\pay{\mu}{y_\epsilon}$ is affine with value
$\pay{x}{x}-\pay{\mu}{x}\ge0$ at $0$ and slope governed by the second clause of (i).
\begin{example}[Hawk--Dove]\label{ex:hd}
With $A$ as in \Cref{exer:hd} and $V<C$, let $x=(p,1-p)$ with $p=V/C$ and $y=(q,1-q)$. The payoff advantage of
Hawk over Dove against $y$ is $(V-qC)/2$, so
\[ \Q_x(y)=(p-q)\,\frac{V-qC}{2}=\frac{C}{2}\,(p-q)^2 . \]
The mixed state is globally, and not only locally, superior. \chk{S1}
\end{example}
\begin{example}[Drift]
For $A=\begin{psmallmatrix}2&1\\1&1\end{psmallmatrix}$ and $x$ the second pure strategy,
$\Q_x(y)=1-(1+q^2)=-q^2<0$ when $y$ plays the first strategy with probability $q>0$. The equilibrium is not
merely not superior; it is inferior to every nearby state. \chk{S4}
\end{example}
\section{Properties}
The source collects five facts \src{Thms.~1--5}. Each is a statement about $\Q$.
\begin{theorem}\label{thm:essprops}
\Scl[Bishop and Cannings 1976; Haigh 1975]
\begin{enumerate}[label=(\alph*)]
\item A game need not have an ESS: Rock--Paper--Scissors has none. \chk{S2}
\item A weakly dominated strategy is not an ESS. \chk{S3}
\item If $x$ is an ESS and $y\ne x$ is a Nash equilibrium, then $\supp y\not\subseteq\supp x$.
\item A game with $n$ strategies has at most $\binom{n}{\lfloor n/2\rfloor}$ ESS.
\item An ESS in the interior of the simplex is the only ESS, and it is globally superior.
\item A quasi-strict equilibrium $x$ is an ESS if and only if $z^{\T}Az<0$ for all $z\ne0$ with
$\supp z\subseteq\supp x$ and $\sum_s z_s=0$.
\end{enumerate}
\end{theorem}
\begin{proof}
(a) By \Cref{cor:uniform} the uniform state $u$ is an equilibrium, and it is the only one. For a pure strategy
$e$, $\pay{u}{e}=0=\pay{e}{e}$ and $\pay{e}{u}=0=\pay{u}{u}$, so both clauses of (i) fail.
(b) If $\mu$ weakly dominates $x$ then $\pay{\mu}{x}\ge\pay{x}{x}$ and $\pay{\mu}{\mu}\ge\pay{x}{\mu}$, so
$\Q_x(\mu)\le0$ with $\mu$ an alternative best reply.
(c) If $\supp y\subseteq\supp x$ then $y$ is a best reply to $x$, since every pure strategy in the support of
$x$ is. The second clause of (i) gives $\pay{x}{y}>\pay{y}{y}$, contradicting that $y$ is an equilibrium.
(d) By (c) the supports of distinct ESS form an antichain of subsets of $S$; apply Sperner's theorem.
(e) If $x$ is interior, every $y$ is a best reply to $x$, so $\Q_x(y)>0$ for all $y\ne x$; then no other state
is an equilibrium by (c).
(f) For $y$ near $x$ write $y-x=z+w$ with $z$ supported in $\supp x$; quasi-strictness makes the first-order
term in $w$ strictly positive, and for $w=0$, $\Q_x(y)=-z^{\T}Az$ because $z^{\T}Ax=0$.
\end{proof}
Criterion (f) is the one used by the companion script to decide evolutionary stability exactly.
\section{Sets, and why they are forced}\label{sec:essets}
A population may be stable as a whole while drifting inside a set of equivalent states. The source surveys
Thomas's evolutionarily stable sets and three variants due to Balkenborg and Schlag \src{\S2.3}. We use the
following form.
\begin{definition}\label{def:esset}
\Scl[Thomas 1985; \cite{Wei95}] A non-empty closed set $L\subseteq\Dist(S)$ is an \term{evolutionarily stable
set} if every $x\in L$ has a neighbourhood $U$ with $\Q_x(y)\ge0$ for all $y\in U$, and $\Q_x(y)>0$ for
$y\in U\setminus L$.
\end{definition}
\noindent A one-point set $\{x\}$ is an evolutionarily stable set exactly when $x$ is an ESS, and every point
of an evolutionarily stable set is a Nash equilibrium.
\begin{theorem}[Stability is a property of sets]\label{thm:esset}
\Sob Let $f\colon(S,A)\to(T,B)$ be a payoff-preserving surjection and let $L\subseteq\Dist(T)$ be an evolutionarily
stable set. Then $f_*^{-1}(L)$ is an evolutionarily stable set of $(S,A)$. If $f$ is not injective and $x$ is
an ESS of $(T,B)$ whose support meets the set of duplicated strategies, then no point of $f_*^{-1}(x)$ is an
ESS.
\end{theorem}
\begin{proof}
By \Cref{prop:push}, $\Q_\sigma(\mu)=\Q_{f_*\sigma}(f_*\mu)$ for all $\sigma,\mu\in\Dist(S)$. Let
$\sigma\in f_*^{-1}(L)$ and let $U$ be the neighbourhood of $f_*\sigma$ from \Cref{def:esset}. Then
$f_*^{-1}(U)$ is a neighbourhood of $\sigma$ on which $\Q_\sigma\ge0$, with strict inequality off
$f_*^{-1}(L)$; and $f_*^{-1}(L)$ is closed and non-empty. For the second statement, the fibre over $x$ contains
a segment through each of its points, on which $\Q_\sigma$ vanishes identically.
\end{proof}
\begin{example}
Duplicate Dove in the Hawk--Dove game. The fibre over the ESS is the segment
$L=\{(p,s,1-p-s)\}$, and $\Q_\sigma(\mu)=\tfrac C2(p-\mu_{\mathrm H})^2$ for $\sigma\in L$: zero exactly on $L$,
positive elsewhere. \chk{S6}
\end{example}
\Cref{thm:esset} explains a development that the source records historically. Duplicating a strategy changes
nothing about the biology or the sociology of a model; it is a change of description. A solution concept
that is destroyed by it cannot be the right concept, and the least repair is to pass from points to sets.
The three variants of Balkenborg and Schlag differ in the order of quantifiers over the neighbourhood (one
threshold for each invader, for each incumbent, or for all) and so in how they behave when $L$ is not compact
in the relevant topology; for the closed sets of \Cref{def:esset} we do not need the distinction.
\section{Relative entropy}
The invasion form has a second life. For $x,y\in\Dist(S)$ with $\supp x\subseteq\supp y$ let
\[ \KL{x}{y}=\sum_{s}x_s\log\frac{x_s}{y_s} \]
be the relative entropy. It is the quantity singled out in \cite{ESCHC}, following Baez and Fritz, as the
unique functorial measure of information lost by a stochastic map. In \Cref{ch:replicator} we shall see that
along the replicator dynamics
\[ \frac{d}{dt}\KL{x}{y(t)}=-\Q_x(y(t)), \]
so that local superiority of $x$ says precisely that relative entropy to $x$ decreases strictly along nearby
trajectories. Evolutionary stability is the statement that a population near $x$ \emph{gains information
about} $x$.
\section*{Notes}
The definition of an ESS is from \cite{MSP73}; the equivalences of \Cref{thm:essequiv} are in \cite{HSS79} and
\cite[Ch.~2]{Wei95}. Parts (c)--(e) of \Cref{thm:essprops} are due to Bishop and Cannings \cite{BiCa76}, part (f)
to Haigh \cite{Hai75}; the sharp maximal number of ESS for given $n$ is a harder problem than the Sperner
bound suggests. Evolutionarily stable sets were introduced by Thomas \cite{Tho85} and refined in
\cite{BaSc01}. The observation that they are the closure of the point concept under duplication of
strategies is, as far as we know, not stated in this form in the literature, though it is implicit in the
treatment of ``clones'' in the literature on stability of sets. The characterization of relative entropy is
in \cite{BaFr14}.
\section*{Exercises}
\begin{exercise}\label{exer:strict}
Show that a strict Nash equilibrium is an ESS, and that in a two-strategy game with $A_{11}\ne A_{21}$ and
$A_{22}\ne A_{12}$ every ESS is either strict or interior.
\end{exercise}
\begin{exercise}\label{exer:rps-ess}
For the generalized Rock--Paper--Scissors game with payoff $a>0$ for a win and $-b<0$ for a loss, show that
the uniform state is an ESS if and only if $a>b$.
\end{exercise}
\begin{exercise}\label{exer:sperner}
Exhibit a game with three strategies and three ESS, attaining the bound of \Cref{thm:essprops}(d).
\end{exercise}
\begin{exercise}\label{exer:fig7}
In the game $\begin{psmallmatrix}1&100\\0&100\end{psmallmatrix}$ of the source's discussion of weak dominance,
compute $\Q_x$ for each pure strategy $x$ and decide which is an ESS.
\end{exercise}
\part{Dynamics}
\chapter{The Replicator Equation}\label{ch:replicator}
\section{Derivation as a quotient}
Let $n_s(t)>0$ be the number of individuals using strategy $s$, and suppose each type grows at a per-capita
rate equal to its payoff against the current population: $\dot n_s=n_s\,f_s(x)$ with $x=n/|n|$, $|n|=\sum_sn_s$,
$f(x)=Ax$. Differentiating $x_s=n_s/|n|$ gives the \term{replicator equation} \cite{TaJo78}
\begin{equation}\label{eq:rep}
\dot x_s=x_s\bigl((Ax)_s-x^{\T}Ax\bigr),\qquad s\in S .
\end{equation}
\begin{proposition}\label{prop:quotient}
\Srf[\cite{HoSi98}] The growth system on the open cone $\R^S_{>0}$ is invariant under the scaling action of
$\R_{>0}$ up to a change of speed along orbits, and \eqref{eq:rep} is the vector field it induces on the
quotient $\R^S_{>0}/\R_{>0}\iso\operatorname{int}\Dist(S)$. The field extends smoothly to the closed simplex.
\end{proposition}
\noindent The source derives \eqref{eq:rep} twice, from births and deaths and from imitation \src{\S3.2.1--3.2.2}. The
first is \Cref{prop:quotient}; the second is \Cref{ch:protocols}. We write $\Rep(S,A)$ for the dynamical system
on $\Dist(S)$ defined by \eqref{eq:rep}, and $\Dyn$ for the category whose objects are compact spaces with a
continuous flow and whose morphisms are continuous maps commuting with the flows.
\section{Naturality}
\begin{theorem}[The replicator equation is a functor]\label{thm:natural}
\Sob If $f\colon(S,A)\to(T,B)$ is payoff-preserving, then $f_*\colon\Dist(S)\to\Dist(T)$ maps solutions of
$\Rep(S,A)$ to solutions of $\Rep(T,B)$. Hence $\Rep\colon\Game\to\Dyn$ is a functor.
\end{theorem}
\begin{proof}
Let $x(t)$ solve \eqref{eq:rep} for $A$ and put $y=f_*x$. By \Cref{prop:push}, $(Ax)_s=(By)_{f(s)}$ and
$x^{\T}Ax=y^{\T}By$. Therefore
\[ \dot y_t=\sum_{f(s)=t}x_s\bigl((Ax)_s-x^{\T}Ax\bigr)=\Bigl(\sum_{f(s)=t}x_s\Bigr)\bigl((By)_t-y^{\T}By\bigr)
=y_t\bigl((By)_t-y^{\T}By\bigr) \]
for $t$ in the image of $f$, and $y_t=0$ identically otherwise, which also solves the equation.
\end{proof}
Three familiar facts are the three generating cases of \Cref{def:map}. \chk{R1}
\begin{corollary}\label{cor:three}
\begin{enumerate}[label=(\alph*)]
\item \emph{Faces are invariant.} For every $S'\subseteq S$ the face $\Dist(S')$ is invariant, and the flow on
it is the replicator flow of the subgame. In particular strategies absent initially stay absent.
\item \emph{Clones lump.} If strategies are duplicated, the total frequency of each class of duplicates
follows the replicator equation of the game without duplicates.
\item \emph{Symmetries act.} The group of symmetries of $(S,A)$ acts on $\Dist(S)$ by automorphisms of the flow;
the fixed-point set of every subgroup is invariant.
\end{enumerate}
\end{corollary}
On the side of payoffs, \eqref{eq:rep} depends only on differences $(Ax)_s-(Ax)_{s'}$, so:
\begin{proposition}\label{prop:shift}
\Scl A column shift does not change the replicator field, and a rescaling $A\mapsto\lambda A$ multiplies it by
$\lambda$. The functor $\Rep$ factors through games modulo column shifts.
\end{proposition}
\section{Two strategies}
By \Cref{prop:shift} a two-strategy game may be taken to be $\begin{psmallmatrix}0&a\\b&0\end{psmallmatrix}$. With
$x$ the frequency of the first strategy, \eqref{eq:rep} reads
\begin{equation}\label{eq:two}
\dot x=x(1-x)\bigl(a-(a+b)x\bigr).
\end{equation}
\begin{center}\small
\begin{tabular}{@{}llll@{}}
\toprule
signs of $(a,b)$ & in the source & rest points & behaviour\\
\midrule
$a>0>b$ or $b>0>a$ & Prisoner's Dilemma & $0,1$ & one strategy wins\\
$a,b>0$ & Hawk--Dove & $0,1,\frac{a}{a+b}$ & interior attracts\\
$a,b<0$ & coordination & $0,1,\frac{a}{a+b}$ & interior repels\\
$a=b=0$ & ``game of life'' & every point & nothing moves\\
\bottomrule
\end{tabular}
\end{center}
\noindent The drift game of \Cref{ch:stability} is the boundary case $a=0>b$:
there $\dot x=x^2(1-x)$ for the invading strategy, and the invader's frequency passes from $x_0$ to $x_1$ in
time
\[ \frac1{x_0}-\frac1{x_1}+\log\frac{x_1(1-x_0)}{x_0(1-x_1)} . \]
An invader that is merely not selected against escapes in time of order $1/x_0$; one that is selected for
escapes in time of order $\log(1/x_0)$. From $x_0=0.05$ to $\tfrac12$ the drift game takes time $20.94$.
\chk{S4}
\section{Geometry: gradients and entropy}
The \term{Shahshahani metric} on the open simplex is $g_x(u,v)=\sum_su_sv_s/x_s$ for tangent vectors $u,v$
(vectors with $\sum_su_s=0$). It is the Fisher information metric of statistics.
\begin{theorem}\label{thm:gradient}
\Scl[Shahshahani 1979; Kimura 1958] If $A$ is symmetric, \eqref{eq:rep} is the gradient flow of
$\tfrac12x^{\T}Ax$ for the Shahshahani metric, and mean payoff increases at the rate
\[ \frac{d}{dt}\,x^{\T}Ax=2\operatorname{Var}_x(Ax)=2\sum_sx_s\bigl((Ax)_s-x^{\T}Ax\bigr)^2 . \]
\end{theorem}
\noindent This is Fisher's fundamental theorem in the form relevant to games in which the two players'
interests coincide. \chk{R2}
\begin{theorem}\label{thm:kl}
\Scl[\cite{HSS79,Zee80}] Along any solution $y(t)$ of \eqref{eq:rep} in the interior of a face containing
$\supp x$,
\[ \frac{d}{dt}\KL{x}{y(t)}=-\Q_x(y(t)). \]
\end{theorem}
\begin{proof}
$\frac{d}{dt}\KL{x}{y}=-\sum_sx_s\dot y_s/y_s=-\sum_sx_s\bigl((Ay)_s-y^{\T}Ay\bigr)=-(\pay{x}{y}-\pay{y}{y})$.
\end{proof}
\begin{corollary}\label{cor:folk3}
\src{Thm.~6.3} An ESS is asymptotically stable; an interior ESS attracts the whole interior of the simplex.
More precisely, if $\Q_x>0$ on $U\setminus\{x\}$, every sublevel set $\{y:\KL{x}{y}\le c\}$ contained in $U$
lies in the basin of attraction of $x$. For Hawk--Dove, $\frac{d}{dt}\KL{x}{y}=-\tfrac C2(p-q)^2$. \chk{R3}
\end{corollary}
\section{The folk theorem and elimination}
\begin{theorem}\label{thm:folk}
\Scl[\cite{HoSi98}; \src{Thm.~6}] (1) Every Nash equilibrium is a rest point of \eqref{eq:rep}. (2) Every
Lyapunov stable rest point is a Nash equilibrium. (3) Every ESS is asymptotically stable. No converse holds.
\end{theorem}
\noindent For (1) see \chk{R7}. A pure state is always a rest point by \Cref{cor:three}(a) and need not be an
equilibrium. For the failure of the converse of (3) the source gives the game
$\begin{psmallmatrix}1&1&1\\0&0&3\\2&1&0\end{psmallmatrix}$: its only equilibrium is the uniform state, which
is asymptotically stable and is not an ESS, since criterion (f) of \Cref{thm:essprops} fails. \chk{R8}
\begin{theorem}[Elimination, with a rate]\label{thm:elim}
\Scl[Akin 1980; \src{Thm.~7}] Suppose the pure strategy $s$ is strictly dominated by $\mu\in\Dist(S)$ with
margin $\delta>0$: $\pay{\mu}{z}-(Az)_s\ge\delta$ for all $z$. Then along every interior solution
\[ x_s(t)\le\frac{x_s(0)}{\prod_{r}x_r(0)^{\mu_r}}\;e^{-\delta t}. \]
\end{theorem}
\begin{proof}
$\frac{d}{dt}\bigl(\log x_s-\sum_r\mu_r\log x_r\bigr)=(Ax)_s-\pay{\mu}{x}\le-\delta$, and
$\prod_rx_r^{\mu_r}\le1$.
\end{proof}
\noindent When $s$ is a twin of another strategy $s'$ with every payoff lowered by $\delta$, the proof gives an
identity: $\log(x_s/x_{s'})$ decreases at the constant rate $\delta$. \chk{R9} The hypothesis that the solution be
interior is the source's proviso that all strategies be initially present, and by \Cref{cor:three}(a) it
cannot be dropped.
\section{Cycles}
\begin{theorem}\label{thm:zerosum}
\Scl[\cite{HoSi98}] Let $A$ be antisymmetric with an interior equilibrium $x^*$. Then $\KL{x^*}{y}$ is constant
along every interior solution of \eqref{eq:rep}. No interior solution converges to $x^*$ or to the boundary.
\end{theorem}
\begin{proof}
$y^{\T}Ay=0$ and $x^{*\T}Ay=-y^{\T}Ax^*=0$, so $\Q_{x^*}\equiv0$; apply \Cref{thm:kl}.
\end{proof}
For Rock--Paper--Scissors this gives the family of closed orbits around the centre. \chk{R4}
\begin{proposition}[Generalized Rock--Paper--Scissors]\label{prop:grps}
\Scl[\cite{Zee80}] Let a win pay $a>0$ and a loss $-b<0$. The linearization of \eqref{eq:rep} at the uniform
state has eigenvalues
\[ \lambda_\pm=\frac{b-a}{6}\pm i\,\frac{\sqrt3\,(a+b)}{6}. \]
The centre is asymptotically stable and an ESS for $a>b$, a centre for $a=b$, and a repeller for $a<b$, when
interior orbits approach the boundary. \chk{R5, R6}
\end{proposition}
\noindent The cases $a>b$ and $a<b$ are the source's ``good'' and ``bad'' versions. By \Cref{cor:three}(c) the
uniform state is a rest point for every $a,b$, being the fixed point of the $\Z/3$ of symmetries. For three
strategies the possible phase portraits were classified by Zeeman and by Bomze \cite{Zee80,Bom83}; they are
assembled from rest points and cycles. With four strategies the state space is three-dimensional and
chaotic attractors occur \cite{ASS80}; the source illustrates one \src{\S3.2.5}. Two statements survive chaos.
\begin{theorem}\label{thm:average}
\Scl[\cite{HoSi98}] If a solution of \eqref{eq:rep} stays at a positive distance from the boundary, then every
limit point of its time averages $\frac1T\int_0^Tx(t)\,dt$ is an interior equilibrium. If the interior
equilibrium is unique, the time averages converge to it.
\end{theorem}
\noindent The second surviving statement is the index theorem of the next chapter.
\section*{Notes}
The replicator equation was introduced in \cite{TaJo78} and named in \cite{ScSi83}. The standard reference is
\cite{HoSi98}; \cite{San10} treats it within a general theory of population dynamics. \Cref{thm:gradient} is in
\cite{Sha79,Aki79}. The functorial statement \Cref{thm:natural} is elementary and its three cases are
classical; we have not found it stated as a single naturality property. Relative entropy as a Lyapunov
function, and the reading of the replicator equation as an information-geometric flow, are developed in
\cite{BaPo16,Har09}. The equivalence of the replicator equation on $n$ strategies with a Lotka--Volterra
system in $n-1$ variables is due to Hofbauer \cite{Hof81}.
\section*{Exercises}
\begin{exercise}\label{exer:two}
Derive \eqref{eq:two} and the escape-time formula for the drift game.
\end{exercise}
\begin{exercise}\label{exer:fisher}
Prove the formula for $\frac{d}{dt}x^{\T}Ax$ in \Cref{thm:gradient}, and show that for general $A$ the rate is
$2\operatorname{Cov}_x(Sx,Ax)$, where $S=\tfrac12(A+A^{\T})$.
\end{exercise}
\begin{exercise}\label{exer:eig}
Verify \Cref{prop:grps} by computing the trace and determinant of the linearization on the tangent space.
\end{exercise}
\begin{exercise}\label{exer:lump}
A population plays Rock--Paper--Scissors with Rock present in two indistinguishable variants, in initial
state $(\tfrac14,\tfrac14,\tfrac14,\tfrac14)$. Describe the motion of the class frequencies.
\end{exercise}
\chapter{Index, Recurrence, and Decomposition}\label{ch:index}
Three questions cannot be answered one equilibrium at a time. How many equilibria can there be, and of what
kinds? What replaces an equilibrium when the dynamics cycles? Which part of a game is responsible for the
cycling? Each has an answer in which topology does the work.
\section{The index theorem}
Write $F_A$ for the replicator field. At a rest point $x$ its derivative preserves the tangent space
$T=\{v:\sum_sv_s=0\}$ of the simplex.
\begin{definition}
A game is \term{regular} if every Nash equilibrium is quasi-strict and $D_xF_A|_T$ is invertible at each. The
\term{index} of a Nash equilibrium $x$ of a regular game is
\[ \operatorname{ind}(x)=\operatorname{sign}\det\bigl(-D_xF_A|_T\bigr)\in\{+1,-1\}. \]
\end{definition}
\noindent Regular games are open and dense among all games. An equilibrium at which every eigenvalue of
$D_xF_A|_T$ has negative real part has index $+1$.
\begin{theorem}[Index theorem]\label{thm:index}
\Scl[Hofbauer and Sigmund; Poincar\'e--Hopf] For a regular game,
\[ \sum_{x\ \mathrm{Nash}}\operatorname{ind}(x)=1 . \]
\end{theorem}
\begin{proof}[Sketch]
For small $\epsilon>0$ the field $F_A(x)+\epsilon(u-x)$, with $u$ the uniform state, points strictly inward
on the boundary of the simplex. Its rest points converge, as $\epsilon\to0$, to the rest points of $F_A$ that
are \emph{saturated}, that is, to the Nash equilibria: a rest point with a strategy outside its support that
earns more than average is pushed out of the simplex and disappears. Regularity makes the correspondence a
bijection that preserves the sign of the determinant. The negative of an inward-pointing field points outward,
and by the Poincar\'e--Hopf theorem the sum of the indices of its zeros is the Euler characteristic of the
simplex, which is $1$ because the simplex is contractible; see \DT{Ch.~7} for the three descriptions of
the Euler characteristic used here.
\end{proof}
The theorem is checked on four hundred random games with three and four strategies. \chk{I1}
\begin{corollary}\label{cor:index}
In a regular game: (a) the number of Nash equilibria is odd; (b) every ESS has index $+1$ \chk{I2}; (c) if
there are $k$ equilibria of index $+1$ there are exactly $k-1$ of index $-1$; in particular two ESS force a
third equilibrium, which is not stable. \chk{I3}
\end{corollary}
\noindent In the coordination game $\begin{psmallmatrix}2&0\\0&1\end{psmallmatrix}$ the two conventions have
index $+1$ and the mixed equilibrium, which separates their basins, has index $-1$. The index theorem is the
reason a model with two stable conventions always has a threshold between them. It holds whatever the
dynamics does elsewhere, cycles and chaos included.
\section{Recurrence and the Conley index}
When trajectories do not converge, the object that plays the part of an equilibrium is a recurrent set.
\begin{definition}
For a flow $\varphi$ on a compact metric space, an \term{$(\epsilon,\tau)$-chain} from $x$ to $y$ is a
sequence $x=x_0,\dots,x_k=y$ with times $t_i\ge\tau$ such that $d(\varphi_{t_i}(x_i),x_{i+1})<\epsilon$. A point
is \term{chain recurrent} if for all $\epsilon,\tau$ there is a chain from it to itself; two chain recurrent
points are equivalent if chains run both ways. The classes are the \term{chain components}.
\end{definition}
\begin{theorem}[Conley's decomposition]\label{thm:conley}
\Scl[Conley 1978] Every flow on a compact metric space has a continuous function that is strictly decreasing
along orbits off the chain recurrent set and constant on each chain component. The flow is gradient-like
between chain components.
\end{theorem}
Chain components generalize equilibria in exactly the way the source's examples require.
\begin{example}\label{ex:chains}
For the Prisoner's Dilemma the chain components are the two pure states, and All-Defect is the only one that
attracts. For a coordination game there are three. For Rock--Paper--Scissors with $a=b$ every state is chain
recurrent and the whole simplex is a single chain component: arbitrarily small errors carry the population
from any closed orbit to any other, and to the boundary. For $a<b$ the chain components are the centre and
the boundary cycle, and the boundary cycle attracts.
\end{example}
Papadimitriou and Piliouras propose the chain components of a learning dynamic, and the sink components
among them, as what a game ``means'' when equilibria do not predict behaviour \cite{PaPi19}.
To each isolated invariant set Conley attaches more than a number.
\begin{definition}
An \term{index pair} for an isolated invariant set $K$ is a pair of compact sets $L\subseteq N$ such that $K$ is
the largest invariant set in $N\setminus L$, $L$ is positively invariant in $N$, and orbits leave $N$ only
through $L$. The \term{Conley index} of $K$ is the pointed homotopy type $h(K)=[N/L]$.
\end{definition}
\begin{theorem}\label{thm:conleyindex}
\Scl[Conley 1978; \cite{Sal85}] The Conley index does not depend on the index pair. It is invariant under
continuation: if a family of flows has a common isolating neighbourhood, the index is constant along the
family. A hyperbolic rest point with $k$ unstable directions has index the pointed sphere $S^k$; an attracting
closed orbit has the index of a circle with a disjoint base point, whose reduced homology has rank one in
degrees $0$ and $1$. If $h(K)$ is not the homotopy type of a point, $K$ is non-empty.
\end{theorem}
\begin{remark}[What is higher here]\label{rem:higher}
The index of \Cref{thm:index} is the Euler characteristic of the Conley index: an equilibrium with $k$
unstable directions contributes $(-1)^k$. The Conley index remembers $k$, and for recurrent sets it remembers a
homotopy type that no count recovers. Continuation invariance is the precise sense in which a qualitative
conclusion drawn from a model survives perturbation of its payoffs: as long as an attractor stays isolated,
its index, and hence its existence, persists. An ESS has index $S^0$ and persists under small changes of the
game; the family of cycles of Rock--Paper--Scissors at $a=b$ is not isolated and does not.
\end{remark}
For computation one discretizes. The \term{invasion graph} of a game has the pure strategies as vertices and
an edge $i\to j$ when $A_{ji}>A_{ii}$, that is, when $j$ invades a population of $i$. Its sink strongly connected
components are a finite shadow of the attracting chain components. \chk{I7} The Markov--Conley chains of
$\alpha$-Rank \cite{OPP19} are random walks on such graphs, weighted by fixation probabilities; we return to
them in \Cref{ch:finite}.
\section{Decomposition}
Every matrix splits as $A=S+K$ with $S=\tfrac12(A+A^{\T})$ symmetric and $K=\tfrac12(A-A^{\T})$ antisymmetric: a
game of common interest plus a zero-sum game. By \Cref{thm:gradient,thm:zerosum} the replicator field is the
sum of a gradient field and a field that, when $K$ has an interior equilibrium, conserves a relative
entropy. Mean payoff obeys $\frac{d}{dt}x^{\T}Ax=2\operatorname{Cov}_x(Sx,Ax)$. \chk{I6}
The antisymmetric part decomposes further, and here the statement is cohomological. Regard an antisymmetric
matrix $K$ as a $1$-cochain on the complete graph with vertex set $S$: $K_{ij}$ is the advantage of $i$ over
$j$.
\begin{theorem}[Hodge decomposition of a zero-sum game]\label{thm:hodge}
\Sli[\cite{JLYY11,CMOP11}] Every antisymmetric $K$ decomposes uniquely as
\[ K_{ij}=(r_i-r_j)+C_{ij},\qquad r_i=\tfrac1n\textstyle\sum_jK_{ij},\qquad\textstyle\sum_jC_{ij}=0\ \text{ for all } i . \]
The two parts are orthogonal for the Frobenius inner product. The gradient part satisfies the cocycle condition
$G_{ij}+G_{jk}+G_{ki}=0$ on every triangle, and conversely every antisymmetric matrix satisfying it is a gradient.
The cyclic part $C$ has the same curl $K_{ij}+K_{jk}+K_{ki}$ as $K$ on every triangle.
\end{theorem}
\noindent The converse statement is the vanishing of the first cohomology of the full simplex on $S$: a
closed cochain is exact. \chk{I4, I5} We call $\tau(K)=\|G\|^2/\|K\|^2\in[0,1]$ the \term{transitivity index}.
Rock--Paper--Scissors has $\tau=0$ and curl $\pm3$; a game of pure rating differences has $\tau=1$; a random
antisymmetric game on five strategies had $\tau=0.56$.
\begin{remark}
If only some pairs of strategies are ever compared, the complete graph is replaced by a comparison graph
with its triangles, and its first cohomology need not vanish. A third, \emph{harmonic}, component appears:
cyclic advantage around a loop that bounds no triangle, locally consistent and globally not a rating. This
is the only place in the volume where a cohomology group is not zero for a trivial reason.
\end{remark}
\section*{Notes}
The index theorem for the replicator equation is in \cite[Ch.~13]{HoSi98}; the perturbation argument is
Hofbauer's. Conley's theory is in \cite{Con78}, with an accessible account of the index in \cite{Sal85}. Chain
recurrence as a solution concept for games is argued in \cite{PaPi19}. The Hodge decomposition of pairwise
comparison data is from \cite{JLYY11}; its game-theoretic form for general finite games, into potential,
harmonic and non-strategic parts, is from \cite{CMOP11}; the use of the transitive and cyclic parts in the
evaluation of agents is from \cite{BTP18}.
\section*{Exercises}
\begin{exercise}\label{exer:index2}
Compute the index of each equilibrium of the three generic classes of two-strategy games in the table of
\Cref{ch:replicator}, and verify \Cref{thm:index}.
\end{exercise}
\begin{exercise}\label{exer:curl}
Show that an antisymmetric $K$ is a gradient if and only if its curl vanishes on all triangles through one
fixed vertex.
\end{exercise}
\begin{exercise}\label{exer:tau}
Compute the Hodge decomposition and the transitivity index of the antisymmetric game on three strategies
with $K_{12}=1$, $K_{23}=1$, $K_{13}=t$, as a function of $t$.
\end{exercise}
\begin{exercise}\label{exer:invgraph}
Determine the invasion graph and its sink components for the Hawk--Dove game with $V<C$. What do they miss?
\end{exercise}
\chapter{Revision Protocols, Other Dynamics, and Open Systems}\label{ch:protocols}
The replicator equation is one dynamic among many. The source derives it a second time from imitation,
introduces two rivals, and reports a theorem that separates them \src{\S3.2.2, \S3.3}. This chapter places all
three in one frame and then takes the frame apart into components.
\section{Revision protocols}
A \term{population game} is a continuous map $F\colon\Dist(S)\to\R^S$; the linear case $F(x)=Ax$ is the
symmetric game $(S,A)$. Following Sandholm \cite{San10}, a \term{revision protocol} is a continuous map
\[ \rho\colon\R^S\times\Dist(S)\longrightarrow\R_{\ge0}^{S\times S}, \]
where $\rho_{ij}(\pi,x)$ is the rate at which a player of strategy $i$ switches to $j$ when payoffs are $\pi$ and
the state is $x$; the \term{mean dynamic} it induces is
\begin{equation}\label{eq:mean}
\dot x_i=\sum_jx_j\,\rho_{ji}(F(x),x)-x_i\sum_j\rho_{ij}(F(x),x).
\end{equation}
\begin{remark}\label{rem:nonlinear}
\Srf[\cite{San10}] For a fixed population state the matrix $\rho$ is the rate matrix of a continuous-time
Markov chain on $S$, and \eqref{eq:mean} is its forward equation $\dot x=xL$. A revision protocol is thus a
map from states to generators, $x\mapsto L(x)$, and the mean dynamic is $\dot x=x\,L(x)$: a Markov chain whose
transition rates depend on its own law. The chain describes one agent; the equation describes the
population. This is the sense in which the continuous models of the source are limits of the finite ones of
\Cref{ch:finite}.
\end{remark}
\begin{proposition}[Imitation gives the replicator equation]\label{prop:ppi}
\Scl[\cite{Sch98,San10}] Under \emph{pairwise proportional imitation}, $\rho_{ij}=x_j[\pi_j-\pi_i]_+$, the mean
dynamic is the replicator equation. \chk{O1}
\end{proposition}
\begin{proof}
$\dot x_i=x_i\sum_jx_j\bigl([\pi_i-\pi_j]_+-[\pi_j-\pi_i]_+\bigr)=x_i\sum_jx_j(\pi_i-\pi_j)=x_i(\pi_i-\bar\pi)$.
\end{proof}
\noindent The factor $x_j$ is the probability of meeting a $j$-player; the agent needs to know nothing about
the game except what it and the player it meets have earned. Two rivals, the Brown--von Neumann--Nash (BNN) dynamic and the Smith dynamic, dispense with the meeting.
\begin{center}\small
\begin{tabular}{@{}lll@{}}
\toprule
dynamic & protocol $\rho_{ij}$ & mean dynamic $\dot x_i$\\
\midrule
replicator & $x_j[\pi_j-\pi_i]_+$ & $x_i(\pi_i-\bar\pi)$\\
BNN & $[\pi_j-\bar\pi]_+=:k_j$ & $k_i-x_i\sum_jk_j$\\
Smith & $[\pi_j-\pi_i]_+$ & $\sum_j\bigl(x_j[\pi_i-\pi_j]_+-x_i[\pi_j-\pi_i]_+\bigr)$\\
\bottomrule
\end{tabular}
\end{center}
\section{Imitation is natural and innovation is not}
Hofbauer and Sandholm isolate four properties of a dynamic $\dot x=V_F(x)$ \cite{HoSa11}; the source
states them as the hypotheses of its Theorem~8. \emph{Continuity}: $V_F$ depends continuously on $F$.
\emph{Positive correlation}: $V_F(x)\cdot F(x)>0$ whenever $V_F(x)\ne0$. \emph{Nash stationarity}: $V_F(x)=0$
exactly at Nash equilibria. \emph{Innovation}: if $x$ is not a Nash equilibrium and an unused strategy is a
best reply to $x$, that strategy grows.
\begin{center}\small
\begin{tabular}{@{}lcccc@{}}
\toprule
& continuity & pos.\ correlation & Nash stationarity & innovation\\
\midrule
replicator & yes & yes & no & no\\
BNN & yes & yes & yes & yes\\
Smith & yes & yes & yes & yes\\
\bottomrule
\end{tabular}
\end{center}
\noindent At All-Cooperate in the Prisoner's Dilemma the replicator field vanishes and the other two do
not \chk{O2}; at every Nash equilibrium of sixty random games both of the others vanish. \chk{O3}
\begin{theorem}[Hofbauer--Sandholm]\label{thm:hs}
\Sli[\cite{HoSa11}; source, Theorem 8] For every dynamic satisfying the four properties there is a game with a
strictly dominated strategy that survives along solutions from most initial conditions.
\end{theorem}
\noindent The example has the same shape for every such dynamic: a game with a cycle, and a twin of one
strategy made slightly worse. In bad Rock--Paper--Scissors (win $1$, loss $2$) with a twin of Scissors that earns
$0.1$ less, the twin's time-averaged share under the Smith dynamic is $0.116$; under the replicator equation
it is zero, and \Cref{thm:elim} gives the rate. \chk{O4}
The functor of \Cref{ch:replicator} explains the difference.
\begin{proposition}[Names and individuals]\label{prop:names}
\Sob
\begin{enumerate}[label=(\alph*)]
\item Every imitative protocol $\rho_{ij}=x_j\,r(\pi_i,\pi_j)$ has a mean dynamic that is natural for all
payoff-preserving maps: faces are invariant and clones lump, exactly as in \Cref{cor:three}.
\item A dynamic that is natural for subgame inclusions leaves every face invariant, so every pure state is a
rest point. In any game with a pure state that is not a Nash equilibrium it violates Nash stationarity and
Innovation.
\item The Brown--von Neumann--Nash and Smith dynamics are natural for symmetries and for neither of the other
two generating cases of \Cref{def:map}: an absent strategy can appear, and duplicating a strategy changes the
motion of the class totals. \chk{O7}
\end{enumerate}
\end{proposition}
\begin{proof}
(a) The mean dynamic is $\dot x_i=x_i\sum_jx_j\bigl(r(\pi_j,\pi_i)-r(\pi_i,\pi_j)\bigr)$. The factor $x_i$ gives
invariance of faces, and the sum depends on $x$ only through the distribution of payoffs, which is unchanged
when clones are merged. (b) is immediate from the definitions. (c) In both protocols the inflow into strategy
$i$ does not carry the factor $x_i$. A strategy with two names receives the inflow twice: for
Rock--Paper--Scissors with Rock duplicated the discrepancy between the pushed-forward field and the field of
the quotient game reached $0.56$ for Smith and $0.38$ for Brown--von Neumann--Nash over fifty random states.
\end{proof}
\begin{remark}
Imitation counts individuals; a direct protocol counts names. Under imitation a strategy is as visible as it
is common, so a twin of a strategy that exists is invisible as a separate thing, and a dominated twin dies at
the rate of its penalty. Under a direct protocol every name is a candidate at every moment whatever its
frequency, so a twin is a second target for switching, and it is replenished each time the cycle makes it
nearly optimal. \Cref{thm:hs} is the price of Nash stationarity: one cannot have both the invariance of
\Cref{thm:natural} and rest points that are exactly the Nash equilibria.
\end{remark}
\section{Populations as open systems}
In \eqref{eq:rep} the game and the learning rule are fused. They can be separated.
\begin{definition}
A \term{population box} on $S$ is an open dynamical system with input a payoff vector $\pi\in\R^S$, state
$x\in\Dist(S)$, output the state, and dynamics $\dot x=V(x,\pi)$. The \term{replicator box} has
$V_i=x_i(\pi_i-x\cdot\pi)$.
\end{definition}
\begin{proposition}[The replicator box integrates and normalizes]\label{prop:softmax}
\Scl For any integrable input $\pi(\cdot)$ and interior initial state, the replicator box has the solution
\[ x(t)=\operatorname{softmax}\Bigl(\log x(0)+\int_0^t\pi(\tau)\,d\tau\Bigr). \]
In the coordinates $z=\log x$ modulo constants the box is the integrator $\dot z=\pi$. \chk{O6}
\end{proposition}
\noindent All the nonlinearity of the replicator equation is in the game and in the readout, the map
$\operatorname{softmax}$ from $\R^S/\R\one$ onto the open simplex; the box itself is linear. The Lyapunov function of \Cref{thm:kl} is
the Bregman divergence of the convex function whose gradient is this readout.
A game is then a way of closing boxes.
\begin{center}
\begin{tikzpicture}[>=stealth,scale=0.95,every node/.style={font=\small}]
\node[draw,thick,minimum width=1.9cm,minimum height=0.9cm] (p) at (0,0) {population};
\node[draw,minimum width=1cm,minimum height=0.7cm] (a) at (0,-1.5) {$A$};
\draw[->] (p.east) -- ++(0.8,0) |- node[pos=0.25,right]{$x$} (a.east);
\draw[->] (a.west) -- ++(-1.25,0) |- node[pos=0.25,left]{$\pi=Ax$} (p.west);
\node at (0,-2.4) {one population};
\begin{scope}[xshift=6.3cm]
\node[draw,thick,minimum width=1.5cm,minimum height=0.9cm] (r) at (-1.6,0) {row};
\node[draw,thick,minimum width=1.5cm,minimum height=0.9cm] (c) at (1.6,0) {column};
\node[draw,minimum width=0.9cm,minimum height=0.7cm] (a2) at (0,0.75) {$B^{\T}$};
\node[draw,minimum width=0.9cm,minimum height=0.7cm] (b2) at (0,-0.75) {$A$};
\draw[->] (r.north) |- node[pos=0.25,left]{$x$} (a2.west);
\draw[->] (a2.east) -| (c.north);
\draw[->] (c.south) |- node[pos=0.25,right]{$y$} (b2.east);
\draw[->] (b2.west) -| (r.south);
\node at (0,-2.4) {two populations};
\end{scope}
\end{tikzpicture}
\end{center}
\begin{remark}\label{rem:wiring}
\Srf[\cite{SSV20,Mye21}] Open dynamical systems are the algebras of an operad of wiring diagrams: a diagram
with boxes of given interfaces determines a closed system once each box is filled. A symmetric game is the
one-box diagram with feedback through $A$; a bimatrix game is the two-box diagram; a local-interaction model
(\Cref{ch:local}) has one box per vertex of a graph. Replacing the replicator box by a
Smith box changes the dynamics and not the diagram. The statement that the source's models differ ``only in
the dynamics'' or ``only in the interaction structure'' is the statement that a model is a pair of a diagram
and a filling.
\end{remark}
\section{Two populations}
For a bimatrix game $(A,B)$ the two-box system with replicator boxes is
\[ \dot x_i=x_i\bigl((Ay)_i-x^{\T}Ay\bigr),\qquad\dot y_j=y_j\bigl((B^{\T}x)_j-y^{\T}B^{\T}x\bigr) \]
on $\Dist(S)\times\Dist(T)$. The single-population equation for $A$ is its restriction to the diagonal in the case
$B=A^{\T}$: the diagonal is the fixed set of the symmetry exchanging the two boxes.
\begin{theorem}\label{thm:selten}
\Scl[\cite{Sel80,RiWe95,HoSi98}] In the two-population replicator dynamics a rest point is asymptotically stable if and
only if it is a strict Nash equilibrium. In particular no mixed equilibrium is asymptotically stable.
\end{theorem}
\noindent After a change of velocity the flow in the interior preserves volume, which excludes interior
attractors. For the source's Battle of the Sexes, with payoffs $A=\begin{psmallmatrix}2&0\\0&1\end{psmallmatrix}$ to
Row and $B=\begin{psmallmatrix}1&0\\0&2\end{psmallmatrix}$ to Column, the mixed equilibrium $(x,y)=(\tfrac23,\tfrac13)$
is a saddle with eigenvalues $\pm\tfrac23$, and orbits started near it end at one of the two pure
equilibria. \chk{O5} The population model selects conventions and never the mixed equilibrium, which is the
content of the source's discussion \src{\S3.4}.
\section*{Notes}
Revision protocols and mean dynamics are developed systematically in \cite{San10}; proportional imitation
is due to Schlag \cite{Sch98} and, in a different form, to Bj\"ornerstedt and Weibull \cite{BjWe96}. The
Brown--von Neumann--Nash dynamic is from \cite{BvN50} and the Smith dynamic from \cite{Smi84}. Elimination of
dominated strategies under imitative dynamics is in \cite{Nac90,SaZh92}. For open dynamical systems and
wiring diagrams see \cite{SSV20,Mye21}; for games assembled compositionally from open pieces, \cite{GHWZ18}
and \cite{GIHC}.
\section*{Exercises}
\begin{exercise}\label{exer:dissat}
Show that \emph{imitation driven by dissatisfaction}, $\rho_{ij}=x_j(K-\pi_i)$ with $K$ larger than every payoff,
also has the replicator equation as its mean dynamic.
\end{exercise}
\begin{exercise}\label{exer:bnnrest}
Show directly that the rest points of the Brown--von Neumann--Nash dynamic are exactly the Nash equilibria.
\end{exercise}
\begin{exercise}\label{exer:softmax}
Prove \Cref{prop:softmax}.
\end{exercise}
\begin{exercise}\label{exer:bos}
Write the two-population replicator equations for the Battle of the Sexes above in the coordinates $(x,y)$,
and verify the eigenvalues $\pm\tfrac23$ at the mixed equilibrium.
\end{exercise}
\part{Structure}
\chapter{Finite Populations}\label{ch:finite}
A real population is finite, and in a finite population chance decides what the differential equation leaves
open. The source's model is the frequency-dependent birth--death process \src{\S4.1}. Its analysis is
classical, and we shall say plainly at the end how little the categorical language adds to it. What it does
add is a precise statement of the one point at which the source draws a conclusion that needs qualifying.
\section{The Moran process}
Two strategies $A$ and $B$ have payoffs $\begin{psmallmatrix}a&b\\c&d\end{psmallmatrix}$, all positive. In a population
of $N$ with $i$ players of type $A$, the expected payoffs against a randomly chosen other player are
\[ F_i=\frac{a(i-1)+b(N-i)}{N-1},\qquad G_i=\frac{c\,i+d(N-i-1)}{N-1}, \]
and the fitnesses are $f_i=1-w+wF_i$, $g_i=1-w+wG_i$ for an intensity of selection $w\in(0,1]$. At each step one
individual is chosen to reproduce with probability proportional to fitness, and its offspring replaces a
uniformly chosen individual. The number of $A$-players is a Markov chain on $\{0,\dots,N\}$, that is, an
endomorphism in $\FinStoch$, with
\[ p_i^+=\frac{if_i}{if_i+(N-i)g_i}\cdot\frac{N-i}{N},\qquad p_i^-=\frac{(N-i)g_i}{if_i+(N-i)g_i}\cdot\frac iN, \]
and $0$ and $N$ absorbing.
\begin{theorem}[Fixation]\label{thm:fix}
\Scl[\cite{Mor58,Now06}] The probability that a single $A$-player takes over the population is
\[ \rho_A=\Bigl(1+\sum_{k=1}^{N-1}\prod_{i=1}^{k}\frac{g_i}{f_i}\Bigr)^{-1}. \]
\end{theorem}
\begin{proof}
The probability $h_i$ of absorption at $N$ from $i$ is the harmonic function with $h_0=0$, $h_N=1$. Harmonicity
gives $h_{i+1}-h_i=(p_i^-/p_i^+)(h_i-h_{i-1})=(g_i/f_i)(h_i-h_{i-1})$, and the differences telescope.
\end{proof}
\noindent For constant fitness $r$ of the mutant relative to the resident this is $\rho=(1-r^{-1})/(1-r^{-N})$, and
$\rho=1/N$ in the neutral case. \chk{F3}
The source tabulates the fixation probability $\rho_B$ of a single defector in the Prisoner's Dilemma
$a=3$, $b=1$, $c=4$, $d=2$ with $w=1$. The formula above, with self-interaction excluded as in the
definition of $F_i$ and $G_i$, reproduces the table; if a player may meet itself the values differ in the
second decimal place at $N=10$ and have the same limit. \chk{F1}
\begin{center}
\begin{tabular}{@{}lccccc@{}}
\toprule
$N$ & $10$ & $10^2$ & $10^3$ & $10^4$ & $10^5$\\
\midrule
source & $0.34263$ & $0.25879$ & $0.25088$ & $0.25009$ & $0.25001$\\
computed, no self-play & $0.34263$ & $0.25879$ & $0.25088$ & $0.25009$ & not run\\
computed, self-play & $0.30163$ & $0.25500$ & $0.25050$ & $0.25005$ & not run\\
\bottomrule
\end{tabular}
\end{center}
\begin{proposition}[The limit]\label{prop:limit}
\Scl If $B$ strictly dominates $A$ ($c>a$ and $d>b$) and $w=1$, then $\rho_B\to1-a/c$ as $N\to\infty$.
\end{proposition}
\begin{proof}
For $\rho_B$ the ratios in \Cref{thm:fix} are those of resident to mutant fitness. With $j$ mutants and
$N\to\infty$ the $j$-th ratio tends to $a/c$, and by dominance all ratios are bounded by some $\theta<1$ for
large $N$, uniformly in the composition. Dominated convergence gives
$\rho_B^{-1}\to\sum_{k\ge0}(a/c)^k=(1-a/c)^{-1}$.
\end{proof}
\noindent With $a=3$ and $c=4$ the limit is $\tfrac14$. \chk{F2} The number $1-a/c$ is the survival probability
of a branching process in which each mutant has relative fitness $c/a$: while mutants are rare they meet only
residents, and their lineage either dies out early or escapes.
\section{Two limits that do not commute}
The source concludes from $\rho_B\to\tfrac14$ that ``the replicator dynamics cannot be the limit of the
birth-death process'', since under the replicator dynamics any positive fraction of defectors takes over with
certainty \src{\S4.1}. The observation is correct. The conclusion holds for one order of limits and fails for
the other.
\begin{theorem}[Mean-field limit]\label{thm:kurtz}
\Scl[\cite{Kur70,TCH05}] Fix an initial \emph{fraction} $x_0\in(0,1)$ and a time horizon $T$, measured in
generations of $N$ steps. As $N\to\infty$ the frequency of $A$ in the Moran process converges in probability,
uniformly on $[0,T]$, to the solution of the \emph{adjusted replicator equation}
\[ \dot x=\frac{x(1-x)\bigl(F(x)-G(x)\bigr)}{xF(x)+(1-x)G(x)}, \]
with fluctuations of order $N^{-1/2}$.
\end{theorem}
\noindent The adjusted equation has the same orbits as \eqref{eq:two} and a different clock. For a Hawk--Dove
game with background fitness the root-mean-square deviation from the solution at $T=4$ was $0.158$, $0.084$
and $0.040$ at $N=50$, $200$ and $800$: it halves when $N$ is quadrupled. \chk{F5}
\begin{remark}[Which limit]\label{rem:limits}
\Sob Write $\Phi_N(x_0,t)$ for the law of the frequency at generation $t$ from initial fraction $x_0$. The
replicator dynamics is the limit $N\to\infty$ with $x_0$ and $t$ fixed. Fixation of a single mutant is the limit
$t\to\infty$ first, at $x_0=1/N$, and then $N\to\infty$; here the initial fraction tends to zero, the limiting
differential equation starts at the rest point $x=0$ and never leaves, and the outcome is decided in a boundary
layer of width $O(1/N)$ where the population is a branching process and not a flow. The two descriptions
compose: a defector lineage escapes the layer with probability $1-a/c$ and, having escaped, is carried to
fixation by the flow with probability tending to one. The square
\[ \begin{tikzcd}[column sep=large]
\Phi_N(x_0,t)\ar[r,"N\to\infty"]\ar[d,"t\to\infty"'] & \varphi_t(x_0)\ar[d,"t\to\infty"]\\
\text{fixation law}\ar[r,"N\to\infty"'] & \text{?}
\end{tikzcd} \]
commutes for each fixed $x_0>0$ in the Prisoner's Dilemma and fails along $x_0=1/N$. The replicator dynamics
is a limit of the birth--death process, and it is not the limit that computes invasion from one mutant.
\end{remark}
\section{Weak selection}
\begin{theorem}[The one-third law]\label{thm:third}
\Sli[\cite{NSTF04}] For $w\to0$, selection favours the fixation of $A$, in the sense $\rho_A>1/N$, if and only if
\[ a(N-2)+b(2N-1)>c(N+1)+d(2N-4). \]
For a coordination game ($a>c$, $d>b$) and large $N$ this holds if and only if the unstable equilibrium
$x^*=(d-b)/(a-c+d-b)$ of the replicator equation, the frequency of $A$ at the barrier between the two
conventions, is below $\tfrac13$.
\end{theorem}
\noindent The condition was confirmed against exact fixation probabilities in 299 random coordination games
at $N=60$. \chk{F4} The constant has a simple origin: to first order in $w$ the advantage $h(x)=F-G$ is
weighted by the number of visits that a neutral lineage started from one mutant pays to frequency $x$, which
is proportional to $1-x$, and $\int_0^1(\alpha x-\beta)\,2(1-x)\,dx=\alpha/3-\beta$. A convention can thus be invaded by a single
mutant, with probability above the neutral one, exactly when its basin under the deterministic dynamics is
smaller than a third; the replicator equation alone says only that it cannot be invaded at all.
\section{Rare mutations}
Add mutation at a small rate $\mu$. The chain becomes ergodic, and as $\mu\to0$ its stationary distribution
concentrates on the monomorphic states, where it is the stationary distribution of the \emph{embedded chain}
that jumps from all-$i$ to all-$j$ with probability proportional to the fixation probability $\rho_{i\to j}$
of a single $j$-mutant \cite{FuIm06}. For large populations and strong selection this chain moves only along the
edges of the invasion graph of \Cref{ch:index} and its stationary distribution is carried by the sink
components: all of Rock--Paper--Scissors, either convention of a coordination game, defection in the Prisoner's
Dilemma. \chk{I7} This is the finite-population counterpart of the chain components of \Cref{thm:conley}, and
it is the construction used to rank learning agents by Markov--Conley chains \cite{OPP19}. Stochastic
stability in the sense of \cite{KMR93,You93} is the same idea for best-reply dynamics, where the selected
convention is the risk-dominant one.
\begin{remark}[What the language adds here]
Not much. A finite-population model is a morphism in $\FinStoch$; fixation is a harmonic function; the
embedded chain is a functor from games to Markov chains that is natural for symmetries and, like the direct
protocols of \Cref{prop:names}, not for cloning (an example is computed in the companion paper \cite{EGML}). The content of the chapter is analytic, and the one structural
point is \Cref{rem:limits}.
\end{remark}
\section*{Notes}
The frequency-dependent Moran process and its fixation probabilities are in \cite{NSTF04,Now06}; the original
process is Moran's \cite{Mor58}. Density-dependent Markov chains and their differential-equation limits are due
to Kurtz \cite{Kur70}; the identification of the limit of the Moran process with the adjusted replicator
equation is in \cite{TCH05}. The one-third law is from \cite{NSTF04}. The small-mutation limit is treated in
\cite{FuIm06}.
\section*{Exercises}
\begin{exercise}\label{exer:neutral}
Show without the formula that neutral fixation has probability $1/N$.
\end{exercise}
\begin{exercise}\label{exer:constant}
Derive $\rho=(1-r^{-1})/(1-r^{-N})$ from \Cref{thm:fix}.
\end{exercise}
\begin{exercise}\label{exer:third}
Deduce the large-population form of the one-third law from the inequality in \Cref{thm:third}.
\end{exercise}
\begin{exercise}\label{exer:coopfix}
For the Prisoner's Dilemma of the source's table, show that the fixation probability of a single cooperator is
smaller than $(3/4)^{N-1}$.
\end{exercise}
\chapter{Local Interaction}\label{ch:local}
In the last part of the source the population lives on a graph: each player meets only its neighbours and
learns only from them \src{\S4.2}. The models are simulated, and the source is candid that their behaviour is
sensitive to details. This is the chapter in which structure helps most, because a graph has maps, and the
maps explain patterns that the simulations display.
\section{The model}
Let $\Gamma$ be a finite graph with vertex set $V$, and $(S,A)$ a game. A \term{configuration} is a map
$\sigma\colon V\to S$. The score of $v$ is $u_v(\sigma)=\sum_{w\sim v}A_{\sigma(v)\sigma(w)}$. Under
\term{imitate-the-best} every player simultaneously adopts the strategy of the highest scorer among itself and
its neighbours. Ties need a rule, and we take one that uses no labels: a player keeps its strategy if that
strategy is among the best, or if the best scorers disagree. This defines a map
\[ U_\Gamma\colon S^V\longrightarrow S^V, \]
a discrete dynamical system on a finite set. Every orbit is eventually periodic, and the questions are which
periods occur and why.
\section{Coverings}
A \term{covering} $p\colon\tilde\Gamma\to\Gamma$ is a graph homomorphism that maps the neighbours of each vertex
bijectively onto the neighbours of its image. The ring $C_{kn}$ covers $C_n$ for $n\ge3$; the infinite line
covers every ring; a torus covers a smaller torus; the square lattice covers them all.
\begin{theorem}[Naturality under coverings]\label{thm:covering}
\Sob For a covering $p\colon\tilde\Gamma\to\Gamma$ the pullback $p^*\colon S^V\to S^{\tilde V}$,
$\sigma\mapsto\sigma\circ p$, commutes with the update:
\[ U_{\tilde\Gamma}\circ p^*=p^*\circ U_\Gamma . \]
Hence $\Gamma\mapsto(S^V,U_\Gamma)$ is a contravariant functor from graphs and coverings to dynamical systems.
The same holds for every update rule in which a player's new strategy is a function of the labelled tree of
walks of some fixed length starting at that player; imitate-the-best uses walks of length two.
\end{theorem}
\begin{proof}
Since $p$ is bijective on neighbourhoods, $u_{\tilde v}(\sigma\circ p)=u_{p(\tilde v)}(\sigma)$ for every $\tilde v$.
Applying this at $\tilde v$ and at each of its neighbours, the pairs (strategy, score) seen by $\tilde v$ are
those seen by $p(\tilde v)$, with multiplicity. The update depends on nothing else.
\end{proof}
\begin{corollary}\label{cor:covering}
\begin{enumerate}[label=(\alph*)]
\item Every orbit on $\Gamma$ lifts to an orbit on every cover. The configurations on the ring $C_{kn}$ that
repeat with spatial period $n$ are exactly the pullbacks of configurations on $C_n$, and they evolve as they do
there. \chk{L2}
\item The automorphisms of $\Gamma$ and the symmetries of the game act on $S^V$ and commute with $U_\Gamma$; the
fixed set of every group of such symmetries is invariant. \chk{L3}
\item What happens on a small ring or torus happens on every larger one that covers it, and on the infinite
lattice. A phenomenon found in simulation on a $30\times30$ torus that survives restriction to a
$3\times3$ or $6\times6$ torus can be analysed there by hand.
\end{enumerate}
\end{corollary}
\begin{remark}
\Sli[\cite{DeLe15,GoSt06}] For continuous-time systems on networks this is the theorem of DeVille and Lerman
that fibrations of graphs induce maps of dynamical systems, and the invariant subspaces of (b) are the
synchrony subspaces of Golubitsky and Stewart. On a Cayley graph the statement that $U$ commutes with
translations is half of the Curtis--Hedlund--Lyndon theorem: the continuous translation-equivariant self-maps of
$S^G$ are exactly the cellular automata \cite{Hed69}. Local-interaction models on lattices are cellular
automata whose local rule happens to come from a game.
\end{remark}
\section{Why the ring rotates}
The source places Rock--Paper--Scissors on a ring of nine players in three clusters, $RRR\,PPP\,SSS$, and
observes that each cluster moves one place per generation, for ever \src{\S4.2.1}. \chk{L1}
\begin{proposition}\label{prop:ring}
\Sob Let $\tau$ be rotation of $C_9$ by three places and $c$ the cyclic relabelling
$R\mapsto P\mapsto S\mapsto R$, which is a symmetry of the game. The configuration $\sigma_0=RRR\,PPP\,SSS$ is
fixed by the \emph{twisted} symmetry $g\colon\sigma\mapsto c\circ\sigma\circ\tau^{-1}$. The set of
configurations fixed by $g$ has $27$ elements and is invariant under $U$. Nine of them are the rotations of
$\sigma_0$, on which $U$ acts as rotation by one place, with period nine; the other eighteen are mapped into
this orbit by one application of $U$. \chk{L8}
\end{proposition}
\begin{proof}
Invariance is \Cref{cor:covering}(b). A fixed configuration is determined by its values on three consecutive
vertices, whence $27$. For the motion, score a win $1$, a loss $-1$ and a tie $0$. A player inside a cluster
scores $0$; at the boundary between the clusters of $R$ and $P$ the $R$-player scores $-1$ and the $P$-player
$+1$. The losing boundary player sees a neighbour with the top score and adopts its strategy; the winning one
keeps its own; the middle player of a cluster sees only its own strategy. Each cluster therefore advances one
place into the cluster it beats and retreats one place from the cluster that beats it. The statement about the
other eighteen configurations is by enumeration.
\end{proof}
\noindent The pattern is a discrete rotating wave: a relative equilibrium, fixed by the dynamics up to a
symmetry. The twisted symmetry accounts for the shape of the pattern, three clusters in cyclic order, and the
local computation for its speed. By \Cref{cor:covering}(a) the same wave runs on every ring of $9k$ players,
and patterns with clusters of other sizes are waves for other twisted symmetries. Within the symmetric set
the wave is the only possible long-run behaviour, which is more than symmetry alone could give. The source
remarks that on a ring the only outcomes are cycling and uniformity. With the tie rule adopted here there is a
third: the configuration $RPS\,RPS\,RPS$, in which every player beats one neighbour and loses to the other, is
a fixed point, since all scores are equal. We found no tie rule stated in the source, and the remark may be
correct for the rule used there; the example shows that it depends on one.
\section{Cooperation at the boundary}
Now let $S=\{C,D\}$ with the Prisoner's Dilemma payoffs $T>R>P>S$ (temptation, reward, punishment,
sucker). On the simple ring a cluster of cooperators cannot grow. On the \term{$1,2$-circulant}, where each
player has the two nearest players on each side as neighbours, it can \src{\S4.2.2}.
\begin{proposition}[Thresholds on the $1,2$-circulant]\label{prop:thresholds}
\Sob Consider a run of at least five cooperators next to a run of at least five defectors. Under
imitate-the-best the boundary between them
\begin{center}
\begin{tabular}{@{}ll@{}}
moves into the defectors, one place per round, & if $3R+S>2T+2P$;\\
is stationary & if $3R+S<2T+2P<4R$;\\
moves into the cooperators, two places per round, & if $2T+2P>4R$.
\end{tabular}
\end{center}
\end{proposition}
\begin{proof}
Number the cooperators $1,2,3,\dots$ from the boundary and the defectors $0,-1,-2,\dots$. The scores are
\begin{align*} u_1&=2R+2S, & u_2&=3R+S, & u_3&=4R,\\ u_0&=2T+2P, & u_{-1}&=T+3P, & u_{-2}&=4P . \end{align*}
Defector $0$ sees players $-2,\dots,2$: the best defector it sees is itself and the best cooperator is player $2$,
so it switches exactly when $3R+S>2T+2P$. Defector $-1$ sees player $0$, who outscores the only cooperator in
view, and stays; the remaining defectors see no cooperator. Cooperators $1$ and $2$ both see defector $0$ and cooperator $3$, and stay exactly when
$4R>2T+2P$; cooperator $3$ sees only cooperators and player $0$ is out of its sight.
\end{proof}
With $R=1$, $P=S=0$ and $T=b$ the thresholds are $b=\tfrac32$ and $b=2$. Starting from six cooperators among
thirty players, the cluster grew by two per round for $b=1.1$, stayed at six for $b=1.7$, and vanished in
two rounds for $b=2.1$. \chk{L6} For the source's matrix $(T,R,P,S)=(1.1,1,0,-0.1)$ the first inequality reads
$2.9>2.2$, which are the two scores the source quotes for the cooperator and the boundary defector. The
simulation then reproduces the rest of the source's account: the cooperators spread until one defector
remains; the lone defector scores $4T=4.4$ and converts its four neighbours; the block of five defectors
shrinks to three and to one; and the number of defectors cycles $1,5,3$ for ever. On the simple ring the same
cluster is frozen for this matrix and eroded for the source's second matrix $(1.5,1,0.6,0)$, as the source
states. \chk{L7}
\begin{remark}
The mechanism is visible in the proof: cooperation spreads when the cooperator one step behind the front,
who has three cooperating neighbours, outscores the defector at the front, who exploits two. On the simple
ring there is no such player. The source's caution that results of this kind depend on the neighbourhood, the
payoffs and the update rule is exactly right, and the proposition says how: through three linear inequalities
that change with each of them.
\end{remark}
\section{Graphs that amplify and suppress selection}
For constant fitness the Moran process can be run on a weighted directed graph: an individual at $i$,
chosen in proportion to fitness, places its offspring at $j$ with probability $w_{ij}$, where $W$ is a
stochastic matrix.
\begin{theorem}[Isothermal theorem]\label{thm:iso}
\Sli[\cite{LHN05}] The fixation probability of a single mutant of fitness $r$, placed uniformly at random,
equals the Moran value $(1-r^{-1})/(1-r^{-N})$ for every $r$ if and only if $W$ is doubly stochastic.
\end{theorem}
\noindent A doubly stochastic matrix is a stochastic map that preserves the uniform distribution, so the
isothermal graphs are the endomorphisms of the probability space $(V,\text{uniform})$ in $\FinStoch$. For them
the number of mutants is itself a birth--death chain with ratio $r$ (\Cref{exer:iso}), and structure is
invisible to selection: on the complete graph and on the cycle the computed fixation probabilities agree
with the Moran value to ten digits. \chk{L4} Other graphs change the balance between selection and drift.
\begin{center}
\begin{tabular}{@{}lccc@{}}
\toprule
$N=6$ & well-mixed & star & directed line\\
\midrule
advantageous mutant, $r=1.5$ & $0.3654$ & $0.4432$ & $0.1667$\\
disadvantageous mutant, $r=0.7$ & $0.0571$ & $0.0333$ & $0.1667$\\
\bottomrule
\end{tabular}
\end{center}
The star amplifies selection in both directions, and on the directed line only a mutant at the root can
take over, so fixation is $1/N$ whatever the fitness. \chk{L5} The values are exact, from the linear system
for the absorption probabilities on all $2^6$ subsets.
\section*{Notes}
Local-interaction models of this kind go back to Nowak and May \cite{NoMa92}; the source's examples are in the
tradition of Skyrms's and Alexander's work on the evolution of social structure \cite{Sky04,Alex07}. Evolutionary
graph theory, the isothermal theorem, amplifiers and suppressors are from \cite{LHN05}. The source ends with a
simulation of the centipede game on a lattice, in which the socially optimal outcome occurs $13.3$ per cent of
the time, close to the figure of about $15$ per cent in the experiments of McKelvey and Palfrey
\src{\S4.2.3}; we have not reproduced it, since it depends on the distribution of initial conditions, which the
functorial statements above do not see.
\section*{Exercises}
\begin{exercise}\label{exer:cover}
Show that reduction modulo $n$ is a covering $C_{kn}\to C_n$ for $n\ge3$ and not for $n=2$.
\end{exercise}
\begin{exercise}\label{exer:twist}
Verify that the configurations on $C_9$ fixed by the twisted symmetry of \Cref{prop:ring} number $27$, that
each uses every strategy exactly three times, and that $RPS\,RPS\,RPS$ is a fixed point of $U$ that is not
among them.
\end{exercise}
\begin{exercise}\label{exer:ring2}
Repeat the analysis of \Cref{prop:thresholds} for the simple ring, and recover the source's two examples.
\end{exercise}
\begin{exercise}\label{exer:iso}
Show that for doubly stochastic $W$ the ratio of the probabilities that the number of mutants increases and
decreases is $r$ in every state. Why is the star not isothermal?
\end{exercise}
\part{Assessment}
\chapter{Assessment}\label{ch:coda}
\section{What the language did}
Five things, in decreasing order of how much they changed our understanding of the source.
\emph{It isolated the invariance that separates the dynamics.} The replicator equation is natural for all
payoff-preserving maps (\Cref{thm:natural}); the Brown--von Neumann--Nash and Smith dynamics are natural only for
symmetries (\Cref{prop:names}). The survival of dominated strategies, which the source presents as a surprising
theorem about a class of dynamics, becomes the visible cost of giving up naturality for inclusions and clones:
a dynamic that sees names instead of individuals keeps reintroducing a bad name.
\emph{It showed why stability must be a property of sets.} The source moves from evolutionarily stable strategies
to evolutionarily stable sets as a refinement motivated by examples. \Cref{thm:esset} gives a reason that is
independent of examples: stability of a point is destroyed by duplicating a strategy, stability of a set is
preserved, and no notion that depends on how strategies are named can be the right one.
\emph{It explained simulated patterns.} The rotating clusters on the ring are forced by a twisted symmetry
and a covering (\Cref{prop:ring}, \Cref{thm:covering}); the growth of cooperation on the circulant is three
linear inequalities (\Cref{prop:thresholds}). Both were found by asking what the maps of the model are.
\emph{It separated the game from the learner.} Treating a population as an open system
(\Cref{prop:softmax}, \Cref{rem:wiring}) makes ``same game, different dynamics'' and ``same dynamics,
different structure'' into statements about a diagram and its fillings, and it is the form in which the
subject is used in machine learning, as the companion paper \cite{EGML} develops.
\emph{It located a non-commuting square.} The source's claim that the replicator dynamics is not the limit of the
birth--death process is a statement about two orders of limits (\Cref{rem:limits}).
\section{What it did not do}
It proved no new theorem of evolutionary game theory. The observations tagged as such are short, and some of
them are surely known to people who work with these models, whether or not they are written down in this
form. The fixation formulas, the mean-field limit and the one-third law gain nothing from being called
morphisms in $\FinStoch$. Chaos in the replicator equation, which the source illustrates with a four-strategy
example \src{\S3.2.5}, is untouched: we have no categorical handle on it beyond the remark that a strange
attractor is a chain component with a non-trivial Conley index. Bomze's classification of the phase
portraits for three strategies is likewise only cited. The centipede simulation is not reproduced. And the
source's philosophical conclusion, that these models give how-possibly explanations whose robustness must be
argued case by case \src{\S5}, is one that the present treatment supports in a specific way and does not
replace: naturality tells you which features of a model cannot matter, and so narrows the list of those that
might.
\section{How much of this is higher}
\begin{center}\small
\begin{tabular}{@{}>{\raggedright}p{0.29\textwidth}>{\raggedright}p{0.31\textwidth}>{\raggedright\arraybackslash}p{0.31\textwidth}@{}}
\toprule
Source & Structure used here & Level\\
\midrule
\S2 stable strategies and sets & $\Game$; pullback along clone maps & $1$-categorical\\
\S3.2 replicator dynamics & the functor $\Rep\colon\Game\to\Dyn$ & $1$-categorical\\
\S3.2.4 stability, cycles & index theorem; Conley index & homotopy types\\
\S3.2.4 Rock--Paper--Scissors & Hodge decomposition & cohomology in degree $1$\\
\S3.3 other dynamics & naturality and its failure & $1$-categorical\\
\S3.3--3.4 dynamics, populations & open systems and wirings & operadic; a double category\\
\S4.1 birth--death process & $\FinStoch$; a non-commuting square & $1$-categorical\\
\S4.2 local interaction & coverings; equivariance & $1$-categorical, with groupoids of symmetries\\
\bottomrule
\end{tabular}
\end{center}
\noindent In summary, the subject at the level of the source is mostly ordinary category theory. Three things point beyond it. Games modulo column shifts and positive rescalings form a groupoid over
each strategy set, and $\Rep$ is invariant along it up to reparametrization of time; treating these
equivalences as $2$-cells is the natural setting for \Cref{prop:shift}. The Conley index is a homotopy type,
functorial for the inclusions of a Morse decomposition, and its continuation invariance is a statement about
families of games. And the first cohomology that vanishes for the complete comparison graph does not vanish
for partial comparisons, which is where the decomposition of \Cref{thm:hodge} acquires a harmonic part.
\section{Programme}
\Spg Four questions seem worth the effort. (1) Is there a homotopy-invariant of a game, computable from the
payoff matrix, that determines the Conley indices of the chain components of its replicator flow, as the
index of \Cref{thm:index} determines their Euler characteristics? (2) Which dynamics, among those arising from
revision protocols, are functors on $\Game$? \Cref{prop:names} shows that all imitative ones are; a
characterization would say what naturality costs in terms of the properties of \Cref{thm:hs}. (3) Can
the covering functor of \Cref{thm:covering} be extended from coverings to fibrations and to stochastic update
rules, so that it applies to the Moran process on graphs and explains amplifiers as it explains waves? (4) Is
there a setting in which the two limits of \Cref{rem:limits} are the two legs of one universal construction?
\section*{Notes}
For the source's own assessment of what evolutionary models explain, see its concluding section. A treatment of
classical game theory in the style of this volume is \cite{GIHC}; relative entropy as a functor, used in
\Cref{ch:replicator}, is developed in \cite{ESCHC}; the index theory used in \Cref{ch:index} is in
\cite{DTHC}.
\appendix
\chapter{Toolkit}\label{app:toolkit}
This appendix collects the general notions used in the text, in the order in which they are needed.
\paragraph{Categories and functors.} A category has objects, morphisms and an associative composition with
identities; a functor preserves them. A statement of the form ``the construction $X\mapsto F(X)$ is natural''
means that $F$ is a functor: every map $X\to Y$ of the relevant kind induces a map $F(X)\to F(Y)$, compatibly
with composition. A group acting on $X$ then acts on $F(X)$, a subobject of $X$ gives an invariant subobject of
$F(X)$, and a quotient of $X$ gives a quotient of $F(X)$.
\paragraph{Convex spaces and the distribution monad.} For a finite set $S$, $\Dist(S)$ is the simplex of
probability distributions on $S$. A map $f\colon S\to T$ induces the pushforward $f_*\colon\Dist(S)\to\Dist(T)$, and
$\Dist$ is a monad on finite sets whose algebras are convex spaces \cite{Fri09}. A map $\Dist(S)\to\R$ is affine
exactly when it is the expectation of a function on $S$; a payoff is a function on $S\times S$, and its
biaffine extension is the mixed extension.
\paragraph{Stochastic maps.} $\FinStoch$ is the category of finite sets and stochastic matrices. A Markov
chain on a finite set is an endomorphism in it. A state is absorbing if its row is a point mass; a function
is harmonic if it is fixed by the matrix acting on functions.
\paragraph{Dynamical systems.} A flow on a compact space $X$ is a continuous action of $\R$; a map of flows is
a continuous map commuting with the actions. A rest point is \emph{Lyapunov stable} if orbits starting near it
stay near it and \emph{asymptotically stable} if in addition they converge to it. A \emph{Lyapunov function}
is a function that decreases along orbits; a strict one certifies asymptotic stability.
\paragraph{Index and Euler characteristic.} For a vector field with non-degenerate zeros on a compact
manifold with boundary on which it points outward, the sum over zeros of the sign of the determinant of the
derivative is the Euler characteristic (Poincar\'e--Hopf). A simplex is contractible, so its Euler
characteristic is $1$.
\paragraph{Cochains on a graph.} A $0$-cochain is a function on vertices and a $1$-cochain an antisymmetric
function on ordered pairs of adjacent vertices. The differential sends $r$ to $(i,j)\mapsto r_i-r_j$. A
$1$-cochain is closed if its sum around every triangle vanishes. On the complete graph every closed
$1$-cochain is a differential.
\paragraph{Coverings and symmetries.} A covering of graphs is a homomorphism bijective on the neighbourhood
of each vertex. An automorphism of a graph is a covering of the graph by itself. A map between dynamical
systems on configuration spaces that commutes with the updates sends orbits to orbits, periodic orbits to
periodic orbits of period dividing the original, and invariant sets to invariant sets.
\chapter{Concordance with the Source}\label{app:concordance}
The table lists the sections of J.~McKenzie Alexander, \emph{Evolutionary Game Theory} \cite{Alex23}, with the
place in this volume where their content is treated and the form it takes there. The source was read from a
text extraction of its PDF; its definitions and theorems were located by search and read in context, and the
remaining text was read selectively, section by section. Figures were not consulted except through their
captions and the surrounding discussion.
{\small
\begin{longtable}{@{}>{\raggedright}p{0.29\textwidth}>{\raggedright}p{0.19\textwidth}>{\raggedright\arraybackslash}p{0.44\textwidth}@{}}
\toprule
Source & Here & Form\\
\midrule
\endhead
1.1 Rock, Paper, Scissors (Lizard, Spock) & \Cref{ex:rps} & circulant games; their automorphism groups\\
1.2--1.3 Game theory; fundamentals & \Cref{ch:games} & the distribution monad; the category $\Game$; Nash's theorem for symmetric games\\
2.1 Basic concepts (Definitions 1--4) & \Cref{thm:essequiv} & one quadratic form $Q_x$; the ray identity \eqref{eq:ray}\\
2.1 Drift game; Hawk--Dove & \Cref{ex:hd}, \Cref{ch:replicator} & $Q=C(p-q)^2/2$; escape time from a neutrally stable state\\
2.2 Properties (Theorems 1--5) & \Cref{thm:essprops} & stated with proofs or references; the Bishop--Cannings bound\\
2.3 Evolutionarily stable sets & \Cref{thm:esset} & pullback along clone maps preserves stable sets and destroys stable points\\
3.1 Introduction & \Cref{ch:replicator} & the category $\Dyn$\\
3.2 Replicator dynamics (Definition 11) & \Cref{prop:quotient}, \Cref{thm:natural} & quotient of the growth equation; functoriality\\
3.2.1 Biological derivation & \Cref{prop:quotient} & as stated\\
3.2.2 Cultural derivation & \Cref{prop:ppi} & mean dynamic of an imitative revision protocol\\
3.2.3 Simple games & \Cref{ch:replicator}, two strategies & one normal form with three generic cases\\
3.2.4 Stability (Theorems 6, 7) & \Cref{thm:kl}, \Cref{thm:folk}, \Cref{thm:elim} & relative entropy as Lyapunov function; elimination with its rate\\
3.2.4 Rock--Paper--Scissors variants & \Cref{thm:zerosum}, \Cref{prop:grps}, \Cref{thm:hodge} & conserved quantity; eigenvalues; cyclic part of a game\\
3.2.4 Classification for three strategies & \Cref{ch:replicator} & cited only\\
3.2.5 Chaos & \Cref{ch:coda} & not treated\\
3.3 Other dynamics (Theorem 8) & \Cref{thm:hs}, \Cref{prop:names} & naturality separates imitation from innovation\\
3.4 Multipopulation games & \Cref{thm:selten} & two boxes and a wiring\\
4.1 Birth--death process & \Cref{thm:fix}, \Cref{prop:limit}, \Cref{rem:limits} & the source's table recomputed; two limits\\
4.2 Local interaction & \Cref{thm:covering} & functoriality for coverings\\
4.2.1 Rock--Paper--Scissors on a ring & \Cref{prop:ring} & twisted symmetry; rotating wave\\
4.2.2 Prisoner's Dilemma on graphs & \Cref{prop:thresholds} & thresholds; the source's run reproduced\\
4.2.3 Centipede game & \Cref{ch:local}, Notes & not reproduced\\
5 Conclusion & \Cref{ch:coda} & what naturality contributes to robustness\\
--- & \Cref{thm:index}, \Cref{thm:conley}, \Cref{thm:conleyindex} & added: index theorem, chain recurrence, Conley index\\
--- & \Cref{thm:kurtz}, \Cref{thm:third} & added: mean-field limit, one-third law\\
--- & \Cref{thm:iso} & added: isothermal theorem, amplifiers and suppressors\\
\bottomrule
\end{longtable}}
\chapter{Computations}\label{app:computations}
The script \texttt{verify-evolutionary-games.py} that accompanies this volume uses only the Python standard
library, fixes its random seed, and runs in about ten seconds. It performs 42 checks, each printing
\texttt{PASS} or \texttt{FAIL} with the computed values, and exits with status zero if and only if all pass.
The checks recompute the numerical statements of the text and test finite or numerical instances of the
structural ones. They are evidence that the examples are stated correctly; they do not prove the theorems.
Differential equations are integrated with a fourth-order Runge--Kutta scheme; fixation probabilities are
computed exactly, from the product formula or by solving the linear system for absorption.
{\small
\begin{longtable}{@{}p{0.08\textwidth}>{\raggedright\arraybackslash}p{0.85\textwidth}@{}}
\toprule
Check & What is computed\\
\midrule
\endhead
S1 & Hawk--Dove with $V=2$, $C=4$: $Q_{x^*}(y)=C(p-q)^2/2$ on a grid of states (\Cref{ex:hd})\\
S2 & Rock--Paper--Scissors: the uniform state is the only Nash equilibrium and is not an ESS\\
S3 & the source's game with a weakly dominated equilibrium strategy: not an ESS (\Cref{thm:essprops})\\
S4 & drift game: the neutral equilibrium is left by the replicator flow; time from $0.05$ to $\tfrac12$ is $20.944$\\
S5 & Hawk--Dove with $V<C$ has exactly one ESS, the mixed one\\
S6 & \Cref{thm:esset}: over the mixed ESS of Hawk--Dove with Dove duplicated, the fibre is a stable set and no point of it is an ESS\\
R1 & \Cref{thm:natural} on random games: pushforward along a clone surjection and a subgame inclusion carries solutions to solutions\\
R2 & \Cref{thm:gradient}: $\frac d{dt}$(mean payoff) $=2\operatorname{Var}$ for symmetric matrices\\
R3 & \Cref{thm:kl}: $\frac d{dt}\KL{x^*}{x}=-Q_{x^*}(x)$ along numerical solutions\\
R4 & \Cref{thm:zerosum}: the relative entropy to the centre is conserved, drift $1.3\times10^{-15}$ over time $40$\\
R5 & \Cref{prop:grps}: eigenvalues $(b-a)/6\pm i\sqrt3(a+b)/6$ against a numerical Jacobian\\
R6 & good Rock--Paper--Scissors converges to the centre; bad Rock--Paper--Scissors leaves every compact subset of the interior\\
R7 & every Nash equilibrium of random games is a rest point\\
R8 & the source's three-strategy game: the unique equilibrium is uniform, asymptotically stable, and not an ESS\\
R9 & \Cref{thm:elim}: the log-ratio of a dominated twin to its original falls at exactly the penalty\\
I1 & \Cref{thm:index} on 400 random games with three or four strategies: indices sum to $1$, the number of equilibria is odd\\
I2 & all 590 ESS found (by Haigh's criterion) have index $+1$\\
I3 & coordination game: indices $+1,+1,-1$\\
I4 & \Cref{thm:hodge}: Rock--Paper--Scissors is purely cyclic, a rating difference purely transitive, the parts orthogonal; $\tau=0.558$ for a random game\\
I5 & the gradient part is a cocycle on every triangle; the cyclic part carries all the curl\\
I6 & $\frac d{dt}x^{\T}Ax=2\operatorname{Cov}_x(Sx,Ax)$ on random games\\
I7 & sink components of the invasion graph for three standard games; the small-mutation chain concentrates on them\\
O1 & \Cref{prop:ppi} on random games and states\\
O2 & at All-Cooperate the replicator field vanishes and the two direct dynamics do not\\
O3 & both direct dynamics vanish at every Nash equilibrium of sixty random games\\
O4 & \Cref{thm:hs}: time-averaged share $0.116$ of a dominated twin under the Smith dynamic; extinction under the replicator\\
O5 & Battle of the Sexes with two populations: the mixed equilibrium is a rest point, and forty nearby orbits end at the two pure equilibria\\
O6 & \Cref{prop:softmax} against a numerical solution\\
O7 & \Cref{prop:names}(c): defect of naturality under cloning, $4\times10^{-17}$ for the replicator, $0.555$ for Smith, $0.380$ for Brown--von Neumann--Nash\\
F1 & the source's table of fixation probabilities, with and without self-interaction\\
F2 & \Cref{prop:limit}: the limit $1-a/c=\tfrac14$\\
F3 & neutral and constant-fitness fixation\\
F4 & \Cref{thm:third} against exact fixation in 299 random coordination games, $N=60$\\
F5 & \Cref{thm:kurtz}: root-mean-square deviation $0.158$, $0.084$, $0.040$ at $N=50,200,800$\\
L1 & ring of nine: rotation by one place per round, period nine\\
L2 & \Cref{thm:covering} for $C_9\to C_3$, all $27$ configurations\\
L3 & equivariance under rotations, reflections and relabelling on random configurations; the twisted symmetry fixes the wave\\
L4 & \Cref{thm:iso}: complete graph and cycle\\
L5 & star and directed line at $N=6$ (exact)\\
L6 & \Cref{prop:thresholds} at $b=1.1$, $1.7$, $2.1$\\
L7 & the source's matrix on the $1,2$-circulant and on the ring; the cycle $1,5,3$\\
L8 & \Cref{prop:ring}: all $27$ symmetric configurations; a frozen configuration outside them\\
\bottomrule
\end{longtable}}
\noindent Two discrepancies with the source were looked for and one convention was found. The source's fixation table
is reproduced to all printed digits only if a player does not interact with itself (F1). No tie rule for
imitate-the-best was found in the source; with the rule of \Cref{ch:local} its described runs are reproduced
(L1, L7), and a frozen configuration exists that its text does not mention (L8).
\chapter{Solutions to the Exercises}\label{app:solutions}
Solutions to all exercises follow, by chapter. Where a solution relies on a computation, the computation is
also carried out by \texttt{verify-evolutionary-games.py}.
\section*{Chapter 1}
\sol{1.1} By affineness in the first argument,
$\pay{y_\epsilon}{y_\epsilon}=(1-\epsilon)\pay{x}{y_\epsilon}+\epsilon\,\pay{\mu}{y_\epsilon}$. Subtract from
$\pay{x}{y_\epsilon}$.
\sol{1.2} A symmetry is a permutation that preserves who beats whom. For Rock--Paper--Scissors the three
rotations do, and a transposition reverses the cycle, so the group is $\Z/3$. For the five-strategy game
the translations give $\Z/5$. A symmetry is an automorphism of a tournament, and such groups have odd order,
since an involution would exchange two strategies and so reverse the result between them. A subgroup of the
symmetric group on five letters of odd order containing a $5$-cycle has order $5$ or $15$, and there is no
subgroup of order $15$, since it would be cyclic. The group is $\Z/5$.
\sol{1.3} Subtract $(V-C)/2$ from the first column and $V/2$ from the second:
$\begin{psmallmatrix}0&V/2\\(C-V)/2&0\end{psmallmatrix}$, so $a=V/2$ and $b=(C-V)/2$. For $V<C$ both are positive:
neither pure state is an equilibrium and the mixed equilibrium has Hawk at frequency $a/(a+b)=V/C$. For
$V>C$, $a>0>b$: Hawk strictly dominates and All-Hawk is the only equilibrium.
\sol{1.4} By \Cref{prop:nashmaps}(a) applied to the clone map onto Hawk--Dove, the equilibria are exactly the
states whose image is the mixed equilibrium: $(V/C,\,s,\,1-V/C-s)$ with $0\le s\le1-V/C$. They form a segment.
\section*{Chapter 2}
\sol{2.1} If $x$ is strict, then $\pay{x}{x}>\pay{y}{x}$ for $y\ne x$, which is the first clause of the definition.
In a two-strategy game let $x$ be a pure ESS, say the first strategy. It is an equilibrium, so $A_{11}\ge A_{21}$,
and by hypothesis the inequality is strict; then $x$ is strict. An ESS that is not pure is interior.
\sol{2.2} The uniform state is an interior equilibrium, so by \Cref{thm:essprops}(f) it is an ESS if and only if
$z^{\T}Az<0$ for $z\ne0$ with $\sum_sz_s=0$. Here $z^{\T}Az=(a-b)(z_1z_2+z_2z_3+z_3z_1)$ and
$z_1z_2+z_2z_3+z_3z_1=-\tfrac12|z|^2$ on that plane, so $z^{\T}Az=-\tfrac{a-b}2|z|^2$, negative exactly when $a>b$.
\sol{2.3} The identity matrix: each pure strategy is a strict equilibrium, hence an ESS, and
$\binom31=3$.
\sol{2.4} Write $y=(1-q,q)$, with $q$ the weight on the second strategy. For $x$ the first pure strategy,
$\pay{x}{y}=1+99q$ and $\pay{y}{y}=(1-q)(1+99q)+100q^2$, so $\Q_x(y)=q(1+99q)-100q^2=q(1-q)>0$ for $0<q<1$: an ESS. For
$x$ the second, with $p=1-q$ the weight on the first, $\Q_x(y)=-p^2<0$: not an ESS, although it is an equilibrium.
\section*{Chapter 3}
\sol{3.1} With payoffs $\begin{psmallmatrix}0&a\\b&0\end{psmallmatrix}$ and state $(x,1-x)$, the two strategies
earn $a(1-x)$ and $bx$, and $\dot x=x(1-x)\bigl(a(1-x)-bx\bigr)$. For $\dot x=x^2(1-x)$, partial fractions give
$\int\frac{dx}{x^2(1-x)}=-\frac1x+\log\frac{x}{1-x}$; evaluate between $x_0$ and $x_1$.
\sol{3.2} $\frac d{dt}x^{\T}Ax=\dot x^{\T}(A+A^{\T})x=2\sum_sx_s\bigl((Ax)_s-x^{\T}Ax\bigr)(Sx)_s
=2\operatorname{Cov}_x(Sx,Ax)$, because $\sum_sx_s\bigl((Ax)_s-x^{\T}Ax\bigr)=0$. For symmetric $A$ this is twice the
variance of $Ax$.
\sol{3.3} At the uniform state the linearization on the tangent plane is $\tfrac13A$ composed with the projection
along $\one$. In the basis of the two complex eigenvectors of the cyclic shift, $A$ acts by
$a\omega+(-b)\bar\omega$ and its conjugate, with $\omega=e^{2\pi i/3}$, so the eigenvalues are
$\tfrac13(a\omega-b\bar\omega)$ and its conjugate: real part $\tfrac13\cdot\tfrac{-a+b}{2}$, imaginary part
$\pm\tfrac13\cdot\tfrac{\sqrt3}2(a+b)$. The trace is $(b-a)/3$ and the determinant
$\bigl((b-a)^2+3(a+b)^2\bigr)/36$.
\sol{3.4} By \Cref{cor:three}(b) the class frequencies follow the replicator equation of Rock--Paper--Scissors
from the initial state $(\tfrac12,\tfrac14,\tfrac14)$. By \Cref{thm:zerosum} they move on the closed curve
on which the relative entropy to the centre is constant, equivalently on which the product of the three
frequencies equals $\tfrac1{32}$. The two variants of Rock keep equal shares.
\section*{Chapter 4}
\sol{4.1} Let $F(x)=x(1-x)\bigl(a-(a+b)x\bigr)$; the index at an equilibrium is the sign of $-F'$. For $a>0>b$ the
only equilibrium is $x=1$, with $F'(1)=b<0$: index $+1$. For $a,b>0$ the only equilibrium is
$x^*=a/(a+b)$, with $F'(x^*)=-(a+b)x^*(1-x^*)<0$: index $+1$. For $a,b<0$ the equilibria are $0$, $1$ and $x^*$,
with $F'(0)=a<0$, $F'(1)=b<0$ and $F'(x^*)>0$: indices $+1,+1,-1$. The sum is $1$ in each case.
\sol{4.2} A gradient has zero curl on every triangle. Conversely, if the curl vanishes on triangles through
the vertex $0$, put $r_i=K_{i0}$. Then $K_{ij}+K_{j0}+K_{0i}=0$ gives $K_{ij}=K_{i0}-K_{j0}=r_i-r_j$.
\sol{4.3} The row means are $r=\bigl(\tfrac{1+t}3,0,-\tfrac{1+t}3\bigr)$, so $G_{12}=G_{23}=\tfrac{1+t}3$,
$G_{13}=\tfrac{2(1+t)}3$, and $C_{12}=C_{23}=\tfrac{2-t}3$, $C_{13}=-\tfrac{2-t}3$. The curl is $2-t$, and
\[ \tau=\frac{2(1+t)^2}{3(2+t^2)} . \]
It equals $1$ at $t=2$, where the game is a rating difference, and $0$ at $t=-1$, which is
Rock--Paper--Scissors.
\sol{4.4} Dove invades Hawk, since $0>(V-C)/2$, and Hawk invades Dove, since $V>V/2$. The graph is a
two-cycle and its only sink component is the whole of it. This records correctly that neither pure state
persists, and it misses the outcome: the flow converges to the mixed state, which is not a vertex.
\section*{Chapter 5}
\sol{5.1} $\dot x_i=\sum_jx_jx_i(K-\pi_j)-x_i(K-\pi_i)\sum_jx_j=x_i(K-\bar\pi)-x_i(K-\pi_i)=x_i(\pi_i-\bar\pi)$.
\sol{5.2} At a Nash equilibrium no strategy earns more than the mean, so $k=0$ and the field vanishes.
Conversely, let $\dot x=0$ and suppose $\kappa=\sum_jk_j>0$. Then $x_i=k_i/\kappa$ for all $i$, so the support of
$x$ consists of strategies earning strictly more than the mean, which contradicts
$\sum_ix_i(\pi_i-\bar\pi)=0$. Hence $k=0$, which is the equilibrium condition.
\sol{5.3} Let $z(t)=\log x(0)+\int_0^t\pi$ and $x=\operatorname{softmax}(z)$. Then
$\frac d{dt}\log x_i=\pi_i-\frac d{dt}\log\sum_je^{z_j}=\pi_i-\sum_jx_j\pi_j$.
\sol{5.4} Row's two strategies earn $2y$ and $1-y$; Column's earn $x$ and $2(1-x)$. Hence
$\dot x=x(1-x)(3y-1)$ and $\dot y=y(1-y)(3x-2)$. At $(\tfrac23,\tfrac13)$ the Jacobian has zero diagonal and both
off-diagonal entries equal to $3\cdot\tfrac29=\tfrac23$; its eigenvalues are $\pm\tfrac23$.
\section*{Chapter 6}
\sol{6.1} With equal fitnesses the number of $A$-players is a bounded martingale, so its expectation at
absorption equals its initial value: $N\rho=1$. Alternatively, each of the $N$ initial individuals is equally
likely to be the ancestor of the final population.
\sol{6.2} Here $g_i/f_i=r^{-1}$ for every $i$, and
$1+\sum_{k=1}^{N-1}r^{-k}=(1-r^{-N})/(1-r^{-1})$.
\sol{6.3} Dividing by $N$ and letting $N\to\infty$ gives $a+2b>c+2d$, that is, $a-c>2(d-b)$. With $a>c$ and $d>b$
this is $x^*=(d-b)/\bigl((a-c)+(d-b)\bigr)<\tfrac13$.
\sol{6.4} With $i$ cooperators,
$\frac{g_i}{f_i}=\frac{4i+2(N-i-1)}{3(i-1)+(N-i)}=\frac{2i+2N-2}{2i+N-3}$, which decreases in $i$ and at $i=N-1$
equals $\frac{4N-4}{3N-5}>\tfrac43$. The last term of the sum in \Cref{thm:fix} alone exceeds $(4/3)^{N-1}$.
\section*{Chapter 7}
\sol{7.1} The neighbours $i\pm1$ of $i$ go to $(i\pm1)\bmod n$, which are distinct and are the neighbours of
$i\bmod n$ when $n\ge3$. For $n=2$ they coincide, and $C_2$ is in any case a single edge.
\sol{7.2} The condition is $\sigma(i+3)=c(\sigma(i))$ for all $i$. The values at $0,1,2$ are free and determine the
rest consistently, because $c^3$ is the identity: $27$ configurations. Each orbit $\{i,i+3,i+6\}$ of the
rotation carries $a$, $c(a)$, $c^2(a)$, so each strategy occurs once per orbit and three times in all. In
$RPS\,RPS\,RPS$ every player beats one neighbour and loses to the other, all scores are $0$, and under the tie
rule nobody changes. It satisfies $\sigma(i+3)=\sigma(i)\ne c(\sigma(i))$ and so is not among the $27$.
\sol{7.3} Number the cooperators $1,2,\dots$ and the defectors $0,-1,\dots$ from the boundary. The scores are
$u_1=R+S$, $u_2=2R$, $u_0=T+P$, $u_{-1}=2P$. Defector $0$ outscores both its neighbours and stays. Cooperator $1$
sees defector $0$ and cooperator $2$, and stays exactly when $2R>T+P$. So a cluster never grows; it is
frozen if $2R>T+P$ and loses one player at each end per round if $2R<T+P$. For $(1.1,1,0,-0.1)$,
$2>1.1$: frozen. For $(1.5,1,0.6,0)$, $2<2.1$: eroded.
\sol{7.4} Let $M$ be the set of mutants and $m=\sum_{i,j\in M}w_{ij}$. The number of mutants increases with
probability proportional to $r\sum_{i\in M,\,j\notin M}w_{ij}=r(|M|-m)$, using row sums, and decreases with
probability proportional to $\sum_{i\notin M,\,j\in M}w_{ij}=|M|-m$, using column sums, with the same
constant. The ratio is $r$. On the star each leaf sends its offspring to the centre, so the column of the
centre sums to $N-1$ and that of a leaf to $1/(N-1)$.
\backmatter
\chapter{References}
\begingroup\small
\renewcommand{\chapter}[2]{}
\noindent Entries were assembled from memory, except \cite{OPP19}, whose authors, title and venue were checked
against the publisher's page on 17 November 2026. Volume and page numbers in particular should be verified
before they are relied on.
\begin{thebibliography}{CMOP11}\setlength{\itemsep}{1pt}
\newcommand{\bi}[1]{\bibitem[#1]{#1}}
\bi{Aki79} E.~Akin, \emph{The Geometry of Population Genetics}, Lecture Notes in Biomathematics 31, Springer, 1979.
\bi{Alex07} J.~M.~Alexander, \emph{The Structural Evolution of Morality}, Cambridge University Press, 2007.
\bi{Alex23} J.~M.~Alexander, \emph{Evolutionary Game Theory}, Elements in Decision Theory and Philosophy, Cambridge University Press, 2023. The source.
\bi{ASS80} A.~Arneodo, P.~Coullet, C.~Tresser, Occurrence of strange attractors in three-dimensional Volterra equations, \emph{Phys.\ Lett.\ A} 79 (1980), 259--263.
\bi{BaFr14} J.~C.~Baez, T.~Fritz, A Bayesian characterization of relative entropy, \emph{Theory Appl.\ Categ.} 29 (2014), 422--456.
\bi{BaPo16} J.~C.~Baez, B.~S.~Pollard, Relative entropy in biological systems, \emph{Entropy} 18 (2016), no.~2, 46.
\bi{BaSc01} D.~Balkenborg, K.~H.~Schlag, Evolutionarily stable sets, \emph{Internat.\ J.~Game Theory} 29 (2001), 571--595.
\bi{BiCa76} D.~T.~Bishop, C.~Cannings, Models of animal conflict, \emph{Adv.\ Appl.\ Probab.} 8 (1976), 616--621.
\bi{BjWe96} J.~Bj\"ornerstedt, J.~W.~Weibull, Nash equilibrium and evolution by imitation, in \emph{The Rational Foundations of Economic Behaviour}, Macmillan, 1996, 155--171.
\bi{Bom83} I.~M.~Bomze, Lotka--Volterra equation and replicator dynamics: a two-dimensional classification, \emph{Biol.\ Cybernet.} 48 (1983), 201--211.
\bi{BTP18} D.~Balduzzi, K.~Tuyls, J.~P\'erolat, T.~Graepel, Re-evaluating evaluation, in \emph{Advances in Neural Information Processing Systems} 31, 2018.
\bi{BvN50} G.~W.~Brown, J.~von Neumann, Solutions of games by differential equations, in \emph{Contributions to the Theory of Games I}, Ann.\ of Math.\ Stud.\ 24, Princeton University Press, 1950, 73--79.
\bi{CMOP11} O.~Candogan, I.~Menache, A.~Ozdaglar, P.~A.~Parrilo, Flows and decompositions of games: harmonic and potential games, \emph{Math.\ Oper.\ Res.} 36 (2011), 474--503.
\bi{Con78} C.~Conley, \emph{Isolated Invariant Sets and the Morse Index}, CBMS Regional Conference Series in Mathematics 38, American Mathematical Society, 1978.
\bi{DeLe15} L.~DeVille, E.~Lerman, Modular dynamical systems on networks, \emph{J.~Eur.\ Math.\ Soc.} 17 (2015), 2977--3013.
\bi{DTHC} Anonymous, \emph{Differential Topology in Higher Categories}, Higher Categorical Semantics, 2026. Companion volume.
\bi{EGML} Anonymous, Evolutionary game theory in machine learning and AI: naturality, regret, and recurrence, Higher Categorical Semantics, 2026. Companion paper.
\bi{ESCHC} Anonymous, \emph{Entropy, Sources, and Channels in Higher Categories}, Higher Categorical Semantics, 2026. Companion volume.
\bi{Fri09} T.~Fritz, Convex spaces I: definition and examples, preprint, arXiv:0903.5522.
\bi{FuIm06} D.~Fudenberg, L.~A.~Imhof, Imitation processes with small mutations, \emph{J.~Econom.\ Theory} 131 (2006), 251--262.
\bi{GHWZ18} N.~Ghani, J.~Hedges, V.~Winschel, P.~Zahn, Compositional game theory, in \emph{LICS 2018}, ACM, 2018, 472--481.
\bi{GIHC} Anonymous, \emph{Games and Information in Higher Categories}, Higher Categorical Semantics, 2026. Companion volume.
\bi{GoSt06} M.~Golubitsky, I.~Stewart, Nonlinear dynamics of networks: the groupoid formalism, \emph{Bull.\ Amer.\ Math.\ Soc.} 43 (2006), 305--364.
\bi{Hai75} J.~Haigh, Game theory and evolution, \emph{Adv.\ Appl.\ Probab.} 7 (1975), 8--11.
\bi{Har09} M.~Harper, Information geometry and evolutionary game theory, preprint, arXiv:0911.1383.
\bi{Hed69} G.~A.~Hedlund, Endomorphisms and automorphisms of the shift dynamical system, \emph{Math.\ Systems Theory} 3 (1969), 320--375.
\bi{Hof81} J.~Hofbauer, On the occurrence of limit cycles in the Volterra--Lotka equation, \emph{Nonlinear Anal.} 5 (1981), 1003--1007.
\bi{HoSa11} J.~Hofbauer, W.~H.~Sandholm, Survival of dominated strategies under evolutionary dynamics, \emph{Theor.\ Econ.} 6 (2011), 341--377.
\bi{HoSi98} J.~Hofbauer, K.~Sigmund, \emph{Evolutionary Games and Population Dynamics}, Cambridge University Press, 1998.
\bi{HSS79} J.~Hofbauer, P.~Schuster, K.~Sigmund, A note on evolutionary stable strategies and game dynamics, \emph{J.~Theoret.\ Biol.} 81 (1979), 609--612.
\bi{JLYY11} X.~Jiang, L.-H.~Lim, Y.~Yao, Y.~Ye, Statistical ranking and combinatorial Hodge theory, \emph{Math.\ Program.} 127 (2011), 203--244.
\bi{KMR93} M.~Kandori, G.~J.~Mailath, R.~Rob, Learning, mutation, and long run equilibria in games, \emph{Econometrica} 61 (1993), 29--56.
\bi{Kur70} T.~G.~Kurtz, Solutions of ordinary differential equations as limits of pure jump Markov processes, \emph{J.~Appl.\ Probab.} 7 (1970), 49--58.
\bi{LHN05} E.~Lieberman, C.~Hauert, M.~A.~Nowak, Evolutionary dynamics on graphs, \emph{Nature} 433 (2005), 312--316.
\bi{Mor58} P.~A.~P.~Moran, Random processes in genetics, \emph{Proc.\ Cambridge Philos.\ Soc.} 54 (1958), 60--71.
\bi{MSP73} J.~Maynard Smith, G.~R.~Price, The logic of animal conflict, \emph{Nature} 246 (1973), 15--18.
\bi{Mye21} D.~J.~Myers, Double categories of open dynamical systems (extended abstract), in \emph{Applied Category Theory 2020}, EPTCS 333, 2021, 154--167.
\bi{Nac90} J.~H.~Nachbar, ``Evolutionary'' selection dynamics in games: convergence and limit properties, \emph{Internat.\ J.~Game Theory} 19 (1990), 59--89.
\bi{Nas51} J.~Nash, Non-cooperative games, \emph{Ann.\ of Math.} 54 (1951), 286--295.
\bi{NoMa92} M.~A.~Nowak, R.~M.~May, Evolutionary games and spatial chaos, \emph{Nature} 359 (1992), 826--829.
\bi{Now06} M.~A.~Nowak, \emph{Evolutionary Dynamics: Exploring the Equations of Life}, Harvard University Press, 2006.
\bi{NSTF04} M.~A.~Nowak, A.~Sasaki, C.~Taylor, D.~Fudenberg, Emergence of cooperation and evolutionary stability in finite populations, \emph{Nature} 428 (2004), 646--650.
\bi{OPP19} S.~Omidshafiei, C.~Papadimitriou, G.~Piliouras, K.~Tuyls, M.~Rowland, J.-B.~Lespiau, W.~M.~Czarnecki, M.~Lanctot, J.~Perolat, R.~Munos, $\alpha$-Rank: multi-agent evaluation by evolution, \emph{Sci.\ Rep.} 9 (2019); arXiv:1903.01373.
\bi{PaPi19} C.~Papadimitriou, G.~Piliouras, Game dynamics as the meaning of a game, \emph{ACM SIGecom Exchanges} 16 (2019), no.~2, 53--63.
\bi{RiWe95} K.~Ritzberger, J.~W.~Weibull, Evolutionary selection in normal-form games, \emph{Econometrica} 63 (1995), 1371--1399.
\bi{Sal85} D.~Salamon, Connected simple systems and the Conley index of isolated invariant sets, \emph{Trans.\ Amer.\ Math.\ Soc.} 291 (1985), 1--41.
\bi{San10} W.~H.~Sandholm, \emph{Population Games and Evolutionary Dynamics}, MIT Press, 2010.
\bi{SaZh92} L.~Samuelson, J.~Zhang, Evolutionary stability in asymmetric games, \emph{J.~Econom.\ Theory} 57 (1992), 363--391.
\bi{Sch98} K.~H.~Schlag, Why imitate, and if so, how? A boundedly rational approach to multi-armed bandits, \emph{J.~Econom.\ Theory} 78 (1998), 130--156.
\bi{ScSi83} P.~Schuster, K.~Sigmund, Replicator dynamics, \emph{J.~Theoret.\ Biol.} 100 (1983), 533--538.
\bi{Sel80} R.~Selten, A note on evolutionarily stable strategies in asymmetric animal conflicts, \emph{J.~Theoret.\ Biol.} 84 (1980), 93--101.
\bi{Sha79} S.~Shahshahani, A new mathematical framework for the study of linkage and selection, \emph{Mem.\ Amer.\ Math.\ Soc.} 17 (1979), no.~211.
\bi{Sky04} B.~Skyrms, \emph{The Stag Hunt and the Evolution of Social Structure}, Cambridge University Press, 2004.
\bi{Smi84} M.~J.~Smith, The stability of a dynamic model of traffic assignment: an application of a method of Lyapunov, \emph{Transportation Sci.} 18 (1984), 245--252.
\bi{SSV20} P.~Schultz, D.~I.~Spivak, C.~Vasilakopoulou, Dynamical systems and sheaves, \emph{Appl.\ Categ.\ Structures} 28 (2020), 1--57.
\bi{TaJo78} P.~D.~Taylor, L.~B.~Jonker, Evolutionarily stable strategies and game dynamics, \emph{Math.\ Biosci.} 40 (1978), 145--156.
\bi{TCH05} A.~Traulsen, J.~C.~Claussen, C.~Hauert, Coevolutionary dynamics: from finite to infinite populations, \emph{Phys.\ Rev.\ Lett.} 95 (2005), 238701.
\bi{Tho85} B.~Thomas, On evolutionarily stable sets, \emph{J.~Math.\ Biol.} 22 (1985), 105--115.
\bi{Wei95} J.~W.~Weibull, \emph{Evolutionary Game Theory}, MIT Press, 1995.
\bi{You93} H.~P.~Young, The evolution of conventions, \emph{Econometrica} 61 (1993), 57--84.
\bi{Zee80} E.~C.~Zeeman, Population dynamics from game theory, in \emph{Global Theory of Dynamical Systems}, Lecture Notes in Math.\ 819, Springer, 1980, 471--497.
\end{thebibliography}
\endgroup
\end{document}