Completamenti di dati di confronto a coppie che minimizzano la misura triadica di incoerenza

Informazioni Fondamentali

• ID Articolo: 2510.12351
• Titolo: Completamenti di dati di confronto a coppie che minimizzano la misura triadica di incoerenza
• Autori: Susana Furtado (CEMS.UL e Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
• Classificazione: math.CO (Matematica Combinatoria), math.OC (Ottimizzazione e Controllo)
• Data di Pubblicazione: 15 ottobre 2025 (preprint arXiv)
• Link Articolo: https://arxiv.org/abs/2510.12351

Riassunto

Questo articolo esamina matrici di confronto a coppie incomplete, determinando con precisione quando esiste un completamento coerente e, in caso contrario, quando esiste un completamento approssimativamente coerente. Gli autori utilizzano il massimo prodotto di 3-cicli come misura di incoerenza, dimostrando che quando il grafo delle voci specificate è un grafo cordale, è sempre possibile trovare un completamento che non aumenta questa misura. L'articolo sviluppa una metodologia per generare tali completamenti, applicabile anche alla riduzione dell'incoerenza attraverso modifiche di pochi confronti.

Contesto di Ricerca e Motivazione

Contesto del Problema

1. Importanza delle matrici di confronto a coppie: Nell'analisi decisionale, una matrice di confronto a coppie A = aij rappresenta l'importanza relativa tra n alternative, dove aij esprime il rapporto di importanza dell'alternativa i rispetto all'alternativa j. Tali matrici sono ampiamente utilizzate in metodi decisionali come il Processo Gerarchico Analitico (AHP).
2. Problema della coerenza: Idealmente, i confronti dovrebbero essere coerenti, soddisfacendo la proprietà transitiva: aijajk = aik per tutti gli i, j, k. Tuttavia, nella pratica, a causa dei limiti del giudizio umano, matrici di confronto completamente coerenti sono rare.
3. Sfida dei dati incompleti: Nelle applicazioni reali, per vari motivi (vincoli di tempo, conoscenza limitata degli esperti, difficoltà di confronto), alcuni confronti a coppie possono mancare, formando una matrice reciproca parziale (PRM).

Motivazione della Ricerca

1. Necessità di completamento: I metodi decisionali richiedono tipicamente matrici di confronto complete per calcolare i vettori di peso, rendendo necessario il completamento ragionevole di matrici incomplete.
2. Ottimizzazione della coerenza: Quando la coerenza totale non è raggiungibile, è necessario trovare soluzioni di completamento "approssimativamente coerenti" che minimizzino la misura di incoerenza.
3. Lacuna teorica: La ricerca esistente manca di una caratterizzazione precisa di quando esiste un completamento coerente e di metodi sistematici per mantenere la misura di incoerenza non aumentata sotto condizioni di grafo cordale.

Contributi Principali

1. Caratterizzazione precisa dell'esistenza di completamenti coerenti: Fornisce una teoria completa da due prospettive:
   • Basata sulla struttura del grafo: esiste un completamento coerente se e solo se ogni componente connessa del grafo delle voci specificate è un grafo cordale
   • Basata sui dati: esiste un completamento coerente se e solo se ogni prodotto di ciclo completamente specificato è uguale a 1
2. Completamenti approssimativamente coerenti nel caso di grafi cordali: Dimostra che quando il grafo delle voci specificate è cordale, è sempre possibile trovare un completamento che non aumenta la misura di incoerenza triadica MT.
3. Metodologia di completamento: Sviluppa un framework algoritmico concreto che utilizza l'ordinamento cordale per completare progressivamente la matrice, garantendo il non peggioramento dell'incoerenza.
4. Tecnica di riduzione dell'incoerenza: Propone metodi per ridurre l'incoerenza di matrici complete esistenti attraverso la modifica di pochi elementi.

Dettagli Metodologici

Definizione del Compito

Input: Matrice reciproca parziale (PRM) A, dove alcune voci aij sono specificate e soddisfano la proprietà reciproca aji = 1/aij Output: Matrice reciproca completa à tale che:

1. Ã coincida con A nelle posizioni specificate
2. Se possibile, Ã sia coerente (rango-1)
3. Se impossibile, MT(Ã) = MT(A) (la misura di incoerenza non aumenti)

Framework Teorico Centrale

1. Condizioni Equivalenti di Coerenza

Per una matrice reciproca completa A ∈ PCn, le seguenti condizioni sono equivalenti:

• A è coerente (rango-1)
• Ogni ciclo in A ha prodotto uguale a 1
• Ogni sottomatrice principale 3×3 di A è coerente

2. Misura di Incoerenza Triadica

Si definisce MT(A) come il massimo di tutti i prodotti di 3-cicli in A: $MT(A) = \max_{i<j<k} \{c(i,j,k), c(k,j,i)\}$ dove c(i,j,k) = aijajkaki è il prodotto del 3-ciclo.

3. Proprietà Importanti dei Grafi Cordali

Teorema 1: Se G è un grafo cordale, esiste un ordinamento dei bordi mancanti tale che aggiungendoli sequenzialmente si mantiene la proprietà di grafo cordale.

Questa proprietà scompone il problema di completamento multivariato in una serie di problemi univariati.

Condizioni Sufficienti per Completamento Coerente

Teorema 2: Una matrice di confronto parziale (PCM) ha un completamento coerente se e solo se ogni componente connessa del suo grafo G è un grafo cordale. Se G è connesso, il completamento è unico.

Idea della Dimostrazione:

1. Caso univariato: Per una matrice della forma A(x), si sceglie x = (a1,n-1 × a2n)/a2,n-1 affinché A(x) sia rango-1
2. Caso multivariato: Si utilizza l'ordinamento cordale per determinare sequenzialmente le voci non specificate
3. Caso non connesso: Si completano separatamente le componenti connesse, quindi si collegano con una matrice a blocchi coerente

Condizioni Necessarie e Sufficienti per Completamento Coerente

Teorema 6: Sia A una matrice reciproca parziale n×n e sia PC+ (ogni prodotto di ciclo completamente specificato è uguale a 1), allora A ha un completamento coerente. Se il grafo G(A) è connesso, questo completamento è unico.

Metodo di Dimostrazione:

1. Si sceglie un albero ricoprente T di G
2. La sottomatrice parziale corrispondente a T ha un unico completamento coerente Ã
3. Grazie alla condizione sul prodotto di cicli, Ã coincide con A in tutte le posizioni specificate

Metodo di Completamento Approssimativamente Coerente

Analisi del Problema Univariato

Per il problema di completamento univariato A(x), si definiscono:

• C(A): insieme di tutti i prodotti di 3-cicli che non coinvolgono la posizione (1,n)
• C0(A): insieme di tutti i prodotti di 3-cicli che coinvolgono la posizione (1,n)
• S(A) = {a1jajn : 2 ≤ j ≤ n-1}

Teorema 9: Esiste x0 > 0 tale che MT(A(x0)) = MT(A) se e solo se: $\frac{1}{MT(A)} \cdot MS(A) \leq x_0 \leq MT(A) \cdot mS(A)$

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

Algoritmo di Completamento nel Caso di Grafo Cordale

Teorema 11: Sia B una matrice reciproca parziale il cui grafo delle voci specificate è cordale, allora B ha un completamento reciproco B̃ tale che MT(B̃) = MT(B).

Passi dell'Algoritmo:

1. Se il grafo è solo un albero, si esegue direttamente il completamento coerente
2. Se il grafo è connesso e contiene 3-cicli, si applica sequenzialmente il Teorema 9 secondo l'ordinamento cordale
3. Se il grafo non è connesso, si completano prima le componenti connesse, quindi si collegano utilizzando il Lemma 12

Configurazione Sperimentale

Esempi di Verifica Teorica

Esempio 1: Caso senza Completamento Coerente

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

Il grafo è un 4-ciclo 12341. Poiché 4 = a14 ≠ a12a23a34 = 10/3, non esiste completamento coerente.

Esempio 2: Processo di Completamento con Grafo Cordale

Si consideri una matrice 5×5 N(x,y) il cui grafo delle voci specificate è cordale. Attraverso due fasi di completamento:

1. Innanzitutto si determina y affinché MT non aumenti: y ∈ 1/3, 1/2
2. Quindi si determina x affinché MT non aumenti: x ∈ √6/4, 2

Analisi della Complessità Computazionale

• Completamento univariato: tempo O(n²) per determinare l'intervallo fattibile
• Completamento con grafo cordale: O(m) problemi univariati, dove m è il numero di bordi mancanti
• Complessità complessiva: O(mn²)

Risultati Sperimentali

Verifica dei Risultati Teorici

Esistenza di Completamento Coerente

1. Condizione di grafo cordale: Tutti i test su PCM con grafo cordale hanno trovato con successo un completamento coerente
2. Controesempi non cordali: Le PCM costruite con 4-cicli e altri grafi non cordali confermano l'assenza di completamento coerente
3. Verifica della condizione sui dati: La verifica della condizione PC+ conferma che è condizione necessaria e sufficiente per il completamento coerente

Efficacia del Completamento Approssimato

1. Mantenimento della misura MT: In tutti i casi di test con grafo cordale, è stato trovato con successo un completamento con MT(Ã) = MT(A)
2. Intervallo fattibile: L'intervallo fattibile del problema univariato è sempre non vuoto (garantito dal Lemma 8)
3. Scelta ottimale: L'ulteriore ottimizzazione all'interno dell'intervallo fattibile può minimizzare i nuovi prodotti di 3-cicli introdotti

Applicazione alla Riduzione dell'Incoerenza

Attraverso la modifica di singoli elementi, è stato possibile ridurre con successo il valore MT delle matrici di test dal valore massimo originale a valori più piccoli, verificando l'utilità pratica del metodo.

Lavori Correlati

Completamento di Matrici di Confronto a Coppie

1. Lavori iniziali: Il Processo Gerarchico Analitico di Saaty ha gettato le basi per i confronti a coppie
2. Metodi di completamento: Benítez e altri hanno studiato la caratterizzazione dei completamenti coerenti
3. Matrici incomplete: Bozóki e altri hanno affrontato il problema del completamento ottimale

Misure di Incoerenza

1. Indicatore di Koczkodaj: K(A) = 1/(1-MT(A)) è equivalente alla misura MT di questo articolo
2. Altre misure: Esistono molteplici misure di incoerenza, ma MT possiede vantaggi di località e facilità computazionale
3. Ricerca assiomatica: Csató ha condotto un'analisi assiomatica degli indici di incoerenza triadica

Applicazione della Teoria dei Grafi al Completamento di Matrici

1. Teoria dei grafi cordali: Il lavoro classico di Golumbic ha stabilito le basi teoriche dei grafi cordali
2. Completamento di matrici: Grone e altri hanno applicato i grafi cordali al completamento di matrici definite positive
3. Contributo di questo articolo: Prima applicazione sistematica della teoria dei grafi cordali al completamento di matrici reciproche

Conclusioni e Discussione

Conclusioni Principali

1. Framework teorico completo: Stabilisce una teoria completa sull'esistenza di completamenti coerenti di matrici reciproche, da due prospettive: struttura del grafo e dati
2. Algoritmo pratico: Fornisce un algoritmo concreto di completamento nel caso di grafo cordale che mantiene la misura di incoerenza non aumentata
3. Estensione applicativa: Il metodo è applicabile alla riduzione dell'incoerenza di matrici esistenti

Limitazioni

1. Restrizione ai grafi cordali: La garanzia di completamento approssimato vale solo nel caso di grafi cordali; il caso generale rimane da approfondire
2. Scelta della misura: Sebbene la misura MT abbia vantaggi teorici, le applicazioni pratiche potrebbero richiedere considerazione di altre misure
3. Efficienza computazionale: Per problemi su larga scala, l'efficienza pratica dell'algoritmo potrebbe richiedere ulteriore ottimizzazione

Direzioni Future

1. Estensione a grafi generali: Ricerca di metodi di completamento approssimato per il caso di grafi non cordali
2. Altre misure: Estensione del metodo ad altre misure di incoerenza
3. Applicazioni pratiche: Verifica dell'efficacia del metodo in problemi decisionali concreti

Valutazione Approfondita

Punti di Forza

1. Completezza teorica: Fornisce una caratterizzazione teorica completa del problema di completamento coerente, colmando un'importante lacuna teorica
2. Innovazione metodologica: Applica ingegnosamente la teoria dei grafi cordali al completamento di matrici reciproche, con un approccio tecnico innovativo
3. Valore pratico: L'algoritmo ha complessità temporale polinomiale, adatto alle applicazioni pratiche
4. Chiarezza espositiva: L'articolo è ben strutturato, le dimostrazioni sono rigorose e gli esempi sono abbondanti

Insufficienze

1. Ambito di applicazione: I risultati principali sono limitati al caso di grafi cordali; il trattamento del caso generale è insufficiente
2. Verifica sperimentale: Mancano esperimenti numerici su larga scala e verifiche su dati reali
3. Analisi comparativa: Manca un confronto sistematico con altri metodi di completamento
4. Dettagli implementativi: Alcuni passaggi algoritmici mancano di dettagli sufficienti per l'implementazione concreta

Potenziale di Impatto

1. Contributo teorico: Fornisce una base teorica solida per il trattamento di dati incompleti nell'analisi decisionale
2. Valore metodologico: L'idea della decomposizione per ordinamento cordale potrebbe ispirare ricerche su altri problemi di completamento di matrici
3. Potenziale pratico: Il metodo è direttamente applicabile alla preelaborazione dei dati in metodi decisionali come AHP
4. Interdisciplinarità: Rappresenta un'integrazione organica di teoria dei grafi, teoria delle matrici e analisi decisionale

Scenari di Applicazione

1. Analisi decisionale: Metodi di decisione multicriteria come AHP e ANP che richiedono confronti a coppie
2. Data mining: Preelaborazione e completamento di dati di relazioni incomplete
3. Reti sociali: Completamento e analisi di coerenza di matrici di intensità di relazioni
4. Economia: Inferenza di relazioni di preferenza e funzioni di utilità

Bibliografia

L'articolo cita 26 lavori correlati, coprendo molteplici ambiti inclusi matrici di confronto a coppie, misure di incoerenza, teoria dei grafi e completamento di matrici, fornendo una solida base teorica per la ricerca.

Valutazione Complessiva: Questo è un articolo di alta qualità che raggiunge progressi teorici significativi nel problema importante del completamento di matrici reciproche. Sebbene presenti alcune insufficienze nella verifica sperimentale e nell'ambito di applicazione, i suoi contributi teorici e l'innovazione metodologica hanno valore importante e esercitano un'influenza positiva sulla ricerca nell'analisi decisionale e nei campi correlati.