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
1776
grizzly

(Оффтоп)

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

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


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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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