Publication:372983

DOI10.1007/978-3-642-16170-4_6zbMath1291.91026DBLPconf/sagt/AulettaFPP10arXiv1002.3474OpenAlexW2169852109WikidataQ58219138 ScholiaQ58219138MaRDI QIDQ372983

Vincenzo Auletta, Francesco Pasquale, Diodato Ferraioli, Giuseppe Persiano

Publication date: 21 October 2013

Published in: Theory of Computing Systems, Algorithmic Game Theory (Search for Journal in Brave)

Abstract: We study "logit dynamics" [Blume, Games and Economic Behavior, 1993] for strategic games. This dynamics works as follows: at every stage of the game a player is selected uniformly at random and she plays according to a "noisy" best-response where the noise level is tuned by a parameter $�eta$. Such a dynamics defines a family of ergodic Markov chains, indexed by $�eta$, over the set of strategy profiles. We believe that the stationary distribution of these Markov chains gives a meaningful description of the long-term behavior for systems whose agents are not completely rational. Our aim is twofold: On the one hand, we are interested in evaluating the performance of the game at equilibrium, i.e. the expected social welfare when the strategy profiles are random according to the stationary distribution. On the other hand, we want to estimate how long it takes, for a system starting at an arbitrary profile and running the logit dynamics, to get close to its stationary distribution; i.e., the "mixing time" of the chain. In this paper we study the stationary expected social welfare for the 3-player CK game, for 2-player coordination games, and for two simple $n$-player games. For all these games, we also give almost tight upper and lower bounds on the mixing time of logit dynamics. Our results show two different behaviors: in some games the mixing time depends exponentially on $�eta$, while for other games it can be upper bounded by a function independent of $�eta$.

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

zbMATH Keywords

mixing timeequilibriasocial welfarelogit dynamics

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) Welfare economics (91B15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mixing time and stationary expected social welfare of logit dynamics
• Worst-case equilibria
• The statistical mechanics of strategic interaction
• Calibrated learning and correlated equilibrium
• A class of games possessing pure-strategy Nash equilibria
• Learning, Local Interaction, and Coordination
• The Price of Stability for Network Design with Fair Cost Allocation
• Settling the complexity of computing two-player Nash equilibria
• The price of anarchy of finite congestion games
• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• Convergence to Equilibrium in Local Interaction Games
• The Complexity of Computing a Nash Equilibrium

Related Items (11)

The price of anarchy and stability in general noisy best-response dynamics ⋮ Decentralized dynamics for finite opinion games ⋮ Convergence to equilibrium of logit dynamics for strategic games ⋮ Mixing time and stationary expected social welfare of logit dynamics ⋮ Metastability of Asymptotically Well-Behaved Potential Games ⋮ Logit dynamics with concurrent updates for local interaction potential games ⋮ Imperfect best-response mechanisms ⋮ Contrasting the Spread of Misinformation in Online Social Networks ⋮ Metastability of logit dynamics for coordination games ⋮ Social pressure in opinion dynamics ⋮ Unnamed Item

This page was built for publication: Mixing time and stationary expected social welfare of logit dynamics