Tractable Bayesian social learning on trees

We study a model of Bayesian agents in social networks who learn from the actions of their neighbors. Agents attempt to iteratively estimate an unknown `state of the world´ s from initial private signals, and the past actions of their neighbors in the network. We investigate the computational problem the agents face in implementing the (myopic) Bayesian decision rule. When private signals are independent conditioned on s, and when the social network graph is a tree, we provide a new `dynamic cavity algorithm´ for the agents´ calculations, with computational effort that is exponentially lower than a naive dynamic program. We use this algorithm to perform the first numerical simulations of Bayesian agents on networks with hundreds of nodes, and observe rapid learning of s in some settings.