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

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 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.