Iterative Ranking from Pair-wise Comparisons

Professor Devavrat Shah
Associate Professor, Massachusetts Institute of Technology
Given on: May 02, 2013

Abstract

The question of aggregating pair-wise comparisons to obtain a global ranking over a collection of objects has been of interest for a very long time: be it ranking of online gamers and chess players, aggregating social opinions, or deciding which product to sell based on transactions. In most settings, in addition to obtaining ranking, finding ‘scores’ for each object (e.g. player’s rating) is of interest for understanding the intensity of the preferences.

We propose an iterative rank aggregation algorithm for discovering scores for objects 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 scores turn out to be the stationary probability of this random walk.

To establish the efficacy of algorithm, the popular Bradley-Terry-Luce (BTL) model is considered. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. In particular, the number of samples required to learn the score well with high probability depends on the structure of comparison graph – when the Laplacian of the comparison graph has constant spectral gap, e.g. pairs chosen at random for comparison, this leads to near-optimal dependence on the number of samples.

This is based on a joint work with Sahand Negahban (MIT) and Sewoong Oh (UIUC).

Biography

Devavrat Shah is currently a Jamieson career development associate professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS) and Operations Research Center (ORC). He received his Bachelor of Technology in Computer Science and Engineering from Indian Institute of Technology, Bombay in 1999 with the Presidents of India Gold Medal – awarded to the best graduating student across all engineering disciplines. He received his PhD in Computer Science from Stanford University in 2004. His doctoral thesis titled “Randomization and Heavy Traffic Theory: New Approaches for Switch Scheduling Algorithms” was completed under supervision of Balaji Prabhakar. His thesis was adjudged winner of George B. Dantzig best dissertation award from INFORMS in 2005. After spending a year between Stanford, Berkeley and MSRI, he started teaching at MIT in Fall 2005.

Devavrat Shah has been co-awarded best paper awards at the IEEE INFOCOM ’04, ACM SIGMETRICS/Performance ’06; and he has supervised best student paper awards at Neural Information Processing Systems ’08, ACM SIGMETRICS/Performance ’09 and Management Science and Operations Management Paper competition ’10.

He was awarded the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms. He received the 2010 Erlang Prize from INFORMS which is given to a young researcher for outstanding contributions to applied probability.