Logit Dynamics with Concurrent Updates for Local Interaction Games

DOI10.1007/978-3-642-40450-4_7MaRDI QIDQ2849298zbMATH OpenOpenAlexWikidataFDO

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

Publication date 17 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Noncooperative games (91A10) Evolutionary games (91A22) Rationality and learning in game theory (91A26) Games involving graphs (91A43) Social networks; opinion dynamics (91D30)

Abstract: Logit choice dynamics are a family of randomized best response dynamics based on the logit choice function [McFadden, 1974], used for modeling players with limited rationality and knowledge. In this paper we study the all-logit dynamics, where at each time step all players concurrently update their strategies according to the logit choice function. In the well studied one-logit dynamics [Blume, 1993] instead at each step only one randomly chosen player is allowed to update. We study properties of the all-logit dynamics in the context of local interaction games, a class of games that has been used to model complex social phenomena and physical systems. In a local interaction game, players are the vertices of a social graph whose edges are two-player potential games. Each player picks one strategy to be played for all the games she is involved in and the payoff of the player is the sum of the payoffs from each of the games. We prove that local interaction games characterize the class of games for which the all-logit dynamics is reversible. We then compare the stationary behavior of one-logit and all-logit dynamics. Specifically, we look at the expected value of a notable class of observables, that we call decomposable observables. We prove that the difference between the expected values of the observables at stationarity for the two dynamics depends only on the rationality level beta and on the distance of the social graph from a bipartite graph. In particular, if the social graph is bipartite then decomposable observables have the same expected value. Finally, we show that the mixing time of the all-logit dynamics has the same twofold behavior that has been highlighted in the case of the one-logit: for some games it exponentially depends on the rationality level beta, whereas for other games it can be upper bounded by a function independent from beta.

Recommendations

• Logit dynamics with concurrent updates for local interaction potential games
• Convergence to equilibrium in local interaction games
• Convergence to equilibrium of logit dynamics for strategic games
• The logit dynamic for games with continuous strategy sets
• Metastability of logit dynamics for coordination games
• Metastability of logit dynamics for coordination games
• Between local and global strategy updating in public goods game
• On local prisoner's dilemma game with Pareto updating rule
• Efficiency in repeated games with local interaction and uncertain local monitoring

Cited in

(7)

• Metastability of logit dynamics for coordination games
• Social pressure in opinion dynamics
• Convergence to equilibrium of logit dynamics for strategic games
• Dynamics in Network Interaction Games
• Contrasting the spread of misinformation in online social networks
• Stochastic Stability in Schelling’s Segregation Model with Markovian Asynchronous Update
• Logit dynamics with concurrent updates for local interaction potential games

This page was built for publication: Logit Dynamics with Concurrent Updates for Local Interaction Games

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