Majority dynamics on trees and the dynamic cavity method

DOI10.1214/10-AAP729zbMath1266.60159arXiv0907.0449MaRDI QIDQ655579

Yashodhan Kanoria, Andrea Montanari

Publication date: 4 January 2012

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

social learning; trees; consensus; best response dynamics; majority dynamics; dynamic cavity method; Ising spin dynamics; parallel/synchronous dynamics

Mathematics Subject Classification ID

05C05: Trees

91A12: Cooperative games

82C22: Interacting particle systems in time-dependent statistical mechanics

60K35: Interacting random processes; statistical mechanics type models; percolation theory

93A14: Decentralized systems

91A26: Rationality and learning in game theory

91D99: Mathematical sociology (including anthropology)

Related Items

Opinion Forming in Erdös-Rényi Random Graph and Expanders, The matrix product approximation for the dynamic cavity method, Probabilistic consensus via polling and majority rules, Majority dynamics with one nonconformist, Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs, Self-organized segregation on the grid, Phase transition of the 2-choices dynamics on core-periphery networks, A note on the majority dynamics in inhomogeneous random graphs, On the spread of influence in graphs, Zero-temperature Glauber dynamics on the 3-regular tree and the median process, Threshold behavior of bootstrap percolation, Opinion forming in Erdős-Rényi random graph and expanders, Dynamic matching pennies on networks, Majority dynamics and the retention of information, Central limit theorem for majority dynamics: bribing three voters suffices, Improved intolerance intervals and size bounds for a Schelling-type spin system

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spin glasses and Stein's method
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• Gibbs measures and phase transitions on sparse random graphs
• Periodic behaviour of generalized threshold functions
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Gibbs measures and phase transitions
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
• Glauber dynamics on trees: Boundary conditions and mixing time
• Glauber dynamics on trees and hyperbolic graphs
• Stretched exponential fixation in stochastic Ising models at zero temperature
• An elementary proof of the local central limit theorem
• Cugliandolo-Kurchan equations for dynamics of spin-glasses
• Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree
• The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
• Counting independent sets up to the tree threshold
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Expander graphs and their applications
• Information, Physics, and Computation
• Learning from Neighbours
• Zero-temperature ising spin dynamics on the homogeneous tree of degree three
• Reaching a Consensus
• Contagion