Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 1397–1496 of 2037. Source text is displayed literally.
1397periods 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 the1461other eighteen configurations is by enumeration.1462\end{proof}1463 1464\noindent The pattern is a discrete rotating wave: a relative equilibrium, fixed by the dynamics up to a1465symmetry. The twisted symmetry accounts for the shape of the pattern, three clusters in cyclic order, and the1466local computation for its speed. By \Cref{cor:covering}(a) the same wave runs on every ring of $9k$ players,1467and patterns with clusters of other sizes are waves for other twisted symmetries. Within the symmetric set1468the wave is the only possible long-run behaviour, which is more than symmetry alone could give. The source1469remarks that on a ring the only outcomes are cycling and uniformity. With the tie rule adopted here there is a1470third: the configuration $RPS\,RPS\,RPS$, in which every player beats one neighbour and loses to the other, is1471a fixed point, since all scores are equal. We found no tie rule stated in the source, and the remark may be1472correct for the rule used there; the example shows that it depends on one.1473 1474\section{Cooperation at the boundary}1475 1476Now let $S=\{C,D\}$ with the Prisoner's Dilemma payoffs $T>R>P>S$ (temptation, reward, punishment,1477sucker). On the simple ring a cluster of cooperators cannot grow. On the \term{$1,2$-circulant}, where each1478player has the two nearest players on each side as neighbours, it can \src{\S4.2.2}.1479 1480\begin{proposition}[Thresholds on the $1,2$-circulant]\label{prop:thresholds}1481\Sob Consider a run of at least five cooperators next to a run of at least five defectors. Under1482imitate-the-best the boundary between them1483\begin{center}1484\begin{tabular}{@{}ll@{}}1485moves into the defectors, one place per round, & if $3R+S>2T+2P$;\\1486is stationary & if $3R+S<2T+2P<4R$;\\1487moves into the cooperators, two places per round, & if $2T+2P>4R$.1488\end{tabular}1489\end{center}1490\end{proposition}1491\begin{proof}1492Number the cooperators $1,2,3,\dots$ from the boundary and the defectors $0,-1,-2,\dots$. The scores are1493\begin{align*} u_1&=2R+2S, & u_2&=3R+S, & u_3&=4R,\\ u_0&=2T+2P, & u_{-1}&=T+3P, & u_{-2}&=4P . \end{align*}1494Defector $0$ sees players $-2,\dots,2$: the best defector it sees is itself and the best cooperator is player $2$,1495so it switches exactly when $3R+S>2T+2P$. Defector $-1$ sees player $0$, who outscores the only cooperator in1496view, and stays; the remaining defectors see no cooperator. Cooperators $1$ and $2$ both see defector $0$ and cooperator $3$, and stay exactly when