From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory

DOI10.1007/978-3-030-35389-6_7zbMATH Open1435.91028arXiv1910.01334OpenAlexW2991027750MaRDI QIDQ776239FDOQ776239

Victor Boone, Georgios Piliouras

Publication date: 30 June 2020

Abstract: Replicator dynamics, the continuous-time analogue of Multiplicative Weights Updates, is the main dynamic in evolutionary game theory. In simple evolutionary zero-sum games, such as Rock-Paper-Scissors, replicator dynamic is periodic cite{zeeman1980population}, however, its behavior in higher dimensions is not well understood. We provide a complete characterization of its behavior in zero-sum evolutionary games. We prove that, if and only if, the system has an interior Nash equilibrium, the dynamics exhibit Poincar'{e} recurrence, i.e., almost all orbits come arbitrary close to their initial conditions infinitely often. If no interior equilibria exist, then all interior initial conditions converge to the boundary. Specifically, the strategies that are not in the support of any equilibrium vanish in the limit of all orbits. All recurrence results furthermore extend to a class of games that generalize both graphical polymatrix games as well as evolutionary games, establishing a unifying link between evolutionary and algorithmic game theory. We show that two degrees of freedom, as in Rock-Paper-Scissors, is sufficient to prove periodicity.

Full work available at URL: https://arxiv.org/abs/1910.01334

Mathematics Subject Classification ID

Evolutionary games (91A22) Algorithmic game theory and complexity (91A68)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Information Theory and Statistical Mechanics
• Evolutionary Games and Population Dynamics
• Evolutionary dynamics of zero-sum games
• Fictitious play, Shapley polygons, and the replicator equations
• Evolutionary dynamics for bimatrix games: A Hamiltonian system?
• Piecewise linear Hamiltonian flows associated to zero-sum games: transition combinatorics and questions on ergodicity
• The multiplicative weights update method: a meta-algorithm and applications
• Multiplicative updates outperform generic no-regret learning in congestion games
• Lotka-Volterra equation and replicator dynamics: New issues in classification
• Replicator equations and the principle of minimal production of information
• A continuous-time approach to online optimization
• The projection dynamic and the replicator dynamic
• Chaos in learning a simple two-person game
• Escort evolutionary game theory
• Optimization Despite Chaos: Convex Relaxations to Complex Limit Sets via Poincaré Recurrence
• From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory

Cited In (1)

• From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Evolutionary games and periodic fitness 👍 👎
• Algorithms, games, and evolution 👍 👎
• Evolutionary stability in repeated games played by finite automata 👍 👎
• Evolutionary game theory: a renaissance 👍 👎
• On arbitrarily long periodic orbits of evolutionary games on graphs 👍 👎
• Evolutionary game theory: Darwinian dynamics and the \(G\) function approach 👍 👎
• Evolutionary games on graphs and discrete dynamical systems 👍 👎
• Cycles versus equilibrium in evolutionary games 👍 👎

This page was built for publication: From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q776239)