Ranking from Stochastic Pairwise Preferences: Recovering Condorcet Winners and Tournament Solution Sets at the Top

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 algo-rithms including the Rank Centrality algorithm, the Matrix Borda algorithm, and the SVM-RankAggregation algorithm succeed in recov-ering a ranking that minimizes a global pair-wise 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 exam-ple, if a Condorcet winner exists that beats ev-ery other item, it is natural to ask that this be ranked at the top. More generally, several tour-nament solution concepts such as the top cycle, Copeland set, Markov set and others have been proposed in the social choice literature for choos-ing a set of winners in the presence of cycles. We show that existing algorithms can fail to per-form well in terms of ranking Condorcet winners and various natural tournament solution sets at the top. We then give alternative ranking algo-rithms that provably rank Condorcet winners, top cycles, and other tournament solution sets of in-terest at the top. In all cases, we give finite sam-ple complexity bounds for our algorithms to re-cover such winners. As a by-product of our anal-ysis, we also obtain an improved sample com-plexity 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)