Abstract:We study the design of voting rules in the metric distortion framework. It is known that any deterministic rule suffers distortion of at least $3$, and that randomized rules can achieve distortion strictly less than $3$, often at the cost of reduced transparency and interpretability. In this work, we explore the trade-off between these paradigms by asking whether it is possible to break the distortion barrier of $3$ using only "bounded" randomness. We answer in the affirmative by presenting a voting rule that (1) achieves distortion of at most $3 - \varepsilon$ for some absolute constant $\varepsilon > 0$, and (2) selects a winner uniformly at random from a deterministically identified list of constant size. Our analysis builds on new structural results for the distortion and approximation of Maximal Lotteries and Stable Lotteries.
From: Ziyi Cai [view email]
[v1]
Mon, 9 Feb 2026 16:33:27 UTC (37 KB)
[v2]
Sun, 2 Aug 2026 13:58:46 UTC (38 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。