Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 2081–2180 of 3949. Source text is displayed literally.
2081 2082Use the birth--death update of Chapter~\ref{ch:markov} at rate \(N\). Its mean field is \(c(n)-x\) by Equation~\eqref{eq:birth-death-drift}. Suppose the weights of present types converge uniformly to bounded strictly positive functions \(f_i(x)\), with a common positive lower bound. The limiting offspring fractions and field are2083\[2084 c_k(x)=\sum_i2085 \frac{x_i f_i(x)}{\overline f(x)}M_{ik},2086 \qquad2087 F_k(x)=c_k(x)-x_k,\qquad2088 \overline f(x)=\sum_i x_i f_i(x).2089\]2090If the weights are Lipschitz, the field is Lipschitz. Its components sum to zero, and \(c_k(x)\geq0\) at a face with \(x_k=0\). A direct form of the integral equation is2091\[2092 x_k(t)=e^{-t}x_k(0)+2093 \int_0^t e^{-(t-s)}c_k(x(s))\,ds .2094\]2095This exhibits the role of the offspring distribution. Invariance of the simplex also follows by constructing the solution locally as the fixed point of this integral map on paths in the simplex, where it is a contraction on short intervals and maps such paths to such paths. Short intervals can be concatenated because the simplex is compact and the constants can be chosen uniformly. With no mutation, \(F_k(x)=x_k(f_k(x)-\overline f(x))/\overline f(x)\). Because \(\overline f(x)>0\), this has the replicator trajectories after a positive change of time. The rates with respect to calendar time differ by this common factor. With mutation, normalization and transmission are combined in \(c\) and need not give a particular additive mutation convention on the replicator equation.2096 2097The distinction between finite and limiting payoffs can be bounded explicitly. For \(n_i>0\) the payoff in Chapter~\ref{ch:markov} satisfies2098\[2099 u_i^N(n)-(Ax)_i=\frac{(Ax)_i-A_{ii}}{N-1}.2100\]2101If \(f_i(n)=\phi(u_i^N(n))\) with a Lipschitz positive map \(\phi\) on the interval covered by the payoffs, the difference from the weight \(\phi((Ax)_i)\) is \(O(N^{-1})\) uniformly over present types. The absent types contribute zero to the birth distribution. Positivity on the compact payoff interval gives a uniform lower bound for the normalization, so the corresponding drift approximation has order \(N^{-1}\). The martingale estimate controls the stochastic error separately at order \(N^{-1/2}\) in root mean square over fixed times.2102 2103\section{When counts close over a graph}2104 2105Suppose the population is an \(N\)-vertex weighted graph. For an oriented pair of vertices \(u,v\), let \(\lambda^N_{uv}\geq0\) be a sampling weight with \(\sum_{u,v}\lambda^N_{uv}=1\). A type \(i\) at \(u\) replaces a type \(j\) at \(v\) at rate \(N\lambda^N_{uv}\varphi(i,j)\), for fixed nonnegative bounded biases \(\varphi\). The relevant statistic is the oriented edge frequency2106\[2107 \theta^N_{ij}(z)=\sum_{u,v}\lambda^N_{uv}2108 \mathbf1_{\{z(u)=i,\ z(v)=j\}}.2109\]2110The density drift on a labeled state \(z\) is2111\(\sum_{i,j}\theta^N_{ij}(z)\varphi(i,j)(e_i-e_j)\), where \(e_i\) is the coordinate unit at \(i\). For a general graph the edge frequencies can vary when the vertex frequencies are fixed. A closed equation for vertex frequencies requires additional information about their evolution.2112 2113An explicit sufficient bound exists for regular weighted sampling. Suppose \(\lambda^N_{uv}=W_{uv}/N\), with \(W\) a nonnegative matrix with row sums one, and write \(J_N\) for the matrix with all entries \(1/N\). If \(\mathbf 1_i\) is the vertex indicator of type \(i\), then2114\[2115 \left|\theta^N_{ij}(z)-x_i x_j\right|2116 = \frac1N\left|\mathbf1_i^{\mathsf T}(W-J_N)\mathbf1_j\right|2117 \leq \|W-J_N\|_{2\to2}\sqrt{x_i x_j}.2118\]2119Thus \(\|W-J_N\|_{2\to2}\to0\) is sufficient for uniform closure of the drift. The proof of Theorem~\ref{thm:egt-fluid} still applies to the projected coordinate processes, using the generator on labeled configurations to obtain their compensators. Uniform drift approximation substitutes for the exact Markov property of the projection.2120\[2121 \begin{tikzcd}[column sep=4.65em]2122 \text{labeled state}\arrow[r,"{\text{observe}}"{above}] &2123 (x,\theta^N)\arrow[r,"{\text{retain counts}}"{above}] & x2124 \end{tikzcd}2125\]2126With uniform sampling of distinct ordered vertices, \(W=(N J_N-I)/(N-1)\). Then \(W-J_N=(J_N-I)/(N-1)\) and its norm is \(1/(N-1)\) for \(N\geq2\). For any graph family satisfying the norm bound, the limiting field is2127\[2128 F(x)=\sum_{i,j}x_i x_j\varphi(i,j)(e_i-e_j).2129\]2130It is Lipschitz on the simplex. Its coordinates sum to zero and each \(F_k(x)\) has the factor \(x_k\), so the simplex is invariant. A density path on labeled configurations therefore converges to this solution under the initial-state hypothesis of Theorem~\ref{thm:egt-fluid}. The omitted edge data may persist on sparse or strongly clustered graphs. One can retain additional observables or prove a separate estimate of their effect. Chapter~\ref{ch:aggregation} gives the criterion for exact Markov closure at each population size.2131\par2132\chapter{Stochastic categories and population aggregation}2133\label{ch:aggregation}2134 2135\section{Kernels as morphisms}2136 2137A state description is useful only when its dynamics can be computed at the level of that description. For the exchangeable population rule in Chapter~\ref{ch:markov}, counts describe a Markov chain exactly. In the network rule of Chapter~\ref{ch:mean-field}, the count drift generally depends on edge frequencies. The category of stochastic kernels gives a common language for these two situations.2138 2139Let \(\mathbf{FinStoch}\) have finite sets as objects and stochastic kernels as morphisms. A kernel \(K:X\rightsquigarrow Y\) assigns to each \(x\in X\) a probability \(K(x,y)\) on \(Y\). The composite of \(K\) and \(H:Y\rightsquigarrow Z\) has entries2140\[2141 (KH)(x,z)=\sum_{y\in Y}K(x,y)H(y,z).2142\]2143Matrix products follow the order in which updates are applied, since laws are row vectors. Identity kernels have entries \(\mathbf 1_{\{x=y\}}\). Matrix associativity is the rule for summing over consecutive unobserved states.2144 2145The monoidal product \(X\times Y\) models joint state spaces, with product kernels given by2146\[2147 (K\otimes H)\big((x,x'),(y,y')\big)=K(x,y)H(x',y').2148\]2149This product applies independent random draws to the two coordinates given their current states. The singleton is monoidal unit and terminal object. Every state space has a deterministic copy operation \(\Delta_X(x)=(x,x)\). A kernel \(K\) preserves copy when \(K\Delta_Y=\Delta_X(K\otimes K)\). On the left, a sample from \(K(x,-)\) is copied. On the right, independent samples are drawn from the same row. Comparing off-diagonal probabilities shows that for distinct \(y,z\) one must have \(K(x,y)K(x,z)=0\). Thus each row is a point mass, and \(K\) comes from a function. Every function preserves copy. This is the deterministic subcategory of \(\mathbf{FinStoch}\), an instance of the distinction between general and deterministic morphisms in a Markov category \cite{fritz-markov}.2150 2151\section{Maps of dynamics}2152 2153A discrete-time system is a pair \((X,P)\) with \(P:X\rightsquigarrow X\). A stochastic map of dynamics from \((X,P)\) to \((Y,Q)\) is a kernel \(K:X\rightsquigarrow Y\) with \(PK=KQ\). The equation says that updating the source and then observing it gives the same law as observing it and applying the target update.2154\[2155\begin{tikzcd}[column sep=large]2156 X \arrow[r,"P"{above}]\arrow[d,"K"{left}] & X\arrow[d,"K"{right}]\\2157 Y \arrow[r,"Q"{above}] & Y2158\end{tikzcd}2159\]2160Iteration gives \(P^nK=KQ^n\) for every \(n\). If \(QH=HR\) as well, then \(P(KH)=(KH)R\), so these maps compose. Equivalently, a system is a functor \(B\mathbb N\to\mathbf{FinStoch}\), where \(B\mathbb N\) has one object and the monoid of nonnegative time steps as its endomorphisms. A stochastic map of dynamics is a natural transformation. The categorical equation for all times is generated by its component at time one.2161 2162If \(\mu P=\mu\), then \((\mu K)Q=\mu PK=\mu K\), so the map transports stationary laws. Independent dynamics can also be composed in parallel. For two maps satisfying \(P_iK_i=K_iQ_i\), the kernel \(K_1\otimes K_2\) intertwines \(P_1\otimes P_2\) and \(Q_1\otimes Q_2\). Here the tensor products of the transitions represent synchronous updates with conditional independence.2163 2164\section{Strong lumpability}2165 2166Let \(q:X\to Y\) be a surjection recording a deterministic statistic, and write \(J(x,y)=\mathbf 1_{\{q(x)=y\}}\). Its values identify blocks \(B_y=q^{-1}(y)\). Strong lumpability requires that the observed process \(q(X_n)\), for a \(P\)-chain \(X_n\), have a fixed Markov update on \(Y\) for every initial law on \(X\). This notion has a block characterization \cite[\S6.3]{kemeny-snell}.2167 2168\begin{theorem}[Strong lumpability]2169For a kernel \(P\) on \(X\), the following are equivalent.2170\begin{enumerate}2171 \item There is a single kernel \(Q\) governing the process \(q(X_n)\) for every initial law.2172 \item There is a kernel \(Q\) on \(Y\) satisfying \(PJ=JQ\).2173 \item For every \(y,y'\) the sum \(\sum_{x'\in B_{y'}}P(x,x')\) is constant for \(x\in B_y\).2174\end{enumerate}2175When these conditions hold, \(Q\) is unique and \(Q(y,y')\) is the common value in the third condition.2176\end{theorem}2177 2178\begin{proof}2179For \(x\in B_y\), the \((x,y')\)-entries of \(PJ\) and \(JQ\) are the block sum and \(Q(y,y')\), respectively. This proves equivalence of the last two conditions because the sums give nonnegative rows of total mass one. Given the original process history, the conditional probability that \(q(X_{n+1})=y'\) is the block sum for \(X_n\). Under the third condition it is \(Q(q(X_n),y')\). Conditioning on the observed history leaves that value unchanged, proving the first condition. Conversely, initialize at a point \(x\) and use the proposed update \(Q\) at time one. Its entry from \(q(x)\) to \(y'\) must equal the block sum from \(x\), hence the block sum agrees for all points in the block.2180\end{proof}