Aggregating Incomplete and Noisy Rankings

Aggregating a collection of (possibly noisy and incomplete) ranked preferences into a complete ranking over a set of alternatives is a fundamental and extensively studied problem with numerous applications. Ranking aggregation has received considerable research attention in several fields, for decades and from virtually all possible aspects. Most relevant, Statistics investigates the properties of ranking distributions, which provide principled ways to generate noisy rankings from structural information about the alternatives' relative order. Best known among them are the distance-based model of Mallows [1957] and the parametric models of Thurstone [1927], Smith [1950], Bradley and Terry [1952], Plackett [1975] and Luce [2012]. Moreover, Machine Learning and Statistical Learning Theory aim to develop (statistically and computationally) efficient ways of retrieving the true ordering of the alternatives from noisy (and possibly incomplete) rankings (see e.g., [Xia, 2019] and the references therein). Virtually all previous work in the latter research direction assumes that the input is a collection of either complete rankings (chosen adversarially, e.g., Ailon et al. [2008], Kenyon-Mathieu and Schudy [2007], or drawn from an unknown ranking distribution, e.g., [Caragiannis et al., 2013, Busa-Fekete et al., 2019]), or outcomes of noisy pairwise comparisons (see e.g., [Feige et al., 1994, Mao et al., 2018a]). Due to a significant volume of relatively recent research, the computational and statistical complexity of determining the best ranking based on either complete rankings or pairwise comparisons are well understood. However, in most modern applications of ranking aggregation, the input consists of incomplete rankings of more than two alternatives. E.g., think of e-commerce or media streaming services, with a huge collection of alternatives, which generate personalized recommendations based on rankings aggregated by user ratings (see also Hajek et al. [2014]).