Computer Science – Social and Information Networks
Scientific paper
2011-02-07
Computer Science
Social and Information Networks
11 pages, 1 figure, submitted
Scientific paper
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/\eps) computational effort to approximately learn the true state of the world with error probability \eps, 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.
Kanoria Yashodhan
Tamuz Omer
No associations
LandOfFree
Efficient Bayesian Social Learning on Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Efficient Bayesian Social Learning on Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Bayesian Social Learning on Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-682217