论文标题
使用评分规则进行汇总
Rank Aggregation Using Scoring Rules
论文作者
论文摘要
为了将排名汇总为社会排名，可以使用多数，否决权和Borda等评分系统。我们区分了三种类型的方法：按得分排名，通过反复选择我们删除并排名最高的获胜者，并反复选择一个失败者来排名，我们删除并排名最低。后一种方法捕获了经常研究的投票规则单一可转让投票（又称即时径流投票），COOMBS和BALDWIN。在实验分析中，我们表明三种方法在实践中产生不同的排名。我们还提供了证据表明，依次选择获胜者最适合检测候选人的“真实”排名。对于我们的课程中的不同规则，我们将研究（参数化的）计算复杂性的确定位置，在哪个位置可以出现在选定的排名中。作为分析的一部分，我们还考虑了STV，COOMB和BALDWIN的获胜者确定问题，并在选民或候选人很少时确定其复杂性。
To aggregate rankings into a social ranking, one can use scoring systems such as Plurality, Veto, and Borda. We distinguish three types of methods: ranking by score, ranking by repeatedly choosing a winner that we delete and rank at the top, and ranking by repeatedly choosing a loser that we delete and rank at the bottom. The latter method captures the frequently studied voting rules Single Transferable Vote (aka Instant Runoff Voting), Coombs, and Baldwin. In an experimental analysis, we show that the three types of methods produce different rankings in practice. We also provide evidence that sequentially selecting winners is most suitable to detect the "true" ranking of candidates. For different rules in our classes, we then study the (parameterized) computational complexity of deciding in which positions a given candidate can appear in the chosen ranking. As part of our analysis, we also consider the Winner Determination problem for STV, Coombs, and Baldwin and determine their complexity when there are few voters or candidates.
