Multiwinner voting rules handle coarse preferences with bounded distortion
The Distortion of Threshold Approval Multiwinner Voting
Computer Science and Game Theory
Summary
The paper looks at how groups pick committees when voters only give rough preferences, like sorting candidates into a few approval categories. The authors study different ways to measure voter happiness with the chosen committee and design voting rules that work well even with limited information. They show these rules can keep the 'distortion' — a measure of how much happiness is lost due to coarse voting — under control. They also prove that their results are close to the best possible under these settings.
What this means in practice
- •For election designers: Choose voting methods that perform well in selecting representative committees when voters provide only limited preference information.
- •For committee organizers: Design nomination and voting processes that reduce welfare loss due to voters categorizing choices coarsely rather than ranking all candidates precisely.
A theory result. No direct application yet.
Authors
Mohamad Latifian, Marzieh Nilipour, Alexandros A. Voudouris
Abstract
We study multiwinner voting with $n$ voters and $m$ candidates, where the goal is to select a committee of size $k$. Voters have unit-sum cardinal utilities but report only coarse information induced by $t$ utility thresholds. In particular, each voter partitions the candidates into approval sets, with the utilities of all candidates in the same set lying between the same pair of consecutive thresholds. We model the utility of each voter for a committee as a normalized monotone symmetric norm, capturing, among others, additive welfare, best-representative utility, top-$r$ welfare, $\ell_p$ welfare, and normalized non-increasing ordered weighted averages. We design a deterministic rule with distortion at most $2(2m)^{1/t}$ and a randomized rule with distortion at most $2\min\{m^{1/(t+1)},m/k\}$. These guarantees hold for every committee size $k$ and every norm in our framework. Consequently, a single threshold yields distortion $O(m)$ for deterministic rules and $O(\sqrt{m})$ for randomized rules, while $O(\log m)$ thresholds suffice for constant distortion. We complement these results with norm-dependent lower bounds that asymptotically match our upper bounds for constant committee sizes, including the single-winner case.