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

1757The script \texttt{verify-evolutionary-games.py} that accompanies this volume uses only the Python standard1758library, fixes its random seed, and runs in about ten seconds. It performs 42 checks, each printing1759\texttt{PASS} or \texttt{FAIL} with the computed values, and exits with status zero if and only if all pass.1760The checks recompute the numerical statements of the text and test finite or numerical instances of the1761structural ones. They are evidence that the examples are stated correctly; they do not prove the theorems.1762Differential equations are integrated with a fourth-order Runge--Kutta scheme; fixation probabilities are1763computed exactly, from the product formula or by solving the linear system for absorption.1764 1765{\small1766\begin{longtable}{@{}p{0.08\textwidth}>{\raggedright\arraybackslash}p{0.85\textwidth}@{}}1767\toprule1768Check & What is computed\\1769\midrule1770\endhead1771S1 & Hawk--Dove with $V=2$, $C=4$: $Q_{x^*}(y)=C(p-q)^2/2$ on a grid of states (\Cref{ex:hd})\\1772S2 & Rock--Paper--Scissors: the uniform state is the only Nash equilibrium and is not an ESS\\1773S3 & the source's game with a weakly dominated equilibrium strategy: not an ESS (\Cref{thm:essprops})\\1774S4 & drift game: the neutral equilibrium is left by the replicator flow; time from $0.05$ to $\tfrac12$ is $20.944$\\1775S5 & Hawk--Dove with $V<C$ has exactly one ESS, the mixed one\\1776S6 & \Cref{thm:esset}: over the mixed ESS of Hawk--Dove with Dove duplicated, the fibre is a stable set and no point of it is an ESS\\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$.