acceptodds
Under review as a conference paper at ICLR 2027

Majority Dynamics on Resampled Sparse Erdos–R\'enyi 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 Erdos–R\'enyi model , with and fixed . 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 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 . First, in the critical window , the probability of blue unanimity is where is the cumulative distribution function of a standard Gaussian random variable. Moreover, consensus is reached after rounds with high probability. Second, in the intermediate regime , 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 , 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Collaborative Agent Networks, Majority Dynamics, Erd\H{o}s--R\'enyi Graphs

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_xT63OpenReview ↗
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

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 ptRp_t^{\mathcal R} and blue-to-red ptBp_t^{\mathcal B} flip probabilities. When p≍log⁡(N)/N=o(1)p \asymp \log(N)/N = o(1), this drift is ptR−ptB≍pΔtNpp_t^{\mathcal R}-p_t^{\mathcal B}\asymp \frac{p\Delta_t}{\sqrt{Np}}, which produces a mean advantage of order Δtlog⁡N\Delta_t \sqrt{\log N}. However, to approximate the flip probabilities, a direct application of Berry–Esseen to each probability gives an additive approximation error O((log⁡N)−1/2)O((\log N)^{-1/2}), which neither accounts for the half-integer lattice correction nor achieves the sharper O((log⁡N)−1)O((\log N)^{-1}) error needed. After multiplicating by NN, the resulting error is O(N/log⁡N)O(N/\sqrt{\log N}), which overwhelms the drift size Δtlog⁡N\Delta_t \sqrt{\log N} when Δt\Delta_t is small. For example, at the critical scale Δt≍N/log⁡N\Delta_t\asymp\sqrt{N/\log N}, where the desired flip-probability difference is only of order N−1/2N^{-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)O((log N)^{-1}) in Lemma A.4, which also provides a uniform comparison of the conditional flip probabilities whose error scales with the current advantage

=\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.

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 pp remains constant or decays slowly with NN, [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 Φ(Δ02pπ(1−p))+o(1).\Phi\left(\Delta_0\sqrt{\frac{2p}{\pi(1-p)}}\right)+o(1). 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 pN≫log⁡NpN \gg \log N 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 Φ(Δ02pπ)+o(1)\Phi\left(\Delta_0\sqrt{\frac{2p}{\pi}}\right)+o(1) at the scale Δ0≍p−1/2\Delta_0\asymp p^{-1/2}, together with high-probability majority victory when Δ0p→∞\Delta_0\sqrt p\to\infty. As a saint check, this is consistent with Sah--Sawhney [4] since p=o(1)p = o(1).

[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 NN 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 1/2+θ/N1/2+\theta/\sqrt N, 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.
Reviewer_7ELcOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies synchronous majority dynamics on an undirected graph independently resampled from G(N,p)G(N,p) each round, with p=blog⁡N/Np=b\log N/N and fixed b>1b>1. All nodes initially hold one of two colors, with an initial bias Δ0\Delta_0 toward one of them. The paper provides a mathematical analysis linking Δ0\Delta_0 to both the fixation probability and the number of rounds until consensus. In particular, the authors show that when the bias satisfies Δ0p=O(1)\Delta_0 \sqrt{p} = O(1), the probability that the majority color wins is Φ(Δ02p/π)+o(1)\Phi(\Delta_0 \sqrt{2p/\pi})+ o(1) and the convergence time is log⁡N/log⁡log⁡N\log N/\log \log N. They also show that if the bias is larger, the majority color wins w.h.p., and provide sharp bounds on how much the convergence time decreases.

Critical strengths
  1. A meaningful extension to sparse, dependent updates. The strength of the paper is a generally tight analysis of an unexplored setting: the novelty lies in simultaneously analyzing a setting where agent updates are mutually dependent and the underlying graph is sparse and dynamically resampled rather than fixed.
Critical weaknesses
  1. The significance for learning and collaborative AI agents is insufficiently established. The paper only mentions a non-peer-reviewed preprint (El et al. 2026) to motivate and justify the significance of this process. Moreover, from a reading of that reference, it is not clear how the majority dynamics studied here fits the model of El et al. beyond the mere fact that agents hold opinions. The interaction pattern is substantially different. This is a critical weakness of the paper.

  2. The paper omits a significant body of related work. One of the most prominent missing references is 'Limit Laws for Consensus Protocols on the Complete Graph' by Becker and Panagiotou (PODC'26). That paper studies both fixation probability and convergence time for majority-like dynamics using similar techniques. The key difference in their model is that at each round, agents sample another agent's color u.a.r., meaning that if agent ii samples agent jj, jj does not necessarily sample ii in the same round. Another important missing line of work concerns biased majority opinion dynamics, such as Lesfari et al. (IJCAI 2022), who studied majority dynamics on sparse fixed graphs where, additionally, agents adopt a preferred opinion with a certain probability. It would be valuable to explicitly differentiate the proposed model from these prior works, particularly with applications to collaborative AI agents in mind.

  3. The presentation overstates parts of the contribution. Page 2, lines 93–95 describes the one- and two-round conditions as explicitly characterized critical thresholds. However, Theorem 3.1 only establishes success above sufficient bounds; I could not find corresponding failure results below them.

  4. The technical novelty and difficulty are not clearly delineated. While I have not checked every proof in full detail, having worked on majority dynamics, the techniques used appear fairly standard. It would be very helpful to include a paragraph clarifying where the analysis relies on standard machinery and where the authors had to introduce novel technical ideas or overcome non-trivial hurdles.

Questions for authors
  1. What concrete question about collaborative AI agents does your model answer beyond the mathematics of majority consensus? In what way your model fits better than similar ones?

  2. What are the main technical challenges of your results?

5 comments

We would like to thank the reviewer for their useful feedbacks. In the revised version, we will add references, and explain the connections and distinctions explicitly. We will also highlight our technical novelty. We provide our responses below to reviewer's questions below.

1. The significance for learning and collaborative AI agents.
Our model provides an idealized benchmark, under which agents exchanges initially imperfect answers through changing reciprocal interactions, without receiving additional evidence. Asymmetric querying and persistent directional influences—potentially representing continuing external guidance, feedback, or preferences—are also relevant mechanisms. We will clarify this scope in the motivation and related-work discussion, explaining which aspects our results address and which require extensions of the model.

2. Related literature. Our study is not an extension of Becker and Panagiotou (PODC'26) or Lesfari et al. (IJCAI 2022). In fact, we didn't notice those two papers while we are working on this project. We thank the reviewer for bringing this relevant paper to our attention. We highlight the difference below.

2.1. Regarding Becker and Panagiotou (PODC'26). In their opinion update model, conditional on the current opinion configuration, the next-round opinion updates of all vertices are jointly independent. Consequently, each vertex contains independently sampled contacts, yielding the exact transition Xt+1∣Xt∼Bin⁡(n,f(Xt/n))X_{t+1}\mid X_t\sim\operatorname{Bin}(n,f(X_t/n)) for a fixed update function ff. Their high-probability guarantee that the initial majority becomes the unanimous opinion considers an initial population count X0=n/2+dnX_0=n/2+d\sqrt n with d→∞d\to\infty, and therefore an initial bias larger than the square-root scale. Their Gaussian winner-selection theorem also treats bounded dd, but in that regime both opinions retain a nonvanishing probability of winning. See Becker and Panagiotou, Theorem 1.2 and Corollary 1.7.

However, in our model, the edge e=(i,j)e = ( i, j ) contributes to both endpoints’ decisions. Thus the next-round opinions on ii and jj remain dependent, even conditional on the entire current configuration. Consequently, the conditional binomial transition above does not apply, and common concentration inequalities can't be applied directly. Our results establish high-probability preservation of the initial majority under dependent updates and substantially smaller initial advantages, where the initial advantage can be down to the order Δ0=Nlog⁡log⁡N=o(N)\Delta_0=\sqrt{\frac{N}{\log\log N}}=o(\sqrt N), much smaller than previous literature.

Moreover, our analysis require novel ideas from the technical level. Note that the expected neighborhood size blog⁡Nb\log N grows with the population, producing an amplification factor of order log⁡N\sqrt{\log N}. Therefore, establishing these results requires additional technical arguments, such as uniform estimates for changing local update laws, precise control of the small drift generated by the initial imbalance, and concentration bounds that account for shared-edge dependence, which are different from the common strategy such as Gaussian fluctuations. In fact, as will be explained in details in the 4th point, we provide a sharper estimate on the difference between flip probabilities, which can't be achieved via a direct application of Berry-Essen approximation.

2.2. Regarding Lesfari et al. (IJCAI 2022). The central distinction is the difference between persistent bias in the update rule and statistical bias confined to the initial opinions. Their process evolves on a fixed graph: an updating agent adopts the preferred opinion with probability α\alpha, and otherwise follows its neighborhood majority. They consider both update schedules, presenting their results primarily for asynchronous dynamics, and demonstrate polynomial or exponential expected convergence times depending on the graph structure and bias. Our update rule is color-symmetric and synchronous, with no preferred-opinion override. In our correctness formulation, the correct label is used only to evaluate the outcome; it is not supplied to the agents or the update rule. Both unanimous configurations are absorbing, and either can prevail. Our question is therefore how communication preserves and aggregates initially available information, whereas persistent-bias models examine the spread of an opinion continually favored during the dynamics.

3. 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 TT 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∈(r∗,1/2)r\in(r_*,1/2),
\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.

4. Technical novelty and difficulty. We thank the reviewer for raising this advice for exposition. In the revised version, we will strengthen this distinction in Section 3.5, “Proof Overview and Technical Contributions.” Here, we mention our two technical contributions, which distinguish our analysis from the standard probabilistic tools.

4.1. Sharper estimates of drift in flip probabilities via Poisson coupling. As explained in equation (3.16), the conditional drift depends on the difference between the red-to-blue ptRp_t^{\mathcal R} and blue-to-red ptBp_t^{\mathcal B} flip probabilities. When p≍log⁡(N)/N=o(1)p \asymp \log(N)/N = o(1), this drift is ptR−ptB≍pΔtNpp_t^{\mathcal R}-p_t^{\mathcal B}\asymp \frac{p\Delta_t}{\sqrt{Np}}, which produces a mean advantage of order Δtlog⁡N\Delta_t \sqrt{\log N}. However, to approximate the flip probabilities, a direct application of Berry–Esseen to each probability gives an additive approximation error O((log⁡N)−1/2)O((\log N)^{-1/2}), which neither accounts for the half-integer lattice correction nor achieves the sharper O((logN)−1)O((log N)^{-1}) error needed. After multiplicating by NN, the resulting error is O(N/log⁡N)O(N/\sqrt{\log N}), which overwhelms the drift size Δtlog⁡N\Delta_t \sqrt{\log N} when Δt\Delta_t is small. For example, at the critical scale Δt≍N/log⁡N\Delta_t\asymp\sqrt{N/\log N}, where the desired flip-probability difference is only of order N−1/2N^{-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)O((log N)^{-1}) in Lemma D.4, which combines Poisson coupling, continuity-corrected local Gaussian estimates, and an exact telescoping comparison. Importantly, improving each separate distributional approximation is still insufficient: the comparison must preserve cancellation between the two transition laws. The telescoping identity in Section 3.5 converts their difference into a sum of local probabilities. Consequently, the approximation errors accumulate only to O(pΔt/log⁡N)O(p\Delta_t/\log N), yielding ptR−ptB=2πpΔt(N−1)p(1−p)+O(pΔtlog⁡N)p_t^{\mathcal R}-p_t^{\mathcal B}= \sqrt{\frac2\pi}\frac{p\Delta_t}{\sqrt{(N-1)p(1-p)}} + O(\frac{p\Delta_t}{\log N}) in the critical window.

4.2. Identifying the sharp rapid-consensus constants requires retaining the exact large-deviation exponent.

In Section 3.5 paragraph 4. Fresh communication completes the decision, we explain how the one-vertex rare-event exponent Jb(r)=b(1−r−r)2J_b(r)=b(\sqrt{1-r}-\sqrt r)^2 determines the one-round extinction density through Jb(r∗)=1J_b(r_*)=1. An exponential bound with unspecified constants would not identify this transition. Matching this extinction density with the Gaussian first-round reduction qK=Φ(−bK)q_K=\Phi(-\sqrt b K) then identifies the two-round constant through qK=r∗q_K=r_*.

Establishing those sharp constants also requires the converse direction under dependent updates. We combine large-deviation lower estimates with the full read-22 inequality: the former makes both expected camp sizes diverge, while the latter bounds the probability of an empty camp by e−μ/2e^{-\mu/2}. This establishes survival on the opposite side of the threshold and supplies the necessary conditions in Theorems 3.1 and 3.2.

4.3. Revision. In the revised version, we will emphasize our technical contributions. To the best of our knowledge, the matching leading constants for one- and two-round unanimity have not previously been established for studying majority dynamics. At the technical level, our use of large-deviation rate functions to identify these sharp constants and establish matching necessary and sufficient conditions provides a new analysis of the rapid-consensus transition in this setting. Likewise, our Poisson-coupling approach, combined with continuity correction, local Gaussian estimates, and an exact telescoping comparison, yields the sharper, advantage-sensitive error O(pΔt/log⁡N)O(p\Delta_t/\log N) needed to resolve the small drift. This precision is unavailable from a direct Berry–Esseen approximation and is essential for our uniform stepwise amplification bounds and Gaussian winner-selection law.

Reviewer_QFxMOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper consider the problem of opinion diffusion via simultaneous majority dynamics on a changing network. Specifically, the paper considers the case of only two opinions and that at each step a new erdos-reiny network is generated on the same set of N nodes with p = O(log N/N).

The paper proves the following results:

  • If one opinion is initially kept by a very large majority, then this opinion will become a consensus in one step with large probability
  • If one opinion has Omega(N/sqrt(log N)) more supporters than the other, then it will become a consensus in two steps with large probability
  • If one opinion has Omega(sqrt{N}/o(sqrt{log n})) more supporters than the other, then it will become a consensus in O(log N / log sqrt{log N}) with large probability
  • If one opinion has O(sqrt{N/log N}) more supporters than the other, then it is not guaranteed it will become a consensus. Anyway in time O(log N / log log N) a consensus will be reached, and the probability that will be reached on one opinion or on the other essentially follows a gaussian distributuion.
Critical strengths

The results provides an almost complete picture of the convergence of consensus with respect to the initial difference of supporters. Technical contribution is also interesting since it is essentially based on showing that the process can be well approximated through gaussian distributions, from which bound essentially follows.

Critical weaknesses
  1. I am not sure how much the contribution fits this setting. While opinion propagation algorithms are essentially of interest in ICLR community, I am not sure if specific results (focusing on changing random graph with critical choice of p) may be relevant.
  2. The paper is not so easy to read. It would benefit of much more high-level ideas, trying to convey what bound, constants, equations mean. There are also some notation that would benefit instead a formal definition such as Phi^-1 in eq 3.1
Questions for authors
  1. Can you stress how the technique used in this paper differ from the ones used for proving results in the static setting? Why is it not sufficient to use that argument plus the observation that with changing environment the probability of a "bad graph" decreases?
3 comments

We would like to thank the reviewer for their useful feedbacks. In the revised version, we will add high-level proof ideas, and highlight our technical novelty. We provide our responses below to reviewer's questions below.

1. Interests for ICLR community. In a large collaborative agents network, interactions between agents are rare on a global scale. Locally, each agent typically interacts with a small number of other agents. Moreover, on different days, agents may not interact with exactly the same contacts as the day before. Therefore, a sparse random graph that is resampled every day, is helpful in understanding behaviors of interaction networks. The Erdos-Renyi graph is one of the most prominent random graph model in the network science. The critical sparsity regime pN≍log⁡NpN\asymp \log N, which contains fruitful phenomena to explore, is also a reasonable assumption on the number of contacts to interact with every day. Therefore, we believe that our research serve a meaningful study for opinion propagation on a rapid-interacting agent network.

2. Exposition of the paper. We appreciate the suggestions on the exposition. We will revise our proof overview by providing high level proof ideas in the revised version.

3. Technical difference from the static setting. The static and resampled setting differ substantially.

The static setting that is closest to ours is the Tran and Vu (2025). We both consider the sparse Erdos-Renyi graph at the critical sparsity pN≥log⁡NpN \geq \log N. Their update graph is fixed throughout the opinion propagation. In their analysis, the probability estimate is only applied in first 2 rounds, followed by a iterative contraction argument on the community size, where the concentration of the adjacency matrix palys a central role, i.e., ∥A−EA∥≤log⁡N\|A - \mathbb E A\| \leq \sqrt{\log N}. We note that, in the static setting, when the initial advantage is at the critical scale Δ0≍p−1/2\Delta_0 \asymp p^{-1/2}, it remains open how the final winner is selected.

In the resampling setting, the contraction argument via ∥A−EA∥\|A - \mathbb E A\| is not necessary, due to the markov property of the process. We instead sharpen their first round analysis by providing sharper approximation to flip probabilities, provided in the Lemma A.4 of the current version. As we have replied to other reviewers, this sharper approximation can't be obtained via a direct application of Berry-Essen. Instead, we applied poisson coupling and continuity-corrected gaussian approximation to obtain this sharper estimate. Those technical contributions allowed us to go down to the critical initial advantage Δ0≍p−1/2\Delta_0 \asymp p^{-1/2}, and obtain winner probability that is asymptotically tight. To our knowledge, comparable results on the static graph remain open.

[1]. BaoLinh Tran and Van Vu. “The “Power of Few” Phenomenon: The Sparse Case”. In: Random Structures & Algorithms 66.1 (2025)

I thank author for their answer. Anyway, I still believe that the paper only marginally fits this venue, and that presentation can be largely improved.

As for the technical difference, I see that your proof approach allows to define winner probabilities, and that this is a sufficient justification for adopting this approach and do not adopt previously adopted approaches. Anyway, 1) I believe that some of the results may be simply achieved by adapting previously adopted approaches by observing that the contraction argument still holds with large probability; 2) the paper would benefit whether this comparison with previous used techniques would be highlighted therein.

We would like to thank the reviewer again for helpful human feedbacks, which greatly improves the exposition of the revised version. We summarize our responses below.

1. Adopting approaches from the static setting. We agree with this observation, but the a direct application of proof outline for the static case can't recover our results in full. Tran and Vu (2025) use probability estimates only in the first two rounds: a Berry–Esseen approximation for the first, and a Chernoff bound with a union bound over vertex sets for the second. They then shrink the smaller camp by a deterministic contraction based on the concentration argument ∥A−p11⊤∥≤CpN\|A-p\mathbf 1\mathbf 1^\top\|\le C\sqrt{pN} and a minimum-degree bound. We note that, when p=blog⁡(N)/Np = b\log(N)/N with 0<b<1/(ln⁡4−1)0 <b < 1/(\ln 4 - 1), the constant CC is not 22 as the suggested by the edge of the semicircle law. This is due to the emergence of large degree vertices in the graph, and the precise value of CC depends on the largest degree.

That is to say, even though the contraction still holds with high probability in our model, due to the cost of CC above, applying their argument only gives an upper bound on the number of rounds to unanimity O(log⁡N/log⁡log⁡N)O(\log N/\log\log N), once Δ0≳1/p≍N/log⁡N\Delta_0\gtrsim 1/p\asymp N/\log N.

Therefore, only a small part of our results will be recovered if one follows their strategy directly, while and none of them in full. We outlined differences below.

  • Theorems 3.1 and 3.2 (unanimity within one or two rounds, if and only if r<r∗r<r_* or K>K2ER(b)K>K_2^{\mathrm{ER}}(b)). The contraction bound holds up to an unspecified constant and reduces the smaller camp by a factor of order pNpN per round, so it certifies that the smaller camp disappears only after order log⁡N/log⁡log⁡N\log N/\log\log N rounds, and it gives no lower bounds. Therefore, it yields neither the round counts nor the necessity arguments. These require the exact large-deviation exponent Jb(r)J_b(r), a union bound, and a read-2 Chernoff converse.

  • Theorem 3.3 (amplification whenever Δ0p→∞\Delta_0\sqrt p\to\infty, with two-sided bounds on the consensus time). The static argument starts only at Δ0≳1/p\Delta_0\gtrsim 1/p, which is within a bounded number of rounds of the two-round scale N/log⁡NN/\sqrt{\log N}, and it gives an upper bound on the time only. The range p−1/2≪Δ0≪1/pp^{-1/2}\ll\Delta_0\ll 1/p, a factor of about N/log⁡N\sqrt{N/\log N}, and the lower bound on the time are not covered.

  • Theorem 3.5 (Gaussian winner selection at Δ0≍p−1/2\Delta_0\asymp p^{-1/2}) and Corollary 3.7 (random votes, Δ0≍N\Delta_0\asymp\sqrt N). Both lie below 1/p1/p, so the static argument does not apply. Below 1/p1/p, a Berry–Esseen approximation of each flip probability has error of order (pN)−1/2(pN)^{-1/2}; summed over the NN agents, this exceeds the first-round drift, of order Δ0pN\Delta_0\sqrt{pN}. We replace it by a local limit theorem with error O(1/log⁡N)O(1/\log N) (Lemma A.4), proved by Poisson coupling, uniform smoothing and Fourier inversion.

  • For sparse static graphs, the corresponding winner-selection law at Δ0≍p−1/2\Delta_0\asymp p^{-1/2} remains open (Conjecture 1.11 of Tran and Vu, 2025).

2. Comparison with techniques for static graphs. We thank the reviewer for the suggestion. In the revised version, we have added the "Technical contributions" section, which highlight our novel techniques, and comparisons with the static setting. Also, the proof overview is separated as section 4.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.