💻 computer science

Voter Model Meets Rumour Spreading: an FPRAS for Consensus Probabilities on Voter Models with Agnostic Nodes

This paper introduces a consensus model combining voter dynamics and rumour spreading with "agnostic" nodes, providing theoretical bounds, exact formulas for special cases, and a fully polynomial-time randomized approximation scheme (FPRAS) to efficiently estimate consensus probabilities on general and Erdős-Rényi graphs.

Original authors: Marcelo Matheus Gauy, Anna Abramishvili, Eduardo Colli, Nicolaus Heuer, Tiago Madeira, Frederik Mallmann-Trenn, Vinícius Franco Vasconcelos, David Kohan Marzagão

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Marcelo Matheus Gauy, Anna Abramishvili, Eduardo Colli, Nicolaus Heuer, Tiago Madeira, Frederik Mallmann-Trenn, Vinícius Franco Vasconcelos, David Kohan Marzagão

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a large room full of people, each holding a colored card. Some people hold Red cards, some hold Blue cards, and some are holding Blank cards.

In the classic "Voter Model" game, everyone starts with a color. Every round, people look at their neighbors, pick one at random, and copy their color. Eventually, the whole room usually agrees on one color (either all Red or all Blue).

This paper introduces a twist: The "Agnostic" Nodes.

The New Game: "Ignorant" vs. "Informed"

In this new version, some people start with Blank cards. We call them "agnostic" (or "ignorant") because they have no opinion yet.

The Rule: If a person with a color (Red or Blue) looks at a neighbor with a Blank card, nothing happens. The person keeps their color.
The Change: If a person with a Blank card looks at a neighbor with a color, they instantly adopt that color. They become "informed" (or "gnostic").
One-Way Street: Once you have a color, you can never go back to being blank. You can only switch from Red to Blue or Blue to Red, but you can't become blank again.

Think of it like a rumor spreading in a town. Some people haven't heard the rumor yet (Blank). Once they hear it, they know it (Red or Blue). But once they know, they can't "un-know" it. The twist here is that there are two competing rumors (Red and Blue) spreading at the same time, fighting to convert the blank people.

The Big Question

The researchers wanted to answer two main questions:

Who will win? If we start with a specific mix of Red, Blue, and Blank people, what are the odds that the whole room ends up Red?
How long will it take? How many rounds of looking and copying until everyone agrees?

The Challenges

The paper explains that this is tricky because the "Blank" people act differently than the "Colored" people. In the old games, everything was symmetrical. Here, the Blank people are like empty vessels waiting to be filled, while the Colored people are like paint that can only change color, not disappear.

The Solutions Found

The authors developed several ways to solve this puzzle:

1. The "Magic Formula" (Martingales)
They found a mathematical "magic trick" (called a martingale) that helps predict the winner. It's like a balance scale. If you know the "influence" of every person in the room (how likely they are to be picked by others), you can calculate the probability of Red winning. However, this formula is hard to use for complex, messy networks.

2. The "Fast Forward" Simulation (The FPRAS)
Since the math is hard to do exactly for big groups, they invented a super-fast computer simulation method.

The Trick: Instead of waiting for the whole room to agree on a color (which takes a long time), the computer simulates the game only until everyone loses their Blank card.
Why it works: The "Blank" people get converted very quickly (like a rumor spreading fast). Once everyone has a color, the game becomes the old, well-understood version. The computer then uses a known formula to guess the final winner based on that moment.
The Result: This method is incredibly fast and accurate. It's a "Fully Polynomial-Time Randomized Approximation Scheme" (FPRAS). In plain English: It's a reliable, fast way to get a very good guess of the winner without waiting forever.

3. Special Shortcuts
They found that for certain simple shapes (like a perfect circle where everyone is connected to everyone else), there is a simple math formula to get the exact answer immediately. Also, if there are only a tiny number of Blank people to start with, they can solve it exactly using a different method.

What They Discovered

Speed: The "Blank" people disappear very fast. The time it takes for the whole group to agree is mostly determined by how long it takes for the "Blank" people to get their first color.
Accuracy: Their simulation method is so good that you don't need to run it millions of times to get a good answer. Even with just a few hundred runs, the estimate is very precise.
Graph Size: Interestingly, the bigger the group (the more people in the room), the better the estimate becomes with the same number of runs.

Summary

This paper takes a classic game of "copy your neighbor" and adds a new type of player: the "blank slate." They figured out that while predicting the exact winner is mathematically tough, we can use a clever shortcut: simulate the game just until the blank slates are filled, and then use that snapshot to predict the final outcome. This allows us to quickly and accurately guess who will win the vote in almost any network, from social media graphs to biological systems.

Technical Summary: Voter Model Meets Rumour Spreading

Problem Statement

This paper addresses a variant of the multi-agent consensus problem known as the Voter Model with Agnostic Nodes. In the classical Voter Model, agents (nodes) hold an initial opinion (colour) and update their state by copying a neighbour, eventually reaching a global consensus. However, many real-world scenarios involve agents who initially possess no opinion (agnostic nodes) rather than an undecided state between existing options.

The authors model this by introducing a state where nodes are "agnostic" (e.g., white). An agnostic node becomes "gnostic" (opinionated) only by copying a gnostic neighbour. Crucially, once a node is gnostic, it cannot revert to being agnostic. This creates an asymmetry: agnostic nodes can become gnostic, but gnostic nodes cannot become agnostic. The core challenges are:

Estimating the probability of consensus for a specific colour (e.g., red) given an initial configuration of gnostic and agnostic nodes.
Determining the time bounds for the process to reach consensus.
Addressing the computational complexity of these estimations, particularly noting that exact computation appears difficult due to the dependence of transition probabilities on the history of the process.

Methodology

Theoretical Framework

The authors frame the problem as a combination of two well-studied processes: the Voter Model and Rumour Spreading.

Martingale Approach: The paper derives a general formula for consensus probability (Theorem 2) involving the left eigenvector of the transition matrix and the probabilities of agnostic nodes selecting gnostic neighbours. Under the assumption of a reversible Markov chain, this simplifies to a martingale property (Theorem 3), similar to classical voter model results.
Counterexamples: The authors demonstrate that the independence assumptions made in prior work (specifically [22]) regarding the probability of a node selecting an agnostic neighbour are incorrect. They provide counterexamples showing that reversibility is required for the martingale property to hold and that exact computation of transition probabilities is non-trivial.

Algorithmic Approach (FPRAS)

Recognizing that exact computation is likely hard, the authors propose a Markov Chain Monte Carlo (MCMC) algorithm (Algorithm 1) to estimate consensus probabilities:

Simulation: Simulate the process only until all agnostic nodes become gnostic (disappear).
Estimation: Once all nodes are gnostic, the system reduces to a classical Voter Model. The authors apply known results (Proposition 1) to calculate the winning probability for the specific configuration reached.
Averaging: Repeat the simulation multiple times and average the results to obtain an unbiased estimator.

The efficiency of this approach relies on the fact that the time for agnostic nodes to disappear (rumour spreading time) is significantly shorter than the time to reach full consensus.

Complexity Analysis

Time Bounds: Using results from rumour spreading literature, the authors prove that the expected time for agnostic nodes to disappear is $O(n^2 \log n)$ for general graphs and $O(n \log n)$ for Erdős-Rényi random graphs.
FPRAS: The paper proves that Algorithm 1 constitutes a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS). It achieves a multiplicative error of $(1 \pm \epsilon)$ with high probability in polynomial time, provided the transition probabilities are not exponentially small.
Special Cases:
- For complete graphs, a closed-form solution is derived where the consensus probability equals the initial proportion of red nodes among gnostic nodes.
- If the number of initial agnostic nodes is logarithmic ( $O(\log n)$ ), the exact consensus probability can be computed in polynomial time using a system of linear equations (Theorem 9).

Key Contributions

General Consensus Formula: A method to compute consensus probabilities for any voter model with agnostic states, yielding a martingale for reversible chains (Theorems 2 and 3).
Correction of Prior Work: Identification and correction of an error in [22] regarding the independence of transition probabilities, demonstrating that exact deterministic computation is likely infeasible and necessitating randomized approximation.
FPRAS for Consensus: The presentation of an efficient MCMC algorithm that provides a fully polynomial-time randomized approximation scheme for estimating consensus probabilities on general graphs.
Time Bounds: Proof that the presence of agnostic nodes does not fundamentally alter the complexity bounds for consensus time, as agnostic nodes disappear faster than consensus is achieved (Lemma 1 and Corollaries 1 & 2).
Polynomial Exact Algorithm: A polynomial-time algorithm for computing exact consensus probabilities when the initial number of agnostic nodes is at most logarithmic in the graph size.
Experimental Validation: Empirical results showing that the proposed MCMC approach yields low standard errors with relatively few runs (typically < 200) and that error decreases as graph size increases.

Results

Theoretical: The paper establishes that for general graphs, the consensus probability can be approximated within a multiplicative error $\epsilon$ in time polynomial in the graph size $n$ and $1/\epsilon$ .
Experimental: Experiments on cliques, cycles, and a subgraph of the Pokec social network confirm that stopping the simulation once all nodes are gnostic (rather than waiting for full consensus) significantly reduces the standard error of the estimate. The results suggest that larger graphs require fewer runs to achieve a given standard error.
Complexity: The computational complexity for a single run is $O(n^2 \log n)$ for general graphs and $O(n \log n)$ for random graphs. The total complexity for the FPRAS is polynomial.

Significance

The paper claims significance by bridging the gap between the classical Voter Model and Rumour Spreading processes to address a realistic scenario where agents start without opinions. By proving that exact computation is likely hard and providing an efficient FPRAS, the authors offer a practical tool for estimating consensus outcomes in multi-agent systems, biological mutation fixation, and information diffusion on networks. The work also corrects a subtle but significant error in previous literature regarding the independence of transition probabilities in similar models. The ability to efficiently estimate these probabilities, even with the added complexity of agnostic nodes, facilitates better understanding and prediction of consensus dynamics in complex networks.