Ranking from Stochastic Pairwise Preferences: Recovering Condorcet Winners and Tournament Solution Sets at the Top
Ranking from Stochastic Pairwise Preferences: Recovering Condorcet Winners and Tournament Solution Sets at the Top
复制标题
随机配对偏好排名：恢复孔多塞获胜者和顶级锦标赛解决方案集
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Agarwal
中科院分区：
文献类型：
--
作者：
A. Rajkumar;Suprovat Ghoshal;Lek;S. Agarwal
我们考虑随机抽样成对偏好中n个项目的排序问题。最近的研究表明，当潜在的成对偏好是非循环的时，包括Rank Centrality算法、Matrix Borda算法和SVM-Rank Aggregation算法在内的几种算法成功地恢复了一个最小化全局成对不一致误差的排名（Rajkumar和Agarwal，2014）。在本文中，我们考虑设置成对的偏好可以包含循环。在这样的设置中，人们可能仍然希望能够在排名的顶部恢复“好”项目。例如，如果孔多塞赢家存在，击败每一个其他项目，这是自然的要求，这是排名在顶部。更一般地说，一些锦标赛解决方案的概念，如顶部循环，科普兰集，马尔可夫集和其他人已经提出了在社会选择文献中选择一组赢家存在的周期。我们发现，现有的算法可能无法很好地执行在排名孔多塞冠军和各种自然锦标赛的解决方案集在顶部。然后，我们给出了替代排名算法，可证明排名孔多塞冠军，顶部的周期，和其他比赛的解决方案集的利益在顶部。在所有情况下，我们给我们的算法，以恢复这样的赢家有限样本的复杂性界限。作为我们分析的副产品，我们还获得了Rank Centrality算法在Bradley-Terry-吕斯（BTL）条件下恢复最佳排名的改进的样本复杂度界限，这回答了Rajkumar和Agarwal（2014）的一个开放问题。
We consider the problem of ranking n items from stochastically sampled pairwise preferences. It was shown recently that when the underlying pairwise preferences are acyclic, several algorithms including the Rank Centrality algorithm, the Matrix Borda algorithm, and the SVM-Rank Aggregation algorithm succeed in recovering a ranking that minimizes a global pairwise disagreement error (Rajkumar and Agarwal, 2014). In this paper, we consider settings where pairwise preferences can contain cycles. In such settings, one may still like to be able to recover 'good' items at the top of the ranking. For example, if a Condorcet winner exists that beats every other item, it is natural to ask that this be ranked at the top. More generally, several tournament solution concepts such as the top cycle, Copeland set, Markov set and others have been proposed in the social choice literature for choosing a set of winners in the presence of cycles. We show that existing algorithms can fail to perform well in terms of ranking Condorcet winners and various natural tournament solution sets at the top. We then give alternative ranking algorithms that provably rank Condorcet winners, top cycles, and other tournament solution sets of interest at the top. In all cases, we give finite sample complexity bounds for our algorithms to recover such winners. As a by-product of our analysis, we also obtain an improved sample complexity bound for the Rank Centrality algorithm to recover an optimal ranking under a Bradley-Terry-Luce (BTL) condition, which answers an open question of Rajkumar and Agarwal (2014).