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

997\end{exercise}998 999\begin{exercise}\label{exer:invgraph}1000Determine the invasion graph and its sink components for the Hawk--Dove game with $V<C$. What do they miss?1001\end{exercise}1002%% ---- end ch/04-index.tex ----1003%% ---- begin ch/05-protocols.tex ----1004\chapter{Revision Protocols, Other Dynamics, and Open Systems}\label{ch:protocols}1005 1006The replicator equation is one dynamic among many. The source derives it a second time from imitation,1007introduces two rivals, and reports a theorem that separates them \src{\S3.2.2, \S3.3}. This chapter places all1008three in one frame and then takes the frame apart into components.1009 1010\section{Revision protocols}1011 1012A \term{population game} is a continuous map $F\colon\Dist(S)\to\R^S$; the linear case $F(x)=Ax$ is the1013symmetric game $(S,A)$. Following Sandholm \cite{San10}, a \term{revision protocol} is a continuous map1014\[ \rho\colon\R^S\times\Dist(S)\longrightarrow\R_{\ge0}^{S\times S}, \]1015where $\rho_{ij}(\pi,x)$ is the rate at which a player of strategy $i$ switches to $j$ when payoffs are $\pi$ and1016the state is $x$; the \term{mean dynamic} it induces is1017\begin{equation}\label{eq:mean}1018\dot x_i=\sum_jx_j\,\rho_{ji}(F(x),x)-x_i\sum_j\rho_{ij}(F(x),x).1019\end{equation}1020 1021\begin{remark}\label{rem:nonlinear}1022\Srf[\cite{San10}] For a fixed population state the matrix $\rho$ is the rate matrix of a continuous-time1023Markov chain on $S$, and \eqref{eq:mean} is its forward equation $\dot x=xL$. A revision protocol is thus a1024map from states to generators, $x\mapsto L(x)$, and the mean dynamic is $\dot x=x\,L(x)$: a Markov chain whose1025transition rates depend on its own law. The chain describes one agent; the equation describes the1026population. This is the sense in which the continuous models of the source are limits of the finite ones of1027\Cref{ch:finite}.1028\end{remark}1029 1030\begin{proposition}[Imitation gives the replicator equation]\label{prop:ppi}1031\Scl[\cite{Sch98,San10}] Under \emph{pairwise proportional imitation}, $\rho_{ij}=x_j[\pi_j-\pi_i]_+$, the mean1032dynamic is the replicator equation. \chk{O1}1033\end{proposition}1034\begin{proof}1035$\dot x_i=x_i\sum_jx_j\bigl([\pi_i-\pi_j]_+-[\pi_j-\pi_i]_+\bigr)=x_i\sum_jx_j(\pi_i-\pi_j)=x_i(\pi_i-\bar\pi)$.1036\end{proof}1037 1038\noindent The factor $x_j$ is the probability of meeting a $j$-player; the agent needs to know nothing about1039the game except what it and the player it meets have earned. Two rivals, the Brown--von Neumann--Nash (BNN) dynamic and the Smith dynamic, dispense with the meeting.1040\begin{center}\small1041\begin{tabular}{@{}lll@{}}1042\toprule1043dynamic & protocol $\rho_{ij}$ & mean dynamic $\dot x_i$\\1044\midrule1045replicator & $x_j[\pi_j-\pi_i]_+$ & $x_i(\pi_i-\bar\pi)$\\1046BNN & $[\pi_j-\bar\pi]_+=:k_j$ & $k_i-x_i\sum_jk_j$\\1047Smith & $[\pi_j-\pi_i]_+$ & $\sum_j\bigl(x_j[\pi_i-\pi_j]_+-x_i[\pi_j-\pi_i]_+\bigr)$\\1048\bottomrule1049\end{tabular}1050\end{center}1051 1052\section{Imitation is natural and innovation is not}1053 1054Hofbauer and Sandholm isolate four properties of a dynamic $\dot x=V_F(x)$ \cite{HoSa11}; the source1055states them as the hypotheses of its Theorem~8. \emph{Continuity}: $V_F$ depends continuously on $F$.1056\emph{Positive correlation}: $V_F(x)\cdot F(x)>0$ whenever $V_F(x)\ne0$. \emph{Nash stationarity}: $V_F(x)=0$1057exactly at Nash equilibria. \emph{Innovation}: if $x$ is not a Nash equilibrium and an unused strategy is a1058best reply to $x$, that strategy grows.1059 1060\begin{center}\small1061\begin{tabular}{@{}lcccc@{}}1062\toprule1063 & continuity & pos.\ correlation & Nash stationarity & innovation\\1064\midrule1065replicator & yes & yes & no & no\\1066BNN & yes & yes & yes & yes\\1067Smith & yes & yes & yes & yes\\1068\bottomrule1069\end{tabular}1070\end{center}1071 1072\noindent At All-Cooperate in the Prisoner's Dilemma the replicator field vanishes and the other two do1073not \chk{O2}; at every Nash equilibrium of sixty random games both of the others vanish. \chk{O3}1074 1075\begin{theorem}[Hofbauer--Sandholm]\label{thm:hs}1076\Sli[\cite{HoSa11}; source, Theorem 8] For every dynamic satisfying the four properties there is a game with a1077strictly dominated strategy that survives along solutions from most initial conditions.1078\end{theorem}1079 1080\noindent The example has the same shape for every such dynamic: a game with a cycle, and a twin of one1081strategy made slightly worse. In bad Rock--Paper--Scissors (win $1$, loss $2$) with a twin of Scissors that earns1082$0.1$ less, the twin's time-averaged share under the Smith dynamic is $0.116$; under the replicator equation1083it is zero, and \Cref{thm:elim} gives the rate. \chk{O4}1084 1085The functor of \Cref{ch:replicator} explains the difference.1086 1087\begin{proposition}[Names and individuals]\label{prop:names}1088\Sob1089\begin{enumerate}[label=(\alph*)]1090\item Every imitative protocol $\rho_{ij}=x_j\,r(\pi_i,\pi_j)$ has a mean dynamic that is natural for all1091payoff-preserving maps: faces are invariant and clones lump, exactly as in \Cref{cor:three}.1092\item A dynamic that is natural for subgame inclusions leaves every face invariant, so every pure state is a1093rest point. In any game with a pure state that is not a Nash equilibrium it violates Nash stationarity and1094Innovation.1095\item The Brown--von Neumann--Nash and Smith dynamics are natural for symmetries and for neither of the other1096two generating cases of \Cref{def:map}: an absent strategy can appear, and duplicating a strategy changes the