Majority dynamics on trees and the dynamic cavity method

DOI10.1214/10-AAP729zbMath1266.60159arXiv0907.0449OpenAlexW3100656268MaRDI 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 learningtreesconsensusbest response dynamicsmajority dynamicsdynamic cavity methodIsing spin dynamicsparallel/synchronous dynamics

Mathematics Subject Classification ID

Trees (05C05) Cooperative games (91A12) Interacting particle systems in time-dependent statistical mechanics (82C22) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Decentralized systems (93A14) Rationality and learning in game theory (91A26) Mathematical sociology (including anthropology) (91D99)

Related Items

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

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