Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 657–756 of 2037. Source text is displayed literally.
657$x^{\T}Ax=y^{\T}By$. Therefore658\[ \dot y_t=\sum_{f(s)=t}x_s\bigl((Ax)_s-x^{\T}Ax\bigr)=\Bigl(\sum_{f(s)=t}x_s\Bigr)\bigl((By)_t-y^{\T}By\bigr)659=y_t\bigl((By)_t-y^{\T}By\bigr) \]660for $t$ in the image of $f$, and $y_t=0$ identically otherwise, which also solves the equation.661\end{proof}662 663Three familiar facts are the three generating cases of \Cref{def:map}. \chk{R1}664 665\begin{corollary}\label{cor:three}666\begin{enumerate}[label=(\alph*)]667\item \emph{Faces are invariant.} For every $S'\subseteq S$ the face $\Dist(S')$ is invariant, and the flow on668it is the replicator flow of the subgame. In particular strategies absent initially stay absent.669\item \emph{Clones lump.} If strategies are duplicated, the total frequency of each class of duplicates670follows the replicator equation of the game without duplicates.671\item \emph{Symmetries act.} The group of symmetries of $(S,A)$ acts on $\Dist(S)$ by automorphisms of the flow;672the fixed-point set of every subgroup is invariant.673\end{enumerate}674\end{corollary}675 676On the side of payoffs, \eqref{eq:rep} depends only on differences $(Ax)_s-(Ax)_{s'}$, so:677 678\begin{proposition}\label{prop:shift}679\Scl A column shift does not change the replicator field, and a rescaling $A\mapsto\lambda A$ multiplies it by680$\lambda$. The functor $\Rep$ factors through games modulo column shifts.681\end{proposition}682 683\section{Two strategies}684 685By \Cref{prop:shift} a two-strategy game may be taken to be $\begin{psmallmatrix}0&a\\b&0\end{psmallmatrix}$. With686$x$ the frequency of the first strategy, \eqref{eq:rep} reads687\begin{equation}\label{eq:two}688\dot x=x(1-x)\bigl(a-(a+b)x\bigr).689\end{equation}690 691\begin{center}\small692\begin{tabular}{@{}llll@{}}693\toprule694signs of $(a,b)$ & in the source & rest points & behaviour\\695\midrule696$a>0>b$ or $b>0>a$ & Prisoner's Dilemma & $0,1$ & one strategy wins\\697$a,b>0$ & Hawk--Dove & $0,1,\frac{a}{a+b}$ & interior attracts\\698$a,b<0$ & coordination & $0,1,\frac{a}{a+b}$ & interior repels\\699$a=b=0$ & ``game of life'' & every point & nothing moves\\700\bottomrule701\end{tabular}702\end{center}703 704\noindent The drift game of \Cref{ch:stability} is the boundary case $a=0>b$:705there $\dot x=x^2(1-x)$ for the invading strategy, and the invader's frequency passes from $x_0$ to $x_1$ in706time707\[ \frac1{x_0}-\frac1{x_1}+\log\frac{x_1(1-x_0)}{x_0(1-x_1)} . \]708An invader that is merely not selected against escapes in time of order $1/x_0$; one that is selected for709escapes in time of order $\log(1/x_0)$. From $x_0=0.05$ to $\tfrac12$ the drift game takes time $20.94$.710\chk{S4}711 712\section{Geometry: gradients and entropy}713 714The \term{Shahshahani metric} on the open simplex is $g_x(u,v)=\sum_su_sv_s/x_s$ for tangent vectors $u,v$715(vectors with $\sum_su_s=0$). It is the Fisher information metric of statistics.716 717\begin{theorem}\label{thm:gradient}718\Scl[Shahshahani 1979; Kimura 1958] If $A$ is symmetric, \eqref{eq:rep} is the gradient flow of719$\tfrac12x^{\T}Ax$ for the Shahshahani metric, and mean payoff increases at the rate720\[ \frac{d}{dt}\,x^{\T}Ax=2\operatorname{Var}_x(Ax)=2\sum_sx_s\bigl((Ax)_s-x^{\T}Ax\bigr)^2 . \]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}. \]