Improving Randomized Metric Distortion to 2.1441

arXiv:2608.29308 · cs.GT, cs.AI · Submitted 2026-08-29 · Read on arXiv

cs.GT, cs.AI

Submitted: 2026-08-29

Updated: 2026-09-06

Code: https://github.com/nisarg89/metric-distortion

License: http://creativecommons.org/licenses/by/4.0/

The gist: In metric social choice, voters rank candidates by their distances in an unknown metric space.

Terminology

Abstract

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 through a potential argument. All the proofs were obtained using GPT-5.6-Sol with significant guidance from the author, who verified them and simplified the exposition.

Sources

Related papers