Задача секретаря

редактировать

Графики вероятностей получения лучшего кандидата (красные кружки) и k / n (синие кресты), где k - размер выборки

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

Основная форма проблемы заключается в следующем: представьте себе администратора, который хочет нанять лучшего секретаря из $n {\ displaystyle n}$ $n$ претендентов на должность.. Претенденты проходят собеседование по одному в случайном порядке. Решение по каждому конкретному заявителю будет принято сразу после собеседования. После отклонения заявитель не может быть отозван. Во время собеседования администратор получает информацию, достаточную для ранжирования кандидата среди всех кандидатов, проинтервьюированных до сих пор, но не знает о качестве еще не замеченных кандидатов. Вопрос заключается в оптимальной стратегии (правило остановки ) для максимизации вероятности выбора лучшего кандидата. Если решение можно отложить до конца, это можно решить с помощью простого алгоритма выбора максимума отслеживания текущего максимума (и того, кто его достиг) и выбора общего максимума в конце. Сложность в том, что решение нужно принимать немедленно.

Самое короткое из известных до сих пор строгих доказательств дает алгоритм шансов (Bruss 2000). Это означает, что оптимальная вероятность выигрыша всегда составляет не менее $1 / e {\ displaystyle 1 / e}$ $1/e$ (где e - основание натурального логарифма ), и последнее верно даже в гораздо большей степени (2003). Оптимальное правило остановки предписывает всегда отклонять первых $∼ n / e {\ displaystyle \ sim n / e}$ $\sim n/e$ кандидатов, прошедших собеседование, а затем останавливаться на первом кандидате, который лучше всех опрошенных кандидатов, поэтому далеко (или продолжая до последнего заявителя, если этого не происходит). Иногда эту стратегию называют $1 / e {\ displaystyle 1 / e}$ $1/e$ правилом остановки, потому что вероятность остановки у лучшего кандидата с этой стратегией составляет примерно $1 / e {\ displaystyle 1 / e}$ $1/e$ уже для умеренных значений $n {\ displaystyle n}$ $n$ . Одна из причин, по которой проблеме секретаря уделяется так много внимания, заключается в том, что оптимальная политика для проблемы (правило остановки) проста и выбирает единственного лучшего кандидата примерно в 37% случаев, независимо от того, 100 или 100 миллионов претендентов.

Содержание

1 Формулировка
2 Выведение оптимальной политики
3 Альтернативное решение
4 Применимость в реальной жизни
5 1 / лучший выбор электронного закона
6 Игра googol
7 Эвристическая эффективность
8 Вариант кардинальной выплаты
9 Другие модификации
- 9.1 Задача множественного выбора
10 Экспериментальные исследования
11 Нейронные корреляты
12 История
13 Комбинаторное обобщение
14 См. Также
15 Примечания
16 Ссылки
17 Внешние ссылки

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

Хотя существует много вариантов, основную проблему можно сформулировать следующим образом:

Необходимо заполнить одну вакансию.
На эту должность n претендентов, и значение n известно.
Кандидатов, если рассматривать их вместе, можно расположить от лучших к худшим однозначно.
Соискатели проходят собеседование последовательно в случайном порядке, причем каждый порядок одинаково вероятен.
Сразу после собеседования опрошенный кандидат либо принимается, либо отклоняется, и решение является безотзывным.
Решение принять или отклонить кандидата может быть основано только на относительном ранге кандидатов, проинтервьюированных на данный момент.
Целью общего решения является получение наивысшего вероятность выбора лучшего претендента из всей группы. Это то же самое, что максимизация ожидаемого выигрыша, при этом выигрыш определяется как один для лучшего кандидата и ноль в противном случае.

Кандидат определяется как кандидат, который на собеседовании лучше, чем все кандидаты, опрошенные ранее. Пропустить означает «отклонить сразу же после собеседования». Поскольку цель задачи - выбрать единственного лучшего соискателя, для принятия будут рассматриваться только кандидаты. «Кандидат» в этом контексте соответствует концепции записи в перестановке.

Получение оптимальной политики

Оптимальной политикой для проблемы является правило остановки. В соответствии с ним интервьюер отклоняет первых r - 1 кандидатов (пусть кандидат M будет лучшим кандидатом среди этих r - 1 кандидатов), а затем выбирает первого последующего кандидата, который лучше, чем кандидат M. Можно показать, что оптимальная стратегия лежит в этом классе стратегий. (Обратите внимание, что мы никогда не должны выбирать кандидата, который не является лучшим кандидатом, которого мы видели до сих пор, поскольку он не может быть лучшим кандидатом в целом.) Для произвольного отсечения r вероятность того, что будет выбран лучший кандидат, составляет

P ( r) = ∑ i = 1 n P (кандидат i выбран ∩ кандидат i является лучшим) = ∑ i = 1 n P (кандидат i выбран | кандидат i является лучшим) ⋅ P (кандидат i является лучшим) = [∑ i = 1 r - 1 0 + ∑ i = rn P (лучший из первых i - 1 претендентов попадает в первые r - 1 претендента | претендент i - лучший)] ⋅ 1 n = [∑ i = rnr - 1 i - 1] ⋅ 1 n = r - 1 n ∑ i = rn 1 i - 1. {\ displaystyle {\ begin {align} 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 {является лучшим}} \ справа) \\ = \ 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 {массив }} \ 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}} \ quad = \ quad {\ frac {r-1 } {n}} \ sum _ {i = r} ^ {n} {\ frac {1} {i-1}}. \ end {align}}}

{\begin{aligned}P(r)=\sum _{i=1}^{n}P\left({\text{applicant }}i{\text{ is selected}}\cap {\text{applicant }}i{\text{ is the best}}\right)\\=\sum _{i=1}^{n}P\left({\text{applicant }}i{\text{ is selected}}|{\text{applicant }}i{\text{ is the best}}\right)\cdot P\left({\text{applicant }}i{\text{ is the best}}\right)\\=\left[\sum _{i=1}^{r-1}0+\sum _{i=r}^{n}P\left(\left.{\begin{array}{l}{\text{the best of the first }}i-1{\text{ applicants}}\\{\text{is in the first }}r-1{\text{ applicants}}\end{array}}\right|{\text{applicant }}i{\text{ is the best}}\right)\right]\cdot {\frac {1}{n}}\\=\left[\sum _{i=r}^{n}{\frac {r-1}{i-1}}\right]\cdot {\frac {1}{n}}\quad =\quad {\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 к бесконечности, записывая $x {\ displaystyle x}$ $x$ как предел (r-1) / n, используя t для (i-1) / n и dt для 1 / n, сумма может быть аппроксимирована интегралом

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

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

Взяв производную P (x) относительно $x {\ displaystyle x}$ $x$ , установив его в 0 и решив относительно x, мы находим, что оптимальный x равен 1 / e. Таким образом, оптимальное отсечение стремится к n / e при увеличении n, и лучший кандидат выбирается с вероятностью 1 / e.

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

$n {\ displaystyle n}$ $n$	1	2	3	4	5	6	7	8	9
$r {\ displaystyle r}$ $r$	1	1	2	2	3	3	3	4	4
$P {\ displaystyle P}$ $P$	1.000	0,500	0,500	0,458	0,433	0,428	0,414	0,410	0,406

Вероятность выбора лучшего претендента в классическом проблема секретаря сходится к $1 / e ≈ 0,368 {\ displaystyle 1 / e \ приблизительно 0,368}$ $1/e\approx 0.368$ .

Альтернативное решение

Эта проблема и несколько модификаций могут быть решены (включая доказательство оптимальности) в напрямую с помощью алгоритма Odds (2000), который также имеет другие приложения. Модификации задачи секретаря, которые могут быть решены с помощью этого алгоритма, включают случайную доступность кандидатов, более общие гипотезы для кандидатов, представляющих интерес для лица, принимающего решения, групповые собеседования для кандидатов, а также определенные модели для случайного числа кандидатов.

Применимость в реальной жизни

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

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

Одним из важных недостатков приложений решения классической задачи секретаря является то, что количество претендентов $n {\ displaystyle n}$ $n$ должно быть известно заранее, что редко бывает кейс. Один из способов преодоления этой проблемы - предположить, что количество претендентов является случайной величиной $N {\ displaystyle N}$ $N$ с известным распределением $P (N = k) k = 1, 2, ⋯ {\ Displaystyle P (N = k) _ {k = 1,2, \ cdots}}$ $P(N=k)_{{k=1,2,\cdots }}$ (Пресман и Сонин, 1972). Однако для этой модели оптимальное решение в целом намного сложнее. Более того, оптимальная вероятность успеха теперь больше не около 1 / е, а обычно ниже. Это можно понять в контексте наличия «цены», которую придется заплатить за незнание количества претендентов. Однако в этой модели цена высока. В зависимости от выбора распределения $N {\ displaystyle N}$ $N$ оптимальная вероятность выигрыша может приближаться к нулю. Поиск способов справиться с этой новой проблемой привел к новой модели, дающей так называемый 1 / e-закон наилучшего выбора.

1 / электронный закон наилучшего выбора

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

Модель определяется следующим образом: Кандидат должен быть выбран на некотором временном интервале $[0, T] {\ displaystyle [0, T]}$ $[0,T]$ из неизвестного числа $N {\ displaystyle N}$ $N$ подходящих кандидатов. Цель состоит в том, чтобы максимизировать вероятность выбора только лучших при гипотезе, что все порядки прибытия разных рангов равновероятны. Предположим, что у всех кандидатов одинаковая, но независимая друг от друга, плотность времени прибытия $f {\ displaystyle f}$ $f$ на $[0, T] {\ displaystyle [0, T]}$ $[0,T]$ и пусть $F {\ displaystyle F}$ $F$ обозначает соответствующую функцию распределения времени прибытия, то есть

F (t) = ∫ 0 tf (s) ds {\ displaystyle F (t) = \ int _ {0} ^ {t} f (s) ds}

F(t)=\int _{{0}}^{{t}}f(s)ds

0 ≤ t ≤ T {\ displaystyle \, 0 \ leq t \ leq T}

\,0\leq t\leq T

Пусть $τ {\ displaystyle \ tau}$ $\tau$ должно быть таким, что $F (τ) = 1 / e. {\ displaystyle F (\ tau) = 1 / e.}$ $F(\tau)=1/e.$ Рассмотрите стратегию ожидания и наблюдения за всеми кандидатами до времени $τ {\ displaystyle \ tau}$ $\tau$ , а затем для выбора, если возможно, первого кандидата через время $τ {\ displaystyle \ tau}$ $\tau$ , которое лучше всех предыдущих. Тогда эта стратегия, называемая 1 / электронной стратегией, имеет следующие свойства:

1 / электронная стратегия

(i) дает результат для всех

N {\ displaystyle N}

N

вероятность успеха не менее 1 / e,

(ii) - это уникальная стратегия, гарантирующая эту нижнюю границу вероятности успеха 1 / e, и эта граница является оптимальной,

(iii) выбирает, если есть по крайней мере один заявитель, ни одного с вероятностью ровно 1 / e.

Закон 1 / e, подтвержденный в 1984 г. F. Томас Брюсс стал неожиданностью. Причина заключалась в том, что значение около 1 / e раньше считалось недостижимым в модели для неизвестного $N {\ displaystyle N}$ $N$ , тогда как теперь это значение 1 / e было достигнуто как нижняя граница вероятности успеха, и это в модели с возможно более слабыми гипотезами (см., например, Math. Reviews 85: m).

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

Игра в гугол

Согласно Фергюсон 1989 ошибка harvnb: несколько целей (2 ×): CITEREFFerguson1989 (help ), проблема секретаря впервые появился в печати, когда он был упомянут Мартином Гарднером в его февральской 1960 г. колонке «Математические игры» в Scientific American. Вот как это сформулировал Гарднер: «Попросите кого-нибудь взять столько листков бумаги, сколько ему заблагорассудится, и на каждом листе напишите разное положительное число. Числа могут варьироваться от малых долей единицы до числа размером с гугол (1 с последующими сотнями нулей) или даже больше. Эти листы переворачиваются лицевой стороной вниз и перетасовываются поверх стола. Вы переворачиваете листы по одному. Цель состоит в том, чтобы перестать поворачиваться, когда вы дойдете до числа, которое вы угадайте, что это самый большой из серии. Вы не можете вернуться и выбрать ранее повернутый лист. Если вы перевернете все листы, то, конечно, вы должны выбрать последний повернутый ".

В статье «Кто решил проблему Секретаря?» Фергюсон 1989 ошибка harvnb: несколько целей (2 ×): CITEREFFerguson1989 (help ) указал, что проблема секретаря осталась нерешенной, как это было заявлено М. Гарднером, то есть как две -персонал игра с нулевой суммой с двумя антагонистическими игроками. В этой игре Алиса, информированный игрок, тайно записывает различные числа на $n {\ displaystyle n}$ $n$ картах. Боб, останавливающий игрок, наблюдает за фактическими значениями и может прекратить переворачивать карты, когда захочет, выигрывая, если последняя повернутая карта имеет максимальное общее количество. Отличие от основной проблемы секретаря заключается в том, что Боб наблюдает за фактическими значениями, записанными на карточках, которые он может использовать в своих процедурах принятия решений. Цифры на карточках аналогичны количественным качествам претендентов в некоторых версиях задачи секретаря. Совместное распределение вероятностей чисел находится под контролем Алисы.

Боб хочет угадать максимальное число с максимально возможной вероятностью, в то время как цель Алисы - сохранить эту вероятность как можно ниже. Для Алисы неоптимально отбирать числа независимо от некоторого фиксированного распределения, и она может играть лучше, выбирая случайные числа некоторым зависимым образом. Для $n = 2 {\ displaystyle n = 2}$ $n=2$ Алиса не имеет стратегии минимакс, что тесно связано с парадоксом T. Обложка. Но для $n>2 {\ displaystyle n>2}$ $n>2$ у игры есть решение: Алиса может выбирать случайные числа (которые являются зависимыми случайными величинами) таким образом, чтобы Боб не мог играть лучше, чем использование классической стратегии остановки, основанной на относительной ранги (Гнедин 1994).

Эвристическая эффективность

В оставшейся части статьи снова рассматривается проблема секретаря для известного числа кандидатов.

Ожидаемая вероятность успеха для трех эвристик.

Stein, Seale Rapoport 2003 вывели ожидаемые вероятности успеха для нескольких психологически правдоподобных эвристик, которые могут быть использованы в задаче секретаря. Они исследовали следующие эвристики:

Правило отсечения (CR) : Не принимайте ни одного из первых y кандидатов; после этого выберите первого встреченного кандидата (т. Е. Кандидата с относительной нк 1). Это правило имеет как частный случай оптимальную политику для классической задачи секретаря, для которой y = r.
Правило подсчета кандидатов (CCR): выберите y-ого встреченного кандидата. Обратите внимание, что это правило не обязательно пропускает кандидатов; он учитывает только количество наблюдаемых кандидатов, а не то, насколько глубоко лицо, принимающее решение, находится в последовательности кандидатов.
Правило последовательного некандидата (SNCR): выберите первого встреченного кандидата после наблюдения y некандидатов (т. е., соискатели с относительным рейтингом>1).

Каждая эвристика имеет единственный параметр y. На рисунке (показан справа) показаны ожидаемые вероятности успеха для каждой эвристики как функция y для задач с n = 80.

Вариант кардинальной выплаты

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

Чтобы смоделировать эту проблему, предположим, что кандидаты $n {\ displaystyle n}$ $n$ имеют «истинные» значения, которые являются случайными величинами X, нарисованными iid из равномерного распределения на [0, 1]. Подобно классической задаче, описанной выше, интервьюер только наблюдает, является ли каждый кандидат лучшим на данный момент (кандидат), должен принять или отклонить каждого на месте и должен принять последнего, если он / она найден. (Для ясности, интервьюер не узнает фактический относительный ранг каждого кандидата. Он / она узнает только, имеет ли кандидат относительный ранг 1.) Однако в этой версии выигрыш определяется истинной стоимостью выбранного кандидата. Например, если он выберет кандидата, истинная ценность которого составляет 0,8, то он / она заработает 0,8. Цель интервьюера - максимизировать ожидаемую ценность отобранного соискателя.

Поскольку ценности заявителя равны i.i.d. извлекается из равномерного распределения на [0, 1], ожидаемое значение t-го кандидата, учитывая, что $xt = max {x 1, x 2,…, xt} {\ displaystyle x_ {t } = \ max \ left \ {x_ {1}, x_ {2}, \ ldots, x_ {t} \ right \}}$ $x_{{t}}=\max \left\{x_{1},x_{2},\ldots,x_{t}\right\}$ задается как

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

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

Как и в классической задаче, Оптимальная политика задается порогом, который для этой задачи мы обозначим $c {\ displaystyle c}$ $c$ , при котором интервьюер должен начать прием кандидатов. Bearden 2006 показал, что c равно $⌊ n ⌋ {\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor}$ $\lfloor {\sqrt n}\rfloor$ или $⌈ n ⌉ {\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$ $\lceil {\sqrt n}\rceil$ . (На самом деле, в зависимости от того, что ближе всего к $n {\ displaystyle {\ sqrt {n}}}$ ${\sqrt n}$ .) Это следует из того факта, что при наличии проблемы с $n {\ displaystyle n}$ $n$ соискатели, ожидаемый выигрыш для некоторого произвольного порога $1 ≤ c ≤ n {\ displaystyle 1 \ leq c \ leq n}$ $1\leq c\leq n$ составляет

V n (c) = ∑ t = cn - 1 [∏ s = ct - 1 (s - 1 s)] (1 t + 1) + [∏ s = cn - 1 (s - 1 s)] 1 2 = 2 cn - c 2 + c - n 2 спн. {\ 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} + cn} {2cn} }.}

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}}}.

Дифференцируя $V n (c) {\ displaystyle V_ {n} (c)}$ $V_{{n}}(c)$ относительно c, получаем

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

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

Поскольку $∂ 2 V / ∂ c 2 < 0 {\displaystyle \partial ^{\,2}V/\partial c^{\,2}<0}$ $\partial ^{{\,2}}V/\partial c^{{\,2}}<0$ для всех допустимых значений $c {\ displaystyle c}$ $c$ , мы находим, что $V { \ displaystyle V}$ $V$ разворачивается в $c = n {\ displaystyle c = {\ sqrt {n}}}$ $c={\sqrt n}$ . Так как V является выпуклой в $c {\ displaystyle c}$ $c$ , оптимальный целочисленный порог должен быть либо $⌊ n ⌋ {\ displaystyle \ lfloor {\ sqrt {n}} \ rfloor }$ $\lfloor {\sqrt n}\rfloor$ или $⌈ n ⌉ {\ displaystyle \ lceil {\ sqrt {n}} \ rceil}$ $\lceil {\sqrt n}\rceil$ . Таким образом, для большинства значений $n {\ displaystyle n}$ $n$ интервьюер начнет принимать кандидатов раньше в версии с кардинальной выплатой, чем в классической версии, где цель состоит в выборе единственного лучшего кандидата. Обратите внимание, что это не асимптотический результат: он верен для всех $n {\ displaystyle n}$ $n$ . Однако это не оптимальная политика для максимизации ожидаемого значения от известного распределения. В случае известного распределения оптимальный люфт может быть рассчитан с помощью динамического программирования.

Другие модификации

Есть несколько вариантов задачи секретаря, которые также имеют простые и элегантные решения.

Один вариант заменяет желание выбрать лучшее желанием выбрать второе. Роберт Дж. Вандербей называет это проблемой «постдока», утверждая, что «лучшие» поступят в Гарвард. Для этой задачи вероятность успеха для четного числа претендентов составляет точно $0,25 n 2 n (n - 1) {\ displaystyle {\ frac {0,25n ^ {2}} {n (n-1)} }}$ ${\frac {0.25n^{2}}{n(n-1)}}$ . Эта вероятность стремится к 1/4, поскольку n стремится к бесконечности, что свидетельствует о том, что легче выбрать лучшее, чем второе из лучших.

Для второго варианта указано количество вариантов выбора больше одного. Другими словами, интервьюер нанимает не одного секретаря, а, скажем, принимает группу студентов из резерва кандидатов. При предположении, что успех достигается тогда и только тогда, когда все отобранные кандидаты превосходят всех невыбранных кандидатов, это снова проблема, которую можно решить. В Vanderbei 1980 было показано, что когда n четно и желательно выбрать ровно половину кандидатов, оптимальная стратегия дает вероятность успеха $1 n / 2 + 1 {\ displaystyle {\ frac {1} {n / 2 + 1}}}$ ${\frac {1}{n/2+1}}$ .

Другой вариант заключается в выборе лучших $k {\ displaystyle k}$ $k$ секретарей из пула $n { \ displaystyle n}$ $n$ , опять же в интерактивном алгоритме. Это приводит к стратегии, связанной с классической, и порогом отсечения $0,25 n 2 n (n - 1) {\ displaystyle {\ frac {0,25n ^ {2}} {n (n-1)}}}$ ${\frac {0.25n^{2}}{n(n-1)}}$ , для которого классическая проблема является частным случаем Ghirdar 2009 ошибка harvnb: нет цели: CITEREFGhirdar2009 (help ).

Проблема с множественным выбором

Игроку разрешено $r {\ displaystyle r}$ $r$ выбора, и он побеждает, если какой-либо вариант является лучшим. Gilbert Mosteller 1966 показали, что оптимальная стратегия задается пороговой стратегией (стратегией отсечения). Оптимальная стратегия принадлежит к классу стратегий, определяемых набором пороговых чисел $(a 1, a 2,..., ar) {\ displaystyle (a_ {1}, a_ {2},..., a_ {r})}$ $(a_{1},a_{2},...,a_{r})$ , где $a 1 < a 2 < ⋯ < a r {\displaystyle a_{1}$ $a_{1}<a_{2}<\cdots <a_{r}$ . Первый вариант следует использовать для первых кандидатов, начиная с $1 {\ displaystyle a_ {1}}$ $a_{1}$ -го кандидата, а как только будет использован первый вариант, второй вариант будет использоваться для первый кандидат, начинающийся с $- 2 {\ displaystyle a_ {2}}$ $a_{2}$ -й кандидат и так далее.

Гилберт и Мостеллер показали, что $(a 1 n, a 2 n, a 3 n, a 4 n) → (e - 1, e - 3 2, e - 47 24, e - 2761 1152) (n → ∞) {\ displaystyle \ left ({\ frac {a_ {1}} {n}}, {\ frac {a_ {2}} {n}}, {\ frac {a_ {3}}) {n}}, {\ frac {a_ {4}} {n}} \ right) \ rightarrow \ left (e ^ {- 1}, e ^ {- {\ frac {3} {2}}}, e ^ {- {\ frac {47} {24}}}, e ^ {- {\ frac {2761} {1152}}} \ right) (n \ rightarrow \ infty)}$ $\left({\frac {a_{1}}{n}},{\frac {a_{2}}{n}},{\frac {a_{3}}{n}},{\frac {a_{4}}{n}}\right)\rightarrow \left(e^{-1},e^{-{\frac {3}{2}}},e^{-{\frac {47}{24}}},e^{-{\frac {2761}{1152}}}\right)(n\rightarrow \infty)$ . Для других случаев $r = 5, 6,..., 10 {\ displaystyle r = 5,6,..., 10}$ $r=5,6,...,10$ , см. Matsui Ano 2016 (например, $a 5 n → e - 4162637 1474560 { \ displaystyle {\ frac {a_ {5}} {n}} \ rightarrow e ^ {- {\ frac {4162637} {1474560}}}}$ ${\frac {a_{5}}{n}}\rightarrow e^{-{\frac {4162637}{1474560}}}$ ).

Когда $r = 2 {\ displaystyle r = 2}$ $r=2$ , вероятность выигрыша сходится к $e - 1 + e - 3 2 (n → ∞) { \ displaystyle e ^ {- 1} + e ^ {- {\ frac {3} {2}}} (n \ rightarrow \ infty)}$ $e^{-1}+e^{-{\frac {3}{2}}}(n\rightarrow \infty)$ (Gilbert Mosteller 1966). Matsui Ano 2016 показали, что для любого положительного целого числа $r {\ displaystyle r}$ $r$ вероятность выигрыша ( $r {\ displaystyle r}$ $r$ проблема выбора секретаря) сходится к $p 1 + p 2 + ⋯ + pr {\ displaystyle p_ {1} + p_ {2} + \ cdots + p_ {r}}$ $p_{1}+p_{2}+\cdots +p_{r}$ где $pi = lim n → ∞ ain {\ displaystyle p_ {i} = \ lim _ {n \ rightarrow \ infty} {\ frac {a_ {i}} {n}}}$ $p_{i}=\lim _{n\rightarrow \infty }{\frac {a_{i}}{n}}$ . Таким образом, вероятность выигрыша сходится к $e - 1 + e - 3 2 + e - 47 24 {\ displaystyle e ^ {- 1} + e ^ {- {\ frac {3} {2}}} + e ^ {- {\ frac {47} {24}}}}$ $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}$ и $e - 1 + e - 3 2 + e - 47 24 + e - 2761 1152 {\ displaystyle e ^ { -1} + e ^ {- {\ frac {3} {2}}} + e ^ {- {\ frac {47} {24}}} + e ^ {- {\ frac {2761} {1152}} }}$ $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}$ при $r = 3, 4 {\ displaystyle r = 3,4}$ $r=3,4$ соответственно.

Экспериментальные исследования

Экспериментальные психологи и экономисты изучили решающее поведение реальных людей в проблемных ситуациях секретарей. В значительной степени эта работа показала, что люди склонны прекращать поиск слишком рано. Это можно объяснить, по крайней мере частично, стоимостью оценки кандидатов. В реальных условиях это может означать, что люди не проводят достаточного поиска всякий раз, когда сталкиваются с проблемами, когда альтернативные решения встречаются последовательно. Например, пытаясь решить, на какой заправке на шоссе остановиться для заправки, люди могут недостаточно искать, прежде чем остановиться. Если это правда, то они будут платить за бензин больше, чем если бы они искали дольше. То же самое может быть верно, когда люди ищут в Интернете авиабилеты. Экспериментальные исследования таких проблем, как проблема секретаря, иногда называют исследованием поведенческих операций.

нейронных коррелятов

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

Исследователи изучили нейронные основы решения проблемы секретарей у здоровых добровольцев с помощью функциональной МРТ. Марковский процесс принятия решения (MDP) использовался для количественной оценки ценности продолжения поиска по сравнению с принятием текущего варианта. Решения о принятии или отклонении варианта касаются теменной и дорсолатеральной префронтальной коры, а также брюшного полосатого тела, передней островковой доли и передняя поясная извилина. Следовательно, области мозга, ранее участвовавшие в интеграции доказательств и представлении вознаграждения, кодируют пересечения пороговых значений, которые инициируют принятие решений о принятии выбора.

История

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

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

Лучший выбор 1 / электронного закона обусловлен F. Томас Брюсс (1984).

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

Комбинаторное обобщение

Проблема секретаря может быть обобщена на случай, когда имеется несколько разных должностей. Опять же, есть $n {\ displaystyle n}$ $n$ кандидатов, поступающих в случайном порядке. Когда кандидат приходит, она показывает набор неотрицательных чисел. Каждое значение указывает ее квалификацию для одной из должностей. Администратор не только должен решить, принимать или нет соискателя, но, если да, также должен назначить ее на постоянное место работы на одну из должностей. Задача - найти задание, в котором сумма квалификаций будет как можно больше. Эта проблема идентична поиску соответствия максимального веса в двудольном графе со взвешенными ребрами, где узлы $n {\ displaystyle n}$ $n$ одной стороны поступают в случайном порядке в оперативный режим. Таким образом, это частный случай проблемы двустороннего соответствия в режиме онлайн.

Обобщая классический алгоритм для задачи секретаря, можно получить задание, в котором ожидаемая сумма квалификаций составляет только множитель $e {\ displaystyle e}$ $e$ менее оптимального (автономного) назначения.

См. также

Примечания

Ссылки

Бирден, Дж. Н. (2006). «Новая задача секретаря с отбором на основе ранга и кардинальными выплатами». Журнал математической психологии. 50 : 58–9. doi : 10.1016 / j.jmp.2005.11.003. CS1 maint: ref = harv (ссылка )
Бирден, Дж. Н., Мерфи, Р. О. Рапопорт, A. (2005). «Расширение задачи секретаря с множеством атрибутов: теория и эксперименты». Journal of Mathematical Psychology. 49 (5): 410–425. CiteSeerX 10.1.1.497.6468. doi :10.1016/j.jmp.2005.08.002.CS1 maint: multiple names: authors list (link )
Bearden, J. Neil; Rapoport, Amnon; Murphy, Ryan O. (September 2006). "Sequential Observation and Selection with Rank-Dependent Payoffs: An Experimental Study". Management Science. 52(9): 1437–1449. doi :10.1287/mnsc.1060.0535.
Bruss, F. Thomas (June 2000). "Sum the odds to one and stop". The Annals of Probability. 28(3): 1384–1391. doi :10.1214/aop/1019160340.
Bruss, F. Thomas (October 2003). "A note on bounds for the odds theorem of optimal stopping". The Annals of Probability. 31(4): 1859–1961. doi :10.1214/aop/1068646368.
Bruss, F. Thomas (August 1984). "A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options". The Annals of Probability. 12(3): 882–889. doi :10.1214/aop/1176993237.
Ferguson, Thomas S. (August 1989). "Who Solved the Secretary Problem?". Statistical Science. 4(3): 282–289. doi :10.1214/ss/1177012493.CS1 maint: ref=harv (link )
Freeman, P.R. (1983). "The secretary problem and its extensions: A review". International Statistical Review / Revue Internationale de Statistique. 51(2): 189–206. doi :10.2307/1402748. JSTOR 1402748.
Girdhar, Yogesh; Dudek, Gregory (2009). "Optimal Online Data Sampling or How to Hire the Best Secretaries". 2009 Canadian Conference on Computer and Robot Vision. pp. 292–298. CiteSeerX 10.1.1.161.41. doi :10.1109/CRV.2009.30. ISBN 978-1-4244-4211-9.
Gilbert, J; Mosteller, F (1966). "Recognizing the Maximum of a Sequence". Journal of the American Statistical Association. 61(313): 35–73. doi :10.2307/2283044. JSTOR 2283044.CS1 maint: ref=harv (link )
Gnedin, A. (1994). "A solution to the game of Googol". Annals of Probability. 22(3) : 1588–1595. doi :10.1214/aop/1176988613.CS1 maint: ref=harv (link )
Hill, T.P. "Knowing When to Stop ". American Scientist, Vol. 97, 126-133 (2009). (For French translation, see cover story in the July issue of Pour la Science (2009))
Ketelaar, Timothy; Todd, Peter M. (2001). "Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem". Conceptual Challenges in Evolutionary Psychology. Studies in Cognitive Systems. 27. pp. 179–211. doi :10.1007/978-94-010-0618-7_7. ISBN 978-94-010-3890-4.
Martin Gardner, New Mathematical Diversions from Scientific American. Simon and Schuster, 1966, Chapter 3, Problem 3 [reprints his original column published in February 1960 with additional comments].
Matsui, T; Ano, K (2016). "Lower bounds for Bruss' odds problem with multiple stoppings". Mathematics of Operations Research. 41(2): 700–714. arXiv : 1204.5537. doi :10.1287/moor.2015.0748.CS1 maint: ref=harv (link )
Merrill R. Flood, letter written in 1958, a copy of which can be found in the Martin Gardner papers at Stanford University Archives, series 1, box 5, folder 19.
Miller, Geoffrey F. (2001). The mating mind: how sexual choice shaped the evolution of human nature. Anchor Books. ISBN 978-0-385-49517-2.
Sardelis, Dimitris A.; Valahas, Theodoros M. (March 1999). "Decision Making: A Golden Rule". The American Mathematical Monthly. 106(3): 215. doi :10.2307/2589677. JSTOR 2589677.
Seale, D.A., Rapoport, A. (1997). "Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem'". Organizational Behavior and Human Decision Processes. 69(3): 221–236. doi :10.1006/obhd.1997.2683.CS1 maint: multiple names: authors list (link )
Stein, W.E.; Seale, D.A.; Rapoport, A. (200 3). "Analysis of heuristic solutions to the best choice problem". European Journal of Operational Research. 151: 140–152. doi :10.1016/S0377-2217(02)00601-X.CS1 maint: ref=harv (link )
Vanderbei, R. J. (November 1980). "The Optimal Choice of a Subset of a Population". Mathematics of Operations Research. 5(4): 481–486. doi :10.1287/moor.5.4.481.CS1 maint: ref=harv (link )
Vanderbei, Robert J. (2012). "The postdoc variant of the secretary problem" (PDF). CiteSeerX 10.1.1.366.1718.Cite journal requires |journal=()

External links

OEISsequence A054404 (Number of daughters to wait before picking in sultan's dowry problem with n daughters)
Weisstein, Eric W. "Sultan's Dowry Problem". MathWorld.
Neil Bearden. "Optimal Search (Secretary Problems)". Archived from the original on 4 January 2017.
Optimal Stopping and Applications book by Thomas S. Ferguson