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

941 942\section{Decomposition}943 944Every matrix splits as $A=S+K$ with $S=\tfrac12(A+A^{\T})$ symmetric and $K=\tfrac12(A-A^{\T})$ antisymmetric: a945game of common interest plus a zero-sum game. By \Cref{thm:gradient,thm:zerosum} the replicator field is the946sum of a gradient field and a field that, when $K$ has an interior equilibrium, conserves a relative947entropy. Mean payoff obeys $\frac{d}{dt}x^{\T}Ax=2\operatorname{Cov}_x(Sx,Ax)$. \chk{I6}948 949The antisymmetric part decomposes further, and here the statement is cohomological. Regard an antisymmetric950matrix $K$ as a $1$-cochain on the complete graph with vertex set $S$: $K_{ij}$ is the advantage of $i$ over951$j$.952 953\begin{theorem}[Hodge decomposition of a zero-sum game]\label{thm:hodge}954\Sli[\cite{JLYY11,CMOP11}] Every antisymmetric $K$ decomposes uniquely as955\[ K_{ij}=(r_i-r_j)+C_{ij},\qquad r_i=\tfrac1n\textstyle\sum_jK_{ij},\qquad\textstyle\sum_jC_{ij}=0\ \text{ for all } i . \]956The two parts are orthogonal for the Frobenius inner product. The gradient part satisfies the cocycle condition957$G_{ij}+G_{jk}+G_{ki}=0$ on every triangle, and conversely every antisymmetric matrix satisfying it is a gradient.958The cyclic part $C$ has the same curl $K_{ij}+K_{jk}+K_{ki}$ as $K$ on every triangle.959\end{theorem}960 961\noindent The converse statement is the vanishing of the first cohomology of the full simplex on $S$: a962closed cochain is exact. \chk{I4, I5} We call $\tau(K)=\|G\|^2/\|K\|^2\in[0,1]$ the \term{transitivity index}.963Rock--Paper--Scissors has $\tau=0$ and curl $\pm3$; a game of pure rating differences has $\tau=1$; a random964antisymmetric game on five strategies had $\tau=0.56$.965 966\begin{remark}967If only some pairs of strategies are ever compared, the complete graph is replaced by a comparison graph968with its triangles, and its first cohomology need not vanish. A third, \emph{harmonic}, component appears:969cyclic advantage around a loop that bounds no triangle, locally consistent and globally not a rating. This970is the only place in the volume where a cohomology group is not zero for a trivial reason.971\end{remark}972 973\section*{Notes}974 975The index theorem for the replicator equation is in \cite[Ch.~13]{HoSi98}; the perturbation argument is976Hofbauer's. Conley's theory is in \cite{Con78}, with an accessible account of the index in \cite{Sal85}. Chain977recurrence as a solution concept for games is argued in \cite{PaPi19}. The Hodge decomposition of pairwise978comparison data is from \cite{JLYY11}; its game-theoretic form for general finite games, into potential,979harmonic and non-strategic parts, is from \cite{CMOP11}; the use of the transitive and cyclic parts in the980evaluation of agents is from \cite{BTP18}.981 982\section*{Exercises}983 984\begin{exercise}\label{exer:index2}985Compute the index of each equilibrium of the three generic classes of two-strategy games in the table of986\Cref{ch:replicator}, and verify \Cref{thm:index}.987\end{exercise}988 989\begin{exercise}\label{exer:curl}990Show that an antisymmetric $K$ is a gradient if and only if its curl vanishes on all triangles through one991fixed vertex.992\end{exercise}993 994\begin{exercise}\label{exer:tau}995Compute the Hodge decomposition and the transitivity index of the antisymmetric game on three strategies996with $K_{12}=1$, $K_{23}=1$, $K_{13}=t$, as a function of $t$.997\end{exercise}998 999\begin{exercise}\label{exer:invgraph}1000Determine the invasion graph and its sink components for the Hawk--Dove game with $V<C$. What do they miss?1001\end{exercise}1002%% ---- end ch/04-index.tex ----1003%% ---- begin ch/05-protocols.tex ----1004\chapter{Revision Protocols, Other Dynamics, and Open Systems}\label{ch:protocols}1005 1006The replicator equation is one dynamic among many. The source derives it a second time from imitation,1007introduces two rivals, and reports a theorem that separates them \src{\S3.2.2, \S3.3}. This chapter places all1008three in one frame and then takes the frame apart into components.1009 1010\section{Revision protocols}1011 1012A \term{population game} is a continuous map $F\colon\Dist(S)\to\R^S$; the linear case $F(x)=Ax$ is the1013symmetric game $(S,A)$. Following Sandholm \cite{San10}, a \term{revision protocol} is a continuous map1014\[ \rho\colon\R^S\times\Dist(S)\longrightarrow\R_{\ge0}^{S\times S}, \]1015where $\rho_{ij}(\pi,x)$ is the rate at which a player of strategy $i$ switches to $j$ when payoffs are $\pi$ and1016the state is $x$; the \term{mean dynamic} it induces is1017\begin{equation}\label{eq:mean}1018\dot x_i=\sum_jx_j\,\rho_{ji}(F(x),x)-x_i\sum_j\rho_{ij}(F(x),x).1019\end{equation}1020 1021\begin{remark}\label{rem:nonlinear}1022\Srf[\cite{San10}] For a fixed population state the matrix $\rho$ is the rate matrix of a continuous-time1023Markov chain on $S$, and \eqref{eq:mean} is its forward equation $\dot x=xL$. A revision protocol is thus a1024map from states to generators, $x\mapsto L(x)$, and the mean dynamic is $\dot x=x\,L(x)$: a Markov chain whose1025transition rates depend on its own law. The chain describes one agent; the equation describes the1026population. This is the sense in which the continuous models of the source are limits of the finite ones of1027\Cref{ch:finite}.1028\end{remark}1029 1030\begin{proposition}[Imitation gives the replicator equation]\label{prop:ppi}1031\Scl[\cite{Sch98,San10}] Under \emph{pairwise proportional imitation}, $\rho_{ij}=x_j[\pi_j-\pi_i]_+$, the mean1032dynamic is the replicator equation. \chk{O1}1033\end{proposition}1034\begin{proof}1035$\dot x_i=x_i\sum_jx_j\bigl([\pi_i-\pi_j]_+-[\pi_j-\pi_i]_+\bigr)=x_i\sum_jx_j(\pi_i-\pi_j)=x_i(\pi_i-\bar\pi)$.1036\end{proof}1037 1038\noindent The factor $x_j$ is the probability of meeting a $j$-player; the agent needs to know nothing about1039the game except what it and the player it meets have earned. Two rivals, the Brown--von Neumann--Nash (BNN) dynamic and the Smith dynamic, dispense with the meeting.1040\begin{center}\small