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 2101–2200 of 3949. Source text is displayed literally.

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}2181 2182A Markov description obtained for one specified initial law can depend on the microscopic conditional distributions within the blocks. This weaker statement does not imply an intertwining for deterministic \(J\). For strong lumpability the intertwining suffices to give both the distributional identity \(\mu P^n J=(\mu J)Q^n\) and the assertion about the full observed process in the theorem.2183 2184The quotient also has a factorization property for stochastic maps of dynamics. Suppose \(H:(X,P)\to(Z,R)\) intertwines the updates and its rows are constant on each \(q\)-fiber. Then the unique kernel \(\overline H\) defined by those common rows satisfies \(H=J\overline H\). From \(PH=HR\) and \(PJ=JQ\) one gets \(JQ\overline H=J\overline H R\). Surjectivity of \(q\) lets one cancel \(J\) since left multiplication by \(J\) simply repeats rows. Thus \(Q\overline H=\overline H R\). Every observation of \(X\) determined by the quotient statistic, and compatible with its own time update, factors through the quotient as a map of dynamics.2185 2186\begin{proposition}[Equivariance gives a quotient]2187If a group \(G\) acts on \(X\) and \(P(gx,gx')=P(x,x')\) for every \(g\), the orbit map \(X\to X/G\) is strongly lumpable.2188\end{proposition}2189 2190\begin{proof}2191Every target orbit \(B\) is preserved bijectively by \(g\), so2192\[2193 \sum_{x'\in B}P(gx,x')=\sum_{u\in B}P(gx,gu)2194                       =\sum_{u\in B}P(x,u).2195\]2196The sums therefore depend only on the source orbit.2197\end{proof}2198 2199For site-independent replacement and permutation-invariant payoffs, site permutations act equivariantly on the labeled chain. Their orbits are precisely the configurations with a given strategy-count vector, recovering the population quotient in Chapter~\ref{ch:markov}. In spatial dynamics the relevant permutation group is typically the automorphism group of the weighted interaction graph. Its orbits may record information beyond counts, such as whether a pair of strategy classes frequently meet across graph edges.2200