A refinement algorithm for rank aggregation over crowdsourced comparison data

Extracting ranking from pairwise comparison data has been very popular these days especially due to the huge source of comparison data available in the Internet. One of the many ways to collect a large amount of data from ordinary users is crowd sourcing. One example is reCaptcha, which converts scanned text images into text by using human recognition capability of a huge number of people.With the comparison data, there have been many algorithms proposed to extract ranking. Since the problem of extracting ranking from comparison data is NP-hard, the proposed algorithms are not guaranteed to be optimal. Thus, in this paper, we propose a simple refinement algorithm called “PM” to make the ranking results of the existing algorithms better. Basically, we check every item in the ranking whether moving the item into other ranking position can reduce the errors of the ranking results. Our refinement algorithm can be used in conjunction with other algorithms. We show that our refinement algorithm can effectively reduce the errors of the original algorithms.