Improving Randomized Metric Distortion to 2.1441
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
- Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
- Optimizing Social Utility in Sequential Experiments
- In-Context Credit Assignment via the Core
- Temporal Liquidity Crossing for Blockchains: An EIP-1559 Extension for Admission Below the Base Fee
- Optimal Regret for Online Market Making with Limit Order Book
- Breaking 1/epsilon Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes