Time-Independent Correct Majorities for Asynchronous Informative Processes in Balanced Binary Trees

Abstract

We study the dynamics of information flow in social networks. In our model, individuals gather and share information about a binary decision, for which there is a correct and incorrect choice. Individuals start by holding independent private beliefs that are biased toward the correct choice and no publicly announced belief. Over time, they spread information locally to their connections in the social network. The dynamics of this model are asynchronous, where at each time step, exactly one random individual announces a public belief, and non-Bayesian, where individuals who announce simply copy the majority belief of their neighbors in the social network, tie-breaking with their own private belief. Our main technical innovation uses time-independent analysis to study the independence of announcements of vertex pairs, which allows us to entirely bypass reasoning in prior work about forming an initial majority through time-dependent arguments. We also prove that in balanced binary trees, a correct majority of public beliefs exists with high probability at every time after more than half of the vertices have publicly announced a belief, which implies a correct majority at stabilization.