Задача про перебірливу наречену, або проблема зупинки вибору — демонстрація застосування теорії оптимальної зупинки For French translation, see cover story in the July issue of Pour la Science (2009)., яка широко вивчається в галузі , статистики та теорії прийняття рішень. Вона також відома як проблема секретаря, проблема приданого султана, проблема метушливого залицяльника, гра гугол і проблема найкращого вибору. Її рішення також відоме як правило 37 %.

Основний варіант постановки проблеми такий: уявіть адміністратора, який хоче найняти найкращого секретаря з претендентів на відповідну посаду; претенденти можуть бути оцінені за рейтингом. Претенденти опитуються по черзі у випадковому порядку. Рішення щодо кожного конкретного претендента приймається відразу після співбесіди. Після відмови претендент не може бути прийнятий на роботу. Під час співбесіди адміністратор отримує достатньо інформації, щоб оцінити рейтинг претендента серед усіх опитаних на даний момент претендентів, але немає можливості порівняти з претендентами, які ще не розглядалися. Питання полягає в оптимальній стратегії (зупинки вибору) щоб максимізувати ймовірність вибору найкращого претендента. Якщо рішення можна відкласти до кінця, задачу можна вирішити за допомогою простого алгоритму вибору максимального відстеження поточного максимуму (і претендента, який його досяг), і вибору загального максимуму в кінці. Складність полягає в тому, що рішення потрібно приймати негайно.

Найкоротший точний доказ, відомий на сьогоднішній день, забезпечується алгоритмом шансів. Він передбачає, що оптимальна ймовірність виграшу завжди принаймні (де e — основа натурального логарифма), і що це справедливо у більш загальному випадку. Правило оптимальної зупинки передбачає стратегію відмови першим які проходять співбесіду, а потім вибору першого претендента, який є кращим за всіх претендентів, опитаних на даний момент (або продовження до останнього претендента, якщо цього ніколи не відбувається). Іноді цю стратегію називають правилом зупинки , оскільки ймовірність зупинитися на найкращому претенденті за допомогою цієї стратегії вже приблизно для помірних значень . Одна з причин, чому проблемі секретаря приділено так багато уваги, полягає в тому, що оптимальна стратегія для цієї проблеми (правило зупинки) проста і вибирає єдиного найкращого кандидата приблизно в 37 % випадків, незалежно від того, чи є 100 чи 100 мільйонів претендентів С. М. Гусейн-Заде, Разборчивая невеста. с. 18, М.: МЦНМО, 2003.

Формулювання

Хоча існує багато варіацій, основну проблему можна сформулювати так С. М. Гусейн-Заде. Разборчивая невеста, с. 3-4, М.: МЦНМО, 2003: Існує єдине вакантне місце. Є n претендентів на посаду і значення n відоме. Про кожного претендента можна сказати, кращий він за іншого чи гірший. Претенденти опитуються послідовно у випадковому порядку, причому кожен порядок є однаково ймовірним. Одразу після співбесіди претендент приймається або відхиляється, і рішення не підлягає скасуванню. Рішення прийняти або відхилити претендента може ґрунтуватися лише на відносних рангах претендентів, з якими на даний момент було проведено співбесіду. Метою загального рішення є найвища ймовірність вибору найкращого претендента з усієї групи. Це еквівалентно максимізації очікуваної нагороди, при цьому виграш визначається як одиниця для найкращого претендента та нуль в інших випадках.

Кандидат визначається як претендент, який під час співбесіди є кращим за всіх попередніх співбесід. Пропустити вживається в значенні «відмовити відразу після співбесіди». Оскільки метою завдання є вибір єдиного найкращого претендента, для прийняття розглядатимуться лише кандидати. «Кандидат» у цьому контексті відповідає поняттю запису в перестановці.

Виведення оптимальної стратегії Оптимальним підходом для цієї задачі є правило зупину. Згідно з ним, інтерв'юер відхиляє перших r − 1 претендентів (нехай претендент M буде найкращим серед цих r — 1 претендентів), а потім вибирає першого наступного претендента, який кращий за претендента M. Можна показати, що оптимальна стратегія належить цьому класу стратегій. (Зауважте, що ми ніколи не повинні вибирати претендента, який не є найкращим, якого ми бачили досі, оскільки він не може бути найкращим претендентом у цілому). Для довільного r розглянемо ймовірність того, що обрано найкращого претендента.

Сума не визначена для r = 1, але в цьому випадку єдиною можливою стратегією є вибір першого претендента, отже P(1) = 1/n. Ця сума отримана завдяки спостереженню, що якщо претендент i є найкращим претендентом, тоді він вибирається тоді і тільки тоді, коли найкращий претендент серед перших i − 1 претендентів є серед перших r − 1 претендентів, яких було відхилено. Якщо спрямувати n до нескінченності та позначити як границю (r−1)/n, використовуючи t замість (i−1)/n і dt замість 1/n, суму можна наблизити інтегралом

Беручи похідну від P(x) за , прирівнюючи її до 0 та вирішуючи для змінної x, ми знаходимо, що оптимальне x дорівнює 1/e. Таким чином, оптимальна зупинка наближується до n/e зі збільшенням n і найкращий претендент вибирається з імовірністю 1/e.

Для малих значень n оптимальне r також можна отримати стандартними методами динамічного програмування. Оптимальні граничні значення r та ймовірність вибору найкращої альтернативи P для кількох значень n наведені в наступній таблиці.

1 2 3 4 5 6 7 8 910 1 1 2 2 3 3 3 4 44 1.000 0.500 0.500 0.458 0.433 0.428 0.414 0.410 0.4060.399

Ймовірність вибору найкращого кандидата в класичній проблемі секретаря збігається до .

Альтернативне рішення Ця задача та кілька її модифікацій можуть бути розв'язані (включно з доказом оптимальності) простим способом за допомогою алгоритму шансів, який також має інші застосування. Модифікації проблеми секретаря, які можна розв'язати за допомогою цього алгоритму, включають випадкову доступність претендентів, більш загальні гіпотези про претендентів, які можуть бути цікавими для особи, яка приймає рішення, групові інтерв'ю претендентів, а також певні моделі для випадкової кількості претендентів.

Обмеження Розв'язання проблеми секретаря має сенс застосовувати лише тоді, коли є виправданим припущення, що претенденти не знають про застосовану стратегію прийняття рішень, оскільки перші претенденти взагалі не мають шансів і тому можуть не з'явитися на співбесіду.

Одним з важливих недоліків застосування рішення класичної проблеми секретаря є те, що кількість претендентів має бути відома заздалегідь, що рідко трапляється. Один із способів подолання цієї проблеми — припустити, що кількість заявників є випадковою величиною із відомим розподілом (Пресман і Сонін, 1972). Однак для цієї моделі оптимальне рішення, як правило, набагато складніше. Крім того, оптимальна ймовірність успіху тепер вже не близька до 1/e, а зазвичай нижча. Це можна тлумачити як «ціну» за відсутність інформації про кількості претендентів. Однак у цієї моделі ціна висока. Залежно від вибору розподілу , оптимальна ймовірність виграшу може наближатися до нуля. Пошук способів вирішення цієї нової проблеми призвів до нової моделі, яка дає так званий 1/e-закон найкращого вибору.

1/e-закон найкращого вибору Суть моделі базується на ідеї, що життя є послідовним і що проблеми реального світу виникають у реальному часі. Крім того, легше оцінити проміжки часу, коли конкретні події (прибуття претендентів) мають відбуватися частіше (якщо вони взагалі відбуваються), ніж оцінювати розподіл кількості конкретних подій, які відбуватимуться. Ця ідея призвела до так званого уніфікованого підходу (1984): Модель визначається наступним чином: претендент має бути вибраний на певному часовому інтервалі із невідомої кількості претендентів, які можуть бути оцінені за рейтингом. Мета полягає в тому, щоб максимізувати ймовірність вибору лише найкращих претендентів за гіпотези, що всі послідовності прибуття претендентів різного рангу однаково ймовірні. Припустимо, що всі претенденти мають однакову, але незалежну один від одного щільність функції часу прибуття на , і нехай позначає відповідну функцію розподілу часу прибуття, тобто

, .

Нехай таке, що Розглянемо стратегію очікування та спостереження за всіма претендентами до часу а потім виберемо, якщо це можливо, першого кандидата після часу , кращого за всіх попередніх. Тоді ця стратегія, яка називається 1/e-стратегія, має такі властивості:

Стратегія 1/e

(i) дає для всіх ймовірність успіху принаймні 1/e,

(ii) оптимальна стратегія мінімаксу коли невідомо,

(iii) не вибирає жодного з претендентів (якщо є принаймні один претендент) з імовірністю, яка точно дорівнює 1/e.

1/e-закон, доведений у 1984 році , став несподіванкою. Причина полягала в тому, що приблизне значення 1/e раніше вважалося недосяжним у моделі для невідомого , тоді як це значення 1/e тепер було досягнуто як нижня межа ймовірності успіху, і це в моделі з, можливо, набагато слабшими гіпотезами (див., наприклад, Math. Reviews 85:m).

Однак існує багато інших стратегій, які досягають (i) і (ii) і, крім того, працюють набагато краще, ніж 1/e-стратегія одночасно для всіх >2. Простим прикладом є стратегія, яка вибирає (якщо це можливо) першого відносно найкращого кандидата після часу за умови, що принаймні один претендент з'явився до цього часу, а в іншому випадку вибирає (якщо це можливо) другого відносно найкращого кандидата після часу .

1/e-закон іноді плутають із розв'язком класичної проблеми секретаря, описаної вище, через подібну роль числа 1/e. Однак у 1/e-законі, ця роль є більш загальною. Результат також сильніший, оскільки він справедливий для невідомої кількості претендентів і оскільки модель, заснована на розподілі часу прибуття F є більш сприйнятливою для практичного застосування.

Гра гугол У статті «Хто вирішив проблему секретаря?» (, 1989), стверджується, що проблема секретаря вперше з'явилася в друкованому вигляді в Мартіна Гарднера в лютому 1960 року в Scientific American:Попросіть когось взяти довільну кількість аркушів, і на кожному аркуші написати позитивне число. Числа можуть варіюватися від дрібних дробів одиниці до числа гугол (одиниця з сотнею нулів) або навіть більше. Ці аркуші перевертають лицьовою стороною вниз і перемішують на столі. По черзі ви перевертаєте аркуші стороною вгору. Мета полягає в тому, щоб припинити гортати аркуші, коли ви дійдете до числа, яке, на вашу думку, є найбільшим у серії. Ви не можете повернутися назад і вибрати раніше перевернутий аркуш. Якщо ви перегортаєте всі аркуші, то, звичайно, ви повинні вибрати останній.Фергюсон зазначив, що гра секретаря залишилася невирішеною, як гра з нульовою сумою з двома протидіючими гравцями. У цій грі:

Аліса, поінформований гравець, таємно пише різні числа на картках. Боб, «зупиняючий» гравець, спостерігає за числами і може припинити перевертання карток коли забажає, виграючи, якщо остання повернута картка має загальну максимальне число. Боб хоче вгадати максимальне число з якомога більшою ймовірністю, тоді як мета Аліси полягає в тому, щоб ця ймовірність була якомога нижчою.

Така постановка проблеми має дві відмінності від основної проблеми секретаря:

Алісі не має записувати числа цілком випадково. Вона може записати їх відповідно до будь-якого спільного розподілу імовірностей щоб ввести в оману Боба. Боб спостерігає за фактичними значеннями, написаними на картках, які він може використовувати у своєму процесі прийняття рішень.

Аналіз стратегії Аліса спочатку записує n чисел, які потім перемішує. Отже, їх порядок не має значення, тобто числа Аліси мають бути . Тоді стратегія Аліси полягає лише у виборі найскладнішої послідовності випадкових змінних з множини взаємозамінних послідовностей.

Стратегію Боба можна формалізувати як правило зупинки для послідовності .