Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.17134 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917099472945152 |
|---|---|
| author | Abam, Mohammad Ali Kareshki, Davoud Nilipour, Marzieh Paydar, Mohammad Hossein Seddighin, Masoud |
| author_facet | Abam, Mohammad Ali Kareshki, Davoud Nilipour, Marzieh Paydar, Mohammad Hossein Seddighin, Masoud |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17134 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Bounds On the Distortion of Randomized and Deterministic Distributed Voting Abam, Mohammad Ali Kareshki, Davoud Nilipour, Marzieh Paydar, Mohammad Hossein Seddighin, Masoud Computer Science and Game Theory 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. |
| title | Tight Bounds On the Distortion of Randomized and Deterministic Distributed Voting |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2509.17134 |