Note on the size of a stable matching

तकनीकी सारांश: एक स्थिर मिलान के आकार पर नोट

समस्या विवरण
यह शोध पत्र एक-से-एक (one-to-one) द्वि-पक्षीय मिलान बाजार (श्रमिक और एकल-स्थान वाली फर्में) में एक स्थिर मिलान (stable matching) के आकार और सबसे बड़े व्यक्तिगत रूप से तर्कसंगत (अधिकतम) मिलान के आकार के बीच संबंध की जांच करता है। जबकि गेल-शैपले (Gale-Shapley) ढांचा स्थिर मिलानों के अस्तित्व की गारंटी देता है, यह इस बात की गारंटी नहीं देता कि ये मिलान नियोजित श्रमिकों या भरे गए पदों की संख्या को अधिकतम करेंगे। लेखक निम्नलिखित प्रश्न को संबोधित करते हैं: एक ऐसे बाजार में जहाँ सबसे बड़ा व्यक्तिगत रूप से तर्कसंगत मिलान $n$ जोड़ों का है, तो किसी भी स्थिर मिलान में जोड़ों की संख्या की निचली सीमा (lower bound) क्या है? इसके अतिरिक्त, वे उन विशिष्ट प्राथमिकता संरचनाओं का लक्षण वर्णन करते हैं जो स्थिर मिलानों को अधिकतम के सापेक्ष यथासंभव छोटा होने के लिए मजबूर करती हैं, और स्थिर जोड़ों और अधिकतम जोड़ों के बीच ओवरलैप का विश्लेषण करते हैं।

कार्यप्रणाली
लेखक मिलान बाजार को मॉडल करने के लिए ग्राफ-सैद्धांतिक दृष्टिकोण का उपयोग करते हैं, जिसमें अनडिरेक्टेड (undirected) और डायरेक्टेड (directed) दोनों ग्राफ स्वरूपों का उपयोग किया गया है।

1. अनडिरेक्टेड ग्राफ स्वरूप: बाजार को एक बाइपार्टाइट ग्राफ $G = (W, F; E)$ के रूप में मॉडल किया गया है, जहाँ किनारे (edges) स्वीकार्य जोड़ों का प्रतिनिधित्व करते हैं। लेखक अधिकतम मिलान के गुणों का उपयोग करके सीमाएं स्थापित करते हैं।
2. डायरेक्टेड ग्राफ (डिग्राफ) स्वरूप: प्राथमिकता संरचनाओं के लक्षण वर्णन के लिए, लेखक माफ़्रे (Maffray, 1992) द्वारा प्रस्तावित मिलान डिग्राफ स्वरूप को अपनाते हैं। इस डिग्राफ $D = (V, A)$ में, वर्टिक्स (vertices) स्वीकार्य जोड़े $(w, f)$ का प्रतिनिधित्व करते हैं, और आर्क (arcs) प्राथमिकता रैंकिंग (जैसे, $(w, f)$ से $(w, f')$ तक का एक आर्क यह दर्शाता है कि श्रमिक $w$ $f'$ को $f$ की तुलना में अधिक पसंद करता है) का प्रतिनिधित्व करते हैं।
3. अनुपयुक्त विकल्पों का पुनरावृत्ति विलोपन (IDUA): लेखक बाजार को उसके "सामान्य रूप" (normal form) में कम करने के लिए IDUA प्रक्रिया (बलिंस्की और रैटियर, 1997; गुटिन आदि, 2023) का उपयोग करते हैं। यह प्रक्रिया पुनरावृत्ति रूप से उन जोड़ों को हटाती है जो किसी भी स्थिर मिलान का हिस्सा नहीं हो सकते (जैसे, ऐसे जोड़े जहाँ एक प्रतिभागी अपने सबसे पसंदीदा साथी के अनमैच (unmatched) होने के दौरान एक कम पसंदीदा साथी के साथ जुड़ा होता है)।
4. रचनात्मक लक्षण वर्णन (Constructive Characterization): लेखक एक आधारभूत बाजार के साथ एक स्थिर अधिकतम मिलान को विस्तारित करके और नए प्रतिभागियों की प्राथमिकताओं को इस तरह से संरचित करके जो मौजूदा स्थिर प्रतिभागियों के लिए "अनुपयुक्त" हों, विशिष्ट बाजारों ($G_n$ और $F_n$) को परिभाषित करते हैं।

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

• थ्योरम 1 (आकार सीमा): प्राथमिक परिणाम यह स्थापित करता है कि किसी भी ऐसे बाजार में जहाँ सबसे बड़ा व्यक्तिगत रूप से तर्कसंगत मिलान आकार $n$ का है, प्रत्येक स्थिर मिलान का आकार कम से कम $\lceil n/2 \rceil$ होना चाहिए।

  • प्रमाण तर्क: प्रमाण दो तथ्यों पर निर्भर करता है: (i) एक स्थिर मिलान एक मैक्सिमल (maximal) मिलान है (कोई भी स्वीकार्य जोड़ा मौजूद नहीं है जिसके दोनों पक्ष अनमैच हों), और (ii) किसी भी ग्राफ में एक मैक्सिमल मिलान, एक मैक्सिमम (maximum) मिलान के आधे आकार का कम से कम होता है।
  • निहितार्थ: संतुलन रोजगार दर कभी भी अधिकतम संभावित रोजगार के 50% से नीचे नहीं गिर सकती, बशर्ते कि अधिकतम मिलान व्यक्तिगत रूप से तर्कसंगत हो।

• थ्योरम 2 (चरम प्राथमिकताओं का लक्षण वर्णन): यह शोध पत्र उन प्राथमिकता प्रोफाइल्स ($F_n$) के वर्ग का लक्षण वर्णन करता है जो इस निचली सीमा को प्राप्त करते हैं।

  • एक बाजार इस सीमा को तब प्राप्त करता है (स्थिर आकार = $\lceil n/2 \rceil$, अधिकतम आकार = $n$) यदि और केवल यदि वह $F_n$ वर्ग से संबंधित हो।
  • संरचनात्मक गुण: इन बाजारों में, प्रतिभागी जो किसी भी स्थिर मिलान में दिखाई नहीं देते हैं (संतुलन में "अनमैच"), वे एक-दूसरे को अनुपयुक्त पाते हैं। यदि वे एक-दूसरे को स्वीकार्य पाते, तो वे एक ब्लॉकिंग पेयर (blocking pair) बनाते, जिससे स्थिर मिलान का आकार बढ़ जाता।
  • शीर्ष पर सहमति (Agreement at the Top):* इन बाजारों का एक स्वाभाविक उप-वर्ग "एग्रीमेंट एट द टॉप" प्रदर्शित करता है, जहाँ प्रतिभागी अपने सबसे कम पसंदीदा स्थिर साथी के नीचे सभी नए, गैर-स्थिर प्रतिभागियों को रैंक करते हैं।

• थ्योरम 3 (ओवरलैप और बलिदान): लेखक एक स्थिर मिलान ($\mu^*$) और एक अधिकतम मिलान ($\mu$) के बीच के प्रतिच्छेदन (intersection) का विश्लेषण करते हैं।

  • मान लीजिए $r$ सामान्य जोड़ों की संख्या है। थ्योरम कहता है: $|\mu^*| \geq (|\mu| + r) / 2$।
  • निहितार्थ: जब स्थिर मिलान को न्यूनतम किया जाता है (अर्थात, $|\mu^*| = \lceil |\mu|/2 \rceil$), तो ओवरलैप $r$ शून्य होना चाहिए। इसका अर्थ है कि यदि बाजार को इस तरह से संरचित किया गया है कि स्थिर मिलान यथासंभव छोटे हों, तो स्थिर मिलान में मौजूद कोई भी जोड़ा अधिकतम मिलान में दिखाई नहीं देगा।
  • स्थिरता की लागत: रोजगार को अधिकतम करने (सभी रिक्तियों को भरने) के लिए उन सभी संतुलन जोड़ियों को "बलिदान" करने की आवश्यकता हो सकती है जो अन्यथा एक छोटे, स्थिर विन्यास में मौजूद होतीं।

महत्व और दायरा
यह शोध पत्र अपने विश्लेषण को "स्थिरता की लागत" के अन्वेषण के रूप में प्रस्तुत करता है। यह स्थिरता और दक्षता (मिलान के आकार द्वारा मापा गया) के बीच के ट्रेड-ऑफ को मात्रात्मक रूप से निर्धारित करता है। लेखक उल्लेख करते हैं कि जबकि स्थिरता यह सुनिश्चित करती है कि कोई ब्लॉकिंग पेयर न हो, यह अधिकतम रोजगार की तुलना में नियोजित श्रमिकों की संख्या में महत्वपूर्ण कमी ला सकती है, विशेष रूप से थ्योरम 2 में पहचाने गए प्राथमिकता संरचनाओं वाले बाजारों में।

लेखक स्पष्ट रूप से अपने परिणामों के दायरे को एक-से-एक द्वि-पक्षीय मिलान बाजारों तक सीमित करते हैं। वे स्वीकार करते हैं कि हालांकि यह ढांचा व्यापक रूप से लागू करने योग्य है (जैसे, छात्र-कॉलेज, डॉक्टर-अस्पताल), यहाँ प्राप्त विशिष्ट सीमाएँ और लक्षण वर्णन अधिक जटिल वातावरण जैसे कि कई-से-एक (many-to-one) बाजारों, कपल्स (couples) वाले बाजारों, या एक-पक्षीय "रूममेट" समस्याओं पर स्वतः लागू नहीं होते हैं। यह शोध पत्र नए एल्गोरिदम या प्रायोगिक अनुप्रयोगों का प्रस्ताव नहीं करता है, बल्कि एक सैद्धांतिक सीमा और स्थिर इक्विलिब्रियम के लिए रोजगार दरों के सबसे खराब मामलों के संरचनात्मक लक्षण वर्णन प्रदान करता है।