Indexed text attachment
evolutionary-game-theory-in-higher-categories.tex
Source for Evolutionary Game Theory in Higher Categories
View paper · Download original file
Lines 2161–2260 of 3949. Source text is displayed literally.
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 2201\section{Generators and approximate quotients}2202 2203A continuous-time finite-state chain has generator \(L_X\) with nonnegative off-diagonal entries and zero row sums. A deterministic quotient intertwines the semigroups at every time if and only if \(L_XJ=JL_Y\). Differentiation at zero gives necessity. For sufficiency the generator equation gives \(L_X^kJ=JL_Y^k\) by induction, and the result follows from the exponential series. Thus a quotient generator exists when each generator block sum is constant on a source block. For off-diagonal blocks the contributing entries are nonnegative. Row sums of the quotient generator are zero by those of \(L_X\). This condition can be checked on jump intensities directly, including when the total holding rate varies among states of a block.2204 2205When block sums almost agree, an error estimate controls the effect on a fixed observation horizon. For a proposed kernel \(Q\) on \(Y\), assume2206\[2207 \sup_{x\in X}\big\|P(x,-)J-Q(q(x),-)\big\|_{\mathrm{TV}}2208 \leq \varepsilon,2209\]2210where total variation is one half the \(\ell^1\) norm. Writing \(E=PJ-JQ\), an exact telescoping identity gives2211\[2212 \mu P^nJ-\mu J Q^n2213 =\sum_{j=0}^{n-1}\mu P^{n-1-j} E Q^j.2214\]2215The row vector before \(E\) is a probability, so the norm of its product with \(E\) is at most \(\varepsilon\) by convexity. Propagation under \(Q^j\) is a contraction in total variation, giving a bound of \(n\varepsilon\) for every starting law \(\mu\). This estimate concerns the one-time observed laws and is uniform on a specified range of time steps. A stationary error estimate requires more information, such as a quantitative contraction for the quotient dynamics. In the limit theorem of Chapter~\ref{ch:mean-field}, the target is a deterministic flow and the uniform drift error is what enters the finite-time comparison.2216\par2217 2218\bookpart{IV}{Games and dynamics with interfaces}2219\chapter{Open games and the continuation interface}2220\label{ch:open-games}2221 2222Classical evolutionary game theory starts from payoffs on an entire2223population interaction. A component description needs an interface for2224an interaction whose surroundings are still unspecified. Open games2225supply that interface in the form of an input and a continuation. The2226continuation tells the component how each possible output would be2227evaluated by its surroundings. This makes off-equilibrium choices2228available for composition \cite{ghani-open-games}.2229 2230\section{Lenses as the deterministic interface}2231 2232Use \((X,S)\) for an interface with forward type \(X\) and backward2233type \(S\). A lens from \((X,S)\) to \((Y,R)\) consists of two maps2234\[2235 v:X\to Y,\qquad u:X\times R\to S.2236\]2237Its forward action sends a state \(x\) to \(v(x)\). Its backward action2238translates a return value \(r\) using the original state \(x\). In game2239semantics a return value may contain utility information. The lens2240axioms here are the composition and identity laws for these pairs.2241 2242For a second lens \((v',u'):(Y,R)\to(Z,Q)\), the composite has forward2243map \(v'v\) and backward map2244\[2245 (x,q)\longmapsto u\bigl(x,u'(v(x),q)\bigr).2246\]2247For three lenses, both parenthesizations substitute the forward values2248in the same order and then the backward values in reverse order.2249The lens \((\operatorname{id}_X,(x,s)\mapsto s)\) is a two-sided identity.2250This gives an ordinary category. The product of two lenses uses2251cartesian products on both types and applies the two maps separately.2252 2253A continuation on the target is an arbitrary function \(k:Y\to R\).2254An input at the source is an element \(x\in X\). A lens sends an2255input forward by \(v\) and transports a continuation backward by2256\[2257 k\longmapsto \bigl(x\longmapsto u(x,k(v(x)))\bigr).2258\]2259The backward transport reverses composition by direct substitution.2260Keeping \(k\) as a function matters. A single value \(k(v(x))\) gives