Coordination problems on networks revisited: statics and dynamics
arXiv:2106.02548 · doi:10.1088/1742-5468/ac2ed8
Abstract
Simple binary-state coordination models are widely used to study collective socio-economic phenomena such as the spread of innovations or the adoption of products on social networks. The common trait of these systems is the occurrence of large-scale coordination events taking place abruptly, in the form of a cascade process, as a consequence of small perturbations of an apparently stable state. The conditions for the occurrence of cascade instabilities have been largely analysed in the literature, however for the same coordination models no sufficient attention was given to the relation between structural properties of (Nash) equilibria and possible outcomes of dynamical equilibrium selection. Using methods from the statistical physics of disordered systems, the present work investigates both analytically and numerically, the statistical properties of such Nash equilibria on networks, focusing mostly on random graphs. We provide an accurate description of these properties, which is then exploited to shed light on the mechanisms behind the onset of coordination/miscoordination on large networks. This is done studying the most common processes of dynamical equilibrium selection, such as best response, bounded-rational dynamics and learning processes. In particular, we show that well beyond the instability region, full coordination is still globally stochastically stable, however equilibrium selection processes with low stochasticity (e.g. best response) or strong memory effects (e.g. reinforcement learning) can be prevented from achieving full coordination by being trapped into a large (exponentially in number of agents) set of locally stable Nash equilibria at low/medium coordination (inefficient equilibria). These results should be useful to allow a better understanding of general coordination problems on complex networks.
arXiv commentRevtex style, 56 pages, 21 figures
References in corpus (48)
- The Dynamics of Protest Recruitment through an Online Network
- A message passing approach for general epidemic models
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- High-accuracy approximation of binary-state dynamics on networks
- Crises and collective socio-economic phenomena: simple models and challenges
- Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (2000)
- Lattice Glass Models
- Edwards measures for powders and glasses
- Survey propagation: an algorithm for satisfiability
- Binary-state dynamics on complex networks: pair approximation and beyond
- Coupled Replicator Equations for the Dynamics of Learning in Multiagent Systems
- Containing epidemic outbreaks by message-passing techniques
- Zero-temperature Hysteresis in Random-field Ising Model on a Bethe Lattice
- Message passing on networks with loops
- Dynamics of Boltzmann Q-Learning in Two-Player Two-Action Games
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- The prevalence of chaotic dynamics in games with many players
- Dynamic message-passing equations for models with unidirectional dynamics
- Local cascades induced global contagion: How heterogeneous thresholds, exogenous effects, and unconcerned behaviour govern online adoption spreading
- Evolutionary dynamics, intrinsic noise and cycles of co-operation
- Hysteresis in the Random Field Ising Model and Bootstrap Percolation
- Intrinsic noise in game dynamical learning
- Large deviations of cascade processes on graphs
- Distribution of Avalanche Sizes in the Hysteretic Response of Random Field Ising Model on a Bethe Lattice at Zero Temperature
- Collaboration in Social Networks
- Statistical Mechanics of maximal independent sets
- Mechanism for the failure of the Edwards hypothesis in the SK spin glass
- Metastable states of spin glasses on random thin graphs
- The stochastic matching problem
- Cycles of cooperation and defection in imperfect learning
- Dynamics to equilibrium in Network Games: individual behavior and global response
- Metastable states and T=0 hysteresis in the random-field Ising model on random graphs
- Equilibria, information and frustration in heterogeneous network games with conflicting preferences
- Metastable states of a ferromagnet on random thin graphs
- Evolution of Coordination in Social Networks: A Numerical Study
- A universal form of slow dynamics in zero-temperature random-field Ising model
- A simple model for multiple-choice collective decision making
- Metastable configurations of spin models on random graphs
- Stochastic optimization by message passing
- The T=0 random-field Ising model on a Bethe lattice with large coordination number: hysteresis and metastable states
- Stable, metastable and unstable states in the mean-field RFIM at T=0
- Multistable binary decision making on networks
- Contagion in an interacting economy
- Variational approximations for stochastic dynamics on graphs
- Fixation and escape times in stochastic game learning
- Stochastic evolution in populations of ideas
- Dynamical selection of Nash equilibria using Experience Weighted Attraction Learning: emergence of heterogeneous mixed equilibria
- Statics and dynamics of selfish interactions in distributed service systems