Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 821–920 of 2037. Source text is displayed literally.
821\end{exercise}822 823\begin{exercise}\label{exer:eig}824Verify \Cref{prop:grps} by computing the trace and determinant of the linearization on the tangent space.825\end{exercise}826 827\begin{exercise}\label{exer:lump}828A population plays Rock--Paper--Scissors with Rock present in two indistinguishable variants, in initial829state $(\tfrac14,\tfrac14,\tfrac14,\tfrac14)$. Describe the motion of the class frequencies.830\end{exercise}831%% ---- end ch/03-replicator.tex ----832%% ---- begin ch/04-index.tex ----833\chapter{Index, Recurrence, and Decomposition}\label{ch:index}834 835Three questions cannot be answered one equilibrium at a time. How many equilibria can there be, and of what836kinds? What replaces an equilibrium when the dynamics cycles? Which part of a game is responsible for the837cycling? Each has an answer in which topology does the work.838 839\section{The index theorem}840 841Write $F_A$ for the replicator field. At a rest point $x$ its derivative preserves the tangent space842$T=\{v:\sum_sv_s=0\}$ of the simplex.843 844\begin{definition}845A game is \term{regular} if every Nash equilibrium is quasi-strict and $D_xF_A|_T$ is invertible at each. The846\term{index} of a Nash equilibrium $x$ of a regular game is847\[ \operatorname{ind}(x)=\operatorname{sign}\det\bigl(-D_xF_A|_T\bigr)\in\{+1,-1\}. \]848\end{definition}849 850\noindent Regular games are open and dense among all games. An equilibrium at which every eigenvalue of851$D_xF_A|_T$ has negative real part has index $+1$.852 853\begin{theorem}[Index theorem]\label{thm:index}854\Scl[Hofbauer and Sigmund; Poincar\'e--Hopf] For a regular game,855\[ \sum_{x\ \mathrm{Nash}}\operatorname{ind}(x)=1 . \]856\end{theorem}857\begin{proof}[Sketch]858For small $\epsilon>0$ the field $F_A(x)+\epsilon(u-x)$, with $u$ the uniform state, points strictly inward859on the boundary of the simplex. Its rest points converge, as $\epsilon\to0$, to the rest points of $F_A$ that860are \emph{saturated}, that is, to the Nash equilibria: a rest point with a strategy outside its support that861earns more than average is pushed out of the simplex and disappears. Regularity makes the correspondence a862bijection that preserves the sign of the determinant. The negative of an inward-pointing field points outward,863and by the Poincar\'e--Hopf theorem the sum of the indices of its zeros is the Euler characteristic of the864simplex, which is $1$ because the simplex is contractible; see \DT{Ch.~7} for the three descriptions of865the Euler characteristic used here.866\end{proof}867 868The theorem is checked on four hundred random games with three and four strategies. \chk{I1}869 870\begin{corollary}\label{cor:index}871In a regular game: (a) the number of Nash equilibria is odd; (b) every ESS has index $+1$ \chk{I2}; (c) if872there are $k$ equilibria of index $+1$ there are exactly $k-1$ of index $-1$; in particular two ESS force a873third equilibrium, which is not stable. \chk{I3}874\end{corollary}875 876\noindent In the coordination game $\begin{psmallmatrix}2&0\\0&1\end{psmallmatrix}$ the two conventions have877index $+1$ and the mixed equilibrium, which separates their basins, has index $-1$. The index theorem is the878reason a model with two stable conventions always has a threshold between them. It holds whatever the879dynamics does elsewhere, cycles and chaos included.880 881\section{Recurrence and the Conley index}882 883When trajectories do not converge, the object that plays the part of an equilibrium is a recurrent set.884 885\begin{definition}886For a flow $\varphi$ on a compact metric space, an \term{$(\epsilon,\tau)$-chain} from $x$ to $y$ is a887sequence $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 point888is \term{chain recurrent} if for all $\epsilon,\tau$ there is a chain from it to itself; two chain recurrent889points are equivalent if chains run both ways. The classes are the \term{chain components}.890\end{definition}891 892\begin{theorem}[Conley's decomposition]\label{thm:conley}893\Scl[Conley 1978] Every flow on a compact metric space has a continuous function that is strictly decreasing894along orbits off the chain recurrent set and constant on each chain component. The flow is gradient-like895between chain components.896\end{theorem}897 898Chain components generalize equilibria in exactly the way the source's examples require.899 900\begin{example}\label{ex:chains}901For the Prisoner's Dilemma the chain components are the two pure states, and All-Defect is the only one that902attracts. For a coordination game there are three. For Rock--Paper--Scissors with $a=b$ every state is chain903recurrent and the whole simplex is a single chain component: arbitrarily small errors carry the population904from any closed orbit to any other, and to the boundary. For $a<b$ the chain components are the centre and905the boundary cycle, and the boundary cycle attracts.906\end{example}907 908Papadimitriou and Piliouras propose the chain components of a learning dynamic, and the sink components909among them, as what a game ``means'' when equilibria do not predict behaviour \cite{PaPi19}.910 911To each isolated invariant set Conley attaches more than a number.912 913\begin{definition}914An \term{index pair} for an isolated invariant set $K$ is a pair of compact sets $L\subseteq N$ such that $K$ is915the largest invariant set in $N\setminus L$, $L$ is positively invariant in $N$, and orbits leave $N$ only916through $L$. The \term{Conley index} of $K$ is the pointed homotopy type $h(K)=[N/L]$.917\end{definition}918 919\begin{theorem}\label{thm:conleyindex}920\Scl[Conley 1978; \cite{Sal85}] The Conley index does not depend on the index pair. It is invariant under