Metastability of logit dynamics for coordination games

DOI10.1007/S00453-017-0371-8MaRDI QIDQ1755731zbMATH OpenOpenAlexDBLPWikidataFDO

Authors V. Auletta, Diodato Ferraioli, Giuseppe Persiano, Francesco Pasquale

Publication date 11 January 2019

Published in Algorithmica (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Evolutionary games (91A22) Rationality and learning in game theory (91A26)

Abstract: Logit Dynamics [Blume, Games and Economic Behavior, 1993] are randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g., exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. It can happen that the chain is "metastable", i.e., on a time-scale shorter than the mixing time, it stays close to some probability distribution over the state space, while in a time-scale multiple of the mixing time it jumps from one distribution to another. In this paper we give a quantitative definition of "metastable probability distributions" for a Markov chain and we study the metastability of the logit dynamics for some classes of coordination games. We first consider a pure $n$-player coordination game that highlights the distinctive features of our metastability notion based on distributions. Then, we study coordination games on the clique without a risk-dominant strategy (which are equivalent to the well-known Glauber dynamics for the Curie-Weiss model) and coordination games on a ring (both with and without risk-dominant strategy).

Recommendations

• Metastability of logit dynamics for coordination games
• Metastability of the logit dynamics for asymptotically well-behaved potential games
• Metastability of asymptotically well-behaved potential games

Cites work

• scientific article; zbMATH DE number 5869530 (Why is no real title available?)
• scientific article; zbMATH DE number 3826915 (Why is no real title available?)
• scientific article; zbMATH DE number 47120 (Why is no real title available?)
• scientific article; zbMATH DE number 486613 (Why is no real title available?)
• scientific article; zbMATH DE number 1907684 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• Basins of Attraction, Long-Run Stochastic Stability, and the Speed of Step-by-Step Evolution
• Censored Glauber dynamics for the mean field Ising model
• Convergence to equilibrium in local interaction games
• Convergence to equilibrium of logit dynamics for strategic games
• Fast convergence in evolutionary equilibrium selection
• Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability
• Glauber dynamics on trees and hyperbolic graphs
• Large deviations and stochastic stability in the small noise double limit
• Learning, Local Interaction, and Coordination
• Logit Dynamics with Concurrent Updates for Local Interaction Games
• Metastability and low lying spectra in reversible Markov chains
• Metastability in stochastic dynamics of disordered mean-field models
• Metastability of asymptotically well-behaved potential games
• Metastability of logit dynamics for coordination games
• Metastable distributions of Markov chains with rare transitions
• Potential games
• Quasi-stationary distributions. Markov chains, diffusions and dynamical systems.
• Rapid innovation diffusion in social networks
• Revisiting log-linear learning: asynchrony, completeness and payoff-based implementation
• Robust stochastic stability
• The complexity of pure Nash equilibria
• The logit-response dynamics
• The mixing time evolution of Glauber dynamics for the mean-field Ising model
• The statistical mechanics of strategic interaction

Cited in

(7)

• Logit Dynamics with Concurrent Updates for Local Interaction Games
• Convergence to equilibrium of logit dynamics for strategic games
• Randomness and metastability in game theory and distributed computing (extended abstract)
• Extinction scenarios in evolutionary processes: a multinomial Wright-Fisher approach
• Metastability of the logit dynamics for asymptotically well-behaved potential games
• Metastability of asymptotically well-behaved potential games
• Metastability of logit dynamics for coordination games

This page was built for publication: Metastability of logit dynamics for coordination games

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