Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting
Marzieh Nilipour, Mohammad Abam, Davoud Kareshki, Masoud Seddighin, MohammadHossein Paydar
We investigate metric distortion in distributed voting, where voters are divided into groups that each select a local representative, and a final winner is chosen from these representatives. This model captures real-world systems such as the U.S. presidential elections, where state-level decisions determine the national outcome. Our analysis focuses on four fundamental cost-minimization objectives introduced by Anshelevich et al.~\cite{anshelevich2022distortion}: the average of averages ($\avgavg$), average of maxima ($\avgmax$), maximum of averages ($\maxavg$), and maximum of maxima ($\maxmax$). We provide improved bounds for both deterministic and randomized rules which provides a near-complete picture of metric distortion in distributed voting. For deterministic mechanisms, we tighten the distortion gaps: we establish a tight lower bound of 5 for $\maxavg$ (improving the previous $2+\sqrt{5}$), reduce the upper bound for $\avgmax$ from 11 to 9, and show a tight upper bound of 3 for $\maxmax$ (improving the previous bound of 5). For randomized rules, we study two classes: (i) $\randdet$, where only the second stage is randomized, and (ii) $\randrand$, where both stages may be randomized. For $\randdet$, we establish tight bounds for all objectives: $5-2/k$ for $\avgavg$, $3$ for $\avgmax$ and $\maxmax$, $5$ for $\maxavg$. For $\randrand$, we show tight bounds of $3$ for $\maxavg$ and $\maxmax$, along with nearly tight bounds for $\avgavg$ and $\avgmax$ in the ranges $[3-2/n, 3-2/(kn^*)]$ and $[3-2/n, 3]$, respectively, where $n$ is the number of voters, $n^*$ is the size of the largest group, and k is the number of groups.