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

1197 1198\section*{Exercises}1199 1200\begin{exercise}\label{exer:dissat}1201Show that \emph{imitation driven by dissatisfaction}, $\rho_{ij}=x_j(K-\pi_i)$ with $K$ larger than every payoff,1202also has the replicator equation as its mean dynamic.1203\end{exercise}1204 1205\begin{exercise}\label{exer:bnnrest}1206Show directly that the rest points of the Brown--von Neumann--Nash dynamic are exactly the Nash equilibria.1207\end{exercise}1208 1209\begin{exercise}\label{exer:softmax}1210Prove \Cref{prop:softmax}.1211\end{exercise}1212 1213\begin{exercise}\label{exer:bos}1214Write the two-population replicator equations for the Battle of the Sexes above in the coordinates $(x,y)$,1215and verify the eigenvalues $\pm\tfrac23$ at the mixed equilibrium.1216\end{exercise}1217%% ---- end ch/05-protocols.tex ----1218\part{Structure}1219%% ---- begin ch/06-finite.tex ----1220\chapter{Finite Populations}\label{ch:finite}1221 1222A real population is finite, and in a finite population chance decides what the differential equation leaves1223open. The source's model is the frequency-dependent birth--death process \src{\S4.1}. Its analysis is1224classical, and we shall say plainly at the end how little the categorical language adds to it. What it does1225add is a precise statement of the one point at which the source draws a conclusion that needs qualifying.1226 1227\section{The Moran process}1228 1229Two strategies $A$ and $B$ have payoffs $\begin{psmallmatrix}a&b\\c&d\end{psmallmatrix}$, all positive. In a population1230of $N$ with $i$ players of type $A$, the expected payoffs against a randomly chosen other player are1231\[ F_i=\frac{a(i-1)+b(N-i)}{N-1},\qquad G_i=\frac{c\,i+d(N-i-1)}{N-1}, \]1232and the fitnesses are $f_i=1-w+wF_i$, $g_i=1-w+wG_i$ for an intensity of selection $w\in(0,1]$. At each step one1233individual is chosen to reproduce with probability proportional to fitness, and its offspring replaces a1234uniformly chosen individual. The number of $A$-players is a Markov chain on $\{0,\dots,N\}$, that is, an1235endomorphism in $\FinStoch$, with1236\[ p_i^+=\frac{if_i}{if_i+(N-i)g_i}\cdot\frac{N-i}{N},\qquad p_i^-=\frac{(N-i)g_i}{if_i+(N-i)g_i}\cdot\frac iN, \]1237and $0$ and $N$ absorbing.1238 1239\begin{theorem}[Fixation]\label{thm:fix}1240\Scl[\cite{Mor58,Now06}] The probability that a single $A$-player takes over the population is1241\[ \rho_A=\Bigl(1+\sum_{k=1}^{N-1}\prod_{i=1}^{k}\frac{g_i}{f_i}\Bigr)^{-1}. \]1242\end{theorem}1243\begin{proof}1244The probability $h_i$ of absorption at $N$ from $i$ is the harmonic function with $h_0=0$, $h_N=1$. Harmonicity1245gives $h_{i+1}-h_i=(p_i^-/p_i^+)(h_i-h_{i-1})=(g_i/f_i)(h_i-h_{i-1})$, and the differences telescope.1246\end{proof}1247 1248\noindent For constant fitness $r$ of the mutant relative to the resident this is $\rho=(1-r^{-1})/(1-r^{-N})$, and1249$\rho=1/N$ in the neutral case. \chk{F3}1250 1251The source tabulates the fixation probability $\rho_B$ of a single defector in the Prisoner's Dilemma1252$a=3$, $b=1$, $c=4$, $d=2$ with $w=1$. The formula above, with self-interaction excluded as in the1253definition of $F_i$ and $G_i$, reproduces the table; if a player may meet itself the values differ in the1254second decimal place at $N=10$ and have the same limit. \chk{F1}1255\begin{center}1256\begin{tabular}{@{}lccccc@{}}1257\toprule1258$N$ & $10$ & $10^2$ & $10^3$ & $10^4$ & $10^5$\\1259\midrule1260source & $0.34263$ & $0.25879$ & $0.25088$ & $0.25009$ & $0.25001$\\1261computed, no self-play & $0.34263$ & $0.25879$ & $0.25088$ & $0.25009$ & not run\\1262computed, self-play & $0.30163$ & $0.25500$ & $0.25050$ & $0.25005$ & not run\\1263\bottomrule1264\end{tabular}1265\end{center}1266 1267\begin{proposition}[The limit]\label{prop:limit}1268\Scl If $B$ strictly dominates $A$ ($c>a$ and $d>b$) and $w=1$, then $\rho_B\to1-a/c$ as $N\to\infty$.1269\end{proposition}1270\begin{proof}1271For $\rho_B$ the ratios in \Cref{thm:fix} are those of resident to mutant fitness. With $j$ mutants and1272$N\to\infty$ the $j$-th ratio tends to $a/c$, and by dominance all ratios are bounded by some $\theta<1$ for1273large $N$, uniformly in the composition. Dominated convergence gives1274$\rho_B^{-1}\to\sum_{k\ge0}(a/c)^k=(1-a/c)^{-1}$.1275\end{proof}1276 1277\noindent With $a=3$ and $c=4$ the limit is $\tfrac14$. \chk{F2} The number $1-a/c$ is the survival probability1278of a branching process in which each mutant has relative fitness $c/a$: while mutants are rare they meet only1279residents, and their lineage either dies out early or escapes.1280 1281\section{Two limits that do not commute}1282 1283The source concludes from $\rho_B\to\tfrac14$ that ``the replicator dynamics cannot be the limit of the1284birth-death process'', since under the replicator dynamics any positive fraction of defectors takes over with1285certainty \src{\S4.1}. The observation is correct. The conclusion holds for one order of limits and fails for1286the other.1287 1288\begin{theorem}[Mean-field limit]\label{thm:kurtz}1289\Scl[\cite{Kur70,TCH05}] Fix an initial \emph{fraction} $x_0\in(0,1)$ and a time horizon $T$, measured in1290generations of $N$ steps. As $N\to\infty$ the frequency of $A$ in the Moran process converges in probability,1291uniformly on $[0,T]$, to the solution of the \emph{adjusted replicator equation}1292\[ \dot x=\frac{x(1-x)\bigl(F(x)-G(x)\bigr)}{xF(x)+(1-x)G(x)}, \]1293with fluctuations of order $N^{-1/2}$.1294\end{theorem}1295 1296\noindent The adjusted equation has the same orbits as \eqref{eq:two} and a different clock. For a Hawk--Dove