Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 341–440 of 2037. Source text is displayed literally.
341 342\begin{description}[leftmargin=1.4em,style=sameline]343\item[Inclusions.] An injective $f$ exhibits $(S,A)$ as the \emph{subgame} of $(T,B)$ on the strategies in its344image.345\item[Clone maps.] A surjective $f$ exhibits $(S,A)$ as $(T,B)$ with some strategies duplicated: $s$ and $s'$346with $f(s)=f(s')$ have equal rows and equal columns in $A$.347\item[Symmetries.] An automorphism of $(S,A)$ is a relabelling of strategies that preserves every payoff.348\end{description}349 350\begin{proposition}\label{prop:push}351\Sob For a payoff-preserving $f\colon(S,A)\to(T,B)$ and $x,y\in\Dist(S)$,352\[ \pay{f_*x}{f_*y}_B=\pay{x}{y}_A,\qquad (B f_*y)_{f(s)}=(Ay)_s\ \text{ for every } s\in S. \]353\end{proposition}354\begin{proof}355$(Bf_*y)_{f(s)}=\sum_t B_{f(s)t}\sum_{f(s')=t}y_{s'}=\sum_{s'}B_{f(s)f(s')}y_{s'}=\sum_{s'}A_{ss'}y_{s'}$. The first356identity follows by pairing with $x$.357\end{proof}358 359So $\Dist$ lifts to a functor from $\Game$ to convex spaces with a biaffine form, and every construction of360this volume can be asked whether it respects that functor.361 362\begin{example}[Rock--Paper--Scissors and its relatives]\label{ex:rps}363Let $S=\Z/n$ with $n$ odd, and let $A_{ij}=1$ if $i-j\in\{1,\dots,\tfrac{n-1}2\}$, $-1$ if364$j-i\in\{1,\dots,\tfrac{n-1}2\}$ and $0$ if $i=j$. For $n=3$ this is Rock--Paper--Scissors and for $n=5$ its365five-strategy extension with which the source opens \src{\S1.1}. Translation $i\mapsto i+1$ is a symmetry, so366$\Z/n$ acts on the game. The subgame of the five-strategy game on $\{0,1,3\}$ is a copy of367Rock--Paper--Scissors, an inclusion in $\Game$; the subgame on $\{0,1,2\}$ is not, since there $2$ beats both368others.369\end{example}370 371A second kind of map acts on payoffs and not on strategies.372 373\begin{definition}374A \term{column shift} replaces $A$ by $A+\one c^{\T}$ for a vector $c\in\R^S$: a constant $c_{s'}$ is added to375every payoff against $s'$. A \term{rescaling} replaces $A$ by $\lambda A$ with $\lambda>0$.376\end{definition}377 378A column shift changes $\pay{x}{y}$ by $c^{\T}y$, which does not depend on $x$; it changes no comparison379between strategies. Every game is a column shift of a unique game with zero diagonal, and the source's380normalization to positive payoffs \src{\S4.1} is a column shift by a constant vector.381 382\section{Equilibria}383 384\begin{definition}385A state $x\in\Dist(S)$ is a \term{(symmetric) Nash equilibrium} of $(S,A)$ if $\pay{x}{x}\ge\pay{y}{x}$ for all386$y\in\Dist(S)$; equivalently, if $(Ax)_s\le x^{\T}Ax$ for all $s$, with equality for $s\in\supp x$. It is387\term{strict} if $\pay{x}{x}>\pay{y}{x}$ for all $y\ne x$, and \term{quasi-strict} if $(Ax)_s<x^{\T}Ax$ for all388$s\notin\supp x$.389\end{definition}390 391\begin{theorem}\label{thm:nash}392\Scl[Nash 1951] Every symmetric game has a symmetric Nash equilibrium. If a finite group $G$ acts on $(S,A)$ by393symmetries, the set of Nash equilibria is $G$-invariant and contains a $G$-fixed point.394\end{theorem}395 396\begin{corollary}\label{cor:uniform}397If a group of symmetries acts transitively on $S$, the uniform state is a Nash equilibrium. In particular the398uniform state is an equilibrium of every game of \Cref{ex:rps}.399\end{corollary}400 401How equilibria behave under the maps of \Cref{def:map} is recorded once and used repeatedly.402 403\begin{proposition}\label{prop:nashmaps}404\Sob Let $f\colon(S,A)\to(T,B)$ be payoff-preserving.405\begin{enumerate}[label=(\alph*)]406\item If $f$ is surjective, then $x$ is a Nash equilibrium of $(S,A)$ if and only if $f_*x$ is a Nash407equilibrium of $(T,B)$.408\item If $f$ is injective, then $f_*x$ Nash in $(T,B)$ implies $x$ Nash in $(S,A)$; the converse holds if and409only if no strategy outside the image of $f$ earns more than $\pay{x}{x}$ against $f_*x$.410\end{enumerate}411\end{proposition}412\begin{proof}413By \Cref{prop:push} the pure payoffs against $f_*x$ at strategies in the image of $f$ are the pure payoffs414against $x$, and the mean payoffs agree. The equilibrium condition on $T$ is the equilibrium condition on $S$415together with a condition at strategies outside the image, which is vacuous when $f$ is surjective.416\end{proof}417 418The asymmetry between (a) and (b) recurs at every level of the theory: clone maps are invisible to selection,419inclusions are visible exactly through the strategies they omit.420 421\section*{Notes}422 423The distribution monad and convex spaces as its algebras go back to Stone and to \'Swirszcz; a modern account424is in \cite{Fri09}. \Cref{thm:nash} is from Nash's paper on non-cooperative games \cite{Nas51}. The category425$\Game$ is not standard. Categories of games with strategy-changing morphisms appear in the literature on426potential games and on open games \cite{GHWZ18}; those morphisms are richer and are not needed here. The427classical theory with rational players is the subject of \cite{GIHC}. The invariance of evolutionary dynamics428under column shifts is used systematically in \cite{Zee80,HoSi98}.429 430\section*{Exercises}431 432\begin{exercise}\label{exer:biaffine}433Let $y_\epsilon=(1-\epsilon)x+\epsilon\mu$. Show that434$\pay{x}{y_\epsilon}-\pay{y_\epsilon}{y_\epsilon}=\epsilon\,\bigl(\pay{x}{y_\epsilon}-\pay{\mu}{y_\epsilon}\bigr)$.435\end{exercise}436 437\begin{exercise}\label{exer:aut}438Determine the group of symmetries of Rock--Paper--Scissors and of the five-strategy game of \Cref{ex:rps}.439\end{exercise}440