CaltechAUTHORS
  A Caltech Library Service

Efficient Bayesian Social Learning on Trees

Kanoria, Yashodhan and Tamuz, Omer (2011) Efficient Bayesian Social Learning on Trees. . (Submitted) https://resolver.caltech.edu/CaltechAUTHORS:20161110-083842987

[img] PDF - Submitted Version
See Usage Policy.

445Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20161110-083842987

Abstract

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
https://arxiv.org/abs/1102.1398arXivArticle
ORCID:
AuthorORCID
Tamuz, Omer0000-0002-0111-0418
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.
Funders:
Funding AgencyGrant Number
Israel Science Foundation1300/08
3Com CorporationUNSPECIFIED
Record Number:CaltechAUTHORS:20161110-083842987
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20161110-083842987
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71911
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:11 Nov 2016 02:06
Last Modified:03 Oct 2019 16:12

Repository Staff Only: item control page