Control in the presence of manipulators: cooperative and competitive cases
Control in the presence of manipulators: cooperative and competitive cases
复制标题
存在操纵器时的控制：合作和竞争案例
DOI：
10.1007/s10458-020-09475-6
复制
发表时间：
2020
影响因子：
1.9
通讯作者：
Hemaspaandra, Lane A.
中科院分区：
文献类型：
--
作者：
Fitzsimmons, Zack;Hemaspaandra, Edith;Hemaspaandra, Lane A.
控制和操纵是对选举攻击研究最多的两种类型。本文研究了存在操纵者的选举控制攻击的复杂性。我们研究了试图控制选举的“主席”与操纵者结盟的情况，以及操纵者试图挫败主席的情况。在后一种情况下，我们可以看到游戏顺序对复杂性的影响。我们证明了所有标准控制情况下，每个具有多项式时间赢家问题的选举系统的上界，其中一些边界位于多项式层次的第二或第三层，并且我们提供了匹配的下界来证明这些紧密性。然而，对于重要的自然系统，复杂性可以低得多。我们证明了对于批准和多数选举，控制器和操纵器之间甚至竞争性冲突的复杂性远远低于这些高界限，甚至低至多项式时间。然而，对于边界投票的情况，我们表明，除非NP = coNP，否则这种冲突会增加复杂性。
Control and manipulation are two of the most studied types of attacks on elections. In this paper, we study the complexity of control attacks on elections in which there are manipulators. We study both the case where the “chair” who is seeking to control the election is allied with the manipulators, and the case where the manipulators seek to thwart the chair. In the latter case, we see that the order of play substantially influences the complexity. We prove upper bounds, holding over every election system with a polynomial-time winner problem, for all standard control cases, and some of these bounds are at the second or third level of the polynomial hierarchy, and we provide matching lower bounds to prove these tight. Nonetheless, for important natural systems the complexity can be much lower. We prove that for approval and plurality elections, the complexity of even competitive clashes between a controller and manipulators falls far below those high bounds, even as low as polynomial time. Yet for a Borda-voting case we show that such clashes raise the complexity unless NP = coNP.