From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory
From MaRDI portal
Publication:776239
DOI10.1007/978-3-030-35389-6_7zbMATH Open1435.91028arXiv1910.01334OpenAlexW2991027750MaRDI QIDQ776239FDOQ776239
Authors: 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
Recommendations
- Cycles versus equilibrium in evolutionary games
- scientific article; zbMATH DE number 1294426
- Algorithms, games, and evolution
- Evolutionary stability in repeated games played by finite automata
- Evolutionary games on graphs and discrete dynamical systems
- Evolutionary game theory: Darwinian dynamics and the \(G\) function approach
- On arbitrarily long periodic orbits of evolutionary games on graphs
- Evolutionary game theory: a renaissance
- Stochastic evolutionary game dynamics: foundations, deterministic approximation, and equilibrium selection
- Evolutionary games and periodic fitness
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Information Theory and Statistical Mechanics
- Title not available (Why is that?)
- Evolutionary Games and Population Dynamics
- Title not available (Why is that?)
- 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 (extended abstract)
- 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
- Poincaré recurrence: old and new
- Cycles in adversarial regularized learning
- 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 (3)
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)
