{"ID":3083597,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-07T05:00:38.846751169Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.06381","arxiv_id":"2606.06381","title":"Discrete Incremental Voting: New Bounds for General Graphs and Expanders","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 $Φ(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).","short_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 sele...","url_abs":"https://arxiv.org/abs/2606.06381","url_pdf":"https://arxiv.org/pdf/2606.06381v1","authors":"[\"Petra Berenbrink\",\"Colin Cooper\",\"Thorsten Götte\",\"Lukas Hintze\",\"Tomasz Radzik\"]","published":"2026-06-04T16:47:45Z","proceeding":"cs.DC","tasks":"[\"cs.DC\"]","methods":"[]","has_code":false}