Search papers, labs, and topics across Lattice.
This paper analyzes the discrete incremental voting (DIV) process on general graphs, establishing new bounds for convergence time based on graph properties such as conductance and degree ratios. The authors derive an expected convergence time of \(O\left(\frac{n(K\log(Kn)+\gamma(G)n)}{\Phi(G)^2}\right)\), which is shown to be optimal for a broad class of bounded expansion graphs. Additionally, they demonstrate that for regular graphs with specific eigenvalue conditions, DIV converges to the initial average opinion with high probability.
The expected convergence time of discrete incremental voting is tightly bound by graph properties, revealing critical insights into opinion dynamics in networks.
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).
