pith. sign in

arxiv: 2606.06381 · v1 · pith:R7PDW6GLnew · submitted 2026-06-04 · 💻 cs.DC

Discrete Incremental Voting: New Bounds for General Graphs and Expanders

Petra Berenbrink , Colin Cooper , Thorsten G\"otte , Lukas Hintze , Tomasz Radzik This is my paper

Pith reviewed 2026-06-27 23:38 UTC · model grok-4.3

classification 💻 cs.DC
keywords discrete incremental votingconductanceconvergence timeexpander graphsopinion dynamicsMarkov chain mixingdistributed consensus
0
0 comments X

The pith

The expected convergence time of discrete incremental voting is O(n(K log(Kn) + γ(G) n)/Φ(G)²) on graphs with conductance Φ, degree ratio γ, and initial opinion spread K.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the discrete incremental voting process on an undirected graph where each node holds an integer opinion. In each step a random node selects a random neighbor and shifts its own opinion by exactly 1 toward the neighbor. The authors prove an upper bound on the expected steps until all opinions coincide, expressed in terms of the graph conductance, the spread of starting opinions, and the ratio of average to minimum degree. The same analysis yields a high-probability guarantee that the final opinion equals the degree-weighted average on sufficiently well-connected regular graphs. Readers care because the bound supplies concrete running-time guarantees for a simple distributed agreement rule that works on arbitrary networks.

Core claim

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(n(K log(Kn) + γ(G) n)/Φ(G)²). This bound is essentially optimal for a large class of graphs of bounded expansion. For regular graphs, if the second largest eigenvalue is o(1/log² n) and K is o(n/log² n), then with high probability DIV converges to the initial average opinion rounded up or down.

What carries the argument

Conductance Φ(G) of the interaction graph, used to bound the mixing time of the Markov chain on opinion vectors under the random-neighbor ±1 update rule.

If this is right

  • On constant-conductance graphs the time is O(n K log(Kn) + n² γ) in expectation.
  • The bound is tight up to constants for the large class of bounded-expansion graphs.
  • On regular graphs satisfying the eigenvalue condition the final opinion matches the average with high probability whenever K is o(n/log² n).
  • The process always reaches a consensus whose expectation equals the degree-weighted average of the initial opinions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same conductance argument may give running-time guarantees for other incremental consensus rules that use small integer updates.
  • Real-world networks whose conductance can be measured from data would inherit explicit convergence estimates from the bound.
  • The eigenvalue condition highlights that rapid mixing, rather than regularity alone, is what forces the outcome to the average.
  • Relaxing the exact ±1 update to larger or probabilistic steps would require a separate mixing analysis.

Load-bearing premise

The process selects nodes and neighbors uniformly at random and changes opinions by exactly ±1, so that standard conductance-based mixing arguments apply without hidden dependencies on the current opinion values.

What would settle it

A concrete family of graphs together with initial opinions for which the measured convergence time grows asymptotically faster than the stated O expression in n, K, γ, and 1/Φ².

read the original abstract

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 $\Phi(G)$, the ratio of the average to smallest degree is $\gamma(G)$, and the maximal difference between initial opinions is $K$, then the expected convergence time is ${O}\left({n\left(K\log (Kn)+\gamma(G) n \right)}/{\Phi(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).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper analyzes the discrete incremental voting (DIV) process on an undirected graph G with n nodes, where each node holds an integer opinion. In each step a uniformly random node selects a uniform random neighbor and increments or decrements its opinion by 1 toward the neighbor's value. The process is shown to converge in expectation to the degree-weighted average of the initial opinions. The main result states that if Φ(G) denotes conductance, γ(G) the ratio of average to minimum degree, and K the maximum initial opinion difference, then the expected convergence time is O(n(K log(Kn) + γ(G)n)/Φ(G)^2). A secondary result asserts that on regular graphs whose second-largest eigenvalue is o(1/log² n) and with K = o(n/log² n), the process converges with high probability to the rounded initial average. The bound is claimed to be essentially optimal for graphs of bounded expansion.

Significance. If the stated bound holds, the work supplies a conductance-based mixing-time analysis for a simple opinion-update rule whose transitions are independent of current opinion values. This yields a clean, parameter-light upper bound that applies to arbitrary graphs and recovers known expander behavior as a special case. The optimality statement for bounded-expansion graphs and the high-probability result under a spectral-gap condition on regular graphs are concrete contributions that can be checked against existing lower-bound constructions in the literature. The absence of opinion-dependent transition probabilities removes a common source of circularity in such analyses.

major comments (2)
  1. [Abstract, §1] Abstract and §1: The optimality claim for 'a large class of graphs of bounded expansion' is stated without an accompanying lower-bound construction or explicit definition of the class inside the manuscript. Because this claim is used to position the upper bound as tight, the matching lower-bound argument (including the specific family of graphs and the Ω(·) expression) must be supplied in the main body.
  2. [Theorem 1] Theorem 1 (or equivalent statement of the main bound): The term γ(G)n inside the numerator is presented as arising from degree variation in the stationary distribution, yet the manuscript does not exhibit the precise place where the minimum-degree normalization enters the potential or coupling argument. A short derivation showing how the factor appears from the conductance definition would confirm that no additional hidden constants are introduced.
minor comments (2)
  1. Notation: the symbol γ(G) is introduced in the abstract but its precise definition (average degree divided by minimum degree) should be restated at first use in the technical sections to avoid ambiguity with other common degree-ratio notations.
  2. The citation to the OPODIS '23 paper is used for the process definition; a one-sentence recap of the exact interaction rule (uniform node then uniform neighbor, ±1 update) would make the manuscript self-contained for readers who have not consulted the reference.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the recommendation for minor revision. We address the two major comments below and will incorporate the requested clarifications and additions into the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract, §1] The optimality claim for 'a large class of graphs of bounded expansion' is stated without an accompanying lower-bound construction or explicit definition of the class inside the manuscript. Because this claim is used to position the upper bound as tight, the matching lower-bound argument (including the specific family of graphs and the Ω(·) expression) must be supplied in the main body.

    Authors: We agree that the optimality statement requires explicit support. In the revision we will add a new subsection (or short appendix) that (i) defines the class as the family of constant-degree graphs with constant conductance (i.e., bounded-expansion regular graphs), and (ii) supplies a matching Ω(n(K + γ n)/Φ²) lower-bound construction via a standard coupon-collector argument on a disjoint union of small cliques connected by a sparse cut of conductance Φ. This establishes tightness up to constant factors for that class. revision: yes

  2. Referee: [Theorem 1] The term γ(G)n inside the numerator is presented as arising from degree variation in the stationary distribution, yet the manuscript does not exhibit the precise place where the minimum-degree normalization enters the potential or coupling argument. A short derivation showing how the factor appears from the conductance definition would confirm that no additional hidden constants are introduced.

    Authors: We will insert a short paragraph immediately after the statement of Theorem 1 that derives the γ factor. Briefly: the conductance definition uses volume (sum of degrees), the stationary distribution π_v = deg(v)/(2m) therefore differs from the uniform distribution by a factor of at most γ = d_avg/d_min, and this ratio appears when we bound the one-step drift of the quadratic potential Φ(x) = Σ_v π_v (x_v - μ)^2 by replacing the uniform-neighbor selection probability with its degree-weighted counterpart; the extra γ multiplies the conductance term exactly once and produces the stated numerator. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The convergence-time bound is stated directly in terms of externally defined graph parameters (conductance Φ(G), degree ratio γ(G)) and initial opinion spread K; these quantities are not fitted inside the paper. The process itself is referenced to a prior OPODIS '23 paper with author overlap, but that citation only supplies the interaction rule and does not carry the mixing or potential-function arguments used for the new O(n(K log(Kn) + γ n)/Φ²) bound. No self-definitional equations, fitted-input predictions, or load-bearing uniqueness theorems appear. The derivation therefore remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard Markov-chain analysis of a random walk on the graph together with the assumption that the process definition from the 2023 reference carries over unchanged; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption The interaction rule is exactly the one defined in Cooper, Radzik, Shiraga (OPODIS '23): a randomly selected node interacts with a randomly selected neighbor and changes opinion by exactly 1 toward the neighbor.
    Invoked in the first paragraph of the abstract as the process under study.
  • standard math Standard conductance and eigenvalue definitions from spectral graph theory apply without modification.
    Used to state the bound and the regular-graph condition.

pith-pipeline@v0.9.1-grok · 5776 in / 1426 out tokens · 23066 ms · 2026-06-27T23:38:32.367253+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 1 canonical work pages

  1. [1]

    Consensus dynamics: An overview.SIGACT News, 51(1):58–104, 2020

    Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview.SIGACT News, 51(1):58–104, 2020

    2020

  2. [2]

    Simple dynamics for plurality consensus.Distributed Comput., 30(4):293–306, 2017

    Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus.Distributed Comput., 30(4):293–306, 2017

    2017

  3. [3]

    Ignore or comply?: On breaking symmetry in consensus

    Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or comply?: On breaking symmetry in consensus. InProceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 335–344, 2017

    2017

  4. [4]

    Distributed averaging in opinion dynamics

    Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik, and Nicolas Rivera. Distributed averaging in opinion dynamics. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 211–221, 2023

    2023

  5. [5]

    Bounds on the voter model in dynamic networks

    Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the voter model in dynamic networks. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 146:1–146:15, 2016

    2016

  6. [6]

    Oxford University Press, Oxford, UK, 2013

    Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, Oxford, UK, 2013

    2013

  7. [7]

    Fan R. K. Chung.Spectral Graph Theory, volume 92 ofCBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997

    1997

  8. [8]

    Coalescing random walks and voting on connected graphs.SIAM J

    Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs.SIAM J. Discret. Math., 27(4):1748–1758, 2013

    2013

  9. [9]

    The power of two choices in distributed voting

    Colin Cooper, Robert Elsässer, and Tomasz Radzik. The power of two choices in distributed voting. InAutomata, Languages, and Programming (ICALP), pages 435–446, 2014

    2014

  10. [10]

    Fast consensus for voting on general expander graphs

    Colin Cooper, Robert Elsässer, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast consensus for voting on general expander graphs. In Distributed Computing - 29th International Symposium (DISC), pages 248–262, 2015

    2015

  11. [11]

    Asynchronous 3-majority dynamics with many opinions

    Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Asynchronous 3-majority dynamics with many opinions. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4095–4131, 2025

    2025

  12. [12]

    Fast plurality consensus in regular expanders

    Colin Cooper, Tomasz Radzik, Nicolas Rivera, and Takeharu Shiraga. Fast plurality consensus in regular expanders. In31st International Symposium on Distributed Computing (DISC), 2017

    2017

  13. [13]

    Discrete Incremental Voting

    Colin Cooper, Tomasz Radzik, and Takeharu Shiraga. Discrete Incremental Voting. In27th International Conference on Principles of Distributed Systems (OPODIS 2023), pages 10:1–10:22, 2024

    2023

  14. [14]

    Discrete incremental voting on expanders.Discret

    Colin Cooper, Tomasz Radzik, and Takeharu Shiraga. Discrete incremental voting on expanders.Discret. Math., 349(1):114708, 2026

    2026

  15. [16]

    The linear voting model

    Colin Cooper and Nicolas Rivera. The linear voting model. In43rd International Colloquium on Automata, Languages, and Programming (ICALP), pages 144:1–144:12, 2016

    2016

  16. [17]

    Mixing beliefs among interacting agents.Advances in Complex Systems, 3(1–4):87–98, 2000

    Guillaume Deffuant, David Neau, Frédéric Amblard, and Gérard Weisbuch. Mixing beliefs among interacting agents.Advances in Complex Systems, 3(1–4):87–98, 2000

    2000

  17. [18]

    Morris H. DeGroot. Reaching a consensus.Journal of the American Statistical Association, 69(345):118–121, 1974

    1974

  18. [19]

    Stabilizing consensus with the power of two choices

    Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. InProceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures, page 149–158, 2011

    2011

  19. [20]

    Cambridge University Press, Cambridge, 5th edition, 2019

    Richard Durrett.Probability: Theory and Examples, volume 49 ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 5th edition, 2019

    2019

  20. [21]

    Nearly-tight analysis for 2-choice and 3-majority consensus dynamics

    Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. InProceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 305–313, 2018

    2018

  21. [22]

    Distributed probabilistic polling and applications to proportionate agreement.Inf

    Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement.Inf. Comput., 171(2):248–268, 2001

    2001

  22. [23]

    Opinion dynamics and bounded confidence models, analysis, and simulation.Journal of Artificial Societies and Social Simulation, 5(3), 2002

    Rainer Hegselmann and Ulrich Krause. Opinion dynamics and bounded confidence models, analysis, and simulation.Journal of Artificial Societies and Social Simulation, 5(3), 2002

    2002

  23. [24]

    Expander graphs and their applications.Bulletin of the American Mathematical Society, 43(4):439– 561, 2006

    Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications.Bulletin of the American Mathematical Society, 43(4):439– 561, 2006

    2006

  24. [25]

    Tail bounds for sums of geometric and exponential variables.Statistics & Probability Letters, 135:1–6, 2018

    Svante Janson. Tail bounds for sums of geometric and exponential variables.Statistics & Probability Letters, 135:1–6, 2018. URL: https://www. sciencedirect.com/science/article/pii/S0167715217303711,doi:10.1016/j.spl.2017.11.017

    work page doi:10.1016/j.spl.2017.11.017 2018

  25. [26]

    Approximating the permanent.SIAM Journal on Computing, 18(6):1149–1178, 1989

    Mark Jerrum and Alistair Sinclair. Approximating the permanent.SIAM Journal on Computing, 18(6):1149–1178, 1989

    1989

  26. [27]

    Levin, Yuval Peres, and Elizabeth L

    David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.Markov Chains and Mixing Times. American Mathematical Society, 2009

    2009

  27. [28]

    Conductance and convergence of markov chains-a combinatorial treatment of expanders

    Milena Mihail. Conductance and convergence of markov chains-a combinatorial treatment of expanders. In30th Annual Symposium on Foundations of Computer Science (FOCS), pages 526–531, 1989

    1989

  28. [29]

    3-majority and 2-choices with many opinions

    Nobutaka Shimizu and Takeharu Shiraga. 3-majority and 2-choices with many opinions. InProceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 207–217, 2025

    2025