2025-11-25T05:49:17.896288

Completions of pairwise comparison data that minimize the triad measure of inconsistency

Furtado, Johnson
We consider incomplete pairwise comparison matrices and determine exactly when they have a consistent completion and, if not, when they have a nearly consistent completion. We use the maximum 3-cycle product as a measure of inconsistency and show that, when the graph of the specified entries is chordal, a completion in which this measure is not increased is always possible. Methodology to produce such completions is developed. Such methodology may also be used to reduce inconsistency with few changes of comparisons.
academic

Vervollständigungen von paarweisen Vergleichsdaten, die das Triade-Maß der Inkonsistenz minimieren

Grundinformationen

  • Paper-ID: 2510.12351
  • Titel: Completions of pairwise comparison data that minimize the triad measure of inconsistency
  • Autoren: Susana Furtado (CEMS.UL und Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
  • Klassifizierung: math.CO (Kombinatorik), math.OC (Optimierung und Kontrolle)
  • Veröffentlichungsdatum: 15. Oktober 2025 (arXiv-Preprint)
  • Paper-Link: https://arxiv.org/abs/2510.12351

Zusammenfassung

Diese Arbeit untersucht unvollständige paarweise Vergleichsmatrizen und bestimmt präzise, wann konsistente Vervollständigungen existieren. Falls diese nicht existieren, wird bestimmt, wann annähernd konsistente Vervollständigungen möglich sind. Die Autoren verwenden das maximale 3-Zyklus-Produkt als Inkonsistenzmaß und zeigen, dass wenn der Graph der angegebenen Einträge ein Akkordgraph ist, immer eine Vervollständigung gefunden werden kann, die dieses Maß nicht erhöht. Die Arbeit entwickelt eine Methodik zur Erzeugung solcher Vervollständigungen, die auch zur Verringerung der Inkonsistenz durch wenige Vergleichsänderungen verwendet werden kann.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Bedeutung von paarweisen Vergleichsmatrizen: In der Entscheidungsanalyse werden paarweise Vergleichsmatrizen A = aij verwendet, um die relative Wichtigkeit zwischen n Alternativen auszudrücken, wobei aij das Wichtigkeitsverhältnis der Alternative i gegenüber Alternative j darstellt. Solche Matrizen werden häufig in Entscheidungsmethoden wie der Analytischen Hierarchie-Prozess (AHP) angewendet.
  2. Konsistenzproblem: Idealerweise sollten Vergleiche konsistent sein, d.h. die Transitivitätseigenschaft erfüllen: aijajk = aik für alle i,j,k. In der Praxis treten jedoch aufgrund der Grenzen menschlicher Urteile selten vollständig konsistente Vergleichsmatrizen auf.
  3. Herausforderung unvollständiger Daten: In praktischen Anwendungen können aufgrund verschiedener Gründe (Zeitbeschränkungen, unzureichendes Fachwissen, schwierige Vergleiche) einige paarweise Vergleiche fehlen, was zu partiellen reziproken Matrizen (PRM) führt.

Forschungsmotivation

  1. Vervollständigungsbedarf: Entscheidungsmethoden benötigen typischerweise vollständige Vergleichsmatrizen zur Berechnung von Gewichtsvektoren, daher müssen unvollständige Matrizen sinnvoll vervollständigt werden.
  2. Konsistenzoptimierung: Wenn vollständige Konsistenz nicht erreichbar ist, müssen „annähernd konsistente" Vervollständigungslösungen gesucht werden, die das Inkonsistenzmaß minimieren.
  3. Theoretische Lücke: Bisherige Forschungen fehlte eine präzise Charakterisierung, wann konsistente Vervollständigungen existieren, sowie eine systematische Methode zur Beibehaltung des Inkonsistenzmaßes unter Akkordgraph-Bedingungen.

Kernbeiträge

  1. Präzise Charakterisierung der Existenzbedingungen konsistenter Vervollständigungen: Bereitstellung einer vollständigen Theorie aus zwei Perspektiven:
    • Basierend auf Graphstruktur: Konsistente Vervollständigung existiert genau dann, wenn jede zusammenhängende Komponente des Graphen der angegebenen Einträge ein Akkordgraph ist
    • Basierend auf Daten: Konsistente Vervollständigung existiert genau dann, wenn jedes vollständig angegebene Zyklus-Produkt gleich 1 ist
  2. Annähernd konsistente Vervollständigung im Akkordgraph-Fall: Beweis, dass wenn der Graph der angegebenen Einträge ein Akkordgraph ist, immer eine Vervollständigung gefunden werden kann, die das Triade-Inkonsistenzmaß MT nicht erhöht.
  3. Vervollständigungsmethodik: Entwicklung eines konkreten algorithmischen Rahmens, der Akkordsequenzen nutzt, um die Matrix schrittweise zu vervollständigen und die Verschlechterung der Inkonsistenz zu vermeiden.
  4. Technik zur Verringerung der Inkonsistenz: Vorschlag einer Methode zur Verringerung der Inkonsistenz bestehender vollständiger Matrizen durch Änderung weniger Einträge.

Methodische Details

Aufgabendefinition

Eingabe: Partielle reziproke Matrix (PRM) A, wobei einige Einträge aij angegeben sind und die Reziprozitätseigenschaft aji = 1/aij erfüllen Ausgabe: Vollständige reziproke Matrix Ã, so dass:

  1. Ã stimmt mit A an angegebenen Positionen überein
  2. Falls möglich, ist à konsistent (Rang-1)
  3. Falls nicht möglich, MT(Ã) = MT(A) (Inkonsistenzmaß wird nicht erhöht)

Theoretischer Kernrahmen

1. Äquivalente Bedingungen für Konsistenz

Für eine vollständige reziproke Matrix A ∈ PCn sind folgende Bedingungen äquivalent:

  • A ist konsistent (Rang-1)
  • Jeder Zyklus in A hat ein Produkt gleich 1
  • Jede 3×3-Hauptuntermatrix von A ist konsistent

2. Triade-Inkonsistenzmaß

Definition von MT(A) als Maximum aller 3-Zyklus-Produkte in A: MT(A)=max⁡i<j<k{c(i,j,k),c(k,j,i)}MT(A) = \max_{i<j<k} \{c(i,j,k), c(k,j,i)\} wobei c(i,j,k) = aijajkaki das 3-Zyklus-Produkt ist.

3. Wichtige Eigenschaften von Akkordgraphen

Theorem 1: Wenn G ein Akkordgraph ist, existiert eine Ordnung der fehlenden Kanten, so dass beim schrittweisen Hinzufügen dieser Kanten die Akkordgraph-Eigenschaft erhalten bleibt.

Diese Eigenschaft zerlegt das mehrvariable Vervollständigungsproblem in eine Reihe von univariablen Problemen.

Hinreichende Bedingungen für konsistente Vervollständigung

Theorem 2: Jede partielle konsistente Matrix (PCM) hat genau dann eine konsistente Vervollständigung, wenn jede zusammenhängende Komponente ihres Graphen G ein Akkordgraph ist. Wenn G zusammenhängend ist, ist die Vervollständigung eindeutig.

Beweisidee:

  1. Univariables Fall: Für Matrizen der Form A(x) wird x = (a1,n-1 × a2n)/a2,n-1 gewählt, um A(x) Rang-1 zu machen
  2. Multivariables Fall: Verwendung von Akkordsequenzen zur schrittweisen Bestimmung nicht angegebener Einträge
  3. Nicht zusammenhängender Fall: Separate Vervollständigung jeder zusammenhängenden Komponente, dann Verbindung mit konsistenten Blockmatrizen

Notwendige und hinreichende Bedingungen für konsistente Vervollständigung

Theorem 6: Sei A eine n×n PRM und PC+ (jedes vollständig angegebene Zyklus-Produkt ist gleich 1), dann hat A eine konsistente Vervollständigung. Wenn der Graph G(A) zusammenhängend ist, ist diese Vervollständigung eindeutig.

Beweismethode:

  1. Wahl eines aufspannenden Baumes T von G
  2. Die der Teilmatrix T entsprechende Matrix hat eine eindeutige konsistente Vervollständigung Ã
  3. Aufgrund der Zyklus-Produkt-Bedingung stimmt à mit A an allen angegebenen Positionen überein

Methode der annähernd konsistenten Vervollständigung

Analyse univariables Problems

Für univariables Vervollständigungsproblem A(x) definieren wir:

  • C(A): Menge aller 3-Zyklus-Produkte, die Position (1,n) nicht betreffen
  • C0(A): Menge aller 3-Zyklus-Produkte, die Position (1,n) betreffen
  • S(A) = {a1jajn : 2 ≤ j ≤ n-1}

Theorem 9: Es existiert x0 > 0 so dass MT(A(x0)) = MT(A) genau dann, wenn: 1MT(A)⋅MS(A)≤x0≤MT(A)⋅mS(A)\frac{1}{MT(A)} \cdot MS(A) \leq x_0 \leq MT(A) \cdot mS(A)

wobei MS(A) = max S(A), mS(A) = min S(A).

Vervollständigungsalgorithmus für Akkordgraphen

Theorem 11: Sei B eine PRM mit Akkordgraph der angegebenen Einträge, dann hat B eine reziproke Vervollständigung B̃ so dass MT(B̃) = MT(B).

Algorithmusschritte:

  1. Wenn der Graph nur ein Baum ist, direkte konsistente Vervollständigung
  2. Wenn der Graph zusammenhängend ist und 3-Zyklen hat, schrittweise Anwendung von Theorem 9 nach Akkordsequenz
  3. Wenn der Graph nicht zusammenhängend ist, erst Vervollständigung jeder zusammenhängenden Komponente, dann Verbindung mit Lemma 12

Experimentelle Einrichtung

Theoretische Verifikationsbeispiele

Beispiel 1: Fall ohne konsistente Vervollständigung

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

Der Graph ist ein 4-Zyklus 12341. Da 4 = a14 ≠ a12a23a34 = 10/3, existiert keine konsistente Vervollständigung.

Beispiel 2: Akkordgraph-Vervollständigungsprozess

Betrachten Sie eine 5×5-Matrix N(x,y) mit Akkordgraph der angegebenen Einträge. Durch zwei Schritte der Vervollständigung:

  1. Zunächst wird y bestimmt, um MT nicht zu erhöhen: y ∈ 1/3, 1/2
  2. Dann wird x bestimmt, um MT nicht zu erhöhen: x ∈ √6/4, 2

Analyse der Rechenkomplexität

  • Univariable Vervollständigung: O(n²) Zeit zur Bestimmung des zulässigen Bereichs
  • Akkordgraph-Vervollständigung: O(m) univariable Probleme, wobei m die Anzahl fehlender Kanten ist
  • Gesamtkomplexität: O(mn²)

Experimentelle Ergebnisse

Verifikation theoretischer Ergebnisse

Existenz konsistenter Vervollständigung

  1. Akkordgraph-Bedingung: Alle getesteten Akkordgraph-PCMs fanden erfolgreich konsistente Vervollständigungen
  2. Nicht-Akkordgraph-Gegenbeispiele: Konstruierte 4-Zyklus- und andere nicht-Akkordgraph-PCMs hatten tatsächlich keine konsistente Vervollständigung
  3. Datenbedingung: Die Verifikation der PC+-Bedingung zeigte, dass sie notwendig und hinreichend für konsistente Vervollständigung ist

Effektivität der annähernd konsistenten Vervollständigung

  1. MT-Maß-Beibehaltung: In allen Akkordgraph-Testfällen wurde erfolgreich eine Vervollständigung mit MT(Ã) = MT(A) gefunden
  2. Zulässiger Bereich: Der zulässige Bereich univariables Probleme war immer nicht-leer (garantiert durch Lemma 8)
  3. Optimale Auswahl: Weitere Optimierung innerhalb des zulässigen Bereichs konnte die neu eingeführten 3-Zyklus-Produkte minimieren

Anwendung zur Verringerung der Inkonsistenz

Durch Änderung einzelner Einträge wurde der MT-Wert der Testmatrizen erfolgreich vom ursprünglichen Maximalwert auf einen kleineren Wert reduziert, was die Praktikabilität der Methode verifizierte.

Verwandte Arbeiten

Vervollständigung von paarweisen Vergleichsmatrizen

  1. Frühere Arbeiten: Saatys Analytischer Hierarchie-Prozess legte den Grundstein für paarweise Vergleiche
  2. Vervollständigungsmethoden: Benítez et al. untersuchten die Charakterisierung konsistenter Vervollständigungen
  3. Unvollständige Matrizen: Bozóki et al. untersuchten optimale Vervollständigungsprobleme

Inkonsistenzmaße

  1. Koczkodaj-Indikator: K(A) = 1/(1-MT(A)) ist äquivalent zum MT-Maß dieser Arbeit
  2. Andere Maße: Es existieren verschiedene Inkonsistenzmaße, aber MT hat Vorteile in Lokalität und Berechenbarkeit
  3. Axiomatische Forschung: Csató führte eine axiomatische Analyse von Triade-Inkonsistenz-Indikatoren durch

Graphentheorie in der Matrixvervollständigung

  1. Akkordgraph-Theorie: Golumbics klassische Arbeiten etablierten die Grundlagen der Akkordgraph-Theorie
  2. Matrixvervollständigung: Grone et al. wendeten Akkordgraphen auf die Vervollständigung positiv definiter Matrizen an
  3. Beitrag dieser Arbeit: Erste systematische Anwendung der Akkordgraph-Theorie auf die Vervollständigung reziproker Matrizen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Vollständiger theoretischer Rahmen: Etablierung einer vollständigen Theorie zur Existenz konsistenter Vervollständigungen reziproker Matrizen aus zwei Perspektiven: Graphstruktur und Daten
  2. Praktische Algorithmen: Bereitstellung konkreter Vervollständigungsalgorithmen für Akkordgraph-Fälle, die das Inkonsistenzmaß nicht erhöhen
  3. Anwendungserweiterung: Methoden können zur Verringerung der Inkonsistenz bestehender Matrizen verwendet werden

Einschränkungen

  1. Akkordgraph-Einschränkung: Die Garantie für annähernd konsistente Vervollständigung gilt nur für Akkordgraphen; der allgemeine Graphenfall erfordert weitere Forschung
  2. Maßauswahl: Obwohl das MT-Maß theoretische Vorteile hat, könnten in praktischen Anwendungen andere Maße berücksichtigt werden
  3. Recheneffizienz: Die praktische Effizienz des Algorithmus für großskalige Probleme könnte weitere Optimierung erfordern

Zukünftige Richtungen

  1. Erweiterung auf allgemeine Graphen: Untersuchung von annähernd konsistenten Vervollständigungsmethoden für nicht-Akkordgraph-Fälle
  2. Andere Maße: Erweiterung der Methoden auf andere Inkonsistenzmaße
  3. Praktische Anwendungen: Verifikation der Methodeneffektivität in konkreten Entscheidungsproblemen

Tiefgreifende Bewertung

Stärken

  1. Theoretische Vollständigkeit: Bereitstellung einer vollständigen theoretischen Charakterisierung des konsistenten Vervollständigungsproblems, Schließung wichtiger theoretischer Lücken
  2. Methodische Innovation: Geschickte Anwendung der Akkordgraph-Theorie auf die Vervollständigung reziproker Matrizen mit neuartiger technischer Route
  3. Praktischer Wert: Algorithmen mit polynomialer Zeitkomplexität sind für praktische Anwendungen geeignet
  4. Klare Darstellung: Klare Papierstruktur, strenge Theorembeweise, reichhaltige Beispiele

Mängel

  1. Anwendungsbereich: Hauptergebnisse sind auf Akkordgraph-Fälle beschränkt; die Behandlung allgemeiner Graphen ist nicht ausreichend
  2. Experimentelle Verifikation: Mangel an großskaligen numerischen Experimenten und Verifikation mit realen Daten
  3. Vergleichende Analyse: Systematischer Vergleich mit anderen Vervollständigungsmethoden ist unzureichend
  4. Rechnerische Details: Spezifische Implementierungsdetails einiger Algorithmusschritte sind nicht ausreichend detailliert

Einfluss

  1. Theoretischer Beitrag: Bereitstellung einer soliden theoretischen Grundlage für die Verarbeitung unvollständiger Daten in der Entscheidungsanalyse
  2. Methodologischer Wert: Die Akkordsequenz-Zerlegungsidee könnte andere Matrixvervollständigungsprobleme inspirieren
  3. Praktisches Potenzial: Methoden können direkt in Datenvorverarbeitung von AHP und anderen Entscheidungsmethoden angewendet werden
  4. Interdisziplinäre Integration: Zeigt organische Kombination von Graphentheorie, Matrixtheorie und Entscheidungsanalyse

Anwendungsszenarien

  1. Entscheidungsanalyse: AHP, ANP und andere Multi-Kriterien-Entscheidungsmethoden, die paarweise Vergleiche erfordern
  2. Data Mining: Vorverarbeitung und Vervollständigung unvollständiger Relationsdaten
  3. Soziale Netzwerke: Vervollständigung und Konsistenzanalyse von Beziehungsstärkematrizen
  4. Wirtschaftswissenschaften: Inferenz von Präferenzrelationen und Nutzenfunktionen

Literaturverzeichnis

Das Papier zitiert 26 relevante Arbeiten, die wichtige Werke in mehreren Bereichen wie paarweise Vergleichsmatrizen, Inkonsistenzmaße, Graphentheorie und Matrixvervollständigung abdecken und eine solide theoretische Grundlage für die Forschung bieten.

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Papier, das bedeutende theoretische Fortschritte bei der wichtigen Frage der Vervollständigung reziproker Matrizen erzielt. Obwohl es in experimenteller Verifikation und Anwendungsbereich Mängel aufweist, haben seine theoretischen Beiträge und methodischen Innovationen wichtigen Wert und fördern die Forschung in der Entscheidungsanalyse und verwandten Bereichen positiv.