CaltechAUTHORS
  A Caltech Library Service

Efficient Bayesian Learning in Social Networks with Gaussian Estimators

Mossel, Elchanan and Olsman, Noah and Tamuz, Omer (2016) Efficient Bayesian Learning in Social Networks with Gaussian Estimators. In: 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2016. IEEE , Piscataway, NJ, pp. 425-432. ISBN 978-1-5090-4551-8. http://resolver.caltech.edu/CaltechAUTHORS:20161110-074103834

[img] PDF - Submitted Version
See Usage Policy.

146Kb

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

Abstract

We consider a group of Bayesian agents who try to estimate a state of the world θ through interaction on a social network. Each agent v initially receives a private measurement of θ: a number S_v picked from a Gaussian distribution with mean θ and standard deviation one. Then, in each discrete time iteration, each reveals its estimate of θ to its neighbors, and, observing its neighbors’ actions, updates its belief using Bayes’ Law. This process aggregates information efficiently, in the sense that all the agents converge to the belief that they would have, had they access to all the private measurements. We show that this process is computationally efficient, so that each agent’s calculation can be easily carried out. We also show that on any graph the process converges after at most 2N · D steps, where N is the number of agents and D is the diameter of the network. Finally, we show that on trees and on distance transitive-graphs the process converges after D steps, and that it preserves privacy, so that agents learn very little about the private signal of most other agents, despite the efficient aggregation of information. Our results extend those in an unpublished manuscript of the first and last authors.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ALLERTON.2016.7852341DOIArticle
http://ieeexplore.ieee.org/document/7852341/PublisherArticle
https://arxiv.org/abs/1002.0747arXivDiscussion Paper
ORCID:
AuthorORCID
Tamuz, Omer0000-0002-0111-0418
Additional Information:© 2016 IEEE. Date of Conference: 27-30 Sept. 2016. Date Added to IEEE Xplore: 13 February 2017. This work is an extension of an unpublished manuscript by Mossel and Tamuz. We thank Shachar Kariv for introducing us to the literature on learning on networks and for fascinating discussions. Thanks go to Marcus Möbius for an interesting discussion and for directing us to the work of DeMarzo et al., after a draft of this note had been circulated. We also thank Grant Schoenebeck, Rafael M. Frongillo and Adam Kalai for interesting discussions regarding follow-up work. We thank Ashwin Ganesan for a lesson on distance-transitive graphs. Finally, we are indebted to Yaron Singer for much support and helpful suggestions on writing the results.
Record Number:CaltechAUTHORS:20161110-074103834
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20161110-074103834
Official Citation:V. Kostina, "When is Shannon's lower bound tight at finite blocklength?," 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA, 2016, pp. 982-989. doi: 10.1109/ALLERTON.2016.7852341
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71907
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:10 Nov 2016 22:36
Last Modified:21 Feb 2017 17:25

Repository Staff Only: item control page