💻 computer science

The Condorcet Dimension of Metric Spaces

यह शोध पत्र स्थापित करता है कि मैनहट्टन या इन्फिनिटी नॉर्म्स वाले द्वि-आयामी मीट्रिक स्पेस में, निकटता-आधारित चुनावों का कोंडोर्सेट आयाम 4 द्वारा सीमित है, और साथ ही यह भी प्रदर्शित करता है कि मतदाताओं की किसी भी वरीयता सेट को किसी भी $p$ -नॉर्म के लिए पर्याप्त उच्च-आयामी मीट्रिक स्पेस में एम्बेड किया जा सकता है।

मूल लेखक: Alexandra Lassota, Adrian Vetta, Bernhard von Stengel

प्रकाशित 2026-08-07

📖 4 मिनट में पढ़ें☕ कॉफ़ी ब्रेक में पढ़ें

CC BY 4.0

मूल लेखक: Alexandra Lassota, Adrian Vetta, Bernhard von Stengel

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल पार्टी में हैं जहाँ हर किसी को एक प्लेलिस्ट में से अपना पसंदीदा गाना चुनना है। यदि एक ऐसा गाना है जो आमने-सामने के वोट में अन्य सभी गानों को हरा देता है, तो वह स्पष्ट विजेता है। लेकिन क्या होगा यदि संगीत की पसंद इतनी मिली-जुली हो कि कोई भी एक गाना अन्य सभी के विरुद्ध नहीं जीत पाता? शायद गाना A, गाना B को हरा दे, गाना B, गाना C को हरा दे, लेकिन गाना C, गाना A को हरा दे। यह असहमति का एक पूर्ण चक्र है, और पार्टी रुक जाती है। यह सामाजिक विज्ञान की एक प्रसिद्ध पहेली है जिसे "कंडोर्सेट विरोधाभास" (Condorcet paradox) कहा जाता है।

इसे ठीक करने के लिए, वैज्ञानिक एक अलग प्रश्न पूछते हैं: एक आदर्श विजेता खोजने के बजाय, क्या हम गानों की एक छोटी "ड्रीम टीम" बना सकते हैं? यदि इस टीम को चुना जाता है, तो टीम के बाहर का कोई भी एकल गाना पूरे समूह को नहीं हरा सकता। इसे "कंडोर्सेट विनिंग सेट" कहा जाता है। बड़ा रहस्य यह है कि यह टीम कितनी बड़ी होनी चाहिए? सबसे खराब स्थिति में, क्या टीम को प्लेलिस्ट के आधे आकार की आवश्यकता होगी? या क्या कोई जादुई सीमा है जहाँ भीड़ को संतुष्ट करने के लिए एक छोटा सा समूह हमेशा पर्याप्त होगा? यह प्रश्न हमें यह समझने में मदद करता है कि क्या लोकतंत्र कभी एक स्थिर, निष्पक्ष समाधान खोज सकता है, या क्या हम अंतहीन असहमति के चक्रों के लिए अभिशप्त हैं।

अब, आइए एक विशिष्ट प्रकार की पार्टी पर ध्यान केंद्रित करें: एक ऐसी पार्टी जहाँ सभी की प्राथमिकताएं इस बात पर आधारित हैं कि कोई उम्मीदवार उन्हें कितना "करीब" महसूस होता है। कल्पना कीजिए कि एक मानचित्र है जहाँ मतदाता और उम्मीदवार बिंदु (dots) हैं। एक मतदाता से एक उम्मीदवार जितना करीब होगा, वह उसे उतना ही पसंद करेगा। यह "स्थानिक मॉडल" (spatial model) है। इस शोध पत्र के शोधकर्ता, एलेक्जेंड्रा लासोटा, एड्रियन वेट्टा और बर्नहार्ड वॉन स्टेंगेल जानना चाहते थे कि, यदि सभी लोग एक दो-आयामी मानचित्र (जैसे कागज का एक टुकड़ा) पर रहते हैं, तो हमारे "ड्रीम टीम" के कितने उम्मीदवारों की आवश्यकता होगी ताकि वे बाकी सभी को हरा सकें?

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

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

शोधकर्ताओं ने एक अलग समस्या का भी समाधान किया: यदि आपके पास प्राथमिकताओं की एक अव्यवस्थित सूची है जो मानचित्र पर फिट बैठती हुई नहीं दिखती है, तो क्या आप उसे जबरदस्ती एक पर फिट कर सकते हैं? उन्होंने दिखाया कि आप किसी भी मतदाता की प्राथमिकताओं को एक उच्च-आयामी स्थान (एक ऐसा मानचित्र जिसमें कई अक्ष/axes हैं) में हमेशा सिकोड़ सकते हैं ताकि यह काम कर सके, और उन्होंने कंप्यूटर पर इसे तेज़ी से करने का एक नुस्खा भी दिया। लेकिन हमारे दो-आयामी दुनिया के लिए मुख्य निष्कर्ष "चार का नियम" (Rule of Four) है: एक सपाट दुनिया में जहाँ लोग निकटता के आधार पर वोट करते हैं, चार का एक छोटा दस्ता अराजकता के खिलाफ अंतिम सुरक्षा कवच है।

तकनीकी सारांश: मीट्रिक स्पेस का कोंडोर्सेट आयाम (The Condorcet Dimension of Metric Spaces)

समस्या की परिभाषा
यह शोध पत्र एक चुनाव के कोंडोर्सेट आयाम (Condorcet dimension) की जांच करता है, जिसे एक कोंडोर्सेट विजेता सेट (Condorcet winning set) की न्यूनतम कार्डिनैलिटी (cardinality) के रूप में परिभाषित किया गया है। एक कोंडोर्सेट विजेता सेट $S \subseteq C$ (जहाँ $C$ उम्मीदवारों का सेट है) एक ऐसा उपसमुच्चय है कि प्रत्येक उम्मीदवार $j \notin S$ के लिए, आधे से अधिक मतदाता कम से कम एक ऐसे उम्मीदवार को पसंद करते हैं जो $S$ में है। जबकि एल्कइंड, लैंग और सफिडाइन [16] ने स्थापित किया था कि $m$ उम्मीदवारों के मामले में $\lceil \log m \rceil$ आकार का एक कोंडोर्सेट विजेता सेट हमेशा मौजूद होता है, सामान्य चुनावों में कोंडोर्सेट आयाम के सटीक ऊपरी स्तर (upper bound) का प्रश्न अभी भी खुला है। लेखक नोट करते हैं कि हालांकि आयाम 3 वाले उदाहरण ज्ञात हैं, लेकिन आयाम 3 से अधिक वाले कोई उदाहरण नहीं मिले हैं, जिससे यह अनुमान लगाया गया है कि सामान्यतः आयाम 3 से अधिक नहीं है।

यह शोध पत्र विशेष रूप से मतदान के स्थानिक मॉडल (spatial model of voting) पर केंद्रित है, जहाँ मतदाता और उम्मीदवार एक मीट्रिक स्पेस में स्थित होते हैं, और प्राथमिकताएं निकटता (पास के उम्मीदवारों को प्राथमिकता) द्वारा निर्धारित होती हैं। यह अध्ययन विशिष्ट नॉर्म्स (norms) के तहत 2-आयामी मीट्रिक स्पेस ( $D=2$ ) पर ध्यान केंद्रित करता है, जो सामान्य मामले के विपरीत है जहाँ एम्बेडिंग आयामों को उच्च ( $D = \min[m-1, n]$ ) होने की आवश्यकता हो सकती है।

कार्यप्रणाली (Methodology)
लेखक विशिष्ट मीट्रिक स्पेस के भीतर ग्राफ-थ्योरेटिक तर्कों और ज्यामितीय विश्लेषण के संयोजन का उपयोग करते हैं:

ग्राफ-थ्योरेटिक ढांचा: इस समस्या को एक मेजोरिटी डाइग्राफ (majority digraph) (एक टूर्नामेंट जहाँ एक आर्क $(j, i)$ तब मौजूद होता है जब बहुमत मतदाता $i$ को $j$ से ऊपर पसंद करते हैं) का उपयोग करके मॉडल किया गया है। एक कोंडोर्सेट विजेता सेट इस डाइग्राफ में एक डोमिनेटिंग सेट (dominating set) के अनुरूप होता है। लेखक इस गुण का लाभ उठाते हैं कि $m$ आकार के टूर्नामेंट में एक डोमिनेटिंग सेट का आकार $\lceil \log m \rceil$ से कम होता है।
ज्यामितीय निर्माण (मैनहट्टन नॉर्म): 2-आयामी मैनहट्टन नॉर्म ( $L_1$ $L_{1}$ ) के लिए, लेखक मतदाताओं के माध्य निर्देशांकों (median coordinates) के आधार पर तल (plane) को चार चतुर्थांशों (quadrants) में विभाजित करते हैं (जिन्हें मूल बिंदु/origin पर स्थानांतरित किया गया है)। वे एक उम्मीदवार सेट $S = \{c_1, c_2, c_3, c_4\}$ $S = {c_{1}, c_{2}, c_{3}, c_{4}}$ को परिभाषित करते हैं, जहाँ प्रत्येक $c_i$ $c_{i}$ चतुर्थांश $Q_i$ $Q_{i}$ में मूल बिंदु के सबसे निकट का उम्मीदवार है।
- वे केस एनालिसिस के माध्यम से सिद्ध करते हैं कि किसी भी चतुर्थांश में स्थित उम्मीदवार $c$ के लिए, उसी चतुर्थांश में मूल बिंदु के सबसे निकट वाला उम्मीदवार $c_i$ , कम से कम आधे मतदाताओं (विशेष रूप से आसन्न या विपरीत चतुर्थांशों में रहने वाले लोगों) द्वारा पसंद किया जाता है।
- यह स्थापित करता है कि $S$ , मेजोरिटी डाइग्राफ में एक डोमिनेटिंग सेट है।
ज्यामितीय रूपांतरण (इन्फिनिटी नॉर्म): 2-आयामी इन्फिनिटी नॉर्म ( $L_\infty$ ) के लिए, लेखक एक ज्यामितीय रोटेशन तर्क का उपयोग करते हैं। वे प्रदर्शित करते हैं कि समन्वय अक्षों (coordinate axes) को 45 डिग्री घुमाने से $L_\infty$ दूरी मीट्रिक एक स्केल्ड $L_1$ (मैनहट्टन) दूरी मीट्रिक में बदल जाता है। फलस्वरूप, प्राथमिकता संरचनाएं संरक्षित रहती हैं, जिससे $L_1$ परिणाम को सीधे $L_\infty$ मामले पर लागू किया जा सकता है।
लोअर बाउंड निर्माण: यह स्थापित करने के लिए कि आयाम हमेशा 1 नहीं होता है, लेखक किसी भी $p$ -norm ( $p \ge 1$ ) के तहत 3 मतदाताओं और 3 उम्मीदवारों के साथ एक विशिष्ट 2-आयामी उदाहरण का निर्माण करते हैं जो कोंडोर्सेट चक्र (Condorcet cycle) की ओर ले जाता है, जिससे सिद्ध होता है कि आयाम कम से कम 2 है।
एम्बेडिंग निर्माण: शोध पत्र समस्या के विपरीत पक्ष को संबोधित करता है: मतदाता प्राथमिकताओं को मीट्रिक स्पेस में एम्बेड करना। यह किसी भी सख्त प्राथमिकताओं के सेट को $D = \min[m, n]$ आयाम वाले $p$ -norm मीट्रिक स्पेस में एम्बेड करने के लिए बहुपद समय (polynomial-time) निर्माण प्रदान करता है। यह यूक्लिडियन ( $L_2$ ) और मैनहट्टन ( $L_1$ ) नॉर्म्स के लिए ज्ञात पिछले परिणामों को सामान्य $p$ -norms तक विस्तारित करता है।

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

$D=2$ के लिए ऊपरी सीमा (Upper Bound): मुख्य परिणाम यह है कि मैनहट्टन नॉर्म या इन्फिनिटी नॉर्म के तहत 2-आयामी मीट्रिक स्पेस में, कोंडोर्सेट आयाम अधिकतम 4 है। यह इन विशिष्ट स्थानिक सेटिंग्स के लिए सामान्य लॉगरिदमिक सीमा की तुलना में एक महत्वपूर्ण सुधार है।
$D=2$ के लिए निचली सीमा (Lower Bound): लेखक सिद्ध करते हैं कि किसी भी $p$ -norm के लिए 2 आयामों में, ऐसे चुनावी उदाहरण मौजूद हैं जहाँ कोंडोर्सेट आयाम कम से कम 2 है (अर्थात, एक कोंडोर्सेट विजेता आवश्यक रूप से मौजूद नहीं होता है)।
सामान्य एम्बेडिंग प्रमेय:
- प्रमेय 7: $m$ उम्मीदवारों और $n$ मतदाताओं वाला कोई भी चुनाव किसी भी $p$ -norm ( $p \ge 0$ ) के लिए $D=m$ आयाम वाले मीट्रिक स्पेस में बहुपद समय में एम्बेड किया जा सकता है।
- प्रमेय 8: ऐसा कोई भी चुनाव किसी भी $p$ -norm ( $p > 1$ ) के लिए $D=n$ आयाम वाले मीट्रिक स्पेस में बहुपद समय में एम्बेड किया जा सकता है।
- ये निर्माण बोगोमोलनाया और लासियर [7] तथा चेन एट अल. [11] के निष्कर्षों को किसी भी $p$ -norm के लिए सामान्यीकृत करते हैं।

महत्व और दावे
शोध पत्र का दावा है कि यह मतदान के विशिष्ट, कम-आयामी स्थानिक मॉडलों के लिए कोंडोर्सेट आयाम पर पहला स्थिर ऊपरी स्तर (constant upper bound) प्रदान करता है। $D=2$ और प्राकृतिक नॉर्म्स (मैनहटन और इन्फिनिटी) का उपयोग करके एम्बेडिंग आयाम को सीमित करके, लेखक यह प्रदर्शित करते हैं कि जीतने वाले सेट को खोजने की जटिलता उम्मीदवारों की संख्या के साथ लॉगरिदमिक रूप से बढ़ने के बजाय एक छोटे स्थिरांक (4) द्वारा सीमित है।

लेखक स्पष्ट रूप से कहते हैं कि उनके परिणाम उस सामान्य अनुमान को हल नहीं करते हैं कि सभी चुनावों (जहाँ $D$ अनबाउंडेड है) के लिए कोंडोर्सेट आयाम 3 से अधिक नहीं है। वे स्वीकार करते हैं कि हाल के स्वतंत्र कार्य जैसे कि चारिकर एट अल. [10] और न्गुयेन एट अल. [28] ने संभावabilistic सैंपलिंग और मिनिमैक्स थ्योरम का उपयोग करके एक स्थिर ऊपरी सीमा 5 (6 और 16 से सुधारा गया) स्थापित की है। इस शोध पत्र का महत्व इसके $D=2$ मामले के लिए ज्यामितीय दृष्टिकोण में निहित है, जो स्थानिक मॉडलों के लिए एक कड़ा बाउंड (4) प्रदान करता है और छोटे कोंडोर्सेट विजेता सेट के अस्तित्व के साथ मीट्रिक आयाम के संबंध को स्पष्ट करता है।

शोध पत्र $D=2$ के लिए सिद्ध निचली सीमा 2 और ऊपरी सीमा 4 के बीच के अंतर को एक खुले प्रश्न के रूप में पहचानकर समाप्त होता है, साथ ही यह सामान्य प्रश्न भी बना हुआ है कि क्या आयाम सार्वभौमिक रूप से 3 द्वारा सीमित है।

तकनीकी सारांश: मीट्रिक स्पेस का कोंडोर्सेट आयाम (The Condorcet Dimension of Metric Spaces)

इसी तरह के और पेपर