Проблема секретаря - Secretary problem

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

В проблема секретаря проблема, которая демонстрирует сценарий, включающий оптимальная остановка теория.^[1] Проблема широко изучалась в области прикладная вероятность, статистика, и теория принятия решений. Он также известен как проблема брака, то проблема приданого султана, то проблема суетливого жениха, то гугол игра, а проблема лучшего выбора.

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

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

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

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

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

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

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

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

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

Сумма не определена для р = 1, но в этом случае единственно возможной политикой является выбор первого заявителя и, следовательно, п(1) = 1/п. Эта сумма получается с учетом того, что если заявитель я является лучшим соискателем, то он выбирается тогда и только тогда, когда лучший соискатель среди первых я - 1 претендент в числе первых р - 1 заявка была отклонена. Сдача п стремятся к бесконечности, пишут ${\displaystyle x}$ как предел (г-1)/п, с помощью т за (i-1)/п и dt для 1 /п, сумму можно аппроксимировать интегралом

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

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

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

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

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

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

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

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

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

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

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

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

Суть модели основана на идее, что жизнь последовательна и что проблемы реального мира возникают в реальном времени. Кроме того, легче оценить время, в которое конкретные события (прибытие кандидатов) должны происходить чаще (если они происходят), чем оценить распределение числа конкретных событий, которые произойдут. Эта идея привела к следующему подходу, так называемому единый подход (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 / электронная стратегия, имеет следующие свойства:

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

(i) урожайность для всех ${\displaystyle N}$ вероятность успеха не менее 1 / е,

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

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

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

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

Игра в гугол

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

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

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

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

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

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

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

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

У каждой эвристики есть единственный параметр y. На рисунке (показан справа) показаны ожидаемые вероятности успеха для каждой эвристики в зависимости от y для проблем с п = 80.

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

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

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

Поскольку ценности заявителя равны i.i.d. вытекает из равномерного распределения на [0, 1], ожидаемое значение из т-й заявитель, учитывая, что ${\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}$, на котором интервьюер должен начать прием кандидатов. Бирден 2006 показало, что c либо ${\displaystyle \lfloor {\sqrt {n}}\rfloor }$ или же ${\displaystyle \lceil {\sqrt {n}}\rceil }$. (Фактически, то, что ближе всего к ${\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 {\frac {0.25n^{2}}{n(n-1)}}}$. Эта вероятность стремится к 1/4, поскольку n стремится к бесконечности, что свидетельствует о том, что легче выбрать лучшее, чем второе из лучших.

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

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

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

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

Гилберт и Мостеллер показали, что ${\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 )}$.Для дальнейших случаев, когда ${\displaystyle r=5,6,...,10}$, видеть Мацуи и Ано 2016 (Например ${\displaystyle {\frac {a_{5}}{n}}\rightarrow e^{-{\frac {4162637}{1474560}}}}$).

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

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

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

Нейронные корреляты

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

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

История

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

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

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

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

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

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

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

Смотрите также

• Проблема с присвоением
• Алгоритм коэффициентов
• Оптимальная остановка
• Проблема Роббинса
• Теория поиска
• Проблема стабильного брака

Примечания

1. Хилл, Теодор П. (2009). «Зная, когда остановиться». Американский ученый. 97 (2): 126–133. Дои:10.1511/2009.77.126. ISSN  1545-2786 - via (Французский перевод см. история на обложке в июльском номере Pour la Science (2009)).
2. Фергюсон, Томас С. (Август 1989 г.). «Кто решил проблему с секретарем?». Статистическая наука. 4 (3): 282–289. CiteSeerX  10.1.1.700.6129. Дои:10.1214 / сс / 1177012493. JSTOR  2245639.
3. Бирден, Мерфи и Рапопорт, 2006 г .; Бирден, Рапопорт и Мерфи, 2006 г .; Сил и Рапопорт, 1997 г.
4. Shadlen, M. N .; Ньюсом, У. Т. (23 января 1996 г.). «Восприятие движения: видение и решение». Труды Национальной академии наук. 93 (2): 628–633. Bibcode:1996ПНАС ... 93..628С. Дои:10.1073 / пнас.93.2.628. ЧВК  40102. PMID  8570606.
5. Ройтман, Джейми Д.; Шадлен, Майкл Н. (1 ноября 2002 г.). «Ответ нейронов в латеральной интрапариетальной области во время комбинированной задачи на время реакции визуальной дискриминации». Журнал неврологии. 22 (21): 9475–9489. Дои:10.1523 / JNEUROSCI.22-21-09475.2002. ЧВК  6758024. PMID  12417672.
6. Heekeren, Hauke ​​R .; Марретт, Шон; Унгерлейдер, Лесли Г. (9 мая 2008 г.). «Нейронные системы, которые опосредуют человеческое восприятие принятия решений». Обзоры природы Неврология. 9 (6): 467–479. Дои:10.1038 / номер 2374. PMID  18464792.
7. Costa, V.D .; Авербек, Б. Б. (18 октября 2013 г.). «Фронтально-теменная и лимбико-полосатая активность лежит в основе выборки информации в задаче наилучшего выбора». Кора головного мозга. 25 (4): 972–982. Дои:10.1093 / cercor / bht286. ЧВК  4366612. PMID  24142842.
8. Кессельхейм, Томас; Радке, Клаус; Тоннис, Андреас; Фёкинг, Бертольд (2013). "Оптимальный онлайн-алгоритм для взвешенного двустороннего сопоставления и расширений комбинаторных аукционов". Алгоритмы - ESA 2013. Конспект лекций по информатике. 8125. С. 589–600. Дои:10.1007/978-3-642-40450-4_50. ISBN  978-3-642-40449-8.

Рекомендации

• Бирден, Дж. (2006). «Новая задача секретаря с отбором на основе ранга и кардинальными выплатами». Журнал математической психологии. 50: 58–9. Дои:10.1016 / j.jmp.2005.11.003.
• Bearden, J.N .; Мерфи, R.O .; Рапопорт, А. (2005). «Мульти-атрибутное расширение задачи секретаря: теория и эксперименты». Журнал математической психологии. 49 (5): 410–425. CiteSeerX  10.1.1.497.6468. Дои:10.1016 / j.jmp.2005.08.002.
• Бирден, Дж. Нил; Рапопорт, Амнон; Мерфи, Райан О. (сентябрь 2006 г.). «Последовательное наблюдение и отбор с выплатами, зависящими от ранга: экспериментальное исследование». Наука управления. 52 (9): 1437–1449. Дои:10.1287 / mnsc.1060.0535.
• Брюсс, Ф. Томас (Июнь 2000 г.). «Суммируйте шансы на единицу и остановитесь». Анналы вероятности. 28 (3): 1384–1391. Дои:10.1214 / aop / 1019160340.
• Брюсс, Ф. Томас (Октябрь 2003 г.). «Заметка об оценках теоремы о вероятностях оптимальной остановки». Анналы вероятности. 31 (4): 1859–1961. Дои:10.1214 / aop / 1068646368.
• Брюсс, Ф. Томас (август 1984 г.). «Единый подход к классу задач наилучшего выбора с неизвестным числом вариантов». Анналы вероятности. 12 (3): 882–889. Дои:10.1214 / aop / 1176993237.
• Фергюсон, Томас С. (август 1989 г.). "Кто решил проблему с секретарем?". Статистическая наука. 4 (3): 282–289. Дои:10.1214 / сс / 1177012493.
• Фриман, П.Р. (1983). «Проблема секретаря и ее расширения: обзор». Международный статистический обзор / Revue Internationale de Statistique. 51 (2): 189–206. Дои:10.2307/1402748. JSTOR  1402748.
• Гирдхар, Йогеш; Дудек, Грегори (2009). «Оптимальная выборка данных в Интернете или как нанять лучших секретарей». 2009 Канадская конференция по компьютерному зрению и зрению роботов. С. 292–298. CiteSeerX  10.1.1.161.41. Дои:10.1109 / CRV.2009.30. ISBN  978-1-4244-4211-9.
• Гилберт, Дж; Мостеллер, Ф (1966). «Распознавание максимума последовательности». Журнал Американской статистической ассоциации. 61 (313): 35–73. Дои:10.2307/2283044. JSTOR  2283044.
• Гнедин, А. (1994). «Решение игры в Гугол». Анналы вероятности. 22 (3): 1588–1595. Дои:10.1214 / aop / 1176988613.
• Хилл, Т. "Зная, когда остановиться ". Американский ученый, Vol. 97, 126-133 (2009). (Французский перевод см. история на обложке в июльском номере Pour la Science (2009))
• Кетелаар, Тимофей; Тодд, Питер М. (2001). «Обрамление наших мыслей: экологическая рациональность как ответ эволюционной психологии на рамочную проблему». Концептуальные вызовы эволюционной психологии. Исследования когнитивных систем. 27. С. 179–211. Дои:10.1007/978-94-010-0618-7_7. ISBN  978-94-010-3890-4.
• Мартин Гарднер, Новые математические отклонения от журнала Scientific American. Саймон и Шустер, 1966, глава 3, проблема 3 [перепечатывает свою оригинальную колонку, опубликованную в феврале 1960 года, с дополнительными комментариями].
• Мацуи, Т; Ано, К. (2016). «Нижние оценки проблемы шансов Брюсса с множественными остановками». Математика исследования операций. 41 (2): 700–714. arXiv:1204.5537. Дои:10.1287 / moor.2015.0748.
• Меррил Р. Флад, письмо, написанное в 1958 году, копию которого можно найти в бумагах Мартина Гарднера в Архиве Стэнфордского университета, серия 1, вставка 5, папка 19.
• Миллер, Джеффри Ф. (2001). Брачный разум: как сексуальный выбор повлиял на эволюцию человеческой природы. Якорные книги. ISBN  978-0-385-49517-2.
• Sardelis, Dimitris A .; Валахас, Теодорос М. (март 1999 г.). «Принятие решений: золотое правило». Американский математический ежемесячник. 106 (3): 215. Дои:10.2307/2589677. JSTOR  2589677.
• Сил, Д.А.; Рапопорт, А. (1997). «Последовательное принятие решений с относительными рангами: экспериментальное исследование« проблемы секретаря ».'". Организационное поведение и процессы принятия решений людьми. 69 (3): 221–236. Дои:10.1006 / obhd.1997.2683.
• Stein, W.E .; Сил, Д.А.; Рапопорт, А. (2003). «Анализ эвристических решений задачи наилучшего выбора». Европейский журнал операционных исследований. 151: 140–152. Дои:10.1016 / S0377-2217 (02) 00601-X.
• Вандербей, Р. Дж. (Ноябрь 1980 г.). «Оптимальный выбор подмножества населения». Математика исследования операций. 5 (4): 481–486. Дои:10.1287 / moor.5.4.481.
• Вандербей, Роберт Дж. (2012). «Постдокторский вариант задачи секретаря» (PDF). CiteSeerX  10.1.1.366.1718.

внешняя ссылка

• OEIS последовательность A054404 (Число дочерей, которым нужно подождать, прежде чем решать проблему приданого султана с n дочерьми)
• Вайсштейн, Эрик В. "Проблема приданого султана". MathWorld.
• Нил Бирден. «Оптимальный поиск (задачи секретаря)». Архивировано из оригинал 4 января 2017 г.
• Оптимальная остановка и приложения книга Томаса С. Фергюсона