Majority Dynamics on Resampled Sparse Erdős--Rényi Graphs: Gaussian Winner Selection in Collaborative Agent Networks
Abstract
Collective decisions in agent networks emerge from repeated local interactions, as agents update their opinions (colors) based on their neighbors, potentially leading to consensus. In sparse communication graphs, repeated interactions can amplify both the initial majority preference and the random fluctuations caused by individual agents. Understanding when the initial majority determines the final preference and how quickly an agreement emerges is, therefore, a basic question in collective decision-making. We study binary majority dynamics as an idealized model of this process. At each round, the interaction graph is independently resampled from the Erdős--Rényi model 𝔾(N,p), with p=blog N/N and fixed b>1. Each agent adopts the majority opinion among its neighbors, retaining its current opinion if there is a tie. For a fixed initial configuration, let Δ0 denote the initial difference between the number of blue agents and the number of red agents. We identify three regimes for the consensus time, determined by |Δ0|. First, when Δ0√p=O(1), the probability of blue unanimity is Φ(Δ0√(2p/π)) + o(1), where Φ is the cumulative distribution function of a standard Gaussian. Moreover, consensus is reached after (1+o(1))log N/loglog N rounds with high probability. Second, in the intermediate regime 1≪Δ0 √p≲ √N, we establish explicit high probability upper and lower bounds on the time to blue-unanimity. Lastly, when the initial blue advantage is above an explicit constant multiple of N/√(log N), blue unanimity is guaranteed within two rounds with high probability. Our findings provide a complete description of how the initial advantage influences winner selection and the speed of consensus in this type of majority dynamics with sparse interactions.
Related
- Collaborative representations for targeted causal inference under outcome selection
- Majority dynamics on sparse random graphs
- Minimax Slope Estimation and Support Recovery under Weak Gaussian Selection
- Sparsity by Default: The Theory and Practice of ARD in Gaussian Process Regression for Variable Selection
- AdaPS-LiNGAM: Adaptive Predecessor Selection for Linear Non-Gaussian Acyclic Models under Small-Sample Settings
BibTeX
@misc{dumitriu2026majority,
title = {{Majority Dynamics on Resampled Sparse Erdős--Rényi Graphs: Gaussian Winner Selection in Collaborative Agent Networks}},
author = {Ioana Dumitriu and Muchen Ju and Hai-Xiao Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.06159},
eprint = {2608.06159},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.06159},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Majority Dynamics on Resampled Sparse Erdős--Rényi Graphs: Gaussian Winner Selection in Collaborative Agent Networks
AU - Ioana Dumitriu
AU - Muchen Ju
AU - Hai-Xiao Wang
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2608.06159
UR - https://arxiv.org/abs/2608.06159
AB - Collective decisions in agent networks emerge from repeated local interactions, as agents update their opinions (colors) based on their neighbors, potentially leading to consensus. In sparse communication graphs, repeated interactions can amplify both the initial majority preference and the random fluctuations caused by individual agents. Understanding when the initial majority determines the final preference and how quickly an agreement emerges is, therefore, a basic question in collective decision-making. We study binary majority dynamics as an idealized model of this process. At each round, the interaction graph is independently resampled from the Erdős--Rényi model 𝔾(N,p), with p=blog N/N and fixed b>1. Each agent adopts the majority opinion among its neighbors, retaining its current opinion if there is a tie. For a fixed initial configuration, let Δ_0 denote the initial difference between the number of blue agents and the number of red agents. We identify three regimes for the consensus time, determined by |Δ_0|. First, when Δ_0√p=O(1), the probability of blue unanimity is Φ(Δ_0√(2p/π)) + o(1), where Φ is the cumulative distribution function of a standard Gaussian. Moreover, consensus is reached after (1+o(1))log N/loglog N rounds with high probability. Second, in the intermediate regime 1≪Δ_0 √p≲ √N, we establish explicit high probability upper and lower bounds on the time to blue-unanimity. Lastly, when the initial blue advantage is above an explicit constant multiple of N/√(log N), blue unanimity is guaranteed within two rounds with high probability. Our findings provide a complete description of how the initial advantage influences winner selection and the speed of consensus in this type of majority dynamics with sparse interactions.
ER -