The Coalitional Manipulation (CM) problem has been studied extensively in the literature for many voting rules. The CM problem, however, has been studied only in the complete information setting, that is, when the manipulators know the votes of the non-manipulators. A more realistic scenario is an incomplete information setting where the manipulators do not know the exact votes of the non- manipulators but may have some partial knowledge of the votes. In this paper, we study a setting where the manipulators know a partial order for each voter that is consistent with the vote of that voter. In this setting, we introduce and study two natural computational problems - (1) Weak Manipulation (WM) problem where the manipulators wish 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) Strong Manipulation (SM) problem where the manipulators wish to vote in a way that makes their preferred candidate win in all possible extensions of the partial votes of the non-manipulators. We study the computational complexity of the WM and the SM problems for commonly used voting rules such as plurality, veto, k-approval, k-veto, maximin, Copeland, and Bucklin. Our key finding is that, barring a few exceptions, manipulation becomes a significantly harder problem in the setting of incomplete votes.
@cite_24: An important research topic in the field of computational social choice is the complexity of various forms of dishonest behavior, such as manipulation, control, and bribery. While much of the work on this topic assumes that the cheating party has full information about the election, recently there have been a number of attempts to gauge the complexity of non-truthful behavior under uncertainty about the voters' preferences. In this paper, we analyze the complexity of (coalitional) manipulation for the setting where there is uncertainty about the voting rule: the manipulator(s) know that the election will be conducted using a voting rule from a given list, and need to select their votes so as to succeed no matter which voting rule will eventually be chosen. We identify a large class of voting rules such that arbitrary combinations of rules from this class are easy to manipulate; in particular, we show that this is the case for single-voter manipulation and essentially all easy-to-manipulate voting rules, and for coalitional manipulation and k-approval. While a combination of a hard-to-manipulate rule with an easy-to-manipulate one is usually hard to manipulate---we prove this in the context of coalitional manipulation for several combinations of prominent voting rules---we also provide counterexamples showing that this is not always the case.
@cite_2: 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 information set, which is the set of profiles of the non-manipulators that are indistinguishable to the manipulator. Given such an information set, a 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.
@cite_2 also study manipulation under partial information setting. However, they focused on whether or not there exists a and shows that it is for many common voting rules. Given some partial votes, a 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. The dominating manipulation problem and the WM and the SM problems do not seem to have any apparent complexity theoretic connection. For example, dominating manipulation problem is for all the common voting rules except plurality and veto, whereas, the SM problem is easy for most of the cases (see table table:partial_summary ). @cite_24 studies manipulation under voting rule uncertainty. However, in our work, the voting rule is fixed and known to the manipulators.