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

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 of1437$S^G$ are exactly the cellular automata \cite{Hed69}. Local-interaction models on lattices are cellular1438automata whose local rule happens to come from a game.1439\end{remark}1440 1441\section{Why the ring rotates}1442 1443The source places Rock--Paper--Scissors on a ring of nine players in three clusters, $RRR\,PPP\,SSS$, and1444observes that each cluster moves one place per generation, for ever \src{\S4.2.1}. \chk{L1}1445 1446\begin{proposition}\label{prop:ring}1447\Sob Let $\tau$ be rotation of $C_9$ by three places and $c$ the cyclic relabelling1448$R\mapsto P\mapsto S\mapsto R$, which is a symmetry of the game. The configuration $\sigma_0=RRR\,PPP\,SSS$ is1449fixed by the \emph{twisted} symmetry $g\colon\sigma\mapsto c\circ\sigma\circ\tau^{-1}$. The set of1450configurations fixed by $g$ has $27$ elements and is invariant under $U$. Nine of them are the rotations of1451$\sigma_0$, on which $U$ acts as rotation by one place, with period nine; the other eighteen are mapped into1452this orbit by one application of $U$. \chk{L8}1453\end{proposition}1454\begin{proof}1455Invariance is \Cref{cor:covering}(b). A fixed configuration is determined by its values on three consecutive1456vertices, whence $27$. For the motion, score a win $1$, a loss $-1$ and a tie $0$. A player inside a cluster1457scores $0$; at the boundary between the clusters of $R$ and $P$ the $R$-player scores $-1$ and the $P$-player1458$+1$. The losing boundary player sees a neighbour with the top score and adopts its strategy; the winning one1459keeps its own; the middle player of a cluster sees only its own strategy. Each cluster therefore advances one1460place into the cluster it beats and retreats one place from the cluster that beats it. The statement about the