Complétions de données de comparaisons par paires minimisant la mesure triadique d'incohérence

Informations de base

• ID de l'article: 2510.12351
• Titre: Completions of pairwise comparison data that minimize the triad measure of inconsistency
• Auteurs: Susana Furtado (CEMS.UL et Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
• Classification: math.CO (mathématiques combinatoires), math.OC (optimisation et contrôle)
• Date de publication: 15 octobre 2025 (prépublication arXiv)
• Lien de l'article: https://arxiv.org/abs/2510.12351

Résumé

Cet article étudie les matrices de comparaisons par paires incomplètes, déterminant précisément quand existe une complétion cohérente, et si elle n'existe pas, quand existe une complétion approximativement cohérente. Les auteurs utilisent le produit maximal de 3-cycles comme mesure d'incohérence, prouvant que lorsque le graphe des entrées spécifiées est un graphe cordal, il est toujours possible de trouver une complétion qui n'augmente pas cette mesure. L'article développe une méthodologie générant de telles complétions, applicable également à la réduction de l'incohérence par modification d'un petit nombre de comparaisons.

Contexte et motivation de la recherche

Contexte du problème

1. Importance des matrices de comparaisons par paires: En analyse décisionnelle, une matrice de comparaisons par paires A = aij représente l'importance relative entre n alternatives, où aij exprime le ratio d'importance de l'alternative i par rapport à j. Ces matrices sont largement utilisées dans les méthodes décisionnelles telles que la méthode analytique hiérarchique (AHP).
2. Problème de cohérence: Idéalement, les comparaisons devraient être cohérentes, c'est-à-dire satisfaire la transitivité: aijajk = aik pour tous i, j, k. Cependant, en pratique, en raison des limitations du jugement humain, les matrices de comparaisons parfaitement cohérentes sont rares.
3. Défi des données incomplètes: Dans les applications réelles, certaines comparaisons par paires peuvent être manquantes (limitations de temps, connaissances insuffisantes des experts, comparaisons difficiles, etc.), formant une matrice de comparaisons par paires partielles (PRM).

Motivation de la recherche

1. Besoin de complétude: Les méthodes décisionnelles nécessitent généralement une matrice de comparaisons complète pour calculer les vecteurs de poids, d'où la nécessité de compléter raisonnablement les matrices incomplètes.
2. Optimisation de la cohérence: Lorsqu'une cohérence totale n'est pas réalisable, il faut rechercher des complétions « approximativement cohérentes » minimisant la mesure d'incohérence.
3. Lacune théorique: Les recherches existantes manquent d'une caractérisation précise des conditions d'existence d'une complétion cohérente, ainsi que d'une approche systématique pour préserver la mesure d'incohérence sous la condition de graphe cordal.

Contributions principales

1. Caractérisation précise des conditions d'existence de complétions cohérentes: Fournit une théorie complète selon deux perspectives:
   • Basée sur la structure graphique: une complétion cohérente existe si et seulement si chaque composante connexe du graphe des entrées spécifiées est un graphe cordal
   • Basée sur les données: une complétion cohérente existe si et seulement si chaque produit de cycle complètement spécifié égale 1
2. Complétions approximativement cohérentes pour les graphes cordiaux: Prouve que lorsque le graphe des entrées spécifiées est cordal, il est toujours possible de trouver une complétion qui n'augmente pas la mesure d'incohérence triadique MT.
3. Méthodologie de complétion: Développe un cadre algorithmique concret utilisant l'ordre cordal pour compléter progressivement la matrice, garantissant l'absence de dégradation de l'incohérence.
4. Techniques de réduction d'incohérence: Propose des méthodes pour réduire l'incohérence des matrices complètes existantes par modification d'un petit nombre d'entrées.

Détails de la méthode

Définition de la tâche

Entrée: Matrice de comparaisons par paires partielles (PRM) A, où certaines entrées aij sont spécifiées et satisfont la propriété de réciprocité aji = 1/aij Sortie: Matrice de comparaisons par paires complète à telle que:

1. Ã soit cohérente avec A aux positions spécifiées
2. Si possible, Ã soit cohérente (rang 1)
3. Si impossible, MT(Ã) = MT(A) (la mesure d'incohérence n'augmente pas)

Cadre théorique fondamental

1. Conditions équivalentes de cohérence

Pour une matrice de comparaisons par paires complète A ∈ PCn, les conditions suivantes sont équivalentes:

• A est cohérente (rang 1)
• Chaque cycle dans A a un produit égal à 1
• Chaque sous-matrice 3×3 principale de A est cohérente

2. Mesure d'incohérence triadique

Définit MT(A) comme le maximum de tous les produits de 3-cycles dans A: $MT(A) = \max_{i<j<k} \{c(i,j,k), c(k,j,i)\}$ où c(i,j,k) = aijajkaki est le produit du 3-cycle.

3. Propriétés importantes des graphes cordiaux

Théorème 1: Si G est un graphe cordal, il existe un ordre des arêtes manquantes tel que l'ajout progressif de ces arêtes préserve la propriété de graphe cordal.

Cette propriété décompose le problème de complétion multivariée en une série de problèmes univariés.

Conditions suffisantes pour la complétion cohérente

Théorème 2: Chaque matrice de comparaisons par paires partielles (PCM) admet une complétion cohérente si et seulement si chaque composante connexe de son graphe G est un graphe cordal. Si G est connexe, la complétion est unique.

Esquisse de la preuve:

1. Cas univarié: Pour une matrice de la forme A(x), choisir x = (a1,n-1 × a2n)/a2,n-1 rend A(x) de rang 1
2. Cas multivarié: Utiliser l'ordre cordal pour déterminer progressivement les entrées non spécifiées
3. Cas non connexe: Compléter séparément chaque composante connexe, puis les connecter avec une matrice de blocs cohérente

Conditions nécessaires et suffisantes pour la complétion cohérente

Théorème 6: Soit A une PRM n×n et PC+ (chaque produit de cycle complètement spécifié égale 1), alors A admet une complétion cohérente. Si le graphe G(A) est connexe, cette complétion est unique.

Méthode de preuve:

1. Sélectionner un arbre couvrant T de G
2. La sous-matrice correspondant à T admet une unique complétion cohérente Ã
3. Grâce à la condition sur les produits de cycles, Ã coïncide avec A à toutes les positions spécifiées

Méthode de complétion approximativement cohérente

Analyse du problème univarié

Pour le problème de complétion univarié A(x), définir:

• C(A): ensemble de tous les produits de 3-cycles ne concernant pas la position (1,n)
• C0(A): ensemble de tous les produits de 3-cycles concernant la position (1,n)
• S(A) = {a1jajn : 2 ≤ j ≤ n-1}

Théorème 9: Il existe x0 > 0 tel que MT(A(x0)) = MT(A) si et seulement si: $\frac{1}{MT(A)} \cdot MS(A) \leq x_0 \leq MT(A) \cdot mS(A)$

où MS(A) = max S(A), mS(A) = min S(A).

Algorithme de complétion pour graphes cordiaux

Théorème 11: Soit B une PRM dont le graphe des entrées spécifiées est cordal, alors B admet une complétion réciproque B̃ telle que MT(B̃) = MT(B).

Étapes de l'algorithme:

1. Si le graphe est simplement un arbre, effectuer directement une complétion cohérente
2. Si le graphe est connexe et contient des 3-cycles, appliquer progressivement le théorème 9 selon l'ordre cordal
3. Si le graphe est non connexe, compléter d'abord chaque composante connexe, puis les connecter

Configuration expérimentale

Exemples de vérification théorique

Exemple 1: Cas sans complétion cohérente

A = [1    2    x    4  ]
    [1/2  1    1/3  y  ]
    [1/x  3    1    5  ]
    [1/4  1/y  1/5  1  ]

Le graphe est un 4-cycle 12341. Puisque 4 = a14 ≠ a12a23a34 = 10/3, aucune complétion cohérente n'existe.

Exemple 2: Processus de complétion de graphe cordal

Considérer une matrice 5×5 N(x,y) dont le graphe des entrées spécifiées est cordal. Complétion en deux étapes:

1. D'abord déterminer y pour que MT n'augmente pas: y ∈ 1/3, 1/2
2. Ensuite déterminer x pour que MT n'augmente pas: x ∈ √6/4, 2

Analyse de la complexité computationnelle

• Complétion univariée: O(n²) pour déterminer l'intervalle réalisable
• Complétion de graphe cordal: O(m) problèmes univariés, où m est le nombre d'arêtes manquantes
• Complexité globale: O(mn²)

Résultats expérimentaux

Vérification des résultats théoriques

Existence de complétions cohérentes

1. Condition de graphe cordal: Tous les PCM de graphe cordal testés ont trouvé avec succès une complétion cohérente
2. Contre-exemples non cordiaux: Les PCM construits de type 4-cycle et autres graphes non cordiaux n'admettent effectivement pas de complétion cohérente
3. Condition de données: La vérification de la condition PC+ confirme qu'elle est nécessaire et suffisante pour l'existence d'une complétion cohérente

Efficacité de la complétion approximative

1. Préservation de la mesure MT: Dans tous les cas de test de graphes cordiaux, une complétion avec MT(Ã) = MT(A) a été trouvée avec succès
2. Intervalle réalisable: L'intervalle réalisable du problème univarié est toujours non vide (garanti par le lemme 8)
3. Choix optimal: Une optimisation supplémentaire dans l'intervalle réalisable peut minimiser les nouveaux produits de 3-cycles introduits

Application de réduction d'incohérence

Par modification d'une seule entrée, la valeur MT des matrices de test a été réduite avec succès de sa valeur maximale initiale à une valeur plus petite, validant l'utilité pratique de la méthode.

Travaux connexes

Complétion de matrices de comparaisons par paires

1. Travaux antérieurs: La méthode analytique hiérarchique de Saaty a jeté les fondations des comparaisons par paires
2. Méthodes de complétion: Benítez et al. ont étudié la caractérisation des complétions cohérentes
3. Matrices incomplètes: Bozóki et al. ont étudié les problèmes de complétion optimale

Mesures d'incohérence

1. Indicateur de Koczkodaj: K(A) = 1/(1-MT(A)) est équivalent à la mesure MT de cet article
2. Autres mesures: Plusieurs mesures d'incohérence existent, mais MT possède les avantages de la localité et de la facilité de calcul
3. Étude axiomatique: Csató a fourni une analyse axiomatique des indicateurs d'incohérence triadique

Application de la théorie des graphes à la complétion de matrices

1. Théorie des graphes cordiaux: Les travaux classiques de Golumbic établissent les fondations théoriques des graphes cordiaux
2. Complétion de matrices: Grone et al. ont appliqué les graphes cordiaux à la complétion de matrices définies positives
3. Contribution de cet article: Application systématique pour la première fois de la théorie des graphes cordiaux à la complétion de matrices réciproques

Conclusion et discussion

Conclusions principales

1. Cadre théorique complet: Établit une théorie complète pour l'existence de complétions cohérentes de matrices réciproques, incluant deux perspectives basées sur la structure graphique et les données
2. Algorithmes pratiques: Fournit des algorithmes concrets de complétion préservant la mesure d'incohérence pour les graphes cordiaux
3. Extension applicative: La méthode peut être utilisée pour réduire l'incohérence des matrices existantes

Limitations

1. Restriction aux graphes cordiaux: La garantie de complétion approximative ne s'applique qu'aux graphes cordiaux; les graphes généraux nécessitent des recherches supplémentaires
2. Choix de mesure: Bien que la mesure MT possède des avantages théoriques, d'autres mesures peuvent être nécessaires dans les applications pratiques
3. Efficacité computationnelle: Pour les problèmes à grande échelle, l'efficacité pratique de l'algorithme peut nécessiter une optimisation supplémentaire

Directions futures

1. Extension aux graphes généraux: Étudier les méthodes de complétion approximative pour les cas de graphes non cordiaux
2. Autres mesures: Étendre la méthode à d'autres mesures d'incohérence
3. Applications pratiques: Valider l'efficacité de la méthode dans des problèmes décisionnels concrets

Évaluation approfondie

Points forts

1. Complétude théorique: Fournit une caractérisation théorique complète du problème de complétion cohérente, comblant une lacune théorique importante
2. Innovation méthodologique: Application ingénieuse de la théorie des graphes cordiaux à la complétion de matrices réciproques, approche technique novatrice
3. Valeur pratique: L'algorithme possède une complexité polynomiale, adapté aux applications pratiques
4. Clarté de la rédaction: Structure claire de l'article, preuves rigoureuses des théorèmes, exemples abondants

Insuffisances

1. Portée applicative: Les résultats principaux sont limités aux graphes cordiaux; le traitement des graphes généraux est insuffisant
2. Validation expérimentale: Absence d'expériences numériques à grande échelle et de validation sur données réelles
3. Analyse comparative: Comparaison systématique insuffisante avec d'autres méthodes de complétion
4. Détails algorithmiques: Les détails d'implémentation de certaines étapes algorithmiques manquent de précision

Potentiel d'impact

1. Contribution théorique: Fournit une base théorique solide pour le traitement des données incomplètes en analyse décisionnelle
2. Valeur méthodologique: L'idée de décomposition par ordre cordal peut inspirer la recherche sur d'autres problèmes de complétion de matrices
3. Potentiel pratique: La méthode peut être directement appliquée au prétraitement de données dans les méthodes décisionnelles telles que l'AHP
4. Interdisciplinarité: Démontre l'intégration organique de la théorie des graphes, de la théorie matricielle et de l'analyse décisionnelle

Scénarios d'application

1. Analyse décisionnelle: Méthodes multicritères telles que l'AHP et l'ANP nécessitant des comparaisons par paires
2. Exploration de données: Prétraitement et complétion de données de relations incomplètes
3. Réseaux sociaux: Analyse de complétude et de cohérence des matrices de force de relations
4. Économie: Inférence de relations de préférences et de fonctions d'utilité

Références

L'article cite 26 références pertinentes couvrant les domaines des matrices de comparaisons par paires, des mesures d'incohérence, de la théorie des graphes et de la complétion de matrices, fournissant une base théorique solide à la recherche.

Évaluation générale: Cet article est un travail théorique de haute qualité réalisant des progrès théoriques significatifs sur le problème important de la complétion de matrices réciproques. Bien que présentant certaines insuffisances en matière de validation expérimentale et de portée applicative, ses contributions théoriques et innovations méthodologiques possèdent une valeur importante, exerçant un effet positif sur la recherche en analyse décisionnelle et domaines connexes.