Robust Lottery Compression for Metric Voting: A Transfer Principle for Bounded Randomness

Abstract

We study metric distortion in randomized social choice under bounded randomness: on every preference profile, the voting rule must deterministically identify a multiset of $K$ candidates and then select a uniformly random entry. Previous work showed that this restricted model can beat the optimal deterministic distortion of $3$. We show that it can in fact approach the current best unrestricted upper benchmark of $5/2$. For every integer $K\ge 802$, there exists a bounded-randomness rule with distortion at most $\frac{5}{2}+3{\left(\frac{\pi }{8K}\right)}^{1/3}+2\sqrt{\frac{\pi }{8K}}$. Consequently, $O({\epsilon }^{-3})$ entries suffice for distortion $5/2+\epsilon$, independently of the numbers of voters and candidates. We also show that $164$ entries already achieve distortion strictly below $3$, giving $2\le N^{\star }\le 164$ for the minimum list size needed to break the deterministic barrier. Our main technical contribution is a dimension-free compression theorem: if a lottery has distortion at most $\rho$ and every candidate in its support has deterministic distortion at most $H$, then it admits a uniform $K$-entry approximation with distortion at most $\rho +(H+1)\sqrt{\pi /(8K)}$. Thus, lotteries whose possible outcomes are already well behaved incur only $O(K^{-1/2})$ compression loss. Mixed Integrated Veto does not satisfy this support condition, so we first remove early-eliminated outcomes, trading $O({\tau }^2)$ distortion loss for an $O(1/\tau )$ bound on the deterministic distortion of every supported candidate. Balancing this repair cost against compression yields the $O(K^{-1/3})$ convergence rate.