[Paper] Discrete Incremental Voting: New Bounds for General Graphs and Expanders

Source: arXiv - 2606.06381v1

Overview

We analyze the discrete incremental voting process (DIV) introduced by Cooper, Radzik, and Shiraga [OPODIS ‘23]. In this process, we consider a set $V$ of $n$ nodes connected in an undirected graph $G = (V, E)$ where each node has an integer opinion. In one step a randomly selected node interacts with its randomly selected neighbor and changes its opinion by $1$ in the direction of the neighbour’s opinion. The process converges to a unique opinion that, in expectation, is the degree-weighted average of the initial opinions. We show that if the graph has conductance $Φ(G)$, the ratio of the average to smallest degree is $γ(G)$, and the maximal difference between initial opinions is $K$, then the expected convergence time is ${O}\left({n\left(K\log (Kn)+γ(G) n \right)}/{Φ(G)^2}\right)$. This bound is essentially optimal for a large class of graphs of bounded expansion. We also show that for regular graphs, if the second largest eigenvalue is $o(1/\log^2 n)$ and $K$ is $o\left({n}/{\log^2 n}\right)$, then w.h.p.\ DIV converges to the initial average opinion (rounded up or down).

Key Contributions

This paper presents research in the following areas:

• cs.DC

Methodology

Please refer to the full paper for detailed methodology.

Practical Implications

This research contributes to the advancement of cs.DC.

Authors

• Petra Berenbrink
• Colin Cooper
• Thorsten Götte
• Lukas Hintze
• Tomasz Radzik

Paper Information

• arXiv ID: 2606.06381v1
• Categories: cs.DC
• Published: June 4, 2026
• PDF: Download PDF