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

Olivier Hudry

Mathematical Social Sciences, 2012, vol. 64, issue 1, 2-10

Abstract: Given a finite set X and a collection Π, 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 Π. In the context of voting theory, X 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 m linear orders is NP-hard for any even m greater than or equal to 4 or for odd m large enough with respect to |X| (about |X|2). We then sharpen these complexity results when coping with other kinds of profiles Π for odd values of m. 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.

Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489611000461
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matsoc:v:64:y:2012:i:1:p:2-10

DOI: 10.1016/j.mathsocsci.2011.06.004

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().