| Title | : | Ranking from Pairwise Comparisons |
| Speaker | : | Arun Rajkumar (Xerox Research Centre India (XRCI)) |
| Details | : | Fri, 2 Dec, 2016 10:00 AM @ BSB 361 |
| Abstract: | : | Ranking a set of candidates or items from pairwise comparisons is a fundamental problem that arises in many settings such as elections, recommendation systems, sports team rankings, document rankings and so on. While the problem of ranking from pairwise comparisons has been studied in multiple communities such as machine learning, operations research, linear algebra, statistics etc., and several algorithms (both classic and recent) have been proposed, it is not well understood under what conditions these different algorithms perform well. In this talk, we aim to fill this fundamental gap, by elucidating precise conditions under which different existing algorithms perform well, as well as giving new algorithms that provably perform well under broader conditions. We will define an interesting class of conditions on the pairwise probabilities of items being preferred to one another and develop algorithms that provably produce optimal rankings with a tight sample complexity. We will show that several existing models such as the Bradley-Terry-Luce (BTL) model, Thurstone model etc., are special cases of this condition. We will also briefly look at the case where items have associated features and see how one can break the O(nlog(n)) sample complexity barrier for ranking in such cases. Time permitting, we will also discuss notions of tournament solutions and some recent work on identifying winners from a set of items by active pairwise comparisons.
References for the talk:
|
