Asynchronous Majority Dynamics in Trees

Abstract

We study information aggregation in social networks via the asynchronous majority dynamics model. In this model, individuals independently draw a private signal, which is correct with probability $\frac{1}{2} + \delta$. At each time step, a random individual is chosen, and that individual announces the majority announced opinion of his neighbors, tiebreaking in favor of his own private signal. In particular, we examine how this model operates in trees.

We specify a procedure for rooting trees that optimizes an existing technique for proving that certain trees stabilize in a correct majority. We also outline a novel proof technique for showing that trees stabilize in a correct majority, in which we show that under asynchronous majority dynamics, "blocks" occur in long paths between nodes with high probability. Finally, we describe a particular binary tree and show that existing techniques fail to prove that this binary tree stabilizes in a correct majority.