Majority Dynamics on Resampled Sparse Erdos–R\'enyi Graphs: Gaussian Winner Selection in Collaborative Agent Networks

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 Erdos–R\'enyi model $\mathbb{G}(N,p)$, with $p=b\log N/N$ and fixed $b>1$. Each agent adopts the majority opinion (color) among its neighbors, retaining its current opinion if there is a tie. For a fixed initial configuration, let ${\Delta }_0$ denote the initial difference between the number of blue agents and the number of red agents. We identify three regimes for winner selection and consensus time, determined by the size of ${\Delta }_0$. First, in the critical window ${\Delta }_0\sqrt{p}=O(1)$, the probability of blue unanimity is $\Phi \left({\Delta }_0\sqrt{2p/\pi }\right)+o(1),$ where $\Phi$ is the cumulative distribution function of a standard Gaussian random variable. Moreover, consensus is reached after $(1+o(1))\log N/\log \log N$ rounds with high probability. Second, in the intermediate regime $1\ll {\Delta }_0\sqrt{p}\lesssim \sqrt{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/\sqrt{\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.