Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 257–356 of 2037. Source text is displayed literally.
257Evolutionary game theory replaces the rational player of classical game theory by a population. Strategies are258inherited or imitated, payoffs are rates of reproduction or adoption, and the questions change from ``what should259one do?'' to ``what persists?''. Alexander's Element \cite{Alex23} is a compact map of the subject: the static260theory of evolutionarily stable strategies and its set-valued refinements; the replicator equation and its261relatives; finite populations; and models in which interaction is local. It is written for philosophers, and it262is candid about where the models are fragile.263 264This volume retells that material with one question in mind: which of the constructions are \emph{natural}, in265the technical sense that they commute with the evident maps between games? The answers organize the subject266more sharply than we expected.267 268\begin{itemize}[leftmargin=1.4em]269\item The replicator equation is a functor from games and payoff-preserving maps to dynamical systems270(\Cref{thm:natural}). Invariance of faces, the lumping of duplicate strategies, and the action of symmetries271are three instances of one statement.272\item Evolutionary stability of a \emph{point} is not preserved by pulling back along a map that duplicates273strategies; evolutionary stability of a \emph{set} is (\Cref{thm:esset}). The set-valued refinements that the274source surveys are what the point-valued notion is forced to become.275\item The equilibria of a regular game carry indices that sum to one, the Euler characteristic of the simplex276(\Cref{thm:index}); behind the number is a homotopy type, the Conley index, and behind recurrent behaviour a277decomposition 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$.