| paper | Voter Model Meets Rumour Spreading: A Study of Consensus Protocols on Graphs with Agnostic Nodes |
| authors | — |
| venue | AAMAS 2025 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 3.3
statement extracted from the paper’s text layer
Given rational masses \(r,b,a\ge 0\) with \(r+b+a=1\), define the asynchronous complete-mixing pull process on every finite lift satisfying \(Nr,Nb,Na\in\mathbb{Z}\). Compute the common probability \(p_R(\mu)\) that the lift reaches red consensus; when \(r+b>0\), \(p_R(\mu)=\frac{r}{r+b}\), while \(r+b=0\) yields no consensus.
A one-role anonymous population with state masses \(\mu=(r,b,a)\), complete-mixing asynchronous pull updates, and finite lifts supplying the canonical stochastic semantics; the objective is exact red-consensus probability.
The finite-lift semantics is not an intrinsic infinite-population stochastic process: the deterministic mean-field dynamics lose the red-versus-blue absorption event and its associated probability.
fatal: False
The mirror covers Corollary 3.3 and its complete-mixing consensus probability, but not Proposition 4.3's quenched random-graph clearance bound, the general MCMC setting, or Theorem 3.1 as a general computational result.
Yes, but the strongest mirror is deliberately narrow: large anonymous populations using a common or small-number-of-roles communication protocol. I would not claim a mirror for arbitrary named-node graphs.
The natural regime is a population of validators, devices, or users using random peer sampling. A permanent type specifies an agent’s communication role and sampling law; its current state is \(R\), \(B\), or \(A\) (agnostic). Type \(i\) has mass \(\mu_i\), and \(K_{ij}\) is the probability that an \(i\)-agent samples a \(j\)-agent. Thus \(N\) may be enormous while the number of communication types \(\tau\) remains small. The evolving state is the mass vector \((r_i,b_i,a_i)\); the paper has no intervention, so there is no artificial control variable to add.
My lead anchor is Corollary 3.3, “Solution for Complete Graph.” It is proved by the authors in the extended version, rather than cited from elsewhere. It states that for the asynchronous pull process on a complete graph,
\[ \Pr(\text{red wins}\mid S_0)=\gamma, \]
where \(\gamma\) is the proportion of red nodes among the initially gnostic nodes.
The corresponding continuous problem is:
\(\mathrm{Complete\text{-}Agnostic\text{-}Consensus}_\infty\). An instance consists of rational masses \(r,b,a\ge 0\) with \(r+b+a=1\), representing red, blue, and agnostic population mass, together with the complete-mixing asynchronous pull protocol. The question is to compute the probability \(p_R\) that the population’s finite high-multiplicity lifts eventually reach red consensus. Formally, for every \(N\) for which \(Nr,Nb,Na\) are integers, run the paper’s process on \(N\) agents and let \(p_R\) be the common value of the resulting consensus probabilities. If \(r+b>0\), the required output is
\[ p_R=\frac{r}{r+b}. \]
If \(r+b=0\), there is no initial gnostic source and consensus is not reached.
This is a genuine population mirror, not merely a change of notation. The instance is the mass vector; individual identities and \(N\) disappear. The objective remains exactly the paper’s objective—the probability of red consensus—and the agnostic asymmetry is preserved. Moreover, every rational high-multiplicity lift has the same answer, so the continuous problem is an exact compression of the discrete family. This is plainly Class A: exact computation takes polynomial time in the encoding length, indeed essentially one rational division.
The mirror should be credible to the authors because the complete graph is not an invented simplification: it is the setting of their own Corollary 3.3. The appropriate interpretation is a large anonymous population with uniform peer sampling, not a small committee whose members happen to be placed on a complete graph.
A second, weaker but broader anchor is Proposition 4.3, “rumour spreading bounds for random graphs.” This is proved in the paper, with the proof deferred to the appendix and adapted from known rumour-spreading arguments. It states that for \(G\sim G(n,p)\), with \(p\gg \log(n)/n\), the expected time \(T_a\) for agnostic vertices to disappear is, with high probability, \(O(\log n)\) in the synchronous model and \(O(n\log n)\) in the asynchronous model.
The continuous problem I would attach to it is:
\(\mathrm{Agnostic\text{-}Clearance}_\infty\). An instance consists of a finite type distribution \(\mu\), an interaction kernel \(K\), initial within-type agnostic fractions \(a_i(0)\), and a rational tolerance \(\varepsilon>0\). The question is to compute the first time at which the agnostic mass
\[ A(t)=\sum_i \mu_i a_i(t) \]
falls below \(\varepsilon\). In the synchronous mean-field model,
\[ a_i(t+1) = a_i(t)\sum_j K_{ij}a_j(t). \]
For the dense random-graph regime corresponding to Proposition 4.3, there is one communication type and \(K=1\), so
\[ a(t+1)=a(t)^2, \qquad a(t)=a(0)^{2^t}. \]
Consequently, for \(0<a(0)<1\),
\[ T_\varepsilon = \max\!\left\{ 0, \left\lceil \log_2 \frac{\log(1/\varepsilon)} {\log(1/a(0))} \right\rceil \right\}. \]
This is again Class A in the anchored one-type regime. If the finite lift starts with one gnostic agent, then \(1-a(0)=1/N\), and taking \(\varepsilon=1/N\) gives \(T_\varepsilon=\Theta(\log N)\), matching the synchronous scale in Proposition 4.3. In asynchronous time, one sweep corresponds to \(N\) individual updates, recovering the extra factor \(N\).
Theorem 3.1 provides a promising extension rather than a separate anchor. Its reversibility condition becomes the natural detailed-balance condition
\[ \mu_iK_{ij}=\mu_jK_{ji} \]
for a finite-type continuum kernel. Thus the paper’s martingale has an immediate population-level analogue. I would not claim that the general reversible-type problem is already tractable, however: the authors themselves note that the martingale may not be efficiently computable in general. The natural follow-up is exact or approximate computation of red-consensus probability for fixed \(\tau\) reversible kernels, with the complete-mixing case as the base case.
This case covers Corollary 3.3 and Proposition 4.3 emphatically. It does not claim to continuize arbitrary nonreversible graphs, the full worst-case statement of Proposition 4.2, or the paper’s general MCMC setting. Those would require either many distinct network types or a graphon-like object, and the high-multiplicity gain could disappear.
The weakest point is unavoidable: an actual infinite population generally never reaches literal all-red or all-blue consensus. My response is to use two standard high-multiplicity interpretations. For the probability problem, define the answer through finite-population lifts; here the answer is exactly invariant across all lifts. For the time problem, replace “the last agnostic individual disappears” by the mass threshold \(A(t)\le\varepsilon\), which is the honest continuous analogue. If a referee insists that a mirror must retain literal global absorption in an infinite population, the second mirror fails. The positive case therefore rests most strongly on Corollary 3.3, where the discrete consensus probability survives continuization without approximation or reinterpretation.
The strongest objection is not that the graph is discrete. A complete graph with anonymous peer-sampling agents is a perfectly sensible high-multiplicity regime. The problem is that the paper’s consensus probability is generated by finite-population noise, whereas the proposed continuum removes precisely that noise.
For Corollary 3.3, the finite-lift definition is therefore not an intrinsic continuous process. In the synchronous mean-field limit, with masses \(r,b,a\), the evolution is
\[ a_{t+1}=a_t^2,\qquad r_{t+1}=(1+a_t)r_t,\qquad b_{t+1}=(1+a_t)b_t. \]
Thus \(a_t\) tends to zero, but once it has disappeared the positive red and blue masses remain mixed forever. There is no red or blue absorption event and hence no random variable whose probability is \(r/(r+b)\). That probability arises from demographic fluctuations in a finite population, eventually amplified on a population-size-dependent time scale.
Defining \(p_R\) by taking the common answer of all finite lifts preserves a number, but it does not produce a stochastic continuum model. It is a wrapper around the already-proved finite formula. A faithful repair would require retaining \(N\), a noise intensity, or a diffusion scaling; alternatively one could add common noise and change the protocol. Either way, the population distribution alone is no longer the complete instance. The finite-lift construction is consequently a thin exact compression, not a worthwhile computational mirror of the consensus process.
Proposition 4.3 has a separate obstruction. In a fixed \(G(n,p)\), a vertex’s relevant type includes its neighbourhood and its position in the graph. With high probability, vertices do not share complete neighbourhood types, so the graph does not possess high multiplicity in the programme’s sense. Collapsing them to one type with \(K=1\) gives an annealed random-peer model, not the paper’s quenched random graph. A graphon or block-type model can retain some aggregate connectivity, but it loses the graph-level fluctuations and tail events controlling the last agnostic vertex.
That last vertex is decisive. The paper’s \(T_a\) is an extreme, finite-particle statistic: the time until a population contains zero agnostic individuals. In the proposed mean-field model, \(A(t)>0\) at every finite time whenever \(A(0)>0\). Replacing zero by \(A(t)\le\varepsilon\) creates a legitimate new observable, but \(\varepsilon\) is arbitrary. Choosing \(\varepsilon=1/N\) to recover the paper’s event simply puts the discarded population size back into the instance. A fixed \(\varepsilon\) instead studies approximate clearance, not Proposition 4.3. This is a genuine continuum degeneration, not a complaint about notation or about the eventual answer.
Theorem 3.1 does not repair either problem. Its quantity
\[ X_t=\sum_v \mu(v)\Pr(R(v)\mid S_t) \]
uses conditional probabilities of eventual finite-population absorption. Writing detailed balance as \(\mu_iK_{ij}=\mu_jK_{ji}\) is formally natural, but it does not make those absorption probabilities functions of a deterministic mass vector. In the continuum limit there is no corresponding absorption event; in a finite-lift formulation, one has merely retained the original finite Markov chain under another notation. Nor is Theorem 3.1 itself a computational result: it is an analytic martingale identity, and the paper explicitly says that its general computation may be inefficient.
The honest escape hatch is the complete-graph finite-lift functional. If that is accepted as a continuous problem, the paper has a valid but very narrow mirror of Corollary 3.3. Under the stronger standard that the society itself must be the continuous stochastic object, both proposed anchors fail: one loses fixation, and the other loses the last-particle clearance event. The remaining mean-field or graphon equations are useful analytic models, but they are not computational mirrors of the paper’s named results.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.