Inspired by the work of [Kempe, Kleinberg, Oren, Slivkins, EC13] we introduce and analyze a model on opinion formation; the update rule of our dynamics is a simplified version of that of Kempe et. al. We assume that the population is partitioned into types whose interaction pattern is specified by a graph. Interaction leads to population mass moving from types of smaller mass to those of bigger. We show that starting uniformly at random over all population vectors on the simplex, our dynamics converges point-wise with probability one to an independent set. This settles an open problem of Kempe et. al., as applicable to our dynamics. We believe that our techniques can be used to settle the open problem for the Kempe et. al. dynamics as well. Next, we extend the model of Kempe et. al. by introducing the notion of birth and death of types, with the interaction graph evolving appropriately. Birth of types is determined by a Bernoulli process and types die when their population mass is less than a parameter @math . We show that if the births are infrequent, then there are long periods of "stability" in which there is no population mass that moves. Finally we show that even if births are frequent and "stability" is not attained, the total number of types does not explode: it remains logarithmic in @math .
Other works, including dynamical systems that show convergence to fixed points, are @cite_9 @cite_20 @cite_21 @cite_12 @cite_7 @cite_28 . @cite_28 focuses on quadratic dynamics and they show convergence in the limit. On the other hand @cite_0 shows that sampling from the distribution this dynamics induces at a given time step is PSPACE-complete. In @cite_9 @cite_20 , it is shown that replicator dynamics in linear congestion and 2-player coordination games converges to pure Nash equilibria, and in @cite_21 @cite_12 it is shown that gradient descent converges to local minima, avoiding saddle points even in the case where the fixed points are uncountably many.
@cite_7 @cite_28 @cite_9 @cite_21 @cite_0 @cite_20 @cite_12
2342774186 2145818164 2493056695 2474090883 1995326443 1857453345 2467441529
A new approach to understanding evolution [Val09], namely viewing it through the lens of computation, has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [CLPV14]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [WVA05], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability. On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game. Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation. The paper promotes the study of computational aspects, primarily the convergence rate, of nonlinear dynamical systems from a combinatorial perspective. The authors identify the class of symmetric quadratic systems. Such systems have been widely used to model phenomena in the natural sciences, and also provide an appropriate framework for the study of genetic algorithms in combinatorial optimisation. They prove several fundamental general properties of these systems, notably that every trajectory converges to a fixed point. They go on to give a detailed analysis of a quadratic system defined in a natural way on probability distributions over the set of matchings in a graph. In particular, they prove that convergence to the limit requires only polynomial time when the graph is a tree. This result demonstrates that such systems, though nonlinear, are amenable to quantitative analysis. > What does it mean to fully understand the behavior of a network of adaptive agents? The golden standard typically is the behavior of learning dynamics in potential games, where many evolutionary dynamics, e.g., replicator dynamics, are known to converge to sets of equilibria. Even in such classic settings many questions remain unanswered. We examine issues such as: Point-wise convergence: Does the system always equilibrate, even in the presence of continuums of equilibria? Computing regions of attraction: Given point-wise convergence can we compute the region of asymptotic stability of each equilibrium (e.g., estimate its volume, geometry)? System invariants: Invariant functions remain constant along every system trajectory. This notion is orthogonal to the game theoretic concept of a potential function, which always strictly increases decreases along system trajectories. Do dynamics in potential games exhibit invariant functions? If so, how many? How do these functions look like? Based on these geometric characterizations, we propose a novel quantitative framework for analyzing the efficiency of potential games with many equilibria. The predictions of different equilibria are weighted by their probability to arise under evolutionary dynamics given uniformly random initial conditions. This average case analysis is shown to offer novel insights in classic game theoretic challenges, including quantifying the risk dominance in stag-hunt games and allowing for more nuanced performance analysis in networked coordination and congestion games with large gaps between price of stability and price of anarchy. CCS Concepts: rTheory of computation! Solution concepts in game theory; Convergence and learning in games; Quadratic Dynamical Systems (QDS), whose definition extends that of Markov chains, are used to model phenomena in a variety of fields like statistical physics and natural evolution. Such systems also play a role in genetic algorithms, a widelyused class of heuristics that are notoriously hard to analyze. Recently took an important step in the study of QDS’s by showing, under some technical assumptions, that such systems converge to a stationary distribution (similar theorems for Markov Chains are well-known). We show, however, that the following sampling problem for QDS’s is PSPACE-hard: Given an initial distribution, produce a random sample from the t’th generation. The hardness result continues to hold for very restricted classes of QDS’s with very simple initial distributions, thus suggesting that QDS’s are intrinsically more complicated than Markov chains. ∗Supported by an IBM Graduate Fellowship and partly under NSF grant CCR-9310214. Email: arora@cs.berkeley.edu. †Work done while at ICSI, Berkeley, and supported in part by a Rothschild postdoctoral fellowship. Email: rabani@theory.lcs.mit.edu. ‡Supported by NSF grant CCR-9310214. Email: vazirani@cs.berkeley.edu. In a recent series of papers a surprisingly strong connection was discovered between standard evolutionary models of natural selection and Multiplicative Weights Updates Algorithm, a ubiquitous model of online learning and optimization. These papers establish that, under specific assumptions, mathematical models of biological evolution can be reduced to studying discrete replicator dynamics, a close variant of MWUA, in coordination games. This connection allows for introducing insights from game theoretic dynamics into the field of mathematical biology. Using these results as a stepping stone, we show that mathematical models of haploid evolution imply the extinction of genetic diversity in the long term limit, a widely believed conjecture in genetics. In game theoretic terms we show that in the case of coordination games, under minimal genericity assumptions, discrete replicator dynamics converge to pure Nash equilibria for all but a zero measure of initial conditions. This result holds despite the fact that mixed Nash equilibria can be exponentially (or even uncountably) many, completely dominating in number the set of pure Nash equilibria. Thus, in haploid organisms the long term preservation of genetic diversity needs to be safeguarded by other evolutionary mechanisms such as mutations and speciation. Given a non-convex twice differentiable cost function f , we prove that the set of initial conditions so that gradient descent converges to saddle points where ∇f has at least one strictly negative eigenvalue has (Lebesgue) measure zero, even for cost functions f with non-isolated critical points, answering an open question in [12]. Moreover, this result extends to forward-invariant convex subspaces, allowing for weak (non-globally Lipschitz) smoothness assumptions. Finally, we produce an upper bound on the allowable step-size.