📈 economics

Experimental Design for Matching

यह शोध पत्र एक अल्टरनेटिंग पाथ रैंडमाइज्ड डिज़ाइन प्रस्तावित करता है जो विसंगति सेटों (disagreement sets) को विसंयुक्त अल्टरनेटिंग पथों और चक्रों में उनके अद्वितीय अपघटन का लाभ उठाकर हस्तक्षेप के तहत मिलान तंत्रों के निष्पक्ष, कम-विचलन वाले प्रयोगात्मक तुलनाओं को सक्षम बनाता है, जबकि इन परिणामों को क्षमता बाधाओं वाले मैनी-टू-वन (many-to-one) परिवेशों तक विस्तारित करता है।

मूल लेखक: Chonghuan Wang

प्रकाशित 2026-01-30

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Chonghuan Wang

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

कल्पना कीजिए कि आप एक विशाल मैचमेकिंग सर्विस के मैनेजर हैं। आपके पास एक नया एल्गोरिदम है (मान लीजिए कि यह "न्यू डांस" है), और एक पुराना, भरोसेमंद एल्गोरिदम है (जो "ओल्ड डांस" है)। आप जानना चाहते हैं: क्या न्यू डांस वास्तव में ओल्ड डांस की तुलना में लोगों को अधिक खुश करता है?

एक आदर्श दुनिया में, आप हर एक व्यक्ति को न्यू डांस के साथ जोड़ सकते हैं, उनकी खुशी माप सकते हैं, फिर तुरंत उन्हें ओल्ड डांस के साथ फिर से जोड़ सकते हैं और भी माप सकते हैं। लेकिन समस्या यह है: आप दोनों को एक ही समय में नहीं कर सकते।

यदि व्यक्ति A, व्यक्ति B के साथ न्यू डांस में नाच रहा है, तो वह उसी क्षण व्यक्ति C के साथ ओल्ड डांस में नहीं नाच सकता। इसे पेपर में "मैचिंग इंटरफेरेंस" (matching interference) कहा गया है। यह एक ही चौराहे पर दो अलग-अलग ट्रैफिक लाइट पैटर्न को टेस्ट करने जैसा है; बिना क्रैश किए आप दोनों पैटर्न एक साथ सक्रिय नहीं रख सकते।

यह पेपर इस समस्या का समाधान करता है कि इन दो मैचिंग प्लान्स को वैज्ञानिक रूप से कैसे टेस्ट किया जाए बिना सिस्टम को क्रैश किए या फर्जी डेटा बनाए।

मुख्य विचार: "डिसएग्रीमेंट मैप" (Disagreement Map)

लेखकों ने महसूस किया कि आपको हर किसी को टेस्ट करने की आवश्यकता नहीं है। आपको केवल उन लोगों को टेस्ट करने की आवश्यकता है जिन्हें दोनों प्लान्स द्वारा अलग तरह से ट्रीट किया जा रहा है।

सहमति (The Agreement): यदि न्यू डांस और ओल्ड डांस दोनों व्यक्ति A को व्यक्ति B के साथ जोड़ते हैं, तो आपको उन्हें टेस्ट करने की आवश्यकता नहीं है। वे दोनों दुनियाओं में समान हैं।
असहमति (The Disagreement): यदि न्यू डांस A को B के साथ जोड़ता है, लेकिन ओल्ड डांस A को C के साथ जोड़ता है, तो वही वह जगह है जहाँ हलचल है।

लेखक इस अंतरों के संग्रह को "डिसएग्रीमेंट सेट" (Disagreement Set) कहते हैं।

जादुई ट्रिक: अल्टरनेटिंग पाथ्स और साइकिल्स (Alternating Paths and Cycles)

एक बार जब आप डिसएग्रीमेंट सेट को अलग कर लेते हैं, तो पेपर एक सुंदर ज्यामितीय संरचना प्रकट करता है। यदि आप उन लोगों को जोड़ने वाली रेखाएं खींचते हैं जो इन असहमतियों में शामिल हैं, तो वे स्वाभाविक रूप से पाथ्स (paths) (जैसे डोमिनोज़ की एक लाइन) और साइकिल्स (cycles) (जैसे हाथ पकड़े दोस्तों का एक घेरा) बनाते हैं।

एक लाइन के लोगों की कल्पना करें:

व्यक्ति 1 को न्यू प्लान में व्यक्ति 2 के साथ जोड़ा गया है।
व्यक्ति 2 को ओल्ड प्लान में व्यक्ति 3 के साथ जोड़ा गया है।
व्यक्ति 3 को न्यू प्लान में व्यक्ति 4 के साथ जोड़ा गया है।
व्यक्ति 4 को ओल्ड प्लान में व्यक्ति 5 के साथ जोड़ा गया है।

यह एक श्रृंखला बनाता है: न्यू → ओल्ड → न्यू → ओल्ड।

पेपर का मुख्य नवाचार एक गेम प्लान है जिसे अल्टरनेटिंग पाथ रैंडमाइज्ड डिज़ाइन (AP Design) कहा जाता है। यह इस प्रकार काम करता है:

लाइन पर चलें: आप इन श्रृंखलाओं (paths) और घेरों (cycles) के माध्यम से चलते हैं।
फ्लिप-फ्लॉप नियम: आप पहले जोड़े के लिए एक निर्णय लेते हैं। यदि आप "न्यू" जोड़ी चुनते हैं, तो आपको अगली जोड़ी को छोड़ना होगा (क्योंकि इंटरफेरेंस होता है)। यदि आप पहली को छोड़ देते हैं, तो आपके पास दूसरी को चुनने का मौका होता है।
सीक्रेट सॉस (संभावना): पेपर इन विकल्पों को चुनने के लिए सटीक संभावनाओं की गणना करता है। यह पाया गया है कि यदि श्रृंखला लंबी है, तो "न्यू" जोड़ी चुनने का सबसे अच्छा मौका लगभग 41.4% ( $\sqrt{2}-1$ $2 - 1$ ) है, न कि 50%।
- 50% क्यों नहीं? यदि आप 50/50 सिक्का उछालते हैं, तो आप गलती से दो ऐसी जोड़ियां चुन सकते हैं जो आपस में टकराती हों। संभावना को थोड़ा झुकाकर (लगभग 41% तक), आप यह सुनिश्चित करते हैं कि सिस्टम स्थिर रहे और डेटा कम "शोर भरा" (noisy) हो।

यह "नेइव" (Naive) तरीके से बेहतर क्यों है

पेपर अपने तरीके की तुलना एक "नेइव" दृष्टिकोण से करता है, जो मूल रूप से यह है: "चलिए एक बड़ा सिक्का उछालते हैं। हेड्स आया, तो हम पूरे सिस्टम को न्यू डांस के साथ चलाएंगे। टेल्स आया, तो हम पूरे सिस्टम को ओल्ड डांस के साथ चलाएंगे।"

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

"मेनी-टू-वन" चुनौती (बफे की समस्या)

पेपर एक कठिन परिदृश्य को भी संबोधित करता है: मेनी-टू-वन मैचिंग (Many-to-One Matching)।
कल्पना कीजिए कि 100 छात्रों वाले एक स्कूल में 5 शिक्षक हैं। प्रत्येक शिक्षक 20 छात्रों को ले सकता है, लेकिन प्रत्येक छात्र का केवल एक ही शिक्षक हो सकता है।

इस मामले में, "चेन" (श्रृंखलाएं) अव्यवस्थित हो जाती हैं। एक शिक्षक कई छात्रों से जुड़ा हो सकता है। पेपर दिखाता है कि आप इसे एक फ्लो नेटवर्क (flow network) (जैसे पानी के पाइप) में बदलकर अभी भी हल कर सकते हैं।

वे असहमतियों का एक "मैप" बनाते हैं।
वे "ऑगमेंटिंग पाथ्स" (augmenting paths) और "यूलर टूर्स" (Euler tours)—जो पेन उठाए बिना लूप को ट्रेस करने के फैंसी तरीके हैं—का उपयोग करके उस अव्यवस्थित मैप को वापस साफ-सुथरी, गैर-टकराव वाली श्रृंखलाओं में तोड़ देते हैं।
एक बार जब उनके पास ये साफ श्रृंखलाएं होती हैं, तो वे उसी "फ्लिप-फ्लॉप" रैंडमाइजेशन ट्रिक का उपयोग कर सकते हैं।

निचोड़ (The Bottom Line)

यह पेपर मैचिंग सिस्टम (जैसे डेटिंग ऐप्स, अंग विनिमय, या स्कूल असाइनमेंट) पर निष्पक्ष प्रयोग चलाने के लिए एक नियम पुस्तिका प्रदान करता है, जहाँ आप दो संस्करणों को एक साथ नहीं चला सकते।

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

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

तकनीकी सारांश: मिलान (मैचिंग) के लिए प्रयोगात्मक डिज़ाइन

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

कार्यप्रणाली
लेखक अल्टरनेटिंग पाथ रैंडमाइज्ड डिज़ाइन (AP डिज़ाइन) का प्रस्ताव करते हैं, जो ग्राफ़ थ्योरी और डिज़ाइन-आधारित अनुमान पर आधारित एक ढांचा है।

असहमति सेट (डिसेग्रीमेंट सेट) और अपघटन (डिकम्पोज़िशन):
मुख्य संरचनात्मक अंतर्दृष्टि असहमति सेट ( $\Delta M_{(t,c)}$ ) की परिभाषा है, जिसमें वे मिलान जोड़े शामिल हैं जो दो योजनाओं (उपचार या नियंत्रण) में से ठीक एक में मौजूद हैं। शोध पत्र सिद्ध करता है कि एक-से-एक (one-to-one) मिलान के लिए, यह सेट विलगित (डिस्क्रीट) अल्टरनेटिंग पाथ और साइकिलों में एक अद्वितीय अपघटन स्वीकार करता है। इन संरचनाओं में, किनारे (एजेस) उपचार मिलान ( $M_t$ ) और नियंत्रण मिलान ( $M_c$ ) के बीच बारी-बारी से चलते हैं। क्षमता संबंधी बाधाओं के कारण, एक अल्टरनेटिंग पाथ या साइकिल में आसन्न किनारों को एक साथ क्रियान्वित नहीं किया जा सकता है।
यादृच्छिकरण योजना (रैंडमाइजेशन स्कीम):
AP डिज़ाइन इन पथों और चक्रों के अनुक्रमिक यादृच्छिकरण को निष्पादित करता है।
- पथ का मामला: एक खुले पथ के लिए, पहला किनारा $p/(1+p)$ प्रायिकता के साथ चुना जाता है। बाद के किनारे $p$ की सशर्त प्रायिकता के साथ चुने जाते हैं यदि पूर्ववर्ती चुना नहीं गया था; अन्यथा, किनारे को नियत रूप से छोड़ दिया जाता है (प्रायिकता 0)।
- चक्र का मामला: समान अनुक्रमिक नियम लागू होते हैं, जहाँ अंतिम किनारा पहले और पूर्ववर्ती किनारों के क्रियान्वयन के आधार पर नियत रूप से निर्धारित होता है ताकि व्यवहार्यता सुनिश्चित हो सके।
- स्वतंत्रता: विभिन्न पथों और चक्रों के बीच यादृच्छिकरण स्वतंत्र रूप से किया जाता है।
अनुमान (एस्टिमेशन):
लेखक औसत उपचार प्रभाव (ATE) का अनुमान लगाने के लिए हॉरविट्ज़-थॉमसन एस्टिमेटर का उपयोग करते हैं। वे AP डिज़ाइन के तहत इस एस्टिमेटर की निष्पक्षता (unbiasedness) स्थापित करते हैं।
अनुकूलन (मिनिमैक्स फ्रेमवर्क):
दक्षता को अनुकूलित करने के लिए, लेखक एक सीमित संभावित परिणाम धारणा के तहत एस्टिमेटर के सबसे खराब स्थिति वाले प्रसरण (वेरिएंस) का विश्लेषण करते हैं। वे इष्टतम सशर्त यादृच्छिककरण प्रायिकता $p$ खोजने के लिए एक मिनिमैक्स समस्या को सूत्रबद्ध करते हैं।
- अनंतस्पर्शी परिणाम (एसिम्प्टोटिक रिजल्ट): लंबे पथों और चक्रों के लिए, इष्टतम $p$ $\sqrt{2} - 1 \approx 0.4142$ की ओर अभिसरित होता है। यह मान 0.5 से स्पष्ट रूप से कम है, जो एक ट्रेड-ऑफ को दर्शाता है जहाँ वर्तमान किनारे के प्रसरण योगदान को कम करने के लिए डाउनस्ट्रीम हस्तक्षेप को ध्यान में रखना आवश्यक है।
मेनी-टू-वन विस्तार:
इस ढांचे को मेनी-टू-वन मिलान (जैसे छात्र-स्कूल असाइनमेंट) के लिए विस्तारित किया गया है, जहाँ क्षमता संबंधी बाधाएं अपघटन को जटिल बनाती हैं। लेखक एक सहायक असंतुलित निर्देशित ग्राफ़ (auxiliary unbalanced directed graph) का निर्माण करते हैं जो असहमति सेट का प्रतिनिधित्व करता है। वे एक व्यवहार्य अपघटन खोजने की समस्या को दो ग्राफ़-सैद्धांतिक कार्यों में कम करते हैं:
- नोड डिग्री में असंतुलन को संभालने के लिए निर्मित फ्लो नेटवर्क में ऑगमेंटिंग पाथ खोजना।
- शेष संतुलित ग्राफ़ पर यूलर-टूर अपघटन (Euler-tour decompositions) करना।
  यह सुनिश्चित करता है कि परिणामी अल्टरनेटिंग पाथ और साइकिल क्षमता संबंधी बाधाओं को पूरा करते हैं, जिससे AP डिज़ाइन और अनुमान गारंटी को लागू किया जा सके।

प्रमुख परिणाम

निष्पक्षता (Unbiasedness): AP डिज़ाइन के तहत हॉरविट्ज़-थॉमसन एस्टिमेटर ATE के लिए निष्पक्ष है।
प्रसरण स्केलिंग (वेरिएंस स्केलिंग): नैिव (naive) डिज़ाइनों के विपरीत (जो पूरे उपचार या नियंत्रण मिलान को 0.5 की प्रायिकता के साथ चुनते हैं), जहाँ जनसंख्या आकार $N \to \infty$ होने पर प्रसरण समाप्त नहीं होता है, AP डिज़ाइन के प्रसरण में $O(1/N)$ की दर से कमी आती है।
केंद्रीय सीमा प्रमेय (CLT): शोध पत्र एस्टिमेटर के लिए एक परिमित-जनसंख्या CLT स्थापित करता है। यह परिणाम गैर-तुच्छ (non-trivial) है क्योंकि असहमति सेट का अपघटन जैसे समय के साथ बढ़ती जनसंख्या के साथ जटिल, विषम और संभावित रूप से अस्थिर पैटर्न (लघु और दीर्घ घटकों का मिश्रण) प्रदर्शित कर सकता है। प्रमाण लिंडेबर्ग-फेलर तर्कों को $\alpha$ -मिक्सिंग तकनीकों और बोलजानो-वेइरस्ट्रास प्रमेय के साथ जोड़ता है।
प्रसरण सीमाएँ: लेखक एक अनुमान योग्य ऊपरी सीमा प्राप्त करते हैं जो केवल अवलोकनीय मात्राओं पर निर्भर करती है, जिससे अनंतस्पर्शी विश्वास अंतराल (confidence intervals) का निर्माण संभव होता है।
संख्यात्मक सत्यापन: रिवेलियो लैब्स (Revelio Labs) के वर्कफोर्स डेटासेट का उपयोग करते हुए, संख्यात्मक प्रयोग पुष्टि करते हैं कि AP डिज़ाइन प्रसरण में कमी लाने के मामले में नैिव डिज़ाइन की तुलना में काफी बेहतर प्रदर्शन करता है। एस्टिमेटर का अनुभवजन्य वितरण मानक सामान्य वितरण के साथ संरेखित है, जो CLT को मान्य करता है। अनुभवजन्य इष्टतम $p$ ( $\approx 0.417$ ) सैद्धांतिक सबसे खराब स्थिति के इष्टतम ( $\sqrt{2}-1$ ) के करीब है।

महत्व और दावे
यह शोध पत्र मिलान तंत्रों के परीक्षण के लिए एक डिज़ाइन-आधारित, धारणा-मुक्त ढांचे के रूप में कार्य करने का दावा करता है। इसका महत्व निम्नलिखित में निहित है:

मिलान हस्तक्षेप को संबोधित करना: यह मिलान बाजारों में निहित विशिष्ट हस्तक्षेप समस्या के लिए एक सिद्धांतपूर्ण समाधान प्रदान करता है, जहाँ इकाइयाँ स्वतंत्र नहीं होती हैं।
संरचनात्मक नवाचार: असहमति सेट को अल्टरनेटिंग पाथ और साइकिल में अद्वितीय अपघटन, हस्तक्षेप प्रबंधन के लिए एक कठोर संरचनात्मक आधार प्रदान करता है।
मजबूत अनुमान (Robust Inference): अस्थिर और विषम घटक संरचनाओं को समायोजित करने के लिए एक CLT स्थापित करके, यह कार्य बिना किसी परिणाम मॉडल की आवश्यकता के जटिल मिलान वातावरण में वैध अनंतस्पर्शी अनुमान को सक्षम बनाता है।
व्यावहारिक प्रयोज्यता: ऑर्गन एक्सचेंज और स्कूल चॉइस जैसे क्षमता संबंधी बाधाओं वाले वास्तविक दुनिया के परिदृश्यों में अनुप्रयोग के लिए ग्राफ़-सैद्धांतिक उपकरणों (ऑगमेंटिंग पाथ और यूलर टूर) के माध्यम से मेनी-टू-वन मिलान में इसका विस्तार किया गया है।

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

मुख्य विचार: "डिसएग्रीमेंट मैप" (Disagreement Map)

जादुई ट्रिक: अल्टरनेटिंग पाथ्स और साइकिल्स (Alternating Paths and Cycles)

यह "नेइव" (Naive) तरीके से बेहतर क्यों है

"मेनी-टू-वन" चुनौती (बफे की समस्या)

निचोड़ (The Bottom Line)

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