सचिव समस्या

n अनुप्रयोगों से सर्वश्रेष्ठ उम्मीदवार (लाल वृत्त) प्राप्त करने की संभावनाओं का ग्राफ, और k/n (नीला क्रॉस) जहां k नमूना आकार है

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

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

अब तक ज्ञात सबसे छोटा कठोर प्रमाण बाधाओं एल्गोरिथ्म द्वारा प्रदान किया गया है। इसका तात्पर्य है कि इष्टतम जीत की संभावना हमेशा कम से कम होती है $1/e$ (जहाँ e (गणितीय स्थिरांक) प्राकृतिक लघुगणक का आधार है), और यह बाद वाला बहुत अधिक सामान्यता में भी धारण करता है। इष्टतम रोक नियम हमेशा पहले को अस्वीकार करने की सलाह देता है $\sim n/e$ जिन आवेदकों का साक्षात्कार लिया जाता है और फिर पहले आवेदक पर रुकते हैं जो अब तक के साक्षात्कार वाले प्रत्येक आवेदक से बेहतर है (या यदि ऐसा कभी नहीं होता है तो अंतिम आवेदक को जारी रखें)। कभी-कभी इस रणनीति को कहा जाता है $1/e$ रोक नियम, क्योंकि इस रणनीति के साथ सबसे अच्छे आवेदक को रोकने की संभावना लगभग है $1/e$ पहले से ही मध्यम मूल्यों के लिए $n$. सचिव समस्या पर इतना अधिक ध्यान देने का एक कारण यह है कि समस्या के लिए इष्टतम नीति (रोकने का नियम) सरल है और 100 या 100 मिलियन आवेदक होने के बावजूद लगभग 37% समय में सबसे अच्छे उम्मीदवार का चयन करता है।

सूत्रीकरण

हालाँकि कई विविधताएँ हैं, मूल समस्या को निम्नानुसार कहा जा सकता है:

• भरने के लिए एक ही पद है।
• पद के लिए n आवेदक हैं, और n का मान ज्ञात है।
• आवेदकों को, यदि सभी को एक साथ देखा जाए, तो उन्हें स्पष्ट रूप से सर्वश्रेष्ठ से सबसे खराब क्रम में रखा जा सकता है।
• आवेदकों का यादृच्छिक क्रम में क्रमिक रूप से साक्षात्कार किया जाता है, जिसमें प्रत्येक आदेश समान रूप से होने की संभावना होती है।
• एक साक्षात्कार के तुरंत बाद, साक्षात्कार के आवेदक को स्वीकार या अस्वीकार कर दिया जाता है, और निर्णय अपरिवर्तनीय है।
• किसी आवेदक को स्वीकार या अस्वीकार करने का निर्णय अब तक साक्षात्कार किए गए आवेदकों के सापेक्ष रैंक पर ही आधारित हो सकता है।
• सामान्य समाधान का उद्देश्य पूरे समूह के सर्वश्रेष्ठ आवेदक के चयन की उच्चतम संभावना है। यह अपेक्षित अदायगी को अधिकतम करने के समान है, जिसमें अदायगी को सर्वश्रेष्ठ आवेदक के लिए एक और अन्यथा शून्य के रूप में परिभाषित किया गया है।

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

इष्टतम नीति प्राप्त करना

समस्या के लिए इष्टतम नीति एक रोक नियम है। इसके तहत, साक्षात्कारकर्ता पहले r − 1 आवेदकों को अस्वीकार करता है (आवेदक M को इन r − 1 आवेदकों में से सबसे अच्छा आवेदक होने दें), और फिर बाद के पहले आवेदक का चयन करता है जो आवेदक M से बेहतर है। यह दिखाया जा सकता है कि इष्टतम रणनीति रणनीतियों के इस वर्ग में निहित है। (ध्यान दें कि हमें कभी भी ऐसे आवेदक का चयन नहीं करना चाहिए जो अब तक हमने देखा है कि सबसे अच्छा नहीं है, क्योंकि वे समग्र रूप से सर्वश्रेष्ठ आवेदक नहीं हो सकते हैं।) एक मनमाना कटऑफ आर के लिए, सबसे अच्छा आवेदक चुने जाने की संभावना है

${\begin{aligned}P(r)&=\sum _{i=1}^{n}P\left({\text{applicant }}i{\text{ is selected}}\cap {\text{applicant }}i{\text{ is the best}}\right)\\&=\sum _{i=1}^{n}P\left({\text{applicant }}i{\text{ is selected}}|{\text{applicant }}i{\text{ is the best}}\right)\cdot P\left({\text{applicant }}i{\text{ is the best}}\right)\\&=\left[\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{the best of the first }}i-1{\text{ applicants}}\\{\text{is in the first }}r-1{\text{ applicants}}\end{array}}\right|{\text{applicant }}i{\text{ is the best}}\right)\right]\cdot {\frac {1}{n}}\\&=\left[\sum _{i=r}^{n}{\frac {r-1}{i-1}}\right]\cdot {\frac {1}{n}}\\&={\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}.\end{aligned}}$

राशि r = 1 के लिए परिभाषित नहीं है, लेकिन इस मामले में एकमात्र व्यवहार्य नीति पहले आवेदक का चयन करना है, और इसलिए P(1) = 1/n। यह राशि इस बात को ध्यान में रखते हुए प्राप्त की जाती है कि यदि आवेदक i सबसे अच्छा आवेदक है, तो इसे चुना जाता है यदि और केवल अगर पहले i − 1 आवेदकों में से सबसे अच्छा आवेदक उन पहले r − 1 आवेदकों में से है जिन्हें अस्वीकार कर दिया गया था। एन को अनंत की ओर ले जाने, लिखने के लिए $x$ (r−1)/n की सीमा के रूप में, (i−1)/n के लिए t और 1/n के लिए dt का उपयोग करके योग को समाकल द्वारा अनुमानित किया जा सकता है

$P(x)=x\int _{x}^{1}{\frac {1}{t}}\,dt=-x\ln(x)\;.$

के संबंध में P(x) का अवकलज लेना $x$, इसे 0 पर सेट करके, और x के लिए हल करके, हम पाते हैं कि इष्टतम x 1/e के बराबर है। इस प्रकार, इष्टतम कटऑफ एन / ई के रूप में बढ़ता है, और सबसे अच्छा आवेदक 1 / ई संभावना के साथ चुना जाता है।

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

$n$	1	2	3	4	5	6	7	8	9
$r$	1	1	2	2	3	3	3	4	4
$P$	1.000	0.500	0.500	0.458	0.433	0.428	0.414	0.410	0.406

शास्त्रीय सचिव समस्या में सर्वश्रेष्ठ आवेदक के चयन की संभावना की ओर अभिसरण होता है $1/e\approx 0.368$.

वैकल्पिक समाधान

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

सीमाएं

सचिव समस्या का समाधान केवल तभी सार्थक है जब यह मानना ​​उचित हो कि आवेदकों को नियोजित निर्णय रणनीति का कोई ज्ञान नहीं है, क्योंकि शुरुआती आवेदकों के पास कोई मौका नहीं है और अन्यथा दिखाई नहीं दे सकता है।

शास्त्रीय सचिव समस्या के समाधान के अनुप्रयोगों के लिए एक महत्वपूर्ण दोष आवेदकों की संख्या है $n$ पहले से पता होना चाहिए, जो शायद ही कभी होता है। इस समस्या को दूर करने का एक तरीका यह मान लेना है कि आवेदकों की संख्या एक यादृच्छिक चर है $N$ के ज्ञात वितरण के साथ $P(N=k)_{k=1,2,\cdots }$ (प्रेसमैन और सोनिन, 1972)। हालांकि, इस मॉडल के लिए, इष्टतम समाधान सामान्य रूप से अधिक कठिन है। इसके अलावा, इष्टतम सफलता की संभावना अब 1/e के आसपास नहीं है, लेकिन आमतौर पर कम है। इसे आवेदकों की संख्या न जानने की कीमत चुकाने के संदर्भ में समझा जा सकता है। हालांकि, इस मॉडल में कीमत ज्यादा है। के वितरण की पसंद पर निर्भर करता है $N$इष्टतम जीत संभावना शून्य तक पहुंच सकती है। इस नई समस्या से निपटने के तरीकों की तलाश में एक नए मॉडल का नेतृत्व किया गया जो तथाकथित 1/ई-कानून को सर्वोत्तम विकल्प प्रदान करता है।

1/सर्वश्रेष्ठ विकल्प का ई-कानून

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