Feb, 2024

运用不完整调查数据计算选举规则

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