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

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--Dove1297game with background fitness the root-mean-square deviation from the solution at $T=4$ was $0.158$, $0.084$1298and $0.040$ at $N=50$, $200$ and $800$: it halves when $N$ is quadrupled. \chk{F5}1299 1300\begin{remark}[Which limit]\label{rem:limits}1301\Sob Write $\Phi_N(x_0,t)$ for the law of the frequency at generation $t$ from initial fraction $x_0$. The1302replicator dynamics is the limit $N\to\infty$ with $x_0$ and $t$ fixed. Fixation of a single mutant is the limit1303$t\to\infty$ first, at $x_0=1/N$, and then $N\to\infty$; here the initial fraction tends to zero, the limiting1304differential equation starts at the rest point $x=0$ and never leaves, and the outcome is decided in a boundary1305layer of width $O(1/N)$ where the population is a branching process and not a flow. The two descriptions1306compose: a defector lineage escapes the layer with probability $1-a/c$ and, having escaped, is carried to1307fixation by the flow with probability tending to one. The square1308\[ \begin{tikzcd}[column sep=large]1309\Phi_N(x_0,t)\ar[r,"N\to\infty"]\ar[d,"t\to\infty"'] & \varphi_t(x_0)\ar[d,"t\to\infty"]\\1310\text{fixation law}\ar[r,"N\to\infty"'] & \text{?}1311\end{tikzcd} \]1312commutes for each fixed $x_0>0$ in the Prisoner's Dilemma and fails along $x_0=1/N$. The replicator dynamics1313is a limit of the birth--death process, and it is not the limit that computes invasion from one mutant.1314\end{remark}1315 1316\section{Weak selection}1317 1318\begin{theorem}[The one-third law]\label{thm:third}1319\Sli[\cite{NSTF04}] For $w\to0$, selection favours the fixation of $A$, in the sense $\rho_A>1/N$, if and only if1320\[ a(N-2)+b(2N-1)>c(N+1)+d(2N-4). \]1321For a coordination game ($a>c$, $d>b$) and large $N$ this holds if and only if the unstable equilibrium1322$x^*=(d-b)/(a-c+d-b)$ of the replicator equation, the frequency of $A$ at the barrier between the two1323conventions, is below $\tfrac13$.1324\end{theorem}1325 1326\noindent The condition was confirmed against exact fixation probabilities in 299 random coordination games1327at $N=60$. \chk{F4} The constant has a simple origin: to first order in $w$ the advantage $h(x)=F-G$ is1328weighted by the number of visits that a neutral lineage started from one mutant pays to frequency $x$, which1329is proportional to $1-x$, and $\int_0^1(\alpha x-\beta)\,2(1-x)\,dx=\alpha/3-\beta$. A convention can thus be invaded by a single1330mutant, with probability above the neutral one, exactly when its basin under the deterministic dynamics is1331smaller than a third; the replicator equation alone says only that it cannot be invaded at all.1332 1333\section{Rare mutations}1334 1335Add mutation at a small rate $\mu$. The chain becomes ergodic, and as $\mu\to0$ its stationary distribution1336concentrates on the monomorphic states, where it is the stationary distribution of the \emph{embedded chain}1337that jumps from all-$i$ to all-$j$ with probability proportional to the fixation probability $\rho_{i\to j}$1338of a single $j$-mutant \cite{FuIm06}. For large populations and strong selection this chain moves only along the1339edges of the invasion graph of \Cref{ch:index} and its stationary distribution is carried by the sink1340components: all of Rock--Paper--Scissors, either convention of a coordination game, defection in the Prisoner's1341Dilemma. \chk{I7} This is the finite-population counterpart of the chain components of \Cref{thm:conley}, and1342it is the construction used to rank learning agents by Markov--Conley chains \cite{OPP19}. Stochastic1343stability in the sense of \cite{KMR93,You93} is the same idea for best-reply dynamics, where the selected1344convention is the risk-dominant one.1345 1346\begin{remark}[What the language adds here]1347Not much. A finite-population model is a morphism in $\FinStoch$; fixation is a harmonic function; the1348embedded chain is a functor from games to Markov chains that is natural for symmetries and, like the direct1349protocols of \Cref{prop:names}, not for cloning (an example is computed in the companion paper \cite{EGML}). The content of the chapter is analytic, and the one structural1350point is \Cref{rem:limits}.1351\end{remark}1352 1353\section*{Notes}1354 1355The frequency-dependent Moran process and its fixation probabilities are in \cite{NSTF04,Now06}; the original1356process is Moran's \cite{Mor58}. Density-dependent Markov chains and their differential-equation limits are due1357to Kurtz \cite{Kur70}; the identification of the limit of the Moran process with the adjusted replicator1358equation is in \cite{TCH05}. The one-third law is from \cite{NSTF04}. The small-mutation limit is treated in1359\cite{FuIm06}.1360 1361\section*{Exercises}1362 1363\begin{exercise}\label{exer:neutral}1364Show without the formula that neutral fixation has probability $1/N$.1365\end{exercise}1366 1367\begin{exercise}\label{exer:constant}1368Derive $\rho=(1-r^{-1})/(1-r^{-N})$ from \Cref{thm:fix}.1369\end{exercise}1370 1371\begin{exercise}\label{exer:third}1372Deduce the large-population form of the one-third law from the inequality in \Cref{thm:third}.1373\end{exercise}1374 1375\begin{exercise}\label{exer:coopfix}1376For the Prisoner's Dilemma of the source's table, show that the fixation probability of a single cooperator is1377smaller than $(3/4)^{N-1}$.1378\end{exercise}1379%% ---- end ch/06-finite.tex ----1380%% ---- begin ch/07-local.tex ----