Motivated by the difficulty of specifying complete ordinal preferences over a
large set of $m$ candidates, we study voting rules that are computable by
querying voters about $t < m$ candidates. Generalizing prior works that focused
on specific instances of this problem, our paper fully characterizes the set of
positional scoring rules that can be computed for any $1 \leq t < m$, which
notably does not include plurality. We then extend this to show a similar
impossibility result for single transferable vote (elimination voting). These
negative results are information-theoretic and agnostic to the number of
queries. Finally, for scoring rules that are computable with limited-sized
queries, we give parameterized upper and lower bounds on the number of such
queries a deterministic or randomized algorithm must make to determine the
score-maximizing candidate. While there is no gap between our bounds for
deterministic algorithms, identifying the exact query complexity for randomized
algorithms is a challenging open problem, of which we solve one special case.

通过对候选人的完整排序偏好的难以确定性我们研究了能够通过查询选民关于 t <m 个候选人的规则计算的投票规则。在先前研究的基础上，我们的研究全面描述了对于任何 1≤t < m 时可以计算的位置评分规则集合，特别地，这不包括多数派规则。然后，我们将这一结论推广到单可变投票 (淘汰投票) 中也出现了类似的不可能性结果。这些负面结果是信息理论的，并且与查询数量无关。最后，对于可以用有限大小的查询计算的评分规则，我们针对决定得分最大候选人的确定性或随机算法必须进行的查询数量提供了参数化的上界和下界。对于确定性算法而言，我们的边界是完全相同的，然而对于随机算法而言，确定其精确的查询复杂度是一个具有挑战性的开放问题，我们解决了其中一个特殊情况。