सचिव समस्या: Difference between revisions

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

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

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

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

थॉमस एस. फर्ग्यूसन के अनुसार सचिव समस्या पहली बार छपाई में दिखाई दी जब इसे [[मार्टिन गार्डनर]] ने अपने फरवरी 1960 में [[ अमेरिकी वैज्ञानिक ]]में [[गणितीय खेल स्तंभ]] में चित्रित किया {{r|TomFer89}} यहां बताया गया है कि गार्डनर ने इसे कैसे तैयार किया किसी को कागज की जितनी चाहें उतनी पर्चियां लेने के लिए कहें और प्रत्येक पर्ची पर एक अलग सकारात्मक संख्या लिखें संख्याएँ 1 के छोटे अंशों से लेकर एक गोगोल के आकार की संख्या 1 के बाद सौ शून्य या इससे भी बड़ी हो सकती हैं इन पर्चियों को उल्टा कर दिया जाता है और एक मेज के ऊपर से फेर दिया जाता है एक समय में आप फिसलकर उल्टा कर देते हैं लक्ष्य यह है कि जब आप उस संख्या तक पहुंचें जिसे आप श्रृंखला में सबसे बड़ा मानते हैं तो मुड़ना बंद कर दें आप वापस नहीं जा सकते हैं और पहले से मुड़ी हुई पर्ची नहीं उठा सकते हैं यदि आप सभी पर्चियों को पलट देते हैं तो निश्चित रूप से आपको अंतिम मुड़ी हुई पर्चियों को चुनना चाहिए।{{sfn|Gardner|1966}}

लेख में सचिव समस्या का समाधान किसने किया फर्ग्यूसन ने बताया कि सचिव की समस्या अनसुलझी रही जैसा कि एम. गार्डनर ने कहा था जो दो विरोधी खिलाड़ियों के साथ दो-व्यक्ति शून्य-राशि के खेल के रूप में है {{r|TomFer89}} इस खेल में ऐलिस, सूचित खिलाड़ी, गुप्त रूप से अलग-अलग नंबर लिखता है <math>n</math> पत्ते बॉब, रोकने वाला खिलाड़ी, वास्तविक मूल्यों को देखता है और जब भी वह चाहता है तो कार्ड को बदलना बंद कर सकता है अगर आखिरी कार्ड बदल गया तो जीतना कुल अधिकतम संख्या है बुनियादी सचिव की समस्या से अंतर यह है कि बॉब कार्डों पर लिखे वास्तविक मूल्यों का अवलोकन करता है जिसका उपयोग वह अपनी निर्णय प्रक्रियाओं में कर सकता है सचिव समस्या के कुछ संस्करणों में कार्ड पर संख्या आवेदकों के संख्यात्मक गुणों के अनुरूप होती है संख्याओं का [[संयुक्त संभाव्यता वितरण]] ऐलिस के नियंत्रण में है।

बॉब उच्चतम संभव संभावना के साथ अधिकतम संख्या का अनुमान लगाना चाहता है जबकि ऐलिस का लक्ष्य इस संभावना को यथासंभव कम रखना है ऐलिस के लिए कुछ निश्चित वितरण से स्वतंत्र रूप से संख्याओं का नमूना लेना इष्टतम नहीं है और वह कुछ आश्रित तरीके से यादृच्छिक संख्याओं को चुनकर बेहतर खेल सकती है के लिए <math>n=2</math> ऐलिस की कोई न्यूनतम रणनीति नहीं है जो थॉमस एम. कवर टी के विरोधाभास से निकटता से संबंधित है  <math>n>2</math> खेल में एक समाधान है ऐलिस यादृच्छिक संख्या जो आश्रित यादृच्छिक चर हैं यह इस तरह से चुन सकता है कि बॉब सापेक्ष पदों के आधार पर शास्त्रीय रोक रणनीति का उपयोग करने से बेहतर नहीं खेल सकता।{{sfn|Gnedin|1994}}

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

* कटऑफ नियम पहले y आवेदकों में से किसी को भी स्वीकार न करें इसके बाद पहले सामना करने वाले उम्मीदवार यानी सापेक्ष पद 1 वाला आवेदक का चयन करें इस नियम में एक विशेष स्थान के रूप में शास्त्रीय सचिव समस्या के लिए इष्टतम नीति है जिसके लिए y = r

*उम्मीदवार गणना नियम सीसीआर वाई-वें सामना करने वाले उम्मीदवार का चयन करें ध्यान दें कि यह नियम आवश्यक रूप से किसी भी आवेदक को छोड़ नहीं देता है यह केवल इस बात पर विचार करता है कि कितने उम्मीदवारों का अवलोकन किया गया है यह नहीं कि आवेदक अनुक्रम में निर्णय निर्माता कितना गहरा है।

* लगातार गैर-उम्मीदवार नियम एसएनसीआर वाई गैर-उम्मीदवारों यानी संबंधित पद वाले आवेदक > 1 का अवलोकन करने के बाद सबसे पहले सामना करने वाले उम्मीदवार का चयन करें ।

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

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

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

चूंकि आवेदक के मान 0, 1 पर एक समान वितरण से प्राप्त करता है दिए गए tवें आवेदक का अपेक्षित मूल्य <math>x_{t}=\max\left\{x_1, x_2, \ldots, x_t\right\}</math> द्वारा दिया गया है

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

<math> V_{n}(c)</math> सी के संबंध में एक प्राप्त कर्ता है

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

इस समस्या का एक अधिक सामान्य रूप पाले और क्रेमर (2014) द्वारा पेश किया गया<ref>{{Cite journal|last1=Palley|first1=Asa B.|last2=Kremer|first2=Mirko|date=2014-07-08|title=Sequential Search and Learning from Rank Feedback: Theory and Experimental Evidence|url=https://pubsonline.informs.org/doi/abs/10.1287/mnsc.2014.1902|journal=Management Science|volume=60|issue=10|pages=2525–2542|doi=10.1287/mnsc.2014.1902|issn=0025-1909}}</ref> मानना है कि प्रत्येक नए आवेदक के आने पर साक्षात्कारकर्ता उन सभी आवेदकों के सापेक्ष उनका पद देखता है जो पहले देखे जा चुके हैं यह प्रतिरूप एक साक्षात्कारकर्ता सीखने की धारणा के अनुरूप है क्योंकि वे पिछले डेटा बिंदुओं के एक समूह को जमा करके खोज प्रक्रिया जारी रखते हैं जिसका उपयोग वे नए उम्मीदवारों के आने पर उनका मूल्यांकन करने के लिए कर सकते हैं इस तथाकथित आंशिक-सूचना प्रतिरूप का एक लाभ यह है कि यदि साक्षात्कारकर्ता को प्रत्येक आवेदक के मूल्य के बारे में पूरी जानकारी दी गई थी तो सापेक्ष पद की जानकारी के साथ प्राप्त किए गए निर्णयों और परिणामों की सीधे संबंधित इष्टतम निर्णयों और परिणामों से तुलना की जा सकती है यह पूर्ण-सूचना समस्या जिसमें आवेदकों को एक ज्ञात वितरण से स्वतंत्र रूप से लिया जाता है और साक्षात्कारकर्ता चयनित आवेदक के अपेक्षित मूल्य को अधिकतम करना चाहता है यह मूल रूप से मोजर द्वारा 1956 में सकागुची 1961 में और कॉर्लिन 1962 में हल किया गया था। <ref>{{Cite journal|last=Moser|first=Leo|date=1956|title=केली की समस्या पर|journal=Scripta Math|volume=22|pages=289–292}}</ref>

एक संस्करण दूसरे सर्वश्रेष्ठ को चुनने की इच्छा के साथ सर्वश्रेष्ठ चुनने की इच्छा को प्रतिस्थापित करता है <ref name=NonExtRose>{{cite journal |last1=Rose |first1=John S. |year=1982 |title=एक यादृच्छिक अनुक्रम से गैर-अत्यधिक उम्मीदवारों का चयन|journal=J. Optim. Theory Appl.|doi=10.1007/BF00934083 |pages=207–219|volume=38|issue=2 |s2cid=121339045 |issn=0022-3239}}</ref><ref name=AthSza>{{cite journal |last1=Szajowski |first1=Krzysztof |year=1982 |title=एथ रैंक के साथ किसी वस्तु का इष्टतम विकल्प|journal=Matematyka Stosowana|series=Annales Societatis Mathematicae Polonae, Series III|doi=10.14708/ma.v10i19.1533 |pages=51–65|volume=10|number=19|issn=0137-2890}}</ref><ref name=postdoc>{{cite journal |last1=Vanderbei |first1=Robert J. |author-link=Robert J. Vanderbei |year=2021 |title=सचिव समस्या का पोस्टडॉक संस्करण|journal=Mathematica Applicanda|series=Annales Societatis Mathematicae Polonae, Series III|url=https://wydawnictwa.ptm.org.pl/index.php/matematyka-stosowana/article/view/7076 |pages=3–13|volume=49|number=1|issn=2299-4009|date=2021-06-21 |doi=10.14708/ma.v49i1.7076 }}</ref> रॉबर्ट जे वेंडरबी ने इसे पोस्ट डॉक समस्या कहते हुए तर्क दिया कि सबसे अच्छा समस्या के लिए समान संख्या में आवेदकों के लिए सफलता की संभावना ठीक है <math> \frac{0.25n^2}{n(n-1)} </math>. यह प्रायिकता 1/4 हो जाती है क्योंकि n अनंत की ओर जाता है जो इस तथ्य को दर्शाता है कि दूसरे-सर्वश्रेष्ठ की तुलना में सर्वश्रेष्ठ को चुनना आसान है।

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

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

एक खिलाड़ी की अनुमति है <math>r</math> विकल्प और वह जीतता है यदि कोई विकल्प सबसे अच्छा है {{harvnb}} गिलबर्ट और मोस्टेलर ने 1966 में दिखाया कि एक इष्टतम रणनीति एक दहलीज रणनीति कटऑफ रणनीति द्वारा दी गई है एक इष्टतम रणनीति संख्याओं के समूह द्वारा परिभाषित रणनीतियों की श्रेणी से संबंधित है <math> (a_1, a_2, ... , a_r)</math>, जहॉं <math> a_1<a_2< \cdots <a_r </math>. पहली पसंद के साथ शुरू होने वाले पहले उम्मीदवारों पर प्रयोग किया जाना है <math>a_1</math>वें आवेदक और एक बार पहली पसंद का उपयोग करने के बाद दूसरी पसंद का उपयोग पहले उम्मीदवार पर किया जाना है <math>a_2</math>वें आवेदक