Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 281–380 of 2037. Source text is displayed literally.
281\item Local interaction models are natural with respect to coverings of the interaction graph and equivariant282under its symmetries (\Cref{thm:covering}), which accounts for the rotating patterns the source exhibits.283\end{itemize}284 285Quantitative statements accompany the qualitative ones throughout: rates of extinction, escape times,286eigenvalues, fixation probabilities, thresholds. All of them are recomputed by the companion script.287 288How much of this is ``higher'' is assessed in \Cref{ch:coda}. The short answer: most of it is ordinary category289theory; homotopy enters through the index and the Conley index; cohomology enters in degree one; and the290compositional structure of \Cref{ch:protocols} is two-dimensional. Nothing here is a new theorem of evolutionary291game theory. A companion paper applies the framework to machine learning.292 293The volume belongs to a series with \cite{GIHC}, on classical game theory, \cite{ESCHC}, on information theory,294and \cite{DTHC}, on differential topology, and uses each of them once.295 296\tableofcontents297%% ---- end front.tex ----298\mainmatter299\part{Statics}300%% ---- begin ch/01-games.tex ----301\chapter{Games, Populations, and the Simplex}\label{ch:games}302 303\section{Two readings of one object}304 305A point of the simplex $\Dist(S)$ over a finite set $S$ of strategies can be read in two ways. It is a306\emph{mixed strategy}: one player randomizing over $S$. It is also a \emph{population state}: a large population307in which the fraction $x_s$ of individuals plays the pure strategy $s$. The source moves between the readings308freely and remarks that the equivalence of two definitions of evolutionary stability rests on their agreement309\src{\S2.1}. The agreement is a fact about maps, and it is the starting point of this volume.310 311Let $\FinStoch$ be the category of finite sets and stochastic matrices, and let $\Dist$ be the finite312distribution monad on $\Set$: $\Dist(S)$ is the set of probability vectors on $S$, a function $f\colon S\to T$313induces the pushforward $f_*\colon\Dist(S)\to\Dist(T)$, $(f_*x)_t=\sum_{f(s)=t}x_s$, and the algebras of $\Dist$ are314the convex spaces. The real line is a convex space, so:315 316\begin{proposition}[Mixed extension]\label{prop:mixed}317\Scl Every function $u\colon S\times S\to\R$ extends uniquely to a map $\Dist(S)\times\Dist(S)\to\R$ that is affine in318each variable separately. In coordinates, with $A=(u(s,s'))$, the extension is $(x,y)\mapsto x^{\T}Ay$.319\end{proposition}320 321\begin{definition}\label{def:game}322A \term{symmetric game} is a pair $(S,A)$ of a finite set $S$ and a matrix $A\in\R^{S\times S}$; the entry323$A_{ss'}$ is the payoff to a player using $s$ against a player using $s'$. For $x,y\in\Dist(S)$ write324\[ \pay{x}{y}=x^{\T}Ay \]325for the payoff of $x$ against $y$, and $f(y)=Ay$ for the vector of payoffs of the pure strategies against $y$.326\end{definition}327 328Biaffinity is what identifies the two readings: the expected payoff against an opponent drawn at random from329a population in state $y$ is the payoff against the mixed strategy $y$, because both are the affine extension330of the same function. Whenever the source appeals to ``no difference from a mathematical point of view'', it331is appealing to \Cref{prop:mixed}.332 333\section{Maps of games}334 335\begin{definition}\label{def:map}336A \term{payoff-preserving map} $f\colon(S,A)\to(T,B)$ is a function $f\colon S\to T$ with337$B_{f(s)f(s')}=A_{ss'}$ for all $s,s'\in S$. Symmetric games and payoff-preserving maps form a category $\Game$.338\end{definition}339 340Three kinds of map generate everything.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.