Randomized voting rule nearly matches best distortion limit
Stable Voting Rules on the Edge of Optimal Metric Distortion
Computer Science and Game Theory
Summary
Choosing the best candidate in voting can be tricky when preferences have hidden distances, like how far voters really are from options. The authors found a new way to pick a winner randomly that is very close to the smallest possible error in reflecting voters' true interests. Their approach builds on a concept called stable k-lotteries and does not need to mix different voting rules, simplifying the process. They also discovered precise limits for stable lotteries when selecting multiple candidates.
voting rulemetric distortionrandomized votingstable k-lotteriescommittee selectionzero-sum gameaggregate preferencescandidate selectionapproximationdistortion bounds
Authors
Ziyi Cai, Moses Charikar, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang, Qilin Ye
Abstract
We prove the existence of a randomized voting rule with metric distortion at most $2.13713$, within $0.025$ of the lower bound of $2.11264$. Our rule comes from a generalization of stable $k$-lotteries developed in the context of committee selection. In contrast to prior work, our rule samples from a single distribution derived from a zero-sum game, without mixing between voting rules. Our result also gives sharp distortion bounds for stable $k$-lotteries, and in particular shows that stable $2$-lotteries have distortion $7/3$, despite only relying on aggregate preferences over triples of candidates.