Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 1441–1540 of 2037. Source text is displayed literally.
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 when1497$4R>2T+2P$; cooperator $3$ sees only cooperators and player $0$ is out of its sight.1498\end{proof}1499 1500With $R=1$, $P=S=0$ and $T=b$ the thresholds are $b=\tfrac32$ and $b=2$. Starting from six cooperators among1501thirty players, the cluster grew by two per round for $b=1.1$, stayed at six for $b=1.7$, and vanished in1502two rounds for $b=2.1$. \chk{L6} For the source's matrix $(T,R,P,S)=(1.1,1,0,-0.1)$ the first inequality reads1503$2.9>2.2$, which are the two scores the source quotes for the cooperator and the boundary defector. The1504simulation then reproduces the rest of the source's account: the cooperators spread until one defector1505remains; the lone defector scores $4T=4.4$ and converts its four neighbours; the block of five defectors1506shrinks to three and to one; and the number of defectors cycles $1,5,3$ for ever. On the simple ring the same1507cluster is frozen for this matrix and eroded for the source's second matrix $(1.5,1,0.6,0)$, as the source1508states. \chk{L7}1509 1510\begin{remark}1511The mechanism is visible in the proof: cooperation spreads when the cooperator one step behind the front,1512who has three cooperating neighbours, outscores the defector at the front, who exploits two. On the simple1513ring there is no such player. The source's caution that results of this kind depend on the neighbourhood, the1514payoffs and the update rule is exactly right, and the proposition says how: through three linear inequalities1515that change with each of them.1516\end{remark}1517 1518\section{Graphs that amplify and suppress selection}1519 1520For constant fitness the Moran process can be run on a weighted directed graph: an individual at $i$,1521chosen in proportion to fitness, places its offspring at $j$ with probability $w_{ij}$, where $W$ is a1522stochastic matrix.1523 1524\begin{theorem}[Isothermal theorem]\label{thm:iso}1525\Sli[\cite{LHN05}] The fixation probability of a single mutant of fitness $r$, placed uniformly at random,1526equals the Moran value $(1-r^{-1})/(1-r^{-N})$ for every $r$ if and only if $W$ is doubly stochastic.1527\end{theorem}1528 1529\noindent A doubly stochastic matrix is a stochastic map that preserves the uniform distribution, so the1530isothermal graphs are the endomorphisms of the probability space $(V,\text{uniform})$ in $\FinStoch$. For them1531the number of mutants is itself a birth--death chain with ratio $r$ (\Cref{exer:iso}), and structure is1532invisible to selection: on the complete graph and on the cycle the computed fixation probabilities agree1533with the Moran value to ten digits. \chk{L4} Other graphs change the balance between selection and drift.1534\begin{center}1535\begin{tabular}{@{}lccc@{}}1536\toprule1537$N=6$ & well-mixed & star & directed line\\1538\midrule1539advantageous mutant, $r=1.5$ & $0.3654$ & $0.4432$ & $0.1667$\\1540disadvantageous mutant, $r=0.7$ & $0.0571$ & $0.0333$ & $0.1667$\\