सचिव समस्या

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/सर्वश्रेष्ठ विकल्प का ई-कानून

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

मॉडल को इस प्रकार परिभाषित किया गया है: एक आवेदक को कुछ समय अंतराल पर चुना जाना चाहिए $[0,T]$ किसी अनजान नंबर से $N$ रैंक करने योग्य आवेदकों की। लक्ष्य इस परिकल्पना के तहत केवल सर्वश्रेष्ठ का चयन करने की संभावना को अधिकतम करना है कि विभिन्न रैंकों के सभी आगमन ऑर्डर समान रूप से होने की संभावना है। मान लीजिए कि सभी आवेदकों का आगमन समय घनत्व समान है, लेकिन एक-दूसरे से स्वतंत्र है $f$ पर $[0,T]$ और जाने $F$ इसी आगमन समय वितरण फ़ंक्शन को निरूपित करें, अर्थात

$F(t)=\int _{0}^{t}f(s)ds$, $\,0\leq t\leq T$.

होने देना $\tau$ ऐसा हो कि $F(\tau )=1/e.$ सभी आवेदकों को समय-समय पर प्रतीक्षा करने और निरीक्षण करने की रणनीति पर विचार करें $\tau$ और यदि संभव हो तो समय के बाद पहले उम्मीदवार का चयन करना $\tau$ जो पिछले सभी से बेहतर है। फिर इस रणनीति, जिसे 1/ई-रणनीति कहा जाता है, में निम्नलिखित गुण हैं:

1/ई-रणनीति

(i) सभी के लिए पैदावार $N$ कम से कम 1/e की सफलता की संभावना,

(ii) चयनकर्ता के लिए एक न्यूनतम-इष्टतम रणनीति है जो नहीं जानता है $N$,

(iii) चयन करता है, यदि कम से कम एक आवेदक है, बिल्कुल 1/e संभावना के साथ कोई नहीं।

एफ. थॉमस ब्रस द्वारा 1984 में सिद्ध किया गया पहला/ई-कानून एक आश्चर्य के रूप में सामने आया। कारण यह था कि अज्ञात के लिए एक मॉडल में पहुंच से बाहर होने से पहले लगभग 1/e के मान पर विचार किया गया था $N$, जबकि यह मान 1/e अब सफलता की संभावना के लिए एक निचली सीमा के रूप में प्राप्त किया गया था, और यह यकीनन बहुत कमजोर परिकल्पनाओं वाले मॉडल में है (उदाहरण के लिए गणित देखें। समीक्षाएं 85:m)।

हालाँकि, कई अन्य रणनीतियाँ हैं जो (i) और (ii) प्राप्त करती हैं और, इसके अलावा, 1/ई-रणनीति की तुलना में सख्ती से बेहतर प्रदर्शन करती हैं। एक साथ सभी के लिए $N$> 2। एक सरल उदाहरण वह रणनीति है जो समय के बाद पहले अपेक्षाकृत सर्वश्रेष्ठ उम्मीदवार का चयन करती है (यदि संभव हो)। $\tau$ बशर्ते कि कम से कम एक आवेदक इस समय से पहले पहुंचे, और अन्यथा समय के बाद दूसरे अपेक्षाकृत सर्वश्रेष्ठ उम्मीदवार का चयन करें (यदि संभव हो)। $\tau$.

संख्या 1/ई की समान भूमिका के कारण 1/ई-कानून कभी-कभी ऊपर वर्णित शास्त्रीय सचिव समस्या के समाधान के साथ भ्रमित हो जाता है। हालांकि, 1/ई-कानून में, यह भूमिका अधिक सामान्य है। परिणाम भी मजबूत है, क्योंकि यह अज्ञात संख्या में आवेदकों के लिए है और चूंकि आगमन समय वितरण एफ पर आधारित मॉडल अनुप्रयोगों के लिए अधिक ट्रैक्टेबल है।

गोगोल का खेल

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

लेख में सचिव समस्या का समाधान किसने किया? फर्ग्यूसन ने बताया कि सेक्रेटरी की समस्या अनसुलझी रही, जैसा कि एम. गार्डनर ने कहा था, जो दो विरोधी खिलाड़ियों के साथ दो-व्यक्ति शून्य-राशि के खेल के रूप में है। इस खेल में ऐलिस, सूचित खिलाड़ी, गुप्त रूप से अलग-अलग नंबर लिखता है $n$ पत्ते। बॉब, रोकने वाला खिलाड़ी, वास्तविक मूल्यों को देखता है और जब भी वह चाहता है तो कार्ड को बदलना बंद कर सकता है, अगर आखिरी कार्ड बदल गया तो जीतना कुल अधिकतम संख्या है। बुनियादी सचिव की समस्या से अंतर यह है कि बॉब कार्डों पर लिखे वास्तविक मूल्यों का अवलोकन करता है, जिसका उपयोग वह अपनी निर्णय प्रक्रियाओं में कर सकता है। सचिव समस्या के कुछ संस्करणों में कार्ड पर संख्या आवेदकों के संख्यात्मक गुणों के अनुरूप होती है। संख्याओं का संयुक्त संभाव्यता वितरण ऐलिस के नियंत्रण में है।

बॉब उच्चतम संभव संभावना के साथ अधिकतम संख्या का अनुमान लगाना चाहता है, जबकि ऐलिस का लक्ष्य इस संभावना को यथासंभव कम रखना है। ऐलिस के लिए कुछ निश्चित वितरण से स्वतंत्र रूप से संख्याओं का नमूना लेना इष्टतम नहीं है, और वह कुछ आश्रित तरीके से यादृच्छिक संख्याओं को चुनकर बेहतर खेल सकती है। के लिए $n=2$ ऐलिस की कोई न्यूनतम रणनीति नहीं है, जो थॉमस एम. कवर|टी के विरोधाभास से निकटता से संबंधित है। ढकना। लेकिन के लिए $n>2$ खेल में एक समाधान है: ऐलिस यादृच्छिक संख्या (जो आश्रित यादृच्छिक चर हैं) को इस तरह से चुन सकता है कि बॉब सापेक्ष रैंकों के आधार पर शास्त्रीय रोक रणनीति का उपयोग करने से बेहतर नहीं खेल सकता।

अनुमानित प्रदर्शन

शेष लेख आवेदकों की ज्ञात संख्या के लिए फिर से सचिव समस्या से संबंधित है।

तीन अनुमानों के लिए अपेक्षित सफलता की संभावनाएं।

Stein, Seale & Rapoport 2003 ने कई मनोवैज्ञानिक रूप से प्रशंसनीय अनुमानों के लिए अपेक्षित सफलता की संभावनाएँ प्राप्त कीं जिन्हें सचिव समस्या में नियोजित किया जा सकता है। उन्होंने जिन ह्यूरिस्टिक्स की जांच की वे थे:

• कटऑफ नियम (CR): पहले y आवेदकों में से किसी को भी स्वीकार न करें; इसके बाद, पहले सामना करने वाले उम्मीदवार (यानी, सापेक्ष रैंक 1 वाला आवेदक) का चयन करें। इस नियम में एक विशेष मामले के रूप में शास्त्रीय सचिव समस्या के लिए इष्टतम नीति है जिसके लिए y = r।
• उम्मीदवार गणना नियम (सीसीआर): वाई-वें सामना करने वाले उम्मीदवार का चयन करें। ध्यान दें कि यह नियम आवश्यक रूप से किसी भी आवेदक को छोड़ नहीं देता है; यह केवल इस बात पर विचार करता है कि कितने उम्मीदवारों का अवलोकन किया गया है, यह नहीं कि आवेदक अनुक्रम में निर्णय निर्माता कितना गहरा है।
• लगातार गैर-उम्मीदवार नियम (एसएनसीआर): वाई गैर-उम्मीदवारों (यानी, संबंधित रैंक वाले आवेदक > 1) का अवलोकन करने के बाद सबसे पहले सामना करने वाले उम्मीदवार का चयन करें।

प्रत्येक अनुमानी का एक एकल पैरामीटर y होता है। आंकड़ा (दाईं ओर दिखाया गया है) n = 80 के साथ समस्याओं के लिए y के एक समारोह के रूप में प्रत्येक अनुमानी के लिए अपेक्षित सफलता की संभावनाएं प्रदर्शित करता है।

कार्डिनल पेऑफ वेरिएंट

एकल सर्वश्रेष्ठ आवेदक ढूँढना एक सख्त उद्देश्य की तरह लग सकता है। कोई कल्पना कर सकता है कि साक्षात्कारकर्ता एक कम-मूल्यवान आवेदक की तुलना में एक उच्च-मूल्यवान आवेदक को नियुक्त करेगा, और न केवल सर्वश्रेष्ठ प्राप्त करने के लिए चिंतित होगा। अर्थात्, साक्षात्कारकर्ता एक आवेदक का चयन करने से कुछ मूल्य प्राप्त करेगा जो आवश्यक रूप से सर्वोत्तम नहीं है, और व्युत्पन्न मूल्य चयनित के मूल्य के साथ बढ़ता है।

इस समस्या को मॉडल करने के लिए, मान लीजिए कि $n$ आवेदकों के पास वास्तविक मूल्य हैं जो यादृच्छिक चर एक्स तैयार i.i.d हैं। [0, 1] पर एक समान वितरण (निरंतर) से। ऊपर वर्णित शास्त्रीय समस्या के समान, साक्षात्कारकर्ता केवल यह देखता है कि क्या प्रत्येक आवेदक अब तक का सबसे अच्छा है (एक उम्मीदवार), प्रत्येक को मौके पर ही स्वीकार या अस्वीकार कर देना चाहिए, और यदि वह पहुंच जाता है तो अंतिम को स्वीकार करना चाहिए। (स्पष्ट होने के लिए, साक्षात्कारकर्ता प्रत्येक आवेदक की वास्तविक सापेक्ष रैंक नहीं सीखता है। वह केवल यह सीखता है कि आवेदक की सापेक्ष रैंक 1 है या नहीं।) हालांकि, इस संस्करण में भुगतान चयनित आवेदक के सही मूल्य द्वारा दिया गया है। उदाहरण के लिए, यदि वह एक आवेदक का चयन करता है जिसका सही मूल्य 0.8 है, तो वह 0.8 कमाएगा। साक्षात्कारकर्ता का उद्देश्य चयनित आवेदक के अपेक्षित मूल्य को अधिकतम करना है।

चूंकि आवेदक के मान i.i.d. [0, 1] पर एक समान वितरण से प्राप्त करता है, दिए गए tवें आवेदक का अपेक्षित मूल्य $x_{t}=\max \left\{x_{1},x_{2},\ldots ,x_{t}\right\}$ द्वारा दिया गया है

$E_{t}=E\left(X_{t}|I_{t}=1\right)={\frac {t}{t+1}}.$

शास्त्रीय समस्या के रूप में, इष्टतम नीति एक दहलीज द्वारा दी गई है, जिसे इस समस्या के लिए हम निरूपित करेंगे $c$, जिस पर साक्षात्कारकर्ता को उम्मीदवारों को स्वीकार करना शुरू कर देना चाहिए। बेयरडेन ने दिखाया कि सी या तो है $\lfloor {\sqrt {n}}\rfloor$ या $\lceil {\sqrt {n}}\rceil$. (वास्तव में, जो भी सबसे करीब है ${\sqrt {n}}$।) यह इस तथ्य से अनुसरण करता है कि एक समस्या दी गई है $n$ आवेदकों, कुछ मनमाने ढंग से सीमा के लिए अपेक्षित अदायगी $1\leq c\leq n$ है

$V_{n}(c)=\sum _{t=c}^{n-1}\left[\prod _{s=c}^{t-1}\left({\frac {s-1}{s}}\right)\right]\left({\frac {1}{t+1}}\right)+\left[\prod _{s=c}^{n-1}\left({\frac {s-1}{s}}\right)\right]{\frac {1}{2}}={\frac {2cn-{c}^{2}+c-n}{2cn}}.$

फर्क $V_{n}(c)$ सी के संबंध में, एक प्राप्त करता है

${\frac {\partial V}{\partial c}}={\frac {-{c}^{\,2}+n}{2{c}^{\,2}n}}.$

फ़ाइल: RelativeRankLearning2.pdf|thumb|आंशिक-सूचना अनुक्रमिक खोज प्रतिमान में सीखना। संख्या खोज में विभिन्न बिंदुओं पर उनके सापेक्ष रैंक (अब तक देखे गए कुल आवेदकों में से) के आधार पर आवेदकों के अपेक्षित मूल्यों को प्रदर्शित करती है। उम्मीदों की गणना मामले के आधार पर की जाती है जब उनके मान समान रूप से 0 और 1 के बीच वितरित किए जाते हैं। सापेक्ष रैंक की जानकारी साक्षात्कारकर्ता को आवेदकों का अधिक बारीकी से मूल्यांकन करने की अनुमति देती है क्योंकि वे उनकी तुलना करने के लिए अधिक डेटा बिंदु जमा करते हैं। तब से $\partial ^{\,2}V/\partial c^{\,2}<0$ के सभी अनुमेय मूल्यों के लिए $c$, हम पाते हैं $V$ पर अधिकतम होता है $c={\sqrt {n}}$. चूँकि V उत्तल है $c$, इष्टतम पूर्णांक-मान थ्रेशोल्ड या तो होना चाहिए $\lfloor {\sqrt {n}}\rfloor$ या $\lceil {\sqrt {n}}\rceil$. इस प्रकार, के अधिकांश मूल्यों के लिए $n$ साक्षात्कारकर्ता शास्त्रीय संस्करण की तुलना में कार्डिनल पेऑफ संस्करण में जल्द ही आवेदकों को स्वीकार करना शुरू कर देगा, जहां उद्देश्य एकल सर्वश्रेष्ठ आवेदक का चयन करना है। ध्यान दें कि यह एक स्पर्शोन्मुख परिणाम नहीं है: यह सभी के लिए है $n$. हालांकि, ज्ञात वितरण से अपेक्षित मूल्य को अधिकतम करने के लिए यह इष्टतम नीति नहीं है। ज्ञात वितरण के मामले में, गतिशील प्रोग्रामिंग के माध्यम से इष्टतम खेल की गणना की जा सकती है।

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

अन्य संशोधन

सचिव समस्या के कई रूप हैं जिनका सरल और सुरुचिपूर्ण समाधान भी है।

एक संस्करण दूसरे सर्वश्रेष्ठ को चुनने की इच्छा के साथ सर्वश्रेष्ठ चुनने की इच्छा को प्रतिस्थापित करता है। रॉबर्ट जे। वेंडरबी ने इसे पोस्टडॉक समस्या कहते हुए तर्क दिया कि सबसे अच्छा हार्वर्ड जाएगा। इस समस्या के लिए, समान संख्या में आवेदकों के लिए सफलता की संभावना ठीक है ${\frac {0.25n^{2}}{n(n-1)}}$. यह प्रायिकता 1/4 हो जाती है क्योंकि n अनंत की ओर जाता है जो इस तथ्य को दर्शाता है कि दूसरे-सर्वश्रेष्ठ की तुलना में सर्वश्रेष्ठ को चुनना आसान है।

दूसरे संस्करण के लिए, चयनों की संख्या एक से अधिक होने के लिए निर्दिष्ट है। दूसरे शब्दों में, साक्षात्कारकर्ता सिर्फ एक सचिव को नहीं बल्कि भर्ती कर रहा है बल्कि, कहते हैं, एक आवेदक पूल से छात्रों की एक कक्षा को स्वीकार करना। इस धारणा के तहत कि सभी चयनित उम्मीदवारों को अगर और केवल तभी सफलता मिलती है सभी गैर-चयनित उम्मीदवारों से बेहतर हैं, यह फिर से एक समस्या है जिसे हल किया जा सकता है। में दिखाया गया था Vanderbei 1980 कि जब n सम है और ठीक आधे उम्मीदवारों का चयन करने की इच्छा है, तो इष्टतम रणनीति की सफलता की संभावना पैदा होती है ${\frac {1}{n/2+1}}$.

एक अन्य संस्करण सर्वश्रेष्ठ का चयन करने का है $k$ सचिव पूल से बाहर $n$, फिर से एक ऑनलाइन एल्गोरिथम में। यह क्लासिक एक और कटऑफ दहलीज से संबंधित रणनीति की ओर जाता है${\frac {0.25n^{2}}{n(n-1)}}$ जिसके लिए शास्त्रीय समस्या एक विशेष मामला है।

बहुविकल्पी समस्या

एक खिलाड़ी की अनुमति है $r$ विकल्प, और वह जीतता है यदि कोई विकल्प सबसे अच्छा है। Gilbert & Mosteller 1966 ने दिखाया कि एक इष्टतम रणनीति एक दहलीज रणनीति (कटऑफ रणनीति) द्वारा दी गई है। एक इष्टतम रणनीति थ्रेसहोल्ड संख्याओं के सेट द्वारा परिभाषित रणनीतियों की श्रेणी से संबंधित है $(a_{1},a_{2},...,a_{r})$, कहाँ $a_{1}<a_{2}<\cdots <a_{r}$. पहली पसंद के साथ शुरू होने वाले पहले उम्मीदवारों पर इस्तेमाल किया जाना है $a_{1}$वें आवेदक, और एक बार पहली पसंद का उपयोग करने के बाद, दूसरी पसंद का उपयोग पहले उम्मीदवार पर किया जाना है $a_{2}$वें आवेदक, और इसी तरह।

गिल्बर्ट और मोस्टेलर ने दिखाया $\left({\frac {a_{1}}{n}},{\frac {a_{2}}{n}},{\frac {a_{3}}{n}},{\frac {a_{4}}{n}}\right)\rightarrow \left(e^{-1},e^{-{\frac {3}{2}}},e^{-{\frac {47}{24}}},e^{-{\frac {2761}{1152}}}\right)(n\rightarrow \infty )$. आगे के मामलों के लिए कि $r=5,6,...,10$, देखना Matsui & Ano 2016 (उदाहरण के लिए ${\frac {a_{5}}{n}}\rightarrow e^{-{\frac {4162637}{1474560}}}$).

कब $r=2$, जीत की संभावना अभिसरित होती है $e^{-1}+e^{-{\frac {3}{2}}}(n\rightarrow \infty )$. Matsui & Ano 2016 ने दिखाया कि किसी भी सकारात्मक पूर्णांक के लिए $r$, जीत की संभावना (का $r$ चॉइस सेक्रेटरी प्रॉब्लम) में परिवर्तित हो जाता है $p_{1}+p_{2}+\cdots +p_{r}$ कहाँ $p_{i}=\lim _{n\rightarrow \infty }{\frac {a_{i}}{n}}$. इस प्रकार, जीत की संभावना परिवर्तित हो जाती है $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}$ और $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}$ कब $r=3,4$ क्रमश।

प्रायोगिक अध्ययन

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

तंत्रिका संबंध

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

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

इतिहास

सेक्रेटरी प्रॉब्लम स्पष्ट रूप से 1949 में मेरिल एम. फ्लड द्वारा पेश की गई थी, जिन्होंने उस वर्ष अपने एक व्याख्यान में इसे मंगेतर समस्या कहा था। 1950 के दशक के दौरान उन्होंने कई बार इसका उल्लेख किया, उदाहरण के लिए, 9 मई 1958 को पर्ड्यू विश्वविद्यालय में एक सम्मेलन वार्ता में, और यह अंततः लोककथाओं में व्यापक रूप से जाना जाने लगा, हालांकि उस समय कुछ भी प्रकाशित नहीं हुआ था। 1958 में उन्होंने लियोनार्ड गिलमैन को एक पत्र भेजा, जिसकी प्रतियां सैमुअल कार्लिन और जे. रॉबिंस सहित एक दर्जन दोस्तों को भेजी गईं, जिसमें आर. पलेर्मो द्वारा एक परिशिष्ट के साथ इष्टतम रणनीति के प्रमाण की रूपरेखा दी गई, जिसने साबित किया कि सभी रणनीतियों में एक रणनीति का प्रभुत्व है। फॉर्म पहले पी को बिना शर्त खारिज कर देता है, फिर अगले उम्मीदवार को स्वीकार करता है जो बेहतर है।

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

सर्वोत्तम पसंद का 1/ई-कानून एफ. थॉमस ब्रस के कारण है।

फर्ग्यूसन की एक व्यापक ग्रंथ सूची है और बताते हैं कि एक समान (लेकिन अलग) समस्या पर 1875 में आर्थर केली और यहां तक ​​​​कि जोहान्स केपलर # दूसरी शादी से बहुत पहले विचार किया गया था।

मिश्रित सामान्यीकरण

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

सेक्रेटरी प्रॉब्लम के लिए क्लासिक एल्गोरिद्म के सामान्यीकरण से, एक असाइनमेंट प्राप्त करना संभव है जहां योग्यता का अपेक्षित योग केवल एक कारक है $e$ एक इष्टतम (ऑफ़लाइन) असाइनमेंट से कम।

यह भी देखें

• असाइनमेंट की समस्या
• ऑड्स एल्गोरिथम
• इष्टतम रोक
• रॉबिन्स की समस्या
• खोज सिद्धांत
• स्थिर विवाह की समस्या

संदर्भ

• Bearden, J.N. (2006). "A new secretary problem with rank-based selection and cardinal payoffs". Journal of Mathematical Psychology. 50: 58–9. doi:10.1016/j.jmp.2005.11.003.
• Bearden, J.N.; Murphy, R.O.; Rapoport, A. (2005). "A multi-attribute extension of the secretary problem: Theory and experiments". Journal of Mathematical Psychology. 49 (5): 410–425. CiteSeerX 10.1.1.497.6468. doi:10.1016/j.jmp.2005.08.002. S2CID 9186039.
• Bearden, J. Neil; Rapoport, Amnon; Murphy, Ryan O. (September 2006). "Sequential Observation and Selection with Rank-Dependent Payoffs: An Experimental Study". Management Science. 52 (9): 1437–1449. doi:10.1287/mnsc.1060.0535.
• Bruss, F. Thomas (June 2000). "Sum the odds to one and stop". The Annals of Probability. 28 (3): 1384–1391. doi:10.1214/aop/1019160340.
• Bruss, F. Thomas (October 2003). "A note on bounds for the odds theorem of optimal stopping". The Annals of Probability. 31 (4): 1859–1961. doi:10.1214/aop/1068646368.
• Bruss, F. Thomas (August 1984). "A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options". The Annals of Probability. 12 (3): 882–889. doi:10.1214/aop/1176993237.
• Flood, Merrill R. (1958). "Proof of the optimum strategy". Letter to Martin Gardner. Martin Gardner papers series 1, box 5, folder 19: Stanford University Archives.{{cite press release}}: CS1 maint: location (link)
• Freeman, P.R. (1983). "The secretary problem and its extensions: A review". International Statistical Review / Revue Internationale de Statistique. 51 (2): 189–206. doi:10.2307/1402748. JSTOR 1402748.
• Gardner, Martin (1966). "3". New Mathematical Diversions from Scientific American. Simon and Schuster. [reprints his original column published in February 1960 with additional comments]
• Girdhar, Yogesh; Dudek, Gregory (2009). "Optimal Online Data Sampling or How to Hire the Best Secretaries". 2009 Canadian Conference on Computer and Robot Vision. pp. 292–298. CiteSeerX 10.1.1.161.41. doi:10.1109/CRV.2009.30. ISBN 978-1-4244-4211-9. S2CID 2742443.
• Gilbert, J; Mosteller, F (1966). "Recognizing the Maximum of a Sequence". Journal of the American Statistical Association. 61 (313): 35–73. doi:10.2307/2283044. JSTOR 2283044.
• Gnedin, A. (1994). "A solution to the game of Googol". Annals of Probability. 22 (3): 1588–1595. doi:10.1214/aop/1176988613.
• Gnedin, A. (2021). "The best choice problem with random arrivals: How to beat the 1/e-strategy". Stochastic Processes and Their Applications. 145: 226–240. doi:10.1016/j.spa.2021.12.008. S2CID 245449000.
• Hill, T.P. "Knowing When to Stop". American Scientist, Vol. 97, 126-133 (2009). (For French translation, see cover story in the July issue of Pour la Science (2009))
• Ketelaar, Timothy; Todd, Peter M. (2001). "Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem". Conceptual Challenges in Evolutionary Psychology. Studies in Cognitive Systems. Vol. 27. pp. 179–211. doi:10.1007/978-94-010-0618-7_7. ISBN 978-94-010-3890-4.
• Matsui, T; Ano, K (2016). "Lower bounds for Bruss' odds problem with multiple stoppings". Mathematics of Operations Research. 41 (2): 700–714. arXiv:1204.5537. doi:10.1287/moor.2015.0748. S2CID 31778896.
• Miller, Geoffrey F. (2001). The mating mind: how sexual choice shaped the evolution of human nature. Anchor Books. ISBN 978-0-385-49517-2.
• Sardelis, Dimitris A.; Valahas, Theodoros M. (March 1999). "Decision Making: A Golden Rule". The American Mathematical Monthly. 106 (3): 215. doi:10.2307/2589677. JSTOR 2589677.
• Seale, D.A.; Rapoport, A. (1997). "Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem'". Organizational Behavior and Human Decision Processes. 69 (3): 221–236. doi:10.1006/obhd.1997.2683.
• Stein, W.E.; Seale, D.A.; Rapoport, A. (2003). "Analysis of heuristic solutions to the best choice problem". European Journal of Operational Research. 151: 140–152. doi:10.1016/S0377-2217(02)00601-X.
• Vanderbei, R. J. (November 1980). "The Optimal Choice of a Subset of a Population". Mathematics of Operations Research. 5 (4): 481–486. doi:10.1287/moor.5.4.481.
• Vanderbei, Robert J. (2012). "The postdoc variant of the secretary problem" (PDF). CiteSeerX 10.1.1.366.1718. {{cite journal}}: Cite journal requires |journal= (help)

बाहरी संबंध

• OEIS sequence A054404 (Number of daughters to wait before picking in sultan's dowry problem with n daughters)
• Weisstein, Eric W. "Sultan's Dowry Problem". MathWorld.
• Neil Bearden. "Optimal Search (Secretary Problems)". Archived from the original on 4 January 2017.
• Optimal Stopping and Applications book by Thomas S. Ferguson