Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 1777–1876 of 2037. Source text is displayed literally.
1777R1 & \Cref{thm:natural} on random games: pushforward along a clone surjection and a subgame inclusion carries solutions to solutions\\1778R2 & \Cref{thm:gradient}: $\frac d{dt}$(mean payoff) $=2\operatorname{Var}$ for symmetric matrices\\1779R3 & \Cref{thm:kl}: $\frac d{dt}\KL{x^*}{x}=-Q_{x^*}(x)$ along numerical solutions\\1780R4 & \Cref{thm:zerosum}: the relative entropy to the centre is conserved, drift $1.3\times10^{-15}$ over time $40$\\1781R5 & \Cref{prop:grps}: eigenvalues $(b-a)/6\pm i\sqrt3(a+b)/6$ against a numerical Jacobian\\1782R6 & good Rock--Paper--Scissors converges to the centre; bad Rock--Paper--Scissors leaves every compact subset of the interior\\1783R7 & every Nash equilibrium of random games is a rest point\\1784R8 & the source's three-strategy game: the unique equilibrium is uniform, asymptotically stable, and not an ESS\\1785R9 & \Cref{thm:elim}: the log-ratio of a dominated twin to its original falls at exactly the penalty\\1786I1 & \Cref{thm:index} on 400 random games with three or four strategies: indices sum to $1$, the number of equilibria is odd\\1787I2 & all 590 ESS found (by Haigh's criterion) have index $+1$\\1788I3 & coordination game: indices $+1,+1,-1$\\1789I4 & \Cref{thm:hodge}: Rock--Paper--Scissors is purely cyclic, a rating difference purely transitive, the parts orthogonal; $\tau=0.558$ for a random game\\1790I5 & the gradient part is a cocycle on every triangle; the cyclic part carries all the curl\\1791I6 & $\frac d{dt}x^{\T}Ax=2\operatorname{Cov}_x(Sx,Ax)$ on random games\\1792I7 & sink components of the invasion graph for three standard games; the small-mutation chain concentrates on them\\1793O1 & \Cref{prop:ppi} on random games and states\\1794O2 & at All-Cooperate the replicator field vanishes and the two direct dynamics do not\\1795O3 & both direct dynamics vanish at every Nash equilibrium of sixty random games\\1796O4 & \Cref{thm:hs}: time-averaged share $0.116$ of a dominated twin under the Smith dynamic; extinction under the replicator\\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 by