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.
翻译:多赢者选举中的公平性是计算社会选择中日益扩大的一线研究,主要涉及使用制约因素来确保公平。最近的工作提出了一个模式,以寻找一个多样的 emph{and}代表委员会,并研究了模型的计算方面。然而,这项工作在候选人和选民如何分组的主要假设下产生了复杂的结果。在这里,我们缩小了这一差距,并用单调、分立的多赢者多赢者投票规则对寻找一个多样化和有代表性的委员会的复杂性进行了分类,以P$\neq$NP为条件。