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

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 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