Tw-02843 RR 215

IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

AGRÉGATION TYPOLOGIQUE
DE DONNÉES
DE PRÉFÉRENCES

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

J. LEMAIRE

Rapport de Recherche N° 215
Février 1977
# AGRÉGATION TYPOLOGIQUE DE DONNÉES DE PRÉFÉRENCES*

Jacques Lemaire

L.A.S.S.Y.

I.U.T., 41 bld Napoléon III

06041 - Nice Cédex

---

## Résumé :

De nombreuses procédures d'agrégation de données de préférences peuvent être formulées en termes métriques. On peut alors les intégrer dans les phases de recherche des noyaux d'un algorithme du type : nuées dynamiques. L'algorithme obtenu permet de déterminer simultanément et de manière optimale :

- une partition en k classes de l'ensemble des données de préférences,

- une représentation des classes formées par k structures ordinales décelant ainsi les principaux groupes d'opinions et leurs tendances.

## Abstract :

Numerous processes dealing with aggregation of preferences can be formulated with metric terms. Then, they can be included in the kernels searching steps of an algorithm such as a dynamic clustering one. One can obtain an algorithm which gives simultaneously with optimal properties :

- a partition of the data set in k classes,

- a representation of these classes with k ordinal structures detecting the main classes of opinions and their tendencies.

<footnote>* Présenté par l'équipe de Classification Automatique et Reconnaissance des Formes.</footnote>
# 1 INTRODUCTION

I et X désignent deux ensembles finis. $|X| = p$. Les (*) éléments de I seront appelés _individus_ et ceux de X _objets_. A chaque élément de I est associée une relation de préférences sur X.

# EXEMPLE

$X = \{1,2,3,4,5,6,7\}$ modélise 7 essences végétales naturelles:

1: géranium

2: menthe

3: marjolaine

4: citral

5: romarin

6: ylan-ylan

7: néroli

40 individus doivent classer ces essences en donnant un _ordre_ ou un _préordre total_ sur X (cf M. BARBUT, B. MONJARDET (03) pour des précisions sur ce type de relations de préférences): (**)

<table><tr><td>1</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr><tr><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td></tr><tr><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td></tr><tr><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td></tr><tr><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td></tr><tr><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td></tr><tr><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td></tr></table>

<footnote>(*) $|E|$ désigne le nombre d'éléments de l'ensemble E.</footnote>

<footnote>(**) Un _préordre total_ sur X est une relation réflexive, transitive et totale sur X. Un _ordre total_ est un préordre total antisymétrique. Si w est un préordre total sur X, on notera: $(x,y)\in w$ par $x>^w y$, $(x,y)\notin w$ et $(y,x)\notin w$ par $x>^w y$, $(x,y)\notin w$ et $(y,x)\notin w$ par $x=y$. Enfin, on utilisera aussi la notation: $X_{1w} > X_{2w} > \dots > X_{qw}$ où figurent les classes d'équivalences de la relation $\equiv_w$ en explicitant éventuellement chacune d'elles.</footnote>
<table><tr><td>INDI. NO 14</td><td>2</td><td>></td><td>4</td><td>></td><td>5</td><td>=</td><td>6</td><td>></td><td>3</td><td>=</td><td>7</td><td>=</td><td>1</td></tr><tr><td>INDI. NO 15</td><td>7</td><td>></td><td>5</td><td>></td><td>6</td><td>></td><td>2</td><td>></td><td>3</td><td>></td><td>4</td><td>></td><td>1</td></tr><tr><td>INDI. NO 16</td><td>2</td><td>></td><td>4</td><td>></td><td>5</td><td>></td><td>6</td><td>></td><td>7</td><td>=</td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 17</td><td>4</td><td>=</td><td>7</td><td>></td><td>2</td><td>></td><td>6</td><td>=</td><td>3</td><td>></td><td>5</td><td>=</td><td>1</td></tr><tr><td>INDI. NO 18</td><td>4</td><td>></td><td>2</td><td>></td><td>5</td><td>></td><td>6</td><td>></td><td>7</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 19</td><td>4</td><td>></td><td>6</td><td>></td><td>7</td><td>></td><td>5</td><td>></td><td>2</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 20</td><td>4</td><td>></td><td>6</td><td>></td><td>3</td><td>></td><td>2</td><td>></td><td>1</td><td>></td><td>7</td><td>></td><td>5</td></tr><tr><td>INDI. NO 21</td><td>4</td><td>></td><td>2</td><td>></td><td>7</td><td>></td><td>5</td><td>></td><td>1</td><td>></td><td>3</td><td>></td><td>6</td></tr><tr><td>INDI. NO 22</td><td>6</td><td>></td><td>2</td><td>></td><td>5</td><td>></td><td>4</td><td>></td><td>3</td><td>=</td><td>7</td><td>></td><td>1</td></tr><tr><td>INDI. NO 23</td><td>2</td><td>></td><td>6</td><td>></td><td>7</td><td>=</td><td>5</td><td>></td><td>4</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 24</td><td>6</td><td>></td><td>5</td><td>></td><td>2</td><td>></td><td>4</td><td>></td><td>7</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 25</td><td>4</td><td>></td><td>2</td><td>></td><td>3</td><td>=</td><td>5</td><td>=</td><td>6</td><td>></td><td>7</td><td>></td><td>1</td></tr><tr><td>INDI. NO 26</td><td>4</td><td>></td><td>7</td><td>></td><td>6</td><td>></td><td>5</td><td>></td><td>3</td><td>></td><td>2</td><td>></td><td>1</td></tr><tr><td>INDI. NO 27</td><td>6</td><td>></td><td>7</td><td>></td><td>1</td><td>></td><td>3</td><td>></td><td>2</td><td>></td><td>5</td><td>></td><td>4</td></tr><tr><td>INDI. NO 28</td><td>6</td><td>></td><td>2</td><td>></td><td>4</td><td>></td><td>3</td><td>></td><td>7</td><td>></td><td>1</td><td>></td><td>5</td></tr><tr><td>INDI. NO 29</td><td>4</td><td>></td><td>2</td><td>=</td><td>5</td><td>></td><td>6</td><td>></td><td>3</td><td>=</td><td>7</td><td>></td><td>1</td></tr><tr><td>INDI. NO 30</td><td>6</td><td>></td><td>4</td><td>></td><td>2</td><td>></td><td>5</td><td>></td><td>3</td><td>></td><td>7</td><td>></td><td>1</td></tr><tr><td>INDI. NO 31</td><td>4</td><td>=</td><td>2</td><td>=</td><td>5</td><td>></td><td>6</td><td>=</td><td>3</td><td>></td><td>7</td><td>=</td><td>1</td></tr><tr><td>INDI. NO 32</td><td>4</td><td>></td><td>7</td><td>></td><td>5</td><td>></td><td>2</td><td>></td><td>6</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 33</td><td>6</td><td>=</td><td>7</td><td>></td><td>2</td><td>=</td><td>4</td><td>></td><td>5</td><td>=</td><td>1</td><td>=</td><td>3</td></tr><tr><td>INDI. NO 34</td><td>7</td><td>></td><td>6</td><td>></td><td>5</td><td>></td><td>2</td><td>></td><td>4</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 35</td><td>4</td><td>></td><td>2</td><td>></td><td>6</td><td>></td><td>5</td><td>></td><td>7</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 36</td><td>5</td><td>></td><td>2</td><td>></td><td>4</td><td>></td><td>7</td><td>></td><td>3</td><td>></td><td>6</td><td>></td><td>1</td></tr><tr><td>INDI. NO 37</td><td>6</td><td>=</td><td>7</td><td>></td><td>3</td><td>=</td><td>2</td><td>=</td><td>4</td><td>=</td><td>5</td><td>></td><td>1</td></tr><tr><td>INDI. NO 38</td><td>6</td><td>></td><td>4</td><td>></td><td>2</td><td>></td><td>5</td><td>></td><td>7</td><td>></td><td>3</td><td>></td><td>1</td></tr><tr><td>INDI. NO 39</td><td>3</td><td>></td><td>6</td><td>></td><td>5</td><td>></td><td>7</td><td>></td><td>1</td><td>></td><td>2</td><td>></td><td>4</td></tr><tr><td>INDI. NO 40</td><td>4</td><td>></td><td>5</td><td>></td><td>3</td><td>></td><td>6</td><td>></td><td>7</td><td>></td><td>2</td><td>></td><td>1</td></tr></table>

Agréger ces relations de préférences consiste à les résumer au mieux par une ou plusieurs relations de préférences sur X d'un certain type. Par exemple, si d désigne la distance de la différence symétrique sur l'ensemble des parties de XxX: si A, B, C, XxX, d(A,B)=|AΔB|, et si wᵢ est le préordre total sur X associé à l'individu i, on appelle ordre total médian (M. BARBUT, B. MONJARDET (03)) toute solution du problème:

(1-1)

$$ \begin{array}{ll} \min & \sum d(w, w_i) \\ \text{ordre total } i \in I \\ \text{sur } X \end{array} $$

Ici, la seule solution de ce problème est définie par:

(cf (4-1-1) pour plus de précisions).

La qualité de ce résumé peut être appréciée en moyennant les tau de KENDALL:

$$ \tau_I = \frac{\sum \tau(w, w_i)}{|I|} $$
où $\tau(w, w_i) = 1 - 2d(w, w_i)/p(p-1)$, $\tau_I$ est toujours compris entre 0 et 1 et les meilleurs résumés correspondent à $\tau_I \approx 1$ (E. JACQUET-LAGREZE (18)). Ici $\tau_I = 0,44$, ce qui n'est pas fameux!

Dans une telle situation, il est naturel de tenter une description locale des données individuelles. Par exemple, la recherche d'une partition de $I$ en 3 classes telles que chacune d'elles soit résumée au mieux par un ou plusieurs ordres médians permet d'améliorer très sensiblement la qualité de ces résumés.
On obtient ici avec notre algorithme:

Classe $C_1 = \{5,7,9,10,14,16,18,20,25,28,29,30,31,35,36,38,40\}$

un ordre total médian: $4>2>5>6>3>7>1$
$w_1 w_1 w_1 w_1 w_1 w_1$

$$ \tau_{C_1} = 0,66 $$

Classe $C_2 = \{2,3,6,8,13,15,19,22,23,24,26,27,33,34,37,39\}$

un ordre total médian: $6>7>5>2>4>3>1$
$w_2 w_2 w_2 w_2 w_2 w_2$

$$ \tau_{C_2} = 0,59 $$

Classe $C_3 = \{1,4,11,12,17,21,32\}$

un ordre total médian: $4>7>2>5>1>3>6$
$w_3 w_3 w_3 w_3 w_3 w_3$

$$ \tau_{C_3} = 0,68 $$

Cet algorithme intègre la procédure d'agrégation précédente dans les phases de recherche des représentants des classes d'une partition de $I$ d'un algorithme de nuées dynamiques (E. DIDAY (12)). Il généralise ainsi une procédure proposée par E. JACQUET-LAGREZE (19) dans le cas de 2 classes. Par ailleurs nous avons pu étendre cette démarche à d'autres procédures d'agrégation classiques où nouvelles à notre connaissance (Exemples (4-1-2) et (4-2-4)) (§5). Cette extension nécessite la considération de modèles ordinaux plus généraux (§3) et une formulation métrique analogue à (1-1) (§4). Afin d'englober les méthodes de comparaisons par paires, nous avons situé ces procédures d'agrégation dans un cadre où les données individuelles sont des graphes de préférences sur $X$ (§2).
Enfin, dans le paragraphe 6, nous étudions les problèmes de convergence de cet algorithme. La suite partition-résumés ordinaux qu'il engendre est stationnaire.

Dans cette première approche, nous nous sommes limités à considérer des modèles ordinaux simples essentiellements définis à partir d'un ordre ou d'un préordre total sur X, pensant qu'une description locale des données de préférences pouvait autoriser une telle simplification. Peut-être serait-il intéressant d'éten-dre cette démarche à des modèles ordinaux plus complexes: quasi-ordres (R. D. LUCE (28), J. MENUET (29), P. FISHBURN (14), F. S. ROBERTS (32)), tresses (C. FLAMENT (16), Y. KERGALL (23)). Il conviendrait aussi de préciser les problèmes de convergence évoqués dans la méthode de codage isotone du modèle (4-2-4) et de la protéger de cas de dégénérescence évoqués dans (27).

## REMARQUES

* Une représentation graphique des classes citées précédem-ment est donnée en annexe. Chacune d'elle semble se caractériser par le rejet de l'une des trois essences suivantes: ylan-ylan, néroli, citral.

* Un programme FORTRAN et son descriptif ayant en options différentes procédures d'agrégation décrites dans le paragraphe 5 sont en cours de réalisation. Ils pourront être obtenus prochainement au L.A.S.S.Y.
## 2 PREFERENCES

Le recueil de données de préférences sous la forme de préordres totaux nécessitant un classement global des objets de X est souvent problématique lorsque leur appréciation est difficilement quantifiable. Il vaut mieux, dans ce cas, recueillir des avis portant sur toutes les comparaisons par paires de ces objets. Afin d'alléger la procédure de recueil de telles données -p(p-1)/2 comparaisons par paires a effectuer- on peut présenter les objets par paquets de faible effectif et demander, pour chaque paquet, un classement global -préordre total sur l'ensemble des objets du paquet- ou les présenter séquentiellement en demandant un jugement de préférence pour chaque couple d'objets se succédant dans une séquence. Evidemment, les paquets ou les séquences sont choisis de telle sorte que les préférences demandées recouvrent toutes les comparaisons par paires de ces objets et que le nombre des paquets ou la longueur des séquences soit minimum. A ce sujet, on pourra consulter: K.D. TOCHER (33), A. DEY (11) et le chapitre consacré aux cycles eulériens dans le livre de C. BERGE. On peut donc interpréter ces données en termes de comparaisons par paires des objets de X et considérer que chaque individu iEI indique pour tout élément (x,y) de l'ensemble X₂ = {(x,y) ∈ XxX; x≠y} une intensité de préférence de x à y: gi(x,y) telle que:

$$ (2-1) \qquad 0 \le g_i(x,y) \le 1 \\ g_i(x,y) + g_i(y,x) = 1 $$

De telles données sont appelées _graphes de préférences_ et G désignera leur ensemble (cf E. JACQUET-LAGREZE (21) ou A. KAUFMAN (22) pour des commentaires sur ce type de données).
Outre la famille $(g_i)_{i \in I}$ des données individuelles, on considérera une famille $(m_i)_{i \in I}$ de **masses** strictement positives permettant, éventuellement de pondérer différemment les individus.

Les données de l'introduction s'intègrent bien dans ce cadre: toutes les masses sont égales à 1 et on peut identifier $F$, l'ensemble des préordres totaux sur $X$ avec un sous ensemble de $G$ en considérant l'injection canonique:

(2-2)

$w \in F \mapsto g^w$ défini par:

$$ 
\begin{align*}
g^w(x,y) &= 1 \text{ si } x>y \\
&= \frac{1}{2} \text{ si } x=y \\
&= 0 \text{ sinon}
\end{align*}
$$

Les graphes de préférences $g \in G$ tels que $g(x,y) = 0$ ou $1$ pour tout $(x,y) \in X_2$ sont appelés **tournois** (cf J.C. BERMOND (06), (07)). Ils correspondent aux relations totales sur $X$.

Evidemment, les graphes de préférences autorisent des **intransitivité s** dans les jugements individuels:

$$ \exists x_1, \dots, x_q \in X: g(x_1, x_2) > \frac{1}{2} \dots g(x_{q-1}, x_q) > \frac{1}{2} \\ \text{et } g(x_q, x_1) > \frac{1}{2} $$

Ces intransitivité s seront considérées comme des erreurs non fondamentales de jugement et il sera supposé que les préférences individuelles s'organisent autour de plusieurs tendances représentables par des modèles ordinaux sans intransitivité s.

### 3 MODELES ORDINAUX

L'ensemble des modèles ordinaux sera noté $E$. De nombreuses procédures d'agrégation de préférences s'intègrent dans l'un des cadres suivants.

#### 3-1 MODELES DIRECTS

$E$ est une partie de l'ensemble $F$ des préordres totaux sur $X$
## EXEMPLES

$$ * E = F $$

$$ * E = F_o \text{ ensemble des ordres totaux sur X.} $$

## 3-2 MODELES TAMPONS

E est le graphe d'une application multivoque A d'un ensemble $H \subset F$ dans un ensemble $K: E = U \{w\} \times A(w)$. Si $w \in H$, A(w) représente l'ensemble des codages admissibles de w. Un modèle ordinal $(w,k) \in E$ sera donc constitué d'une partie purement ordinale $w \in H$ et d'un codage admissible de celle-ci $k \in A(w)$. Evidemment, ce codage sera choisi de manière optimale.

## EXEMPLES

(3-2-1)

$$ * H = F_o, K = G \text{ et si } w \in H, $$

$$ k \in A(w) \text{ si } \forall(x,y) \in X_2: x \ge y \Rightarrow k(x,y) \ge \frac{1}{2}. $$

A introduit une notion de transitivité au niveau des graphes de préférences. On peut montrer facilement que $g \in U A(w)$ si et seulement si:

$$ \forall x_1, \dots, x_q \in X: g(x_1, x_2) > \frac{1}{2} \dots g(x_{q-1}, x_q) > \frac{1}{2} \\ \Rightarrow g(x_1, x_q) \ge \frac{1}{2} $$

(3-2-2)

$$ * H = F, K \subset \mathbb{R}^X \text{ et si } w \in H, $$

(*)

$$ k \in A(w) \text{ si } \forall(x,y) \in X_2: x \ge y \Leftrightarrow k(x) \ge k(y). $$

Dans les trois choix ci-dessous pour K:

(3-2-2-1)

$$ K = \mathbb{R}^X $$

(3-2-2-2)

$$ K = \{k \in \mathbb{R}^X; \sum k(x) = 0 \text{ et } \sum k(x)^2 = 1\} $$

(3-2-2-3)

$$ K = \{k \in \mathbb{R}^X; \forall x \in X: k(x) > 0 \text{ et } \sum k(x) = 1\} $$

on notera le caractère surjectif de A et le caractère univoque de $A^{-1}$.

## 4 MESURE D'ADEQUATION D'UN MODELE ORDINAL

L'adéquation d'un modèle ordinal $\in E$ pour représenter

(*)

Si A et B sont deux ensembles, $A^B$ désigne l'ensemble des applications de B dans A.
un graphe de préférences gEG sera mesurée par une application q de ExG dans $\mathbb{R}^+$, cette adéquation étant d'autant plus forte que q(e,g) est faible. Les exemples suivants correspondent aux principales mesures classiques en analyse des préférences.

## EXEMPLES

### 4-1 MODELES DIRECTS

(4-1-1) Si $w \in F_0$ et $g \in G$, $q(w,g) = \sum_{u \in X_2} |g^w(u) - g(u)|$. Ce choix prolonge la distance de la différence symétrique sur F: si $w, w' \in F$, $|w \Delta w'| = \sum_{u \in X_2} |g^w(u) - g^{w'}(u)|$; ceci permet d'intégrer dans ce cadre l'exemple² de l'introduction. On peut exprimer $q(w,g)$ différemment (E. JACQUET-LAGREZE (18)):

$$q(w,g) = \frac{p(p-1)}{2} - \sum_{w \in W^*} (g(u) - g(\tilde{u})) \quad (*)$$

(4-1-2) Si $w \in F$ et $g \in G$, $q(w,g) = \left\| s_w - s_g \right\|^2$ où:

||·|| désigne la norme euclidienne usuelle sur $\mathbb{R}^X$:

$$\text{si } k \in \mathbb{R}^X, ||k|| = (\sum k(x))^2 \frac{1}{2} \quad x \in X$$

$s_g$ désigne la **fonction score** du graphe de préférences g:

$$s_g \in \mathbb{R}^X \text{ et si } x \in X, s_g(x) = \sum_{y \neq x} g(x,y)$$

$$s_w = s_g w.$$

Cette fonction score s'introduit naturellement lorsque les données sont des préordres totaux sur X. En effet:

$$(4-1-2-1) \qquad \text{si } w \in F \text{ et } x \in X, s_w(x) = \frac{|\{y \in X : y \le x\}| + |\{y \in X : y > x\}|}{2} - 1$$

Calcul pratique sur un exemple:

$X = \{a, b, c, d, e\}$

préordre w: a=e>b>c=d

numéros: 4 3 2 1 0

moyennes 3,5 2 0,5

fonction score: $s_w(a)=s_w(e)=3,5$ $s_w(b)=2$ $s_w(c)=s_w(d)=0,5$.

La formule (4-1-2-1) révèle le caractère **exhaustif** du codage

<footnote>(*) Si $(x,y) \in X_2$, $(\tilde{x},y) = (y,x)$.</footnote>

<footnote>Si $w \in F$, $w^* = w \cap X_2$.</footnote>
de $g^w$ par $s_w$ (on aurait pu utiliser aussi la fonction "rang moyen" de M. BESSON (08)). Un tel codage permet aussi des représentations factorielles où les axes sont aisemment interprétables (J.P. BENZECRI (04), J.P. FENELON (13)).

## 4-2 MODELES TAMPONS

Si $e=(w,k) \in E$ et $g \in G$, $q(e,g)$ ne dépend ici que de la partie codée $k$ de $e$ ce qui confère à celle-ci un rôle tampon entre la partie ordinale $w$ et le graphe de préférences $g$.

(4-2-1) \* Exemple (3-2-1) et $q(e,g) = - \sum_{u \in X_2} g(u) \log k(u)$. Ce choix correspond à un critère de maximum de vraisemblance lorsque les données individuelles sont des tournois et les masses des entiers (R.A. BRADLEY, M.E. TERRY (09)). Il en est de même dans l'exemple suivant.

(4-2-2) \* Exemple (3-2-2-3) et $q(e,g) = - \sum_{(x,y) \in X_2} g(x,y) \log \frac{k(x)}{k(x)+k(y)}$. Introduite dans l'article précédent, cette mesure fournit des modèles ordinaux possédant des propriétés d'exhaustivité statistique (A. ASTIE (01)).

(4-2-3) \* Exemple (3-2-2-1) et $q(e,g) = ||k-s_g||^2$ où $||.||$ est la norme euclidienne usuelle sur $\mathbb{R}^X$ (cf § 4-1). Il en sera de même dans l'exemple suivant.

(4-2-4) \* Exemple (3-2-2-2) et $q(e,g) = \min_{h \in K_g} || k-h ||^2$ où $K_g$ est le cône des codages admissibles de $g$:
$$K_g = \{h \in \mathbb{R}^X : \forall (x,y) \in X_2 : g(x,y) \ge \frac{1}{2} \Rightarrow h(x) \ge h(y)\}$$

Ce cône étant convexe et fermé, $q(e,g) = ||k-P_g(k)||^2$ où $P_g$ est le projecteur orthogonal sur $K_g$. Dans le cas de graphes de préférences associés à des préordres totaux, l'algorithme de J.B. KRUSKAL (25) permet de déterminer facilement $P_g(k)$. Cette projection pourra être interprétée comme un codage optimal du graphe de préférences $g$. Il convient aussi de remarquer qu'une telle mesure permet de traiter des données incomplètes: il suffit de supprimer les conditions qui, dans
$K_g$, correspond aux couples $(x,y) \in X_2$ n'ayant pas fait l'objet d'un jugement de préférence.

## 5 AGREGATION DES PREFERENCES INDIVIDUELLES D'UNE CLASSE C ⊂ I

La mesure d'adéquation précédente permet d'apprécier l'adéquation d'un modèle ordinal eée pour résumer les graphes de préférences $g_i$ associés aux individus iec en calculant la moyenne: $\bar{q}_C(e) = \frac{1}{m_C} \sum_{i \in I} q(e,g_i)$ où $m_C = \sum_{i \in I} g_i$ désigne la masse de la classe C. Agréger les préférences individuelles de cette classe consiste à rechercher les modèles ordinaux les plus adéquats, c'est à dire solutions du problème:

(5-1)

$$ \min_{e \in E} \bar{q}_C(e) $$

Pour différents choix de $q$, la résolution de ce problème a déja fait l'objet de nombreuses publications. Pour ces choix, nous nous limiterons à décrire le principe de cette résolution en indiquant les références correspondantes.

## 5-2 MODELES DIRECTS

\* Exemple (4-1-1) avec $E=F_o$. E. JACQUET-LAGREZE (18) a montré que si $w \in F_o$, $\bar{q}_C(w) = q(w, \bar{g}_C)$ où $\bar{g}_C = \frac{1}{m_C} \sum_{i \in I} g_i$ désigne le graphe moyen de C. Compte tenu de l'expression de $q(w,g)$ donnée en (4-1-1), le problème (5-1) se formule ici:

(5-2-1)

$$ \max_{w \in F_o} \sum_{u \in w} (\bar{g}_C(u) - \bar{g}_C(\bar{u})) $$

E. JACQUET-LAGREZE (18) propose une heuristique pour approcher ses solutions. Celles-ci peuvent être obtenues exactement en prolongeant l'heuristique précédente par un algorithme de BRANCH AND BOUND; celui de J.C. PEYROUX (30) ou de J. DE CANI (10) par exemple.

Remarque: on peut démontrer (J. LEMAIRE (27)) que le choix: $q(w,g) = \sum_{u \in X_2} (g^w(u) - g(u))^2$ conduit aux même résultats que la méthode précédente.

\* Exemple (4-1-2) avec $E=F$. Cette méthode suggérée par la formulation du problème (5-1) consiste à rechercher les
préordres totaux dont le score approxime au mieux le score de $\bar{g}_C$ suivant la norme euclidienne usuelle dans $\mathbb{R}^X$. En effet: $\bar{q}_C(w) = \|s_w - s_g\|^2 + \frac{1}{m_C} \sum_{i \in C} \|s_i - s_g\|^2$; ceci permet de présenter le problème (5-1) sous la forme:

$$ (5-2-2) \qquad \min_{w \in F} \|s_w - s_g\|^2 $$

Comparée avec celle de l'exemple (4-2-3) traitée plus loin, cette méthode présente l'avantage de fournir un résumé purement ordinal plus exhaustif. Par exemple si $X = \{a, b, c, d, e\}$ et si $s_g$ est défini par:

<table><thead><tr><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th></tr></thead><tbody><tr><td>0</td><td>1,8</td><td>2,1</td><td>4</td><td>2,1</td></tr></tbody></table>

l'unique solution du problème (5-2-2) est définie par: $d>c=e=b>a$ alors que la méthode de BORDA généralisée (exemple (4-2-3)) conduit à un modèle ordinal dont la partie purement ordinale est égale à: $d>c=e>b>a$. Une préférence stricte entre c,e et b y est introduite bien que les scores moyens de ces objets soient relativement voisins.

Grâce à l'interprétation graphique donnée par G. KREWERAS (24) -au préordre weF admettant pour classes d'équivalences $X_1 \succ X_2 \succ \dots \succ X_q$ est associé le chemin $C_w$ du graphe $(\mathcal{G}(X), \succ)$ tel que: $C_w = (X, X \setminus X_1, X \setminus X_1 \cup X_2, \dots, X \setminus X_1 \cup \dots \cup X_q = \emptyset)$- qui établit une correspondance bijective entre F et l'ensemble des chemins d'origine X et d'extrémité $\emptyset$ du graphe précédent, on peut formuler le problème (5-2-2) en termes de recherche de chemins de valuation minimum. En effet, en valuant le graphe par l'application v telle que:

$$ \text{si } X \supseteq A \supseteq B, v(A,B) = \sum_{x \in A \setminus B} \left( \frac{|A| + |B| - 1}{2} - s_g(x) \right)^2, $$

la correspondance précédente vérifie la propriété:

$$ v_{w \in F}: \|s_w - s_g\|^2 = v(C_w). \qquad (*) $$

<footnote>(*) Si $C = (A_1, \dots, A_q)$ est un chemin du graphe précédent, sa *valuation* $v(C)$ est définie par: $v(C) = \sum_{i=1}^q v(A_i, A_{i-1})$.</footnote>
La proposition suivante restreint l'exploration des chemins d'origine X et d'extrémité $\emptyset$ à ceux du sous graphe défini par les sommets du chemin correspondant au préordre fourni par la méthode de BORDA généralisée.

(5-2-3) PROPOSITION

Toute solution du problème (5-2-2) contient le préordre w tel que: $v(x,y) \in X_2: x \succcurlyeq_w y \iff s_{g_C}^-(x) \succcurlyeq_w s_{g_C}^-(y)$.

Démonstration en annexe.

Par exemple avec les données précédentes on obtient le sous graphe:

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

Il n'y a qu'un seul chemin de valuation minimum: $C_W = (X, \{a,b,c,e\}, \{a\}, \emptyset)$ et $v(C_W)=0,06$. Il correspond au préordre w: $d>c=e=b>a$ et $||s_w - s_{g_C}||^2 = 0,06$. (pour la recherche d'un tel chemin cf J.C. DERNIAME, C. PAIR (34) par exemple).

5-3 MODELES TAMPONS

* Exemple (4-2-1) (R.A. BRADLEY, M.E. TERRY (09), REMAGE RUSSEL, W.A. THOMPSON (31), A. ASTIE (02)). Dans ce cas:

$\bar{q}_C(e) = - \sum_{u \in X_2} \bar{g}_C(u) \log k(u)$. Pour w fixé dans $F_o$, il est facile de voir que le problème $\min_{k \in A(w)} \bar{q}_C(w,k)$ admet comme unique solution:

$$ (5-3-1) \qquad k(u) = \begin{cases} \max(\frac{1}{2}, \bar{g}_C(u)) & \text{si } u \in w \\ \min(\frac{1}{2}, \bar{g}_C(u)) & \text{si } u \notin w \end{cases} $$

Le problème (5-1) peut alors se formuler:
$$
(5-3-2) \quad \max_{w \in F_o, u \in W^*} \sum_c \bar{g}_c(u) \log \max\left(\frac{1}{2}, \bar{g}_c(u)\right) + \bar{g}_c(\bar{u}) \log \min\left(\frac{1}{2}, \bar{g}_c(\bar{u})\right)
$$
$$
\text{k étant calculé par les formules (5-3-1). Le problème (5-3-2) se traite comme (5-2-1).
$$

* Exemple (4-2-2) (R.A. BRADLEY, M.E. TERRY (09), L.R. FORD (17), A. ASTIE (01)). Ici: $\bar{q}_c(e) = - \sum_{(x,y) \in X_2} \bar{g}_c(x,y) \log \frac{k(x)}{k(x)+k(y)}$ A étant surjectif, la minimisation de cette expression par rapport à $e \in E$ équivaut à celle de l'expression de droite par rapport à $k \in K$ et au calcul de $w=A^{-1}(k)$. En annulant les dérivées partielles, on obtient les relations:

$$
(5-3-3) \qquad \forall x \in X: k(x) = \frac{\sum_{y \neq x} \frac{1}{k(x)+k(y)}}{g_c(x)}
$$

Elles suggèrent une procédure itérative du type: $k^n = f(k^{n-1})$.

Moyennant une hypothèse assez restrictive sur les données:

$\forall (x,y) \in X_2, \exists x_0, \dots, x_q \in X: x_0 = x, x_q = y \text{ et } \forall j: \bar{g}_c(x_{j-1}, x_j) > 0$
L.R. FORD (17) démontre la convergence de la suite $(k^n)_{n \ge 0}$ vers la solution du système (5-3-3) (elle est unique).

* Exemple (4-2-3) (G. KREWERAS (24)). Là encore:

$\bar{q}_c(e) = \| k - s_{\bar{g}_c} \|^2 + \frac{1}{m_c} \sum_{i \in \mathcal{I} \mathcal{E} \mathcal{C}} m_i \| s_{\bar{g}_i} - s_{\bar{g}_c} \|^2$. L'unique solution du problème (5-1) est donc définie par les relations:

$$
(5-3-4) \qquad k = s_{\bar{g}_c} \quad \text{et} \quad w = A^{-1}(k) \quad \text{(Méthode de BORDA généralisée).}
$$
L'article précédent expose une construction géométrique de cette solution dans le _permutoèdre_, image de F dans $\mathbb{R}^X$ par l'application $w \mapsto s_w$.

* Exemple (4-2-4): $\bar{q}_c(e) = \frac{1}{m_c} \sum_{i \in \mathcal{I} \mathcal{E} \mathcal{C}} m_i || k - P_{\bar{g}_i}(k) ||^2$.

A étant surjectif, le problème (5-1) sera résolu en minimisant la partie droite de l'expression précédente par rapport à $k \in K$.

En posant : $\mathbb{R}_o^X = \{ \text{fe } \mathbb{R}^X ; \sum f(x) = 0 \}$

$$
u = (\mathbb{R}_o^X)^C \qquad x \in X
$$

$$
\| \| F \| \| = \left( \frac{1}{m_c} \sum_{i \in \mathcal{I} \mathcal{E} \mathcal{C}} m_i \| f_i \|^2 \right)^{\frac{1}{2}} \quad \text{si } F = (f_i)_{i \in \mathcal{I} \mathcal{E} \mathcal{C}} \text{ e } U
$$

$$
V = \{F = (f_i)_{i \in \mathcal{I} \mathcal{E} \mathcal{C}} ; \exists k \in \mathbb{R}_o^X, \forall i \in \mathcal{I} \mathcal{E} \mathcal{C} : f_i = k \}
$$

$$
Q = \prod_{i \in \mathcal{I} \mathcal{E} \mathcal{C}} k
$$
on peut formuler ce problème de minimisation en termes
d'analyse canonique entre le sous espace vectoriel V et le
cône Q de U:

(5-3-5)

$$
\begin{array}{llll}
\min & \min & ||| F-H ||| & \\
\mathit{FEV} & \mathit{HEQ} & & \\
||| F ||| = 1 & & &
\end{array}
$$

Le lien entre cette nouvelle formulation et la précédente
est le suivant: F=(k)$_{iec}$ et H=(h$_i$)$_{iec}$ sont solutions de (5-3-5)
si et seulement si k minimise $\sum_i m_i |||k-P_g(k)|||^2$ et $h_i = P_g(k)$
pour tout iec. On retrouve ainsi la formulation de J. DE LEEUW,
Y. TAKANE, F. YOUNG (26).

Classique pour aborder ce type de problème, la méthode de
relaxation suivante:

initialisation: H°e Q

itération n: $F^n$ solution de $\min_{FEV, |||F|||=1} |||F-H^n-|||^2$

puis: $H^n$ solution de $\min_{HEQ} |||F^n - H|||$

décompose le problème (5-3-5) en une succession de minimisations partielles
dont les solutions -uniques- sont facilement calculables (cf
J. LEMAIRE (27) pour plus de précisions). Bien qu'affirmée dans
l'article (26), la convergence de la suite $(F^n, H^n)_{n \ge 1}$ ne paraît
pas généralement acquise, les hypothèses habituelles de con-
vexité n'étant pas réalisées à cause de la normalisation impo-
sée. Le résultat suivant explique néanmoins les "convergences
expérimentales" constatées sur ordinateur.

(5-3-6)

PROPOSITION

La suite définie par : $e_n = |||F^n - H^n|||$ converge en décroissant vers une limite e.

$$
\lim_{n \to \infty} |||F^n - F^{n+1}||| = \lim_{n \to \infty} |||H^n - H^{n+1}||| = 0.
$$

Toute valeur d'adhérence $(F^*, H^*)$ de la suite $(F^n, H^n)_{n \ge 1}$
vérifie: $F^*$ solution de $\min_{FEV} |||F-H^*|||$,

$|||F||| = 1$
$$
\begin{array}{l}
\begin{array}{l}
\text{H}^* \text{ solution de} \quad \min_{\text{HEQ}} \quad \|\| \text{F}^* - \text{H} \|\| \\
\text{et } \text{e} = \|\| \text{F}^* - \text{H}^* \|\|
\end{array}
\\[1em]
\text{Evidemment, rien ne garantit qu'une telle valeur d'adhérence soit solution du problème (5-3-5). On trouvera dans (27) un exemple montrant l'influence du choix initial H° sur cette propriété.}
\end{array}
$$

Evidemment, rien ne garantit qu'une telle valeur d'adhérence soit solution du problème (5-3-5). On trouvera dans (27) un exemple montrant l'influence du choix initial H° sur cette propriété.

## 6 ALGORITHME D'AGREGATION-PARTITIONNEMENT

Adaptation de l'algorithme des nuées dynamiques (E. DIDAY (12)) au cadre ordinal, cet algorithme permet de rechercher simultanément:

une **partition** de I en k classes: $\underline{C} = (C_1, \dots, C_k)$,

une représentation de ces classes par un k-uplet de **résumés**
**ordinaux**: $\underline{L} = (L_1, \dots, L_k)$

présentant des propriétés d'optimalité vis à vis d'un critère construit à partir de la mesure q du paragraphe 5.

On note : $\mathbb{P}_k$ l'ensemble des partitions de I en k classes :

$$
\mathbb{P}_k = \left\{ (C_1, \dots, C_k) ; \begin{array}{l} I = U C_j, \forall j \in I \text{;} k : C_j \neq \emptyset, \forall j, j' \in I \text{;} k : j \neq j' \\ \text{où } I \in I \end{array} \right\} = \{1, \dots, k\} ,
$$

$\mathbb{I}$ l'ensemble des résumés ordinaux. Les éléments de $\mathbb{I}$ seront formés d'un nombre fini de modèles ordinaux: $\mathbb{I} = \mathcal{S}_f(E)$ (ensemble des parties finies de E),

$\mathbb{I}_k = \mathbb{I} \times \dots \times \mathbb{I}$ (k fois).

Le critère d'adéquation d'un couple partition-résumés est défini

par: si $\underline{C} = (C_1, \dots, C_k) \in \mathbb{P}_k$ et $\underline{L} = (L_1, \dots, L_k) \in \mathbb{I}_k$,

$$
W(\underline{C}, \underline{L}) = \sum_{j \in I} m_{C_j | \underline{L}_j} \sum_{j \in I} \bar{q}_{C_j} (e).
$$

Les meilleurs couples sont solutions du problème :

$$
\min \min_{\underline{C} \in \mathbb{P}_k} W(\underline{C}, \underline{L}) \\
\underline{L} \in \mathbb{I}_k
$$

Là encore, la méthode de relaxation suivante :

initialisation : $\underline{C}^0 \in \mathbb{P}_k$

itération n: $\underline{L}^n$ solution de $\min_{\underline{L} \in \mathbb{I}_k} W(\underline{C}^{n-1}, \underline{L})$

puis: $\underline{C}^n$ solution de $\min_{\underline{C} \in \mathbb{P}_k} W(\underline{C}, \underline{L}^n)$
permet d'aborder le problème (6-1). Les sous problèmes précédents peuvent être facilement solutionnés moyennant une hypothèse supplémentaire pour les modèles tampons:

(6-2) pour toute partie C de I et tout élément weH, le problème $\min_{k \in A(w)} \bar{q}_C(w, k)$ n'admet qu'une seule solution. On vérifiera facilement que celle-ci est réalisée dans tous les exemples cités sauf peut être dans l'exemple (4-2-4). Avec cette hypothèse, on peut énoncer:

(6-3) **PROPOSITION**

Si $\underline{ceP}_k$, la solution **maximum** (au sens de l'inclusion) du problème $\min_{\underline{L} \in \underline{P}_k} W(\underline{C}, \underline{L})$ est définie par:
$$ vje[k]: \underline{L}_j^* = \{e^*; e^* \text{ solution de } \min_{e \in E} \bar{q}_C(e)\}. $$
Démonstration en annexe.

Cette proposition ramène le problème de la représentation des classes d'une partition à k problèmes d'agrégation ordinale dont il faut chercher **toutes** les solutions (§ 5).

(6-4) **PROPOSITION**

Si $\underline{L} \in \underline{P}_k$, une solution du problème $\min_{\underline{ceP}_k} W(\underline{C}, \underline{L})$ est définie par:
$$ vje[k]: \underline{C}_j^* = \{ieI; j \text{ plus petite solution de } \min_{j' \in \underline{L}_j'} \sum_{e \in \underline{eL}_j'} q(e, g_i)\}. $$
Pour une démonstration: cf E. DIDAY (12) par exemple.

Moyennant de tels choix à chaque itération de l'algorithme, on obtient des résultats de convergence.

(6-5) **PROPOSITION**

Les suites $(W(\underline{C}^n, \underline{L}^n))_{n \ge 1}$ et $(\underline{C}^n, \underline{L}^n)$ sont toutes deux stationnaires, la première étant de plus décroissante.

Démonstration en annexe.
ANNEXE 1: ANALYSE EN COMPOSANTES PRINCIPALES DES SCORES DES PREORDRES
DE L'INTRODUCTION

<figure><img src="image_3.png" /></figure>
# ANNEXE 2: DEMONSTRATIONS

## PROPOSITION (5-2-3)

On pose $s=s_{g_c}$ et on définit le préordre $w_s$ par:

$$x \succcurlyeq_{w_s} y \Leftrightarrow s(x) \succcurlyeq_{s} y$$

Soit w. une solution du problème (5-2-2); il faut montrer:

$$s(x) \succcurlyeq_{s} s(y) \Rightarrow s_{w.}(x) \succcurlyeq_{s_{w.}}(y)$$

Cette implication sera prouvée en deux étapes:

$$1- s(x) \succcurlyeq_{s} s(y) \Rightarrow s_{w.}(x) \succcurlyeq_{s_{w.}} s(y)$$

Soit $w_1$ le préordre total obtenu à partir de w. en inversant les rôles de x et de y. Définissant: $F_w = \|s_w - s\|_2^2$, il vient:
$$ 
\begin{align*} 
F_w &= F_{w.} - (s_{w.}(x) - s(x))^2 - (s_{w.}(y) - s(y))^2 \\ 
&\quad + (s_{w.}(y) - s(x))^2 + (s_{w.}(x) - s(y))^2 \\ 
&= F_w + 2(s(x) - s(y))(s_{w.}(x) - s_{w.}(y)) 
\end{align*} 
$$
si l'on utilise la définition de $\| \cdot \|_2^2$.

L'implication résulte alors du caractère optimal de w.: $F_w \succcurlyeq F_{w.}$

$$2- s(x) = s(y) \Rightarrow s_{w.}(x) = s_{w.}(y)$$

Soient $s. = s(x) = s(y)$, $B = \{z \in X; s(z) = s.\}$, $s_1 > \dots > s_q$ les différentes valeurs de $s_w$. sur B et $B_j = \{z \in B; s_{w.}(z) = s_j\}$ pour $j=1, \dots, q$. Pour démontrer l'implication ci-dessus, il suffit de prouver successivement que les éventualités: $q>3$, $q=3$, $q=2$ sont impossibles.

### 2-1 supposons $q>3$

Les ensembles $B_2, \dots, B_{q-1}$ constituent des classes d'équivalence successives de w.: $\dots >_{w.} B_{2w.} > \dots >_{w.} B_{q-1w.} > \dots$ En effet, il suffit d'établir que: $s_1 >_{w.} s_{w.}(z) >_{s_q} s_q \Rightarrow z \in B$. Pour cela considérons u,vEB tels que $s_{w.}(u) = s_1$ et $s_{w.}(v) = s_q$. Si $s_{w.}(u) >_{w.} s_{w.}(z) >_{w.} s_{w.}(v)$, d'après l'implication 1-, on a: $s(u) \succcurlyeq s(z) \succcurlyeq s(v)$ soit: $s(z) = s$. Ainsi zEB.

Considérons alors le préordre total w construit à partir de w. en réunissant les classes $B_2$ et $B_3$. En posant $b_j = |B_j|$,
et en utilisant la formule (4-1-2-1), il vient:

$$F_w = F_w - \frac{b_2 b_3}{4} (b_2 + b_3)$$

ce qui contredit l'optimalité de w.: $F_w \ge F_w$. Cette éventualité est donc impossible.

### 2-2 supposons q=3

Soient: $A=\{z \in X \setminus B; s_w(z)=s_1\}$, $C=\{z \in X \setminus B; s_w(z)=s_q\}$, $a=|A|$ et $b=|B|$. Par un raisonnement analogue au précédent, on montre que les ensembles: $... \supseteq AUB_1 \supseteq B_2 \supseteq B_3 \supset C \supseteq ...$ constituent des classes d'équivalence successives de w.. Si A ou C est vide, la démarche précédente appliquée à $B_1$ et $B_2$ ou $B_2$ et $B_3$ conduit à une contradiction.

Sinon, considérons les préordres $w_1$ et $w_2$ construits à partir de w. en: - réunissant $B_1$, $B_2$ et isolant A pour $w_1$,

- réunissant A, $B_1$, $B_2$ pour $w_2$;

d'après (4-1-2-1), il vient:

$$ 
\begin{align*}
F_{w_1} &= F_w + b_1 \left( m + \frac{(a-b_2)(a+b_1+b_2)}{4} \right) & \text{où} \\
F_{w_2} &= F_w + b_2 \left( -m - \frac{(a+b_1)(a+b_1+b_2)}{4} \right) & \text{m= $\sum_{x \in A} s_w(x)$}
\end{align*}
$$

ce qui, avec les relations: $F_{w_1} \ge F_w$ et $F_{w_2} \ge F_w$, conduit à la contradiction: $b_2 - a \ge -b_1 - a$. Cette éventualité est donc aussi impossible.

### 2-3 supposons q=2

Comme précédemment, les ensembles: $... \supseteq AUB_1 \supseteq CUB_2 \supseteq ...$ constituent des classes d'équivalence successives de w.. Si A ou C est (sont) vide (s), un des raisonnements précédents conduit à une contradiction. Sinon, considérons les préordres $w_1$ et $w_2$ construits à partir de w. en:

- réunissant $AUB_1$ et $B_2$ et isolant C pour $w_1$,

- réunissant $CUB_2$ et $B_1$ et isolant A pour $w_2$.

D'après (4-1-2-1), il vient:

$$F_{w_1} = F_w + b_2 \left( -m - n + (c - a - b_1) \frac{a + b_1 + b_2 + c}{4} \right)$$
$$F_{w_2} = F_w + b_1(m+n-(c-a+b_2)) \frac{a+b_1+b_2+c}{4}$$

où m= Σ s.- s(x) et n= Σ s.- s(x). Là encore, les inégalités x∈A et x∈C Fw₁≥Fw. et Fw₂≥Fw. conduisent à la contradiction:c-a-b₁>c-a+b₂. Cette éventualité est donc elle aussi impossible. La proposition est donc établie.

PROPOSITION (5-3-6)

Pour simplifier les écritures, on notera dans ce paragraphe -et celui-ci seulement- $||.||$ au lieu de $||||.||$ et (..,) le produit scalaire associé à cette norme euclidienne.

Si $P_V$ et $P_Q$ désignent respectivement les projecteurs orthogonaux sur V et Q, il est facile d'établir que la solution du problème: $\min_{F \in V} ||F-G||$ (resp. $\min_{F \in Q} ||F-G||$) où $G=(g_i)_{i \in \mathbb{N}}$ désigne un élément de U est définie par: $F^* = \frac{P_V(G)}{||P_V(G)||}$ où $P_V(G) = (\bar{g}_c)_{i \in \mathbb{N}}$ si $P_V(G) \neq 0$ (resp. $F^* = P_Q(G)$). Dans la phase d'initialisation, nous supposerons donc avoir choisi H° tel que $P_V(H^°) \neq 0$. Cette condition sera réalisée à chaque itération (LEMME suivant).

* La première assertion de la PROPOSITION est évidente.

On a même pour tout $n \ge 1$:

$$||F^n - H^n|| \le ||F^n - H^{n-1}|| \le ||F^{n-1} - H^{n-1}||$$

* Pour démontrer la seconde il suffit de prouver que:

$\lim_{n \to \infty} ||F^{n-1} - F^n|| = 0$ puisque $P_Q$ est continue. Considérons une valeur $\varepsilon > 0$. Pour n assez grand, on a:

$$0 \le ||F^{n-1} - H^{n-1}||^2 \le ||F^n - H^{n-1}||^2 \le \varepsilon$$

Posant: $G^n = P_V(H^{n-1})$, l'orthogonalité entre $H^{n-1} - G^n$ et V permet d'écrire:

$$0 \le ||F^{n-1} - G^n||^2 \le ||F^n - G^n||^2 \le \varepsilon$$

En développant, on obtient:

$$(G^n, F^{n-1} - F^n)^2 \le \varepsilon^2 / 4$$
$$ \text{soit: } \|F^{n-1} - F^n\|^2 \le \frac{\epsilon^2}{4 \cos^2(G^n, F^{n-1} - F^n) \|G^n\|^2} \quad (*) $$

$$ \text{Or } \cos^2(G^n, F^{n-1} - F^n) = \|F^{n-1} - F^n\|^2/4 \text{ puisque } \|F^{n-1}\| = \|F^n\| = 1 \\ \text{et } F^n = \lambda G^n \text{ avec } \lambda > 0. \text{ Dès lors:} $$

$$ \|F^{n-1} - F^n\|^4 \le \frac{\epsilon^2}{\|G^n\|^2} $$

Pour conclure, il suffit de démontrer le:

LEMME

La suite $(\|G^n\|)_{n \ge 1}$ est croissante.

$$ \|G^{n-1}\|^2 = \|H^{n-2}\|^2 \cos^2(F^{n-1}, H^{n-2}) \text{ puisque } G^{n-1} \text{ et } H^{n-2} - G^{n-1} \text{ sont orthogonaux. Or, on a:} $$

$$ - \frac{\|H^{n-2}\|^2 \le \|H^{n-1}\|^2}{\|H^{n-2}\| \le \|H^{n-1}\|} $$

$$ \text{car } \|H^{n-2}\|^2 = \|F^{n-2}\|^2 - \|F^{n-2} - H^{n-2}\|^2 \quad (H^{n-2} = P_Q(F^{n-2}) \\ \le \|F^{n-1}\|^2 - \|F^{n-1} - H^{n-1}\|^2 \text{ d'après (a)}) $$

$$ \le \|H^{n-1}\|^2 - \frac{\cos^2(F^{n-1}, H^{n-2}) \le \cos^2(F^n, H^{n-1})}{\cos^2(F^{n-1}, H^{n-2})} $$

$$ \text{car } \cos^2(F^{n-1}, H^{n-2}) = 1 - \|F^{n-1} - L^{n-1}\|^2 / \|F^{n-1}\|^2 \quad \text{où } L^{n-1} \text{ est la projection orthogonale de } F^{n-1} \text{ sur le sous espace engendré par } H^{n-2}. \text{ L'optimalité de } H^{n-1} \text{ implique alors:} $$

$$ \cos^2(F^{n-1}, H^{n-2}) \le 1 - \frac{\|F^{n-1} - H^{n-1}\|^2}{\|F^{n-1}\|^2} $$

$$ \text{soit: } \cos^2(F^{n-1}, H^{n-2}) \le \cos^2(F^{n-1}, H^{n-1}). $$

Puis, notant $M^{n-1}$ la projection de $G^n$ sur le sous espace engendré par $F^{n-1}$, il vient:

$$ \cos^2(F^{n-1}, H^{n-1}) = \frac{\|M^{n-1}\|^2}{\|H^{n-1}\|^2} \le \frac{\|G^n\|^2}{\|H^{n-1}\|^2} = \cos^2(F^n, H^{n-1}) $$

puisque $M^{n-1}$ est aussi la projection de $H^{n-1}$ sur ce sous espace.

En revenant à l'expression de $\|G^{n-1}\|^2$:

$$ \|G^{n-1}\|^2 \le \|H^{n-1}\|^2 \cos^2(F^n, H^{n-1}) = \|G^n\|^2. \text{ Le lemme est démontré.} $$

<footnote>(*) $\cos(F,G) = \frac{\langle F,G \rangle}{\|F\| \|G\|}$</footnote>
La dernière assertion en résulte: si $(F^{n(m)}, H^{n(m)})_{m \ge 0}$ est une sous suite convergent vers $(F^*, H^*)$, $\lim_{m \to \infty} F^{n(m)} = F^*$ et $P_Q$ continue impliquent: $\lim_{m \to \infty} H^{n(m)} = P_Q(F^*)$. Donc $H^* = P_Q(F^*)$. De même, $\lim_{m \to \infty} H^{n(m)} = H^*$ et $G \mapsto \frac{P_V(G)}{||P_V(G)||}$ continue sur le domaine: $\{\text{GEU}; \cos^2(P_V(G), G) \ge \delta > 0\}$-condition acquise pour la suite $(H^n)_{n \ge 0}$ grâce à l'hypothèse: $P_V(H^0) \ne 0$ et à la croissance de la suite $(\cos^2(F^n, H^{n-1}))_{n \ge 1}$ (démonstration du lemme)- impliquent: $\lim_{m \to \infty} F^{n(m)+1} = P_V(H^*)/||P_V(H^*)||$. Pour conclure, il suffit de remarquer que $\lim_{m \to \infty} F^{n(m)+1} = \lim_{m \to \infty} F^{n(m)}$ d'après l'assertion précédente. Le reste de la proposition est alors évident.

PROPOSITION (6-3)

Le caractère additif de W implique:

$L^+ = (L_1^+, \dots, L_k^+)$ solution de min $W(\underline{C}, \underline{L})$ si et seulement si
$$ \underline{L} = \underline{e} \underline{\Pi}_k $$
$\text{vj}\text{e}]k$: $L_j^+$ est solution de min $\frac{1}{|\underline{L}|} \sum \bar{q}_C$ (e).
$$ \underline{L} \underline{e} \underline{\Pi} |\underline{L}| e \underline{e} \underline{L} \underline{C}_j $$

Le k-uplet $\underline{L}^*$ défini dans la proposition est donc bien solution du problème min $W(\underline{C}, \underline{L})$. De plus si $\underline{L}^+$ est une autre solution:

$$ \text{vj}\text{e}]k: \frac{1}{|\underline{L}_j^+|} \sum_{e \underline{e} \underline{L}_j^+} \bar{q}_{C_j}(e) = \min_{e \underline{e} \underline{\Pi}} \bar{q}_{C_j}(e) $$

Ceci n'est possible que si:

$$ \text{vj}\text{e}]k: e \underline{e} \underline{L}_j^+ \Rightarrow \bar{q}_{C_j}(e) = \min_{e \underline{e} \underline{\Pi}} \bar{q}_{C_j}(e) $$

ce qui assure: $\text{vj}\text{e}]k: L_j^+ \subset \underline{L}_j^*$.

REMARQUE: pour toute partie C de I, le problème min $\bar{q}_C(e)$ n'admet qu'un nombre fini de solutions. C'est évident pour les modèles directs où E est fini. Pour les modèles tampons, cela résulte de l'hypothèse (6-2): notant $k^*(w)$ l'unique solution du problème: min $\bar{q}_C(w, k)$, les solutions du problème $\min_{k \in \mathbb{N}} \bar{q}_C(k)$ sont définies par: $\underline{e} \underline{e} \underline{E}$
$e^* = (w^*, k^*)$ où $w^*$ est solution de $\min_{w \in H} \bar{q}_C(w, k^*(w))$ et $k^* = k^*(w)$.

PROPOSITION (6-5)

La methode de relaxation choisie implique:

(b)

$$ \forall n \ge 1: W(\underline{C}^n, \underline{L}^n) \le W(\underline{C}^{n-1}, \underline{L}^n) \le W(\underline{C}^{n-1}, \underline{L}^{n-1}) $$

La décroissance de la suite $(W(\underline{C}^n, \underline{L}^n))_{n \ge 1}$ en résulte.

De plus, comme $W(\underline{C}^{n-1}, \underline{L}^n) = \min_{\underline{L} \in \Pi_k} W(\underline{C}^{n-1}, \underline{L})$ et $\Pi_k$ est fini, la suite $(W(\underline{C}^{n-1}, \underline{L}^n))_{n \ge 1}$ est stationnaire. D'après (b)

il en est de même de la suite $(W(\underline{C}^n, \underline{L}^n))_{n \ge 1}$. Pour n assez grand on a donc: $W(\underline{C}^{n-1}, \underline{L}^n) = W(\underline{C}^{n-1}, \underline{L}^{n-1})$. Comme $\underline{L}^n$

minimise $W(\underline{C}^{n-1}, \underline{L})$, il résulte de la proposition (6-3) et du caractère maximum de $\underline{L}^n$ que: $\underline{L}^{n-1} \subset \underline{L}^n$. La stationnarité de la suite $(\underline{L}^n)_{n \ge 1}$ résulte du caractère fini de E pour les modèles directs ou de H et de l'hypothèse (6-2) (cf REMARQUE ci-dessus) pour les modèles tampons. La stationnarité de la suite $(\underline{C}^n)_{n \ge 0}$ en découle.

REMARQUE: toute limite $(\underline{C}^*, \underline{L}^*)$ de la suite $(\underline{C}^n, \underline{L}^n)_{n \ge 1}$ vérifie évidemment:

$\underline{L}^*$ est solution de $\min W(\underline{C}^*, \underline{L})$

$\underline{C}^*$ est solution de $\min_{\underline{L} \in \Pi_k} W(\underline{C}, \underline{L}^*)$

(C'est un élément non biaisé: cf E. DIDAY (12))
BIBLIOGRAPHIE

[ 1 ] ASTIE A. (1970)
COMPARAISONS PAR PAIRES ET PROBLEMES DE CLASSEMENT
ESTIMATION ET TESTS STATISTIQUES
MATH. SCI. HUM., NO 32, PP 17-44

[ 2 ] ASTIE A. (1973)
COMPARAISONS PAR PAIRES. RECHERCHE D'UN CLASSEMENT OU D'UN
ENSEMBLE DE CLASSEMENTS DES OBJETS COMPARES
REV. DE STAT. APPL., 21, NO 3, P 51-63

[ 3 ] BARBUT M., MUNJARDET B. (1970)
ORDRE ET CLASSIFICATION. ALGEBRE ET COMBINATOIRE
HACHETTE UNIVERSITE

[ 4 ] BENZECRI J.P. (1971)
SUR L'ANALYSE DES PREFERENCES
D.T.F., PP 195-205

[ 5 ] BERGE C. (1970)
GRAPHES ET HYPERGRAPHES
DUNOD

[ 6 ] BERMOND J.C. (1972)
ORDRES & DISTANCE MINIMUM D'UN TOURNOI ET GRAPHES PARTIELS
SANS CIRCUITS MAXIMAUX
MATH. SCI. HUM., NO 37, PP 5-25

[ 7 ] BERMOND J.C., KOORATOFF Y. (1976)
UNE HEURISTIQUE POUR LE CALCUL DE L'INDICE DE TRANSITIVITE D'HUM
TOURNOI
R.A.I.R.O., INFORMATIQUE THEORIQUE, VOL 10, NO 3, MARS

[ 8 ] BESSON M. (1975)
WANG MOTEN ET AGREGATION DE CLASSEMENTS
M.A.I.K.O., JANV., S-1, P 37-59

[ 9 ] GRAUDET W.A., TERRY M.E. (1952)
THE RANK ANALYSIS OF INCOMPLETE BLOCK DESIGNS. 1 THE METHOD
OF AIRIED COMPARISONS
BIOMETRIA, 41, PP 502-537

[10] DE CANE J.S. (1972)
A GRANCH AND BUNDED ALGORITHM FOR MAXIMUM LIKEHOOD PAIRED
COMPARISON RANKING
BIOMETRIA, 59, NO 1, PP 131-135

[11] DEY A. (1970)
ON CONSTRUCTION OF BALANCED N-ARY BLOCK DESIGNS
ANN. INST. STAT., V 22

[12] DIDAY E. (1971)
UNE NOUVELLE METHODE EN CLASSIFICATION AUTOMATIQUE ET
RECONNAISSANCE DES FORMES
REV. DE STAT. APPL., VOL 19, NO 2
[ 13 ] FENELON J.P. (1971)
UN CAS D'ANALYSE DE PREFERENCES EN ESTHETIQUE
O.T.F., PP 207-220

[ 14 ] FISHBURN P.C. (1974)
LEXICOGRAPHIC ORDERS, UTILITIES AND DECISION RULES. A SURVEY
MANAGEMENT SCIENCE, TOME 20, NO 11, PP 1442-1471

[ 15 ] FLAMENT C. (1962)
L'ANALYSE ALGEBRIQUE DE QUESTIONNAIRES
THESE DE DOCTORAT D'ETAI

[ 16 ] FLAMENT C. (1971)
TRESSES DE GUTTMAN
O.I.F., PP 245-254

[ 17 ] FORD L.R. JR. (1957)
SOLUTION OF A RANKING PROBLEM FROM BINARY COMPARISONS
AMER. MATH. MONTHLY, 64, P 28-33

[ 18 ] JACQUET-LAGREZE E. (1969)
L'AGREGATION DES OPINIONS INDIVIDUELLES
INFORMATIQUE EN SCIENCES HUMAINES, NO 4

[ 19 ] JACQUET-LAGREZE E. (1971)
ANALYSE D'OPINIONS VALUEES ET GRAPHES DE PREFERENCES
MATH. SCI. HUM., NO 33, PP 33-35

[ 20 ] JACQUET-LAGREZE E. (1973)
METHODES ET PROGRAMMES EN ANALYSE DES DONNES ORDINALES
SEMA, DIRECTION SCIENTIFIQUE
RAPPORT SYNTHESE ET FORMATION NO 81

[ 21 ] JACQUET-LAGREZE E. (1975)
LA MODELISATION DES PREFERENCES. PREORDRES, QUASI ORDRES
ET RELATIONS FLOUES
SEMA, DIRECTION SCIENTIFIQUE
RAPPORT DE RECHERCHE NO 80

[ 22 ] KAUFMANN A. (1975)
INTRODUCTION A LA THEORIE DES SOUS ENSEMBLES FLUUS. TOME 3
MASSUN

[ 23 ] KERWALL T. (1974)
ETUDE DES TRESSES DE GUTTMAN EN ALGEBRE A P VALEURS
MATH. SCI. HUM., NO 46, PP 5-19

[ 24 ] BREWERAS G. (1969)
AGREGATION ET DYNAMIQUE DES ORDRES DE PREFERENCE
COMPTE RENDU DU COLLEQUE DU C.K.N.R.S. : LA DECISION. P 137-151

[ 25 ] KRUSKAL J.B. (1964)
MULTIDIMENSIONAL SCALING BY OPTIMIZING GOODNESS OF FIT TO A NON
METRIC HYPOTHESIS
PSYCHOMETRICA, VOL. 29, PP 1-27

[ 26 ] DE LEEUW J.Y. TAKANE Y., YOUNG F. (1976)
ADDITIVE STRUCTURE IN QUALITATIVE DATA: AN ALTERNATING LEAST
SQUARES METHOD WITH OPTIMAL SCALING FEATURE.
PSYCHOMETRIKA (A PARAITRE)
[ 27 ] LEMAIRE J. (1976)
AGREGATION TYPOLOGIQUE DES PREFERENCES
THESE DE 3 IEME CYCLE, UNIV. DE NICE

[ 28 ] LUCE R.D. (1956)
SEMI ORDERS AND A THEORY OF UTILITY DISCRIMINATION
ECONOMETRICA, VOL. 24, PP. 178-191

[ 29 ] MENJET J. (1974)
QUASI ORDRES ET MODELISATION DES PREFERENCES
SEMA, DIRECTION SCIENTIFIQUE
NOTE DE TRAVAIL NO 197

[ 30 ] PETROUX C. (1975)
AGREGATION D'OPINIONS INDIVIDUELLES
THESE DE 3 IEME CYCLE, UNIV. DE PARIS 6

[ 31 ] REMAGE RUSSEL, THOMPSON W.A. (1966)
MAXIMUM LIKELIHOOD PAIRED COMPARISONS
BIOMETRINA, 53, NO 1-2, PP 143-149

[ 32 ] ROBERTS F.S. (1971)

HOMOGENEOUS FAMILIES OF SEMI ORDERS AND THE THEORY OF
PROBABILISTIC CONSISTENCY
J. OF MATH. PSYCHOLOGY, TOME 8, PP 248-263

[ 33 ] TOCHER N. D. (1952)
DESIGN AND ANALYSIS OF BLOCK EXPERIMENTS
J. ROY. STAT. SOC., B.14

[ 34 ] DERNIAME J.C., PAIR C. (1971)
PROBLEMES DE CHEMINEMENT DANS LES GRAPHESS
DUNOD

NICE le 4-9-1976