Approval-Based Multiwinner Voting with Candidate Qualities

Abstract

We initiate the study of a new model of approval-based multiwinner voting in which each candidate carries an exogenous quality score, capturing, for instance, the reliability of the candidate or their relevance to the context of the selection. Quality scores break with the standard assumption of approval-based multiwinner voting that candidates are fully defined by the set of their supporters. We rethink what proportional representation means in the presence of quality scores. For this, we introduce a threshold-based and a value-based family of axioms, analyze their relationships, satisfiability, and computational complexity, and present rules that achieve the strongest jointly satisfiable combinations of our proportionality axioms. We then analyze the compatibility of proportionality with the natural goal of maximizing the summed quality of the selected candidates. While imposing standard proportionality notions can lead to an almost complete loss of quality, we show that under a new class of reciprocal axioms, which scale a group's entitlement by the quality of its commonly approved candidate(s), there always exist proportional committees retaining at least 3/4 of the optimal summed quality, and such committees can be computed by our voting rules at no additional computational cost.