مسئله منشی

در مسئله منشی مشکل، پیدا کردن نقطهٔ بهینه بین میزان اطلاعات دریافت شده و لحظهٔ مناسب برای استفاده از اطلاعات است.
در اواخر دهه ۱۹۵۰ و اوایل دهه ۱۹۶۰ مسئله ای ظاهر شد که تا حدی تفریحی بود که به مسئله منشی یا ازدواج مشهور است.
این مسئله برای نخستین بار در ستون بازی های ریاضی در یک مجله آمریکایی مطرح شد.
بیان مسئله آسان و راه حل آن قابل توجه است. میان آمار دانان و احتمال دانان چندین نفر از جمله لیندلی، داینکین، [ ۱] چو، موگریتی، روبینز، ساموئلز، گیلبرت و موستلر[ ۲] این مسئله را اخذ کردند و توسعه دادند. بعد از آن مسئله منشی فراگیر و عمومی تر شد که اکنون می توان به آن عنوان یک گرایش درسی بین ریاضیات، احتمال و بهینه سازی داد.
شکل استاندارد مسئله منشی به اینگونه است که N نفر برای منشی گری تقاضا می دهند و به طور تصادفی مرتب و یکی پس از دیگری مصاحبه می شوند. مصاحبه کننده در هر لحظه اطلاعات متقاضی های قبلی و متقاضی فعلی را دارد و باید در همان لحظه تصمیم بر انتخاب یا رد مصاحبه شونده بگیرد.
مصاحبه کننده امکان انتخاب کاندیدی که رد کرده است را ندارد و مصاحبه تا آن جایی ادامه می یابد که بهترین منشی را انتخاب کند. هدف این مسئله بالا بردن احتمال انتخاب بهترین متقاضی است.
بیان مسئله منشی بسیار متنوع است امّا ساده ترین شکل آن به شرح زیر است:
• تنها یک نفر برای موقعیت منشی نیاز است.
• تعداد متقاضیان مشخص و برابر N {\displaystyle N} است.
• متقاضیان که به شکل تصادفی مرتب شده اند، به ترتیب مصاحبه می شوند.
• وضعیت متقاضیان بدین گونه است که می توان آن ها را از بدترین به بهترین رده بندی کرد و تصمیم گیری در هر مرحله بر مبنای رده بندی متقاضیان قبلی است که رد شده اند.
• متقاضی که رد شده است دوباره فراخوانده نمی شود.
• مصاحبه کننده تنها در حالتی که بهترین منشی را انتخاب کند راضی می شود.
سیاست بهینه برای این مسئله، قانون توقف است؛ بنابراین مصاحبه کننده ، r − 1 نفر اولِ متقاضیان را رد می کند ( در حالی که متقاضی M ام بهترین بین r − 1 نفری باشد که رد شده اند ) و پس از آن هر متقاضی ای که بهتر از متقاضی M ام بود را انتخاب می کند. احتمال انتخاب بهترین منشی به شکل زیر است:
متقاضی i ام انتخاب شود A :
متقاضی i ام بهترین باشد B :