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

Given a finite set XX and a collection ΠΠ, called a profile, of binary relations defined on XX (which can be linear orders, complete preorders, any relations, and so on), a relation RR is said to be median if it minimizes the total number of disagreements with respect to ΠΠ. In the context of voting theory, XX can be considered as a set of candidates and the relations of ΠΠ 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 ΠΠ 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 ΠΠ, 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 ΠΠ of mm linear orders is NP-hard for any even mm greater than or equal to 4 or for odd mm large enough with respect to |X||X| (about |X|2|X|2). We then sharpen these complexity results when coping with other kinds of profiles ΠΠ for odd values of mm. In particular, when the relations of ΠΠ and the median relation are complete preorders, we obtain the same results for the NP-hardness of Kemeny’s problem.

► We consider the aggregation of mm linear orders into median relations. ► Here, the median relations are complete preorders or weak orders. ► We discuss the values of mm for which this problem is NP-hard. ► We then sharpen the complexity results when coping with other kinds of preferences.