SOURCE-LINKED INTELLIGENCE

Improving Randomized Metric Distortion to 2.1441

arXiv · AI, language, vision and robotics · article · Aug 29, 2026 · UTC

In metric social choice, voters rank candidates by their distances in an unknown metric space. A voting rule uses these rankings to select a candidate or a lottery over candidates, aiming to minimize the average distance to voters. Distortion measures the worst-case approximation ratio. While the best distortion of deterministic rules is $3$, prior work pins down the best distortion of randomized rules to $[2.1126,2.5]$. We improve the upper bound to $2.1441$, closing over $90\%$ of this gap. The proof introduces random-size stable lotteries, proves their existence, and derives the new bound t

Read original source ↗ Open in workspace

recordType

paper

region

Global