Asymptotic Equivalence of Immediate and Deferred Acceptance

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

दशकों से, विशेषज्ञ इसे करने के दो मुख्य तरीकों पर बहस कर रहे हैं। पहला तरीका है डिफर्ड एक्सेप्टेंस (DA - विलंबित स्वीकृति)। इसे एक धीमी, सावधानीपूर्ण नृत्य की तरह समझें। छात्र अपने शीर्ष विकल्प के लिए आवेदन करते हैं। स्कूल अपने पसंदीदा आवेदकों को थामे रखते हैं लेकिन उन्हें हमेशा के लिए "हाँ" नहीं कहते; वे बस "शायद" कहते हैं। यदि बाद में कोई बेहतर छात्र आता है, तो स्कूल उन्हें बदल सकता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि सब कुछ तय न हो जाए। यह अपने निष्पक्ष होने और धोखाधड़ी असंभव होने के लिए प्रसिद्ध है, लेकिन यह थोड़ा अव्यवस्थित और अक्षम हो सकता है।

दूसरा तरीका है इमीडिएट एक्सेप्टेंस (IA - तत्काल स्वीकृति), जिसे अक्सर "बोस्टन तंत्र" के रूप में जाना जाता है। यह एक उन्मत्त दौड़ की तरह है। छात्र कतार में लगते हैं और अपने शीर्ष विकल्प के लिए आवेदन करते हैं। स्कूल कतार को देखते हैं, प्राथमिकता के आधार पर अपने पसंदीदा को चुनते हैं, और कहते हैं, "आप अंदर हैं!" यदि आपको अस्वीकार कर दिया जाता है, तो आप तुरंत अपने दूसरे विकल्प की ओर दौड़ते हैं। इसकी कमी यह है कि यदि आप अपने शीर्ष विकल्प के लिए देर से आवेदन करते हैं, तो आप उस व्यक्ति की जगह खो सकते हैं जिसकी प्राथमिकता अधिक है जिसने पहले आवेदन किया था, भले ही आप वास्तव में उस स्कूल को अधिक पसंद करते हों। इस कारण से, IA की अक्सर अनैतिक या हेरफेर के योग्य होने के लिए आलोचना की जाती है। हालाँकि, इसके पास एक बड़ी शक्ति है: यदि हर कोई सच बोलता है कि वे क्या चाहते हैं, तो IA एक ऐसा परिणाम सुनिश्चित करता है जहाँ किसी को भी तब तक अधिक खुश नहीं बनाया जा सकता जब तक कि किसी और को दुखी न किया जाए। इसे "पारेटो एफिशिएंसी" (Pareto efficiency) कहा जाता है।

तो, यहाँ मिलियन डॉलर का सवाल है: क्या IA की शक्ति वास्तव में वास्तविक जीवन में कोई बड़ा अंतर पैदा करती है? क्या यह बच्चों को ऐसे स्कूलों में पहुँचाता है जो वे बहुत अधिक पसंद करते हैं, DA पद्धति की तुलना में? या क्या अंतर बस एक छोटा, अदृश कण जैसा है? यह पहेली है जिसे जोसुए ऑर्टेगा (Josué Ortega) अपने शोध पत्र में सुलझाते हैं।

---

द ग्रेट स्कूल रेस: दो तंत्रों की एक कहानी

क्वीन्स यूनिवर्सिटी बेलफास्ट के एक शोधकर्ता, जोसुए ऑर्टेगा ने इस बहस को सुलझाने के लिए एक विशाल विचार प्रयोग (thought experiment) चलाने का निर्णय लिया। उन्होंने वास्तविक शहरों के साथ उनके जटिल इतिहास और राजनीति को नहीं देखा। इसके बजाय, उन्होंने एक "रैंडम मार्केट" की कल्पना की—एक ऐसी दुनिया जहाँ प्रत्येक छात्र की पसंदीदा स्कूलों की सूची पूरी तरह से यादृच्छिक (random) रूप से चुनी गई है, जैसे टोकरी से नाम निकालना। इस दुनिया में, $n$ छात्र और $n$ स्कूल हैं।

ऑर्टेगा ने "औसत रैंक" (average rank) को मापने का निर्णय लिया। कल्पना कीजिए कि यदि प्रत्येक छात्र को एक स्कोर मिलता है कि उनका आवंटित स्कूल उनकी सूची में कितने स्थान पर था। यदि आपको अपना #1 विकल्प मिलता है, तो आपकी रैंक 1 है। यदि आपको अपना #100 विकल्प मिलता है, तो आपकी रैंक 100 है। लक्ष्य इस संख्या को यथासंभव कम रखना है।

लंबे समय से, हमें धीमे, सावधानीपूर्ण नृत्य (DA) का उत्तर पता था। 1970 के दशक में, गणितज्ञों ने पता लगाया कि एक रैंडम मार्केट में, औसत छात्र लगभग $\log n$ (n का लघुगणक) की रैंक वाले स्कूल में समाप्त होता है। यदि आपके पास 1,000 छात्र हैं, तो औसत रैंक लगभग 7 है। यदि आपके पास 100,000 छात्र हैं, तो यह लगभग 11 है। यह बढ़ता तो है, लेकिन बहुत धीरे।

लेकिन उन्मत्त दौड़ (IA) के बारे में क्या? क्योंकि IA अलग तरह से काम करता है—जहाँ आवेदन का क्रम मायने रखता है और छात्र केवल इसलिए खारिज हो सकते हैं क्योंकि वे "देर" से आए—गणितज्ञों ने सोचा कि यह बहुत अधिक जटिल हो सकता है। कुछ कंप्यूटर वैज्ञानिकों ने इसे हल करने की कोशिश की थी, लेकिन वे केवल किसी विशिष्ट रैंक प्राप्त करने की संभावनाओं को समझ सके, न कि सभी के लिए औ औसत रैंक को। उन्होंने अनुमान लगाया कि यह भी लघुगणकीय (logarithmic) ही होगा, लेकिन कोई इसे सिद्ध नहीं कर सका।

"कूपन कलेक्टर" का रहस्य

ऑर्टेगा की सफलता यह समझने में थी कि दोनों तंत्र, अपने पूरी तरह से अलग दिखने के बावजूद, गुप्त रूप से एक ही खेल खेल रहे हैं। उन्होंने इसे समझाने के लिए एक क्लासिक पहेली का उपयोग किया जिसे कूपन कलेक्टर प्रॉब्लम कहा जाता है।

कल्पना कीजिए कि आप $n$ अलग-अलग ट्रेडिंग कार्डों का एक पूरा सेट इकट्ठा करने की कोशिश कर रहे हैं। हर बार जब आप अनाज का एक डिब्बा खरीदते हैं, तो आपको एक रैंडम कार्ड मिलता है। सभी कार्डों को कम से कम एक बार पाने के लिए आपको कितने डिब्बे खरीदने होंगे?
इसका उत्तर लगभग $n \times \log n$ है। आप अंतिम कुछ दुर्लभ कार्डों को खोजने के लिए बहुत सारे डिब्बे खरीदने में समय बिताते हैं।

ऑर्टेगा ने दिखाया कि डिफर्ड एक्सेप्टेंस (DA) बिल्कुल इसी तरह है। छात्र तब तक आवेदन करते रहते हैं जब तक कि प्रत्येक स्कूल को कम से कम एक आवेदन प्राप्त न हो जाए। सभी द्वारा किए गए कुल आवेदन लगभग उतने ही हैं जितने कि कूपन इकट्ठा करने के लिए आपको अनाज के डिब्बों की आवश्यकता होगी। चूंकि औसत छात्र लगभग $\log n$ आवेदन करता है, इसलिए उनकी अंतिम स्कूल रैंक भी लगभग $\log n$ होती है।

फिर, ऑर्टेगा ने अपनी दृष्टि इमीडिएट एक्सेप्टेंस (IA) की ओर मोड़ी। पहली नज़र में यह अलग लगता है क्योंकि छात्र तुरंत फिर से आवेदन नहीं कर सकते; उन्हें दोबारा प्रयास करने से पहले एक "राउंड" समाप्त होने का इंतजार करना पड़ता है। लेकिन ऑर्टेगा ने महसूस किया कि यदि आप प्रक्रिया को एक विशिष्ट तरीके से देखते हैं, तो यह भी एक कूपन कलेक्टर की तरह ही है।

उन्होंने एक थोड़े "विस्मृतिशील" (amnesiac) संस्करण की कल्पना की। मान लीजिए कि एक छात्र यादृच्छिक रूप से स्कूल चुनता रहता है, भले ही उसने पहले ही उस स्कूल का प्रयास किया हो। यदि वह एक ऐसा स्कूल चुनता है जिसका उसने पहले ही प्रयास किया है, तो वह उसे अनदेखा कर देता है (यह एक "बर्बाद" ड्रा है)। ऑर्टेगा ने सिद्ध किया कि इन बर्बाद हुए ड्रॉ के साथ भी, प्रत्येक स्कूल को भरने के लिए आवश्यक वास्तविक आवेदनों की संख्या अभी भी लगभग कूपन कलेक्टर समस्या के समान ही है।

बड़ा खुलासा

यहाँ मुख्य बात है: दोनों विधियों के बीच का अंतर आश्चर्यजनक रूप से छोटा है।

ऑर्टेगा ने गणितीय रूप से सिद्ध किया कि जैसे-जैसे बाजार बहुत बड़ा होता जाता है (जैसे कि $n$ बहुत बड़ा हो जाता है), इमीडिएट एक्सेप्टेंस (IA) प्रणाली में छात्रों के लिए औसत रैंक भी लगभग $\log n$ ही रहती है।

इसका अर्थ यह है कि भले ही IA "पारेटो कुशल" (Pareto efficient) है (यानी, यदि सभी सच बोलते हैं तो यह सैद्धांतिक रूप से पूर्ण है), यह छात्रों को उनके शीर्ष विकल्पों को प्राप्त करने के मामले में DA पद्धति की तुलना में कोई बहुत बड़ा लाभ नहीं देता है। "प्रथम-क्रम" का सुधार—बड़ा, ध्यान देने योग्य लाभ—बस मौजूद ही नहीं है।

ऑर्टेगा का शोध पत्र स्पष्ट रूप से इस विचार को खारिज करता है कि IA एक जादुई समाधान है जो बड़े रैंडम बाजारों में छात्रों के परिणामों में भारी सुधार करता है। जबकि IA विशिष्ट, छोटे परिदृश्यों या विशिष्ट प्राथमिकता नियमों के साथ थोड़ा बेहतर हो सकता है, यह शोध पत्र दिखाता है कि सामान्य मामले में, दोनों तंत्र एसिम्प्टोटिक रूप से समान (asymptotically equivalent) हैं। दोनों ही छात्रों को बाजार के आकार के सापेक्ष लगभग लघुगणकीय (logarithmic) रैंक में पहुँचाते हैं।

यह क्यों मायने रखता है

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

ऑर्टेगा का कार्य इस निष्कर्ष को अन्य विविधताओं तक भी विस्तारित करता है। चाहे स्कूलों के पास कई सीटें हों (many-to-one matching), या छात्र भरे हुए स्कूलों को छोड़ कर आगे जाने की अनुमति रखते हों ("IA with skips" नामक एक भिन्नता), परिणाम वही रहता है: औसत रैंक लगभग $\log n$ के आसपास रहती है।

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