Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 721–820 of 2037. Source text is displayed literally.
721\end{theorem}722 723\noindent This is Fisher's fundamental theorem in the form relevant to games in which the two players'724interests coincide. \chk{R2}725 726\begin{theorem}\label{thm:kl}727\Scl[\cite{HSS79,Zee80}] Along any solution $y(t)$ of \eqref{eq:rep} in the interior of a face containing728$\supp x$,729\[ \frac{d}{dt}\KL{x}{y(t)}=-\Q_x(y(t)). \]730\end{theorem}731\begin{proof}732$\frac{d}{dt}\KL{x}{y}=-\sum_sx_s\dot y_s/y_s=-\sum_sx_s\bigl((Ay)_s-y^{\T}Ay\bigr)=-(\pay{x}{y}-\pay{y}{y})$.733\end{proof}734 735\begin{corollary}\label{cor:folk3}736\src{Thm.~6.3} An ESS is asymptotically stable; an interior ESS attracts the whole interior of the simplex.737More precisely, if $\Q_x>0$ on $U\setminus\{x\}$, every sublevel set $\{y:\KL{x}{y}\le c\}$ contained in $U$738lies in the basin of attraction of $x$. For Hawk--Dove, $\frac{d}{dt}\KL{x}{y}=-\tfrac C2(p-q)^2$. \chk{R3}739\end{corollary}740 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})$.