Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 1797–1896 of 2037. Source text is displayed literally.
1797O5 & Battle of the Sexes with two populations: the mixed equilibrium is a rest point, and forty nearby orbits end at the two pure equilibria\\1798O6 & \Cref{prop:softmax} against a numerical solution\\1799O7 & \Cref{prop:names}(c): defect of naturality under cloning, $4\times10^{-17}$ for the replicator, $0.555$ for Smith, $0.380$ for Brown--von Neumann--Nash\\1800F1 & the source's table of fixation probabilities, with and without self-interaction\\1801F2 & \Cref{prop:limit}: the limit $1-a/c=\tfrac14$\\1802F3 & neutral and constant-fitness fixation\\1803F4 & \Cref{thm:third} against exact fixation in 299 random coordination games, $N=60$\\1804F5 & \Cref{thm:kurtz}: root-mean-square deviation $0.158$, $0.084$, $0.040$ at $N=50,200,800$\\1805L1 & ring of nine: rotation by one place per round, period nine\\1806L2 & \Cref{thm:covering} for $C_9\to C_3$, all $27$ configurations\\1807L3 & equivariance under rotations, reflections and relabelling on random configurations; the twisted symmetry fixes the wave\\1808L4 & \Cref{thm:iso}: complete graph and cycle\\1809L5 & star and directed line at $N=6$ (exact)\\1810L6 & \Cref{prop:thresholds} at $b=1.1$, $1.7$, $2.1$\\1811L7 & the source's matrix on the $1,2$-circulant and on the ring; the cycle $1,5,3$\\1812L8 & \Cref{prop:ring}: all $27$ symmetric configurations; a frozen configuration outside them\\1813\bottomrule1814\end{longtable}}1815 1816\noindent Two discrepancies with the source were looked for and one convention was found. The source's fixation table1817is reproduced to all printed digits only if a player does not interact with itself (F1). No tie rule for1818imitate-the-best was found in the source; with the rule of \Cref{ch:local} its described runs are reproduced1819(L1, L7), and a frozen configuration exists that its text does not mention (L8).1820%% ---- end ch/C-computations.tex ----1821%% ---- begin ch/D-solutions.tex ----1822\chapter{Solutions to the Exercises}\label{app:solutions}1823 1824Solutions to all exercises follow, by chapter. Where a solution relies on a computation, the computation is1825also carried out by \texttt{verify-evolutionary-games.py}.1826 1827\section*{Chapter 1}1828 1829\sol{1.1} By affineness in the first argument,1830$\pay{y_\epsilon}{y_\epsilon}=(1-\epsilon)\pay{x}{y_\epsilon}+\epsilon\,\pay{\mu}{y_\epsilon}$. Subtract from1831$\pay{x}{y_\epsilon}$.1832 1833\sol{1.2} A symmetry is a permutation that preserves who beats whom. For Rock--Paper--Scissors the three1834rotations do, and a transposition reverses the cycle, so the group is $\Z/3$. For the five-strategy game1835the translations give $\Z/5$. A symmetry is an automorphism of a tournament, and such groups have odd order,1836since an involution would exchange two strategies and so reverse the result between them. A subgroup of the1837symmetric group on five letters of odd order containing a $5$-cycle has order $5$ or $15$, and there is no1838subgroup of order $15$, since it would be cyclic. The group is $\Z/5$.1839 1840\sol{1.3} Subtract $(V-C)/2$ from the first column and $V/2$ from the second:1841$\begin{psmallmatrix}0&V/2\\(C-V)/2&0\end{psmallmatrix}$, so $a=V/2$ and $b=(C-V)/2$. For $V<C$ both are positive:1842neither pure state is an equilibrium and the mixed equilibrium has Hawk at frequency $a/(a+b)=V/C$. For1843$V>C$, $a>0>b$: Hawk strictly dominates and All-Hawk is the only equilibrium.1844 1845\sol{1.4} By \Cref{prop:nashmaps}(a) applied to the clone map onto Hawk--Dove, the equilibria are exactly the1846states whose image is the mixed equilibrium: $(V/C,\,s,\,1-V/C-s)$ with $0\le s\le1-V/C$. They form a segment.1847 1848\section*{Chapter 2}1849 1850\sol{2.1} If $x$ is strict, then $\pay{x}{x}>\pay{y}{x}$ for $y\ne x$, which is the first clause of the definition.1851In a two-strategy game let $x$ be a pure ESS, say the first strategy. It is an equilibrium, so $A_{11}\ge A_{21}$,1852and by hypothesis the inequality is strict; then $x$ is strict. An ESS that is not pure is interior.1853 1854\sol{2.2} The uniform state is an interior equilibrium, so by \Cref{thm:essprops}(f) it is an ESS if and only if1855$z^{\T}Az<0$ for $z\ne0$ with $\sum_sz_s=0$. Here $z^{\T}Az=(a-b)(z_1z_2+z_2z_3+z_3z_1)$ and1856$z_1z_2+z_2z_3+z_3z_1=-\tfrac12|z|^2$ on that plane, so $z^{\T}Az=-\tfrac{a-b}2|z|^2$, negative exactly when $a>b$.1857 1858\sol{2.3} The identity matrix: each pure strategy is a strict equilibrium, hence an ESS, and1859$\binom31=3$.1860 1861\sol{2.4} Write $y=(1-q,q)$, with $q$ the weight on the second strategy. For $x$ the first pure strategy,1862$\pay{x}{y}=1+99q$ and $\pay{y}{y}=(1-q)(1+99q)+100q^2$, so $\Q_x(y)=q(1+99q)-100q^2=q(1-q)>0$ for $0<q<1$: an ESS. For1863$x$ the second, with $p=1-q$ the weight on the first, $\Q_x(y)=-p^2<0$: not an ESS, although it is an equilibrium.1864 1865\section*{Chapter 3}1866 1867\sol{3.1} With payoffs $\begin{psmallmatrix}0&a\\b&0\end{psmallmatrix}$ and state $(x,1-x)$, the two strategies1868earn $a(1-x)$ and $bx$, and $\dot x=x(1-x)\bigl(a(1-x)-bx\bigr)$. For $\dot x=x^2(1-x)$, partial fractions give1869$\int\frac{dx}{x^2(1-x)}=-\frac1x+\log\frac{x}{1-x}$; evaluate between $x_0$ and $x_1$.1870 1871\sol{3.2} $\frac d{dt}x^{\T}Ax=\dot x^{\T}(A+A^{\T})x=2\sum_sx_s\bigl((Ax)_s-x^{\T}Ax\bigr)(Sx)_s1872=2\operatorname{Cov}_x(Sx,Ax)$, because $\sum_sx_s\bigl((Ax)_s-x^{\T}Ax\bigr)=0$. For symmetric $A$ this is twice the1873variance of $Ax$.1874 1875\sol{3.3} At the uniform state the linearization on the tangent plane is $\tfrac13A$ composed with the projection1876along $\one$. In the basis of the two complex eigenvectors of the cyclic shift, $A$ acts by1877$a\omega+(-b)\bar\omega$ and its conjugate, with $\omega=e^{2\pi i/3}$, so the eigenvalues are1878$\tfrac13(a\omega-b\bar\omega)$ and its conjugate: real part $\tfrac13\cdot\tfrac{-a+b}{2}$, imaginary part1879$\pm\tfrac13\cdot\tfrac{\sqrt3}2(a+b)$. The trace is $(b-a)/3$ and the determinant1880$\bigl((b-a)^2+3(a+b)^2\bigr)/36$.1881 1882\sol{3.4} By \Cref{cor:three}(b) the class frequencies follow the replicator equation of Rock--Paper--Scissors1883from the initial state $(\tfrac12,\tfrac14,\tfrac14)$. By \Cref{thm:zerosum} they move on the closed curve1884on which the relative entropy to the centre is constant, equivalently on which the product of the three1885frequencies equals $\tfrac1{32}$. The two variants of Rock keep equal shares.1886 1887\section*{Chapter 4}1888 1889\sol{4.1} Let $F(x)=x(1-x)\bigl(a-(a+b)x\bigr)$; the index at an equilibrium is the sign of $-F'$. For $a>0>b$ the1890only equilibrium is $x=1$, with $F'(1)=b<0$: index $+1$. For $a,b>0$ the only equilibrium is1891$x^*=a/(a+b)$, with $F'(x^*)=-(a+b)x^*(1-x^*)<0$: index $+1$. For $a,b<0$ the equilibria are $0$, $1$ and $x^*$,1892with $F'(0)=a<0$, $F'(1)=b<0$ and $F'(x^*)>0$: indices $+1,+1,-1$. The sum is $1$ in each case.1893 1894\sol{4.2} A gradient has zero curl on every triangle. Conversely, if the curl vanishes on triangles through1895the vertex $0$, put $r_i=K_{i0}$. Then $K_{ij}+K_{j0}+K_{0i}=0$ gives $K_{ij}=K_{i0}-K_{j0}=r_i-r_j$.1896