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.
Revtex style, 56 pages, 21 figures
References in corpus (11)
- A message passing approach for general epidemic models
- Survey propagation: an algorithm for satisfiability
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- Dynamic message-passing equations for models with unidirectional dynamics
- Dynamics to equilibrium in Network Games: individual behavior and global response
- Equilibria, information and frustration in heterogeneous network games with conflicting preferences
- Evolution of Coordination in Social Networks: A Numerical Study
- A simple model for multiple-choice collective decision making
- 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
- Contagion in an interacting economy