Papers for

committee organizers

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

Proportional representation challenges with changing ranked votes over time

Proportional Representation in Temporal Voting with Ranked Preferences

Abstract: We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutoff may differ across voters and rounds. We therefore require proportionality to hold for every admissible choice of cutoffs, whether fixed and common, common but varying across rounds, or set individually for each voter in each round. Combining these interpretations with temporal versions of justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC) gives us a hierarchy of axioms. We ask which of these axioms can be guaranteed, and with how much knowledge of the future. Unlike with approval ballots, no version of EJR can be guaranteed, and for the other axioms, flexibility in the cutoffs comes at a price. With a fixed common cutoff, JR, PJR, and PSC can be guaranteed, but only by rules that see all preferences in advance. Once the cutoff may vary across rounds, even such rules cannot guarantee JR or PSC for groups that agree in only some rounds. For groups that agree in every round, however, knowing only the number of rounds suffices for PJR in polynomial time, and PSC needs no knowledge of the future at all. Under individual cutoffs, no version of JR or PJR can be guaranteed, yet a rule as simple as serial dictatorship achieves PJR up to an additive loss that no rule can improve on, however much it knows. Natural preference restrictions restore exact guarantees. Finally, we show that checking our axioms is often coNP-complete; but perhaps surprisingly, a stronger axiom can be easier to check.

Thu 24 SeptComputer Science and Game TheoryArtificial Intelligence
The gist
This paper looks at how to fairly represent voters when decisions happen one by one over time and voters can rank their preferences differently each time. The authors find that ensuring fair representation is more complicated when voters rank rather than approve candidates, especially if the criteria for which candidates count as approved changes from round to round or voter to voter. Some fairness guarantees require knowing future voter preferences in advance, while others can be met with limited or no future knowledge depending on the situation. They also show that checking whether these fairness conditions are met can be computationally hard.
Open → 2609.30555v1