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.
翻译:在社会排名中,人们可以使用多种等级、Veto和Borda等评分系统。我们区分了三种评分方法:分级、反复选择我们删除的胜者、排名最高、反复选择我们删除的败者、排名最低的败者,然后反复选择我们删除的败者、排名最低的败者。后一种方法捕捉了经常研究的投票规则:单一可转移投票(aka instant runnoff 投票)、Coombs和Baldwin。在一项实验分析中,我们发现这三种方法在实际中产生不同的排名。我们还提供了证据,证明按顺序选择优者最适于检测候选人的“真实”排名。对于我们班级的不同规则,我们随后研究确定某个特定候选人在所选的排名中的位置的(参数化)计算复杂性。作为我们分析的一部分,我们还考虑了STV、Coombs和Baldwin的温人决定问题,并在没有多少选民或候选人时决定其复杂性。