摘要
由于在大量候选人中指定完整的序数偏好存在困难,我们研究了可以通过查询 $t < m$ 个候选人的投票者来计算的投票规则。本文推广了先前针对该问题特定实例的研究,全面刻画了可以在任何 $1 \leq t < m$ 时计算的职位评分规则集合,值得注意的是,该集合不包含简单多数规则。然后,我们将其扩展到表明单一可转移投票(淘汰投票)也存在类似的不可能性结果。这些负面结果是信息论的,与查询的数量无关。最后,对于可以使用有限大小查询计算的评分规则,我们给出了确定得分最大化候选人所需的确定性或随机算法的查询次数的参数上限和下限。虽然我们的界限对于确定性算法没有差距,但确定随机算法的精确查询复杂度是一个具有挑战性的开放性问题,我们解决了一个特例。