[figure]

Représenter et agréger des préférences à l’aide d’une interprétation markovienne

François Glineur

Faculté Polytechnique de Mons

LAMSADE, séminaire MCAD Université Paris-Dauphine 16 novembre 1999

Représenter et agréger des préférences à l’aide d’une interprétation markovienne

[figure]

[figure: Plan]

Introduction

⋄ Chaînes de Markov ⋄ Relations de préférence

Méthode stochastique

⋄ Une relation de préférence ⋄ Cas multicritère ⋄ Introduire de l’incomparabilité

Illustrations

⋄ Quelques relations de préférence ⋄ Localisation d’usine

Conclusions

François Glineur, FPMs  Page 2  LAMSADE, Université Paris-Dauphine

[figure]

[figure]

Chaînes de Markov

Définitions

E = ensemble de n états = {E_{i}} X = ensemble de variables aléatoires = {X_{t}} où t est un index temporel discret et X_{t} ∈ E X est une chaîne de Markov discrète à temps fini ssi

⋄ X_{t} dépend uniquement de X_{t−1} (processus markovien, sans mémoire)

⋄ Cette dépendance est invariante dans le temps (processus homogène)

X est complètement défini par la matrice M = {p_{i,j}} où

p_{i,j} = ℙ(X_{t} = E_{j} | X_{t−1} = E_{i})

Représentation comme un graphe orienté valué (sommets ≡ états, arcs ≡ transitions)

François Glineur, FPMs  Page 3  LAMSADE, Université Paris-Dauphine

[figure]

Exemples et propriétés

M =(\begin{matrix}\frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & \frac{1}{4} & \frac{3}{4} \\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{matrix} ) [figure: E_{1}; 1/2; 1/2; E_{2}; 1/3; 1/3; 1/3; E_{3}; 1/4; 3/4; E_{4}; 1/2; 1/2]

M est une matrice stochastique (somme des lignes égale à 1) Soit a_{0} la distribution de probabilité initiale (correspondant à la v.a. X_{0})

1. Il est possible de calculer a_{i} (distribution de X_{i}) récursivement à partir de a_{i−1} ∀i

2. La suite {a_{i}} tend vers une limite a indépendamment de la distribution initiale a_{0} (sous une hypothèse de régularité)

3. Cette limite a est appelée distribution stationnaire, et peut être calculée efficacement (système linéaire)

Dans l’exemple, a =(_{0} _{0} \frac{2}{5} \frac{3}{5} )

François Glineur, FPMs  Page 4  LAMSADE, Université Paris-Dauphine

[figure]

[figure]

Relations de préférence

Définitions

A = ensemble de n alternatives = {A_{i}}

R = relation binaire sur A (⊆ A × A)

Soit a, b, c ∈ A. La relation R est ⋄ réflexive si a R a ⋄ complète si a R b ou b R a ⋄ symétrique si a R b ⇒ b R a ⋄ asymétrique si a R b ⇒ b ¬R a ⋄ transitive si a R b et b R c ⇒ a R c

On donne à la relation R la signification ≤ :

a R b ⇔ a n’est pas préféré strictement à b

I ≡ la partie indifférence” de R, définie par

a I b ⇔ a R b et b R a

S ≡ la partie “préférence stricte” de R, définie

par a S b ⇔ a R b et b ¬R a

R = I ∪ S, I est symétrique et réflexive, S est asymétrique

François Glineur, FPMs  Page 5  LAMSADE, Université Paris-Dauphine

[figure]

Représentations et exemples

⋄ Représentation matricielle {r_{i,j}} avec r_{i,j} égal à 1 si A_{i} R A_{j}, 0 sinon

⋄ Représentation comme un graphe orienté (sommets ≡ alternatives, arcs ≡ relation R)

Par exemple, A = {a, b, c} et R = {(a, c), (c, a), (a, b), (b, c), (a, a), (b, b), (c, c)} est réflexive et complète

M =(\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}) [figure: a; b; c]

François Glineur, FPMs  Page 6  LAMSADE, Université Paris-Dauphine

[figure]

Quelques relations de préférence

Soit R une relation complète et réflexive

⋄ Si S et I sont tous les deux transitives, R est un préordre complet (ordre avec ex-aequo). On peut associer à chaque alternative une valeur v_{i} telle que

A_{i} R A_{j} ⇔ v_{i} ≤ v_{j}

⋄ Si S est transitive et I = {(a, a)} ∀a ∈ R, R est un ordre complet (sans ex-aequo). On peut associer à chaque alternative une valeur distincte v_{i} telle que

A_{i} R A_{j} ⇔ v_{i} ≤ v_{j}

François Glineur, FPMs  Page 7  LAMSADE, Université Paris-Dauphine

[figure]

⋄ Si on peut associer à chaque alternative un intervalle de la droite réelle U_{i} = [v_{i} v′_{i}] tel que

A_{i} I A_{j} ⇔ U_{i} ∩ U_{j} ≠ ∅

et

A_{i} S A_{j} ⇔ v′_{i} < v_{j} ,

R est un ordre d’intervalle (complet). S est transitive mais I ne l’est pas.

⋄ Si on peut associer à chaque alternative un intervalle de la droite réelle U_{i} = [v_{i} v′_{i}] tel que

A_{i} I A_{j} ⇔ U_{i} ∩ U_{j} ≠ ∅ ,
A_{i} S A_{j} ⇔ v′_{i} < v_{j}

et si aucun intervalle n’est inclus strictement dans un autre, R est un semiordre (complet). S est transitive mais I ne l’est pas.

François Glineur, FPMs  Page 8  LAMSADE, Université Paris-Dauphine

[figure]

[figure]

Quelques exemples

⋄ Ordre complet (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix})

[figure: a; b; c]

⋄ Préordre complet (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{matrix})

[figure: a; b, c]

⋄ Ordre d’intervalle (\begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix})

[figure: {; [; a; ]; [; b; ]; [; c; ]; }; d]

⋄ Semiordre (\begin{matrix}1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 \end{matrix})

[figure: [; a; ]; [; b; {; ]; [; }; d; c; ]]

François Glineur, FPMs  Page 9  LAMSADE, Université Paris-Dauphine

[figure]

\overline{Théorèmes}

Soit R une relation de préférence sans alternatives équivalentes (a et b sont équivalentes ssi a R x ⇔ b R x et x R a ⇔ x R b ∀x ∈ A)

⋄ Si R est un semiordre, il existe un unique ordre complet sous-jacent à R. Il s’agit de l’ordre des nombres {v_{i}} (ou {v′_{i}}). De plus, si on ordonne les lignes et les colonnes de la représentation matricielle de R selon cet ordre, on obtient une matrice échelonnée.

⋄ Si R est un ordre d’intervalle, il existe deux ordres complets sous-jacent à R. De plus, si on ordonne les lignes (et les colonnes) de la représentation matricielle de R selon le premier (et le second) de ces ordres, on obtient aussi une matrice échelonnée.

François Glineur, FPMs  Page 10  LAMSADE, Université Paris-Dauphine

[figure]

⋄

(\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{matrix})

est une matrice échelonnée

[figure]

[figure]

Méthode stochastique

Une relation de préférence

Soit R une relation de préférence complète et réflexive. Nous procédons comme suit :

1. Construction d’une chaîne de Markov : Associer un état E_{i} à chaque alternative A_{i}

2. Choisir les probabilités de transition, en respectant les conditions suivantes ⋄ p_{i,j} > 0 si A_{i} R A_{j} ⋄ p_{i,j} = 0 si A_{i} ¬R A_{j} ⋄ La matrice {p_{i,j}} est stochastique

3. Calculer la distribution stationnaire et classer les alternatives selon les probabilités résultantes

Justification

Intuitivement, ce processus ne peut passer que d’une alternative à une alternative préférée (ou équivalente). Il est donc raisonnable de penser que les meilleures alternatives auront une forte probabilité dans la distribution stationnaire.

François Glineur, FPMs  Page 12  LAMSADE, Université Paris-Dauphine

[figure]

Choix des {p_{i,j}}

Objectif : valeur de p_{i,j} indépendante des alternatives autres que A_{i} et A_{j}

Si A_{i} R A_{j}, poser p_{i,j} = \frac{1}{n}, sinon poser p_{i,j} = 0

Mais M n’est pas nécessairement stochastique ⇒ modifier p_{i,i} selon

p_{i,i} = 1 − ∑_{j≠i} p_{i,j}

Avec ce choix, le processus de Markov peut être interprété comme suit :

1. Je suis à l’état E_{i}

2. Choisir au hasard un état E_{j} (de façon équiprobable)

3. Si A_{i} R A_{j}, passer à l’état E_{j}, sinon rester en E_{i}

François Glineur, FPMs  Page 13  LAMSADE, Université Paris-Dauphine

[figure]

\overline{Exemples}

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}) donne M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & \frac{2}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{2}{3} \end{matrix} )

[figure: a; b; c]

La distribution stationnaire est ( \frac{1}{4}  \frac{1}{4}  \frac{1}{2} ) : c

est en tête, a et b suivent.

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}) donne M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & \frac{2}{3} & \frac{1}{3} \\ 0 & 0 & 1 \end{matrix})

[figure: a; b; c]

La distribution stationnaire est (_{0} _{0} _{1}) : c est en tête mais nous n’avons plus d’information distinguant les autres alternatives (impossible de quitter l’état c)

François Glineur, FPMs  Page 14  LAMSADE, Université Paris-Dauphine

[figure]

Amélioration du choix des {p_{i,j}}

Ajoutons un état fictif neutre E_{0}, ne représentant aucune alternative, tel que p_{0,0} = 0 et p_{0,i} = \frac{1}{n}. Les transitions depuis cet état ne favorisent aucune alternative. Nous gardons la règle

Si A_{i} R A_{j}, poser p_{i,j} = \frac{1}{n}, sinon poser p_{i,j} = 0

mais choisissons les p_{i,0} pour rendre la matrice stochastique, i.e.

p_{i,0} = 1 − ∑_{j≠0} p_{i,j}

Avec ce choix, le processus de Markov peut être interprété comme suit :

François Glineur, FPMs  Page 15  LAMSADE, Université Paris-Dauphine

[figure]

1. Je suis à l’état E_{i}

2. Choisir au hasard un état E_{j} (de façon équiprobable)

3. Si A_{i} R A_{j}, passer à l’état E_{j}, sinon passer à l’état neutre E_{0}

[figure]

\overline{Exemples}

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}) donne M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

La distribution stationnaire est ( \frac{7}{27} \frac{6}{27} \frac{9}{27} \frac{5}{27} ) : c est en tête, b est le moins bon

R = (\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{matrix}) donne M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & \frac{1}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

La distribution stationnaire est ( \frac{4}{27} \frac{6}{27} \frac{9}{27} \frac{8}{27} ) : c est en tête, a est le moins bon

\overline{Propriété}

Si R est un préordre complet, les probabilités de la distribution stationnaire sont correspondent à ce préordre

François Glineur, FPMs  Page 17  LAMSADE, Université Paris-Dauphine

[figure]

[figure]

Cas multicritère

R = ensemble de relations de préférence {R_{i}} où chaque R_{i} est complète et réflexive. Ces relations sont pondérées par des poids {w_{i}} de somme égale à 1. M_{i} = matrice stochastique pour chaque R_{i} (calculée comme ci-dessus). Soit

M = ∑_{i} w_{i}M_{i}

M est aussi stochastique et décrit une chaîne de Markov. Nous classons les alternatives selon les probabilités résultant de la distribution stationnaire.

François Glineur, FPMs  Page 18  LAMSADE, Université Paris-Dauphine

[figure]

1. Je suis à l’état E_{i}

2. Choisir au hasard une relation R_{p} (selon les poids {w_{i}})

3. Choisir au hasard un état E_{j} (de façon équiprobable)

4. Si A_{i} R A_{j}, passer à l’état E_{j}, sinon passer à l’état neutre E_{0}

François Glineur, FPMs  Page 19  LAMSADE, Université Paris-Dauphine

[figure]

\overline{Exemples}

r = 2, w_{1} = \frac{1}{3} et w_{2} = \frac{2}{3}

M_{1} = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & 0 & \frac{1}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix}) M_{2} = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

M = (\begin{matrix}\frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & \frac{1}{3} & \frac{1}{9} & \frac{5}{9} \\ \frac{2}{9} & \frac{2}{9} & \frac{1}{3} & \frac{2}{9} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \end{matrix})

R_{1} : [figure: b; a; c] R_{2} : [figure: b; a; c]

La distribution stationnaire est ( \frac{16}{79} \frac{24}{79} \frac{21}{79} \frac{18}{79} ) : b est en tête, a est le moins bon

François Glineur, FPMs  Page 20  LAMSADE, Université Paris-Dauphine

[figure]

[figure]

Ajouter l’incomparabilité

\overline{Motivation}

Au vu du théorème d’Arrow, il est illusoire d’espérer de bonnes propriétés d’une méthode d’analyse multicritère produisant un préordre complet. ⇒ Affaiblir la relation produite par notre méthode Pas de distinction entre A_{i} S A_{j} et A_{i} I A_{j} (indifférence et préférence stricte) Quand A_{i} et A_{j} sont indifférents, choisir quelque chose de moins radical que p_{i,j} = \frac{1}{n} :

⋄ Si A_{i} S A_{j}, poser p_{i,j} = \frac{1}{n} ⋄ Si A_{i} I A_{j}, poser p_{i,j} = \frac{α}{n} ⋄ Sinon let p_{i,j} = 0

où α est un paramètre à choisir entre 0 et 1

François Glineur, FPMs  Page 21  LAMSADE, Université Paris-Dauphine

[figure]

Le processus de Markov peut à présent être interprété comme suit :

1. Je suis à l’état E_{i}

2. Choisir au hasard une relation R_{p} (selon les poids {w_{i}})

3. Choisir au hasard un état E_{j} (de façon équiprobable) ⋄ Si A_{i} S_{p} A_{j}, passer à l’état E_{j} ⋄ Si A_{i} I_{p} A_{j}, passer à l’état E_{j} avec une probabilité α ou à l’état neutre E_{0} avec une probabilité 1 − α ⋄ Sinon, passer à l’état neutre E_{0}

Utiliser cette famille de préordres complets paramétrée par α pour construire une relation partielle :

⋄ Si A_{i} est meilleur que A_{j} pour toutes

les valeurs de α, déclarer A_{i} > A_{j} ⋄ Si A_{i} est moins bon que A_{j} pour toutes

les valeurs de α, déclarer A_{i} < A_{j} ⋄ Sinon, déclarer A_{i} et A_{j} incomparables

François Glineur, FPMs  Page 22  LAMSADE, Université Paris-Dauphine

[figure]

\overline{Exemples}

Ordre complet Préordre complet Ordre d’intervalle Semiordre

François Glineur, FPMs  Page 23  LAMSADE, Université Paris-Dauphine

[figure]

Propriétés

Si R est un préordre complet, le rangement obtenu est conforme à R ∀α ∈ [0 1] Si R est un semiordre, le rangement obtenu correspond à l’unique ordre complet sous-jacent R ∀α ∈]0 1[ Si R est un ordre d’intervalle, les rangements obtenus pour α tendant vers 0 et 1 correspondent aux deux ordres complets sous-jacents à R ⇒ il y a au moins un cas d’incomparabilité

\overline{Utilisation}

Si on doit sélectionner une seule alternative, choisir parmi toutes celles se trouvant en tête pour au moins une valeur de α (celles-ci étant incomparables entre elles) Plus un croisement est proche de 0 ou 1, moins l’incomparabilité associée est prononcée

François Glineur, FPMs  Page 24  LAMSADE, Université Paris-Dauphine

[figure]

Illustrations - Semiordres

[figure]

[figure]

Localisation d’usine

⋄ 5 critères numériques : Prix, Transport, Environnement, Résidents, Compétition

⋄ Utilisation de seuils pour calculer un semiordre pour chaque critère

François Glineur, FPMs  Page 26  LAMSADE, Université Paris-Dauphine

[figure]

[figure]

Conclusions

Méthode stochastique

⋄ Principe intuitif ⋄ Résultats graphiques ⋄ Pas de paramètre à fixer ⋄ Implémentation aisée

Analyse multicritère

⋄ Généralisation naturelle ⋄ Analyse de sensibilité facile à réaliser ⋄ Exploitation d’information cardinale

possible

Perspectives

⋄ Propriétés théoriques (indépendance) ⋄ Relations valuées

François Glineur, FPMs  Page 27  LAMSADE, Université Paris-Dauphine