Dominating Manipulations in Voting with Partial Information
Dominating Manipulations in Voting with Partial Information
复制标题
以部分信息主导投票操纵
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Lirong Xia
中科院分区：
文献类型：
--
作者：
Vincent Conitzer;T. Walsh;Lirong Xia
当操作器仅具有有关非操纵者投票的部分信息时，我们会考虑操纵问题。这样的部分信息由{\ em信息集}描述，这是与操纵器无法区分的非操纵器的概况集。鉴于这样的信息集，{\ em占主导地位的操纵}是一项非真实的投票，操纵者可以投票，这使得赢家至少在操纵者以真实的投票投票时，至少比赢家一样优选（有时更可取）。当操纵器具有完整的信息时，计算是否存在主导操作的是许多常见的投票规则（通过已知结果）。我们表明，当操纵器没有信息时，对于许多常见的投票规则，没有任何主导操作。当操纵器的信息由部分订单表示并且只有一小部分偏好是未知的，那么计算主导操作对于许多常见的投票规则而言是NP-HARD。因此，我们的结果阐明了我们是否可以通过限制有关其他选民投票的信息来防止战略行为。
We consider manipulation problems when the manipulator only has partial information about the votes of the non-manipulators. Such partial information is described by an {\em information set}, which is the set of profiles of the non-manipulators that are indistinguishable to the manipulator. Given such an information set, a {\em dominating manipulation} is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator's information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.