Aggregating Incomplete and Noisy Rankings

Dimitris Fotakis, Alkis Kalavasis, Konstantinos Stavropoulos
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2278-2286, 2021.

Abstract

We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce a natural generalization of both the Mallows model, a popular model of ranking distributions, and the extensively studied model of ranking from pairwise comparisons. Our selective Mallows model outputs a noisy ranking on any given subset of alternatives, based on an underlying Mallows distribution. Assuming a sequence of subsets where each pair of alternatives appears frequently enough, we obtain strong asymptotically tight upper and lower bounds on the sample complexity of learning the underlying complete central ranking and the (identities and the) ranking of the top k alternatives from selective Mallows rankings. Moreover, building on the work of (Braverman and Mossel, 2009), we show how to efficiently compute the maximum likelihood complete ranking from selective Mallows rankings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-fotakis21a, title = { Aggregating Incomplete and Noisy Rankings }, author = {Fotakis, Dimitris and Kalavasis, Alkis and Stavropoulos, Konstantinos}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2278--2286}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/fotakis21a/fotakis21a.pdf}, url = {https://proceedings.mlr.press/v130/fotakis21a.html}, abstract = { We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce a natural generalization of both the Mallows model, a popular model of ranking distributions, and the extensively studied model of ranking from pairwise comparisons. Our selective Mallows model outputs a noisy ranking on any given subset of alternatives, based on an underlying Mallows distribution. Assuming a sequence of subsets where each pair of alternatives appears frequently enough, we obtain strong asymptotically tight upper and lower bounds on the sample complexity of learning the underlying complete central ranking and the (identities and the) ranking of the top k alternatives from selective Mallows rankings. Moreover, building on the work of (Braverman and Mossel, 2009), we show how to efficiently compute the maximum likelihood complete ranking from selective Mallows rankings. } }
Endnote
%0 Conference Paper %T Aggregating Incomplete and Noisy Rankings %A Dimitris Fotakis %A Alkis Kalavasis %A Konstantinos Stavropoulos %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-fotakis21a %I PMLR %P 2278--2286 %U https://proceedings.mlr.press/v130/fotakis21a.html %V 130 %X We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce a natural generalization of both the Mallows model, a popular model of ranking distributions, and the extensively studied model of ranking from pairwise comparisons. Our selective Mallows model outputs a noisy ranking on any given subset of alternatives, based on an underlying Mallows distribution. Assuming a sequence of subsets where each pair of alternatives appears frequently enough, we obtain strong asymptotically tight upper and lower bounds on the sample complexity of learning the underlying complete central ranking and the (identities and the) ranking of the top k alternatives from selective Mallows rankings. Moreover, building on the work of (Braverman and Mossel, 2009), we show how to efficiently compute the maximum likelihood complete ranking from selective Mallows rankings.
APA
Fotakis, D., Kalavasis, A. & Stavropoulos, K.. (2021). Aggregating Incomplete and Noisy Rankings . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2278-2286 Available from https://proceedings.mlr.press/v130/fotakis21a.html.

Related Material