The Complexity of Voter Control and Shift Bribery Under Parliament Choosing Rules
The Complexity of Voter Control and Shift Bribery Under Parliament Choosing Rules
复制标题
议会选举规则下选民控制和转移贿赂的复杂性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Piotr Faliszewski
中科院分区：
文献类型：
--
作者：
T. Put;Piotr Faliszewski
我们研究了两种议会选举规则下的选民控制和转移贿赂问题的复杂性，一种是基于多数原则，另一种是基于Borda规则，考虑了政党进入议会需要通过门槛的情况和没有门槛的情况。议会选择规则是一个给定选民偏好概况的函数，其中每个选民对政党进行排名，输出每个政党在议会中应该获得的席位比例。我们研究了三个问题的复杂性，转移贿赂，通过增加选民来控制，以及通过删除选民来控制，其中一些代理人修改选举以增加分配给特定政党的议会席位的比例。我们表明，在大多数情况下，对于我们的议会选择规则，这些问题可以在多项式时间内解决，但我们也显示了基于borda的规则的几个$${{\mathrm {NP}}}$$ np -硬度结果，对于存在进入议会门槛的情况。
We study the complexity of voter control and shift bribery problems under two parliament choosing rules, one based on the Plurality rule and one based on the Borda rule considering both the case where there is a threshold a party needs to pass to enter the parliament, and the case where there is no such threshold. A parliament choosing rule is a function that given a preference profile of the voters where each voter ranks political parties outputs the fraction of seats each of the parties should receive in the parliament. We study the complexity of three problems, shift bribery, control by adding voters, and control by deleting voters, where some agent modifies the election in order to increase the fraction of the seats in parliament assigned to a given party. We show that in most cases these problems can be solved in polynomial time for our parliament choosing rules, but we also show several $${{\mathrm {NP}}}$$NP-hardness results for the Borda-based rule, for the case where there is a threshold for entering the parliament.
巴克林的操纵、贿赂和竞选管理的复杂性以及后备投票
影响因子：
1.9
作者：
P. Faliszewski;Y. Reisch;J. Rothe;L. Schend
通讯作者：
L. Schend