Médianes métriques et latticielles

URL des Cahiers : https://halshs.archives-ouvertes.fr/CAHIERS-MSECahiers de la MSE 2004.44 - Série Bleue - ISSN : 1624-0340In this paper, we present the notion of median useful for the aggregation of preferences and, more generally, in problems of consensus. After the introduction on the general notion of median, the first section studies the median relations of a profile of arbitrary or particular (tournaments, linear orders) relations. The computation of the medians of linear orders is difficult. The second section is devoted to this problem of which several equivalent formulations are presented. Then complexity results are specified, resolution methods are sketched and properties of median linear orders are given. The third section bears on the case where the computation of medians is easy, i.e. the case where the set of objects to aggregate can be endowed with an order structure, namely a structure of median semilattice.Dans ce texte, nous présentons les notions de médianes utiles pour l'agrégation des préférences et plus généralement pour les problèmes de consensus. Après une introduction sur les médianes en général, la première partie considère les relations médianes, définies métriquement, pour des profils de relations binaires soit quelconques, soit composés de tournois ou d'ordres totaux. Le calcul des médianes d'ordres totaux s'avère « difficile » et la deuxième partie traite de ce problème en en donnant d'abord diverses formulations, puis en précisant les résultats de complexité algorithmique, enfin en esquissant les méthodes de résolution et en donnant certaines propriétés des ordres médians. La troisième partie considère au contraire le cas où le calcul des médianes est « facile ». Ce cas est celui où l'ensemble des objets susceptibles d'être agrégés peut être muni d'une structure d'ordre qui en fait un demi-treillis à médianes, dans lequel les médianes s'obtiennent alors au moyen d'expressions algébriques