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

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 ----1381\chapter{Local Interaction}\label{ch:local}1382 1383In the last part of the source the population lives on a graph: each player meets only its neighbours and1384learns only from them \src{\S4.2}. The models are simulated, and the source is candid that their behaviour is1385sensitive to details. This is the chapter in which structure helps most, because a graph has maps, and the1386maps explain patterns that the simulations display.1387 1388\section{The model}1389 1390Let $\Gamma$ be a finite graph with vertex set $V$, and $(S,A)$ a game. A \term{configuration} is a map1391$\sigma\colon V\to S$. The score of $v$ is $u_v(\sigma)=\sum_{w\sim v}A_{\sigma(v)\sigma(w)}$. Under1392\term{imitate-the-best} every player simultaneously adopts the strategy of the highest scorer among itself and1393its neighbours. Ties need a rule, and we take one that uses no labels: a player keeps its strategy if that1394strategy is among the best, or if the best scorers disagree. This defines a map1395\[ U_\Gamma\colon S^V\longrightarrow S^V, \]1396a discrete dynamical system on a finite set. Every orbit is eventually periodic, and the questions are which1397periods occur and why.1398 1399\section{Coverings}1400 1401A \term{covering} $p\colon\tilde\Gamma\to\Gamma$ is a graph homomorphism that maps the neighbours of each vertex1402bijectively onto the neighbours of its image. The ring $C_{kn}$ covers $C_n$ for $n\ge3$; the infinite line1403covers every ring; a torus covers a smaller torus; the square lattice covers them all.1404 1405\begin{theorem}[Naturality under coverings]\label{thm:covering}1406\Sob For a covering $p\colon\tilde\Gamma\to\Gamma$ the pullback $p^*\colon S^V\to S^{\tilde V}$,1407$\sigma\mapsto\sigma\circ p$, commutes with the update:1408\[ U_{\tilde\Gamma}\circ p^*=p^*\circ U_\Gamma . \]1409Hence $\Gamma\mapsto(S^V,U_\Gamma)$ is a contravariant functor from graphs and coverings to dynamical systems.1410The same holds for every update rule in which a player's new strategy is a function of the labelled tree of1411walks of some fixed length starting at that player; imitate-the-best uses walks of length two.1412\end{theorem}1413\begin{proof}1414Since $p$ is bijective on neighbourhoods, $u_{\tilde v}(\sigma\circ p)=u_{p(\tilde v)}(\sigma)$ for every $\tilde v$.1415Applying this at $\tilde v$ and at each of its neighbours, the pairs (strategy, score) seen by $\tilde v$ are1416those seen by $p(\tilde v)$, with multiplicity. The update depends on nothing else.1417\end{proof}1418 1419\begin{corollary}\label{cor:covering}1420\begin{enumerate}[label=(\alph*)]