Discrete Incremental Voting: New Bounds for General Graphs and Expanders
Provides tight theoretical bounds for a consensus process on general graphs, addressing a gap for graphs with varying degrees and conductance.
The paper analyzes the discrete incremental voting process on general graphs and expanders, proving an expected convergence time bound of O(n(K log(Kn) + γ(G)n) / Φ(G)^2) that is essentially optimal for bounded-expansion graphs, and shows that for regular expanders with small second eigenvalue, the process w.h.p. converges to the initial average opinion.
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).