Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 877–976 of 2037. Source text is displayed literally.
877index $+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 under921continuation: if a family of flows has a common isolating neighbourhood, the index is constant along the922family. A hyperbolic rest point with $k$ unstable directions has index the pointed sphere $S^k$; an attracting923closed orbit has the index of a circle with a disjoint base point, whose reduced homology has rank one in924degrees $0$ and $1$. If $h(K)$ is not the homotopy type of a point, $K$ is non-empty.925\end{theorem}926 927\begin{remark}[What is higher here]\label{rem:higher}928The index of \Cref{thm:index} is the Euler characteristic of the Conley index: an equilibrium with $k$929unstable directions contributes $(-1)^k$. The Conley index remembers $k$, and for recurrent sets it remembers a930homotopy type that no count recovers. Continuation invariance is the precise sense in which a qualitative931conclusion drawn from a model survives perturbation of its payoffs: as long as an attractor stays isolated,932its index, and hence its existence, persists. An ESS has index $S^0$ and persists under small changes of the933game; the family of cycles of Rock--Paper--Scissors at $a=b$ is not isolated and does not.934\end{remark}935 936For computation one discretizes. The \term{invasion graph} of a game has the pure strategies as vertices and937an edge $i\to j$ when $A_{ji}>A_{ii}$, that is, when $j$ invades a population of $i$. Its sink strongly connected938components are a finite shadow of the attracting chain components. \chk{I7} The Markov--Conley chains of939$\alpha$-Rank \cite{OPP19} are random walks on such graphs, weighted by fixation probabilities; we return to940them in \Cref{ch:finite}.941 942\section{Decomposition}943 944Every matrix splits as $A=S+K$ with $S=\tfrac12(A+A^{\T})$ symmetric and $K=\tfrac12(A-A^{\T})$ antisymmetric: a945game of common interest plus a zero-sum game. By \Cref{thm:gradient,thm:zerosum} the replicator field is the946sum of a gradient field and a field that, when $K$ has an interior equilibrium, conserves a relative947entropy. Mean payoff obeys $\frac{d}{dt}x^{\T}Ax=2\operatorname{Cov}_x(Sx,Ax)$. \chk{I6}948 949The antisymmetric part decomposes further, and here the statement is cohomological. Regard an antisymmetric950matrix $K$ as a $1$-cochain on the complete graph with vertex set $S$: $K_{ij}$ is the advantage of $i$ over951$j$.952 953\begin{theorem}[Hodge decomposition of a zero-sum game]\label{thm:hodge}954\Sli[\cite{JLYY11,CMOP11}] Every antisymmetric $K$ decomposes uniquely as955\[ 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 . \]956The two parts are orthogonal for the Frobenius inner product. The gradient part satisfies the cocycle condition957$G_{ij}+G_{jk}+G_{ki}=0$ on every triangle, and conversely every antisymmetric matrix satisfying it is a gradient.958The cyclic part $C$ has the same curl $K_{ij}+K_{jk}+K_{ki}$ as $K$ on every triangle.959\end{theorem}960 961\noindent The converse statement is the vanishing of the first cohomology of the full simplex on $S$: a962closed cochain is exact. \chk{I4, I5} We call $\tau(K)=\|G\|^2/\|K\|^2\in[0,1]$ the \term{transitivity index}.963Rock--Paper--Scissors has $\tau=0$ and curl $\pm3$; a game of pure rating differences has $\tau=1$; a random964antisymmetric game on five strategies had $\tau=0.56$.965 966\begin{remark}967If only some pairs of strategies are ever compared, the complete graph is replaced by a comparison graph968with its triangles, and its first cohomology need not vanish. A third, \emph{harmonic}, component appears:969cyclic advantage around a loop that bounds no triangle, locally consistent and globally not a rating. This970is the only place in the volume where a cohomology group is not zero for a trivial reason.971\end{remark}972 973\section*{Notes}974 975The index theorem for the replicator equation is in \cite[Ch.~13]{HoSi98}; the perturbation argument is976Hofbauer's. Conley's theory is in \cite{Con78}, with an accessible account of the index in \cite{Sal85}. Chain