Multiclass MinMax Rank Aggregation

Rankings, a special form of ordinal data, have received significant attention in the machine learning community as they arise in a number of important application domains, such as recommender systems, social voting and product placement platforms. Of particular importance are rankings of the form of linear orders (permutations) and partial rankings (weak orders), which are frequently obtained through conversion from ratings. One of the main processing tasks for rankings is rank aggregation, which often involves evaluating the median of a set of permutations or partial rankings under a suitably chosen distance function [2], [4], [7], [9], [11], [12], [16]. The median rank aggregation problem under the Kendall τ distance was introduced by Kemeny [11], and was proved to be NPhard by Bartholdi et al. [4]. A number of approximation algorithms for the problem have been described in [2], mostly pertaining to permutations; a corresponding PTAS (polynomial time approximation scheme) was proposed in [12]. In the context of partial ranking aggregation, known solutions include the results of [1], [10]. Median aggregation under other distance functions has received less attention, one notable exception being the Spearman rank aggregation problem [7], which is known to provide a constant approximation for Kendall τ aggregation using a polynomial time algorithm based on weighted bipartite matching [9]. We propose to investigate a broad new family of rank aggregation problems in which the median is replaced by a minmax type of function and where the rankings are grouped in classes.