Iterative Ranking from Pair-wise Comparisons
The question of aggregating pairwise 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 (e.g. MSR's TrueSkill system) and chess players, aggregating social opinions, or deciding which product to sell base...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137118.2 |
| _version_ | 1826197473437155328 |
|---|---|
| author | Negahban, Sahand N. Oh, Sewoong Shah, Devavrat |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Negahban, Sahand N. Oh, Sewoong Shah, Devavrat |
| author_sort | Negahban, Sahand N. |
| collection | MIT |
| description | The question of aggregating pairwise 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 (e.g. MSR's TrueSkill system) 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 to understanding the intensity of the preferences. In this paper, we propose a novel 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 edges present between two objects if they are compared; the scores turn out to be the stationary probability of this random walk. The algorithm is model independent. To establish the efficacy of our method, however, we consider the popular Bradley-Terry-Luce (BTL) model in which each object has an associated score which determines the probabilistic outcomes of pairwise comparisons between objects. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. This, in essence, leads to order-optimal dependence on the number of samples required to learn the scores well by our algorithm. Indeed, the experimental evaluation shows that our (model independent) algorithm performs as well as the Maximum Likelihood Estimator of the BTL model and outperforms a recently proposed algorithm by Ammar and Shah [1]. |
| first_indexed | 2024-09-23T10:48:13Z |
| format | Article |
| id | mit-1721.1/137118.2 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:48:13Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/137118.22021-12-10T17:33:01Z Iterative Ranking from Pair-wise Comparisons Negahban, Sahand N. Oh, Sewoong Shah, Devavrat Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science The question of aggregating pairwise 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 (e.g. MSR's TrueSkill system) 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 to understanding the intensity of the preferences. In this paper, we propose a novel 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 edges present between two objects if they are compared; the scores turn out to be the stationary probability of this random walk. The algorithm is model independent. To establish the efficacy of our method, however, we consider the popular Bradley-Terry-Luce (BTL) model in which each object has an associated score which determines the probabilistic outcomes of pairwise comparisons between objects. We bound the finite sample error rates between the scores assumed by the BTL model and those estimated by our algorithm. This, in essence, leads to order-optimal dependence on the number of samples required to learn the scores well by our algorithm. Indeed, the experimental evaluation shows that our (model independent) algorithm performs as well as the Maximum Likelihood Estimator of the BTL model and outperforms a recently proposed algorithm by Ammar and Shah [1]. 2021-12-10T17:33:00Z 2021-11-02T17:13:03Z 2021-12-10T17:33:00Z 2012 2019-07-16T14:30:45Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137118.2 Shah, Devavrat and Negahban, Sahand. 2012. "Iterative ranking from pair-wise comparisons." en https://papers.nips.cc/paper/4701-iterative-ranking-from-pair-wise-comparisons Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/octet-stream Neural Information Processing Systems (NIPS) |
| spellingShingle | Negahban, Sahand N. Oh, Sewoong Shah, Devavrat Iterative Ranking from Pair-wise Comparisons |
| title | Iterative Ranking from Pair-wise Comparisons |
| title_full | Iterative Ranking from Pair-wise Comparisons |
| title_fullStr | Iterative Ranking from Pair-wise Comparisons |
| title_full_unstemmed | Iterative Ranking from Pair-wise Comparisons |
| title_short | Iterative Ranking from Pair-wise Comparisons |
| title_sort | iterative ranking from pair wise comparisons |
| url | https://hdl.handle.net/1721.1/137118.2 |
| work_keys_str_mv | AT negahbansahandn iterativerankingfrompairwisecomparisons AT ohsewoong iterativerankingfrompairwisecomparisons AT shahdevavrat iterativerankingfrompairwisecomparisons |