The Coalitional Manipulation problem has been studied extensively in the
literature for many voting rules. However, most studies have focused on the
complete information setting, wherein the manipulators know the votes of the
non-manipulators. While this assumption is reasonable for purposes of showing
intractability, it is unrealistic for algorithmic considerations. In most
real-world scenarios, it is impractical for the manipulators to have accurate
knowledge of all the other votes. In this paper, we investigate manipulation
with incomplete information. In our framework, the manipulators know a partial
order for each voter that is consistent with the true preference of that voter.
In this setting, we formulate three natural computational notions of
manipulation, namely weak, opportunistic, and strong manipulation. We say that
an extension of a partial order is if there exists a manipulative vote for that
extension.
1. Weak Manipulation (WM): the manipulators seek to vote in a way that makes
their preferred candidate win in at least one extension of the partial votes of
the non-manipulators.
2. Opportunistic Manipulation (OM): the manipulators seek to vote in a way
that makes their preferred candidate win in every viable extension of the
partial votes of the non-manipulators.
3. Strong Manipulation (SM): the manipulators seek to vote in a way that
makes their preferred candidate win in every extension of the partial votes of
the non-manipulators.
We consider several scenarios for which the traditional manipulation problems
are easy (for instance, Borda with a single manipulator). For many of them, the
corresponding manipulative questions that we propose turn out to be
computationally intractable. Our hardness results often hold even when very
little information is missing, or in other words, even when the instances are
quite close to the complete information setting.

本文探究了在不完整信息情况下的联合操纵问题及其计算性质，并提出了三种自然的操纵计算概念。我们提出的操纵问题在很多情况下都是计算上难以处理的，即使在很少信息缺失的情况下也是如此，这也使得本文的研究有着重要的实际应用意义。

带有部分信息的投票操纵复杂性

Complexity of Manipulation with Partial Information in Voting

In the Possible Winner problem in computational social choice theory, we are
given a set of partial preferences and the question is whether a distinguished
candidate could be made winner by extending the partial preferences to linear
preferences. Previous work has provided, for many common voting rules, fixed
parameter tractable algorithms for the Possible Winner problem, with number of
candidates as the parameter. However, the corresponding kernelization question
is still open and in fact, has been mentioned as a key research challenge. In
this paper, we settle this open question for many common voting rules.
We show that the Possible Winner problem for maximin, Copeland, Bucklin,
ranked pairs, and a class of scoring rules that include the Borda voting rule
do not admit a polynomial kernel with the number of candidates as the
parameter. We show however that the Coalitional Manipulation problem which is
an important special case of the Possible Winner problem does admit a
polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring
rules that includes the Borda voting rule, when the number of manipulators is
polynomial in the number of candidates. A significant conclusion of our work is
that the Possible Winner problem is harder than the Coalitional Manipulation
problem since the Coalitional Manipulation problem admits a polynomial kernel
whereas the Possible Winner problem does not admit a polynomial kernel.

本文针对计算社会选择理论中可能获胜者问题，以及围绕所述问题的投票规则和多项式核心化方面的挑战等，进行了研究，并对常见投票规则的可能获胜者问题是否具有多项式核心化进行了描述，同时，对所研究问题与合谋操纵问题的关系进行了探讨。