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

1861 u_i^N(n)=\sum_{j\in S}\frac{n_j-\mathbf 1_{\{i=j\}}}{N-1}A_{ij}.1862\]1863If \(n_i=0\), there is no individual of type \(i\) whose payoff is needed. Give each currently present type a strictly positive reproductive weight \(f_i(n)\). For instance a positive response \(f_i(n)=\phi(u_i^N(n))\) implements a prescribed mapping from payoffs to reproductive probabilities. The choice is part of the model. Adding the same constant to all payoffs preserves many static comparisons. Adding the same constant to positive reproductive weights changes ratios \(f_i/f_j\) in general and hence can change the stochastic dynamics. A common positive multiplication of all weights at a state leaves their normalized ratios unchanged. The distinction parallels the several meanings of payoff equivalence in Chapter~\ref{ch:payoff-equivalence}.1864 1865\section{Birth, mutation, and replacement}1866 1867The birth--death process updates one position at a time. It belongs to the overlapping-generation tradition of Moran's model \cite{moran-random}. Here the parent is chosen with probability proportional to its reproductive weight, the offspring type is sampled from a mutation kernel, and a uniformly chosen member of the current population is replaced. The parent is eligible for replacement in this convention. Let \(M_{ik}\) be the probability that a type \(i\) parent produces type \(k\), with each row of \(M\) summing to one. Define1868\[1869 b_i(n)=\frac{n_i f_i(n)}{\sum_j n_j f_j(n)},\qquad1870 c_k(n)=\sum_i b_i(n)M_{ik},\qquad1871 d_j(n)=\frac{n_j}{N}.1872\]1873For an absent type we set \(n_i f_i(n)=0\) by convention. The offspring distribution is \(c(n)\). Let \(e_i\) denote the count vector with a unit at \(i\) and zero elsewhere. If \(k\neq j\) and \(n_j>0\), the transition from \(n\) to \(n+e_k-e_j\) has probability \(c_k(n)d_j(n)\). The probability of remaining at \(n\) is \(\sum_j c_j(n)d_j(n)\). These probabilities sum to one because all ordered pairs of offspring and removed types have been accounted for. A death rule depending on the parent or on its location replaces the product \(c_kd_j\) by a joint kernel. In that case the joint law is part of the dynamics.1874 1875The update can also be written as a composition of kernels, retaining only the information required by the next stage. With \(D_n=\{(k,j)\in S^2:n_j>0\}\), each arrow below is well defined on its displayed states:1876\[1877\begin{tikzcd}[column sep=large]1878 \{n\} \arrow[r,"c\otimes d"{above}] &1879 D_n \arrow[r,"{\text{replacement}}"{above}] &1880 C_N(S).1881\end{tikzcd}1882\]1883The final map is deterministic. This factorization makes conservation of total population size explicit. It also gives a route to composition with other mechanisms, such as scheduling several local updates, by composing their kernels in time. The conditional mean of the frequency increment is1884\begin{equation}1885 \mathbb E[x_{\mathrm{next}}-x\mid n]1886      =\frac{1}{N}\bigl(c(n)-x\bigr).1887 \label{eq:birth-death-drift}1888\end{equation}1889For this identity, simply average \(e_k-e_j\) against the joint law. Independence supplies the stated \(c\) and \(d\), while the mean-increment formula needs only their marginals. The second moments can depend on the joint law even when the drift agrees.1890 1891In the independent case, writing \(\operatorname{diag}(c)\) for the diagonal matrix with entries \(c_k\), the conditional covariance of the frequency increment is1892\[1893 \frac{1}{N^2}\bigl(\operatorname{diag}(c)-cc^{\mathsf T}1894                   +\operatorname{diag}(d)-dd^{\mathsf T}\bigr),1895\]1896with \(c,d\) taken as columns in this formula. Each removed or added type is represented by a random coordinate vector. Independence makes their cross covariance zero, so the two covariance matrices add. The matrix annihilates the all-ones vector, expressing that a frequency increment is tangent to the affine simplex. This covariance and the conditional drift answer different questions about the same update kernel.1897 1898\begin{proposition}[Fixation and recurrence]1899\label{prop:fixation-recurrence}1900For the update above with strictly positive reproductive weights, suppose first that \(M\) is the identity. The chain reaches a monomorphic population almost surely, and each monomorphic population is absorbing. If \(M\) instead has strictly positive entries, the chain is irreducible and aperiodic. It has a unique stationary law and converges to that law from every initial distribution.1901\end{proposition}1902 1903\begin{proof}1904When \(M\) is the identity, a currently absent type cannot be produced. In a monomorphic state all replacements preserve the type. Starting from any state containing \(i\), choose a parent of type \(i\) and remove an individual of another type at each successive step until reaching the monomorphic state of type \(i\). Each step has strictly positive conditional probability and the path has length at most \(N-1\). The state set is finite, so there is a uniform positive lower bound on the probability of absorption within \(N-1\) steps, considering one such path for each state. By the Markov property, the probability of avoiding absorption over successive blocks of \(N-1\) steps decays geometrically.1905 1906If \(M\) is strictly positive, \(c_k(n)>0\) for every \(k\) and every \(n\). A move removing a present type and adding any specified type is therefore possible. Starting from \(n\), repeatedly move a unit from a coordinate in surplus relative to a target \(n'\) to one in deficit. This reaches \(n'\) in at most \(N\) steps. Every state also has a self-loop because at least one \(d_j\) is positive and every \(c_j\) is positive. Thus the \(N\)-step transition matrix is strictly positive. A stationary law exists as a limit point of Ces\`aro averages. The \(N\)-step matrix has a common strictly positive minorant in every row. Removing it leaves the same residual mass in every row and gives a total-variation contraction by that residual mass, which is strictly less than one. This proves uniqueness and convergence for the full chain.1907\end{proof}1908 1909\section{Fixation probabilities retain the update law}1910 1911When mutation is absent, let \(h_i(n)\) be the probability of fixation at the monomorphic state of type \(i\). Conditioning on the first update makes \(h_i\) harmonic away from the absorbing states. Its boundary values are one at fixation of \(i\) and zero at fixation of any other type. These conditions characterize it. Indeed, a harmonic function with these boundary values has constant conditional mean until absorption, and the absorption argument above gives almost sure convergence to the boundary values. Boundedness on the finite state space permits taking expectations in the limit.1912 1913Under neutral reproduction all present reproductive weights are equal, so \(c(n)=x\) in the mutation-free process. Equation~\eqref{eq:birth-death-drift} gives harmonicity of \(n_i/N\), and the boundary values give \(h_i(n)=n_i/N\). For nonneutral reproduction these fixation probabilities depend on the transition law. The drift alone can be insufficient when different updates induce different hitting distributions, and a deterministic trajectory is a different observable from the absorption probability. The next chapter studies selection by rare mutation, in which fixation between departures from recurrent states supplies the effective transition information. Chapter~\ref{ch:mean-field} compares the frequency process with its deterministic limit on a fixed time interval.1914\par1915\chapter{Rare mutation and stochastic stability}1916\label{ch:stochastic-stability}1917 1918A small mutation probability changes the meaning of a long-run prediction. The mutation-free chain can have many recurrent classes. With positive mutation the chain can leave those classes, and its stationary law can weight them differently even when mutation tends to zero. The stationary limit first takes a long-time average at positive mutation and then decreases the mutation parameter. This order is intrinsic to the prediction.1919 1920\section{A theorem for stationary weights}1921 1922Let \(E\) be a nonempty finite state set and \(P\) an irreducible transition matrix on \(E\), with rows indexed by the starting state. An in-tree rooted at \(i\) assigns one outgoing edge to each vertex other than \(i\), such that repeated traversal of the edges brings any vertex to \(i\). The root has no outgoing edge. Define1923\[1924 W_i(P)=\sum_{\tau\text{ rooted at }i}1925      \prod_{(x,y)\in\tau}P(x,y).1926\]1927The one-state case uses the weight one for the empty tree. Each weight is positive because the support of \(P\) has a path from every vertex to \(i\). Choosing at each vertex an edge decreasing the shortest such path length gives a tree of positive weight.1928 1929\begin{theorem}[Markov chain tree formula]1930\label{thm:markov-trees}1931The unique stationary distribution of \(P\) is1932\(\pi(i)=W_i(P)/\sum_j W_j(P)\).1933\end{theorem}1934 1935\begin{proof}1936It suffices to show that the weighted inflow to \(i\) from distinct states equals the weighted outflow from \(i\):1937\[1938 \sum_{j\ne i}W_j(P)P(j,i)1939       =W_i(P)\sum_{k\ne i}P(i,k).1940\]1941A term on the left adds the edge \(j\to i\) to a tree rooted at \(j\). This produces a directed graph with one outgoing edge at every vertex and a unique directed cycle, of length at least two, containing \(i\). A term on the right adds \(i\to k\) to a tree rooted at \(i\). It gives a graph of the same kind. From such a graph, deleting the edge entering \(i\) on the cycle recovers the construction on the left. Deleting the outgoing edge at \(i\) recovers the construction on the right. The products are the same because they use all edges of the corresponding graph. The diagonal terms of stationarity cancel, so this bijection proves the displayed identity. Normalize and use uniqueness of the stationary law for a finite irreducible chain.1942\end{proof}1943 1944This is the rooted-tree form of the Markov chain tree theorem \cite{leighton-rivest}. It accounts for indirect paths between states. The stationary ranking can depend on several paths taken together and therefore need not coincide with a ranking of the individual edges leaving each state.1945 1946\section{Leading powers and stable states}1947 1948Suppose \(P^\epsilon\) is irreducible for every sufficiently small \(\epsilon>0\). Assume for each off-diagonal edge that its weight is either identically zero for small \(\epsilon\), or1949\[1950 P^\epsilon(x,y)1951   =c_{xy}\epsilon^{r_{xy}}+o(\epsilon^{r_{xy}}),1952 \qquad c_{xy}>0,\quad r_{xy}\geq 0 .1953\]1954Call \(r_{xy}\) the resistance. Omit identically zero edges and set1955\[1956 \gamma_i=\min_{\tau\text{ rooted at }i}1957               \sum_{(x,y)\in\tau}r_{xy}.1958\]1959For each root define \(a_i>0\) by summing \(\prod_{(x,y)\in\tau}c_{xy}\)1960over its minimizers. Each tree product has exponent given by the sum of its edge resistances. The tree sum is finite and its coefficients at the smallest exponent are positive. Hence