论文标题
可能的赢家在部分连锁店中的复杂性
The Complexity of Possible Winners on Partial Chains
论文作者
论文摘要
可能的赢家（PW）问题是计算社会选择中的基本算法问题，它涉及选举，其中选民在候选人之间仅表达部分偏好。通过一系列调查，针对所有纯粹的位置评分规则确定了PW问题的复杂性的完整分类：PW问题是在P中，用于多元化和否决权规则，以及所有其他此类规则的NP完整规则。最近，对PW问题进行了研究，这些问题是在自然环境中出现的一系列有限部分订单的类别，例如分区的部分订单和截断的部分订单；特别是，有一些规则在此类限制的部分订单上从NP填充到P的一些规则。在这里，我们研究了部分链中的PW问题，即部分订单，这些订单是其域子集的总订单。这些订单自然而然地在各种环境中出现，包括电影或餐馆的排名。我们通过确定可能令人惊讶的是，这种限制不会改变问题的复杂性，即，对于所有纯粹的位置评分规则，除多元化和否决权规则外，PW问题是NP问题，我们将PW问题的复杂性分类为部分链中。作为副产品，我们获得了在任意部分订单上PW问题复杂性的新的，更有原则的证明。
The Possible Winner (PW) problem, a fundamental algorithmic problem in computational social choice, concerns elections where voters express only partial preferences between candidates. Via a sequence of investigations, a complete classification of the complexity of the PW problem was established 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. More recently, the PW problem was studied on classes of restricted partial orders that arise in natural settings, such as partitioned partial orders and truncated partial orders; in particular, it was shown that there are rules for which 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 are 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, namely, the PW problem is NP-complete for all pure positional scoring rules other than the plurality and veto rules. As a byproduct, we obtain a new and more principled proof of the complexity of the PW problem on arbitrary partial orders.
