From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory
From MaRDI portal
(Redirected from Publication:776239)
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.
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
- scientific article; zbMATH DE number 5869530 (Why is no real title available?)
- scientific article; zbMATH DE number 3616736 (Why is no real title available?)
- scientific article; zbMATH DE number 903638 (Why is no real title available?)
- scientific article; zbMATH DE number 3106184 (Why is no real title available?)
- A continuous-time approach to online optimization
- Chaos in learning a simple two-person game
- Cycles in adversarial regularized learning
- Escort evolutionary game theory
- Evolutionary Games and Population Dynamics
- Evolutionary dynamics for bimatrix games: A Hamiltonian system?
- Evolutionary dynamics of zero-sum games
- Fictitious play, Shapley polygons, and the replicator equations
- From Darwin to Poincaré and von Neumann: recurrence and cycles in evolutionary and algorithmic game theory
- Information Theory and Statistical Mechanics
- Lotka-Volterra equation and replicator dynamics: New issues in classification
- Multiplicative updates outperform generic no-regret learning in congestion games (extended abstract)
- Optimization Despite Chaos: Convex Relaxations to Complex Limit Sets via Poincaré Recurrence
- Piecewise linear Hamiltonian flows associated to zero-sum games: transition combinatorics and questions on ergodicity
- Poincaré recurrence: old and new
- Replicator equations and the principle of minimal production of information
- The multiplicative weights update method: a meta-algorithm and applications
- The projection dynamic and the replicator dynamic
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)
