A computational study of the Kemeny rule for preference aggregation

Abstract

We consider from a computational perspective the problem of how to aggregate the ranking preferences of a number of alternatives by a number of different voters into a single consensus ranking, following the majority voting rule. Social welfare functions for aggregating preferences in this way have been widely studied since the time of Condorcet (1785). One drawback of majority voting procedures when three or more alternatives are being ranked is the presence of cycles in the majority preference relation. The Kemeny order is a social welfare function whicll has been designed to tackle the presence of such cycles. However computing a Kemeny order is known to be NP-hard. We develop a greedy heuristic and an exact branch and bound procedure for computing Kemeny orders. We present results of a computational study on these procedures.