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

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*)]1421\item Every orbit on $\Gamma$ lifts to an orbit on every cover. The configurations on the ring $C_{kn}$ that1422repeat with spatial period $n$ are exactly the pullbacks of configurations on $C_n$, and they evolve as they do1423there. \chk{L2}1424\item The automorphisms of $\Gamma$ and the symmetries of the game act on $S^V$ and commute with $U_\Gamma$; the1425fixed set of every group of such symmetries is invariant. \chk{L3}1426\item What happens on a small ring or torus happens on every larger one that covers it, and on the infinite1427lattice. A phenomenon found in simulation on a $30\times30$ torus that survives restriction to a1428$3\times3$ or $6\times6$ torus can be analysed there by hand.1429\end{enumerate}1430\end{corollary}1431 1432\begin{remark}1433\Sli[\cite{DeLe15,GoSt06}] For continuous-time systems on networks this is the theorem of DeVille and Lerman1434that fibrations of graphs induce maps of dynamical systems, and the invariant subspaces of (b) are the1435synchrony subspaces of Golubitsky and Stewart. On a Cayley graph the statement that $U$ commutes with1436translations is half of the Curtis--Hedlund--Lyndon theorem: the continuous translation-equivariant self-maps of