We introduce -Rank, a principled evolutionary dynamics methodology for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous- and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, the type of interactions, and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). -Rank provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics. This is a consequence of the links we establish to the MCC solution concept when the underlying evolutionary model's ranking-intensity parameter, , is chosen to be large, which exactly forms the basis of -Rank. In contrast to the Nash equilibrium, which is a static concept based on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley's Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. -Rank runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce proofs that not only provide a unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the -Rank methodology. We empirically validate the method in several domains including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.
Evolutionary dynamics have often been presented as a practical tool for analyzing interactions among meta-strategies found in EGTA @cite_53 @cite_14 @cite_41 , and for studying the change in policies of multiple learning agents @cite_41 , as the EGTA approach is largely based on the same assumptions as evolutionary game-theory, viz. repeated interactions among sub-groups sampled independently at random from an arbitrarily-large population of agents.
@cite_41 @cite_53 @cite_14
2343319590 1567092208 2568440864 2415757320
Empirical game-theoretic analysis (EGTA) has recently been applied successfully to analyze the behavior of large numbers of competing traders in a continuous double auction market. Multiagent simulation methods like EGTA are useful for studying complex strategic environments like a stock market, where it is not feasible to solve analytically for the rational behavior of each agent. A weakness of simulation-based methods in strategic settings, however, is that it is typically impossible to prove that the strategy profile assigned to the simulated agents is stable, as in a Nash equilibrium. I propose using reinforcement learning to analyze the regret of supposed Nash-equilibrium strategy profiles found by EGTA. I have developed a new library of reinforcement learning tools, which I have integrated into an extended version of the market simulator from our prior work. I provide evidence for the effectiveness of our library methods, both on a suite of benchmark problems from the literature, and on non-equilibrium strategy profiles in our market environment. Finally, I use our new reinforcement learning tools to provide evidence that the equilibria found by EGTA in our recent continuous double auction study are likely to have only negligible regret, even with respect to an extended strategy space. This text offers a systematic, rigorous, and unified presentation of evolutionary game theory, covering the core developments of the theory from its inception in biology in the 1970s through recent advances. Evolutionary game theory, which studies the behavior of large populations of strategically interacting agents, is used by economists to make predictions in settings where traditional assumptions about agents' rationality and knowledge may not be justified. Recently, computer scientists, transportation scientists, engineers, and control theorists have also turned to evolutionary game theory, seeking tools for modeling dynamics in multiagent systems. Population Games and Evolutionary Dynamics provides a point of entry into the field for researchers and students in all of these disciplines. The text first considers population games, which provide a simple, powerful model for studying strategic interactions among large numbers of anonymous agents. It then studies the dynamics of behavior in these games. By introducing a general model of myopic strategy revision by individual agents, the text provides foundations for two distinct approaches to aggregate behavior dynamics: the deterministic approach, based on differential equations, and the stochastic approach, based on Markov processes. Key results on local stability, global convergence, stochastic stability, and nonconvergence are developed in detail. Ten substantial appendixes present the mathematical tools needed to work in evolutionary game theory, offering a practical introduction to the methods of dynamic modeling. Accompanying the text are more than 200 color illustrations of the mathematics and theoretical results; many were created using the Dynamo software suite, which is freely available on the author's Web site. Readers are encouraged to use Dynamo to run quick numerical experiments and to create publishable figures for their own research. Evolutionary dynamics has been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [P. Moran, Random processes in genetics, Proceedings of the Cambridge Philosophical Society 54 (1) (1958) 60-71]. Recently, this approach has been generalized in [E. Lieberman, C. Hauert, M.A. Nowak, Evolutionary dynamics on graphs, Nature 433 (2005) 312-316] by arranging individuals on the nodes of a network (in general, directed). In this setting, the existence of directed arcs enables the simulation of extreme phenomena, where the fixation probability of a randomly placed mutant (i.e., the probability that the offspring of the mutant eventually spread over the whole population) is arbitrarily small or large. On the other hand, undirected networks (i.e., undirected graphs) seem to have a smoother behavior, and thus it is more challenging to find suppressors amplifiers of selection, that is, graphs with smaller greater fixation probability than the complete graph (i.e., the homogeneous population). In this paper we focus on undirected graphs. We present the first class of undirected graphs which act as suppressors of selection, by achieving a fixation probability that is at most one half of that of the complete graph, as the number of vertices increases. Moreover, we provide some generic upper and lower bounds for the fixation probability of general undirected graphs. As our main contribution, we introduce the natural alternative of the model proposed in [E. Lieberman, C. Hauert, M.A. Nowak, Evolutionary dynamics on graphs, Nature 433 (2005) 312-316]. In our new evolutionary model, all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals. We prove that our new model of mutual influences admits a potential function, which guarantees the convergence of the system for any graph topology and any initial fitness vector of the individuals. Furthermore, we prove fast convergence to the stable state for the case of the complete graph, as well as we provide almost tight bounds on the limit fitness of the individuals. Apart from being important on its own, this new evolutionary model appears to be useful also in the abstract modeling of control mechanisms over invading populations in networks. We demonstrate this by introducing and analyzing two alternative control approaches, for which we bound the time needed to stabilize to the ''healthy'' state of the system. We discuss how to use evolutionary game theory (EGT) as a framework for studying how cultural dynamics and structural properties can influence the evolution of norms and behaviors within a society. We provide a brief tutorial on how EGT works, and discuss what kinds of insights it can provide. We then describe three published studies in which we have developed EGT models that help explain how structural and external conditions in a society affect the emergence of social norms.