English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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.

Classifying the Complexity of the Possible Winner Problem on Partial Chains