Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 301–400 of 2037. Source text is displayed literally.
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.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