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

Математическая задача, связанная с теорией оптимальной остановки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

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

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

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

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

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

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

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

Игра в Гугол

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

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

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

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

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

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

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

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

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

Мы говорим, что правило остановки для Боба является стратегией остановки относительного ранга , если оно зависит только от относительных рангов , а не от их числовых значений. Другими словами, это как если бы кто-то тайно вмешался после того, как Алиса выбрала свои числа, и изменил каждое число на его относительный ранг (случайным образом разрывая связи). Например, изменяется на или с равной вероятностью. Это создает впечатление , будто Алиса разыграла заменяемую случайную перестановку на . Теперь, поскольку единственная заменяемая случайная перестановка на - это просто равномерное распределение по всем перестановкам на , оптимальная стратегия остановки относительного ранга - это оптимальное правило остановки для задачи секретаря, приведенной выше, с вероятностью выигрыша. ${\displaystyle \tau }$ ${\displaystyle X_{1},X_{2},...,X_{n}}$ ${\displaystyle X_{1},X_{2},...,X_{n}}$ ${\displaystyle 0.2,0.3,0.3,0.1}$ ${\displaystyle 2,3,4,1}$ ${\displaystyle 2,4,3,1}$ ${\displaystyle \{1,2,...,n\}}$ ${\displaystyle \{1,2,...,n\}}$ ${\displaystyle \{1,2,...,n\}}$

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

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

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

Существует ли заменяемая последовательность случайных величин , такая что для любого правила остановки ${\displaystyle X_{1},...,X_{n}}$ ${\displaystyle \tau }$

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

?

Решение

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

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

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

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

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

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

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

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

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

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

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

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

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

Поскольку значения заявителя равны iid, они получены из равномерного распределения на [0, 1], ожидаемое значение t -го заявителя определяется выражением ${\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}}.}$

Как и в классической задаче, оптимальная политика задается порогом, который для этой задачи мы обозначим через , при котором интервьюер должен начать прием кандидатов. Берден показал, что c равно либо или . ^[8] (Фактически, в зависимости от того, что ближе всего к .) Это следует из того факта, что при наличии проблемы с заявителями ожидаемый выигрыш для некоторого произвольного порога равен ${\displaystyle 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}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

^[16] рассчитано до , при . ${\displaystyle r=4}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}$

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

• Экономический портал
• Математический портал

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

Примечания

1. Фергюсон, Томас С. (август 1989 г.). «Кто решил проблему секретаря?». Статистическая наука . 4 (3): 282–289. дои : 10.1214/ss/1177012493 .
2. Хилл, Теодор П. (2009). «Знать, когда остановиться». Американский учёный . 97 (2): 126–133. дои : 10.1511/2009.77.126. ISSN  1545-2786. S2CID  124798270.Перевод на французский язык см. на обложке июльского номера журнала Pour la Science (2009).
3. Томсон, Джонни (21 апреля 2022 г.). «Математики предлагают «правило 37%» для самых важных решений в вашей жизни». Большое Думай . Проверено 6 февраля 2024 г.
4. Гнедин 2021.
5. Гарднер 1966.
6. Обложка, Томас М. (1987), Обложка, Томас М.; Гопинат Б. (ред.), «Выберите наибольшее число», Открытые проблемы коммуникации и вычислений , Нью-Йорк, Нью-Йорк: Springer, стр. 152–152, doi : 10.1007/978-1-4612-4808-8_43, ISBN 978-1-4612-4808-8, получено 25 июня 2023 г.
7. Гнедин 1994.
8. Берден 2006.
9. Палли, Аса Б.; Кремер, Мирко (8 июля 2014 г.). «Последовательный поиск и обучение на основе ранговой обратной связи: теория и экспериментальные данные». Наука управления . 60 (10): 2525–2542. дои : 10.1287/mnsc.2014.1902. ISSN  0025-1909.
10. Мозер, Лео (1956). «О задаче Кэли». Скриптовая математика . 22 : 289–292.
11. Сакагути, Минору (1 июня 1961 г.). «Динамическое программирование некоторой последовательной схемы выборки». Журнал математического анализа и приложений . 2 (3): 446–466. дои : 10.1016/0022-247X(61)90023-3 . ISSN  0022-247X.
12. Роуз, Джон С. (1982). «Отбор неэкстремальных кандидатов из случайной последовательности». Дж. Оптим. Теория Прикл . 38 (2): 207–219. дои : 10.1007/BF00934083. ISSN  0022-3239. S2CID  121339045.
13. Шайовский, Кшиштоф (1982). «Оптимальный выбор объекта a-го ранга». Математика Стосована . Annales Societatis Mathematicae Polonae, серия III. 10 (19): 51–65. дои : 10.14708/ma.v10i19.1533. ISSN  0137-2890.
14. Вандербей, Роберт Дж. (21 июня 2021 г.). «Постдок вариант задачи о секретаре». Приложение Математика . Annales Societatis Mathematicae Polonae, серия III. 49 (1): 3–13. дои : 10.14708/ma.v49i1.7076. ISSN  2299-4009.{{cite journal}}: CS1 maint: date and year (link)
15. Гирдхар и Дудек 2009.
16. Гилберт и Мостеллер 1966.
17. Мацуи и Ано 2016.
18. Берден, Мерфи и Рапопорт, 2006; Берден, Рапопорт и Мерфи, 2006 г.; Сил и Рапопорт, 1997 г.; Пэлли и Кремер, 2014 г.
19. Шадлен, Миннесота; Ньюсом, WT (23 января 1996 г.). «Восприятие движения: видеть и решать». Труды Национальной академии наук . 93 (2): 628–633. Бибкод : 1996PNAS...93..628S. дои : 10.1073/pnas.93.2.628 . ПМК 40102 . ПМИД  8570606. 
20. Ройтман, Джейми Д.; Шадлен, Майкл Н. (1 ноября 2002 г.). «Реакция нейронов латеральной внутритеменной области во время комбинированной задачи на время реакции зрительной дискриминации». Журнал неврологии . 22 (21): 9475–9489. doi : 10.1523/JNEUROSCI.22-21-09475.2002. ПМК 6758024 . ПМИД  12417672. 
21. Хикерен, Хауке Р.; Марретт, Шон; Унгерлейдер, Лесли Г. (9 мая 2008 г.). «Нервные системы, которые опосредуют процесс принятия решений человеком». Обзоры природы Неврология . 9 (6): 467–479. дои : 10.1038/nrn2374. PMID  18464792. S2CID  7416645.
22. Коста, В.Д.; Авербек, BB (18 октября 2013 г.). «Лобно-теменная и лимбически-полосатая активность лежит в основе выборки информации в задаче наилучшего выбора». Кора головного мозга . 25 (4): 972–982. doi : 10.1093/cercor/bht286. ПМК 4366612 . ПМИД  24142842. 
23. Наводнение 1958 года.
24. Гарднер 1966, Задача 3.
25. Брюсс 1984.
26. Фергюсон 1989.
27. Кессельхайм, Томас; Радке, Клаус; Тённис, Андреас; Фёкинг, Бертольд (2013). «Оптимальный онлайн-алгоритм для взвешенного двустороннего сопоставления и расширения комбинаторных аукционов». Алгоритмы – ЕКА 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.
• Берден, Дж. Н.; Мерфи, РОД; Рапопорт, А. (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: location (link)
• Фриман, 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. doi : 10.1006/obhd.1997.2683.
• Штейн, МЫ; Сил, округ Колумбия; Рапопорт, А. (2003). «Анализ эвристических решений задачи наилучшего выбора». Европейский журнал операционных исследований . 151 : 140–152. дои : 10.1016/S0377-2217(02)00601-X.
• Вандербей, Р.Дж. (ноябрь 1980 г.). «Оптимальный выбор подмножества населения». Математика исследования операций . 5 (4): 481–486. дои : 10.1287/мор.5.4.481.
• Вандербей, Роберт Дж. (2012). Постдок-вариант задачи секретаря (PDF) (Отчет). CiteSeerX  10.1.1.366.1718 .

Внешние ссылки

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

Примечания

1. импортировать  numpy  как  np, импортировать  pandas  как  pd# Определите функцию, для которой вы хотите найти максимальную функцию def  ( r , n ): if r == 1 : return 0 else : return ( r - 1 ) / n * np . сумма ([ 1 / ( i - 1 ) для i в диапазоне ( r , n + 1 )])                         # Определите функцию для решения проблемы для конкретного n defsolve (  n ) : значения = [ func ( r , n ) for r в диапазоне ( 1 , n + 1 )] r_max = np . argmax ( значения ) + 1 возвращает r_max , значения [ r_max - 1 ]                   # Определите функцию для печати результатов в виде таблицы Markdown def  print_table ( n_max ):  # Подготовьте данные для таблицы  data  =  [ solve ( n )  for  n  in  range ( 1 ,  n_max + 1 )]  df  =  pd . DataFrame ( данные ,  столбцы = [ 'r' ,  'Максимальное значение' ],  индекс = диапазон ( 1 ,  n_max + 1 ))  df . индекс . имя  =  'н'  # Конвертируем DataFrame в Markdown и печатаем  print ( df.transpose ( ) . to_markdown ( ))# Распечатаем таблицу для n от 1 до 10 print_table ( 10 )