{"ID":5935624,"CreatedAt":"2026-07-07T01:22:02.77346169Z","UpdatedAt":"2026-07-07T02:10:06.972658124Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.03564","arxiv_id":"2607.03564","title":"New bounds on randomized metric distortion of top-$k$ voting","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.","short_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 opti...","url_abs":"https://arxiv.org/abs/2607.03564","url_pdf":"https://arxiv.org/pdf/2607.03564v1","authors":"[\"Alec Sun\",\"Daniel Zhu\"]","published":"2026-07-03T19:05:48Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}