Convergence to equilibrium of logit dynamics for strategic games

DOI10.1007/S00453-015-0025-7zbMATH Open1349.91041DBLPjournals/algorithmica/AulettaFPPP16arXiv1212.1884OpenAlexW1132647567WikidataQ58219117 ScholiaQ58219117MaRDI QIDQ334931FDOQ334931

Authors: V. Auletta, Diodato Ferraioli, Francesco Pasquale, Paolo Penna, Giuseppe Persiano 

Publication date: 1 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise beta describes the behavior of a complex system whose individual components act selfishly and keep responding according to some partial ("noisy") knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by the inverse of the parameter beta. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that, for potential games, the mixing time is upper and lower bounded by an exponential in the inverse of the noise and in the maximum potential difference. Instead, for games with dominant strategies, the mixing time cannot grow arbitrarily with the inverse of the noise. Finally, we refine our analysis for a subclass of potential games called graphical coordination games, a class of games that have been previously studied in Physics and, more recently, in Computer Science in the context of diffusion of new technologies. We give evidence that the mixing time of the logit dynamics for these games strongly depends on the structure of the underlying graph. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in the inverse of noise. Moreover, we consider two specific and popular network topologies, the clique and the ring. For games played on a clique we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in the inverse of the noise and in the maximum potential difference, while for games played on a ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.

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

Recommendations

• Metastability of logit dynamics for coordination games
• Metastability of logit dynamics for coordination games
• Logit dynamics with concurrent updates for local interaction potential games

zbMATH Keywords

Markov chaingame theorypotential gamesconvergence time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Noncooperative games (91A10) Evolutionary games (91A22) Games involving graphs (91A43)

Cites Work

• Algorithmic Game Theory
• Title not available (Why is that?)
• The emergence of rational behavior in the presence of stochastic perturbations
• The statistical mechanics of strategic interaction
• Convergence to equilibrium of logit dynamics for strategic games
• Learning, Local Interaction, and Coordination
• Approximating the Permanent
• Payoff-based dynamics for multiplayer weakly acyclic games
• Atomic congestion games: fast, myopic and concurrent
• Glauber dynamics on trees and hyperbolic graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convergence to equilibrium in local interaction games
• Metastability of logit dynamics for coordination games
• Dynamics in network interaction games
• Logit Dynamics with Concurrent Updates for Local Interaction Games
• Concurrent imitation dynamics in congestion games
• Title not available (Why is that?)

Cited In (17)

• Logit Dynamics with Concurrent Updates for Local Interaction Games
• Graphical potential games
• Convergence to equilibrium of logit dynamics for strategic games
• Multistability and Hopf bifurcation analysis for a three-strategy evolutionary game with environmental feedback and delay
• Metastability of logit dynamics for coordination games
• Decentralized dynamics for finite opinion games
• Decentralized dynamics for finite opinion games
• Convergence of incentive-driven dynamics in Fisher markets
• Logit dynamics with concurrent updates for local interaction potential games
• Generalized mirror descents in congestion games
• Metastability of the logit dynamics for asymptotically well-behaved potential games
• Replicator based on imitation for finite and arbitrary networked communities
• Metastability of logit dynamics for coordination games
• Metastability of asymptotically well-behaved potential games
• Distortion based potential game for distributed coverage control
• Sampling from the Gibbs Distribution in Congestion Games
• Introspection dynamics in asymmetric multiplayer games

This page was built for publication: Convergence to equilibrium of logit dynamics for strategic games

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