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 921–1020 of 2037. Source text is displayed literally.

921continuation: 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}. Chain977recurrence as a solution concept for games is argued in \cite{PaPi19}. The Hodge decomposition of pairwise978comparison data is from \cite{JLYY11}; its game-theoretic form for general finite games, into potential,979harmonic and non-strategic parts, is from \cite{CMOP11}; the use of the transitive and cyclic parts in the980evaluation of agents is from \cite{BTP18}.981 982\section*{Exercises}983 984\begin{exercise}\label{exer:index2}985Compute the index of each equilibrium of the three generic classes of two-strategy games in the table of986\Cref{ch:replicator}, and verify \Cref{thm:index}.987\end{exercise}988 989\begin{exercise}\label{exer:curl}990Show that an antisymmetric $K$ is a gradient if and only if its curl vanishes on all triangles through one991fixed vertex.992\end{exercise}993 994\begin{exercise}\label{exer:tau}995Compute the Hodge decomposition and the transitivity index of the antisymmetric game on three strategies996with $K_{12}=1$, $K_{23}=1$, $K_{13}=t$, as a function of $t$.997\end{exercise}998 999\begin{exercise}\label{exer:invgraph}1000Determine the invasion graph and its sink components for the Hawk--Dove game with $V<C$. What do they miss?1001\end{exercise}1002%% ---- end ch/04-index.tex ----1003%% ---- begin ch/05-protocols.tex ----1004\chapter{Revision Protocols, Other Dynamics, and Open Systems}\label{ch:protocols}1005 1006The replicator equation is one dynamic among many. The source derives it a second time from imitation,1007introduces two rivals, and reports a theorem that separates them \src{\S3.2.2, \S3.3}. This chapter places all1008three in one frame and then takes the frame apart into components.1009 1010\section{Revision protocols}1011 1012A \term{population game} is a continuous map $F\colon\Dist(S)\to\R^S$; the linear case $F(x)=Ax$ is the1013symmetric game $(S,A)$. Following Sandholm \cite{San10}, a \term{revision protocol} is a continuous map1014\[ \rho\colon\R^S\times\Dist(S)\longrightarrow\R_{\ge0}^{S\times S}, \]1015where $\rho_{ij}(\pi,x)$ is the rate at which a player of strategy $i$ switches to $j$ when payoffs are $\pi$ and1016the state is $x$; the \term{mean dynamic} it induces is1017\begin{equation}\label{eq:mean}1018\dot x_i=\sum_jx_j\,\rho_{ji}(F(x),x)-x_i\sum_j\rho_{ij}(F(x),x).1019\end{equation}1020