2025/09/21 by Mohammad Ali Abam, Davoud Kareshki, Abam, Mohammad Ali +7
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Voting Systems #Internet Traffic Analysis and Secure E-voting
paper · pdf · doi:10.48550/arxiv.2509.17134
openalex publication_date 2025/09/21 · openalex created_date 2025/10/16 · openalex updated_date 2026/07/28
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 \citepanshelevich2022distortion: \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+√(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.