# Médianes métriques et latticielles

Olivier Hudry, Bruno Leclerc, Bernard Monjardet, Jean-Pierre Barthélemy

► To cite this version:

Olivier Hudry, Bruno Leclerc, Bernard Monjardet, Jean-Pierre Barthélemy. Médianes métriques et latticielles. 2004. halshs-03322636

HAL Id: halshs-03322636

https://shs.hal.science/halshs-03322636v1

Submitted on 19 Aug 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

UNIVERSITÉ PARIS 1
-PANTHÉON - SORBONNE -

Cahiers

de la
MSE

CERMSEM

UMR CNRS 8095

Médianes métriques et latticielles

Olivier HUDRY

Bruno LECLERC

Bernard MONJARDET

Jean-Pierre BARTHÉLEMY

2004.44

<figure><img src="image_3.png" /></figure>

CENTRE NATIONAL
DE LA RECHERCHE
SCIENTIFIQUE

Maison des Sciences Économiques, 106-112 boulevard de L'Hôpital, 75647 Paris Cedex 13
ISSN : 1624-0340
# Médianes métriques et latticielles

Olivier Hudry(1), Bruno Leclerc(2), Bernard Monjardet(3), Jean-Pierre Barthélemy(4)

25 avril 2004

## Résumé

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.

**Mots-clés** : consensus, demi-treillis à médianes, graphe pondéré, ordre médian, relation médiane, tournoi, treillis.

## Abstract

In this paper we present the notions 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 strucure, namely a structure of median semilattice.

**Key words:** consensus, lattice, median, median order, median semilattice, tournament, weighted graph.

AMS subject classification numbers: 06, 91.

(1) Département Informatique et Réseaux, ENST, 46, rue Barrault, 75634 Paris cedex 13 et CERMSEM, hudry@infres.enst.fr

(2) CAMS, EHESS, 54 bd Raspail, 75270 Paris Cedex 06, leclerc@ehess.fr

(3) CERMSEM, Université Paris I, Maison des Sciences Économiques, 106-112, bd de l'Hôpital 75647 Paris Cedex 13, monjarde@univ-paris1.fr

(4) LIASC, ENST de Bretagne, BP 832, 29285 BREST Cedex et CAMS, jp.barthelemy@enst-bretagne.fr
# Médianes métriques et latticielles<fnref n="1" />

## 2.1. Introduction

Cet article concerne les problèmes d'agrégation des préférences qui se présentent dans les problématiques du choix collectif ou de la décision multicritère. Plus précisément, il porte sur la théorie de la médiane pour des relations binaires, ses extensions abstraites (aux treillis) et ses applications aux problèmes d'agrégation. Dans cette introduction, nous considérons d'abord la notion de médiane en général, puis les médianes de relations binaires et enfin les médianes latticielles.

### 2.1.1. Médianes, en général

La notion de médiane provient d'abord de la géométrie. Nous avons tous affronté, en nos lycéennes enfances, des segments de droite particuliers dans les triangles. Une bissectrice coupe un angle en deux angles égaux et s'en vient choir sur le côté opposé. Une hauteur, partant d'un sommet, aborde le côté opposé selon un angle droit. Enfin, une médiane, issue d'un sommet, partage le côté opposé en deux parties égales. C'est précisément sur le partage qu'est fondée la médiane. La médiane d'une série statistique ordonnée la divise en deux parties égales. Dans leur fameux *Dictionnaire de statistique*, Kendall et Buckland [KEN 57] distinguent « médiane » et « centre médian » en écrivant que, « selon la tradition italienne », le centre médian est un point dont la somme des distances à des points d'un ensemble donné est minimum. En fait ces deux notions coïncident, comme l'avait déjà noté Laplace [LAP 74]. Les médianes mettent donc en regard deux structures : une structure

<footnote n="1">¹ Article rédigé par Olivier HUDRY, Bruno LECLERC, Bernard MONJARDET et Jean-Pierre BARTHELEMY.</footnote>
ordinale (ici, un ordre total ; plus généralement, on parlera de médianes latticielles ou algébriques) et une structure métrique (on parlera alors de médiane métrique). Il est piquant de noter que si la médiane est de nature métrique, elle n'est pas de nature géométrique : l'intersection des trois médianes d'un triangle est son centre de gravité et non la médiane (métrique) de ses trois sommets. Par ailleurs, la médiane de points alignés ne dépend que de la succession de ces points et non des longueurs des intervalles les séparant.

### 2.1.2. Médianes de relations binaires

Le problème de l'agrégation de relations binaires (en l'occurrence de préordres totaux) a été posé formellement par Arrow [ARR 51]. Très rapidement, la notion de médiane venait s'inscrire dans la lignée de ce travail, et selon les deux dimensions que nous avons mentionnées plus haut : ordinale et métrique. Relativement à la première, Guilbaud [GUI 52] faisait remonter les questions arrowiennes à la théorie des votes développée à la fin du 18e siècle par Condorcet et quelques autres. En particulier, il soulignait que la règle majoritaire n'était généralement pas applicable, et d'ajouter : « L'étude analytique du paradoxe de Condorcet nous conduira d'ailleurs à entrevoir comment on peut construire une médiane dans des structures partiellement ordonnées de types variés ». Condorcet (et quelques autres, à sa suite), en effet, notant que les modes de scrutin usuels pouvaient conduire à l'élection d'un candidat qui serait battu à la majorité par un autre, proposait de décomposer ce scrutin en duels (i. e. d'opposer les candidats deux à deux) et à déclarer vainqueur un candidat battant tous les autres à la majorité. Malheureusement, il s'aperçut que ce mode de scrutin soulevait d'autres difficultés, illustrées plus loin (voir la partie 2.2.4).

À la fin des années cinquante, pour pallier le résultat d'impossibilité d'Arrow, Kemeny [KEM 59] introduisait, pour les ordres totaux, la notion de médiane métrique, fondée sur la distance de la différence symétrique, distance comptant le nombre de « désaccords » entre deux relations. La justification donnée par Kemeny reposait sur une caractérisation axiomatique de ladite distance. Depuis ces travaux pionniers, le thème de la médiane de relations binaires a pris force et vigueur. On trouvera dans [BAR 81] un bilan de la déjà foisonnante littérature consacrée à ce sujet. Sur un plan algorithmique, notons enfin que, à l'exception de certains cas assez évidents, la recherche d'une médiane (au sens de Kemeny, et pour des relations binaires de types variés) conduit généralement à des problèmes NP-difficiles [HUD 89].
2.1.3. Médianes latticielles

Comme souvent lorsqu'il s'agit de questions mathématiques, la compréhension
d'un lien profond entre deux approches s'obtient à l'aide d'une troisième : une
approche abstraite dans laquelle on peut les plonger. Ici, c'est le modèle abstrait des
treillis (et demi-treillis) qui relie les approches ordinales (Guilbaud) et métriques
(Kemeny). Dans deux articles séminaux, Barbut ([BAR 61] et [BAR 67]) montrait
que le résultat de Laplace, sur l'équivalence des médianes ordinales et métriques, se
généralise aux treillis distributifs et fait explicitement le lien, non seulement avec la
règle majoritaire de Condorcet, mais aussi avec la statistique ordinale développée par
Kendall [KEN 38] (le fameux coefficient τ de Kendall n'est autre qu'une
normalisation entre -1 et +1 de la distance de la différence symétrique — utilisée,
rappelons-le, par Kemeny). Les résultats de Barbut ont été, ensuite, systématisés par
Monjardet qui a introduit, entre autres, la notion d'intervalle médian [MON 80].
Deux extensions ont alors été développées :

– extension à d'autres structures ordinales, en particulier aux treillis (et demi-treillis) modulaires ;

– étude des médianes dans les arbres (l'initiateur est, sans conteste, Camille Jordan [JOR 69]).

Toute proposition vraie pour les arbres et les treillis distributifs a toutes les chances de l'être aussi pour la structure abstraite plus générale de demi-treillis à médianes (considérée précédemment par Sholander [SHO 54] et Avann [AVA 61]. C'est ainsi que les résultats de Barbut pour les treillis distributifs, et de Zelinka [ZEL 68] et Slater [SLA 78] pour les arbres, ont été étendus aux demi-treillis à médianes par Bandelt et Barthélemy [BAN 84].

Le thème abordé dans cet article est très prolifique. Environ deux cents références
décoraient l'article de Barthélemy et Monjardet [BAR 81], écrit il y a plus de vingt
ans ; leur nombre a sans doute plus que triplé (en particulier le champ des médianes
a été fort envahi par la classification automatique). Nous avons donc dû faire des
choix drastiques. Du côté relationnel, nous nous sommes restreints essentiellement
aux relations quelconques, aux tournois et aux ordres totaux (d'autres relations
interviennent cependant dans la dernière partie à titre d'application de la notion de
médiane latticielle). Du côté métrique, nous avons mis l'accent sur la distance de la
différence symétrique et son extension aux demi-treillis. À côté, il y aurait eu des
aspects « géodésiques » (par exemple, dans le treillis permutoèdre) qui relèvent
autant de la théorie des graphes que de celle des ensembles ordonnés. Du côté
latticiel, nous avons mis l'accent sur la structure où s'expriment naturellement les
médianes, c'est-à-dire les demi-treillis à médianes. Cela ne doit pas faire oublier que
des résultats parallèles ou plus généraux (demi-treillis semi-modulaires, voire
quelconques) ont été obtenus plus ou moins récemment.
Outre cette introduction (première partie), cette contribution comprend trois parties. La partie 2.2. dresse le décor en donnant diverses définitions qui seront utilisées dans la suite et en étudiant les médianes pour les relations binaires quelconques, puis pour les tournois. La partie 2.3. porte sur les ordres (totaux) médians et particulièrement sur le problème de leur calcul effectif. Tout en reprenant les aspects algébriques de la partie 2.2., elle développe diverses questions relevant de l'optimisation combinatoire. La dernière partie traite des médianes latticielles. On y remarque d'abord que plusieurs ensembles de relations binaires constituent, une fois convenablement ordonnés, des treillis ou demi-treillis. On fait alors une transition des relations binaires aux treillis, incluant une extension de la distance de la différence symétrique et donc de la médiane. L'accent est ensuite naturellement mis sur les demi-treillis à médianes, dont on a dit plus haut qu'ils constituent le cadre pour l'unification de la plupart des résultats « positifs » de la littérature. Cette partie revient aussi sur les usages en mettant en évidence comment cette approche latticielle abstraite vient s'instancier pour rendre compte de résultats sur des relations binaires de type particulier ou sur d'autres modèles de préférence (fonctions de choix).

## 2.2. Relations médianes : généralités

### 2.2.1. Le modèle

On considère dans cet article :

- un ensemble fini $V = \{1, ..., i, ..., v\}$ de $v$ éléments appelés dans la suite des votants, mais qui peuvent aussi bien représenter des « agents », des « critères », etc.

- un ensemble fini $X = \{x, y, z, ...\}$ de $n$ éléments appelés dans la suite des candidats, mais qui peuvent aussi bien représenter des « décisions », des « objets », etc.

Chaque votant est supposé comparer les candidats deux à deux. Il exprime ainsi ses préférences entre les candidats au moyen d'une relation binaire $R$ définie sur $X$. On fait l'hypothèse que $R$ appartient à un ensemble donné $\mathcal{D}$ de relations binaires définies sur $X$. Autrement dit, si $R = P(X^2)$ désigne l'ensemble des parties de $X^2$, c'est-à-dire l'ensemble des relations binaires définies sur $X$, on a $\mathcal{D} \subseteq R$. La donnée pour chaque votant $i$ de sa relation de préférence $R_i$ définit ce qu'on appelle un *profil de préférences individuelles*. On note un tel profil $\Pi = (R_1, ..., R_i, ..., R_v)$. L'ensemble de tous les profils de préférences possibles est donc $\mathcal{D}^v$.

À chaque profil possible de préférences individuelles, on cherche à associer une relation de préférence « collective » représentant la préférence « agrégée », ou « consensus », des préférences individuelles. On demandera souvent à cette préférence collective soit d'être du même type que les préférences individuelles, i. e.
d'appartenir à $\mathcal{D}$, soit plus généralement d'appartenir à un ensemble $\mathcal{M}$ (pour « modèle ») de relations contenant $\mathcal{D}$. Nous aurons donc en général $\mathcal{D} \subseteq \mathcal{M} \subseteq \mathbb{R}$. Classiquement, on appelle *procédure d'agrégation* une application de $\mathcal{D}^v$ dans $\mathcal{M}$. Dans la suite, nous aurons besoin d'élargir cette définition en considérant par exemple des applications de $\mathcal{D}^v$ dans $P^*(\mathcal{M})$, où $P^*(\mathcal{M})$ désigne l'ensemble des parties non vides de $\mathcal{M}$.

On désire aussi que la procédure utilisée pour agréger les préférences vérifie de « bonnes » propriétés. Par exemple, si les votants sont unanimes à préférer le candidat $x$ au candidat $y$, il faut que dans la préférence collective $x$ soit aussi préféré à $y$. La recherche de bonnes procédures d'agrégation se heurte à des obstacles (comme l'effet Condorcet évoqué à la section 2.3. ou le théorème d'Arrow [ARR 51] ; on pourra aussi consulter sur ces sujets les articles constituant le numéro 163 de *Mathématiques et Sciences humaines* [MSH 03]) qui conduisent à être moins ambitieux sur les procédures d'agrégation considérées.

Le type de procédures d'agrégation que nous allons utiliser dans cet article appartient à la vaste classe de ce qui est appelé les *procédures métriques d'agrégation des préférences*. Elles sont fondées sur une idée très naturelle que l'on retrouve dans des contextes variés (par exemple en analyse des données). On va rechercher la préférence collective « la plus proche » — en un sens à préciser — des préférences individuelles du profil considéré. Pour définir cette notion de proximité, on commence par se donner une *distance* $d$ sur l'ensemble $\mathcal{M}$ des relations collectives possibles, c'est-à-dire à en faire un espace métrique $(\mathcal{M}, d)$. En utilisant cette distance, on définit ensuite une mesure d'éloignement (cf. [BAR 81]) entre un profil $\Pi$ de préférences individuelles et une relation $R$ quelconque de $\mathcal{M}$. Les relations de préférence collective associées au profil $\Pi$ sont alors les relations de $\mathcal{M}$ minimisant cet éloignement.

### 2.2.2. La procédure médiane

Une distance $d$ étant donnée sur $\mathcal{M}$, la procédure médiane est la procédure métrique où l'éloignement $E(\Pi, R)$ entre un profil $\Pi = (R_1, ..., R_i, ..., R_v)$ de préférences individuelles et une relation $R$ quelconque de $\mathcal{M}$ est obtenu en sommant les distances des différentes relations du profil considéré à la relation $R$ :

$$E(\Pi, R) = \sum_{i=1}^{v} d(R_i, R).$$
DEFINITION 2.1.— Soit $\Pi \in \mathcal{D}^v$ un profil de préférences individuelles définies sur $X$ et soit $\mathcal{M} \subseteq \mathcal{R}$. Une $\mathcal{M}$-médiane de $\Pi$ est une relation de $\mathcal{M}$ solution du problème d'optimisation suivant : minimiser $E(\Pi, \mathcal{M})$.

$\mathcal{M} \in \mathcal{M}$

On notera que l'ensemble $\mathcal{M}$ étant fini, il existe toujours au moins une
$\mathcal{M}$-médiane d'un profil, et qu'il peut en exister plusieurs. On notera Méd$_{\mathcal{M}}(\Pi)$
l'ensemble des $\mathcal{M}$-médianes du profil $\Pi$. Évidemment, les $\mathcal{M}$-médianes d'un profil
vont dépendre de la distance $d$ choisie sur $\mathcal{M}$. Dans la suite, nous nous limiterons à
la distance la plus naturelle et la plus utilisée pour un ensemble de relations binaires,
à savoir la distance de la différence symétrique. Rappelons la définition de cette
distance, que nous notons $\delta$ (Δ désignant la différence symétrique ensembliste) ;
pour deux relations binaires $R$ et $R'$ définies sur $X$, on a :

$$
\delta(R, R') = |R \Delta R'| = |R \cup R'| - |R \cap R'| = |R \setminus R'| + |R' \setminus R|,
$$

ce qui peut aussi s'écrire :

$$
\delta(R, R') = \left| \{ (x, y) : [(x, y) \in R \text{ et } (x, y) \notin R'] \text{ ou } [(x, y) \notin R \text{ et } (x, y) \in R'] \} \right|.
$$

Autrement dit, la distance de la différence symétrique entre $R$ et $R'$ est le nombre
de couples de $X$ appartenant à l'une des relations et non à l'autre (elle mesure donc le
nombre de leurs « désaccords »).

L'éloignement d'un profil $\Pi = (R_1, ..., R_i, ..., R_v)$ à une relation $R$ est alors,
pour la distance $\delta$ :

$$
E(\Pi, R) = \sum_{i=1}^{v} \delta(R_i, R).
$$

2.2.3. Les $\mathcal{R}$-médianes d'un profil de relations

Nous commençons par considérer le cas où les préférences individuelles des
votants peuvent être des relations binaires arbitraires, c'est-à-dire le cas pour lequel
on a $\mathcal{D} = \mathcal{R}$. Bien que peu réaliste pour le cas des préférences, ce cas peut se
présenter dans d'autres contextes et les résultats obtenus sur les $\mathcal{R}$-médianes restent
valables pour des relations non quelconques. Nous avons besoin de définir certains
paramètres associés au profil $\Pi = (R_1, ..., R_i, ..., R_v)$. On pose :

$$
V_{\pi}(x, y) = \{i \in V : x R_i y\},
$$

$$
V_{\pi}^{c}(x, y) = \{i \in V : (x, y) \notin R_{i}\},
$$
## 8 Concepts et méthodes pour l'aide à la décision

$$ 
\begin{align*}
v_{\pi}(x, y) &= |V_{\pi}(x, y)| = |\{i \in V : x R_i y\}|, \\
v_{\pi}^{c}(x, y) &= |V_{\pi}^{c}(x, y)| = |\{i \in V : (x, y) \notin R_i\}|, \\
w_{\pi}(x, y) &= v_{\pi}(x, y) - v_{\pi}^{c}(x, y).
\end{align*}
$$

Ainsi $V_\pi(x, y)$ désigne l'ensemble des votants préférant le candidat $x$ au candidat $y$, $v_\pi(x, y)$ le nombre de ces votants et $v_\pi^c(x, y)$ le nombre des votants ne préférant pas $x$ à $y$ (ce qui, en général, ne veut pas dire qu'ils préfèrent $y$ à $x$). On a évidemment les égalités $v_\pi(x, y) + v_\pi^c(x, y) = v$ et $w_\pi(x, y) = 2v_\pi(x, y) - v$. Lorsqu'il n'y a pas d'ambiguïté, c'est-à-dire pratiquement toujours, on omet l'indice $\pi$ dans les notations précédentes (par exemple, la notation $V_\pi(x, y)$ devient $V(x, y)$).

Le premier résultat consiste à exprimer l'éloignement d'un profil à une relation $R$ arbitraire au moyen des paramètres précédents, ainsi que les modifications de cet éloignement si l'on retire ou ajoute un couple à $R$.

LEMME 2.2.– Pour $\Pi = (R_1, ..., R_i, ..., R_v) \in \mathcal{R}^v$ et $R \in \mathcal{R}$, on a :

$$ (a) E(\Pi, R) = \sum_{(x,y) \in R} v^c(x,y) + \sum_{(x,y) \notin R} v(x,y); $$

$$ (b) E(\Pi, R) = \sum_{i=1}^{v} |R_i| - \sum_{(x,y) \in R} w(x,y); $$

$$ (c) \text{ si } (x, y) \in R, E(\Pi, R \setminus \{(x, y)\}) = E(\Pi, R) + w(x, y); $$

$$ (d) \text{ si } (x, y) \notin R, E(\Pi, R \cup \{(x, y)\}) = E(\Pi, R) - w(x, y). $$

Preuve.

Montrons d'abord (a). Par définition de $E(\Pi, R)$, on a :

$$ E(\Pi, R) = \sum_{i=1}^{v} \delta(R_i, R) = \sum_{i=1}^{v} |R_i \Delta R|. $$

Introduisons la fonction caractéristique de $R_i \Delta R$, $\delta_i$, définie par :

$$ \forall (x,y) \in X^2, \delta_i(x, y) = 1 \text{ si } (x, y) \in R_i \Delta R \text{ et } \delta_i(x, y) = 0 \text{ sinon.} $$

Il vient alors :

$$ E(\Pi, R) = \sum_{i=1}^{v} \sum_{(x,y) \in X^2} \delta_i(x,y) = \sum_{(x,y) \in X^2} \sum_{i=1}^{v} \delta_i(x,y). $$
En partitionnant $X^2$ en $R$ et son complémentaire, on obtient :

$$
\begin{align*}
E(\Pi, R) &= \sum_{(x,y) \in R} \sum_{i=1}^{v} \delta_i(x,y) + \sum_{(x,y) \notin R} \sum_{i=1}^{v} \delta_i(x,y) \\
&= \sum_{(x,y) \in R} v^c(x,y) + \sum_{(x,y) \notin R} v(x,y),
\end{align*}
$$

ce qui établit la première relation. En ajoutant et en retranchant $\sum_{(x,y) \in R} v(x,y)$, on obtient (b) :

$$
\begin{align*}
E(\Pi, R) &= \sum_{(x,y) \in R} v(x,y) + \sum_{(x,y) \notin R} v(x,y) - \left[ \sum_{(x,y) \in R} v(x,y) - \sum_{(x,y) \in R} v^c(x,y) \right] \\
&= \sum_{(x,y) \in X^2} v(x,y) - \sum_{(x,y) \in R} w(x,y) \\
&= \sum_{i=1}^{v} |R_i| - \sum_{(x,y) \in R} w(x,y).
\end{align*}
$$

Les relations (c) et (d) se déduisent immédiatement de (b). $\square$

<figure><img src="image_4.png" /></figure>

Dans les cas simples, les relations médianes d'un profil sont liées aux relations « majoritaires » associées au profil, relations que nous allons définir maintenant après avoir introduit quelques notations.

Pour $\Pi \in \mathbb{R}^v$ et pour tout entier $\sigma$, nous posons :

$$
R(\Pi, \sigma) = \{(x, y) \in X^2 : v(x, y) \geq \sigma\}.
$$

Là aussi cette relation sera le plus souvent notée simplement $R(\sigma)$. D'autre part si $r$
est un réel, la notation $\lceil r \rceil$ (respectivement $\lfloor r \rfloor$) désigne la partie entière par excès
(respectivement par défaut) de $r$. Finalement nous posons $\alpha = \lceil (n+1)/2 \rceil$ et
$\beta = \lfloor (n+1)/2 \rfloor$ (donc, si $n = 2p + 1$, $\alpha = \beta = p + 1$ ; si $n = 2p$, $\alpha = p + 1$ et
$\beta = p$).

DEFINITION 2.3.— Pour $\Pi \in \mathbb{R}^v$, la relation majoritaire stricte associée au profil $\Pi$
est la relation

$$
R(\alpha) = \{(x, y) \in X^2 : v(x, y) \geq \alpha = \lceil (n+1)/2 \rceil\}
$$

et la relation majoritaire associée au profil Π est la relation
$$
R(\beta) = \{(x, y) \in X^2 : v(x, y) \geq \beta = \lfloor (n+1)/2 \rfloor\}.
$$

Un candidat $x$ est donc préféré à $y$ dans la relation majoritaire stricte
(respectivement dans la relation majoritaire) si le nombre de votants préférant $x$ à $y$
dans le profil $\Pi$ est strictement supérieur (respectivement supérieur ou égal) à la
moitié du nombre des votants. Évidemment, ces deux relations sont identiques si le
nombre de votants est impair. On remarque aussi les égalités

$$
R(\alpha) = \{(x, y) \in X^2 : v(x, y) > v^c(x, y)\} = \{(x, y) \in X^2 : w(x, y) > 0\}
$$

et $R(\beta) = \{(x, y) \in X^2 : v(x, y) \geq v^c(x, y)\} = \{(x, y) \in X^2 : w(x, y) \geq 0\}$.

L'ensemble $R(\beta) \setminus R(\alpha) = \{(x, y) \in X^2 : w(x, y) = 0\}$ est l'ensemble des couples $(x, y)$ de candidats pour lesquels il y a autant de votants préférant $x$ à $y$ que de votants ne préférant pas $x$ à $y$. Dans le cas où, pour tout votant, $x$ n'est pas préféré à $y$ si et seulement si $y$ est préféré à $x$, $R(\beta) \setminus R(\alpha)$ est l'ensemble des couples de candidats ex æquo, c'est-à-dire des candidats pour lesquels les nombres de votants préférant l'un des candidats à l'autre sont égaux.

Après avoir rappelé la notion d'intervalle, nous allons pouvoir maintenant énoncer le premier résultat concernant les médianes (arbitraires) d'un profil de relations (arbitraires). Dans le treillis booléen ($\mathcal{R}$, $\subseteq$) de toutes les relations binaires définies sur $X$, l'intervalle $[S, T]$ défini par deux relations $S$ et $T$ vérifiant $S \subseteq T$ est l'ensemble $\{R \in \mathcal{R} : S \subseteq R \subseteq T\}$.

PROPOSITION 2.4.— Soit $\Pi \in \mathcal{R}^v$ un profil de relations binaires sur $X$. On a :

$$
\text{Méd}_{\mathcal{R}}(\Pi) = [R(\alpha), R(\beta)].
$$

Le nombre de $\mathcal{R}$-médianes de $\Pi$ vaut $2^{\lceil R(\beta) \rceil \cdot \lceil R(\alpha) \rceil}$. Si on a $R(\beta) \setminus R(\alpha) = \emptyset$ (en particulier si le nombre de votants est impair), alors $\Pi$ admet une médiane unique.

Preuve.

Soit $R$ une $\mathcal{R}$-médiane de $\Pi$. Si l'inclusion $R(\alpha) \subseteq R$ n'est pas vérifiée, il existe $(x, y) \in X^2$ avec $w(x, y) > 0$ et $(x, y) \notin R$. Par le lemme 2.2. (d), on a :

$$
E(\Pi, R \cup \{(x, y)\}) = E(\Pi, R) - w(x, y) < E(\Pi, R),
$$

ce qui est impossible, puisque $R$ est une médiane de $\Pi$. De même, si l'inclusion $R \subseteq R(\beta)$ n'est pas vérifiée, il existe $(x, y) \in X^2$ avec $(x, y) \in R$ et $w(x, y) < 0$. Par le lemme 2.2. (c), on a :

$$
E(\Pi, R \setminus \{(x, y)\}) = E(\Pi, R) + w(x, y),
$$
de nouveau une contradiction.

Donc les $\mathcal{R}$-médianes de $\Pi$ sont dans l'intervalle $[R(\alpha), R(\beta)]$ et, puisque toutes les relations $R$ de cet intervalle ont le même éloignement au profil (autrement dit, $E(\Pi, R) = E(\Pi, R(\alpha)) = \sum_{i=1}^{v} |R_i| - \sum_{w(x,y)>0} w(x, y)$), on obtient ainsi toutes les $\mathcal{R}$-médianes de $\Pi$.

Le nombre de $\mathcal{R}$-médianes en découle immédiatement : on peut prendre ou non chaque élément de $R(\beta) \setminus R(\alpha)$ pour constituer une $\mathcal{R}$-médiane de $\Pi$. $\square$

Les $\mathcal{R}$-médianes de $\Pi$ sont donc toutes les relations comprises entre les relations majoritaires de $\Pi$. Elles forment un intervalle $[R(\alpha), R(\beta)]$ — appelé *intervalle médian* — du treillis booléen ($\mathcal{R}, \subseteq$) de toutes les relations binaires définies sur $X$. La dernière section de cet article reviendra sur les liens entre médianes et treillis, mais l'on peut tout de suite remarquer que les relations majoritaires s'obtiennent au moyen des opérations de ce treillis, i. e. au moyen de l'union et de l'intersection. En effet, on a

$$R(\alpha) = \bigcup_{\substack{W \subseteq V \\ \text{et } |W| \ge \alpha}} \left( \bigwedge_{i \in W} R_i \right) \quad \text{et} \quad R(\beta) = \bigcup_{\substack{W \subseteq V \\ \text{et } |W| \ge \beta}} \left( \bigwedge_{i \in W} R_i \right).$$

### 2.2.4. Les $\mathcal{M}$-médianes d'un profil de relations

Nous considérons maintenant le cas où les relations de préférences collectives associées au profil $\Pi$ ne sont plus des relations quelconques, mais doivent appartenir à un ensemble $\mathcal{M}$ de relations binaires, c'est-à-dire doivent être des $\mathcal{M}$-médianes de $\Pi$. On peut toujours considérer les $\mathcal{R}$-médianes de $\Pi$, c'est-à-dire l'intervalle médian $[R(\alpha), R(\beta)]$, mais cet intervalle peut très bien ne contenir aucune relation appartenant à $\mathcal{M}$. Par exemple, si $\mathcal{D}$ et $\mathcal{M}$ sont tous les deux égaux à l'ensemble des ordres totaux sur trois candidats $x, y$ et $z$, il est facile de s'assurer que la $\mathcal{R}$-médiale du profil formé des trois ordres totaux $x > y > z$, $y > z > x$ et $z > x > y$ est la relation réflexive $R$ définie par $x \ R \ y$, $y \ R \ z$ et $z \ R \ x$, qui n'est pas un ordre total (c'est un circuit !). En fait on a le résultat suivant qui, bien qu'évident, n'est pas sans intérêt :

**PROPOSITION 2.5.** — Soient $\Pi \in \mathbb{R}^v$ et $\mathcal{M} \subseteq \mathbb{R}$. Si $\mathcal{M} \cap \text{Méd}_{\mathbb{R}}(\Pi) \neq \emptyset$, alors $\text{Méd}_{\mathcal{M}}(\Pi) = \mathcal{M} \cap \text{Méd}_{\mathbb{R}}(\Pi)$.
Preuve.

En effet, s'il existe une relation de $\mathcal{M}$ dans l'intervalle médian du profil $\Pi$, alors cette relation (ainsi que toutes les autres relations de $\mathcal{M}$ appartenant à cet intervalle) minimise l'éloignement du profil à n'importe quelle relation de $\mathcal{M}$, puisqu'elle le minimise sur l'ensemble de toutes les relations binaires. $\square$

### 2.2.5. Les $\mathcal{T}'$-médianes d'un profil de tournois

Nous restreignons maintenant les relations modélisant les préférences individuelles ou collectives des votants en supposant qu'il s'agit de relations de tournois. Un tournoi $T$ sur $X$ est une relation totale (ou complète, c'est-à-dire que si on n'a pas $xRy$, alors on doit avoir $yRx$) et antisymétrique ($xRy$ et $yRx$ impliquent $x = y$). Un tournoi qui est de plus transitif ($xRy$ et $yRz$ impliquent $xRz$) est un ordre total, relation constituant un modèle classique de préférence transitive. Mais des relations de préférence modélisées par des tournois non transitifs apparaissent souvent, par exemple lorsqu'on demande à un votant d'indiquer pour chaque paire de candidats celui qu'il préfère. Nous noterons $\mathcal{T}'$ (respectivement $\mathcal{L}'$) l'ensemble des tournois (respectivement des ordres totaux) définis sur $X$. Il résulte immédiatement des propriétés des tournois que, pour un profil $\Pi = (T_1, ..., T_i, ..., T_v) \in \mathcal{T}'^v$ (et en particulier pour $\Pi \in \mathcal{L}'^v$), on a, pour tout $x$ et tout $y$ :

$$v_{\pi}^{c}(x, y) = v_{\pi}(y, x) \text{ si } x \neq y ; \quad v_{\pi}^{c}(x, x) = 0 ;$$

$$w_{\pi}(x, y) = 2v_{\pi}(x, y) - v ; \quad w_{\pi}(x, x) = v ;$$

$$v_{\pi}(x, y) + v_{\pi}(y, x) = v \text{ si } x \neq y ; \quad v_{\pi}(x, y) + v_{\pi}(y, x) = 2v \text{ si } x = y.$$

Comme précédemment, lorsqu'il n'y a pas d'ambiguïté (c'est-à-dire pratiquement toujours), on omet l'indice dans les notations précédentes. L'éloignement d'un tournoi $T$ à un profil de tournois $\Pi = (T_1, ..., T_i, ..., T_v)$ est alors donné par :

$$E(\Pi, T) = \sum_{(x,y) \in T} v(y,x) + \sum_{(x,y) \notin T} v(x,y) = \frac{v \cdot n(n+1)}{2} - \sum_{(x,y) \in T} w(x,y).$$

En utilisant la proposition 2.5. et la formule précédente, on trouve facilement tous les tournois médians d'un profil de tournois, c'est-à-dire les tournois $T$ minimisant $E(\Pi, T)$ dans l'ensemble $\mathcal{T}'$ des tournois définis sur $X$.

**PROPOSITION 2.6.** — Soit $\Pi \in \mathcal{T}'^v$ un profil de tournois. On a alors $\text{Méd}_{\mathcal{T}'}(\Pi) = \mathcal{T}' \cap [R(\alpha), R(\beta)]$. De plus, le nombre de tournois médians de $\Pi$ est $2^{|R(\beta) \setminus R(\alpha)|/2}$. L'éloignement d'un tournoi médian $T$ au profil $\Pi$ vaut :
$$E(\Pi, T) = \frac{v \cdot n(n+1)}{2} - \sum_{w(x,y)>0} w(x, y).$$

Preuve.

D'après la proposition 2.5., il suffit de montrer qu'il existe toujours un tournoi dans l'intervalle médian $[R(\alpha), R(\beta)]$ de $\Pi$. Or, pour obtenir un tel tournoi, il suffit d'ajouter à la relation antisymétrique $R(\alpha)$, un et un seul des deux couples $(x, y)$ ou $(y, x)$ chaque fois que $x$ et $y$ sont ex æquo, c'est-à-dire chaque fois qu'on a $v(x, y) = v(y, x)$. $\square$

## 2.3. Les ordres totaux médians ($\mathcal{L}$-médianes) d'un profil d'ordres totaux

Considérons maintenant le cas où les relations de préférence des votants sont des ordres totaux. Puisque les ordres totaux sont des tournois particuliers, on peut appliquer les résultats précédents pour trouver les tournois médians d'un profil $\Pi$ d'ordres totaux. Ce sont les tournois contenus dans l'intervalle médian de $\Pi$, intervalle qui en contient toujours, d'après la proposition 2.6. ci-dessus.

Tout peut changer si l'on cherche maintenant les ordres totaux médians de $\Pi$, c'est-à-dire les ordres totaux $\mathcal{L}$ minimisant $E(\Pi, \mathcal{L})$ dans l'ensemble $\mathcal{L}$ des ordres totaux définis sur $X$. En effet, comme l'a montré l'exemple donné à la section 2.2.4. (avant la proposition 2.5.), l'intervalle médian d'un profil d'ordres totaux peut ne contenir aucun ordre total (dans cet exemple, l'intervalle médian se réduit à la relation majoritaire, et cet unique tournoi médian est un circuit). On doit alors distinguer deux cas. Dans le premier, il existe un ordre total dans l'intervalle médian de $\Pi$, ou — de façon équivalente — la relation majoritaire stricte $R(\alpha)$ de $\Pi$ est sans circuit. Dans ce cas (conformément à la proposition 2.6.), les ordres médians de $\Pi$ sont tous les ordres totaux contenus dans l'intervalle médian, c'est-à-dire tous les ordres totaux contenant la relation $R(\alpha)$ (il est bien connu qu'une relation est contenue dans un ordre total si et seulement si elle est sans circuit). Le second cas est celui où l'intervalle médian du profil ne contient aucun ordre total, ou — de façon équivalente — celui où la relation majoritaire stricte du profil contient un circuit. On dit alors qu'il y a effet Condorcet<fnref n="2" />. L'existence possible d'un effet Condorcet a la

<footnote n="2">² L'existence possible de circuits dans la relation majoritaire a été en effet montrée par Condorcet dans son ouvrage [CAR 85], où il préconise l'emploi de cette relation. Une analyse fine [YOU 88] des propositions — non dénuées d'obscurité — de Condorcet pour pallier l'existence de tels circuits a aussi conduit à lui attribuer la paternité de la procédure associant, à un profil d'ordres totaux, ses ordres médians. En fait, cette procédure peut être définie de multiples façons (cf. [MON 90a]), ce qui explique qu'elle ait été retrouvée par</footnote>
conséquence suivante. Alors que l'obtention des relations médianes ou des tournois médians d'un profil était facile, celle des ordres médians devient un problème difficile (en fait « NP-difficile », cf. la partie 2.3.4.) qui nécessite de rechercher les propriétés de tels ordres et d'utiliser les méthodes d'optimisation combinatoire susceptibles de trouver des solutions exactes ou approchées pour de tels problèmes. Ceci va être l'objet de la présente section de cet article, la quatrième revenant sur le cas « facile », dont on peut faire la théorie dans le cadre des « demi-treillis à médianes ».

### 2.3.1. Formulation sous forme de problème de programmation linéaire en 0-1

Considérons un profil $\Pi = (L_1, ..., L_i, ..., L_v) \in \mathcal{L}^v$ d'ordres totaux et un ordre total $L$. On a vu dans la partie 2.2.3. (lemme 2.2.) que l'éloignement $E(\Pi, L)$ peut s'exprimer comme suit :

$$E(\Pi, L) = \sum_{i=1}^{v} |L_i| - \sum_{(x,y) \in L} w(x, y).$$

Exprimons cette distance à l'aide de variables binaires. Pour cela, introduisons la fonction caractéristique $\rho = (\rho_{xy})_{(x,y) \in X^2}$ de $L$. Celle-ci est définie de $X^2$ dans $\{0, 1\}$ par $\rho_{xy} = 1$ si on a $xLy$, $\rho_{xy} = 0$ sinon. En remarquant que pour chaque ordre $L_i$ ($1 \le i \le v$) on a $|L_i| = \frac{n(n+1)}{2}$, on obtient l'expression suivante pour l'éloignement :

$$E(\Pi, L) = \frac{v \cdot n(n+1)}{2} - \sum_{(x,y) \in X^2} w(x, y) \cdot \rho_{xy}.$$

Les variables étant les termes $\rho_{xy}$ pour $(x,y) \in X^2$, ce qui précède permet de considérer $E(\Pi, L)$ comme la fonction objectif d'un problème de programmation linéaire en les variables binaires $\rho_{xy}$. Comme minimiser une fonction revient à maximiser son opposée (avec une différence de signe entre les deux optima), minimiser $E(\Pi, L)$ revient donc, à une constante additive près que nous omettrons dans la suite, à maximiser $\sum_{(x,y) \in X^2} w(x, y) \cdot \rho_{xy}$.

<footnote>maints auteurs, dont le premier semble avoir été J.G. Kemeny, d'où parfois le nom de règle de Kemeny (voir [KEM 59]).</footnote>
Il ne nous reste plus qu’à traduire les propriétés caractéristiques d’un ordre total sous forme de contraintes linéaires. Le lecteur se convaincra facilement que ces propriétés se traduisent par les contraintes suivantes :

• réflexivité : $\forall x \in X, \rho_{xx} = 1$ ;

• antisymétrie : $\forall (x,y) \in X^2$ avec $x \neq y, \rho_{xy} + \rho_{yx} \leq 1$ ;

• complétude : $\forall (x,y) \in X^2$ avec $x \neq y, \rho_{xy} + \rho_{yx} \geq 1$ ;

• transitivité : $\forall (x,y,z) \in X^3, \rho_{xy} + \rho_{yz} - \rho_{xz} \leq 1$.

La détermination d'un ordre médian revient donc à la résolution du problème de programmation linéaire en 0-1 suivant :

$$ \text{Maximiser} \quad \sum_{(x,y) \in X^2} w(x,y) \rho_{xy} $$

$$ \text{avec les contraintes} \quad \left\{ \begin{array}{l} \forall x \in X, \rho_{xx} = 1 \\ \forall (x,y) \in X^2 \text{ avec } x \neq y, \rho_{xy} + \rho_{yx} = 1 \\ \forall (x,y,z) \in X^3, \rho_{xy} + \rho_{yz} - \rho_{xz} \le 1 \\ \forall (x,y) \in X^2, \rho_{xy} \in \{0, 1\} \end{array} \right. $$

### 2.3.2. Formulation à l'aide de graphes

Une relation binaire étant un graphe et réciproquement, on peut formuler le problème à l'aide de graphes. Les considérations qui précèdent montrent que les préférences des votants peuvent se résumer en la donnée des termes $w(x, y)$ pour tout élément $x$ et tout élément $y$ de $X$ (avec $w(y, x) = -w(x, y)$ pour $x \neq y$ car on a affaire à des préférences individuelles qui sont des ordres totaux ; dans le cas général, les préférences peuvent se résumer en la donnée des termes $v(x, y)$). Les mêmes considérations ont montré que la minimisation de l'éloignement revenait à maximiser la somme $\sum_{(x,y) \in X^2} w(x,y) \rho_{xy}$.

On peut alors résumer un profil $\Pi = (L_1, \dots, L_v)$ défini sur $X$ par un graphe orienté $G = (X, X^2)$ (autrement dit, $G$ possède tous les arcs possibles) dont chaque arc $(x, y)$ est pondéré par $w(x, y)$ ; nous dirons que le graphe pondéré $G$ est représentatif du profil $\Pi$. On constate donc que les poids des arcs $(x, y)$ et $(y, x)$, pour $x$ et $y$ distincts, sont opposés. On constate aussi, puisque $w(x, y)$ est égal à $2v(x, y) - v$, que tous les poids ont la parité de $v$ et sont compris entre $-v$ (aucun votant ne préfère $x$ à $y$) et $v$ (tous les votants préfèrent $x$ à $y$, ce qui est notamment le cas pour $x = y$). On peut alors chercher à caractériser les graphes représentatifs d'un
profil d'ordres totaux. Les travaux de Debord [DEB 87], prolongeant ceux de McGarvey [MCG 53], permettent d'obtenir une telle caractérisation, pour des profils contenant un nombre d'ordres totaux suffisamment grand.

THEOREME 2.7.– Soit $G = (X, X^2)$ un graphe possédant tous les arcs possibles, ces arcs étant pondérés par une fonction $w$. On peut associer à $G$ un profil de $v$ ($v > 0$) d'ordres totaux dont $G$ sera représentatif si on a les propriétés suivantes :

1. pour tout $(x, y) \in X^2$, $w(x, y)$ a la parité de $v$;

2. pour tout $x \in X$, $w(x, x) = v$;

3. pour tout $(x, y) \in X^2$ avec $x \neq y$, $w(y, x) = -w(x, y)$;

4. $v \ge \frac{1}{2} \sum_{x \neq y} |w(x, y)|$.

Dans la suite, nous dirons qu'une fonction de poids $w$ possède la propriété (P) si elle vérifie les conditions suivantes : 1. toutes ses valeurs ont même parité ; 2. les quantités $w(x, x)$ sont identiques pour tout $x \in X$ ; 3. pour tout $(x, y) \in X^2$ avec $x \neq y$, $w(y, x) = -w(x, y)$. On dira que $w$ possède la propriété (P') si elle est à valeurs positives et qu'elle vérifie en outre les conditions 1 et 2 précédentes.

Pour établir le théorème 2.7., on construit un profil d'ordres totaux à partir du graphe $G$. Notons que cette construction fait intervenir un nombre $v$ d'ordres totaux au moins égal à $\frac{1}{2} \sum_{x \neq y} |w(x, y)|$, ce qui ne correspond pas nécessairement à la valeur minimale de $v$ pour laquelle il existe un profil de $v$ ordres totaux dont $G$ soit représentatif<fnref n="3" />. Notons aussi que la construction du profil mise en œuvre par Debord est polynomiale si on accepte de représenter un profil de manière légèrement différente de ce que nous faisions jusqu'à présent. Au lieu de décrire le profil en énumérant les $v$ ordres le constituant, on énumère les ordres deux à deux distincts apparaissant dans le profil, suivis de leur nombre d'occurrences (voir [HUD 89] pour plus de détails)<fnref n="4" />.

<footnote n="3">³ Il existe des graphes $G$ représentatifs de profils d'ordres totaux mais ne respectant pas la condition 4 du théorème 2.7. À part certains cas simples, on ne sait pas caractériser ces graphes, ni même les reconnaître en un temps polynomial.</footnote>

<footnote n="4">⁴ Cette représentation des profils est notamment utilisée pour l'étude de la complexité du problème, puisque sa polynomialité permet de travailler avec les graphes représentatifs plutôt qu'avec les profils eux-mêmes, sans changer qualitativement les résultats obtenus. On peut l'utiliser par exemple pour démontrer le théorème 2.16. énoncé plus loin. Par ailleurs, l'énoncé du théorème 2.7. permet aussi de caractériser un profil de $v$ tournois, moyennant une légère adaptation : il suffit de remplacer la condition 4 par l'inégalité $v \ge \max_{(x,y)}|w(x,y)|$. Cette inégalité, la parité de $v$ et la stricte positivité de $v$ donnent alors toutes les valeurs possibles de $v$. Un cas particulier est celui pour lequel $v$ vaut 1 (le profil</footnote>
On peut de même associer un graphe à l'ordre médian L cherché. Il suffit pour
cela de considérer le graphe dont la matrice d'adjacence admet ρ$_{xy}$ pour élément
générique, où (ρ$_{xy}$)_{(x,y)∈X²} désigne, rappelons-le, la fonction caractéristique de L.
Du point de vue des graphes, déterminer un ordre total maximisant $\sum_{(x,y)∈X^2} w(x, y) \cdot \rho_{xy}$
revient alors à sélectionner des arcs de G constituant un ordre total et dont la somme
des poids soit la plus grande possible : ces arcs (x, y) seront ceux définis par
l'égalité ρ$_{xy}$ = 1.

Outre cette formulation, les propriétés des ordres totaux (aussi bien ceux
constituant le profil que celui que l'on cherche comme relation médiane) permettent
d'énoncer la recherche d'un ordre médian de plusieurs façons équivalentes, ce qui est
l'objet de ce qui suit.

2.3.3. Formulations équivalentes de la recherche d'un ordre total médian d'un profil d'ordres totaux

En constatant que les poids du graphe *G* représentatif du profil Π sont
partiellement redondants, du fait de la relation *w*(*y*, *x*) = - *w*(*x*, *y*) pour *x* ≠ *y*, on
peut ne retenir que les arcs de poids strictement positif ou, pour les paires d'arcs (x,
y) et (y, x) de poids nuls, l'un des deux arcs choisi arbitrairement. On obtient alors
un tournoi *T* pondéré positivement, représentatif lui aussi du profil Π. Cette
modélisation est souvent rencontrée dans la littérature, conduisant à de nouvelles
formulations pour le problème de la recherche d'un ordre total médian d'un profil
d'ordres totaux. Nous en donnons certaines ci-dessous (sans démontrer leur
équivalence<fnref n="5" /> ; on pourra se reporter à [CHA 96b] pour plus de détails). Nous
commençons par rappeler les trois expressions rencontrées plus haut : la première
est celle d'origine ; la deuxième, celle qui permet d'exprimer le problème sous forme
de problème de programmation linéaire en variables binaires ; la troisième est celle
que l'on obtient en considérant le graphe représentatif du profil considéré. Les
solutions des problèmes 2.8., 2.9. et 2.10. sont donc les mêmes, mais vues sous des
angles différents : en tant que relation binaire pour le problème 2.8., ou comme
ensemble de variables binaires (définissant la fonction caractéristique de la solution

<footnote>est réduit à un tournoi, qui peut être par exemple le tournoi majoritaire d'un profil d'ordres totaux) : on obtient le problème de Slater [SLA 61] de l'ajustement d'un tournoi en un ordre total ; tous les poids *w* valent alors 1 ou -1.</footnote>

<footnote n="5">⁵ Ces formulations sont souvent accompagnées de noms différents. Certains ont été évoqués plus haut, comme *problème de l'ordre médian* ou *règle de Kemeny*. On rencontre aussi *Linear Order Problem* ou *Linear Ordering Problem* dans la littérature anglo-saxonne, etc. Nous précisons certains de ces noms ci-dessous.</footnote>
du problème 2.8.) pour le problème 2.9., ou encore sous forme d'un graphe (dont la
matrice d'adjacence est donnée par la solution du problème 2.9.) pour le
problème 2.10.

PROBLEME 2.8.- Étant donné un profil Π de v ordres totaux définis sur X,
déterminer un ordre total médian.

PROBLEME 2.9.- Étant donnés les entiers w(x, y) vérifiant la propriété (P), déterminer une solution optimale du problème suivant :

$$
\begin{array}{ll}
\text{Maximiser} & \sum_{(x,y) \in X^2} w(x,y) \cdot \rho_{xy} \\
\text{avec les contraintes} & \left\{
\begin{array}{l}
\forall x \in X, \rho_{xx} = 1 \\
\forall (x,y) \in X^2 \text{ avec } x \neq y, \rho_{xy} + \rho_{yx} = 1 \\
\forall (x,y,z) \in X^3, \rho_{xy} + \rho_{yz} - \rho_{xz} \le 1 \\
\forall (x,y) \in X^2, \rho_{xy} \in \{0, 1\}
\end{array}
\right.
\end{array}
$$

Pour énoncer certains des problèmes suivants, nous introduisons une nouvelle
notation. Soit $G = (X, A)$ un graphe dont les arcs $a$ sont pondérés par $w(a)$. Pour tout
sous-ensemble $B$ de $A$, on pose $w(B) = \sum_{b \in B} w(b)$, quantité que nous appellerons le
poids de $B$.

PROBLEME 2.10.- Étant donné un graphe G = (X, X²) possédant tous les arcs possibles et dont chaque arc (x, y) est pondéré par w(x, y), ces poids vérifiant la propriété (P), déterminer L ⊂ X² de poids w(L) maximum et tel que (X, L) soit le graphe d'un ordre total défini sur X.

Pour la formulation suivante, rappelons qu'un ordre total est un tournoi transitif
et réciproquement. Si l'on ne garde de G que les arcs de poids positif et certains arcs
de poids nul pour obtenir un tournoi T comme il est dit plus haut (début du
paragraphe 2.3.3.), sélectionner dans G un arc (x, y) de poids strictement négatif (qui
ne figure donc pas dans T, mais tel que l'arc (y, x) figure, lui, dans T) revient dans T
à inverser l'arc (x, y) pour retrouver l'arc (y, x). On obtient ainsi la formulation du
problème 2.11. (connu, en anglais, sous le nom de minimum reversing set problem,
au moins dans le cas où tous les poids valent 1 ; voir [BAR 95a]) ; notons qu'une
solution optimale du problème 2.11. (un tournoi transitif) définit encore une
solution optimale du problème 2.8., c'est-à-dire un ordre médian.

PROBLEME 2.11.- Étant donné un tournoi T = (X, A) dont les arcs (x, y) sont pondérés par des poids w(x, y) vérifiant la propriété (P'), déterminer un sous-
ensemble $A'$ de $A$ de poids minimum tel que l'inversion dans $T$ des éléments de $A'$ transforme $T$ en un tournoi transitif.

Un tournoi $T$ est transitif (c'est-à-dire représentatif d'un ordre total) si et seulement si $T$ est sans circuit de longueur supérieure ou égale à 3 (en nombre d'arcs)<fnref n="6" />. Cette remarque permettrait de montrer l'équivalence, en un certain sens, entre les énoncés des problèmes 2.11. et 2.12. Plus précisément, les solutions optimales du problème 2.11. (des sous-ensembles d'arcs) ne sont pas nécessairement les mêmes que celles du problème 2.12. En revanche, il est facile de montrer que les poids des solutions optimales du problème 2.11. et du problème 2.12. sont identiques : les sous-ensembles d'arcs optimaux de ces problèmes ne diffèrent que par d'éventuels arcs de poids nul (s'il en existe).

**PROBLEME 2.12.**— Étant donné un tournoi $T = (X, A)$ dont les arcs $(x, y)$ sont pondérés par des poids $w(x, y)$ vérifiant la propriété $(P')$, déterminer un sous-ensemble $A'$ de $A$ de poids minimum tel que la suppression dans $T$ des éléments de $A'$ laisse un graphe sans circuit de longueur supérieure ou égale à 3.

La formulation suivante découle immédiatement du problème 2.12. Elle a pour seul mérite de relier deux problèmes étudiés parfois séparément (le problème 2.12. étant une forme pondérée de ce que la littérature anglo-saxonne appelle le problème du minimum feedback arc set, et le problème 2.13. une forme pondérée de ce que la même littérature nomme le problème du maximum arc consistent set ou aussi acyclic subdigraph problem). On verra cependant plus loin qu'ils ne se comportent pas de la même façon par rapport aux algorithmes à garantie de performances.

**PROBLEME 2.13.**— Étant donné un tournoi $T = (X, A)$ dont les arcs $(x, y)$ sont pondérés par des poids $w(x, y)$ vérifiant la propriété $(P')$, déterminer un sous-ensemble $A'$ de $A$ de poids maximum tel que le graphe $(X, A')$ soit sans circuit de longueur supérieure ou égale à 3.

Le problème 2.14. traduit les problèmes 2.11. et 2.12. en termes matriciels (c'est en ces termes que Slater [SLA 61] définissait son problème de l'ajustement d'un tournoi — dont tous les poids valent 1 — par un ordre total ; cette approche a aussi été utilisée par Younger [YOU 63]). Pour cela, soit $T = (X, A)$ un tournoi dont les arcs $(x, y)$ sont pondérés par des poids $w(x, y)$ vérifiant la propriété $(P')$, on définit la matrice $M = (m_{xy})_{(x,y)\in X^2}$ des poids de $T$ par :

<footnote n="6">⁶ Autrement dit, il ne doit y avoir aucun circuit, sauf les boucles $(x, x)$, pour $x \in X$, caractéristiques de la réflexivité.</footnote>
$$m_{xy} = \begin{cases} w(x, y) & \text{si } (x, y) \in A \\ 0 & \text{sinon} \end{cases}.$$

PROBLEME 2.14.- Étant donnée la matrice M des poids d'un tournoi pondéré par w vérifiant la propriété (P'), déterminer un (même) ordre sur les lignes et sur les colonnes de M de façon à minimiser la somme des termes situés sous la diagonale.<fnref n="7" />

Pour la dernière formulation, nous avons besoin d'outils plus sophistiqués : les hypergraphes. Un hypergraphe, ou système d'ensembles, est une généralisation des graphes non orientés. Plus précisément, un hypergraphe $H = (Y, F)$ est un couple d'ensembles constitué d'un ensemble $Y$, dont les éléments sont appelés sommets, et d'un sous-ensemble $F$ des parties non vides de $Y$ recouvrant tous les éléments de $Y$. Si tous les éléments de $F$ sont de cardinal égal à 2, on retrouve la notion habituelle de graphe non orienté. Étant donné un tournoi $T = (X, A)$, on considère ici l'hypergraphe $H(T)$ des circuits de $T$ : les sommets de $H(T)$ sont les arcs de $T$ qui ne sont pas des boucles et par lesquels passent des circuits de $T$, les éléments de $F$ sont les sous-ensembles de $X$ définissant les circuits de $T$. Un transversal d'un hypergraphe $H = (Y, F)$ est un sous-ensemble $Y'$ de $Y$ tel que tout élément de $F$ (un sous-ensemble non vide de $Y$) contienne au moins un élément de $Y'$. Pour un tournoi $T$ dont les arcs sont pondérés, chaque sommet de $H(T)$ possède un poids, qui est le poids de l'arc de $T$ associé au sommet considéré de $H(T)$ ; on peut alors définir le poids d'un transversal comme la somme des poids des sommets constituant le transversal. On obtient alors la dernière formulation considérée ici (déjà présente dans [BER 72] pour le problème de Slater) :

PROBLEME 2.15.- Étant donné un tournoi $T = (X, A)$ dont les arcs $(x, y)$ sont pondérés par des poids $w(x, y)$ vérifiant la propriété (P'), déterminer un transversal de poids minimum de l'hypergraphe $H(T)$ des circuits de $T$.

### 2.3.4. Complexité de la recherche d'un ordre médian d'un profil d'ordres totaux

La théorie de la complexité (voir [GAR 79] ou [BAR 92]) a pour objectif d'étudier l'efficacité des algorithmes et la difficulté intrinsèque d'un problème. Sans entrer dans les détails, un problème est dit polynomial s'il existe un algorithme de complexité polynomiale permettant de le résoudre (de manière exacte). Il existe par ailleurs de nombreux problèmes pour lesquels on ne connaît pas d'algorithme de

<footnote n="7">⁷ Une variante, liée au problème 2.13., consisterait à maximiser la somme des termes situés au-dessus de la diagonale. Elle est alors un cas particulier du problème rencontré en économie sous le nom de « triangulation » d'un tableau carré de coefficients reflétant des échanges inter-industriels (pour des exemples, voir [GRÖ 84] ou [REI 85]).</footnote>
résolution polynomial (ce qui ne signifie pas qu'il n'en existe pas). C'est le cas en particulier des problèmes NP-complets et des problèmes NP-difficiles<fnref n="8" />. La conséquence pratique de la NP-difficulté d'un problème est que les algorithmes connus pour résoudre ce problème sont de complexité élevée (typiquement, exponentielle) : le temps de calcul nécessaire pour résoudre un tel problème de manière exacte peut donc rapidement devenir prohibitif quand la taille des données croît<fnref n="9" />. Il est donc important, pour la résolution pratique d'un problème, de connaître sa complexité. Le théorème 2.16. donne la complexité de l'agrégation d'un profil d'ordres totaux en un ordre total.

**THEOREME 2.16.–** La détermination d'un ordre total médian d'un profil d'ordres totaux est un problème NP-difficile.

On trouvera dans [WAK 86] et dans [HUD 89] d'autres résultats de complexité relatifs à la détermination de relations médianes (ainsi que, dans [HUD 89], la démonstration du théorème 2.16.). Mis à part des cas triviaux, les problèmes d'agrégation de préférences sont en général NP-difficiles ou de complexité inconnue. Par exemple, l'agrégation d'un profil d'ordres totaux en un préordre total est aussi un problème NP-difficile ; en revanche, la complexité du problème de Slater (c'est-à-dire l'ajustement d'un tournoi en un ordre total, ce qui correspond à un profil réduit à un tournoi) reste actuellement un problème ouvert. Par ailleurs, en l'absence d'effet Condorcet (le tournoi majoritaire représentant le profil est alors sans circuit), les ordres totaux médians sont exactement les ordres totaux majoritaires.

Signalons cependant un cas polynomial non trivial : il s'agit de l'agrégation d'un *profil d'ordres totaux unimodaux* (voir [BLA 48]). Pour définir la structure d'ordre unimodal, on suppose que chaque votant attribue une valeur numérique à

<footnote n="8">⁸ Un *problème NP-complet* est un problème de décision (problème pour lequel on pose une question admettant la réponse « oui » ou « non ») appartenant à la classe NP (classe des problèmes de décision polynomiaux non déterministes : pour toute instance admettant la réponse « oui », on peut vérifier en un temps polynomial que la réponse est bien « oui », quitte à utiliser une solution fournie par un « devin ») et faisant partie des problèmes les plus difficiles de la classe NP (l'existence d'un algorithme polynomial pour résoudre un tel problème entraînerait celle d'algorithmes polynomiaux pour résoudre tout problème de NP). Un *problème NP-difficile* est un problème, de décision ou non, au moins aussi difficile qu'un problème NP-complet. On peut associer canoniquement un problème de décision à un problème d'optimisation ; si ce problème de décision est NP-complet, alors le problème d'optimisation est lui-même NP-difficile.</footnote>

<footnote n="9">⁹ Pour illustrer la croissance d'une complexité non polynomiale, considérons la méthode consistant à énumérer les *n* ordres totaux et à garder le meilleur. En supposant qu'on dispose d'un ordinateur capable de traiter un milliard d'ordres totaux en une seconde, il faudrait environ 4 ms pour *n* = 10, 77 ans pour *n* = 20, 8,4.10¹³ siècles pour *n* = 30, 2,6.10²⁹ siècles pour *n* = 40 et presque 10⁴⁶ siècles pour *n* = 50.</footnote>
chaque candidat. On suppose d'autre part que les candidats sont classés selon un critère indépendant des votants et définissant un ordre total, que nous noterons $\mathfrak{P}$, sur les candidats (par exemple, pour une élection politique, l'échelle classique allant de l'extrême gauche à l'extrême droite, en supposant que l'on puisse identifier l'appartenance politique de chaque candidat et distinguer deux candidats quelconques par rapport à ce critère ; cela n'est pas toujours une tâche facile en pratique). Notons $x_1 \in \mathfrak{P}$, $x_2 \in \mathfrak{P}$, ... $\in \mathfrak{P}$, $x_n$ l'ordre des candidats selon $\mathfrak{P}$, ce qui fixe la numérotation des candidats. Par rapport à la numérotation induite par $\mathfrak{P}$, appelons $\gamma_k^i$ la valeur attribuée par le votant $i$ (pour $1 \le i \le v$) au candidat $x_k$ (pour $1 \le k \le n$), en supposant toutes ces valeurs distinctes. Nous dirons que l'ordre de préférence $L_i$ du votant $i$ est unimodal par rapport à $\mathfrak{P}$ s'il existe un indice $k(i)$, compris entre 1 et $n$, tel que la suite $(\gamma_k^i)_{1 \le k \le k(i)}$ soit croissante et la suite $(\gamma_k^i)_{k(i) \le k \le n}$ décroissante (dans l'exemple précédent d'une élection politique, cela signifie que le votant $k$ a un candidat préféré, $x_{k(i)}$, et que plus on s'éloigne de ce candidat, vers la gauche ou vers la droite, moins sont appréciés les candidats que l'on rencontre ; on n'impose rien en revanche sur la façon dont le votant $k$ classe deux candidats placés de part et d'autre de $x_{k(i)}$). Cet ordre est donc défini par $x_k, L_i, x_{k'}$ si et seulement si on a $\gamma_k^i > \gamma_{k'}^i$. Un profil d'ordres totaux est dit *profil d'ordres totaux unimodaux* s'il existe un ordre $\mathfrak{P}$ défini sur $X$ tel que tous les ordres du profil soient unimodaux pour l'ordre $\mathfrak{P}$. Dans ce cas, comme il est dit plus haut, on peut montrer que la détermination d'un ordre total médian est polynomiale.

### 2.3.5. Méthodes de résolution

La conséquence algorithmique du théorème 2.16. est qu'on ne connaît pas, dans le cas général, d'algorithmes polynomial permettant de calculer exactement un ordre médian (et qu'il n'en existe pas si $\mathfrak{P}$ est différent de $\mathfrak{NP}$). Nous ne ferons ici qu'évoquer les principales orientations algorithmiques utilisées pour déterminer des ordres médians, le problème étant modélisé à l'aide d'un tournoi pondéré (le lecteur intéressé trouvera des références bibliographiques dans [BAR 81] et [HUD 97], en plus de celles citées plus bas).

Les méthodes exactes de résolution (voir par exemple [CHA 04] pour des références bibliographiques) actuellement connues étant de complexité élevée, elles ne permettent pas la résolution de problèmes de grande taille. Ce sont essentiellement des méthodes arborescentes par séparation et évaluation, avec divers ingrédients plus ou moins sophistiqués. On retiendra en particulier, pour la conception d'une fonction d'évaluation, le recours à la relaxation continue (par rapport à la formulation du problème 2.9. ci-dessus, les contraintes $\rho_{xy} \in \{0,1\}$ sont remplacées par $\rho_{xy} \in [0,1]$), la relaxation lagrangienne (par relaxation des contraintes
de transitivité ; voir [ARD 84] et [CHA 04]) et l'application de la théorie polyédrale à l'aide de plans sécants (pour obtenir une méthode appelée *branch and cut* dans la littérature anglo-saxonne ; voir par exemple [JÜN 85], [REI 85], [MIT 96] et [MIT 00]). D'autres efforts portent sur l'exploitation de propriétés combinatoires (voir [CHA 97] ou [CHA 04]) ou de structures appropriées pour mémoriser certaines informations. Par exemple, l'utilisation d'un tas accélère la recherche de la feuille à développer dans une stratégie de type « meilleur d'abord » [WOI 97], et celle d'un « arbre des sections commençantes » permet d'élaguer l'arbre de recherche autrement que par l'application habituelle de la fonction d'évaluation [GUÉ 95]. Ces algorithmes ont des performances qui dépendent beaucoup des instances à traiter. On peut par exemple résoudre en un temps raisonnable des instances réelles ou simulant des données réelles de taille allant jusqu'à une centaine de candidats (ainsi le logiciel disponible à l'adresse http://www.enst.fr/~charon/tournament/median.html permet de traiter des instances simulant certaines données réelles avec 100 candidats et 25 votants en environ 1 seconde). Les instances aléatoires semblent plus difficiles à traiter (le même logiciel nécessite environ 1000 secondes pour des instances aléatoires du problème de Slater avec 36 candidats ; d'autres résultats obtenus à l'aide de ce logiciel peuvent être trouvés dans [CHA 04]).

Une autre possibilité consiste à renoncer à une solution systématiquement exacte et à se contenter d'une solution approchée, en espérant calculer une bonne solution approchée en un temps « raisonnable ». Certaines de ces méthodes heuristiques sont spécifiques au problème à résoudre (plusieurs d'entre elles concernent même initialement le problème de Slater, mais peuvent souvent être généralisées au cas d'un tournoi pondéré ; voir par exemple [BEC 67], [SMI 74], [GOD 83], [COO 88], [BAR 89], [KAY 95], [CHA 96a] ou [MEN 00]). D'autres sont issues de l'adaptation de métaheuristiques (méthodes approchées générales) comme le recuit simulé, la méthode Tabou, les méthodes de bruitage, les algorithmes génétiques ou encore des hybridations entre ces méthodes (voir par exemple [HUD 89], [CHA 98], [CAM 99], [LAG 99], [CON 00], [CAM 01], [SCH 03] ou [CHA 04]). Si la qualité de certaines des heuristiques spécifiques peut décroître assez vite avec la taille de l'instance à traiter, les métaheuristiques semblent donner de bons résultats en un faible temps de calcul. Ainsi, les expériences rapportées dans [CHA 04] indiquent que les méthodes de bruitage (voir [CHA 02] pour une présentation de ces méthodes) ont pu déterminer une solution exacte du premier coup en un temps négligeable pour les 5790 tournois, ayant jusqu'à 100 sommets, qui ont servi de tests à une méthode exacte, sauf pour six tournois, qui ont nécessité une seconde application.

On notera encore un autre type de méthodes appropriées pour la résolution des problèmes difficiles : les méthodes probabilistes. Elles ont été appliquées à des tournois dont tous les poids valent 1 dans [POL 86] et [POL 88]. Dans [POL 86] est présenté un algorithme récursif qui s'applique à plusieurs problèmes d'optimisation, dont la recherche d'un graphe sans circuit dans un graphe orienté.
Étant donné un graphe $G = (X, A)$ pondéré par une fonction $c$ à valeurs positives ou nulles, il permet, pour les problèmes considérés et pour certaines valeurs d'un réel $\lambda$ compris strictement entre 0 et 1, d'exhiber un graphe partiel $H = (X, B)$ tel qu'on ait
$$ \sum_{b \in B} c(b) \geq \lambda \sum_{a \in A} c(a) + \frac{1-\lambda}{2} \xi(G), \text{ où } \xi(G) \text{ est le poids d'un arbre couvrant de poids} $$

minimum (par rapport à $c$) de $G$. Dans le cas de la recherche d'un graphe partiel maximum sans circuit d'un graphe orienté antisymétrique avec $c$ qui est la fonction constante égale à 1, la valeur $\lambda = 0,5$ donne d'intéressants résultats. On obtient en effet un algorithme qui sélectionne dans un tournoi au moins $\frac{n(n+3)}{4} + \frac{n-1}{4}$ arcs sans circuit de longueur (en nombre d'arcs) supérieure ou égale à 3, et donc qui inverse au plus $\frac{(n-1)^2}{4}$ arcs pour obtenir un ordre total. Ce résultat est amélioré dans [POL 88], à l'aide d'une méthode probabiliste en $O(n^3 \log n)$ qui détermine (au moins pour $n$ assez grand) un graphe partiel sans circuit de longueur (en nombre d'arcs) supérieure ou égale à 3 dans un tournoi dont tous les poids valent 1, avec au moins $\frac{n(n+3)}{4} + \frac{n\sqrt{n}}{8\sqrt{\pi}}$ arcs du tournoi, et donc un ordre total obtenu en inversant au plus $\frac{n(n-1)}{4} - \frac{n\sqrt{n}}{8\sqrt{\pi}}$ arcs.

La dernière possibilité évoquée ici concerne les algorithmes approchés avec garantie de performances (voir [VAZ 03]). On peut en effet concevoir, pour le problème 2.13. énoncé plus haut (recherche d'un graphe partiel sans circuit et de poids maximum) un algorithme (déterministe) qui, à défaut de donner systématiquement une solution optimale, permet d'obtenir une solution qui ne soit pas « trop éloignée » d'une solution optimale. Il suffit pour cela d'aligner les sommets du tournoi sur une droite horizontale, selon une numérotation quelconque des sommets, par exemple $x_1, x_2, ..., x_n$. Par rapport à cet alignement, certains arcs (qui ne sont pas des boucles) sont orientés de gauche à droite, les autres de droite à gauche. La sélection des boucles et de tous les arcs orientés de gauche à droite permet d'obtenir un graphe partiel sans circuit de longueur supérieure ou égale à 3 ; soit $w_1$ la somme des poids de ces arcs. En appelant $w_{max}$ le poids d'une solution optimale du problème 2.13. pour le tournoi considéré, on obtient ainsi $w_{max} \geq w_1$. En faisant de même avec les boucles et les arcs orientés de droite à gauche, on obtient une autre solution, de poids $w_2$ vérifiant aussi l'inégalité $w_{max} \geq w_2$. Appelons $W$ la somme de tous les poids du tournoi : $W = \sum_{a \in A} w(a)$. Les boucles (de poids $v$) étant

comptées deux fois dans $w_1 + w_2$, on a les relations suivantes : $w_1 + w_2 = W + n.v$ et $w_{max} \leq W$. En supposant $w_2$ au moins aussi grand que $w_1$ (sinon on inverse la
numérotation des sommets), on déduit de ce qui précède l'encadrement
$\frac{w_{max}}{2} < w_2 \le w_{max}$, ou encore la majoration $\frac{w_{max}-w_2}{w_{max}} < \frac{1}{2}$ : l'erreur relative que
l'on commet en adoptant la solution associée à $w_2$ au lieu d'une solution optimale
ne peut excéder 50 %, quel que soit le tournoi considéré ; on peut donc se tromper
mais, en un certain sens, pas trop<fnref n="10" />.

2.3.6. Propriétés des ordres médians

Pour terminer cette partie, nous évoquons quelques propriétés des ordres totaux médians des profils d'ordres totaux. La première peut être établie à l'aide d'un raisonnement proche de celui qui clôt la partie précédente. Nous supposons ici que le profil d'ordres totaux considéré est décrit par son tournoi représentatif (cf. partie 2.3.3.) et que l'on s'intéresse au problème 2.11. (inverser un ensemble d'arcs de poids minimum pour transformer le tournoi associé au profil en un orde total).

PROPOSITION 2.17.— Soit $T = (X, A)$ le tournoi associé à un profil $\Pi$ d'ordres totaux et soit $w$ sa fonction de poids. Soit $L = x_1 > x_2 > \dots > x_n$ un ordre médian de $\Pi$. On a alors, pour tout $i$ compris entre $1$ et $n-1$ :

$$
\sum_{\substack{(x_j, x_k) \in A \\ 1 \le j \le i < k \le n}} w(x_j, x_k) \ge \sum_{\substack{(x_k, x_j) \in A \\ 1 \le j \le i < k \le n}} w(x_k, x_j).
$$

Preuve.

Supposons qu'il existe un indice *i* pour lequel l'inégalité précédente ne soit pas
satisfaite. Autrement dit, si on place les sommets de *T* sur une droite horizontale, les
indices croissant de gauche à droite, et que l'on sépare par un trait vertical les
sommets d'indices compris entre 1 et *i* des autres, les arcs qui traversent le trait
vertical de droite à gauche sont de poids total strictement supérieur au poids total des
arcs traversant le trait vertical de gauche à droite. Considérons alors l'ordre total *L*'
obtenu en intervertissant la partie située à gauche du trait vertical avec celle située à
droite, c'est-à-dire l'ordre total *L*' = *x*<sub>*i*+1</sub> > ... > *x*<sub>*n*</sub} > *x*<sub>1</sub} > ... > *x*<sub>*i*</sub>. Comme
l'obtention de *L*' nécessite l'inversion des mêmes arcs que pour obtenir *L* sauf les
arcs qui traversent le trait vertical (les arcs impliqués dans l'une ou l'autre somme de

<footnote n="10">¹⁰ On notera que, par rapport à l'existence d'algorithmes à garantie de performances, les huit problèmes énoncés dans la partie 2.3.3. ne sont plus nécessairement équivalents. Ainsi, le raisonnement que l'on vient de décrire n'est-il pas applicable fructueusement au problème 2.12., faute de pouvoir trouver une minoration de la valeur minimum de ce problème par un terme non nul proportionnel à W.</footnote>
l'énoncé de la proposition), il est facile de voir que $L'$ serait strictement meilleur que $L$, ce qui est incompatible avec l'optimalité de $L$. D'où le résultat. ☐

La proposition suivante ([YOU 63] et [JAC 69]) exprime le fait qu’un intervalle quelconque d’un ordre médian est un ordre médian du sous-tournoi induit par cet intervalle.

**PROPOSITION 2.18.**— Soit $T = (X, A)$ le tournoi pondéré associé à un profil $\Pi$ d'ordres totaux et soit $L = x_1 > x_2 > \dots > x_n$ un ordre médian de $\Pi$. Alors, pour tout $i$ et tout $j$ avec $1 \le i < j \le n$, $x_i > x_{i+1} > \dots > x_j$ est un ordre médian du sous-tournoi de $T$ engendré par $x_i, x_{i+1}, \dots, x_j$.

Preuve.

Supposons qu'il existe deux indices $i$ et $j$ pour lesquels la proposition 2.18. ne soit pas vraie. Soit $L'$ l'ordre total obtenu en remplaçant $x_i > \dots > x_j$ dans $L$ par un ordre médian du sous-tournoi de $T$ engendré par $x_i, \dots, x_j$. Il est facile de voir qu'alors $L'$ serait strictement meilleur que $L$, une contradiction avec l'optimalité de $L$. ☐

On peut en déduire le corollaire suivant.

**COROLLAIRE 2.19.**— Soit $T = (X, A)$ le tournoi pondéré associé à un profil $\Pi$ d'ordres totaux et soit $w$ sa fonction de poids. Soit $L = x_1 > x_2 > \dots > x_n$ un ordre médian de $\Pi$. Supposons que les poids $w(a)$ pour $a \in A$ soient tous non nuls. Alors, pour tout $i$ compris entre 1 et $n-1$, l'arc entre $x_i$ et $x_{i+1}$ est orienté de $x_i$ vers $x_{i+1}$.

Preuve.

Il suffit d'appliquer la proposition 2.18. avec $j = i + 1$. ☐

Si on applique en particulier le corollaire 2.19. à un tournoi $T$ dont les poids valent 1 (problème de Slater), on retrouve un résultat bien connu (voir [REM 66]), selon lequel les arcs reliant deux sommets consécutifs dans un ordre médian quelconque de $T$ définissent un chemin hamiltonien<fnref n="11" /> de $T$. Le lien entre ordres médians et chemins hamiltoniens intervient aussi pour établir le théorème 2.20.

**THEOREME 2.20.**— Soit $\Pi$ un profil de $v$ ordres totaux définis sur $X$ à $n$ éléments. Alors, si $v$ est pair, le nombre d'ordres médians de $\Pi$ est compris entre 1 et $n!$, les bornes pouvant être atteintes. Si $v$ est impair et assez grand, le nombre d'ordres médians de $\Pi$ est compris entre 1 et $\frac{\mu n \sqrt{n} n!}{2^n}$, où $\mu$ est une constante.

<footnote n="11">¹¹ Rappelons qu’un chemin hamiltonien de $T$ est un chemin passant exactement une fois par chaque sommet de $T$.</footnote>
Preuve.

Dans les deux cas, le minorant est trivial : il suffit par exemple de considérer le cas d'un profil constitué de $v$ fois le même ordre total.

Si $v$ est pair, considérons les deux ordres totaux opposés $L_1 = x_1 > \dots > x_n$ et $L_2 = x_n > \dots > x_1$. Le profil constitué de $L_1$ reproduit $v/2$ fois et de $L_2$ reproduit aussi $v/2$ fois est représenté par un tournoi dont tous les poids sont nuls (pour chaque candidat $x$ et chaque candidat $y$, il existe autant de votants préférant $x$ à $y$ ou $y$ à $x$). Dans ce cas, il est facile de constater que les $n!$ ordres totaux définis sur $X$ sont tous des solutions optimales. D'où le résultat puisque, d'autre part, $n!$ est trivialement un majorant du nombre d'ordres médians.

Si $v$ est impair, les poids des arcs du tournoi $T$ représentatif de $\Pi$ sont tous impairs, donc non nuls. Alors, d'après ce qui précède, on peut majorer le nombre d'ordres médians de $\Pi$ par le nombre de chemins hamiltoniens de $T$. Or, Alon a montré [ALO 90] que ce nombre est majoré par $\frac{\mu n\sqrt{n \cdot n}!}{2^n}$, pour une certaine constante $\mu$ et pour $n$ assez grand. $\square$

Le nombre maximum d'ordres médians d'un profil de $v$ ordres totaux n'est pas connu exactement quand $v$ est impair. Des résultats (combinatoires ou expérimentaux) sur certains profils semblent indiquer que le nombre maximum d'ordres médians admis par un profil constitué d'un nombre impair d'ordres totaux est significativement inférieur au nombre de chemins hamiltoniens du tournoi représentatif de ce profil. Le nombre d'ordres médians peut cependant être exponentiel pour certains profils. Plus précisément, il est montré dans [WOI 97] que, pour un tournoi dont les poids valent 1 (problème de Slater), le nombre de solutions optimales peut atteindre $\exp\left[\frac{\ln 3}{4}(3n - 2\log_3 n - 3)\right]$ quand $n$ est une puissance de 3.

Puisqu'un tel tournoi peut, via le théorème 2.7., être associé à un profil d'ordres totaux, on en déduit que ce nombre exponentiel minore le nombre maximum d'ordres médians qu'un profil d'ordres totaux peut admettre.

Une autre propriété vérifiée par les ordres totaux médians est la règle d'unanimité (ou principe de Pareto). Pour un profil $\Pi = (L_1, L_2, \dots, L_v)$ de $v$ ordres totaux, notons $U(\Pi) = \bigcap_{1 \le i \le v} L_i$ la partie unanime de $\Pi$. Le théorème suivant (voir [FEL 73], [MON 73] ou [BAR 76]) exprime le fait que, si tous les votants préfèrent un candidat $x$ à un candidat $y$, alors $x$ doit aussi être préféré à $y$ dans tout ordre médian de $\Pi$.

**THEOREME 2.21.**— Soit $\Pi$ un profil de $v$ ordres totaux et soit $L$ un ordre médian de $\Pi$. On a alors : $U(\Pi) \subseteq L$.
Enfin, mentionnons une dernière propriété : la *consistance*. Elle exprime le fait que, si deux profils $\Pi$ et $\Pi'$ d'ordres totaux définis sur X admettent des ordres médians communs, l'ensemble des ordres médians de la concaténation de $\Pi$ et de $\Pi'$ est l'ensemble des ordres médians communs à $\Pi$ et à $\Pi'$.

**THEOREME 2.22.-** *Soient $\Pi = (L_1, L_2, ..., L_v)$ et $\Pi' = (L'_1, L'_2, ..., L'_v)$ deux profils de respectivement $v$ et $v'$ ordres totaux. Soit $\Pi\Pi'$ le profil obtenu par concaténation de $\Pi$ et de $\Pi'$ : $\Pi\Pi' = (L_1, L_2, ..., L_v, L'_1, L'_2, ..., L'_v)$. On a alors : $Méd_\Pi(\Pi) \cap Méd_\Pi(\Pi') \neq \emptyset \Rightarrow Méd_\Pi(\Pi\Pi') = Méd_\Pi(\Pi) \cap Méd_\Pi(\Pi')$.*

Cette propriété de consistance est la plus importante dans une remarquable caractérisation axiomatique de la procédure des ordres médians due à Young et Levenglick ([YOU 78]), ainsi que dans la caractérisation de la procédure médiane dans les demi-treillis à médianes (cf. plus loin le théorème 2.28.). Par ailleurs, elle reste vraie pour toutes les médianes métriques (voir [BAR 91]). D'autres propriétés des ordres médians sont décrites dans [BAR 81], [CHA 96b], [CHA 97] ou, pour des tournois dont les poids valent 1, dans [LAS 97].

## 2.4. Médianes dans les treillis et demi-treillis

Nous avons jusqu'ici abordé le problème du consensus en recherchant les médianes de profils de relations binaires. Nous avons établi que cette recherche, facile dans certains cas (relations et tournois médians) peut devenir fort difficile dans d'autres (ordres médians). Le but de cette section est de montrer que ces résultats se généralisent grandement. En effet, on peut définir et rechercher des médianes dans tout ensemble ordonné où il existe une généralisation naturelle de la distance de la différence symétrique, et en particulier dans tout demi-treillis (fini). Dès lors la recherche de consensus médians peut se faire pour tout ensemble d'objets à agréger pouvant être muni d'un tel ordre. Et le fait que cette recherche soit ou non facile dépend des propriétés structurelles de l'ensemble ordonné, le « bon » cas étant celui des demi-treillis à médianes, qui seront présentés à la section 2.4.3. Auparavant, à la section 2.4.1., nous donnons les notions nécessaires sur les ensembles ordonnés, en nous appuyant sur le cas d'ensembles de relations binaires ordonnées par inclusion. En particulier, nous précisons la nature d'ensembles ordonnés de relations utilisées pour modéliser les préférences ou les classements individuels. La section 2.4.2. montre comment définir une généralisation de la distance de la différence symétrique dans les demi-treillis et comment se calcule l'éloignement associé entre un v-uple d'éléments et un élément. La section 2.4.4. évoque brièvement les difficultés qui surgissent si l'on travaille dans un demi-treillis qui n'est plus à médianes. Enfin, on présente dans la section 2.4.5. des situations où ces généralisations latticielles se sont révélées efficaces.
### 2.4.1. Structures ordonnées

On considère souvent un ensemble de relations $\mathcal{D}$ qui est (partiellement) ordonné, c'est-à-dire muni d'une relation d'ordre $\leq$ vérifiant les trois propriétés : pour tous $R, R', R'' \in \mathcal{D}$, $R \leq R$ (réflexivité), $R \leq R'$ et $R' \leq R$ impliquent $R = R'$ (antisymétrie), $R \leq R'$ et $R' \leq R''$ impliquent $R \leq R''$ (transitivité). Fréquemment, cet ordre n'est autre que la restriction à $\mathcal{D}$ de l'ordre d'inclusion sur l'ensemble $P(X^2)$ de toutes les relations binaires sur $X$. Sauf indication contraire, nous nous placerons dans ce cas et écrirons $R \subseteq R'$ pour $R \leq R'$, et $R \subsetneq R'$ si, de plus, $R \neq R'$. Dans cette partie, les ordres considérés sont généralement des « ordres partiels », mais aussi éventuellement des ordres totaux.

Étant donnée une partie $\mathcal{A}$ de $\mathcal{D}$, un minorant de $\mathcal{A}$ est une relation $R$ de $\mathcal{D}$ telle que, pour tout $A \in \mathcal{A}$, $R \subseteq A$. La partie $\mathcal{A}$ est minorée si elle a au moins un minorant. De même, un majorant de $\mathcal{A}$ est une relation $R$ de $\mathcal{D}$ telle que $A \subseteq R$ pour tout $A \in \mathcal{A}$, et $\mathcal{A}$ est majorée si elle a un majorant. La partie $\mathcal{A}$ est dite bornée inférieurement si elle est minorée et si l'ensemble de ses minorants a un maximum, appelé alors l'infimum de $\mathcal{A}$ et noté $\bigwedge \mathcal{A}$ (l'infimum de deux éléments $R$ et $R'$ est noté $R \wedge R'$). Lorsque l'intersection $\bigcap \mathcal{A}$ de toutes les relations de $\mathcal{A}$ est un élément de $\mathcal{D}$, on a $\bigwedge \mathcal{A} = \bigcap \mathcal{A}$. De même, $\mathcal{A}$ est bornée supérieurement si elle est majorée et si l'ensemble de ses majorants a un minimum, le supremum de $\mathcal{A}$, qui est noté $\bigvee \mathcal{A}$, ou $\bigcup \mathcal{A}$ s'il s'agit de l'union (le supremum de deux éléments $R$ et $R'$ est noté $R \vee R'$). On remarque alors que, quand il existe, le minimum (resp. le maximum) de $\mathcal{A}$ est aussi son infimum (resp. son supremum).

L'ensemble ordonné $\mathcal{D}$ est :

- un *inf-demi-treillis* si toute paire $\{R, R'\}$ de ses éléments admet un infimum $R \wedge R'$,

- un *sup-demi-treillis* si toute paire $\{R, R'\}$ de ses éléments admet un supremum $R \vee R'$,

- un *treillis* si toute paire admet un infimum et un supremum, donc s'il est à la fois un inf-demi-treillis et un sup-demi-treillis.

Ainsi, si $\mathcal{D}$ est totalement ordonné, c'est un treillis avec, respectivement, le minimum pour infimum et le maximum pour supremum. L'ensemble $P(X^2)$ est un treillis avec l'intersection pour infimum et l'union pour supremum. La table 2.1. donne la structure ordinale des principaux ensembles de relations binaires réflexives et transitives sur $X$, ordonnés par inclusion.
<table><caption>Table 2.1.</caption><thead><tr><th>Ensemble D</th><th>Propriétés</th><th>Infimum</th><th>Supremum</th><th>Structure ordinale</th></tr></thead><tbody><tr><td>Q, préordres (partiels)</td><td></td><td>Intersection ∩</td><td>Fermeture transitive de l'union ∨</td><td>Treillis</td></tr><tr><td>E, équivalences</td><td>Symétrie</td><td>Intersection ∩</td><td>Fermeture transitive de l'union ∨</td><td>Treillis</td></tr><tr><td>O, ordres (partiels)</td><td>Antisymétrie</td><td>Intersection ∩</td><td>—</td><td>Inf-demi-treillis</td></tr><tr><td>W, préordres totaux</td><td>Totalité</td><td>—</td><td>Fermeture transitive de l'union ∨</td><td>Sup-demi-treillis</td></tr><tr><td>L, ordres totaux</td><td>Antisymétrie et totalité</td><td>—</td><td>—</td><td>—</td></tr></tbody></table>

L'inclusion sur l'ensemble $\mathcal{L}$ des ordres totaux, et plus généralement sur l'ensemble $\mathcal{T}$ des tournois, correspond à une structure d'antichainne, c'est-à-dire que, pour $T, T' \in \mathcal{T}$, $T \subseteq T'$ implique $T = T'$. Nous pouvons cependant munir l'ensemble $\mathcal{T}$ d'un ordre de treillis, par référence à un tournoi fixé $T_0$. Celui-ci est arbitraire, mais il est commode de choisir un ordre total comme suit : on numérote les éléments de $X$ en posant $X = \{1, 2, ..., n\}$ et on prend $T_0 = \{(i, j) \in X^2 : i \le j\}$.

Notons $T_0^d = \{(i, j) \in X^2 : j < i\}$ le tournoi (irréflexif) dual de $T_0$ ; on associe à tout tournoi $T$ la relation $I(T)$ des couples inversés dans $T$ par rapport à $T_0$, c'est-à-dire $I(T) = \{(i, j) \in T : j < i\} = T \cap T_0^d$. La correspondance $T \leftrightarrow I(T)$ établit une bijection entre l'ensemble $\mathcal{T}$ des tournois sur $X$, d'une part, et l'ensemble $P(T_0^d)$ des ensembles d'arcs inversés, d'autre part. L'ordre d'inclusion (un ordre de treillis) sur le second induit alors un ordre sur $\mathcal{T}$ par : $T \subseteq T'$ si et seulement si $I(T) \subseteq I(T')$. Le minimum pour cet ordre est $T_0$ (avec $I(T_0) = \emptyset$) et le maximum $T_0^d$ ($I(T_0^d) = T_0^d$). La restriction à $\mathcal{L}$ de l'ordre qui vient d'être défini sur $\mathcal{T}$ est encore un ordre de treillis (treillis permutoèdre), quoique de façon moins évidente [GUI 63].

Nous venons de constater que, soit directement par l'ordre d'inclusion, soit par un aménagement de celui-ci, les ensembles de relations binaires considérés sont munis de structures latticielles (c.-à-d. sont des demi-treillis ou treillis). Cette observation est renforcée par le fait que l'on retrouve de telles structures pour d'autres
modélisations des préférences ou des choix : formes valuées (ou floues) des relations [LEC 95], fonctions de choix [MON 04]. Elle a conduit à poser le problème du consensus au niveau plus abstrait des structures latticielles elles-mêmes, avec l'obtention de résultats s'appliquant à des situations diverses (cf., e.g., [MON 90b], [BAR 91], [LEC 93], [LEC 95], [DAY 03]). Nous nous plaçons désormais dans le cadre général d'un treillis ou d'un inf-demi-treillis *D* dont les éléments sont notés *s*, *t*, etc. Nous considérons un profil Π = (*t*₁, ..., *t*ᵢ, ..., *t*ⱼ) ∈ *D*sup, que nous cherchons à agréger en un élément unique *t* ∈ *D* (on se place donc dans le cas *M* = *D*). On pourra consulter [DAV 90] sur les ensembles ordonnés et treillis.

Une relation binaire *R* sur *X* est un ensemble de couples d'éléments qui peuvent chacun être vus comme une relation élémentaire. Cette décomposition se prolonge à tout demi-treillis *D* en considérant ses éléments *irréductibles*. Un élément *t* de *D* est dit *sup-irréductible* si on ne peut l'obtenir comme supremum d'une partie de *D* ne le contenant pas et, de même, *t* est *inf-irréductible* s'il n'est pas l'infimum d'une partie ne le contenant pas. Nous nous intéresserons ici au rôle des sup-irréductibles, sachant que les mêmes considérations s'appliquent aussi, quoique plus rarement en pratique, aux inf-irréductibles. Soit *t* ∈ *D* ; on note :

- *S* ou *S*(*D*) l'ensemble des sup-irréductibles de *D*;

- *S*<sub>*t*</sub> l'ensemble des sup-irréductibles *s* de *D* vérifiant *s* ≤ *t*.

On obtient ainsi une représentation des éléments de *D* par des parties de *S*, dont deux propriétés essentielles sont rappelées ci-dessous :

THEOREME 2.23.— Soit *D* un ensemble ordonné. Pour tout *t* ∈ *D*, on a *t* = ∨*S*<sub>*t*</sub> ;
pour tous *t*, *t'* ∈ *D* tels que *t* ∧ *t*' existe, on a *S*<sub>*t*∧*t*'</sub> = *S*<sub>*t*</sub>∩*S*<sub>*t*'</sub>.

La représentation *t* a *S*<sub>*t*</sub> de *D* dans *P*(*S*) est donc un *inf-morphisme*, en ce sens qu'elle préserve les infimums, et un *plongement d'ordre*, car on vérifie que, pour *t*, *t'* ∈ *D*, on a *t* ≤ *t'* ⇔ *S*<sub>*t*</sub> ⊆ *S*<sub>*t*'</sub>. Pour les treillis et demi-treillis de la table 2.1. : *S*(Q) = *S*(O) est l'ensemble des ordres sur *X* contenant un unique couple (x, y) d'éléments distincts ; *S*(E) est l'ensemble des équivalences sur *X* contenant une unique paire de couples (x, y), (y, x) d'éléments distincts ; *S*(W) est l'ensemble des ordres totaux sur *X* (on montre en effet qu'un préordre total est l'union — et le supremum — des ordres totaux qu'il contient).

Chacun des sup-irréductibles du treillis $\mathcal{T}'$ des tournois est identifiable à un
couple de $T_0^d$ et on a $S(\mathcal{T}') = \{T \in \mathcal{T} : |I(T)| = 1\}$. Quant aux sup-irréductibles du
treillis permutoèdre $\mathcal{L}$, ils sont encore associés aux couples de $T_0^d$, mais de façon
plus complexe : le sup-irréductible associé au couple $(x, y) \in T_0^d$ est le plus petit
des ordres totaux contenant ce couple.
Il est important pour la suite de noter que si $t \nsim t'$ existe, on a $S_t \cup S_{t'} \subseteq S_{t \nsim t'}$,
mais non l'égalité en général. Par exemple, considérons le treillis $Q$ des préordres
sur $X$, trois éléments $x, y, z$ de $X$ et deux préordres $Q$ et $Q'$ tels que $(x, y) \in Q$ et
$(y, z) \in Q'$. Alors, par transitivité, on a $(x, z) \in Q \lor Q'$, que le couple $(x, z)$ soit ou
non dans $Q$ ou dans $Q'$.

2.4.2. La distance de la différence symétrique dans les demi-treillis et ses éloignements

La distance de la différence symétrique définie au paragraphe 2.2.2. se généralise
aisément à tout demi-treillis D en passant par la représentation par les sup-
irréductibles qui vient d'être définie. On pose maintenant, pour t, t' ∈ D,

$$
\begin{align*}
\delta(t, t') &= |S_t \Delta S_{t'}| = |S_t \cup S_{t'}| - |S_t \cap S_{t'}| = |S_t \setminus S_{t'}| + |S_{t'} \setminus S_t| \\
&= |\{s \in S : [s \in S_t \text{ et } s \notin S_{t'}] \text{ ou } [s \notin S_t \text{ et } s \in S_{t'}]\}|.
\end{align*}
$$

Sur les treillis et inf-demi-treillis P(X²) (relations binaires), Q (préordres), Œ (équivalences), O (ordres) et T'(tournois), on retrouve le nombre de couples par lesquels deux relations R et R' diffèrent, c'est-à-dire la distance de la différence symétrique telle qu'elle a été définie plus haut. Il en est de même dans le treillis permutoèdre L. La situation est différente dans le sup-demi-treillis W (préordres totaux) où le comptage s'effectue sur les ordres totaux inclus ou non dans R et R'.

Considérons maintenant un profil Π = (t₁, ..., tᵢ, ..., t_v) ∈ D<sup>v</sup>, et définissons les
paramètres suivants : pour tout sup-irréductible s ∈ S(D),

$$
v_{\pi}(s) = |\{i \in V : s \leq t_i\}|,
$$

$$
v_{\pi}^{c}(s) = |\{i \in V : s \leq t_{i}\}|,
$$

$$
w_{\pi}(s) = v_{\pi}(s) - v_{\pi}^{c}(s).
$$

Comme plus haut, lorsqu'il n'y a pas d'ambiguïté, c'est-à-dire pratiquement
toujours, on omet l'indice $\pi$ dans ces notations. On a les égalités $v(s) + v^c(s) = v$ et
$w(s) = 2v(s) - v$. Nous dirons qu'un sup-irréductible $s$ est majoritaire si $2v(s) > v$
(c'est-à-dire si $s$ apparaît dans une majorité stricte des représentations des éléments du
profil), et équilibré si $2v(s) = v$.

Pour aborder le problème de l'agrégation du profil Π de D en un unique élément t
de D, nous exprimons l'éloignement E(Π, t) = Σ v i=1 δ(t, tᵢ) d'un profil Π à un élément
t arbitraire de D au moyen des paramètres précédents.
LEMME 2.24.—Pour $\Pi = (t_1, \dots, t_p, \dots, t_v) \in D^v$ et $t \in D$, on a :

$$E(\Pi, t) = \sum_{i=1}^{v} |S_{t_i}| - \sum_{s \in S_t} w(s).$$

Il s'agit d'une version latticielle de l'égalité (b) du lemme 2.2. de la section 2.2.3. et elle se démontre en fait de façon analogue. La quantité $-w(s)$ apparaît alors comme étant la contribution du sup-irréductible $s$ de $S_t$ à l'éloignement de $t$. De façon analogue à ce qui a été décrit plus haut, cette contribution est négative si $s$ est un sup-irréductible majoritaire, nulle s'il est équilibré, et positive sinon. Pour obtenir un éloignement aussi réduit que possible, le mieux serait donc de trouver un élément $t$ de $D$ dont la représentation $S_t$ contiendrait tous les sup-irréductibles majoritaires, éventuellement certains équilibrés, et aucun autre sup-irréductible. L'objet de la section suivante est de reconnaître ceux des demi-treillis où il existe toujours un tel élément.

### 2.4.3. Médianes dans les demi-treillis à médianes

Nous supposons maintenant que $D$ est un inf-demi-treillis, éventuellement un treillis, et nous continuons à transposer certaines notations du paragraphe 2.2.3. Pour $\Pi \in D^v$ et pour tout entier $\sigma$, nous posons :

$$S(\Pi, \sigma) = \{s \in S : v(s) \geq \sigma\}.$$

Cet ensemble sera le plus souvent noté simplement $S(\sigma)$. En particulier, en reprenant les nombres $\alpha$ et $\beta$ définis au paragraphe 2.2.3., $S(\alpha)$ est l'ensemble des sup-irréductibles majoritaires et $S(\beta) \setminus S(\alpha)$ est celui, qui est vide si $v$ est impair, des sup-irréductibles équilibrés.

PROPOSITION 2.25.—Pour tous $s, s' \in S$, $s \in S(\sigma)$ et $s' \le s$ entraînent $s' \in S(\sigma)$.

Preuve.

Si $s \in S(\sigma)$, il existe une partie $W \subseteq V$ telle que $|W| \ge \sigma$ et $s \le t_i$ pour tout $i \in W$. Alors, $s' \le s$ implique $s' \le t_i$ pour tout $i \in W$ et donc $s' \in S(\sigma)$. $\square$

Sous réserve de l'existence de ces éléments, posons $t(\sigma) = \bigvee S(\sigma)$ et $t'(\sigma) = \bigvee\{\wedge\{t_i : i \in W\} : W \subseteq V, |W| \ge \sigma\}$ (le second est un « polynôme latticiel »). Rappelons une propriété générale des inf-demi-treillis : même si $D$ n'est pas un treillis, toute partie majorée $D'$ de $D$ a un supremum, à savoir l'infimum des majorants de $D'$. En particulier, pour tout $t \in D$, le sous-ensemble ordonné $\{t' \in D : t' \le t\}$ est un treillis.
PROPOSITION 2.26. – Si l’un des éléments $t(\sigma)$ et $t'(\sigma)$ existe, l’autre existe aussi, et $t(\sigma) = t'(\sigma)$.

Preuve.

Supposons que $t'(\sigma)$ existe. Soit $s \in S(\sigma)$. Il existe donc une partie $W \subseteq V$ telle que $|W| \ge \sigma$ et $s \le t_i$ pour tout $i \in W$. Donc $s \le \bigwedge\{t_i : i \in W\} \le t'(\sigma)$ ; alors, $t'(\sigma)$ est un majorant de $S(\sigma)$, d'où l'existence de $t(\sigma)$, avec $t(\sigma) \le t'(\sigma)$.

D'autre part, selon le théorème 2.23., la représentation par les sup-irréductibles est un inf-morphisme. On a donc $S_{\wedge\{t_i : i \in W\}} = \big|_{i \in W} S_{t_i}$ qui, pour $|W| \ge \sigma$, est un sous-ensemble de $S(\sigma)$. Il s'ensuit que l'élément $t(\sigma) = \vee S(\sigma)$, dont l'existence est assurée par la première partie de la preuve, est un majorant de $\wedge_{i \in W} t_i = \vee S_{\wedge\{t_i : i \in W\}}$. Par conséquent, $t'(\sigma)$ est un supremum d'éléments tous majorés par $t(\sigma)$, ce qui entraîne $t(\sigma) \ge t'(\sigma)$.

Supposons que $t(\sigma)$ existe. Il majore chaque infimum $\wedge\{t_i : i \in W\}$ pour lequel on a $|W| \ge \sigma$, d'où l'existence de $t'(\sigma)$, et on peut appliquer ce qui précède. $\square$

D'après cette proposition, l'élément $t(\alpha)$ a une expression polynomiale $t(\alpha) = \vee\{\wedge\{t_i : i \in W\} : W \subseteq V, |W| \ge \alpha\}$ qui, rapprochée de celle apparaissant à la fin du paragraphe 2.2.3., constitue une formalisation latticielle de la règle majoritaire, et aussi une représentation $S_{t(\alpha)}$ qui contient tous les sup-irréductibles majoritaires. Mais $S_{t(\alpha)}$ contient aussi en général des sup-irréductibles qui ne sont ni majoritaires ni équilibrés.

Nous allons maintenant considérer des inf-demi-treillis particuliers, dans lesquels la représentation par les sup-irréductibles est non seulement un inf-morphisme mais aussi un sup-morphisme. Tout d'abord, un treillis $D$ est distributif s'il vérifie l'une des conditions équivalentes suivantes :

$$ (1) \text{ pour tous } t, t', t'' \in D, t \wedge (t' \vee t'') = (t \wedge t') \vee (t \wedge t''); $$

$$ (2) \text{ pour tous } t, t', t'' \in D, t \vee (t' \wedge t'') = (t \vee t') \wedge (t \vee t''); $$

$$ (3) \text{ s } \in S, D' \subseteq D \text{ et } s \le \vee D' \text{ impliquent } s \le t \text{ pour au moins un élément } t \in D; $$

$$ (4) \text{ pour tous } t, t' \in D, \text{ on a } S_t \cup S_{t'} = S_{t \vee t'}. $$

Sans démontrer complètement ces équivalences classiques, observons par exemple que, si (1) est vraie, $s \le \vee D'$ entraîne, par distributivité, $s = s \wedge (\vee D') = \vee\{s \wedge t : t \in D'\}$, d'où, s étant sup-irréductible, $s = s \wedge t'$, c'est-à-dire
$s \le t'$, pour au moins un élément $t'$ de $D'$. De même, supposons (3) vraie, et soient $t, t' \in D$ et $s \in S_{t \vee t'}$. On a $s \le t$ ou $s \le t'$, donc $S_{t \vee t'} \subseteq S_t \cup S_{t'}$, d'où (4) puisque l'inclusion inverse est toujours vraie.

Les treillis distributifs forment une classe de treillis d'autant plus importante qu'elle comprend les ensembles totalement ordonnés (avec les opérations maximum et minimum comme supremum et infimum), mais aussi les produits de tels ensembles et les treillis des parties d'un ensemble, munis de l'union et de l'intersection. Ainsi, dans les exemples précédents, les treillis $P(X^2)$ et $T'$ sont distributifs. Par extension, un inf-demi-treillis $D$ est dit distributif si, pour tout $t \in D$, le treillis $\{t' \in D : t' \le t\}$ est distributif.

Un demi-treillis à médianes [AVA 61] est un inf-demi-treillis distributif $D$ tel que $t_1 \vee t_2 \vee t_3$ existe pour tous $t_1, t_2, t_3 \in D$ tels que les trois éléments $t_1 \vee t_2, t_1 \vee t_3$ et $t_2 \vee t_3$ existent. Alors, pour tous $t, t', t'' \in D$, l'élément $(t \wedge t') \vee (t' \wedge t'') \vee (t'' \wedge t)$ existe toujours dans un tel treillis. Par un calcul algébrique sans difficulté, cette existence assure celle de $t(\alpha)$ (mais non celle de $t(\beta)$), sous sa forme de polynôme latticiel. On obtient la caractérisation suivante des médianes pour la distance $\delta$ dans de tels demi-treillis [BAN 84], qui généralise une série de résultats sur les médianes dans les treillis distributifs remontant à [BAR 61] :

THEOREME 2.27.— Soient $D$ un demi-treillis à médianes et $\Pi \in D^v$ un profil de $D$. Si $v$ est impair, $t(\alpha)$ est l'unique médiane de $\Pi$ ; si $v$ est pair, l'ensemble des médianes de $\Pi$ est $\text{Méd}_D(\Pi) = \{\vee S' : S(\alpha) \subseteq S' \subseteq S(\beta) \text{ et } \vee S' \text{ existe}\}$.

Preuve.

On a observé après le lemme 2.24. qu'un élément $t$ vérifiant $S(\alpha) \subseteq S_t \subseteq S(\beta)$ minimise $E(\Pi, t)$, s'il existe. D'après ce qui précède et la proposition 2.26., $t(\alpha) = \vee S(\alpha)$ existe pour tout profil d'un demi-treillis à médianes. Soit $s \in S$ tel que $s \le t(\alpha)$. D'après la propriété (3) des treillis distributifs, il existe $s' \in S(\alpha)$ tel que $s \le s'$, d'où $s \in S(\alpha)$ d'après la proposition 2.25. Donc $S_{t(\alpha)} = S(\alpha)$, ce qui établit que $t(\alpha)$ est une médiane. On montre de même que $s \le \vee S'$ avec $S' \subseteq S(\beta)$ entraîne $s \in S(\beta)$. Donc les éléments qui ont le même éloignement que $S(\alpha)$ sont ceux de la forme $\vee S'$ avec $S(\alpha) \subseteq S' \subseteq S(\beta)$. Si $v$ est impair, on a $S(\alpha) = S(\beta)$ et $t(\alpha)$ est la seule médiane. $\square$

En particulier, si $D$ est un treillis distributif, on a simplement $\text{Méd}_D(\Pi) = \{t \in D : t(\alpha) \le t \le t(\beta)\}$, ce qui généralise la proposition 2.4. portant sur les médianes d'un profil de relations binaires. Nous reviendrons plus loin (paragraphe 2.4.5.) sur l'intérêt de la prise en compte des demi-treillis à médianes.

Il est implicite, en particulier dans le théorème 2.22., que la procédure médiane peut être considérée en tant que multi-procédure d'agrégation associant à tout profil de
longueur finie $\Pi \in D^* = \bigcup_{v \in N} D^v$ une partie non vide $c(\Pi) \subseteq D$. Dans les demi-treillis à médianes, cette procédure a été caractérisée axiomatiquement [MCM 00]. Rappelons qu'un élément $s$ d'un inf-demi-treillis $D$ est sup-irréductible si et seulement s'il existe un élément $s^-$ unique de $D$ tel que $s^- \le s$, $s^- \ne s$, et $s^- \le s' \le s$ entraîne $s' = s^-$ ou $s' = s$. Pour deux profils $\Pi = (t_1, ..., t_i, ..., t_v)$ et $\Pi' = (t'_1, ..., t'_j, ..., t'_{v'}) \in D^*$, la *concaténation* de $\Pi$ et $\Pi'$ est le profil $\Pi\Pi' = (t_1, ..., t_v, t'_1, ..., t'_{v'})$. On a alors le théorème 2.28. ci-dessous. Même si les structures en jeu et l'énoncé différent notablement, on remarquera que la propriété de consistance donnée ci-dessous est une généralisation directe de celle apparaissant dans la caractérisation de la procédure médiane sur les profils d'ordres totaux évoquée à la fin du paragraphe 2.3.6.

THEOREME 2.28.— Soient $D$ un demi-treillis à médianes et une multi-procédure d'agrégation $c: D^* \rightarrow (P(D) \setminus \{\emptyset\})$. Alors $c$ est la procédure médiane si et seulement si elle vérifie les propriétés :

*Condorcet :* $\Pi \in D^v$ avec $v$ pair, $s \in S(D)$, $2v(s) = v$, $t \in D$ et $t \nsim s$ existe entraînent $[t \nsim s^- \in c(\Pi) \Leftrightarrow t \nsim s \in c(\Pi)]$.

*Consistance :* $\Pi, \Pi' \in D^*$ et $c(\Pi) \cap c(\Pi') \ne \emptyset$ entraînent $c(\Pi\Pi') = c(\Pi) \cap c(\Pi')$.

*Conformité :* $\Pi \in D^1$ et $\Pi = (t)$ entraînent $c(\Pi) = \{t\}$.

Dans ce paragraphe, nous avons, suivant en cela la majeure partie de la littérature, développé le cas des inf-demi-treillis et donc considéré des (inf-)demi-treillis à médianes. Bien évidemment, tout ce qui précède peut être repris pour des sup-demi-treillis en échangeant les rôles de l'infimum et du supremum (les inf-irréductibles prenant donc la place des sup-irréductibles). Nous verrons au paragraphe 2.4.5. que le sup-demi-treillis $\mathcal{W}$ des préordres totaux est justement un « sup-demi-treillis à médianes ».

### 2.4.4. Autres demi-treillis

Les demi-treillis à médianes constituent donc un type de structure où les médianes ont une caractérisation simple. De plus, la médiane $t(\alpha)$ est aisément calculable, pourvu que la détermination de l'ensemble $S_t$ pour tout $t \in S$ et le calcul du supremum soient aisés. La recherche des médianes pour la distance de la différence symétrique dans un treillis ou demi-treillis d'un autre type devient difficile [LEC 94].

Dans un inf-demi-treillis distributif qui n'est pas à médianes, les conclusions du théorème 2.27. s'appliquent à tout profil pour lequel $t(\alpha)$ existe. Autrement, on
recherche les éléments $t$ de $D$ de la forme $t = (\vee S_1) \vee (\vee S_2)$ où $S_1$ est un ensemble de sup-irréductibles majoritaires tel que $\vee S_1$ existe et maximise $\sum_{s \in S_1} w(s)$ sous cette condition et $S_2$ est un ensemble de sup-irréductibles équilibrés tel que $t$ existe, un problème qui peut être difficile.

Lorsque $D$ est un inf-demi-treillis non distributif, on n'est même plus assuré que $t(\alpha)$ est une médiane, car la représentation $S_{t(\alpha)}$ peut contenir des sup-irréductibles $s$ appartenant à $S \setminus S(\beta)$, donc pour lesquels $w(s)$ est négatif. Il reste toutefois des liens entre les médianes et la règle majoritaire, qui s'appliquent, par exemple, au treillis des équivalences (ou partitions) [BAR 95b] comme à celui des préordres, ou au demi-treillis des ordres [LEC 03] :

THEOREME 2.29.— Soit D un inf-demi-treillis. Pour tout profil $\Pi$ de $D$ tel que $t(\beta)$ existe et pour toute médiane $t$ de $\Pi$, on a l'inégalité $t \le t(\beta)$ ; pour tout profil $\Pi$ tel que $t(\alpha)$ existe et pour toute médiane $t$ de $\Pi$, il existe une médiane $t'$ telle que $t' \le t \wedge t(\alpha)$ et que tout élément $t''$ vérifiant $t' \le t'' \le t$ est une médiane.

### 2.4.5. Applications

On a déjà noté que le théorème 2.27., qui caractérise les médianes dans, entre autres, les treillis distributifs, s'applique aux treillis de parties d'un ensemble, et donc aux treillis $P(X^2)$ des relations binaires et $\mathcal{T}'$ des tournois, précédemment décrits. Une classe de treillis distributifs (généralisant le treillis des parties d'un ensemble), est celle des produits directs d'ordres totaux. Ces treillis apparaissent naturellement dans de nombreux problèmes et modélisations. Ainsi, considérons par exemple une évaluation multicritère avec $k$ critères, chacun prenant ses valeurs dans un ensemble totalement ordonné fini $D^i$ ; un élément $t$ de $D$ est alors identifiable à un $k$-uple $(t^1, ..., t^i, ..., t^k) \in D = D^1 \times ... D^i \times ... \times D^k$. On vérifie que les médianes d'un $v$-uple de tels objets s'obtiennent en prenant la ou les valeurs médianes sur chaque critère.

Un autre exemple est celui des fonctions de choix vérifiant certaines conditions. Une fonction de choix sur $X$ est une application $ch: P*(X) \rightarrow P*(X)$ (comme en section 2.2.1., $P*(X)$ désigne l'ensemble des parties non vides de $X$) vérifiant, pour tout $Y \subseteq X$, $ch(Y) \subseteq Y$. L'idée est qu'une telle fonction exprime la sélection qu'opère un agent parmi les éléments de toute partie $Y$, et il est alors naturel de considérer le choix social sous l'angle du consensus de fonctions de choix. Parmi les nombreux axiomes définissant des classes intéressantes de fonctions de choix (cf. [ALE 02], [MON 04]), on trouve la propriété d'hérédité (H) suivante :
(H) Pour tous $Y, Z \subseteq X$ tels que $Y \subseteq Z$, on a $Y \cap ch(Z) \subseteq ch(Y)$.

L'ensemble $\mathcal{X}$ des fonctions de choix sur $X$ est naturellement ordonné, en posant, pour $ch, ch' \in \mathcal{X}$, $ch \le ch'$ si $ch(Y) \subseteq ch'(Y)$ pour tout $Y \subseteq X$. On montre alors que le sous-ensemble ordonné $\mathcal{X}_H$ des fonctions de choix satisfaisant la condition d'héritage est un treillis distributif.

L'extension aux demi-treillis à médianes constituée par le théorème 2.27. se justifie par le fait que l'on rencontre fréquemment de tels demi-treillis, qui ne sont pas des treillis. En effet, considérons un ensemble fini $E$ muni d'une relation symétrique $C$ modélisant une idée de « compatibilité ». On s'intéresse à l'ensemble $\mathcal{F}$ des parties $F$ de $E$ dont les éléments sont deux à deux compatibles (en d'autres termes, la relation $C$ est connexe sur $F$, qui est une *clique* au sens de la théorie des graphes). On vérifie alors que, ordonné par inclusion, $\mathcal{F}$ est un demi-treillis à médianes. Ainsi, si $E$ est un ensemble ordonné et $C$ sa relation de comparabilité, les cliques de $C$ correspondent aux parties totalement ordonnées de $E$ (dites aussi les *chaînes de $C$*) et elles constituent un tel demi-treillis.

Voici un exemple de demi-treillis à médianes de ce type. Associons à tout préordre total $W$ sur $X$ la famille (totalement odonnée par inclusion) $N(W)$ de parties de $X$ définie par $N(W) = \{\{y \in X : y \in W\}, x \in X\}$. On vérifie qu'on définit ainsi une bijection entre, d'une part, l'ensemble $W$ des préordres totaux sur $X$ et, d'autre part, l'ensemble $\mathcal{N}$ des chaînes de $P(X)$ contenant $X$, avec de plus l'équivalence $W \subseteq W' \Leftrightarrow N(W') \subseteq N(W)$. D'après ce qui précède, $\mathcal{N}$ est un demi-treillis à médianes. Comme l'ordre d'inclusion sur $\mathcal{N}$ est dual du sup-demi-treillis $W$ décrit dans la table 2.1., celui-ci est bien un sup-demi-treillis à médianes. Les sup-irréductibles de $\mathcal{N}$ correspondent aux inf-irréductibles de $W$, et la distance de la différence symétrique $\delta$ sur $\mathcal{N}$ compte les parties de $X$ présentes dans l'un exactement des $N(W)$ et $N(W')$. Toutefois, avec cette métrique, on obtient souvent des médianes qui contiennent peu de parties de $X$ et correspondent donc à des préordres totaux médians peu discriminants.

Les fonctions de choix vérifiant la condition d'Arrow (A) suivante se rattachent à cet exemple.

(A) Pour tous $Y, Z \subseteq X$ tels que $Y \subseteq Z$ et $Y \cap ch(Z) \neq \emptyset$, $Y \cap ch(Z) = ch(Y)$.

La condition (A) implique (H) et caractérise les fonctions de choix qui sont *rationalisables par un préordre total*, c'est-à-dire que, si $ch$ vérifie (A), il existe un préordre total $W$ sur $X$ tel que $ch(Y)$ est l'ensemble des éléments maximaux dans $Y$ pour $W$. L'ensemble $\mathcal{X}_A$ des fonctions de choix satisfaisant la condition (A) est un demi-treillis à médianes, isomorphe à $\mathcal{N}$ et dual de $W$.
Références

[ALE 02] ALESKEROV F., MONJARDET B., *Utility maximisation, choice and preference*, Springer-Verlag, Berlin, 2002.

[ALO 90] ALON N., « The maximum number of Hamiltonian paths in tournaments », *Combinatorica* 10, pp. 319-324, 1990.

[ARD 84] ARDITTI D., « Un nouvel algorithme de recherche d'un ordre induit par des comparaisons par paires », in *Data analysis and informatics III*, E. Diday, M. Jambu, L. Lebart, J. Pagès, R. Tomassone (éds), North Holland, Amsterdam, pp. 323-343, 1984.

[ARR 51] ARROW K.J., *Social choice and individual values*, Wiley, New York, 1951 ; on préférera l'édition de 1963.

[AVA 61] AVANN S.P., « Metric ternary distributive semi-lattices », *Proc. Amer. Math. Soc.* 12, pp. 407-414, 1961.

[BAN 84] BANDELT H.J., BARTHELEMY J.-P., « Medians in median graphs », *Discrete Applied Math.* 8, pp. 131-142, 1984.

[BAR 61] BARBUT M., « Médiane, distributivité, éloignements », *Publications du Centre de mathématiques sociales*, Paris, 1961, et *Math. Sci. hum.* 70, pp. 5-31, 1980.

[BAR 67] BARBUT M., « Médiane, Condorcet et Kendall », *Note SEMA*, Paris, 1967, et *Math. Sci. hum.* 69, pp. 5-13, 1980.

[BAR 76] BARTHELEMY J.-P., « Sur les éloignements symétriques et le principe de Pareto », *Mathématiques et Sciences humaines* 56, pp. 97-125, 1976.

[BAR 81] BARTHÉLEMY J.-P., MONJARDET B., « The median procedure in cluster analysis and social choice theory », *Mathematical Social Sciences* 1, pp. 235-267, 1981.

[BAR 89] BARTHÉLEMY J.-P., GUENOCHE A., HUDRY O., « Median linear orders: heuristics and a branch and bound algorithm », *European Journal of Operational Research* 41, pp. 313-325, 1989.

[BAR 91] BARTHÉLEMY J.-P., JANOWITZ M.F., « A formal theory of consensus », *SIAM J. Discr. Math.* 4, pp. 305-322, 1991.

[BAR 92] BARTHELEMY J.-P., COHEN G., LOBSTEIN A., *Complexité algorithmique et problèmes de communications*, Masson, Paris, 1992.

[BAR 95a] BARTHELEMY J.-P., HUDRY O., ISAAK G., ROBERTS F.S., TESMAN B., « The reversing number of a digraph », *Discrete Applied Mathematics* 60, pp. 39-76, 1995.

[BAR 95b] BARTHÉLEMY J.-P., LECLERC B., « The median procedure for partitions », in *Partitioning data sets*, I.J. Cox, P. Hansen et B. Julesz (éds), *DIMACS Series in Discrete Mathematics and Theoretical Computer Science* 19, Amer. Math. Soc., Providence, RI, pp. 3-34, 1995.

[BEC 67] BECKER O., « Das Helmstädtersche Reihenfolgeproblem — die Effizienz verschiedener Näherungsverfahren », in *Computers Uses in the Social Science*, Vienne, Autriche, 1967.
[BER 72] BERMOND J.-C., « Ordres à distance minimum d'un tournoi et graphes partiels sans circuits maximaux », *Mathématiques et Sciences humaines* 37, pp. 5-25, 1972.

[BLA 48] BLACK D., « On the rationale of group decision-making », *Journal of Political Economy* 56, pp. 23-34, 1948.

[CAM 99] CAMPOS V., LAGUNA M., MARTI R., « Scatter search for the linear ordering problem », in *New Ideas in Optimization*, D. Corne, M. Dorigo, F. Glover (éds), McGraw-Hill, pp. 331-339, 1999.

[CAM 01] CAMPOS V., GLOVER F., LAGUNA M., MARTI R., « An experimental evaluation of a scatter search for the linear ordering problem », *Journal of Global Optimization* 21 (4), pp. 397-414, 2001.

[CAR 85] CARITAT M.J.A.N., marquis de CONDORCET, *Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix*, Paris, 1785.

[CHA 96a] CHANAS S., KOBYLANSKI P., « A new heuristic algorithm solving the linear ordering problem », *Computational optimization and applications* 6, pp. 191-205, 1996.

[CHA 96b] CHARON I., HUDRY O., WOIRGARD F., « Ordres médians et ordres de Slater des tournois », *Mathématiques, Informatique et Sciences humaines* 133, pp. 23-56, 1996.

[CHA 97] CHARON I., GUENOCHE A., HUDRY O., WOIRGARD F., « New results on the computation of median orders », *Discrete Mathematics* 165-166, pp. 139-154, 1997.

[CHA 98] CHARON I., HUDRY O., « Lamarckian genetic algorithms applied to the aggregation of preferences », *Annals of Operations Research* 80, pp. 281-297, 1998.

[CHA 02] CHARON I., HUDRY O., « Méthodes de bruitage », in *Optimisation approchée en recherche opérationnelle*, M. Pirlot et J. Teghem (éds), Hermès, pp. 101-128, 2002.

[CHA 04] CHARON I., HUDRY O., « A branch and bound algorithm to solve the linear ordering problem for weighted tournaments », *Discrete Applied Mathematics*, 2004, à paraître.

[CON 00] CONGRAM R. K., « Polynomially searchable exponential neighbourhoods for sequencing problems in combinatorial optimisation », thèse de doctorat de l'université de Southampton, Grande-Bretagne, 2000.

[COO 88] COOK W.D., GOLAN I., KRESS M., « Heuristics for ranking players in a round robin tournament », *Computers and Operations Research* 15 (2), pp. 135-144, 1988.

[DAV 90] DAVEY B.A., PRIESTLEY H.A., *Introduction to lattices and order*, Cambridge University Press, Cambridge, 1990.

[DAY 03] DAY W.H.E., MCMORRIS F.R., *Axiomatic Consensus Theory in Group Choice and Biomathematics*. Frontiers in applied mathematics 29, SIAM, Philadelphia, 2003.

[DEB 87] DEBORD B., « Caractérisation des matrices de préférences nettes et méthodes d'agrégation associées », *Mathématiques et Sciences humaines* 97, pp. 5-17, 1987.

[FEL 73] FELDMAN J., « Pôles, intermédiaires et centres dans un groupe d'opinions », *Mathématiques et Sciences humaines* 43, pp. 39-54, 1973.
[GAR 79] GAREY M.R., JOHNSON D.S., *Computers and intractability, a guide to the theory of NP-completeness*, Freeman, New York, 1979.

[GOD 83] GODDARD S.T., « Tournament rankings », *Management Science* 29 (12), pp. 1385-1392, 1983.

[GRÖ 84] GRÖTSCHEL, M., JÜNGER M., REINELT G., « Optimal triangulation of large real-world input-output-matrices », *Statistische Hefte* 25, pp. 261-295, 1984.

[GUÉ 95] GUENOCHE A., « How to choose according to partial evaluations », in *Advances in Intelligent Computing*, B. Bouchon-Meunier, R.R. Yager, L.A. Zadeh (éds), IPMU'94, *Lecture Notes in Computer Sciences* n° 945, Springer-Verlag, Berlin-Heidelberg, pp. 611-618, 1995.

[GUI 52] GUILBAUD G. Th., « Les théories de l'intérêt général et le problème logique de l'agrégation », *Économie appliquée* 5, pp. 501-584, 1952. Repris dans *Éléments de la théorie des jeux*, Dunod, Paris, 1968.

[GUI 63] GUILBAUD G. Th., ROSENSTIEHL P., « Analyse algébrique d'un scrutin », *Math. Sci. hum.* 4, pp. 9-33, 1963.

[HUD 89] HUDRY O., *Recherche d'ordres médians : complexité, algorithmique et problèmes combinatoires*, thèse de l'ENST, Paris, 1989.

[HUD 97] HUDRY O., « Algorithms for the aggregation of ordinal preferences: a review », actes de la *First Conference on Operations and Quantitative Management (ICOQM)*, pp. 169-176, 1997.

[JAC 69] JACQUET-LAGREZE É., « L'agrégation des opinions individuelles », *Informatique et Sciences humaines* 4, pp. 1-21, 1969.

[JOR 69] JORDAN C., « Sur les assemblages de lignes », *Journal für die reine und andgewandte Mathematik* 70, pp. 185-190, 1869.

[JÜN 85] JÜNGER M., *Polyhedral combinatorics and the acyclic subdigraph problem*, Heldermann Verlag, Berlin, 1985.

[KAY 95] KAYKOBAD M., AHMED Q.N.U., SHAFIQUL KHALID A.T.M., BAKHTIAR R.-A., « A new algorithm for ranking players of a round-robin tournament », *Computers and Operations Research* 22 (2), pp. 221-226, 1995.

[KEM 59] KEMENY J.G., « Mathematics without numbers », *Daedalus* 88, pp. 577-591, 1959.

[KEN 38] KENDALL M.G., *Rank correlation methods*, Hafner, New York, 1938.

[KEN 57] KENDALL M.G., BUCKLAND W.R., *A dictionary of statistical terms*, Oliver and Boyd, Édimbourg, 1957.

[LAG 99] LAGUNA M., MARTI R., CAMPOS V., « Intensification and diversification with elite tabu search solutions for the linear ordering problem », *Computers and Operations Research* 26 (12), pp. 1217-1230, 1999.
[LAP 74] LAPLACE P.-S., *Mémoire sur la probabilité des causes par les événements, Œuvres complètes, tome VIII, pp. 141-153, 1774.* Repris dans *Théorie analytique*, livre 2, chapitre 4, 1812.

[LAS 97] LASLIER J.-F., *Tournament Solutions and Majority Voting*, Springer, Berlin, Heidelberg, New York, 1997.

[LEC 93] LECLERC B., « Lattice valuations, medians and majorities », *Discrete Mathematics* 111, pp. 345-356, 1993.

[LEC 94] LECLERC B., « Medians for weight metrics in the covering graphs of semilattices », *Discrete Applied Math.* 49, pp. 281-297, 1994.

[LEC 95] LECLERC B., MONJARDET B., « Latticial Theory of Consensus », in *Social Choice, Welfare, and Ethics*, W. Barnett, H. Moulin, M. Salles, N. Schofield (éds), Cambridge University Press, Cambridge, pp. 145-160, 1995.

[LEC 03] LECLERC B., « The median procedure in the semilattice of orders », *Discrete Applied Math.* 127, pp. 241-269, 2003.

[MCG 53] MCGARVEY D., « A theorem on the construction of voting paradoxes », *Econometrica* 21, pp. 608-610, 1953.

[MCM 00] MCMORRIS F.R., MULDER H.M., POWERS R.C., « The median function on median graphs and semilattices », *Discrete Applied Math.* 101, pp. 221-230, 2000.

[MEN 00] MENDONÇA D., RAGHAVACHARI M., « Comparing the efficacy of ranking methods for multiple round-robin tournaments », *European Journal of Operational Research* 123, pp. 593-605, 2000.

[MIT 96] MITCHELL J.E., BORCHERS B., « Solving real world linear ordering problems using a primal-dual interior point cutting plane method », *Annals of Operations Research* 62, pp. 253-276, 1996.

[MIT 00] MITCHELL J.E., BORCHERS B., « Solving linear ordering problems with a combined interior point/simplex cutting plane algorithm », in *High Performance Optimization*, H.L. Frenk, K. Roos, T. Terlaky, S. Zhang (éds), Kluwer Academic Publishers, Dordrecht, Pays-Bas, pp. 349-366, 2000.

[MON 73] MONJARDET B., « Tournois et ordres médians pour une opinion », *Mathématiques et Sciences humaines* 43, pp. 55-73, 1973.

[MON 80] MONJARDET B., « Théorie et applications de la médiane dans les treillis distributifs », *Annals of Discrete Math.*, pp. 87-91, 1980.

[MON 90a] MONJARDET B., « Sur diverses formes de la règle de Condorcet d'agrégation des préférences », *Math. Inf. Sci. hum* 111, pp. 61-71, 1990.

[MON 90b] MONJARDET B., « Arrowian characterizations of latticial federation consensus functions », *Mathematical Social Sciences* 20, pp. 51-71, 1990.

[MON 04] MONJARDET B., RADERANIRINA V., « Lattices of choice functions and consensus problems », *Social Choice and Welfare*, 2004, à paraître.
[MSH 03] *Théorie du choix social : cinquantenaires*, B. Monjardet, O. Hudry (éds), *Mathématiques et Sciences humaines* 163, 2003.

[POL 86] POLJAK S., TURZIK D., « A polynomial time heuristic for certain subgraph optimization problems with guaranteed lower bound », *Discrete Mathematics* 58, pp. 99-104, 1986.

[POL 88] POLJAK S., RÖDL V., SPENCER J., « Tournament ranking with expected profit in polynomial time », *SIAM Journal Disc. Math.* 1 (3), pp. 372-376, 1988.

[REI 85] REINELT G., *The linear ordering problem : algorithms and applications*, Research and Exposition in Mathematics 8, Heldermann Verlag, Berlin, 1985.

[REM 66] REMAGE R., THOMPSON W.A., « Maximum likelihood paired comparison rankings », *Biometrika* 53, pp. 143-149, 1966.

[SCH 03] SCHIAVINOTTO T., STÜTZLE T., « Search space analysis of the linear ordering problem », in *Applications of Evolutionary Computing*, G.R. Raidl et alii (éds), Lecture Notes in Computer Science 2611, Springer Verlag, Berlin, Allemagne, pp. 322-333, 2003.

[SHO 54] SHOLANDER M., « Medians, lattices and trees », *Proc. Amer. Math. Soc.* 5, pp. 808-812, 1954.

[SLA 61] SLATER P., « Inconsistencies in a schedule of paired comparisons », *Biometrika* 48, pp. 303-312, 1961.

[SLA 78] SLATER P.J., « Centers to centroids in graphs », *Journal of Graph Theory* 2, pp. 209-222, 1978.

[SMI 74] SMITH A.F.M., PAYNE C.D., « An algorithm for determining Slater's *i* and all nearest adjoining orders », *British Journal of Mathematical and Statistical Psychology* 27, pp. 49-52, 1974.

[VAZ 03] VAZIRANI V.V., *Approximation Algorithms*, Springer, Berlin, 2003.

[WAK 86] WAKABAYASHI Y., *Aggregation of binary relations: algorithmic and polyhedral investigations*, thèse de doctorat de l'université d'Augsbourg, 1986.

[WOI 97] WOIRGARD F., *Recherche et dénombrement des ordres médians des tournois*, thèse de doctorat de l'ENST, Paris, 1997.

[YOU 63] YOUNGER D.H., « Minimum feedback arc sets for a directed graph », *IEEE Trans. of the profes. tech. group in circuit theory* 10 (2), pp. 238-245, 1963.

[YOU 78] YOUNG H.P., LEVENGLICK A., « A Consistent Extension of Condorcet's Election Principle », *SIAM Journal on Applied Mathematics* 35, pp. 285-300, 1978.

[YOU 88] YOUNG H.P., « Condorcet Theory of Voting », *American Political Science Review* 82, pp. 1231-1244, 1988.

[ZEL 68] ZELINKA B.L., « Median and peripherian of trees », *Arch. Math. (Brno)*, pp. 87-95, 1968.