Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions

Rank aggregation from pairwise preferences has widespread applications in recommendation systems and information retrieval. Given the enormous economic and societal impact of these applications, and the consequent incentives for malicious players to manipulate ranking outcomes in their favor, making rank aggregation algorithms robust to adversarial manipulations in data is a crucial challenge. In this paper, we initiate the study of robustness in rank aggregation under the popular Bradley-Terry-Luce (BTL) model for pairwise comparisons. We consider a setting where pairwise comparisons are initially generated according to a BTL model, but a fraction of these comparisons are corrupted adversarially prior to being reported to us. We consider a strong contamination model, where an adversary having complete knowledge of the initial truthful data and the true BTL weights, can corrupt this data by inserting, deleting, or changing data points. The goal is to recover the true BTL weights given this corrupted data. We characterize the extent of corruption under which the true BTL weights are uniquely identifiable. We also provide a novel algorithm that provably filters out the adversarial corruption from data under reasonable conditions on data generation and corruption. We support our theory with experiments on both synthetic as well as real data, showing the resilience of our algorithm to a substantial degree of corruption and the vulnerability of existing approaches to even small amounts of corruption.