Necessary and Sufficient Conditions for the Existence of Cycles in Evolutionary Dynamics of Two-Strategy Games on Networks (I)

We study the convergence of evolutionary games on networks, in which the agents can choose between two strategies, by modeling the dynamics as a discrete time Markov process with a finite state space. Based on the transition matrix associated with the Markov process we construct a necessary and sufficient condition for the existence of cycles to evolutionary game dynamics under synchronous updating governed by an arbitrary deterministic update rule. We are able to identify the equilibrium states and cycles and show that for any initial condition the dynamics converge to either an equilibrium state or a cycle in finite time. A similar result is shown to apply for a general class of asynchronous update rules. For stochastic update rules, we derive a property that is sufficient for the existence of a unique limiting matrix, which characterizes the stochastic game dynamics. Consequently, we formulate a necessary and sufficient condition for the existence of cycles that holds for all levels of synchrony in the updating process. We illustrate how our results can be applied in two ways: first, for a given game, one can always calculate the required payoffs to prevent a trajectory to converge to a cycle; second, the effect of network structures on the fixation probability is explored numerically. Since the results hold for arbitrary payoff functions, they also apply to multiplayer games that in general cannot be reduced to an equivalent two-player game