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. https://resolver.caltech.edu/CaltechAUTHORS:20161110-074103834
![]() |
PDF
- Submitted Version
See Usage Policy. 150kB |
Use this Persistent URL to link to this item: https://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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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. | ||||||||||||
DOI: | 10.1109/ALLERTON.2016.7852341 | ||||||||||||
Record Number: | CaltechAUTHORS:20161110-074103834 | ||||||||||||
Persistent URL: | https://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: | 11 Nov 2021 04:53 |
Repository Staff Only: item control page