Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 11, 2016 | Submitted
Report Open

Efficient Bayesian Social Learning on Trees


We consider a set of agents who are attempting to iteratively learn the 'state of the world' from their neighbors in a social network. Each agent initially receives a noisy observation of the true state of the world. The agents then repeatedly 'vote' and observe the votes of some of their peers, from which they gain more information. The agents' calculations are Bayesian and aim to myopically maximize the expected utility at each iteration. This model, introduced by Gale and Kariv (2003), is a natural approach to learning on networks. However, it has been criticized, chiefly because the agents' decision rule appears to become computationally intractable as the number of iterations advances. For instance, a dynamic programming approach (part of this work) has running time that is exponentially large in min(n; (d - 1)^t), where n is the number of agents. We provide a new algorithm to perform the agents' computations on locally tree-like graphs. Our algorithm uses the dynamic cavity method to drastically reduce computational effort. Let d be the maximum degree and t be the iteration number. The computational effort needed per agent is exponential only in O(td) (note that the number of possible information sets of a neighbor at time t is itself exponential in td). Under appropriate assumptions on the rate of convergence, we deduce that each agent is only required to spend polylogarithmic (in 1=є) computational effort to approximately learn the true state of the world with error probability є, on regular trees of degree at least five. We provide numerical and other evidence to justify our assumption on convergence rate. We extend our results in various directions, including loopy graphs. Our results indicate efficiency of iterative Bayesian social learning in a wide range of situations, contrary to widely held beliefs.

Additional Information

Submitted on 7 Feb 2011. October 29, 2013. Supported by 3Com Corporation Stanford Graduate Fellowship. Supported by ISF grant 1300/08. We would like to thank Andrea Montanari, Elchanan Mossel and Allan Sly for valuable discussions.

Attached Files

Submitted - 1102.1398.pdf


Files (456.2 kB)
Name Size Download all
456.2 kB Preview Download

Additional details

August 19, 2023
October 23, 2023