مشاكل السكرتيرة

تُجسّد مسألة السكرتيرة سيناريو يتضمن نظرية التوقف الأمثل ^{[ 1 ] [ 2 ]} ، والتي دُرست على نطاق واسع في مجالات الاحتمالات التطبيقية والإحصاء ونظرية القرار . وتُعرف أيضًا بمسألة الزواج ، ومسألة مهر السلطان ، ومسألة الخاطب المُتطلّب ، ولعبة غوغول ، ومسألة الاختيار الأمثل . ويُعرف حلّها أيضًا بقاعدة 37% . ^{[ 3 ]}

تتمثل الصيغة الأساسية للمشكلة فيما يلي: تخيل مديرًا يرغب في توظيف أفضل سكرتيرة من بين${\displaystyle n}$يتم تقييم المتقدمين لشغل وظيفة معينة. تُجرى مقابلات مع المتقدمين واحدًا تلو الآخر بترتيب عشوائي. يُتخذ القرار بشأن كل متقدم على حدة فور انتهاء المقابلة. بمجرد رفض المتقدم، لا يمكن استدعاؤه مرة أخرى. خلال المقابلة، يحصل المسؤول على معلومات كافية لتقييم المتقدم من بين جميع المتقدمين الذين تمت مقابلتهم حتى الآن، ولكنه يجهل جودة المتقدمين الذين لم تتم مقابلتهم بعد. السؤال المطروح هو: ما هي الاستراتيجية المثلى ( قاعدة التوقف ) لزيادة احتمالية اختيار أفضل متقدم؟ إذا أمكن تأجيل القرار إلى النهاية، فيمكن حل هذه المشكلة باستخدام خوارزمية الاختيار القصوى البسيطة ، وذلك بتتبع القيمة القصوى الحالية (ومن حققها)، ثم اختيار القيمة القصوى الإجمالية في النهاية. تكمن الصعوبة في ضرورة اتخاذ القرار فورًا.

أقصر برهان دقيق معروف حتى الآن هو ما تقدمه خوارزمية الاحتمالات . وهذا يعني أن احتمال الفوز الأمثل يكون دائمًا على الأقل${\displaystyle 1/e}$(حيث e هو أساس اللوغاريتم الطبيعي )، وأن هذا الأخير ينطبق بشكل أعم بكثير. تنص قاعدة التوقف المثلى على رفض الأول دائمًا.${\displaystyle \sim n/e}$يتم إجراء مقابلات مع المتقدمين، ثم يتوقف التقييم عند أول متقدم يكون أفضل من جميع المتقدمين الذين تمت مقابلتهم حتى الآن (أو يستمر حتى آخر متقدم إذا لم يحدث ذلك). تُسمى هذه الاستراتيجية أحيانًا بـ${\displaystyle 1/e}$قاعدة التوقف، لأن احتمال التوقف عند أفضل متقدم باستخدام هذه الاستراتيجية هو بالفعل حوالي${\displaystyle 1/e}$بالنسبة للقيم المتوسطة لـ${\displaystyle n}$أحد أسباب الاهتمام الكبير الذي حظيت به مسألة السكرتيرة هو أن السياسة المثلى لحلها (قاعدة التوقف) بسيطة، إذ تختار أفضل مرشح بنسبة 37% تقريبًا، بغض النظر عن عدد المتقدمين، سواء كان 100 أو 100 مليون. تُعدّ مسألة السكرتيرة معضلة استكشاف واستغلال .

على الرغم من وجود العديد من الاختلافات، إلا أنه يمكن صياغة المشكلة الأساسية على النحو التالي:

• يوجد منصب واحد شاغر.
• يوجد عدد n من المتقدمين للوظيفة، وقيمة n معروفة.
• يمكن تصنيف المتقدمين، إذا تم النظر إليهم جميعًا معًا، من الأفضل إلى الأسوأ بشكل لا لبس فيه.
• يتم إجراء المقابلات مع المتقدمين بالتتابع وبترتيب عشوائي، مع كون كل ترتيب له نفس الاحتمالية.
• مباشرة بعد المقابلة، يتم قبول المتقدم الذي تمت مقابلته أو رفضه، ويكون القرار نهائياً وغير قابل للتراجع.
• لا يمكن اتخاذ قرار قبول أو رفض المتقدم إلا بناءً على الترتيب النسبي للمتقدمين الذين تمت مقابلتهم حتى الآن.
• يهدف الحل العام إلى تحقيق أعلى احتمال لاختيار أفضل متقدم من بين جميع المتقدمين. وهذا يُعادل تعظيم العائد المتوقع، حيث يُعرّف العائد بأنه واحد لأفضل متقدم وصفر لغيره.

يُعرَّف المرشح بأنه المتقدم الذي، عند إجراء المقابلة معه، يكون أفضل من جميع المتقدمين الذين تمت مقابلتهم سابقًا. يُستخدم مصطلح " التجاهل " بمعنى "الرفض فورًا بعد المقابلة". ولأن الهدف من هذه المسألة هو اختيار أفضل متقدم، فسيتم النظر في قبول المرشحين فقط. ويُشير مصطلح "المرشح" في هذا السياق إلى مفهوم السجل في عملية التبديل.

السياسة المثلى لحل هذه المشكلة هي قاعدة التوقف . بموجبها، يرفض القائم بالمقابلة أول r  −  1 متقدمًا (ليكن المتقدم M هو أفضل متقدم من بين هؤلاء المتقدمين r  −  1)، ثم يختار أول متقدم لاحق يكون أفضل من المتقدم M. يمكن إثبات أن الاستراتيجية المثلى تقع ضمن هذه الفئة من الاستراتيجيات. بالنسبة لقيمة قطع اختيارية r ، فإن احتمال اختيار أفضل متقدم هو

${\displaystyle {\begin{aligned}P(r)&=\sum _{i=1}^{n}P\left({\text{تم اختيار المتقدم }}i{\text{)}}\cap {\text{المتقدم }}i{\text{ هو الأفضل}}\right)\\&=\sum _{i=1}^{n}P\left({\text{تم اختيار المتقدم }}i{\text{)}}|{\text{المتقدم }}i{\text{ هو الأفضل}}\right)\cdot P\left({\text{المتقدم }}i{\text{ هو الأفضل}}\right)\\&=\left[\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{الأفضل من الأول }}i-1{\text{ المتقدمين}}\\{\text{في أول }}r-1{\text{ المتقدمين}}\end{array}}\right|{\text{المتقدم }}i{\text{ هو الأفضل}}\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 متقدمًا تم رفضهم. بجعل n تؤول إلى اللانهاية، نكتب${\displaystyle x}$باعتبار (r−1) / n نهايةً ، وباستخدام t لـ (i−1) / n و dt لـ 1/ n ، يمكن تقريب المجموع بالتكامل

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

بأخذ مشتقة P ( x ) بالنسبة إلى${\displaystyle x}$بوضعها مساوية للصفر، وحل المعادلة لإيجاد قيمة x ، نجد أن قيمة x المثلى تساوي 1/ e . وبالتالي، فإن الحد الأمثل يؤول إلى n / e مع ازدياد قيمة n ، ويتم اختيار أفضل متقدم باحتمالية 1/ e .

بالنسبة للقيم الصغيرة لـ n ، يمكن أيضًا الحصول على القيمة المثلى لـ r باستخدام أساليب البرمجة الديناميكية القياسية. يوضح الجدول التالي العتبات المثلى r واحتمالية اختيار البديل الأفضل P لعدة قيم لـ n . ^{[ ملاحظة 1 ]}

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10
${\displaystyle r}$	1	1	2	2	3	3	3	4	4	4
${\displaystyle P}$	1.000	0.500	0.500	0.458	0.433	0.428	0.414	0.410	0.406	0.399

يتقارب احتمال اختيار أفضل مرشح في مسألة السكرتيرة الكلاسيكية نحو${\displaystyle 1/e\approx 0.368}$.

يمكن حل هذه المشكلة والعديد من التعديلات عليها (بما في ذلك إثبات الأمثلية) بطريقة مباشرة باستخدام خوارزمية الاحتمالات ، والتي لها تطبيقات أخرى أيضًا. تشمل التعديلات التي يمكن حلها باستخدام هذه الخوارزمية لمشكلة السكرتيرة: التوافر العشوائي للمتقدمين، وفرضيات أكثر عمومية حول المتقدمين الذين قد يكونون محل اهتمام صانع القرار، وإجراء مقابلات جماعية مع المتقدمين، بالإضافة إلى نماذج معينة لعدد عشوائي من المتقدمين.

إن حل مشكلة السكرتيرة لا يكون ذا معنى إلا إذا كان من المبرر افتراض أن المتقدمين ليس لديهم أي معرفة باستراتيجية القرار المستخدمة، لأن المتقدمين المبكرين ليس لديهم أي فرصة على الإطلاق وقد لا يظهرون بخلاف ذلك.

من أهم عيوب تطبيق حل مشكلة السكرتيرة الكلاسيكية هو عدد المتقدمين${\displaystyle n}$يجب أن تكون هذه المعلومات معروفة مسبقًا، وهو أمر نادر الحدوث. إحدى طرق التغلب على هذه المشكلة هي افتراض أن عدد المتقدمين هو متغير عشوائي.${\displaystyle N}$مع توزيع معروف لـ ${\displaystyle P(N=k)_{k=1,2,\cdots }}$(بريسمان وسونين، 1972). مع ذلك، يُعدّ الحل الأمثل لهذا النموذج أصعب بكثير بشكل عام. علاوة على ذلك، لم يعد احتمال النجاح الأمثل قريبًا من 1/ e ، بل أصبح عادةً أقل. يُمكن فهم ذلك في سياق وجود "ثمن" يُدفع لعدم معرفة عدد المتقدمين. مع ذلك، في هذا النموذج، يكون الثمن باهظًا. اعتمادًا على اختيار توزيع${\displaystyle N}$قد تقترب احتمالية الفوز المثلى من الصفر. وقد أدى البحث عن طرق للتعامل مع هذه المشكلة الجديدة إلى نموذج جديد ينتج عنه ما يسمى بقانون 1/e للاختيار الأمثل.

يرتكز جوهر هذا النموذج على فكرة أن الحياة متسلسلة وأن مشاكل العالم الحقيقي تظهر في الوقت الفعلي. كما أنه من الأسهل تقدير الأوقات التي من المفترض أن تحدث فيها أحداث معينة (مثل وصول المتقدمين للوظائف) بشكل متكرر (إن حدثت بالفعل) من تقدير توزيع عدد الأحداث المحددة التي ستحدث. وقد أدت هذه الفكرة إلى النهج التالي، وهو ما يُعرف بالنهج الموحد (1984):

يُعرَّف النموذج على النحو التالي: يجب اختيار المتقدم خلال فترة زمنية محددة.${\displaystyle [0,T]}$من رقم غير معروف${\displaystyle N}$من بين المتقدمين القابلين للترتيب. الهدف هو تعظيم احتمالية اختيار الأفضل فقط بافتراض أن جميع ترتيبات الوصول ذات الرتب المختلفة متساوية الاحتمالية. لنفترض أن جميع المتقدمين لديهم نفس كثافة وقت الوصول، ولكنها مستقلة عن بعضها البعض.${\displaystyle f}$على${\displaystyle [0,T]}$ودع ${\displaystyle F}$لنرمز إلى دالة توزيع وقت الوصول المقابلة، أي

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

يترك${\displaystyle \tau }$أن يكون على هذا النحو${\displaystyle F(\tau )=1/e.}$ضع في اعتبارك استراتيجية الانتظار ومراقبة جميع المتقدمين حتى الوقت المناسب.${\displaystyle \tau }$ثم اختيار المرشح الأول، إن أمكن، بعد مرور الوقت${\displaystyle \tau }$وهي أفضل من جميع الاستراتيجيات السابقة. إذن، تتميز هذه الاستراتيجية، المسماة استراتيجية 1/e ، بالخصائص التالية:

استراتيجية 1/ e

(i) ينتج عنه للجميع${\displaystyle N}$احتمال نجاح لا يقل عن 1/e،

(ii) هي استراتيجية مثلى من حيث الحد الأدنى والحد الأقصى للمُنتقي الذي لا يعرف${\displaystyle N}$،

(iii) يختار، إذا كان هناك متقدم واحد على الأقل، لا أحد على الإطلاق باحتمالية 1/e بالضبط.

كان قانون 1/e، الذي أثبته ف. توماس بروس عام 1984 ، بمثابة مفاجأة. والسبب هو أنه كان يُعتقد سابقًا أن قيمة تقارب 1/e غير قابلة للتحقيق في نموذج للمجهول.${\displaystyle N}$، في حين أن هذه القيمة 1/e تم تحقيقها الآن كحد أدنى لاحتمالية النجاح، وهذا في نموذج بفرضيات أضعف بكثير يمكن القول (انظر على سبيل المثال Math. Reviews 85:m).

ومع ذلك، توجد العديد من الاستراتيجيات الأخرى التي تحقق (أ) و(ب)، بل وتتفوق عليها في الأداء بشكل واضح على استراتيجية 1/e في الوقت نفسه لجميع${\displaystyle N}$٢. مثال بسيط على ذلك هو الاستراتيجية التي تختار (إن أمكن) أول مرشح هو الأفضل نسبيًا بعد مرور الوقت${\displaystyle \tau }$بشرط أن يكون أحد المتقدمين على الأقل قد وصل قبل هذا الوقت، وإلا يتم اختيار ثاني أفضل مرشح نسبياً بعد انقضاء الوقت (إن أمكن).${\displaystyle \tau }$[ ^{4 ]​}

يُخلط أحيانًا بين قانون 1/e وحل مسألة السكرتيرة الكلاسيكية المذكورة أعلاه نظرًا لتشابه دور العدد 1/e. مع ذلك، فإن هذا الدور في قانون 1/e أكثر عمومية. كما أن النتيجة أقوى، لأنها تنطبق على عدد غير معروف من المتقدمين، ولأن النموذج القائم على توزيع وقت الوصول F أسهل في التعامل معه بالنسبة للتطبيقات.

في مقال "من حل مشكلة السكرتيرة؟" ( فيرغسون ، 1989) ^{[ 1 ]} ، يُزعم أن مشكلة السكرتيرة ظهرت لأول مرة مطبوعة في عمود الألعاب الرياضية لمارتن غاردنر في فبراير 1960 في مجلة ساينتفك أمريكان :

اطلب من شخص ما أن يأخذ أي عدد من قصاصات الورق، ويكتب على كل قصاصة عددًا موجبًا مختلفًا. قد تتراوح الأعداد من أجزاء صغيرة من 1 إلى عدد بحجم غوغول (1 متبوعًا بمئة صفر) أو حتى أكبر. تُقلب هذه القصاصات ووجهها لأسفل وتُخلط على سطح طاولة. تُقلب القصاصات واحدة تلو الأخرى ووجهها لأعلى. الهدف هو التوقف عن التقليب عند الوصول إلى العدد الذي يُخمن أنه الأكبر في السلسلة. لا يمكنك العودة واختيار قصاصة سبق قلبها. إذا قلبت جميع القصاصات، فبالطبع يجب عليك اختيار آخر قصاصة تم قلبها. ^{[ 5 ]}

أشار فيرغسون إلى أن لعبة السكرتيرة ظلت دون حل، باعتبارها لعبة محصلتها صفر بين لاعبين متنافسين. ^{[ 1 ]} في هذه اللعبة:

• أليس، اللاعبة المطلعة، تكتب سراً أرقاماً مميزة على${\displaystyle n}$بطاقات.
• بوب، اللاعب الذي يقوم بالتوقف، يراقب القيم الفعلية ويمكنه التوقف عن قلب البطاقات متى شاء، ويفوز إذا كانت البطاقة الأخيرة التي تم قلبها تحمل الرقم الأقصى الإجمالي.
• يريد بوب أن يخمن الرقم الأقصى بأعلى احتمال ممكن، بينما هدف أليس هو إبقاء هذا الاحتمال منخفضًا قدر الإمكان.

يكمن الاختلاف مع مشكلة السكرتيرة الأساسية في أمرين:

• لا يتعين على أليس كتابة الأرقام بشكل عشوائي ومنتظم. يمكنها كتابتها وفقًا لأي توزيع احتمالي مشترك لخداع بوب.
• يراقب بوب القيم الفعلية المكتوبة على البطاقات، والتي يمكنه استخدامها في إجراءات اتخاذ القرار الخاصة به.

يتناول الجزء المتبقي من المقال مرة أخرى مشكلة السكرتيرة لعدد معروف من المتقدمين.

قام كل من شتاين، وسيل، ورابوبورت (2003) باستخلاص احتمالات النجاح المتوقعة لعدة أساليب استدلالية معقولة نفسياً يمكن استخدامها في مشكلة السكرتيرة. وكانت الأساليب الاستدلالية التي درسوها هي:

• قاعدة القطع (CR): لا تقبل أيًا من المتقدمين الـ y الأوائل ؛ بعد ذلك، اختر أول مرشح يتم مواجهته (أي المتقدم الحاصل على الترتيب النسبي 1). وتُعد هذه القاعدة حالة خاصة من السياسة المثلى لمسألة السكرتير الكلاسيكية حيث y  = r . 
• قاعدة عدّ المرشحين (CCR): يتم اختيار المرشح رقم y الذي تمت مواجهته. تجدر الإشارة إلى أن هذه القاعدة لا تتجاهل بالضرورة أي متقدمين؛ فهي تأخذ في الاعتبار فقط عدد المرشحين الذين تمت ملاحظتهم، وليس مدى تعمق صانع القرار في تسلسل المتقدمين.
• قاعدة المرشح غير المتتالي (SNCR): اختر أول مرشح يتم مواجهته بعد ملاحظة y من غير المرشحين (أي المتقدمين ذوي الرتبة النسبية  >  1).

لكل طريقة استدلالية مُعامل واحد y . يُظهر الشكل (الموضح على اليمين) احتمالات النجاح المتوقعة لكل طريقة استدلالية كدالة لـ y للمسائل التي يكون فيها n  =  80.

قد يبدو العثور على أفضل مرشح هدفًا صارمًا للغاية. يمكن للمرء أن يتصور أن القائم بالمقابلة يفضل توظيف مرشح ذي قيمة أعلى على مرشح ذي قيمة أقل، ولا يقتصر اهتمامه على الحصول على الأفضل فحسب. أي أن القائم بالمقابلة سيستفيد من اختيار مرشح ليس بالضرورة الأفضل، وتزداد هذه الفائدة مع ازدياد قيمة المرشح المختار.

لنمذجة هذه المشكلة، افترض أن${\displaystyle n}$يمتلك المتقدمون قيمًا "حقيقية" عبارة عن متغيرات عشوائية X مُختارة بشكل مستقل ومتطابق من توزيع منتظم على الفترة [0،  1]. على غرار المسألة الكلاسيكية المذكورة أعلاه، يلاحظ المُقابل فقط ما إذا كان كل متقدم هو الأفضل حتى الآن (مرشح)، وعليه قبول أو رفض كل منهم على الفور، ويجب عليه قبول الأخير إذا تم الوصول إليه. (للتوضيح، لا يعرف المُقابل الترتيب النسبي الفعلي لكل متقدم، بل يعرف فقط ما إذا كان ترتيبه النسبي 1). مع ذلك، في هذه الحالة، يُحدد العائد بالقيمة الحقيقية للمتقدم المُختار. على سبيل المثال، إذا اختار مُتقدمًا قيمته الحقيقية 0.8، فسيحصل على 0.8. هدف المُقابل هو تعظيم القيمة المتوقعة للمتقدم المُختار.

بما أن قيم المتقدم هي عينات مستقلة ومتطابقة التوزيع من توزيع منتظم على الفترة [0،  1]، فإن القيمة المتوقعة للمتقدم رقم t، مع الأخذ في الاعتبار ما يلي:${\displaystyle x_{t}=\max \left\{x_{1},x_{2},\ldots ,x_{t}\right\}}$يُعطى بواسطة

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

كما هو الحال في المسألة الكلاسيكية، تُعطى السياسة المثلى بواسطة عتبة، والتي سنرمز لها في هذه المسألة بـ${\displaystyle c}$، وعندها ينبغي على القائم بالمقابلة أن يبدأ بقبول المرشحين. وقد أظهر بيردن أن قيمة c إما${\displaystyle \lfloor {\sqrt {n}}\rfloor }$أو${\displaystyle \lceil {\sqrt {n}}\rceil }$[ ^{8 ] ( في} الواقع، أيهما أقرب إلى${\displaystyle {\sqrt {n}}}$.) وينتج هذا عن حقيقة أنه عند وجود مشكلة مع${\displaystyle n}$المتقدمون، العائد المتوقع لعتبة معينة تعسفية${\displaystyle 1\leq c\leq n}$يكون

${\displaystyle 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}}.}$

التمايز${\displaystyle V_{n}(c)}$بالنسبة إلى c ، نحصل على

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

منذ${\displaystyle \partial ^{\,2}V/\partial c^{\,2}<0}$جميع القيم المسموح بها لـ${\displaystyle c}$، نجد أن${\displaystyle V}$يتم تحقيق أقصى قيمة عند${\displaystyle c={\sqrt {n}}}$بما أن V محدبة في${\displaystyle c}$، يجب أن تكون العتبة المثلى ذات القيمة الصحيحة إما${\displaystyle \lfloor {\sqrt {n}}\rfloor }$أو${\displaystyle \lceil {\sqrt {n}}\rceil }$وبالتالي، بالنسبة لمعظم قيم${\displaystyle n}$سيبدأ القائم بالمقابلة بقبول المتقدمين في وقت أبكر في نسخة العائد الأساسي مقارنةً بالنسخة الكلاسيكية حيث يكون الهدف هو اختيار أفضل متقدم واحد. تجدر الإشارة إلى أن هذه ليست نتيجة تقاربية: فهي تنطبق على جميع${\displaystyle n}$ومن المثير للاهتمام، إذا كان كل واحد من${\displaystyle n}$للسكرتيرات قيمة ثابتة ومميزة عن${\displaystyle 1}$ل${\displaystyle n}$، ثم${\displaystyle V}$يتم تحقيق أقصى قيمة عند${\displaystyle c={\sqrt {n}}-1}$^{[ 9 ]} بالنسبة للتوزيعات المعروفة الأخرى ، يمكن حساب اللعب الأمثل عبر البرمجة الديناميكية.

يفترض شكلٌ أعمّ لهذه المشكلة، طرحه بالي وكريمر (2014) ^{[ 10 ]} ، أنه مع وصول كل متقدم جديد، يلاحظ القائم بالمقابلة ترتيبه بالنسبة لجميع المتقدمين الذين تمت مقابلتهم سابقًا. يتوافق هذا النموذج مع فكرة تعلّم القائم بالمقابلة أثناء استمراره في عملية البحث، وذلك بتجميع مجموعة من البيانات السابقة التي يمكنه استخدامها لتقييم المرشحين الجدد عند وصولهم. من مزايا هذا النموذج، المعروف بنموذج المعلومات الجزئية، إمكانية مقارنة القرارات والنتائج المُتخذة بناءً على معلومات الترتيب النسبي مباشرةً بالقرارات والنتائج المثلى المقابلة لو كان لدى القائم بالمقابلة معلومات كاملة عن قيمة كل متقدم. وقد حُلّت هذه المشكلة، التي تُعرف بمشكلة المعلومات الكاملة، حيث يتم اختيار المتقدمين بشكل مستقل من توزيع معروف، ويسعى القائم بالمقابلة إلى تعظيم القيمة المتوقعة للمتقدم المُختار، في الأصل من قِبل موسر (1956) ^{[ 11 ]} ، وساكاغوتشي (1961) ^{[ 12 ]} ، وكارلين (1962).

توجد عدة صيغ لمسألة السكرتيرة والتي لها أيضًا حلول بسيطة وأنيقة.

درس علماء النفس التجريبيون والاقتصاديون سلوك اتخاذ القرار لدى الأفراد في مواقف معضلة السكرتيرة. ^{[ 19 ]} وقد أظهرت هذه الدراسات، في معظمها، أن الناس يميلون إلى التوقف عن البحث مبكرًا. ويمكن تفسير ذلك، جزئيًا على الأقل، بتكلفة تقييم المرشحين. في الواقع، قد يشير هذا إلى أن الناس لا يبذلون جهدًا كافيًا في البحث عندما يواجهون مشكلات تتضمن بدائل متسلسلة. على سبيل المثال، عند محاولة تحديد محطة الوقود المناسبة على الطريق السريع، قد لا يبحث الناس بما فيه الكفاية قبل التوقف. إذا صحّ ذلك، فسيدفعون على الأرجح سعرًا أعلى للوقود مقارنةً بما لو بحثوا لفترة أطول. وينطبق الأمر نفسه على البحث عن تذاكر الطيران عبر الإنترنت. يُشار أحيانًا إلى البحوث التجريبية حول مشكلات مثل معضلة السكرتيرة باسم بحوث العمليات السلوكية .

على الرغم من وجود مجموعة كبيرة من أبحاث علم الأعصاب حول تكامل المعلومات ، أو تمثيل الاعتقاد، في مهام اتخاذ القرار الإدراكي باستخدام كل من الحيوانات ^{[ 20 ] [ 21 ]} والبشر ^{[ 22 ]} ، إلا أن هناك القليل نسبيًا من المعلومات حول كيفية اتخاذ قرار التوقف عن جمع المعلومات.

درس الباحثون الأسس العصبية لحل مشكلة السكرتيرة لدى متطوعين أصحاء باستخدام التصوير بالرنين المغناطيسي الوظيفي . ^{[ 23 ]} استُخدمت عملية اتخاذ القرار ماركوف ( MDP) لتقييم قيمة الاستمرار في البحث مقابل الالتزام بالخيار الحالي. وقد أظهرت قرارات قبول أو رفض خيار ما نشاطًا في القشرة الجدارية وقشرة الفص الجبهي الظهرية الجانبية ، بالإضافة إلى الجسم المخطط البطني ، والفص الجزيري الأمامي ، والتلفيف الحزامي الأمامي . وبالتالي، فإن مناطق الدماغ التي سبق ربطها بتكامل الأدلة وتمثيل المكافأة تُشفّر تجاوزات العتبة التي تُحفز قرارات الالتزام بخيار ما.

يبدو أن مشكلة السكرتيرة طُرحت عام ١٩٤٩ على يد ميريل إم. فلود ، الذي أطلق عليها اسم مشكلة الخطيبة في محاضرة ألقاها في ذلك العام. وقد أشار إليها عدة مرات خلال خمسينيات القرن العشرين، على سبيل المثال، في محاضرة ألقاها في مؤتمر بجامعة بيردو في ٩ مايو ١٩٥٨، وأصبحت معروفة على نطاق واسع في الأوساط العلمية رغم عدم نشر أي شيء عنها آنذاك. في عام ١٩٥٨، أرسل رسالة إلى ليونارد جيلمان ، مع نسخ منها إلى اثني عشر صديقًا من بينهم صموئيل كارلين وج. روبنز، يشرح فيها برهانًا على الاستراتيجية المثلى، مع ملحق من إعداد ر. باليرمو الذي أثبت أن جميع الاستراتيجيات تهيمن عليها استراتيجية من النوع "رفض المرشح الأول p رفضًا قاطعًا، ثم قبول المرشح التالي الأفضل". ^{[ ٢٤ ]}

يبدو أن أول منشور كان بقلم مارتن غاردنر في مجلة ساينتفك أمريكان ، فبراير 1960. كان قد سمع عنها من جون إتش فوكس الابن، وإل جيرالد مارني، اللذين توصلا بشكل مستقل إلى مسألة مكافئة في عام 1958؛ وأطلقوا عليها اسم "لعبة غوغول ". لم يكن فوكس ومارني يعرفان الحل الأمثل؛ فطلب غاردنر المشورة من ليو موزر ، الذي قدم (بالاشتراك مع جيه آر باوندر) تحليلًا صحيحًا للنشر في المجلة. بعد ذلك بوقت قصير، راسل العديد من علماء الرياضيات غاردنر ليخبروه عن المسألة المكافئة التي سمعوا عنها، والتي يُرجح أن يكون مصدرها جميعًا هو عمل فلوود الأصلي. ^{[ 25 ]}

يعود قانون الاختيار الأفضل 1/ e إلى ف. توماس بروس . ^{[ 26 ]}

يحتوي كتاب فيرغسون على قائمة مراجع شاملة، ويشير إلى أن مشكلة مماثلة (وإن كانت مختلفة) قد تناولها آرثر كايلي عام 1875، بل وحتى يوهانس كيبلر قبل ذلك بكثير، الذي أمضى عامين في دراسة 11 مرشحًا للزواج خلال الفترة 1611-1613 بعد وفاة زوجته الأولى. ^{[ 27 ] [ 28 ]}

يمكن تعميم مشكلة السكرتيرة لتشمل حالة وجود وظائف متعددة ومختلفة. ومرة ​​أخرى، هناك${\displaystyle n}$يتقدم المتقدمون للوظائف بترتيب عشوائي. عند وصول أي مرشح، يكشف عن مجموعة من الأرقام غير السالبة. يحدد كل رقم مؤهله لإحدى الوظائف. لا يقتصر دور المسؤول على اتخاذ قرار قبول المتقدم من عدمه، بل عليه أيضًا، في حال قبوله، تعيينه بشكل دائم في إحدى الوظائف. الهدف هو إيجاد تعيين يحقق أكبر مجموع ممكن من المؤهلات. هذه المسألة مماثلة لإيجاد مطابقة ذات وزن أقصى في رسم بياني ثنائي الأجزاء ذي حواف مرجحة، حيث${\displaystyle n}$تصل عقد أحد الجانبين إلى الإنترنت بترتيب عشوائي. لذا، فهي حالة خاصة من مشكلة المطابقة الثنائية عبر الإنترنت .

من خلال تعميم الخوارزمية الكلاسيكية لمسألة السكرتيرة، من الممكن الحصول على مهمة يكون فيها المجموع المتوقع للمؤهلات مجرد عامل من عوامل${\displaystyle e}$أقل من التخصيص الأمثل (غير المتصل بالإنترنت). ^{[ 29 ]}

• مسألة التخصيص
• خوارزمية الاحتمالات
• التوقف الأمثل
• مشكلة روبنز
• مُرضٍ
• نظرية البحث
• مشكلة الزواج المستقر
• معضلة الاستكشاف والاستغلال

• بيردن، جيه إن (2006). "مسألة سكرتيرة جديدة مع اختيار قائم على الرتبة وعوائد أساسية". مجلة علم النفس الرياضي . 50 : 58-59 . doi : 10.1016/j.jmp.2005.11.003 .
• بيردن، جيه إن؛ مورفي، آر أو؛ رابوبورت، إيه. (2005). "توسيع متعدد السمات لمسألة السكرتيرة: النظرية والتجارب". مجلة علم النفس الرياضي . 49 (5): 410-425 . CiteSeerX 10.1.1.497.6468 . doi : 10.1016/j.jmp.2005.08.002 . S2CID 9186039 .  
• بيردن، ج. نيل؛ رابوبورت، أمنون؛ مورفي، رايان أو. (سبتمبر 2006). "الملاحظة والاختيار المتسلسل مع العوائد المعتمدة على الرتبة: دراسة تجريبية". مجلة علوم الإدارة . 52 (9): 1437-1449 . doi : 10.1287/mnsc.1060.0535 .
• بروس، ف. توماس (يونيو 2000). "اجمع الاحتمالات إلى واحد وتوقف" . حوليات الاحتمالات . 28 (3): 1384-1391 . doi : 10.1214/aop/1019160340 . hdl : 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/182735 .
• بروس، ف. توماس (أكتوبر 2003). "ملاحظة حول حدود نظرية الاحتمالات للتوقف الأمثل" . حوليات الاحتمالات . 31 (4): 1859-1961 . doi : 10.1214/aop/1068646368 . hdl : 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/181669 .
• بروس، ف. توماس (أغسطس 1984). "نهج موحد لفئة من مسائل الاختيار الأمثل مع عدد غير معروف من الخيارات" . حوليات الاحتمالات . 12 (3): 882-889 . doi : 10.1214/aop/1176993237 .
• فلود، ميريل ر. (1958). "إثبات الاستراتيجية المثلى". أوراق مارتن غاردنر، السلسلة 1، الصندوق 5، المجلد 19. رسالة إلى مارتن غاردنر. أرشيف جامعة ستانفورد.
• فريمان، بي آر (1983). "مشكلة السكرتيرة وامتداداتها: مراجعة". المجلة الإحصائية الدولية / Revue Internationale de Statistique . 51 (2): 189-206 . doi : 10.2307/1402748 . JSTOR 1402748 . 
• غاردنر، مارتن (1966). "3". انحرافات رياضية جديدة من مجلة ساينتفك أمريكان . سيمون وشوستر.[يعيد نشر مقاله الأصلي الذي نُشر في فبراير 1960 مع تعليقات إضافية]
• جيردهار، يوجيش؛ دوديك، غريغوري (2009). "أخذ عينات البيانات الأمثل عبر الإنترنت أو كيفية توظيف أفضل السكرتيرات". المؤتمر الكندي لعام 2009 حول رؤية الحاسوب والروبوت . الصفحات 292-298 . CiteSeerX 10.1.1.161.41 . doi : 10.1109/CRV.2009.30 . ISBN   978-1-4244-4211-9. S2CID 2742443 . 
• جيلبرت، ج؛ موستيلر، ف (1966). "التعرف على القيمة القصوى في متتالية". مجلة الجمعية الإحصائية الأمريكية . 61 (313): 35-73 . doi : 10.2307/2283044 . JSTOR 2283044 . 
• غنيدين، أ. (1994). "حل لعبة غوغول" . حوليات الاحتمالات . 22 (3): 1588-1595 . doi : 10.1214/aop/1176988613 .
• غنيدين، أ. (2021). "مسألة الاختيار الأمثل مع وصولات عشوائية: كيفية التغلب على استراتيجية 1/e" . العمليات العشوائية وتطبيقاتها . 145 : 226-240 . doi : 10.1016/j.spa.2021.12.008 . S2CID 245449000 . 
• هيل، تي بي. " معرفة متى تتوقف ". مجلة ساينتست الأمريكية ، المجلد 97، الصفحات 126-133 (2009). (للاطلاع على الترجمة الفرنسية، انظر المقال الرئيسي في عدد يوليو من مجلة بور لا ساينس (2009)).
• كيتيلار، تيموثي؛ تود، بيتر م. (2001). "تأطير أفكارنا: العقلانية البيئية كإجابة علم النفس التطوري على مشكلة الإطار". التحديات المفاهيمية في علم النفس التطوري . دراسات في الأنظمة المعرفية. المجلد  27. الصفحات 179-211 . doi : 10.1007/978-94-010-0618-7_7 . ISBN  978-94-010-3890-4.
• ماتسوي، ت؛ أنو، ك (2016). "الحدود الدنيا لمسألة احتمالات بروس مع التوقفات المتعددة". رياضيات بحوث العمليات . 41 (2): 700-714 . arXiv : 1204.5537 . doi : 10.1287/moor.2015.0748 . S2CID 31778896 . 
• ميلر، جيفري ف. (2001). عقل التزاوج: كيف شكّل الاختيار الجنسي تطور الطبيعة البشرية . دار أنكور للنشر. رقم ISBN 978-0-385-49517-2.
• سارديليس، ديميتريس أ.؛ فالاهاس، ثيودوروس م. (مارس 1999). "اتخاذ القرار: قاعدة ذهبية". المجلة الرياضية الأمريكية الشهرية . 106 (3): 215. doi : 10.2307/2589677 . JSTOR 2589677 . 
• سيل، د.أ.؛ رابوبورت، أ. (1997). "اتخاذ القرارات المتسلسلة مع الرتب النسبية: دراسة تجريبية لـ "مشكلة السكرتيرة"". السلوك التنظيمي وعمليات اتخاذ القرار البشري . 69 (3): 221– 236. doi : 10.1006/obhd.1997.2683 .
• شتاين، دبليو إي؛ سيل، دي إيه؛ رابوبورت، إيه. (2003). "تحليل الحلول الاستدلالية لمسألة الاختيار الأمثل". المجلة الأوروبية لبحوث العمليات . 151 : 140-152 . doi : 10.1016/S0377-2217(02)00601-X .
• فاندرباي، آر جيه (نوفمبر 1980). "الاختيار الأمثل لمجموعة فرعية من مجتمع إحصائي". رياضيات بحوث العمليات . 5 (4): 481-486 . doi : 10.1287/moor.5.4.481 .
• فاندرباي، روبرت ج. (2012). نسخة ما بعد الدكتوراه من مشكلة السكرتيرة (ملف PDF) (تقرير). CiteSeerX 10.1.1.366.1718 . 

• تسلسل OEIS A054404 (عدد البنات اللاتي يجب الانتظار قبل الاختيار في مسألة مهر السلطان مع n من البنات)
• وايسشتاين، إريك دبليو. "مشكلة مهر السلطان" . عالم الرياضيات .
• نيل بيردن. "البحث الأمثل (مسائل السكرتارية)" . مؤرشف من الأصل في 4 يناير 2017.
• كتاب "التوقف الأمثل وتطبيقاته" من تأليف توماس س. فيرغسون