Ranking from Pairwise Comparisons
[Summary & Contributions] | [Relevant Publications]
Summary and Contributions
In many applications, ranging from sports tournaments to elections and from consumer studies to product feature design, one is given pairwise comparison data expressing users’ preferences between pairs of candidates or items at a time, and the goal is to aggregate these pairwise comparisons to construct a global ranking over the items, or to identify the top few items etc. Indeed, this problem is so ubiquitous that several different algorithms have been developed for it in different communities, including maximum likelihood estimation methods in statistics, spectral ranking methods in graph theory, noisy sorting methods in theoretical computer science, and many others. Our research group has developed a unified understanding of several diverse algorithms for ranking from pairwise comparisons, focusing in particular on understanding the conditions on various probabilistic models for pairwise comparison data under which these algorithms succeed or fail (see figure below); we have also designed new algorithms that recover a good ranking/identify a good set of items under broader conditions than previous algorithms, require less computation or adaptivity to achieve such recovery than previous algorithms, and/or are more robust to corruption in the data than previous algorithms.
Various classes of models for ranking
from pairwise comparisons studied and/or defined in our work.
Relevant Publications
- Arpit Agarwal, Shivani Agarwal, and Prathamesh Patil.
Stochastic dueling bandits with adversarial corruption.
In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), 2021.
[pdf] - Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna, and Prathamesh Patil.
Rank aggregation from pairwise comparisons in the presence of adversarial corruptions.
In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
[pdf] - Arpit Agarwal, Prathamesh Patil, and Shivani Agarwal.
Accelerated spectral ranking.
In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018.
[pdf] - Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna.
Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons.
In Proceedings of the 30th Annual Conference on Learning Theory (COLT), 2017.
[pdf] - Shivani Agarwal.
On ranking and choice models.
In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 2016.
Invited paper.
[pdf] - Siddartha Ramamohan, Arun Rajkumar, and Shivani Agarwal.
Dueling bandits: Beyond Condorcet winners to general tournament solutions.
In Advances in Neural Information Processing Systems (NIPS), 2016.
[pdf] - Arun Rajkumar and Shivani Agarwal.
When can we rank well from comparisons of O(n log n) non-actively chosen pairs?
In Proceedings of the 29th Annual Conference on Learning Theory (COLT), 2016.
[pdf] - Arun Rajkumar, Suprovat Ghoshal, Lek-Heng Lim and Shivani Agarwal.
Ranking from stochastic pairwise preferences: Recovering Condorcet winners and tournament solution sets at the top.
In Proceedings of the 32nd International Conference on Machine Learning (ICML), 2015.
[pdf] - Arun Rajkumar and Shivani Agarwal.
A statistical convergence perspective of algorithms for rank aggregation from pairwise data.
In Proceedings of the 31st International Conference on Machine Learning (ICML), 2014.
[pdf]
Shivani Agarwal 