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

277decomposition whose obstruction is a first cohomology class (\Cref{ch:index}).278\item A population is an open system, with payoffs as input and a state as output, and a game is a wiring of279such systems (\Cref{ch:protocols}). The replicator is one box among several, and the source's comparison of280dynamics is a comparison of boxes.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}