On the Complexity of Finding a Diverse and Representative Committee using a Monotone, Separable Positional Multiwinner Voting Rule
This addresses a fairness issue in computational social choice for election systems, but it is incremental as it builds on prior work by removing restrictive assumptions.
The paper tackles the problem of finding a diverse and representative committee in multiwinner elections, closing a gap by providing a full complexity classification under the assumption P ≠ NP, showing that the problem is NP-hard in general but polynomial-time solvable in certain cases.
Fairness in multiwinner elections, a growing line of research in computational social choice, primarily concerns the use of constraints to ensure fairness. Recent work proposed a model to find a diverse \emph{and} representative committee and studied the model's computational aspects. However, the work gave complexity results under major assumptions on how the candidates and the voters are grouped. Here, we close this gap and classify the complexity of finding a diverse and representative committee using a monotone, separable positional multiwinner voting rule, conditioned \emph{only} on the assumption that P $\neq$ NP.