Classifying the complexity of the possible winner problem on partial chains

Abstract

The Possible Winner (PW) problem, a fundamental algorithmic problem in computational social choice, concerns elections where voters express only partial preferences between candidates. A sequence of investigations led to a complete classification of the complexity of this problem for all pure positional scoring rules: the PW problem is in P for the plurality and veto rules, and NP-complete for all other such rules. The PW problem has also been studied on classes of restricted partial orders, such as partitioned partial orders and truncated partial orders; one of the findings is that there are positional scoring rules for which the complexity of the PW problem drops from NP-complete to P on such restricted partial orders. Here, we investigate the PW problem on partial chains, i.e., partial orders that consist of a total order on a subset of their domains. Such orders arise naturally in a variety of settings, including rankings of movies or restaurants. We classify the complexity of the PW problem on partial chains by establishing that, perhaps surprisingly, this restriction does not change the complexity of the problem. Specifically, we show that the PW problem on partial chains is NP-complete for all pure positional scoring rules other than the plurality rule and the veto rule, while, of course, for the latter two rules this problem remains in P.