Independent scholarship · Open accessThe monthly digest

Indexed text attachment

evolutionary-game-theory-in-higher-categories.tex

Source for Evolutionary Game Theory in Higher Categories

View paper · Download original file

Lines 857–956 of 2037. Source text is displayed literally.

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 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 condition