तकनीकी सारांश: रैंक एकत्रीकरण में आनुपातिक प्रतिनिधित्व

समस्या की परिभाषा

यह शोध पत्र रैंक एकत्रीकरण (rank aggregation) की समस्या को संबोधित करता है, जहाँ लक्ष्य एक प्रोफ़ाइल $R$ के भारित इनपुट रैंकिंग को एक एकल आउटपुट रैंकिंग में संयोजित करना है। इस सेटिंग में, एक प्रोफ़ाइल $R$ में उम्मीदवारों का एक सेट $C$ और प्रत्येक संभावित रैंकिंग $\succ$ को एक भार $R(\succ) \in [0, 1]$ प्रदान करने वाला एक फलन शामिल है, ताकि सभी भारों का योग 1 हो। ये भार विभिन्न मानदंडों (जैसे होटल बुकिंग में मूल्य बनाम रेटिंग) के महत्व या एक विशिष्ट रैंकिंग का समर्थन करने वाले मतदाताओं के हिस्से का प्रतिनिधित्व करते हैं।

पहचानी गई केंद्रीय चुनौती यह है कि शास्त्रीय सामाजिक कल्याण कार्य (Social Welfare Functions - SWFs), जैसे कि केमेनी नियम (Kemeny rule), बोर्डा काउंट (Borda count) और कोंडोरसेट-प्रकार के नियम (Condorcet-type rules), स्वाभाविक रूप से बहुसंख्यकवादी (majoritarian) होते हैं। वे आउटपुट रैंकिंग को उच्चतम-भारित इनपुट के निकटतम बनाने का प्रयास करते हैं, जिससे अल्पसंख्यक प्राथमिकताओं की अनदेखी होती है। उदाहरण के लिए, यदि दो विपरीत रैंकिंग्स के भार 51% और 49% हैं, तो मानक SWFs अक्सर केवल 51% वाली रैंकिंग को ही चुनते हैं, जिससे 49% समूह का प्रतिनिधित्व नहीं हो पाता। यह शोध पत्र ऐसे SWFs डिजाइन करने का प्रयास करता है जो आनुपातिक प्रतिनिधित्व (proportional representation) की गारंटी देते हैं, यह सुनिश्चित करते हुए कि प्रत्येक इनपुट रैंकिंग का आउटपुट पर उसके भार के अनुपात में प्रभाव पड़े।

कार्यप्रणाली और ढांचा

लेखक आनुपातिकता को औपचारिक रूप बनाने के लिए एक इनपुट रैंकिंग $\succ$ की एक आउटपुट रैंकिंग $\triangleright$ के लिए उपयोगिता (utility) को उनके बीच जोड़ी-वार समझौतों (pairwise agreements) की संख्या के रूप में परिभाषित करते हैं:
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ and } x \triangleright y\}|$$
चूंकि $m$ उम्मीदवारों के लिए कुल $\binom{m}{2}$ तुलनाएँ होती हैं, इसलिए एक इनपुट रैंकिंग जिसका भार $\alpha$ है, उसे आदर्श रूप से कम से कम $\lfloor \alpha \binom{m}{2} \rfloor$ उपयोगिता प्राप्त होनी चाहिए।

यह शोध पत्र अनुमोदन-आधारित समिति मतदान (approval-based committee voting) और सहभागी बजटिंग (participatory budgeting) से प्रेरित आनुपातिकता के अभिसाखियों (axioms) का एक पदानुक्रम प्रस्तुत करता है:

1. सर्वसम्मत न्यायसंगत प्रतिनिधित्व (Unanimous Justified Representation - uJR): एक कमजोर आवश्यकता जिसमें यह अनिवार्य है कि $1/\binom{m}{2}$ से अधिक भार वाली किसी भी इनपुट रैंकिंग को कम से कम एक जोड़ी-वार समझौता प्राप्त हो।
2. सर्वसम्मत आनुपातिक न्यायसंगत प्रतिनिधित्व (Unanimous Proportional Justified Representation - uPJR): मुख्य अभिसाखी जो यह आवश्यक करती है कि $\alpha$ भार वाली किसी भी इनपुट रैंकिंग को कम से कम $\lfloor \alpha \binom{m}{2} \rfloor$ उपयोगिता प्राप्त हो।
3. सुदृढ़ आनुपातिक न्यायसंगत प्रतिनिधित्व (Strong Proportional Justified Representation - sPJR): एक सुदृढ़ विस्तार जो रैंकिंग के समूहों तक गारंटी का विस्तार करता है। यदि एक उप-प्रोफ़ाइल $S$ का कुल भार $\alpha$ है, तो आउटपुट को $S$ की रैंकिंग के संघ (union) से कम से कम $\lfloor \alpha \binom{m}{2} \rfloor$ जोड़ी-वार समझौतों के साथ सहमत होना चाहिए।

इन अभिसाखियों को प्राप्त करने के लिए, लेखक सहभागी बजटिंग से मूल्य निर्धारण क्षमता (priceability) की अवधारणा को अनुकूलित करते हैं। वे आउटपुट रैंकिंग के निर्माण को एक क्रमिक खरीद प्रक्रिया के रूप में मॉडल करते हैं जहाँ उम्मीदवारों (या जोड़ियों) को इनपुट रैंकिंग के बजटों का उपयोग करके "खरीदा" जाता है।

मुख्य योगदान और परिणाम

1. मौजूदा विधियों की सीमाएं

शोध पत्र पहले स्क्वेर्ड केमेनी नियम (Squared Kemeny rule) (जिसे लेडरर एट अल. [2024] द्वारा आनुपातिक रैंकिंग के लिए प्रस्तावित किया गया था) का विश्लेषण करता है। लेखक सिद्ध करते हैं कि $m \ge 5$ के लिए, स्क्वेर्ड केमेनी नियम सबसे कमजोर अभिसाखी, uJR को भी विफल कर देता है। विशेष रूप से, वे ऐसी प्रोफ़ाइल का निर्माण करते हैं जहाँ महत्वपूर्ण भार वाली एक इनपुट रैंकिंग को स्क्वेर्ड केमेनी आउटपुट से शून्य उपयोगिता प्राप्त होती है, जो नई प्रणालियों की आवश्यकता को प्रदर्शित करती है।

2. आनुपातिक क्रमिक बोर्डा नियम (Proportional Sequential Borda Rule - PSB)

uPJR को संतुष्ट करने के लिए, लेखक आनुपातिक क्रमिक बोर्डा नियम (PSB) का प्रस्ताव करते हैं।

• तंत्र: PSB क्रमिक रूप से कार्य करता है। प्रत्येक दौर में, यह वर्तमान बजटों के आधार पर भारित बोर्डा स्कोर को अधिकतम करने वाले उम्मीदवार का चयन करता है। इसके बाद, यह इनपुट रैंकिंग के बजटों को उनके द्वारा चयनित उम्मीदवार के स्कोर में योगदान के अनुपात में अपडेट करता है, प्रभावी रूप से चयनित उम्मीदवार के स्थान के लिए "भुगतान" करता है।
• सैद्धांतिक गारंटी: लेखक एक संरचित अभिसाखी रैंक-प्राइसएबिलिटी (rank-priceability) पेश करते हैं, जो सहभागी बजटिंग में प्राइसएबिलिटी को दर्शाती है। वे सिद्ध करते हैं कि रैंक-प्राइसएबिलिटी uPJR को निहित करती है।
• परिणाम: प्रमेय 4.5 स्थापित करता है कि PSB रैंक-प्राइसएबिलिटी को संतुष्ट करता है और फलस्वरूप uPJR को भी।
• मात्रात्मक गारंटी: अभिसाखी संतुष्टि के अलावा, प्रमेय 4.6 सिद्ध करता है कि PSB प्रत्येक उप-प्रोफ़ाइल $S$ को कम से कम $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$ की औसत उपयोगिता की गारंटी देता है। यह समूह के भार के सापेक्ष उपयोगिता पर एक रैखिक निचली सीमा प्रदान करता है।

3. फ्लो-एडजस्टिंग बोर्डा नियम (Flow-adjusting Borda Rule - FB)

लेखक दिखाते हैं कि PSB sPJR को विफल कर देता है क्योंकि इसकी भुगतान योजना उन रैंकिंग समूहों की पर्याप्त सुरक्षा नहीं करती है जो मिलकर कार्य करते हैं। इसे संबोधित करने के लिए, वे पेयर-प्राइसएबिलिटी (pair-priceability) नामक एक परिष्कृत अभिसाखी पेश करते हैं, जहाँ भुगतान केवल रैंकों के बजाय विशिष्ट उम्मीदवार जोड़ियों के लिए किया जाता है।

• तंत्र: फ्लो-एडजस्टिंग बोर्डा नियम (FB), PSB का एक परिष्कृत रूप है। PSB की तरह, FB भी क्रमिक रूप से बोर्डा विजेता का चयन करता है। हालाँकि, एक साधारण आनुपातिक भुगतान के बजाय, FB एक निर्मित नेटवर्क में अधिकतम प्रवाह समस्या (maximum flow problem) को हल करके भुगतान निर्धारित करता है। यह नेटवर्क यह सुनिश्चित करता है कि लागत प्रति उपयोगिता अनुपात न्यूनतम हो, जबकि बजट बाधाओं और जोड़ी-वार बाधाओं का सम्मान किया जाए।
• परिणाम: प्रमेय 5.5 सिद्ध करता है कि FB पेयर-प्राइसएबिलिटी को संतुष्ट करता है, जो बदले में sPJR (प्रमेय 5.3) को निहित करता है।
• मात्रात्मक गारंटी: प्रमेय 5.6 दिखाता है कि FB, PSB के समान ही $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$ की रैखिक औसत उपयोगिता गारंटी प्रदान करता है, जो व्यक्तियों और समूहों दोनों के लिए मजबूत निष्पक्षता सुनिश्चित करता है।

4. अतिरिक्त संस्करण

परिशिष्ट में, लेखक रैंक्ड मेथड ऑफ इक्वल शेयर्स (Ranked Method of Equal Shares - RMES) पर चर्चा करते हैं, जो सहभागी बजटिंग से 'मेथड ऑफ इक्वल शेयर्स' (MES) से प्रेरित एक संस्करण है। वे दिखाते हैं कि RMES रैंक-प्राइसएबिलिटी (और इस प्रकार uPJR) को संतुष्ट करता है और एक थोड़ा अलग उपयोगिता प्रोफ़ाइल प्रदान करता है, जो प्रारंभिक बोर्डा स्कोर के आधार पर पहले $\lfloor m/4 \rfloor$ उम्मीदवारों का चयन करता है।

महत्व और दावे

शोध पत्र का दावा है कि यह रैंक एकत्रीकरण के लिए पहले वास्तव में आनुपातिक सामाजिक कल्याण कार्यों को प्रस्तुत करता है। इसका प्राथमिक महत्व निम्नलिखित है:

• क्षेत्रों को जोड़ना: यह सफलतापूर्वक अनुमोदन-आधारित समिति मतदान और सहभागी बजटिंग (विशेष रूप से PJR और प्राइसएबिलिटी) के गहरे परिणामों को रैंक एकत्रीकरण के क्षेत्र में स्थानांतरित करता है।
• एक खुली समस्या का समाधान: यह उन SWFs को डिजाइन करने की खुली समस्या को हल करता है जो uPJR और sPJR को संतुष्ट करते हैं, जिसे पिछले प्रयास (जैसे स्क्वेर्ड केमेनी) करने में विफल रहे थे।
• अभिसाखी और मात्रात्मक शक्ति: प्रस्तावित नियम (PSB और FB) न केवल मजबूत अभिसाखी निष्पक्षता शर्तों को संतुष्ट करने के लिए सिद्ध किए गए हैं, बल्कि वे किसी भी मतदाता के समूह के लिए औसत उपयोगिता पर मजबूत मात्रात्मक गारंटी भी प्रदान करते हैं, जिससे यह सुनिश्चित होता है कि अल्पसंख्यक प्राथमिकताओं की व्यवस्थित रूप से अनदेखी नहीं की जाती है।

लेखक उल्लेख करते हैं कि जबकि उनका कार्य उपयोगिता मीट्रिक के रूप में जोड़ी-वार समझौते पर ध्यान केंद्रित करता है, यह साहित्य में एक मानक दृष्टिकोण है। वे सुझाव देते हैं कि भविष्य के कार्य अधिक मजबूत निष्पक्षता अवधारणाओं (जैसे EJR या कोर-स्थिरता) और अधिक सामान्य उपयोगिता कार्यों की खोज कर सकते हैं जो विभिन्न रैंकिंग स्थितियों के बदलते मूल्य को ध्यान में रखते हैं।