CSL Master Calendar

Back to Listing

Communications Seminar: Iterative Ranking from Pair-wise Comparisons

Event Type
Communications Seminar
141 Coordinated Science Lab
Nov 26, 2012   4:00 - 5:00 pm  
Professor Sewoong Oh, IESE
Originating Calendar
CSL Communications Group Calendar

The question of aggregating pairwise comparisons to obtain a global ranking has been of interest for a very long time: be it ranking of online gamers (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In addition to obtaining a ranking, finding 'scores' for each object is of interest for understanding the intensity of the preferences. In this talk, I will describe a new approach for discovering scores for objects (or items) from pairwise comparisons. The algorithm has a natural random walk interpretation over the graph of objects with an edge present between a pair of objects if they are compared; the stationary probability of this random walk assigns a score to each objects. To establish the efficacy of our method, we consider the popular Bradley-Terry-Luce (BTL) model and provide an upper bound on the finite sample error rate. The number of samples required to learn the score well with high probability depends on the structure of the comparison graph. When the Laplacian of the comparison graph has a strictly positive spectral gap, this leads to an order-optimal sample complexity. We also provide numerical results on real and synthetic data-sets to compare our approach to other popular approaches.

link for robots only