New bounds on randomized metric distortion of top-$k$ voting
2026-07-03 • Computer Science and Game Theory
Computer Science and Game Theory
AI summaryⓘ
The authors study how well randomized voting methods pick candidates close to voters' preferences when voters only share their top choice or top k choices. They find a simple way to choose candidates by giving them a chance proportional to their vote share raised to a specific power, which achieves the best possible worst-case accuracy for top-choice voting. They also identify a unique best method that depends on the detailed distribution of votes, improving accuracy for each specific scenario. Lastly, they extend their results to cases where voters share their top k choices and provide a formula to evaluate accuracy there, improving on previous bounds.
randomized social choicemetric distortionfirst-choice votingtop-k votingvote shareworst-case distortioninstance-specific distortionvote vectorcyclic profileapproximation bounds
Authors
Alec Sun, Daniel Zhu
Abstract
We prove new upper and lower bounds on metric distortion for randomized social choice mechanisms. Under first-choice voting where each voter reports only their most preferred candidate, we show that selecting a candidate with probability proportional to the $\frac{n}{n-1}$-th power of their vote share achieves the optimal worst-case distortion of $3 - \frac{2}{n}$. This is a simpler single-rule alternative to prior work. We also study instance-specific metric distortion of first-choice mechanisms in terms of the vote vector $ν$. We show that there is a uniquely optimal rule achieving distortion $1 + \frac{2}{\sum_i \frac{ν_i}{1 - ν_i}}$. Finally, we extend our results to top-$k$ voting where each voter reports their $k$ nearest candidates. We derive a formula for the worst-case distortion for any $k\ge 2$. For the cyclic profile family this improves the previously best known $3 - \frac{2}{\lfloor \frac{n}{k} \rfloor}$ lower bound.