Papers for

election designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Multiwinner voting rules handle coarse preferences with bounded distortion

The Distortion of Threshold Approval Multiwinner Voting

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.

Fri 9 OctComputer Science and Game Theory
The gist
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.
Open → 2610.13725v1