LIPIcs.APPROX-RANDOM.2020.20.pdf
- Filesize: 0.51 MB
- 15 pages
Document
Reaching a Consensus on Random Networks: The Power of Few
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-11
File
Document Identifiers
Acknowledgements
We would like to thank A. Do, A, Ferber, A. Deneanu, J. Fox and X. Chen for inspiring discussions, H. V. Le, T. Can and L. T. D. Tran for proof-reading.
Cite AsGet BibTex
Linh Tran and Van Vu. Reaching a Consensus on Random Networks: The Power of Few. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.20
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.20
Abstract
A community of n individuals splits into two camps, Red and Blue. The individuals are connected by a social network, which influences their colors. Everyday, each person changes his/her color according to the majority of his/her neighbors. Red (Blue) wins if everyone in the community becomes Red (Blue) at some point.
We study this process when the underlying network is the random Erdos-Renyi graph G(n, p). With a balanced initial state (n/2 persons in each camp), it is clear that each color wins with the same probability.
Our study reveals that for any constants p and ε, there is a constant c such that if one camp has n/2 + c individuals at the initial state, then it wins with probability at least 1 - ε. The surprising fact here is that c does not depend on n, the population of the community. When p = 1/2 and ε = .1, one can set c = 6, meaning one camp has n/2 + 6 members initially. In other words, it takes only 6 extra people to win an election with overwhelming odds. We also generalize the result to p = p_n = o(1) in a separate paper.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Random graphs
- Mathematics of computing → Graph theory
- Mathematics of computing → Probability and statistics
Keywords
- Random Graphs Majority Dynamics Consensus
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. Time-space trade-offs in population protocols. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, page 2560–2579, USA, 2017. Society for Industrial and Applied Mathematics.
- Dan Alistarh, Rati Gelashvili, and Milan Vojnović. Fast and exact majority in population protocols. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, page 47–56, New York, NY, USA, 2015. Association for Computing Machinery. URL: https://doi.org/10.1145/2767386.2767429.
- Itai Benjamini, Siu-On Chan, Ryan O’Donnell, Omer Tamuz, and Li-Yang Tan. Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs. Stochastic Processes and their Applications, 126(9):2719–2733, September 2016. URL: https://doi.org/10.1016/j.spa.2016.02.015.
- Béla Bollobás. Models of Random Graphs, chapter 2, pages 34-50. Cambridge University Press, Cambridge, 2001. URL: https://doi.org/10.1017/CBO9780511814068.
- Peter Clifford and Aidan Sudbury. A model for spatial conflict. Biometrika, 60:581-588, 1973. URL: https://doi.org/10.1093/biomet/60.3.581.
- Morris H. DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118-121, 1974. URL: http://www.jstor.org/stable/2285509.
- Carl-Gustav Esseen. A moment inequality with an application to the central limit theorem. Scandinavian Actuarial Journal, 1956(2):160-170, 1956. URL: https://doi.org/10.1080/03461238.1956.10414946.
- Nikolaos Fountoulakis, Mihyun Kang, and Tamás Makai. Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs, 2019. URL: http://arxiv.org/abs/1910.05820.
- Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. URL: https://doi.org/10.1080/01621459.1963.10500830.
- Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Preliminaries, chapter 1, pages 1-23. John Wiley & Sons, Ltd, 2011. URL: https://doi.org/10.1002/9781118032718.ch1.
- Elchanan Mossel, Joe Neeman, and Omer Tamuz. Majority dynamics and aggregation of information in social networks. Autonomous Agents and Multi-Agent Systems, 28(3):408-429, May 2014. URL: https://doi.org/10.1007/s10458-013-9230-4.
- Elchanan Mossel and Omer Tamuz. Opinion exchange dynamics. Probab. Surveys, 14:155-204, 2017. URL: https://doi.org/10.1214/14-PS230.
- I. G. Shevtsova. An improvement of convergence rate estimates in the lyapunov theorem. Doklady Mathematics, 82(3):862-864, December 2010. URL: https://doi.org/10.1134/S1064562410060062.
-
Linh Tran and Van Vu. Power of few: The general case. Paper in preparation.
- Roman Vershynin. Concentration of Sums of Independent Random Variables, pages 11-37. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018. URL: https://doi.org/10.1017/9781108231596.006.