On the computation of median linear orders, of median complete preorders and of median weak orders
- 作者：Olivier Hudry hudry@enst.fr hudry@infres.enst.fr
- 刊名：Mathematical Social Sciences
- 出版年：2012
- 期刊代码：41_01654896
- 类别：mt
- 出版时间：July, 2012
- 卷：64
- 期：1
- 页码：2-10
- 文件大小：496 K
摘要
Given a finite set and a collection , called a profile, of binary relations defined on (which can be linear orders, complete preorders, any relations, and so on), a relation is said to be median if it minimizes the total number of disagreements with respect to . In the context of voting theory, 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 linear orders is NP-hard for any even greater than or equal to 4 or for odd large enough with respect to (about ). We then sharpen these complexity results when coping with other kinds of profiles for odd values of . In particular, when the relations of and the median relation are complete preorders, we obtain the same results for the NP-hardness of Kemeny鈥檚 problem.