Проблема с секретарем

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

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

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

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

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

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

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

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

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

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

${\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}}\\&={\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$ в качестве предела (r−1) / n , используя t для (i−1) / n и dt для 1/ n , сумму можно аппроксимировать интегралом

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

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

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

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

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

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

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

Ограничения

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

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

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

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

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

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

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

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

(i) доходность для всех $N$ вероятность успеха не менее 1/e,

(ii) является минимаксно-оптимальной стратегией для селектора, который не знает $N$,

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

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

Однако существует множество других стратегий, которые достигают (i) и (ii) и, более того, работают строго лучше, чем стратегия 1/e. одновременно для всех $N$>2. Простым примером является стратегия, которая выбирает (если возможно) первого относительно лучшего кандидата по истечении определенного времени. $\tau$ при условии, что хотя бы один претендент прибыл до этого времени, а в противном случае выбирает (если возможно) второго относительно лучшего кандидата по истечении времени $\tau$.

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

Игра в Гугол

В статье «Кто решил проблему секретаря?» ( Фергюсон , 1989) Утверждается, что задача о секретаре впервые появилась в печати в Мартина Гарднера «Математические игры» в феврале 1960 года колонке в журнале Scientific American :

Попросите кого-нибудь взять столько листов бумаги, сколько ему захочется, и на каждом листе написать разные положительные числа. Числа могут варьироваться от небольших долей 1 до числа размером с гугол (1, за которым следует сотня нулей) или даже больше. Эти листочки переворачивают лицевой стороной вниз и кладут на стол. По одному переворачивайте листочки лицевой стороной вверх. Цель состоит в том, чтобы перестать поворачиваться, когда вы дойдете до числа, которое, по вашему мнению, является самым большим из ряда. Вы не можете вернуться и выбрать ранее перевернутый лист. Если вы перевернете все листы, то, конечно, вам придется выбрать последний перевернутый.

Фергюсон отметил, что игра с секретарем осталась нерешенной, поскольку это игра с нулевой суммой с двумя антагонистическими игроками. В этой игре:

• Алиса, информированный игрок, тайно записывает отдельные числа на $n$ карты.
• Боб, останавливающий игрок, наблюдает за фактическими значениями и может прекратить переворачивать карты, когда захочет, выигрывая, если последняя перевернутая карта имеет общее максимальное число.
• Боб хочет угадать максимальное число с максимально возможной вероятностью, а цель Алисы — сделать эту вероятность как можно более низкой.

Отличий от основной задачи секретаря два:

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

Стратегический анализ

Алиса сначала записывает n чисел, которые затем перемешиваются. Таким образом, их порядок не имеет значения, а это означает, что числа Алисы должны быть заменяемой последовательностью случайных величин. $X_{1},X_{2},...,X_{n}$. Тогда стратегия Алисы заключается в простом выборе самой сложной последовательности случайных величин, которую можно заменить.

Стратегию Боба можно формализовать как правило остановки. $\tau$ для последовательности $X_{1},X_{2},...,X_{n}$.

Мы говорим, что правило остановки $\tau$ для Боба является стратегией остановки относительного ранга тогда и только тогда, когда она зависит только от относительных рангов $X_{1},X_{2},...,X_{n}$, а не от их числовых значений. Другими словами, это как если бы кто-то тайно вмешался после того, как Алиса выбрала свои числа, и изменил каждое число в $X_{1},X_{2},...,X_{n}$ в его относительный ранг (разрыв связей случайным образом). Например, $0.2,0.3,0.3,0.1$ меняется на $2,3,4,1$ или $2,4,3,1$ с равной вероятностью. Это создает впечатление, будто Алиса разыграла заменяемую случайную перестановку на $\{1,2,...,n\}$. Теперь, поскольку единственная заменяемая случайная перестановка на $\{1,2,...,n\}$ это просто равномерное распределение по всем перестановкам на $\{1,2,...,n\}$, оптимальная стратегия остановки относительного ранга — это оптимальное правило остановки для задачи секретаря, приведенной выше, с вероятностью выигрыша $$Pr(X_{\tau }=\max _{i\in 1:n}X_{i})=\max _{r\in 1:n}{\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}$$Цель Алисы тогда состоит в том, чтобы убедиться, что Боб не сможет добиться большего, чем стратегия остановки относительного ранга.

По правилам игры последовательность Алисы должна быть взаимозаменяемой, но для успеха в игре Алиса не должна делать ее независимой. Если Алиса выберет числа независимо от некоторого фиксированного распределения, это позволит Бобу добиться большего. Чтобы увидеть это интуитивно, представьте, что $n=2$, а Алиса должна выбрать оба числа из нормального распределения $N(0,1)$, независимо. Тогда, если Боб перевернет одно число и увидит $-3$, то он вполне уверенно может перевернуть второе число, а если Боб перевернёт одно число и увидит $+3$, то он вполне уверенно сможет выбрать первое число. Алиса может добиться большего, выбрав $X_{1},X_{2}$ которые положительно коррелируют.

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

Существует ли сменная последовательность случайных величин $X_{1},...,X_{n}$, такой, что для любого правила остановки $\tau$, $$Pr(X_{\tau }=\max _{i\in 1:n}X_{i})\leq \max _{r\in 1:n}{\frac {r-1}{n}}\sum _{i=r}^{n}{\frac {1}{i-1}}$$?

Решение

Для $n=2$, если Боб использует оптимальную стратегию остановок относительного ранга, то вероятность победы Боба равна 1/2. Удивительно, но у Алисы нет минимаксной стратегии, что тесно связано с парадоксом Т. Ковера. и парадокс двух конвертов . Конкретно, Боб может использовать эту стратегию: выбрать случайное число. $Y$. Если $X_{1}>Y$, затем выбери $X_{1}$, иначе выбери $X_{2}$. Теперь Боб может выиграть с вероятностью строго больше 1/2. Предположим, что числа Алисы разные, тогда при условии, что $Y\not \in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]$, Боб выигрывает с вероятностью 1/2, но при условии $Y\in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]$, Боб выигрывает с вероятностью 1.

Обратите внимание, что случайное число $Y$ можно выбрать из любого случайного распределения, при условии, что $Y\in [\min(X_{1},X_{2}),\max(X_{1},X_{2})]$ имеет ненулевую вероятность.

Однако для любого $\epsilon >0$, Алиса может построить заменяемую последовательность $X_{1},X_{2}$ такая, что вероятность победы Боба не более $1/2+\epsilon$.

Но для $n>2$, ответ — да: Алиса может выбирать случайные числа (которые являются зависимыми случайными величинами) таким образом, что Боб не сможет играть лучше, чем использовать классическую стратегию остановки, основанную на относительных рангах.

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

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

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

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

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

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

Кардинальный вариант выигрыша

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

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

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

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

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

$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)$ относительно c получаем

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

Обучение в парадигме последовательного поиска частичной информации. Числа отображают ожидаемую ценность кандидатов на основе их относительного ранга (из общего числа m кандидатов, просмотренных на данный момент) на различных этапах поиска. Ожидания рассчитываются на основе случая, когда их значения равномерно распределены между 0 и 1. Информация об относительном ранге позволяет интервьюеру более точно оценивать кандидатов, поскольку они накапливают больше точек данных для их сравнения.

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

Более общая форма этой проблемы, предложенная Пэлли и Кремером (2014). предполагает, что по мере прибытия каждого нового заявителя интервьюер наблюдает за его рангом относительно всех кандидатов, за которыми наблюдалось ранее. Эта модель согласуется с идеей обучения интервьюеров по мере того, как они продолжают процесс поиска, накапливая набор прошлых данных, которые они могут использовать для оценки новых кандидатов по мере их поступления. Преимущество этой так называемой модели частичной информации заключается в том, что решения и результаты, достигнутые с учетом информации об относительном ранге, можно напрямую сравнить с соответствующими оптимальными решениями и результатами, если бы интервьюеру была предоставлена ​​полная информация о ценности каждого заявителя. Эта проблема полной информации, в которой кандидаты выбираются независимо от известного распределения, а интервьюер стремится максимизировать ожидаемую ценность выбранного кандидата, была первоначально решена Мозером (1956): Сакагути (1961), и Карлин (1962).

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

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

Выберите второе лучшее, используя одну попытку

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

Выберите k лучших, используя k попыток.

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

В общем, метод оптимального решения начинается с наблюдения $r=\left\lfloor {\frac {n}{ke^{1/k}}}\right\rfloor$ кандидатов, не выбирая ни одного из них, затем выберите каждого кандидата, который лучше первого $r$ кандидатов, пока у нас не закончатся кандидаты или кандидаты. Если $k$ остается постоянным, пока $n\to \infty$, то вероятность успеха сходится к ${\frac {1}{ek}}$. Вандербей , 1980 , если $k=n/2$, то вероятность успеха равна ${\frac {1}{n/2+1}}$.

Выбирайте лучшее, используя несколько попыток

В этом варианте игроку разрешено $r$ выбор и побеждает, если какой-либо выбор является лучшим. Оптимальная стратегия для этой задачи принадлежит к классу стратегий, определяемых набором пороговых чисел $(a_{1},a_{2},...,a_{r})$, где $a_{1}>a_{2}>\cdots >a_{r}$.

В частности, представьте, что у вас есть $r$ письма о приеме с пометкой $1$ к $r$. У тебя было бы $r$ сотрудники, работающие с заявлениями, каждый из которых имеет по одному письму. Вы продолжаете проводить собеседования с кандидатами и ранжировать их в таблице, которую может видеть каждый специалист по подаче заявлений. Теперь офицер $i$ отправит письмо о принятии первому кандидату, который лучше всех кандидатов $1$ к $a_{i}$. (Неотправленные письма о зачислении по умолчанию передаются последним претендентам, как и в стандартной задаче о секретаре.)

В $n\rightarrow \infty$ лимит, каждый $a_{i}\sim ne^{-k_{i}}$, для некоторого рационального числа $k_{i}$.

Вероятность выигрыша

Когда $r=2$, вероятность выигрыша сходится к $e^{-1}+e^{-{\frac {3}{2}}},(n\rightarrow \infty )$. В более общем смысле, для положительных целых чисел $r$, вероятность выигрыша сходится к $p_{1}+p_{2}+\cdots +p_{r}$, где $p_{i}=\lim _{n\rightarrow \infty }{\frac {a_{i}}{n}}$.

вычислено до $r=4$, с $e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}$.

Мацуи и Ано 2016 дали общий алгоритм. Например, $p_{5}=e^{-{\frac {4162637}{1474560}}}$.

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

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

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

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

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

История

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

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

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

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

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

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

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

См. также

• Проблема с назначением
• Алгоритм шансов
• Оптимальная остановка
• Проблема Роббинса
• Теория поиска
• Проблема стабильного брака

Ссылки

• Берден, Дж. Н. (2006). «Новая задача секретаря с ранговым отбором и кардинальными выплатами». Журнал математической психологии . 50 : 58–9. дои : 10.1016/j.jmp.2005.11.003 .
• Берден, Дж. Н.; Мерфи, РОД; Рапопорт, А. (2005). «Многоатрибутное расширение проблемы секретаря: теория и эксперименты». Журнал математической психологии . 49 (5): 410–425. CiteSeerX   10.1.1.497.6468 . дои : 10.1016/j.jmp.2005.08.002 . S2CID   9186039 .
• Берден, Дж. Нил; Рапопорт, Амнон; Мерфи, Райан О. (сентябрь 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 .
• Флуд, Меррилл Р. (1958). «Доказательство оптимальной стратегии». Письмо Мартину Гарднеру. Документы Мартина Гарднера, серия 1, коробка 5, папка 19: Архив Стэнфордского университета. {{cite press release}}: CS1 maint: местоположение ( ссылка )
• Фриман, PR (1983). «Проблема секретаря и ее расширения: обзор». Международное статистическое обозрение/Revue Internationale de Statistique . 51 (2): 189–206. дои : 10.2307/1402748 . JSTOR   1402748 .
• Гарднер, Мартин (1966). «3». Новые математические развлечения от Scientific American . Саймон и Шустер. [перепечатывает свою оригинальную колонку, опубликованную в феврале 1960 года, с дополнительными комментариями]
• Гирдхар, Йогеш; Дудек, Грегори (2009). «Оптимальная выборка онлайн-данных или как нанять лучших секретарей». 2009 Канадская конференция по компьютерному и роботизированному зрению . стр. 292–298. CiteSeerX   10.1.1.161.41 . дои : 10.1109/CRV.2009.30 . ISBN  978-1-4244-4211-9 . S2CID   2742443 .
• Гилберт, Дж; Мостеллер, Ф (1966). «Распознавание максимума последовательности». Журнал Американской статистической ассоциации . 61 (313): 35–73. дои : 10.2307/2283044 . JSTOR   2283044 .
• Гнедин, А. (1994). «Разгадка игры Гугол» . Анналы вероятности . 22 (3): 1588–1595. дои : 10.1214/aop/1176988613 .
• Гнедин, А. (2021). «Задача о лучшем выборе со случайными поступлениями: как победить стратегию 1/e» . Случайные процессы и их приложения . 145 : 226–240. дои : 10.1016/j.spa.2021.12.008 . S2CID   245449000 .
• Хилл, Т.П. « Знать, когда остановиться ». Американский учёный , Том. 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 .
• Мацуи, Т; Ано, К. (2016). «Нижние оценки проблемы шансов Брусса с несколькими остановками». Математика исследования операций . 41 (2): 700–714. arXiv : 1204.5537 . дои : 10.1287/moor.2015.0748 . S2CID   31778896 .
• Миллер, Джеффри Ф. (2001). Брачный разум: как сексуальный выбор повлиял на эволюцию человеческой природы . Якорные книги. ISBN  978-0-385-49517-2 .
• Сарделис, Димитрис А.; Валахас, Теодорос М. (март 1999 г.). «Принятие решений: золотое правило». Американский математический ежемесячник . 106 (3): 215. дои : 10.2307/2589677 . JSTOR   2589677 .
• Сил, округ Колумбия; Рапопорт, А. (1997). «Последовательное принятие решений с относительными рангами: экспериментальное исследование« проблемы секретаря » ». Организационное поведение и процессы принятия человеческих решений . 69 (3): 221–236. дои : 10.1006/obhd.1997.2683 .
• Штейн, МЫ; Сил, округ Колумбия; Рапопорт, А. (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 дочерьми)
• Вайсштейн, Эрик В. «Проблема приданого султана» . Математический мир .
• Нил Бирден. «Оптимальный поиск (Задачи секретаря)» . Архивировано из оригинала 4 января 2017 года.
• «Оптимальная остановка и применение» Книга Томаса С. Фергюсона