The Complexity of the Possible Winner Problem with Partitioned Preferences

The Possible-Winner problem asks, given an election where the voters' preferences over the set of candidates is partially specified, whether a distinguished candidate can become a winner. In this work, we consider the computational complexity of the Possible-Winner problem under the assumption that the voter preferences are partitioned. That is, we assume that every voter provides a complete order over sets of incomparable candidates (e.g., candidates are ranked by their level of education). We consider elections with partitioned profiles over positional scoring rules. Our first result is a polynomial time algorithm for voting rules with two distinct values, which include the common k-approval voting rule. We then go on to prove NP-hardness for the class of voting rules that produce scoring vectors with at least four distinct values, and a large class of voting rules that produce scoring vectors with three distinct values.