论文标题
关于获胜者验证的复杂性和候选人多翼投票规则的候选人
On the complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules
论文作者
论文摘要
在多赢家选举的文献中，Chamberlin-Courant和Monroe规则是基本且经过充分研究的规则。确定是否存在具有Chamberlin-Courant（Monroe）评分的K大小的委员会的问题，最多是NP完整的。我们在此环境中考虑以下自然问题：a）给定K大小的委员会作为投入，是一个最佳的K级委员会，b）给定候选人C和委员会规模K，是否有一个最佳的K尺寸委员会包含C？ 在这项工作中，我们解决了在排名和批准选票的情况下，在Chamberlin-Courant和Monroe投票规则中，这两个问题的复杂性。我们表明，验证如果给定委员会是最佳的，则对于$θ_{2}}^{p} $完成了后一个问题。当输入由单峰排名组成时，我们还证明了第二个问题的有效算法。我们的贡献填补了这些重要的多获胜者规则的文献中的基本差距。
The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for $Θ_{2}^{P}$. We also demonstrate efficient algorithms for the second problem when the input consists of single-peaked rankings. Our contribution fills an essential gap in the literature for these important multi-winner rules.
