论文标题
贪婪批准规则的鲁棒性
Robustness of Greedy Approval Rules
论文作者
论文摘要
我们使用Bredereck等人提出的框架研究了Greedycc，Greedypav和Phargmen的顺序规则的鲁棒性。对于（Multiwinner）序数选举，并通过Gawron和Faliszewski的批准设置采用。首先，我们表明，对于我们的每个规则和每个委员会规模的$ k $，在某些选举中增加或取消了一定的批准会导致获胜委员会彻底改变（即行动后的获胜委员会在操作前与该委员会脱节）。其次，我们表明，确定需要从选举中添加（或删除）以改变其结果的问题是我们的每个规则的NP完整。最后，我们在存在随机噪声的情况下实验评估规则的鲁棒性。
We study the robustness of GreedyCC, GreedyPAV, and Phargmen's sequential rule, using the framework introduced by Bredereck et al. for the case of (multiwinner) ordinal elections and adopted to the approval setting by Gawron and Faliszewski. First, we show that for each of our rules and every committee size $k$, there are elections in which adding or removing a certain approval causes the winning committee to completely change (i.e., the winning committee after the operation is disjoint from the one before the operation). Second, we show that the problem of deciding how many approvals need to be added (or removed) from an election to change its outcome is NP-complete for each of our rules. Finally, we experimentally evaluate the robustness of our rules in the presence of random noise.
