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

741\section{The folk theorem and elimination}742 743\begin{theorem}\label{thm:folk}744\Scl[\cite{HoSi98}; \src{Thm.~6}] (1) Every Nash equilibrium is a rest point of \eqref{eq:rep}. (2) Every745Lyapunov stable rest point is a Nash equilibrium. (3) Every ESS is asymptotically stable. No converse holds.746\end{theorem}747 748\noindent For (1) see \chk{R7}. A pure state is always a rest point by \Cref{cor:three}(a) and need not be an749equilibrium. For the failure of the converse of (3) the source gives the game750$\begin{psmallmatrix}1&1&1\\0&0&3\\2&1&0\end{psmallmatrix}$: its only equilibrium is the uniform state, which751is asymptotically stable and is not an ESS, since criterion (f) of \Cref{thm:essprops} fails. \chk{R8}752 753\begin{theorem}[Elimination, with a rate]\label{thm:elim}754\Scl[Akin 1980; \src{Thm.~7}] Suppose the pure strategy $s$ is strictly dominated by $\mu\in\Dist(S)$ with755margin $\delta>0$: $\pay{\mu}{z}-(Az)_s\ge\delta$ for all $z$. Then along every interior solution756\[ x_s(t)\le\frac{x_s(0)}{\prod_{r}x_r(0)^{\mu_r}}\;e^{-\delta t}. \]757\end{theorem}758\begin{proof}759$\frac{d}{dt}\bigl(\log x_s-\sum_r\mu_r\log x_r\bigr)=(Ax)_s-\pay{\mu}{x}\le-\delta$, and760$\prod_rx_r^{\mu_r}\le1$.761\end{proof}762 763\noindent When $s$ is a twin of another strategy $s'$ with every payoff lowered by $\delta$, the proof gives an764identity: $\log(x_s/x_{s'})$ decreases at the constant rate $\delta$. \chk{R9} The hypothesis that the solution be765interior is the source's proviso that all strategies be initially present, and by \Cref{cor:three}(a) it766cannot be dropped.767 768\section{Cycles}769 770\begin{theorem}\label{thm:zerosum}771\Scl[\cite{HoSi98}] Let $A$ be antisymmetric with an interior equilibrium $x^*$. Then $\KL{x^*}{y}$ is constant772along every interior solution of \eqref{eq:rep}. No interior solution converges to $x^*$ or to the boundary.773\end{theorem}774\begin{proof}775$y^{\T}Ay=0$ and $x^{*\T}Ay=-y^{\T}Ax^*=0$, so $\Q_{x^*}\equiv0$; apply \Cref{thm:kl}.776\end{proof}777 778For Rock--Paper--Scissors this gives the family of closed orbits around the centre. \chk{R4}779 780\begin{proposition}[Generalized Rock--Paper--Scissors]\label{prop:grps}781\Scl[\cite{Zee80}] Let a win pay $a>0$ and a loss $-b<0$. The linearization of \eqref{eq:rep} at the uniform782state has eigenvalues783\[ \lambda_\pm=\frac{b-a}{6}\pm i\,\frac{\sqrt3\,(a+b)}{6}. \]784The centre is asymptotically stable and an ESS for $a>b$, a centre for $a=b$, and a repeller for $a<b$, when785interior orbits approach the boundary. \chk{R5, R6}786\end{proposition}787 788\noindent The cases $a>b$ and $a<b$ are the source's ``good'' and ``bad'' versions. By \Cref{cor:three}(c) the789uniform state is a rest point for every $a,b$, being the fixed point of the $\Z/3$ of symmetries. For three790strategies the possible phase portraits were classified by Zeeman and by Bomze \cite{Zee80,Bom83}; they are791assembled from rest points and cycles. With four strategies the state space is three-dimensional and792chaotic attractors occur \cite{ASS80}; the source illustrates one \src{\S3.2.5}. Two statements survive chaos.793 794\begin{theorem}\label{thm:average}795\Scl[\cite{HoSi98}] If a solution of \eqref{eq:rep} stays at a positive distance from the boundary, then every796limit point of its time averages $\frac1T\int_0^Tx(t)\,dt$ is an interior equilibrium. If the interior797equilibrium is unique, the time averages converge to it.798\end{theorem}799 800\noindent The second surviving statement is the index theorem of the next chapter.801 802\section*{Notes}803 804The replicator equation was introduced in \cite{TaJo78} and named in \cite{ScSi83}. The standard reference is805\cite{HoSi98}; \cite{San10} treats it within a general theory of population dynamics. \Cref{thm:gradient} is in806\cite{Sha79,Aki79}. The functorial statement \Cref{thm:natural} is elementary and its three cases are807classical; we have not found it stated as a single naturality property. Relative entropy as a Lyapunov808function, and the reading of the replicator equation as an information-geometric flow, are developed in809\cite{BaPo16,Har09}. The equivalence of the replicator equation on $n$ strategies with a Lotka--Volterra810system in $n-1$ variables is due to Hofbauer \cite{Hof81}.811 812\section*{Exercises}813 814\begin{exercise}\label{exer:two}815Derive \eqref{eq:two} and the escape-time formula for the drift game.816\end{exercise}817 818\begin{exercise}\label{exer:fisher}819Prove the formula for $\frac{d}{dt}x^{\T}Ax$ in \Cref{thm:gradient}, and show that for general $A$ the rate is820$2\operatorname{Cov}_x(Sx,Ax)$, where $S=\tfrac12(A+A^{\T})$.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