论文标题
在部分投票概况中确定必要和可能的顶级冠军的复杂性
The Complexity of Determining the Necessary and Possible Top-k Winners in Partial Voting Profiles
论文作者
论文摘要
当选民偏好以不完整（部分）方式知道选民时，胜利者的决心通常被视为对必要和可能的获胜者的识别；这些候选人分别在所有完成或至少完成部分投票概况中获胜。如果是位置得分规则，获奖者是获得选民最高总分的候选人。然而，选举的结果可能超出了最高赢家的绝对赢家，例如委员会选择，政党的初选以及在招募中排名。我们研究了确定部分投票概况的必要和可能的顶级奖金获奖者的计算复杂性。我们的结果适用于位置评分规则的一般类别，并专注于作为输入的一部分以及固定$ K $的$ K $的情况。
When voter preferences are known in an incomplete (partial) manner, winner determination is commonly treated as the identification of the necessary and possible winners; these are the candidates who win in all completions or at least one completion, respectively, of the partial voting profile. In the case of a positional scoring rule, the winners are the candidates who receive the maximal total score from the voters. Yet, the outcome of an election might go beyond the absolute winners to the top-$k$ winners, as in the case of committee selection, primaries of political parties, and ranking in recruiting. We investigate the computational complexity of determining the necessary and possible top-$k$ winners over partial voting profiles. Our results apply to general classes of positional scoring rules and focus on the cases where $k$ is given as part of the input and where $k$ is fixed.
