जोड़ीदार तुलना डेटा की पूर्णता जो ट्रायड असंगति के माप को कम करती है

मूल जानकारी

• पेपर ID: 2510.12351
• शीर्षक: Completions of pairwise comparison data that minimize the triad measure of inconsistency
• लेखक: Susana Furtado (CEMS.UL और Faculdade de Economia, Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
• वर्गीकरण: math.CO (संयोजन गणित), math.OC (अनुकूलन और नियंत्रण)
• प्रकाशन समय: 15 अक्टूबर 2025 (arXiv प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2510.12351

सारांश

यह पेपर अधूरे जोड़ीदार तुलना मैट्रिक्स का अध्ययन करता है, सटीक रूप से निर्धारित करता है कि कब संगत पूर्णता मौजूद है, और यदि नहीं तो कब अनुमानित संगत पूर्णता मौजूद है। लेखक अधिकतम 3-चक्र गुणनफल को असंगति के माप के रूप में उपयोग करते हैं, यह साबित करते हैं कि जब निर्दिष्ट प्रविष्टियों का ग्राफ एक कॉर्डल ग्राफ है, तो हमेशा ऐसी पूर्णता खोजी जा सकती है जो इस माप को नहीं बढ़ाती। पेपर ऐसी पूर्णताओं को उत्पन्न करने के लिए पद्धति विकसित करता है, जिसका उपयोग कुछ तुलनाओं में परिवर्तन के माध्यम से असंगति को कम करने के लिए भी किया जा सकता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

1. जोड़ीदार तुलना मैट्रिक्स का महत्व: निर्णय विश्लेषण में, जोड़ीदार तुलना मैट्रिक्स A = aij का उपयोग n विकल्पों के बीच सापेक्ष महत्व को दर्शाने के लिए किया जाता है, जहाँ aij विकल्प i का विकल्प j के सापेक्ष महत्व अनुपात दर्शाता है। ऐसे मैट्रिक्स का व्यापक अनुप्रयोग पदानुक्रमित विश्लेषण विधि (AHP) जैसी निर्णय विधियों में होता है।
2. संगति समस्या: आदर्श रूप से, तुलनाएँ संगत होनी चाहिए, अर्थात् संक्रामकता को संतुष्ट करना चाहिए: aijajk = aik सभी i,j,k के लिए। हालांकि, व्यावहारिक रूप से मानव निर्णय की सीमाओं के कारण, पूरी तरह संगत तुलना मैट्रिक्स दुर्लभ होते हैं।
3. अधूरे डेटा की चुनौती: वास्तविक अनुप्रयोगों में, विभिन्न कारणों से (समय की सीमा, विशेषज्ञ ज्ञान की कमी, तुलना की कठिनाई आदि), कुछ जोड़ीदार तुलनाएँ अनुपलब्ध हो सकती हैं, जिससे आंशिक पारस्परिक मैट्रिक्स (PRM) बनते हैं।

अनुसंधान प्रेरणा

1. पूर्णता की आवश्यकता: निर्णय विधियों को आमतौर पर वजन सदिश की गणना के लिए पूर्ण तुलना मैट्रिक्स की आवश्यकता होती है, इसलिए अधूरे मैट्रिक्स की तर्कसंगत पूर्णता की आवश्यकता होती है।
2. संगति अनुकूलन: जब पूर्ण संगति प्राप्त नहीं की जा सकती, तो "अनुमानित संगत" पूर्णता समाधान खोजने की आवश्यकता होती है, असंगति के माप को कम करते हुए।
3. सैद्धांतिक अंतराल: मौजूदा अनुसंधान में यह स्पष्ट नहीं है कि कब संगत पूर्णता मौजूद है, और कॉर्डल ग्राफ स्थितियों में असंगति के माप को नहीं बढ़ाते हुए पूर्णता के लिए कोई व्यवस्थित विधि नहीं है।

मुख्य योगदान

1. संगत पूर्णता के अस्तित्व की सटीक विशेषता: दो दृष्टिकोणों से पूर्ण सिद्धांत प्रदान करता है:
   • ग्राफ संरचना के आधार पर: यदि और केवल यदि निर्दिष्ट प्रविष्टियों के ग्राफ का प्रत्येक जुड़ा हुआ घटक एक कॉर्डल ग्राफ है, तो संगत पूर्णता मौजूद है
   • डेटा के आधार पर: यदि और केवल यदि प्रत्येक पूरी तरह निर्दिष्ट चक्र गुणनफल 1 के बराबर है, तो संगत पूर्णता मौजूद है
2. कॉर्डल ग्राफ स्थिति में अनुमानित संगत पूर्णता: साबित करता है कि जब निर्दिष्ट प्रविष्टियों का ग्राफ एक कॉर्डल ग्राफ है, तो हमेशा ऐसी पूर्णता खोजी जा सकती है जो ट्रायड असंगति के माप MT को नहीं बढ़ाती।
3. पूर्णता पद्धति: कॉर्डल क्रम का उपयोग करके क्रमिक रूप से मैट्रिक्स को पूर्ण करने के लिए एक ठोस एल्गोरिदमिक ढांचा विकसित करता है, यह सुनिश्चित करते हुए कि असंगति को बदतर न बनाया जाए।
4. असंगति में कमी की तकनीक: कुछ प्रविष्टियों को संशोधित करके मौजूदा पूर्ण मैट्रिक्स की असंगति को कम करने की विधि प्रस्तावित करता है।

विधि विवरण

कार्य परिभाषा

इनपुट: आंशिक पारस्परिक मैट्रिक्स (PRM) A, जहाँ कुछ प्रविष्टियाँ aij निर्दिष्ट हैं और पारस्परिकता गुण aji = 1/aij को संतुष्ट करती हैं आउटपुट: पूर्ण पारस्परिक मैट्रिक्स Ã, जैसे कि:

1. Ã निर्दिष्ट स्थितियों पर A के साथ सहमत है
2. यदि संभव हो, तो Ã संगत है (rank-1)
3. यदि संभव न हो, तो MT(Ã) = MT(A) (असंगति के माप को नहीं बढ़ाता)

मुख्य सैद्धांतिक ढांचा

1. संगति की समतुल्य शर्तें

पूर्ण पारस्परिक मैट्रिक्स A ∈ PCn के लिए, निम्नलिखित शर्तें समतुल्य हैं:

• A संगत है (rank-1)
• A में प्रत्येक चक्र का गुणनफल 1 के बराबर है
• A का प्रत्येक 3×3 मुख्य उप-मैट्रिक्स संगत है

2. ट्रायड असंगति का माप

MT(A) को A में सभी 3-चक्र गुणनफलों के अधिकतम मान के रूप में परिभाषित करता है: $MT(A) = \max_{i<j<k} \{c(i,j,k), c(k,j,i)\}$ जहाँ c(i,j,k) = aijajkaki 3-चक्र गुणनफल है।

3. कॉर्डल ग्राफ का महत्व

प्रमेय 1: यदि G एक कॉर्डल ग्राफ है, तो अनुपलब्ध किनारों का एक क्रम मौजूद है, जैसे कि इन किनारों को क्रमिक रूप से जोड़ते समय हर बार कॉर्डल ग्राफ गुण बना रहता है।

यह गुण बहु-चर पूर्णता समस्या को एक श्रृंखला एकल-चर समस्याओं में विभाजित करता है।

संगत पूर्णता की पर्याप्त शर्तें

प्रमेय 2: प्रत्येक आंशिक संगत मैट्रिक्स (PCM) यदि और केवल यदि इसके ग्राफ G का प्रत्येक जुड़ा हुआ घटक एक कॉर्डल ग्राफ है, तो एक संगत पूर्णता मौजूद है। यदि G जुड़ा हुआ है, तो पूर्णता अद्वितीय है।

प्रमाण की रूपरेखा:

1. एकल-चर स्थिति: A(x) जैसे मैट्रिक्स के लिए, x = (a1,n-1 × a2n)/a2,n-1 चुनें ताकि A(x) rank-1 हो
2. बहु-चर स्थिति: कॉर्डल क्रम का उपयोग करके क्रमिक रूप से अनिर्दिष्ट प्रविष्टियों को निर्धारित करें
3. असंयुक्त स्थिति: प्रत्येक जुड़े हुए घटक को अलग से पूर्ण करें, फिर संगत ब्लॉक मैट्रिक्स से जोड़ें

संगत पूर्णता की आवश्यक और पर्याप्त शर्तें

प्रमेय 6: मान लीजिए A एक n×n का PRM है और PC+ है (प्रत्येक पूरी तरह निर्दिष्ट चक्र गुणनफल 1 के बराबर है), तो A के पास एक संगत पूर्णता है। यदि ग्राफ G(A) जुड़ा हुआ है, तो यह पूर्णता अद्वितीय है।

प्रमाण विधि:

1. G का एक फैलने वाला वृक्ष T चुनें
2. T के अनुरूप आंशिक मैट्रिक्स का एक अद्वितीय संगत पूर्णता Ã है
3. चक्र गुणनफल शर्त के कारण, Ã सभी निर्दिष्ट स्थितियों पर A के साथ सहमत है

अनुमानित संगत पूर्णता विधि

एकल-चर समस्या विश्लेषण

एकल-चर पूर्णता समस्या A(x) के लिए, परिभाषित करें:

• C(A): सभी 3-चक्र गुणनफल जो स्थिति (1,n) को शामिल नहीं करते
• C0(A): सभी 3-चक्र गुणनफल जो स्थिति (1,n) को शामिल करते हैं
• S(A) = {a1jajn : 2 ≤ j ≤ n-1}

प्रमेय 9: एक x0 > 0 मौजूद है जैसे कि MT(A(x0)) = MT(A) यदि और केवल यदि: $\frac{1}{MT(A)} \cdot MS(A) \leq x_0 \leq MT(A) \cdot mS(A)$

जहाँ MS(A) = max S(A), mS(A) = min S(A)।

कॉर्डल ग्राफ स्थिति में पूर्णता एल्गोरिदम

प्रमेय 11: मान लीजिए B एक PRM है जिसके निर्दिष्ट प्रविष्टियों का ग्राफ कॉर्डल है, तो B के पास एक पारस्परिक पूर्णता B̃ है जैसे कि MT(B̃) = MT(B)।

एल्गोरिदम चरण:

1. यदि ग्राफ केवल एक वृक्ष है, तो सीधे संगत पूर्णता करें
2. यदि ग्राफ जुड़ा हुआ है और 3-चक्र है, तो कॉर्डल क्रम के अनुसार प्रमेय 9 को क्रमिक रूप से लागू करें
3. यदि ग्राफ असंयुक्त है, तो पहले प्रत्येक जुड़े हुए घटक को पूर्ण करें, फिर लेम्मा 12 का उपयोग करके जोड़ें

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन उदाहरण

उदाहरण 1: कोई संगत पूर्णता नहीं होने की स्थिति

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

ग्राफ 4-चक्र 12341 है, चूंकि 4 = a14 ≠ a12a23a34 = 10/3, कोई संगत पूर्णता नहीं है।

उदाहरण 2: कॉर्डल ग्राफ पूर्णता प्रक्रिया

5×5 मैट्रिक्स N(x,y) पर विचार करें, जिसके निर्दिष्ट प्रविष्टियों का ग्राफ कॉर्डल है। दो चरणों में पूर्णता के माध्यम से:

1. पहले y को निर्धारित करें ताकि MT न बढ़े: y ∈ 1/3, 1/2
2. फिर x को निर्धारित करें ताकि MT न बढ़े: x ∈ √6/4, 2

कम्प्यूटेशनल जटिलता विश्लेषण

• एकल-चर पूर्णता: संभव्य क्षेत्र निर्धारित करने के लिए O(n²) समय
• कॉर्डल ग्राफ पूर्णता: O(m) एकल-चर समस्याएँ, जहाँ m अनुपलब्ध किनारों की संख्या है
• कुल जटिलता: O(mn²)

प्रायोगिक परिणाम

सैद्धांतिक परिणामों का सत्यापन

संगत पूर्णता का अस्तित्व

1. कॉर्डल ग्राफ शर्त: सभी परीक्षित कॉर्डल ग्राफ PCM ने सफलतापूर्वक एक संगत पूर्णता खोजी
2. गैर-कॉर्डल ग्राफ प्रतिउदाहरण: निर्मित 4-चक्र आदि गैर-कॉर्डल ग्राफ PCM में वास्तव में कोई संगत पूर्णता नहीं है
3. डेटा शर्त: PC+ शर्त का सत्यापन दर्शाता है कि यह संगत पूर्णता के लिए आवश्यक और पर्याप्त है

अनुमानित पूर्णता प्रभाव

1. MT माप संरक्षण: सभी कॉर्डल ग्राफ परीक्षण मामलों में, MT(Ã) = MT(A) की पूर्णता सफलतापूर्वक खोजी गई
2. संभव्य क्षेत्र: एकल-चर समस्या का संभव्य क्षेत्र हमेशा गैर-रिक्त होता है (लेम्मा 8 द्वारा गारंटीकृत)
3. इष्टतम चयन: संभव्य क्षेत्र के भीतर आगे अनुकूलन नई शुरू की गई 3-चक्र गुणनफलों को कम कर सकता है

असंगति में कमी का अनुप्रयोग

एकल प्रविष्टि को संशोधित करके, परीक्षण मैट्रिक्स के MT मान को मूल अधिकतम मान से छोटे मान तक कम करने में सफलतापूर्वक, विधि की व्यावहारिकता को सत्यापित करता है।

संबंधित कार्य

जोड़ीदार तुलना मैट्रिक्स की पूर्णता

1. प्रारंभिक कार्य: Saaty के पदानुक्रमित विश्लेषण विधि ने जोड़ीदार तुलना की नींव रखी
2. पूर्णता विधियाँ: Benítez आदि ने संगत पूर्णता की विशेषता का अध्ययन किया
3. अधूरे मैट्रिक्स: Bozóki आदि ने इष्टतम पूर्णता समस्या का अध्ययन किया

असंगति के माप

1. Koczkodaj सूचकांक: K(A) = 1/(1-MT(A)) इस पेपर के MT माप के समतुल्य है
2. अन्य माप: कई असंगति माप मौजूद हैं, लेकिन MT में स्थानीयता और आसान गणना के लाभ हैं
3. अक्षीय अनुसंधान: Csató ने ट्रायड असंगति सूचकांक का अक्षीय विश्लेषण किया

ग्राफ सिद्धांत का मैट्रिक्स पूर्णता में अनुप्रयोग

1. कॉर्डल ग्राफ सिद्धांत: Golumbic के शास्त्रीय कार्य ने कॉर्डल ग्राफ की नींव स्थापित की
2. मैट्रिक्स पूर्णता: Grone आदि ने सकारात्मक निश्चित मैट्रिक्स पूर्णता में कॉर्डल ग्राफ लागू किए
3. इस पेपर का योगदान: पारस्परिक मैट्रिक्स पूर्णता में कॉर्डल ग्राफ सिद्धांत का पहली बार व्यवस्थित अनुप्रयोग

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

1. पूर्ण सैद्धांतिक ढांचा: पारस्परिक मैट्रिक्स संगत पूर्णता के अस्तित्व के लिए एक पूर्ण सिद्धांत स्थापित करता है, जिसमें ग्राफ संरचना और डेटा-आधारित दोनों दृष्टिकोण शामिल हैं
2. व्यावहारिक एल्गोरिदम: कॉर्डल ग्राफ स्थिति में असंगति के माप को नहीं बढ़ाते हुए पूर्णता के लिए ठोस एल्गोरिदम प्रदान करता है
3. अनुप्रयोग विस्तार: विधि मौजूदा मैट्रिक्स की असंगति को कम करने के लिए उपयोगी है

सीमाएँ

1. कॉर्डल ग्राफ प्रतिबंध: अनुमानित पूर्णता की गारंटी केवल कॉर्डल ग्राफ स्थिति में है, सामान्य ग्राफ स्थिति को अभी और अनुसंधान की आवश्यकता है
2. माप चयन: हालांकि MT माप में सैद्धांतिक लाभ हैं, व्यावहारिक अनुप्रयोगों में अन्य मापों पर विचार करने की आवश्यकता हो सकती है
3. कम्प्यूटेशनल दक्षता: बड़े पैमाने की समस्याओं के लिए, एल्गोरिदम की व्यावहारिक दक्षता को आगे अनुकूलित करने की आवश्यकता हो सकती है

भविष्य की दिशाएँ

1. सामान्य ग्राफ विस्तार: गैर-कॉर्डल ग्राफ स्थितियों में अनुमानित पूर्णता विधि का अनुसंधान
2. अन्य माप: विधि को अन्य असंगति मापों तक विस्तारित करना
3. व्यावहारिक अनुप्रयोग: विशिष्ट निर्णय समस्याओं में विधि की प्रभावशीलता का सत्यापन

गहन मूल्यांकन

शक्तियाँ

1. सैद्धांतिक पूर्णता: संगत पूर्णता समस्या के लिए एक पूर्ण सैद्धांतिक विशेषता प्रदान करता है, एक महत्वपूर्ण सैद्धांतिक अंतराल को भरता है
2. विधि नवाचार: कॉर्डल ग्राफ सिद्धांत को पारस्परिक मैट्रिक्स पूर्णता में कुशलतापूर्वक लागू करता है, तकनीकी मार्ग नया है
3. व्यावहारिक मूल्य: एल्गोरिदम में बहुपद समय जटिलता है, व्यावहारिक अनुप्रयोगों के लिए उपयुक्त है
4. स्पष्ट लेखन: पेपर संरचना स्पष्ट है, प्रमेय प्रमाण कठोर हैं, उदाहरण समृद्ध हैं

कमियाँ

1. अनुप्रयोग सीमा: मुख्य परिणाम कॉर्डल ग्राफ स्थिति तक सीमित हैं, सामान्य ग्राफ के लिए उपचार अपर्याप्त है
2. प्रायोगिक सत्यापन: बड़े पैमाने पर संख्यात्मक प्रयोग और वास्तविक डेटा सत्यापन की कमी है
3. तुलनात्मक विश्लेषण: अन्य पूर्णता विधियों के साथ व्यवस्थित तुलना अपर्याप्त है
4. कम्प्यूटेशनल विवरण: कुछ एल्गोरिदम चरणों के विशिष्ट कार्यान्वयन विवरण पर्याप्त नहीं हैं

प्रभाव

1. सैद्धांतिक योगदान: निर्णय विश्लेषण में अधूरे डेटा प्रसंस्करण के लिए एक ठोस सैद्धांतिक आधार प्रदान करता है
2. पद्धति मूल्य: कॉर्डल क्रम विघटन का विचार अन्य मैट्रिक्स पूर्णता समस्याओं के अनुसंधान को प्रेरित कर सकता है
3. व्यावहारिक संभावना: विधि AHP जैसी निर्णय विधियों में डेटा पूर्व-प्रसंस्करण में सीधे लागू की जा सकती है
4. विषय अंतर-अनुशासन: ग्राफ सिद्धांत, मैट्रिक्स सिद्धांत और निर्णय विश्लेषण का जैविक संयोजन दर्शाता है

लागू परिदृश्य

1. निर्णय विश्लेषण: AHP, ANP आदि जो जोड़ीदार तुलना की आवश्यकता वाली बहु-मानदंड निर्णय विधियाँ
2. डेटा खनन: अधूरे संबंध डेटा का पूर्व-प्रसंस्करण और पूर्णता
3. सामाजिक नेटवर्क: संबंध शक्ति मैट्रिक्स की पूर्णता और संगति विश्लेषण
4. अर्थशास्त्र: वरीयता संबंध और उपयोगिता कार्य का अनुमान

संदर्भ

पेपर 26 संबंधित संदर्भों का हवाला देता है, जिसमें जोड़ीदार तुलना मैट्रिक्स, असंगति माप, ग्राफ सिद्धांत और मैट्रिक्स पूर्णता आदि कई क्षेत्रों के महत्वपूर्ण कार्य शामिल हैं, जो अनुसंधान के लिए एक ठोस सैद्धांतिक आधार प्रदान करते हैं।

समग्र मूल्यांकन: यह पारस्परिक मैट्रिक्स पूर्णता की इस महत्वपूर्ण समस्या पर एक उच्च-गुणवत्ता वाला सैद्धांतिक पेपर है जो महत्वपूर्ण सैद्धांतिक प्रगति प्राप्त करता है। हालांकि प्रायोगिक सत्यापन और अनुप्रयोग सीमा के संदर्भ में कुछ कमियाँ हैं, लेकिन इसके सैद्धांतिक योगदान और विधि नवाचार का महत्वपूर्ण मूल्य है, और निर्णय विश्लेषण और संबंधित क्षेत्रों के अनुसंधान में सकारात्मक प्रेरणा प्रदान करता है।