Parameterized Complexity of Committee Elections with Dichotomous and Trichotomous Votes

We study the winner determination problem for three prevalent committee election rules: Chamberlin-Courant Approval Voting (CCA), Proportional Approval Voting (PAV), and Satisfaction Approval Voting (SAV). Axiomatic and algorithmic studies of elections under these rules have been conducted recently. It is known that the winner determination problem is NP-hard for CCA and PAV and polynomial-time solvable for SAV, if the input votes are dichotomous. Moreover, parameterized complexity of the two NP-hard cases has been examined with respect to some natural parameters such as the number of candidates or the number of votes. In this paper, we extend the above studies to committee elections with trichotomous votes and identify cases, where trichotomous votes lead to an increase of parameterized complexity. We also consider the maximin (or egalitarian) variations of the rules, where the minimum satisfaction of the voters is maximized.