Задача о разборчивой невесте

Задача о разборчивой невесте (проблема остановки выбора) — оптимизационная задача, впервые сформулированная Мартином Гарднером в 1960 году.

В англоязычной литературе встречается также под названием задачи о секретаре.

Формулировка

Задача может быть сформулирована следующим образом:

1. Невеста ищет себе жениха (существует единственное вакантное место).
2. Есть известное число претендентов — $n$.
3. Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
4. Претенденты образуют линейный порядок: асимметричный, транзитивный — о каждом претенденте известно, лучше он или хуже любого из предыдущих.
5. Пообщавшись с претендентом, невеста сравнивает его с предыдущими и либо отказывает, либо принимает его предложение. Если предложение принято, они женятся и процесс останавливается. Если невеста отказывает жениху, то вернуться к нему позже она не сможет.
6. Невеста выигрывает, если она выберет самого лучшего претендента. Выбор даже второго по порядку сравнения — проигрыш.

Требуется найти решение, с наибольшей вероятностью приводящее к выбору самого лучшего претендента.

Решения

Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико, оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых $n/e$ (где $e=2{,}718\ldots$ — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих. При увеличении $n$ вероятность выбора наилучшего претендента стремится к $1/e\approx 37\%$.

История

Задача о разборчивой невесте, по-видимому, была введена в 1949 году Мерриллом М. Фладом, который назвал её проблемой невесты в лекции, которую он прочитал в том же году. Он упоминал ее несколько раз в течение 1950-х годов, например, в выступлении на конференции в Purdue 9 мая 1958 года, и в конечном итоге она стала широко известна в народе, хотя в то время ничего не было опубликовано. В 1958 году он отправил письмо Леонарду Гиллману с копиями дюжине друзей, включая Сэмюэля Карлина и Дж. Роббинса, в котором изложил доказательство оптимальной стратегии с приложением Р. Палермо, который доказал, что среди всех стратегий доминирует стратегия "отклонить первое p безоговорочно, затем принять следующего кандидата, который лучше".

Первая публикация, очевидно, была сделана Мартином Гарднером в журнале Scientific American за февраль 1960 года. Он слышал об этом от Джона Х. Фокса-младшего и Л. Джеральда Марни, которые независимо друг от друга придумали аналогичную задачу в 1958 году; они назвали это «game of googol». Фокс и Марни не знали оптимального решения; Гарднер обратился за советом к Лео Мозеру, который (вместе с Дж. Р. Паундером) предоставил правильный анализ для публикации в журнале. Вскоре после этого несколько математиков написали Гарднеру об эквивалентной задаче, о которой они знали по слухам, и вероятном схождении всех задач к оригинальной работе Флада.

В 1963 году Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.

1/e-закон наилучшего выбора принадлежит Ф. Томасу Брюссу (1984).

Фергюсон (1989) имеет обширную библиографию и указывает, что подобная (но другая) проблема рассматривалась Артуром Кейли в 1875 году и даже Иоганном Кеплером задолго до этого.

На Конференции Разработчиков Игр 2011 Сергей Орловский рассказал об этой задаче.

Варианты задачи

Среди вариантов и обобщений задачи встречаются такие, в которых заранее неизвестно общее количество претендентов, или такие, в которых для каждого претендента можно не только сравнить его с остальными, но и дать ему абсолютную оценку.

В диссертации Бориса Березовского, впоследствии члена-корреспондента РАН, на соискание ученой степени доктора наук «Разработка теоретических основ алгоритмизации принятия предпроектных решений и их применения», защищенной в 1983 году, рассматривается обобщение задачи о разборчивой невесте.

Ссылки

• С. М. Гусейн-Заде. Разборчивая невеста. — МЦНМО, 2003. — Т. 25. — 20 с. — (Библиотека «Математическое просвещение»). — ISBN 5-94057-076-3.
• С. М. Гусейн-Заде. Разборчивая невеста. Видео-лекция. Малый мехмат, МГУ, 30.11.2002.
• И. Р. Высоцкий, И. В. Ященко Задачи заочных интернет-олимпиад по теории вероятностей и статистике — МЦНМО, 2017, с.255, 275 — ISBN 978-5-4439-1136-6
• Steven R. Finch. 5.15 Optimal Stopping Constants // Mathematical constants. — Cambridge University Press, 2003. — ISBN 978-0-521-81805-6. Errata and Addenda.