2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4
 
 Re: Задача о разборчивой невесте
Сообщение27.12.2018, 19:03 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение28.12.2018, 02:06 
Заслуженный участник


20/04/10
2048
grizzly

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение07.01.2019, 17:55 
Заслуженный участник


20/04/10
2048
Хочется рассказать о стратегии, максимизирующей вес жениха для следующего распределения весов: $(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 и это примерно потолок для такой стратегии.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение08.01.2019, 00:34 


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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение19.01.2019, 18:39 
Заслуженный участник


20/04/10
2048
Внимательно посмотрел литературу по теме. Оказалось, что всё уже украдено до нас. Задача с равномерным распределением весов (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$$
По-моему очень красивый результат, не уступающий своим изяществом классической проблеме. Также формула для ожидаемого веса уже встречается в упомянутой работе, хотя и не выписывается для общего случая явно. В более поздних работах можно найти её в явном виде.

 Профиль  
                  
 
 Re: Задача о разборчивой невесте
Сообщение20.01.2019, 02:01 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 51 ]  На страницу Пред.  1, 2, 3, 4

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group