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

[grizzly]

Поискал в любимом сборнике комбинаторных тождеств (ссылка на том 4, но меняя цифру 4 в адресной строке, можно найти и первые 3 тома). Там эта формула дана под номером (6.97) и получается какой-то трансформацией из обобщённой свёртки Вандермонда. На вид она выглядит не так устрашающе, но что-то мне перехотелось её доказывать :)

[lel0lel]

grizzly

(Оффтоп)

Большое спасибо за сборник тождеств, очень полезная ссылка. На некоторое время возьму паузу -- при рассмотрении случая равномерного распределения весов и больших $n$ возникли временные трудности. Предварительно картина вырисовывается такая, что для $n=100$ стратегия предложенная Вами оказывается очень близкой к оптимальной. В следующем году постараюсь рассказать о результатах более ясно.

[lel0lel]

Хочется рассказать о стратегии, максимизирующей вес жениха для следующего распределения весов: $(p_1,1), (p_2,2),\ldots,(p_{100},100).$ Стратегия определяется ста параметрами остановки выбора: $a_1,a_2,\ldots,a_{100}$. Смысл этих параметров в следующем: $a_1$ указывает с какого по счету кандидата следует (выбирать) останавливаться на самом лучшем среди просмотренных ранее, $a_2$ -- параметр остановки для второй с конца позиции в позиционном списке просмотренных кандидатов. Можно заметить, что в случае оптимальной стратегии можно выбрать $a_{50}=\ldots=a_{100}=100$. Другими словами, если текущий кандидат занимает 50-ую или более позицию с конца позиционного списка, то его брать не следует, кроме случая когда за ним других кандидатов больше нет (т.е. когда он последний в очереди). Пояснение здесь такое: следующий кандидат с вероятностью большей (или равной в случае если текущий кандидат предпоследний) чем 1/2 займёт в позиционном списке более высокую позицию. Численные эксперименты подтверждают это утверждение.

Далее я генерировал случайные наборы параметров остановки (также проверял тривиальные, например $a_1=\ldots=a_{100}=100$), затем эти параметры нужно варьировать и выбирать такие их вариации, которые приводят к наибольшему ожидаемому весу (формула для которого получена выше), это приведёт к нахождению локального максимума ожидаемого веса. Хотя строго доказательства оптимальности получаемой стратегии (определяемой найденными параметрами остановки) я не нашёл, но есть уверенность, что получается именно оптимальная. Дело в том, что для $n<25$ я проверил результаты, получаемые численным поиском максимума, с результатами, получаемыми полным перебором всевозможных стратегий. Также заметил, что численный поиск (он завершается когда ожидаемый вес перестаёт возрастать) всегда приводит к решению с одним и тем же ожидаемым весом, вне зависимости от начального набора параметров остановки.

Для оптимальной стратегии параметры остановки $(a_1,a_2,\ldots,a_{100})$:

(28, 48, 60, 68, 74, 78, 81, 83, 85, 87, 88, 90, 91, 91, 92, 93, 93, 
94, 94, 95, 95, 96, 96, 96, 96, 97, 97, 97, 97, 97, 98, 98, 98, 98, 
98, 98, 98, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 100, 100, 
100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 
100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 
100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 
100, 100, 100, 100, 100, 100, 100)

В переводе: первых 27 пропускаем, с 28 начинаем соглашаться на лучшего; с 48 ещё начинаем соглашаться на второго по лучшести и так далее. При такой стратегии ожидаемый вес равен

$$ \mathoperator{E}(W/S)=\frac{890068375249377435276407336006408473}{9138582027089704342317513701352000}\approx97.4 $$

Это лишь немного улучшает результат

grizzly в сообщении #1363485 писал(а):

Добился среднего 97,25 и это примерно потолок для такой стратегии.

[mustang]

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

Понятно, что первыми никто быть не хочет, поэтому будем считать, что среди женихов демократия - место (порядок) каждого определяется голосованием всех.

Ну и, каждый жених оценивает конкурента относительно себя также, как и невеста (лучше или хуже).

Смогут женихи выстроиться в ряд?

А если они оценивают конкурентов с вероятностью ошибки $p$? Скажем, $p=0.25$

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

P.S. В "мальчиковой" терминологии исходная задача — стратегия призывника на призывном пункте: приезжают представители в/ч и нужно соглашаться на службу в данной в/ч. Предлагают один раз и дать ответ надо сразу. Априорных знаний о том, какие "покупатели" приедут - нет, служить уедешь в любом случае

[lel0lel]

Внимательно посмотрел литературу по теме. Оказалось, что всё уже украдено до нас. Задача с равномерным распределением весов (absolute ranks) рассматривалась Chow, Moriguti, Robbins, Samuels (1964) (Chow et al.) и была решена в случае больших $n$. Небольшое отличие от обсуждаемой нами задачи в том, что в статье минимизируется ожидаемый "the absolute rank of the person selected". Понятно почему это удобно: так как вычисляется предел ожидаемого ранка секретаря (или жениха) при $n\to\infty$, то в случае минимизации он оказывается конечной величиной. Впрочем, в нашем случае в рассматриваемом пределе конечной величиной будет ожидаемое отклонение от максимально возможного веса равного $n$, поэтому приведу ответ из работы, но в наших терминах:

$$\lim_{n\to\infty} \left(n-\operatorname{E}[W/S_{\text{opt}}(n)]\right)=-1+\prod\limits_{j=1}^{\infty}\left(\frac{j + 2}{j}\right)^{1/(j + 1)}\cong 2.8695$$

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

[grizzly]

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

А я всё пытался придумать более жизненную постановку задачи, но закрутился с делами и не довёл до ума. Вполне естественно, кажется, добавить к задаче всего пару условий: (а) каждое тестирование кандидата имеет цену (время, деньги, другие ресурсы) и (б) при выборе кандидата разрешено вернуться на $k$ шагов назад. То есть мы не обязаны сразу дать положительный или отрицательный ответ кандидату, а всегда можем выбирать среди $k$ последних (считаем, что более ранние к этому времени уже женятся / находят работу).

Учитывать второе условие я ещё не пробовал, но вот с первым получается что-то не совсем понятное. Мне кажется, что если стоимость оценки кандидата будет реалистичной, то наилучшей стратегией становится такая: посмотреть одного кандидата и при следующих просмотрах взять первого же, который оказался лучше предыдущего. Только это всё были прикидки на коленке, довести до конца которые у меня пока нет возможности. Но я чуть позже вернусь к такой постановке задачи (и, может, ещё со вторым условием что-то придумаю).