Non-Bayesian Asynchronous Information Aggregation in Trees

Abstract

In this work, we study information aggregation in social networks. We use an asynchronous, non-Bayesian model motivated by historical instances of information cascades. In our model, nodes in a graph are assigned binary private signals independently at random, with a small bias in favor of one signal, called the \emph{ground truth} or \emph{correct signal}. Social learning of the private signals occurs via an asynchronous stochastic process. At every step, one node is chosen uniformly at random to make a public announcement. A chosen node will conform to the majority of its neighbors' public announcements, breaking ties using its own private signal. The process terminates in a stable state, meaning that no node would change its announcement if chosen. We are interested in quantifying how structural properties of the graph determine the announcements at termination.

Previously, Feldman et al. showed that in sparse (bounded max degree), expansive graphs, the process terminates in a correct consensus with high probability. This work extends their results by focusing on a less restrictive notion of sparsity. We show that in any tree, regardless of degree, after a slightly super-linear number of steps, the majority of the nodes will have the correct announcement with high probability. Furthermore, in contrast to the approach of Feldman et al., we cannot invoke expansiveness to conclude anything about the state of announcements at termination in trees. We provide a novel argument in the case of complete binary trees, showing that the process stabilizes in a correct majority with high probability.