论文标题
从截短的选票中近似投票规则
Approximating Voting Rules from Truncated Ballots
论文作者
论文摘要
古典投票规则假定选票是完全偏好的命令，而不是候选人。但是，当候选人的数量足够大时，要求选民对所有候选人进行排名太高。我们建议确定等级K，要求所有选民指定他们最好的K候选人，然后考虑规则的“ Top-K近似”，这些规则仅考虑到每个选票的顶级候选人。我们考虑了近似质量的两个度量：选择与原始规则相同的获胜者的概率和得分比。我们进行了最糟糕的研究（仅针对后一种措施），对于这两个措施，平均研究和实际数据集的研究。
Classical voting rules assume that ballots are complete preference orders over candidates. However, when the number of candidates is large enough, it is too costly to ask the voters to rank all candidates. We suggest to fix a rank k, to ask all voters to specify their best k candidates, and then to consider "top-k approximations" of rules, which take only into account the top-k candidates of each ballot. We consider two measures of the quality of the approximation: the probability of selecting the same winner as the original rule, and the score ratio. We do a worst-case study (for the latter measure only), and for both measures, an average-case study and a study from real data sets.
