Understanding the Impact of Proportionality in Approval-Based Multiwinner Elections
Niclas Boehmer, Lara Glessen, Jannik Peters
尽管对基于批准的多赢家投票的相称性进行了广泛的理论研究,但其对哪些委员会和候选人在实践中可以被选中的影响仍然知之甚少。 我们通过(i)分析与相称性公理行为相关的几个自然问题的计算复杂性,以及(ii)对现实世界和合成选举进行广泛的实验研究来解决这一差距。 我们的发现揭示了不同实例之间相称性限制性的重大变化,包括以前在一些现实世界中未被观察到的高度限制。 我们还介绍和评估新的措施,以量化候选人对实现比例结果的重要性,这与通过批准分数评估候选人人数明显不同。
Despite extensive theoretical research on proportionality in approval-based multiwinner voting, its impact on which committees and candidates can be selected in practice remains poorly understood. We address this gap by (i) analyzing the computational complexity of several natural problems related to the behavior of proportionality axioms, and (ii) conducting an extensive experimental study on both real-world and synthetic elections. Our findings reveal substantial variation in the restrictivene...