सचिव समस्या

File:Secretary problem graphs.svg

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 }$