{"ID":2868188,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.17134","arxiv_id":"2509.17134","title":"Tight Bounds On the Distortion of Randomized and Deterministic Distributed Voting","abstract":"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 \\citep{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.","short_abstract":"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 decis...","url_abs":"https://arxiv.org/abs/2509.17134","url_pdf":"https://arxiv.org/pdf/2509.17134v2","authors":"[\"Mohammad Ali Abam\",\"Davoud Kareshki\",\"Marzieh Nilipour\",\"Mohammad Hossein Paydar\",\"Masoud Seddighin\"]","published":"2025-09-21T15:51:05Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}