New Randomized Voting Rules Beat Distortion Barrier While Preserving Privacy
Researchers achieve distortion below 3 in metric voting with differential privacy guarantees.
The metric distortion framework studies how well ordinal voting rules approximate the optimal candidate when voters and candidates lie in an unknown metric space. For decades, deterministic rules were known to have worst-case distortion at least 3. Recent randomized rules broke that barrier, but questions remained about their stability and privacy under small changes to voter preferences. This paper, from Sakaue, Fujii, Kumabe, and Yoshida, tackles both issues head-on.
They present a randomized voting rule that achieves distortion strictly below 3 (specifically 3−ε) while maintaining a worst-case sensitivity of O((log m+1)/n) — meaning the distribution of winners changes only slightly when one voter is removed. They also construct a differentially private variant that releases a single sampled winner with distortion ≤3−ε and satisfies (O((log m+log(1/δ)+1)/n), δ)-differential privacy. Both variants rely on a clever use of Gibbs distributions over small candidate lists, where a single temperature parameter governs the trade-off between distortion, sensitivity, and privacy. The analysis builds on a biased-metric viewpoint and proves a novel stability property for the biased-metric ratio.
- Deterministic voting rules have worst-case distortion at least 3; this paper achieves distortion ≤3−ε with a randomized rule.
- The rule's sensitivity under one-voter deletion is bounded by O((log m+1)/n), ensuring stable outcomes.
- A differentially private variant releases a single winner with distortion ≤3−ε and privacy loss O((log m+log(1/δ)+1)/n).
Why It Matters
Combines optimal social choice theory with privacy, enabling practical voting systems that are both fair and private.