An algorithm for rank aggregation problem

摘要

The rank aggregation problem is an old problem which arises in many different settings. Let be the set of alternatives. Suppose δ1, δ2, … , δk are some individual preferences on A. The problem is to find a rank ordering δ such that is the minimum among all rank orderings, where d is a metric on the set of the rank orderings on A defined by Keen. We know that this problem is NP-hard. In this paper, we introduce an algorithm such that by using any rank ordering as an input, the output is a rank ordering which satisfies the extended Condorcet property. Also for a set of individual preferences, we introduce a rank ordering such that if we consider it as an input of the algorithm, we expect that the output is an optimal rank aggregation.