Topologically robust zero-sum games and Pfaffian orientation: How network topology determines the long-time dynamics of the antisymmetric Lotka-Volterra equation

To explore how the topology of interaction networks determines the robustness of dynamical systems, we study the antisymmetric Lotka-Volterra equation (ALVE). The ALVE is the replicator equation of zero-sum games in evolutionary game theory, in which the strengths of pairwise interactions between strategies are defined by an antisymmetric matrix such that typically some strategies go extinct over time. Here we show that there also exist topologically robust zero-sum games, such as the rock-paper-scissors game, for which all strategies coexist for all choices of interaction strengths. We refer to such zero-sum games as coexistence networks and construct coexistence networks with an arbitrary number of strategies. By mapping the long-time dynamics of the ALVE to the algebra of antisymmetric matrices, we identify simple graph-theoretical rules by which coexistence networks are constructed. Examples are triangulations of cycles characterized by the golden ratio $\phi =1.6180...$, cycles with complete subnetworks, and non-Hamiltonian networks. In graph-theoretical terms, we extend the concept of a Pfaffian orientation from even-sized to odd-sized networks. Our results show that the topology of interaction networks alone can determine the long-time behavior of nonlinear dynamical systems, and may help to identify robust network motifs arising, for example, in ecology.

Figure 1

Coexistence networks in the antisymmetric Lotka-Volterra equation (ALVE) (1). The long-time dynamics of the ALVE are independent of the initial conditions and two scenarios are possible for a state $i$ (equivalently strategy): Either the state concentration vanishes $(x_i\to 0$ as $t\to \infty$; extinction and depletion) or it remains bounded away from 0 for all times $(x_i\ge \text{const.}>0$ for all $t$; survival and condensation). Survival and extinction of states depend only on the weighted network defined by the network topology and the weights. (a) Trajectories of the ALVE for a directed cycle of 5 nodes with an interior edge from node 4 to 2 (see insets). All states coexist. This coexistence does not only occur for unit weights (i), but for all choices of weights on that network topology (ii). Such network topologies are called coexistence networks or topologically robust zero-sum games. (b) The vast majority of networks are not coexistence networks; here shown for the rock-paper-scissors-lizard-Spock game (network topology of five states with two in-going and two out-going links for every node); see insets. (i) For unit weights, all states coexist, but states 3 and 4 go extinct for differently chosen weights (ii). Thus, coexistence in the rock-paper-scissors-lizard-Spock game depends on the rates.

Figure 2

Organization and application of the results of this work. The mathematical aspects are presented in Secs. 2, 3, and 4. We discuss the application of our mathematical results in Sec. 6, indicated by the last column with reference to the corresponding subsection.

Figure 3

Graph-theoretical definition of the Pfaffian. (a) The antisymmetric matrix $A$ and the corresponding, pretzel-like, weighted network $\mathcal{N}\left(A\right)$. (b) $\mathcal{N}\left(A\right)$ has two perfect matchings, ${\mu }_1=((1\to 2),(3\to 4))$ and ${\mu }_2=((3\to 1),(4\to 2))$. Each of the perfect matchings gives rise to a summand in the Pfaffian of $A$. Note that the graph-theoretical definition of the Pfaffian only includes negative matrix entries. Thus, the difference of the signs of the two summands arises from the network topology (via the permutations of the respective perfect matchings). The sign of a perfect matching depends on the number of transpositions needed to permute the indices of the matching's partition to the ordered partition $(1,2,3,4)$. (c) The Pfaffian of $A$ is the sum over the contributions stemming from all perfect matchings; see Eq. (5). All signs in the final sum of the graph-theoretical definition of the Pfaffian are determined by the network topology alone.

Figure 4

Algebraic characterization of coexistence networks via the adjugate vector of $A$. (a) Algebraic determination of coexistence networks; here illustrated for a cycle of five nodes (orange edges) with the two additional interior edges $(4,2)$ and $(3,1)$ (cyan edges). The network is factor-critical. The entries of the adjugate vector are calculated via the near-perfect matchings of the network and their signs (here, eight near-perfect matchings in total); see Fig. 3 for details of the computation. The near-perfect matching $((3\to 1),(4\to 2))$ creates the negative summand $\left(-a_{13}{a}_{24}\right)$. Thus, the weights can be chosen such that the kernel of $A$ is not strictly positive. Therefore, this network is not a coexistence network. Note that by setting one of the two or both cyan matrix entries to zero, the resulting network topology is a coexistence network. (b) (i) Cycles of odd length are coexistence networks because their adjugate vector is always strictly positive, whereas cycles of even length are not. (ii) The cycle with five nodes and the additional interior edge $(4,2)$ is a coexistence network as is inferred from the adjugate vector in (a) by setting $a_{13}=0$. (iii) The complete network of five nodes is not a coexistence network; see also Fig. 1. Additional near-perfect matchings arise through the interior edges $(5,3),(1,4)$, and $(2,5)$.

Figure 5

Graph-theoretical conditions for Hamiltonian coexistence networks. (a) Hamiltonian network ${\mathcal{N}}^{\left(9\right)}$ of 9 nodes consisting of edges from the Hamiltonian cycle (orange) and interior edges (2,7),(4,7), and (9,3) (cyan). (b) We identified the cycle condition (9) and the crossing condition (10) to check whether a network topology is a coexistence network. These conditions are both necessary and sufficient. The cycle condition ensures that only cycles of odd length are created within the Hamiltonian cycle through any interior edge. The crossing condition ensures that two crossing cycles share only an odd number of nodes connected by an even number of edges. It follows that ${\mathcal{N}}^{\left(9\right)}$ is a coexistence network. (c) Near-perfect matchings contributing to the first, second, and eighth component of the adjugate vector (8). Crossing edges do not contribute to the same near-perfect matching. (d) The component-wise calculation of the adjugate vector $\mathbf{r}$ confirms that the network topology ${\mathcal{N}}^{\left(9\right)}$ in (a) is a coexistence network because all vector components are strictly positive for all choices of weights.

Figure 6

All coexistence networks with up to 9 nodes. We determined all coexistence networks for up to $S\le 9$ by establishing all Hamiltonian coexistence networks via the graph-theoretical coexistence conditions (9) and (10) and deleting suitable edges; see Sec. 4c. (a)–(c) All coexistence networks for $S=3,5$, and 7 nodes. Coexistence networks are, for example, cycles, concatenations of smaller coexistence networks, and so-called generating coexistence networks (green color). Generating coexistence networks have a saturated number of edges: Upon adding any further edge to their network topology, they are no longer coexistence networks. (*) denotes specific triangulations of cycles that are discussed in Sec. 5a. These are dilute networks, but the total number of near-perfect matchings grows exponentially fast with the number of nodes $S$ at a rate characterized by the golden ratio $\phi =1.6180...$; see Eq. (17). (**) denotes cycles with complete subnetworks; see Sec. 5b. These networks are dense, but the total number of near-perfect matchings grows only polynomially as $\sim S^3$. (d) Generating coexistence networks with 9 nodes. Upon deleting suitable edges from these generating coexistence networks, all other 1454 coexistence networks for $S\le 9$ are generated.

Figure 7

Specific generating coexistence networks. (a) Triangulation of a cycle of size $S=13$. The orientation of the interior edges is chosen such that the network is a generating coexistence network. The adjugate vector is obtained as ${\mathbf{r}}^{\left(13\right)}=(13,8,5,6,6,5,8,13,8,10,9,10,8)$ if unit weights are chosen. Each entry equals the number of near-perfect matchings if the corresponding node is deleted from the network. The ratio of its first two entries converges to the golden ratio $\phi =1.6180...$ as $S=2n-1\to \infty$. The total number of near-perfect matchings in the network is obtained from the sum over all entries of this adjugate vector and grows exponentially fast at a rate characterized by $\phi$; see Eq. (17). (b) Cycle of size $S=11$ with a complete subnetwork on the odd nodes. The adjugate vector for unit weights is obtained as ${\mathbf{r}}^{\left(11\right)}=(1,5,1,8,1,9,1,8,1,5,1)$. Such networks are dense $(1/4$ of all possible edges are realized as $S\gg 1$, as opposed to the triangulations for which only $\sim 4/S$ of all possible edges are realized). Even though these networks are dense, the number of near-perfect matchings grows only polynomially with the system size $S$.

Figure 8

The dimer problem for graphs of odd size. (a) What is the number of closest-packing configurations with dimers (so-called dimer coverings) for the triangulation of a cycle of size $S=7$? A closest-packing configuration is a covering of the graph that leaves only one node of the graph uncovered. Our results obtained in Sec. 4 show that this question can be answered for all factor-critical coexistence networks. (b) All possible dimer coverings of the triangulation in (a) are depicted. Each closest-packing configuration with one uncovered node corresponds to one near-perfect matching of the triangulation. In total, 15 near-perfect matchings exist. The number of near-perfect matchings excluding node $i$ equals the $i\mathrm{th}$ component of the adjugate vector of the chosen directed graph (the Pfaffian orientation of the network topology) upon setting all weights to one. Here, the adjugate vector is obtained as ${\mathbf{r}}^{\left(7\right)}=(3,2,1,2,3,2,2)$ for unit weights; see Eq. (15). The total number of dimer coverings for the triangulation of a cycle grows exponentially fast with the number of nodes $S$ at a rate characterized by the golden ratio $\phi =1.6180...$; see Sec. 5a for details.