On the computation of median linear orders, of median complete preorders and of median weak orders

Given a finite set X and a collection Pi, called a profile, of binary relations defined on X (which can be linear orders, complete preorders, any relations, and so on), a relation R is said to be median if it minimizes the total number of disagreements with respect to Pi. In the context of voting theory, X can be considered as a set of candidates and the relations of Pi as the preferences of voters, while a median relation can be adopted as the collective preference with respect to the voters' opinions. If the relations of Pi are tournaments (which includes linear orders), then there always exists a median complete preorder (i.e. a median complete and transitive relation) which is in fact a linear order. Moreover, if there is no tie when aggregating the tournaments of Pi, then all the median complete preorders are linear orders. We show the same when the median is assumed to be a weak order (a weak order being the asymmetric part of a complete preorder). We then deduce from this that the computation of a median complete preorder or of a median weak order of a profile Pi of in linear orders is NP-hard for any even m greater than or equal to 4 or for odd m large enough with respect to vertical bar X vertical bar (about vertical bar X vertical bar(2)). We then sharpen these complexity results when coping with other kinds of profiles Pi for odd values of m. In particular, when the relations of Pi and the median relation are complete preorders, we obtain the same results for the NP-hardness of Kemeny's problem. (C) 2012 Published by Elsevier B.V.