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

[grizzly]

wrest в сообщении #1362423 писал(а):

то никакого матожидания невеста вычислять не может.

Так ведь она считать вообще не умеет. Для того здесь у неё советники, которые посчитают и предложат оптимальную стратегию :)

Спасибо за анализ! Я предполагал, что для реальной жизни лучше пропускать раза в 3 меньше, чем 37%, но вот что не в 3, а в 5 -- это немного неожиданно.

Посмотрите ещё, пжл, симметричный случай в стратегии "пан или пропал": дополнительная премия за выбор самого лучшего -- $+100$, штраф за одинокость -- $-100$. Думаю, что это ничего не меняет, но всё же.

[wrest]

worm2 в сообщении #1362429 писал(а):

Невеста легко избавится от сколь угодно большого штрафа, просто выйдя за последнего :)

Да, если она может действовать иначе чем "пропустить $n$ первых, затем выйти за лучшего из предыдущих."
Я думаю, что можно это правило поведения снять.

Но нужно оставить правило, что невесте сообщается не рейтинг, и даже не порядок в рейтинге (этот был "5-м по лучшести, этот 8-м"), а только результат сравнения текущего жениха с уже отброшенными на предмет превосходства его рейтинга над всеми остальными. Тогда у невесты могут появляться стратегии "выйти за 1-го лучшего из предыдущих", "выйти за 2-го лучшего из предыдущих", "если совсем не повезло, то выйти за последнего из стоящих в очереди".

-- 19.12.2018, 13:58 --

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

Посмотрите ещё, пжл, симметричный случай в стратегии "пан или пропал": дополнительная премия за выбор самого лучшего -- $+100$, штраф за одинокость -- $-100$. Думаю, что это ничего не меняет, но всё же.

Пропустить надо будет 7 или 8, средний рейтинг будет 100,1 (точнее сказать не могу -- это на выборке 100 000 перестановок женихов на каждое количество пропущенных).

[grizzly]

wrest в сообщении #1362433 писал(а):

Пропустить надо будет 7 или 8

Спасибо, я был уверен, что ничего не изменится, но думать было лень :)

[Legioner93]

wrest
Всё, я ваше замечание понял. Вы правы! Выбор весов (рейтингов) лучшего жениха, жениха на втором месте, и т.д., произволен. И от выбора этих весов (рейтингов) будет зависеть мат. ожидание.

Один из вариантов -- взять линейный вес, т.е. соответствующий месту. Тогда лучший жених наделяется весом в $100$, второй $99$, и так далее.
Тогда выбор второго жениха, по мнению невесты, будет не сильно хуже, чем выбор самого лучшего. А выбор самого худшего будет в $100$ раз хуже, чем выбор лучшего. В принципе -- разумно.

Можно также попробовать взять веса (рейтинги) от $-49$ до $50$.

Другой, предельный случай -- присвоить лучшему жениху вес в $10^{100}$, а остальным около нуля. Тогда максимизация мат. ожидания и будет означать стратегию выбора лучшего жениха, и это мат. ожидание будет $0.37 \cdot 10^{100}$

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

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

[wrest]

Legioner93 в сообщении #1362446 писал(а):

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

Ну понимаете, у одного много денег, другой умнее всех, третий сильнее, четвертый красивее и т.п. Тут могут быть сложности.

[lel0lel]

Legioner93 в сообщении #1362446 писал(а):

Выбор весов (рейтингов) лучшего жениха, жениха на втором месте, и т.д., произволен. И от выбора этих весов (рейтингов) будет зависеть мат. ожидание.

Мат. ожидание зависеть будет, а вот стратегия невесты по оптимизации этого мат. ожидания не будет. Так как невеста не знает рейтингов женихов, она лишь способна расположить уже рассмотренных кандидатов в порядке возрастания рейтинга. Поэтому для неё кандидат с рейтингом $10^6$ будет всего лишь лучше всех ранее рассмотренных, если у них были рейтинги порядка $100$. Кроме того, за этим кандидатом возможно будет другой с рейтингом $10^9$. Не очень жизненно, зато соответствует условию - "лучше или хуже".

[grizzly]

Legioner93 в сообщении #1362446 писал(а):

реалистичная раздача рейтингов

Реалистичная раздача рейтингов превратит оценивание невестой в нетранзитивное отношение и задача в такой формулировке вообще потеряет смысл.

[mihaild]

lel0lel в сообщении #1362450 писал(а):

Мат. ожидание зависеть будет, а вот стратегия невесты по оптимизации этого мат. ожидания не будет

Будет.
Два вырожденных примера: вес лучшего $1$, вес остальных $0$ - надо максимизировать шансы выбрать лучшего. Вес худшего $0$, вес остальных $1$ - надо максимизировать шансы не выбрать худшего (для этого вроде бы оптимально взять первого, который лучше кого-то из уже рассмотренных - проигрываем только в случае отсортированной по убыванию перестановки; а хотя бы на одной перестановке мы в любом случае проиграем).

[wrest]

lel0lel в сообщении #1362450 писал(а):

Мат. ожидание зависеть будет, а вот стратегия невесты по оптимизации этого мат. ожидания не будет.

Будет, конечно.

lel0lel в сообщении #1362450 писал(а):

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

Не всех. Если три подряд жениха оказались "не лучше предыдущих", то кто из трех лучше а кто хуже остается неизвестным. В оригинальной задаче невеста получает только ответы "да: этот лучше предыдущих" и "нет: этот не лучше предыдущих".

[mihaild]

wrest в сообщении #1362464 писал(а):

В оригинальной задаче невеста получает только ответы "да: этот лучше предыдущих" и "нет: этот не лучше предыдущих".

Alise в сообщении #1362117 писал(а):

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

Я бы это трактовал как "для текущего кандидата $x$ и любого из предыдущих $y$ известно, кто из $x$ и $y$ лучше".
Впрочем, можно просто сформулировать две разных задачи.

[lel0lel]

Пусть число претендентов $n$. Это число, конечно, должно быть известно невесте, иначе, ни о какой стратегии говорить не придётся. Стратегия невесты эквивалентна выбору правила, с помощью которого на основании номера кандидата и его позиции в рейтинге просмотренных кандидатов она делает выбор (0-отклонить; 1-приголубить). Другими словами стратегия это последовательность последовательностей из единичек и нулей. Пусть $F_{n}(k,r)$ может иметь значения 1 или 0, здесь $k, r$ натуральные числа такие что $k\leq n$ (это номер просматриваемого кандидата) и $r\leq k$ (его позиция в текущем рейтинге). Считаем, что если $r=k$ это самый высокий (лучше всех) в рейтинге. Случай $n=1$ тривиален, стратегия невесты $F_1(1,1)=1$. Случай $n=2$, тут возможны две стратегии тождественные с точки зрения оптимизации мат. ожидания; первая это $F_2(1,1)=1$, вторая $F_2(1,1)=0, F_2(2,1)=F_2(2,2)=1$. Среднее значение рейтинга жениха получится $(p_1+p_2)/2$, но всё же невесте лучше посоветовать выбрать первую стратегию, чтобы потом локти не кусала. Случай $n=3$, не перебирал все стратегии, но на мой взгляд максимум мат. ожидания даст следующая $F_3(1,1)=0, F_3(2,1)=0, F_3(2,2)=1, F_3(3,1)=F_3(3,2)=F_3(3,3)=1$. Мат. ожидание $1/6p_1+2/6p_2+3/6p_3$, где $p_1<p_2<p_3$.

mihaild в сообщении #1362458 писал(а):

Будет.
Два вырожденных примера: вес лучшего $1$, вес остальных $0$ - надо максимизировать шансы выбрать лучшего.

Невеста же не знает изначально ничего о рейтингах.

[mihaild]

lel0lel в сообщении #1362467 писал(а):

Стратегия невесты эквивалентна выбору правила, с помощью которого на основании номера кандидата и его позиции в рейтинге просмотренных кандидатов она делает выбор (0-отклонить; 1-приголубить).

Можно же еще учитывать перестановку предыдущих (это скорее всего не поможет, но как строго доказать - не знаю).

lel0lel в сообщении #1362467 писал(а):

Невеста же не знает изначально ничего о рейтингах.

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

[DeBill]

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

[EUgeneUS]

DeBill
В википедии пишут что в докторской БАБ рассматривал обобщения задачи.

[lel0lel]

wrest в сообщении #1362464 писал(а):

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

Всё же я предпочту придерживаться формулировки:

Alise в сообщении #1362117 писал(а):

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

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

mihaild в сообщении #1362468 писал(а):

Можно же еще учитывать перестановку предыдущих

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

mihaild в сообщении #1362468 писал(а):

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

Конечно, согласен с вами, но с другой стороны ведь нехорошо вот так взять и оставить барышню наедине с проблемой. Поэтому замечу, что для случая трёх кандидатов (уже не тривиальный случай) максимизирующая стратегия есть, это $S=\left\lbrace(0),(0,1),(1,1,1)\right\rbrace$; другими словами - первого отклоняет, за второго выходит если он лучше первого, иначе идёт за третьего какой бы он ни был. Далее, с ростом числа кандидатов число стратегий, которые можно посоветовать невесте будет возрастать, как вы заметили та или иная стратегия будет побеждать при определенных условиях накладываемых на рейтинги кандидатов. Можно выбрать любую модель распределения рейтингов (например, как выше предлагалось, нормальное распределение) и в рамках этой модели посчитать с какой вероятностью следует пользоваться той или иной стратегией. Нужно проверять, но пока есть ощущение, что в рамках более-менее реалистического распределения, эти вероятности будут равны для всех стратегий, которые при определённых условиях приводят к максимуму. Тогда мы вправе советовать барышне любую из них.

Чтобы не быть голословным, приведу случай $n=4$. Рейтинги $p_1<p_2<p_3<p_4$. Совсем неудачные стратегии рассматривать не будем. Тогда:
$S_1=\left\lbrace(0),(0,1),(0,1,1),(1,1,1,1)\right\rbrace,$
$S_2=\left\lbrace(0),(0,1),(0,0,1),(1,1,1,1)\right\rbrace,$
$S_3=\left\lbrace(0),(0,0),(0,1,1),(1,1,1,1)\right\rbrace,$
$S_4=\left\lbrace(0),(0,0),(0,0,1),(1,1,1,1)\right\rbrace.$
Ожидания:
$M[S_1]=(p_1 + 5 p_2 + 8 p_3 + 10 p_4)/24$,
$M[S_2]=(2 p_1 + 4 p_2 + 7 p_3 + 11 p_4)/24$,
$M[S_3]=(2 p_1 + 6 p_2 +8 p_3 +8 p_4)/24$,
$M[S_4]=(4 p_1 + 4 p_2 + 6 p_3 + 10 p_4)/24$.
Видно, что конкурентом $S_2$, является только $S_1$. Это и есть две подходящие, при определённых условиях на рейтинги, стратегии. Сравнивая $M[S_2]$ и $M[S_1]$, получим, что если $p_4+p_1>p_3+p_2$, тогда $S_2$ оптимальная, иначе $S_1$. Теперь предположим, что у нас гауссиана для рейтингов, кем-то сгенерированы 4 случайные точки на вещественной оси, вопрос - с какой вероятностью середина отрезка, образованного крайними точками, правее середины отрезка, образованного внутренними точками. Тем самым, невеста может вооружаться любой из первых двух стратегий. А если она при этом мечтает о самом-самом, то лучше выбрать $S_2$.