Iterative ranking from pair-wise comparisons

By Sahand N. Negahban, Sewoong Oh, Devavrat Shah. 2012

287 citations recorded by the source corpus.

Subfields: Information Retrieval & Search

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Retrieval & Search

Citations in the corpus

Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, methodology): “As a second application, assume that the comparison graph is an Erd¨os-R´enyi graph with parameter p , possibly vanishing in d , a setting that has been the focus of much of the recent work on the BTL model (Negahban et al., 2012; Yan et al., 2012; Han et al., 2020).”
High-Fidelity Generative Image Compression (2020, methodology): “We validated that the ordering is consistent with other methods for obtaining total orderings from pairwise comparisons that do not allow the computation of confidence intervals [37, 12].”
Active Ranking with Subset-wise Preferences (2018, background): “Over the years, ranking from pairwise preferences (k = 2) has been studied in both the batch or non-adaptive setting [20, 32, 37, 30] and the active or adaptive setting [7, 22, 2].”
Copeland Dueling Bandits (2015, result): “Since our results (see §5) establish bounds on the number of queries to non-Copeland winners, they can also be applied to other notions of regret.”
Fast and Accurate Inference of Plackett-Luce Models (2015, methodology): “Rank Centrality considers transition rates proportional to the ratio of wins, whereas (7) justifies making transition rates proportional to the count of wins.”
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model (2020, methodology): “This problem formulation is standard in the literature; in particular, its analysis has been the subject of a number of recent papers, e.g., (Negahban et al. , 2012; Rajkumar & Agarwal, 2014; Negahban et al. , 2016; Agarwal et al. , 2018; Hendrickx et al. , 2019).”
Graph Resistance and Learning from Pairwise Comparisons (2019, background): “Our work is most closely related to the papers (Negahban et al., 2012) and (Negahban et al.”
Preference-based Online Learning with Dueling Bandits: A Survey (2018, methodology): “…motivated by the PageRank algorithm (Brin and Page, 1998), which has been well studied in social choice theory (Cohen et al., 1999; Brandt and Fischer, 2007) and rank aggregation (Negahban et al., 2012), and which is widely used in many application ﬁelds (Brin and Page, 1998; Kocsor et al., 2008).”
Random walks and diffusion on networks (2016, unknown): “[324, 331, 332].”
Maximum Selection and Ranking under Noisy Comparisons (2017, methodology): “Two types of algorithms have been proposed for maximum selection and ranking under noisy comparisons: nonadaptive or offline (Rajkumar & Agarwal, 2014; Negahban et al., 2012; 2016; Jang et al., 2016) where the comparison pairs are chosen in advance, and adaptive or online where the comparison pairs ”
Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence (2015, methodology): “Negahban et al. (2012) provide minimax bounds for the BTL model in the special case of comparisons chosen uniformly at random.”