Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting

Mohammad Abam, Davoud Kareshki, Marzieh Nilipour, MohammadHossein Paydar, Masoud Seddighin

Advances in Neural Information Processing Systems 38 (NeurIPS 2025) Main Conference Track

We study metric distortion in distributed voting, where $n$ voters are partitioned into $k$ groups, each selecting a local representative, and a final winner is chosen from these representatives (or from the entire set of candidates). This setting models systems like U.S. presidential elections, where state-level decisions determine the national outcome. We focus on four cost objectives from Anshelevich \et~\cite{anshelevich2022distortion}: $\avgavg$, $\avgmax$, $\maxavg$, and $\maxmax$. We present improved distortion bounds for both deterministic and randomized mechanisms, offering a near-complete characterization of distortion in this model. For deterministic mechanisms, we reduce the upper bound for $\avgmax$ from $11$ to $7$, establish a tight lower bound of $5$ for $\maxavg$ (improving on $2+\sqrt{5}$), and tighten the upper bound for $\maxmax$ from $5$ to $3$. For randomized mechanisms, we consider two settings: (i) only the second stage is randomized, and (ii) both stages may be randomized. In case (i), we prove tight bounds: $5\!-\!2/k$ for $\avgavg$, $3$ for $\avgmax$ and $\maxmax$, and $5$ for $\maxavg$. In case (ii), we show tight bounds of $3$ for $\maxavg$ and $\maxmax$, and nearly tight bounds for $\avgavg$ and $\avgmax$ within $[3\!-\!2/n,\ 3\!-\!2/(kn^*)]$ and $[3\!-\!2/n,\ 3]$, respectively, where $n^*$ denotes the largest group size.