- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies synchronous majority dynamics on independently resampled Erdős–Rényi graphs with edge probability p = b log N/N, for fixed b > 1. It characterizes how the initial opinion imbalance affects the eventual winner and the time to unanimity. The main result establishes a Gaussian winner-selection law in the critical window, together with an asymptotically precise consensus time of log N/log log N. The paper also provides two-sided bounds on consensus time above the critical window and sufficient conditions for unanimity within one or two rounds. A corollary shows that, under independent initial votes with a specified vanishing bias, the final consensus matches the asymptotic accuracy of centralized majority voting. The theoretical results are complemented by simulations.
Critical strengths
The paper provides a precise characterization of winner selection near balance. Identifying the critical initial-advantage scale is useful, but obtaining the limiting winning probability and the leading-order consensus time gives a substantially more complete picture. In particular, the analysis explains when early fluctuations can overturn the initial majority and when subsequent updates reliably amplify the selected opinion.
The treatment of the drift near balance is a useful technical contribution. Approximating the two flip probabilities separately does not provide sufficient accuracy to control their small difference. The local comparison in Equation (3.17) addresses this issue directly. Combined with the existing one-step central limit theorem and concentration bounds, it supports both majority amplification and the lower and upper bounds on consensus time.
Critical weaknesses
The implications for learning and collaborative AI systems remain limited. The model assumes homogeneous agents, binary opinions, synchronous updates, and a completely independent communication graph at every round. Resampling is particularly consequential because it removes dependence between the current opinions and the next interaction graph. The paper gives an interesting mathematical benchmark, but does not establish how its conclusions inform the analysis or design of a learning system. Corollary 3.6 provides a useful information-aggregation interpretation, although it concerns independent initial votes under a specific bias scaling. The experiments examine the same idealized model and therefore do not strengthen the broader application claims.
Several statements make the contribution and its relationship to previous work less precise than they should be. Lines 64-69 describe fixed initial advantages as leading to majority victory with high probability in earlier dense-graph results. In particular, Sah and Sawhney obtain a nontrivial Gaussian winning probability, which remains below one for fixed p and a fixed positive advantage. Appendix G gives a more accurate account, so these sections are inconsistent. Separately, lines 93-95 describe the one- and two-round conditions as critical thresholds, whereas Theorem 3.1 establishes sufficient conditions without matching converse results. These issues are fixable, but they matter because distinguishing a positive winning advantage from high-probability victory, and a sufficient condition from a sharp threshold, is central to the paper.
The numerical validation is limited to a single population size, N = 10⁴. Since the main results concern asymptotic winning probabilities and consensus times, these experiments do not show how the approximation errors change with N or how quickly the predicted scaling becomes visible. Experiments across several population sizes would make the finite-size relevance of the theory clearer. This limits the empirical validation, although it does not undermine the proofs.
Questions for authors
Could you clarify the precise technical advance over the existing one-step CLT and the sparse resampled-SBM tools discussed in Appendix G.2? The local comparison in Equation (3.17) appears to be an important additional ingredient. A more explicit explanation of which estimates fail near balance in the previous analysis, and how the present argument overcomes that failure, would help assess the significance of the contribution. This is a clarification request about the current results.
Are the constants in Theorem 3.1 proved to be sharp? If so, where are the matching converse statements established? Otherwise, could you consistently describe these as sufficient conditions and revise the claim in lines 93-95? I am asking about the strength of the current theorem, rather than requesting an additional result.
Could you reconcile the descriptions of the dense-graph results in lines 64-69 with Appendix G.1? In particular, please distinguish high-probability unanimity from high-probability victory of the initially larger camp.
7 comments
3. Distinction between our results and previous dense-graph results.
Thanks for pointing out these issues. We will clarify the scope of previous works and their relation to ours more clearly in the revision.
There is a major line of research on Majority Dynamics, focusing on the static update graph case. In the dense regime where remains constant or decays slowly with , [1,2,3,5] proved rapid stabilization and show that constant size or even one-vertex advantages can affect the winning probability. The asymptotically exact winning probability was calculated explicitly by Sah--Sawhney [4], which is In the sparse regime, isolated vertices below the connectivity threshold create an immediate obstruction to unanimity; above the connectivity threshold, under the static update graph, [6,7,8,9,10] show that sparse random graphs can still amplify small initial majorities to consensus, and subsequent work progressively lowers the required edge density for this sparse “power of few” behavior.
Note that, Sah--Sawhney [4] focus on the regime where and the update graph is static. Hence, neither their conclusions nor their techniques can be borrowed directly to our purpose. Our results establish the corresponding Gaussian winner selection probability at the scale , together with high-probability majority victory when . As a saint check, this is consistent with Sah--Sawhney [4] since .
[1]. 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”. In: Stochastic Processes and their Applications 126.9 (2016)
[2]. Ross Berkowitz and Pat Devlin. “Central limit theorem for majority dynamics: Bribing three voters suffices”. In: arXiv preprint arXiv:2010.08172.
[3]. Nikolaos Fountoulakis, Mihyun Kang, and Tam´as Makai. “Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs”. In: Random Structures & Algorithms
[4]. Ashwin Sah and Mehtaab Sawhney. “Majority dynamics: The power of one”. In: Israel Journal of Mathematics (2024), pp. 1–49
[5]. Linh Tran and Van Vu. “Reaching a Consensus on Random Networks: The Power of Few”. In: Theory of Computing 19.6 (2023), pp.1–21
[6]. Debsoumya Chakraborti, Jeong Han Kim, Joonkyung Lee, and Tuan Tran. “Majority dynamics on sparse random graphs”. In: Random Structures & Algorithms 63.1 (2023), pp. 171–191
[7]. Sean Jaffe. “A new bound in Majority Dynamics on Random Graphs”. In: arXiv preprint arXiv:2503.14401 (2025).
[8]. Jeong Han Kim and BaoLinh Tran. “A new density limit for unanimity in majority dynamics on random graphs”. In: arXiv preprint arXiv:2503.07447 (2025)
[9]. BaoLinh Tran and Van Vu. “The “Power of Few” Phenomenon: The Sparse Case”. In: Random Structures & Algorithms 66.1 (2025)
[10]. Ahad N Zehmakan. “Opinion forming in Erd˝os–R´enyi random graph and expanders”. In: Discrete Applied Mathematics 277 (2020), pp. 280–290
4. Numerical validation in a single population size. Thank you for raising this concern. We will include and compare experiment outcomes at several population sizes in the revised version.
5. The implications for learning and collaborative AI systems remain limited.
Corollary 3.7 establishes that sparse, decentralized communication matches the asymptotic accuracy of centralized majority voting on the initial answers. For independent initial binary answers, each correct with probability , it gives
\qquad T=(1+o(1))\frac{\log N}{\log\log N} \quad\text{with high probability}.$$ Each agent communicates with $b\log N$ peers on average per round. The correct label enters only the evaluation of the outcome. This quantifies how local exchanges aggregate initially weak information and disseminate a collective decision throughout the network, accounting for the dependence created by repeated interactions. The winner-selection theorem also quantifies error propagation. For a fixed normalized initial advantage $x_0>0$ in favor of the correct answer, correct and incorrect unanimity occur with probabilities $\Phi(x_0)+o(1)$ and $\Phi(-x_0)+o(1)$, respectively. These laws separate decision accuracy from the speed of agreement and quantify how early fluctuations affect the final answer. Together, the results provide an explicit benchmark for collaborative decision systems with sparse, changing communication: final accuracy relative to centralized voting, the initial signal needed for reliable selection, and the number of interaction rounds needed to reach agreement.
We would like to thank the reviewer for their useful feedbacks. In the revised version, we have added a paragraph for
Technical contributions, addressing our technical contributions and explain the connections and distinctions with previous work explicitly. We provide our responses below to reviewer's questions below.1. Technical advance over the existing one-step CLT and the sparse resampled-SBM
1.1. Precise drift at the critical scale. As explained in equation (3.16), the conditional drift depends on the difference between the red-to-blue ptR and blue-to-red ptB flip probabilities. When p≍log(N)/N=o(1), this drift is ptR−ptB≍NppΔt, which produces a mean advantage of order ΔtlogN. However, to approximate the flip probabilities, a direct application of Berry–Esseen to each probability gives an additive approximation error O((logN)−1/2), which neither accounts for the half-integer lattice correction nor achieves the sharper O((logN)−1) error needed. After multiplicating by N, the resulting error is O(N/logN), which overwhelms the drift size ΔtlogN when Δt is small. For example, at the critical scale Δt≍N/logN, where the desired flip-probability difference is only of order N−1/2. Thus the approximation error of a direct application of Berry–Esseen is not affordable.
To address this issue, we prove a sharper approximation error O((logN)−1) in
=\sqrt{\frac2\pi} \frac{p\Delta_t}{\sqrt{(N-1)p(1-p)}} +O\left(\frac{p|\Delta_t|}{\log N}\right).$$ The proof of this Lemma combines Poisson coupling, continuity-corrected local Gaussian estimates, and an exact telescoping comparison, which are novel in the literature. Moreover, at $|\Delta_t|\asymp\sqrt{N/\log N}$, and It identifies the conditional mean to accuracy $o(\sqrt N)$ and determines the exact Gaussian shift $x_0=\Delta_0\sqrt{2p/\pi}$ when combined with the Berkowitz--Devlin centered one-step CLT. **1.2. Uniform amplification under dependent updates.** We establish two-sided amplification, $$c_1\sqrt{\log N}\,\Delta_t \le\Delta_{t+1}\le C_2\sqrt{\log N}\,\Delta_t,$$ with failure probability at most $2\exp(-c\Delta_t^2\log N/N)$, uniformly over configurations with $\sqrt{N/\log N}\le\Delta_t\le KN/\sqrt{\log N}$. This provides quantitative control of both the growth rate and the reliability of majority amplification. Our application of the read-$k$ Chernoff bound accounts for shared-edge dependence through the read-$2$ structure of the updates. The two-sided control supplies matching leading upper and lower consensus-time bounds. **1.3. Sharp winner selection and consensus-time asymptotics.** These estimates yield the uniform Gaussian winning probability $\Phi(x_0)+o(1)$ and the consensus time $(1+o(1))\log N/\log\log N$ throughout the critical window. They resolve the $p^{-1/2}$ advantage scale for homogeneous resampled ER graphs. We combine the general sparse-binomial and concentration tools from the sparse-SBM analysis with our local comparison to establish these results for $a=b$, complementing its dynamical results for fixed assortativity $a>b$. We will highlight these contributions in Section 3.5. ***2. Regarding 'sharp constants' in Theorem 3.1.*** We thank the reviewer for identifying this gap. Matching necessary conditions can be established. We will include both sufficient and necessary conditions in the revised version. Specifically, writing $T$ for the first time either color reaches unanimity, we can obtain the following lower bounds on the time to convergence: - One-round unanimity: for every fixed $r\in(r_*,1/2)$, $$|\Delta_0|\le(1-2r)N \quad\Longrightarrow\quad \mathbb P(T\ge2)=1-o(1).$$ - Two-round unanimity: for every fixed $K\in(0,K_2^{\mathrm{ER}}(b))$, $$|\Delta_0|\le K\frac{N}{\sqrt{\log N}} \quad\Longrightarrow\quad \mathbb P(T\ge3)=1-o(1).$$ Together with the existing sufficient conditions, these results establish the sharp leading constants $1-2r_*=\sqrt{2b-1}/b$ and $K_2^{\mathrm{ER}}(b)$. We will organize each theorem to include both sufficient and necessary bounds and revise the introductory wording to ''sharp leading-order thresholds''. This qualification makes it clear that the results concern fixed gaps from the leading constants and do not locate the finer transition windows around equality.Lemma A.4, which also provides a uniform comparison of the conditional flip probabilities whose error scales with the current advantage