Preference Analysis Using Random Spanning Trees: A Stochastic Sampling Approach to Inconsistent Pairwise Comparisons

1. Problématique

L'article aborde un défi fondamental dans l'analyse de la décision multicritère : l'incertitude inhérente aux jugements humains lors de comparaisons par paires.

• Inconsistance des jugements : Les décideurs produisent souvent des jugements incohérents (par exemple, si A > B et B > C, alors A devrait être > C, mais les intensités relatives peuvent ne pas respecter la transitivité cardinale).
• Limites des méthodes traditionnelles : Les approches classiques (comme l'AHP avec la méthode du vecteur propre à droite ou la moyenne géométrique des lignes) traitent l'inconsistance comme une erreur à minimiser. Elles forcent la production d'un unique vecteur de priorité, rejetant ainsi l'information contenue dans la distribution des incohérences.
• Complexité computationnelle : Une approche conceptuellement supérieure, l'analyse des arbres couvrants (spanning trees), permet d'énumérer toutes les combinaisons de jugements indépendants pour générer l'ensemble complet des vecteurs de priorité cohérents. Cependant, le nombre de combinaisons croît de manière exponentielle ($m^{m-2}n^{n-2}$), rendant l'énumération complète impossible pour des problèmes réalistes (ex: des milliards de combinaisons).
• Données incomplètes : Dans les grands problèmes, les décideurs ne peuvent souvent pas fournir toutes les comparaisons par paires. Les méthodes existantes nécessitent alors une imputation des données manquantes, ce qui peut fausser les résultats.

2. Méthodologie

Les auteurs proposent un cadre stochastique basé sur l'échantillonnage aléatoire pour contourner la barrière computationnelle tout en préservant l'information sur l'incertitude.

• Approche par Arbres Couvrants : Au lieu de chercher une solution unique, la méthode considère chaque arbre couvrant (sous-ensemble de $n-1$ jugements indépendants) comme une « mentalité » cohérente du décideur. Chaque arbre génère un vecteur de priorité distinct.
• Échantillonnage par Marche Aléatoire (Random Walk) : Pour éviter l'énumération exhaustive, l'article utilise un algorithme de marche aléatoire (basé sur les travaux d'Aldous et Broder) pour générer un échantillon statistiquement représentatif d'arbres couvrants. Cette méthode garantit que chaque arbre a une probabilité uniforme d'être sélectionné.
• Gestion des données incomplètes : L'approche s'applique nativement aux matrices de comparaison par paires incomplètes en utilisant la formule de Kirchhoff, sans nécessiter d'imputation de données manquantes.
• Indicateurs de Performance : À partir de l'échantillon, deux métriques probabilistes sont calculées :
  1. Indice de Victoire par Paires (PWI - Pairwise Winning Index) : La probabilité qu'une alternative $a_i$ soit préférée à une alternative $a_j$.
  2. Indice d'Acceptabilité de Rang (RAI - Rank Acceptability Index) : La probabilité qu'une alternative occupe un rang spécifique (1er, 2ème, etc.).
• Détermination de la taille de l'échantillon : En utilisant la théorie de l'échantillonnage statistique, les auteurs établissent une formule pour déterminer le nombre d'itérations nécessaire ($It$) pour atteindre une précision $\lambda$ avec un niveau de confiance $C$ :
  $$It(\lambda, C) = \frac{Z_C^2}{4\lambda^2}$$
  Par exemple, pour une précision de $\pm 1\%$ avec 99 % de confiance, environ 16 641 itérations suffisent.

3. Contributions Clés

1. Reconceptualisation de l'inconsistance : L'inconsistance n'est plus vue comme un bruit à éliminer, mais comme un signal d'incertitude révélant la pluralité des préférences possibles au sein d'un même décideur.
2. Cadre d'échantillonnage stochastique : Développement d'une méthode pratique permettant d'analyser des problèmes à grande échelle (des milliards de combinaisons) en utilisant un nombre gérable d'itérations (~20 000), rendant l'approche des arbres couvrants opérationnelle.
3. Robustesse aux données incomplètes : La méthode fonctionne directement avec des matrices incomplètes, éliminant le besoin d'estimations arbitraires des valeurs manquantes.
4. Validation rigoureuse :
   • Exemple didactique (Choix d'écoles) : Comparaison avec l'énumération complète (944 784 combinaisons). Les résultats de l'échantillonnage aléatoire correspondent à moins de 1 % de l'énumération complète.
   • Étude de cas réelle (Infrastructure télécom) : Application à un problème de sélection d'infrastructure avec 6 critères et 4 alternatives, impliquant 21,7 milliards de combinaisons d'arbres couvrants. L'échantillonnage a fourni des estimations stables avec un écart-type inférieur à 0,005.

4. Résultats Principaux

• Précision et Stabilité : Dans l'étude de cas télécom, 20 expériences indépendantes de 20 000 itérations chacune ont produit des résultats très cohérents. Les écarts-types des fréquences de préférence et de rang étaient négligeables (< 0,005), confirmant la fiabilité de l'approche stochastique.
• Analyse des préférences :
  • Pour le problème télécom, l'analyse a révélé que les options « Fibre » et « Courant porteur » étaient clairement dominées.
  • Une incertitude significative existait entre « Micro-ondes » et « Satellite », qui étaient tous deux fortement préférés aux autres, mais dont la hiérarchie relative était moins tranchée (PWI de 51 % pour le micro-ondes face au satellite).
  • Les indices RAI ont montré que le satellite avait une probabilité de 45,3 % d'être classé 1er, mais aussi une faible probabilité d'être classé dernier, offrant une vue nuancée du risque.
• Comparaison avec les méthodes traditionnelles : Contrairement aux méthodes traditionnelles qui donnent un seul classement (ex: Satellite > Micro-ondes > Fibre > Courant), la nouvelle approche fournit une distribution de probabilités, permettant au décideur de comprendre la robustesse de son choix.

5. Signification et Impact

Ce travail transforme l'analyse des préférences en passant d'une logique déterministe (trouver la « vraie » préférence) à une logique probabiliste (caractériser l'incertitude).

• Prise de décision éclairée : Les décideurs ne reçoivent pas seulement un gagnant, mais une mesure de la confiance qu'ils peuvent avoir en ce gagnant. Une forte dispersion des résultats (faible PWI/RAI) signale un besoin de réflexion ou de collecte de données supplémentaires.
• Évolutivité : La méthode rend possible l'analyse de problèmes complexes et réels qui étaient auparavant inaccessibles en raison de la croissance exponentielle des combinaisons.
• Intégrité des données : En acceptant les données incomplètes sans imputation, la méthode préserve l'intégrité des jugements fournis par les parties prenantes, évitant les biais introduits par le remplissage de données manquantes.

En conclusion, l'article propose un outil robuste et scalable qui intègre l'incertitude humaine directement dans le processus décisionnel, offrant une alternative supérieure aux méthodes d'agrégation ponctuelle traditionnelles pour les problèmes multicritères complexes.