Среди общего множества женихов сколько именно женихов никогда не станут мужьями в задаче о разборчивой невесте?

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

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

И поиск количества таких женихов (при условии, что это всегда 1 процент от позиций в списке женихов больше 100 мужчин) — это новая задача или часть решения традиционной задачи о разборчивой невесте? Если это новая задача, ранее никем не сформированная, в науке назовут ли её моим именем?

По дате

По рейтингу

anathomy

Новичок

3д

Изменено

Ответ от \ RawMind AI :

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

В традиционной формулировке задачи о разборчивой невесте, оптимальная стратегия заключается в том, чтобы первые \( n/e \) (где \( e \approx 2.718 \)) претендентов отклонить и выбрать первого из последующих, который лучше всех предыдущих.

Таким образом, количество женихов, которые никогда не станут мужьями по этой стратегии, равно первым \( n/e \) претендентам. Это новая задача в рамках традиционной формулировки, но она является частью общего решения.

Если вы хотите установить алгоритм для жениха, который обречен не стать мужем разборчивой невесты, то можно сказать, что это будет любой из первых \( n/e \) претендентов. Если же рассматривать задачу более глубоко и ввести новые параметры или условия, то это может быть новая задача.

Если вы сформулируете эту задачу и опубликуете её научную работу, вполне возможно, что она будет названа по вашему имени. Например, "Задача о разборчивой невесте в варианте [Ваше имя]".

eigenbasis

Мыслитель

2д

Не вовсе ясна постановка задачи. В классической задаче о разборчивой невесте к ней в случайную очередь выстраиваются N женихов, на которых как-то задан порядок (кто лучше, а кто хуже). Затем невеста выбирает жениха по правилу: либо отказать текущему и перейти к следующему, либо выбрать текущего и завершить поиск. Я дополнительно люблю добавлять условие, что если первым N-1 было отказано, то обязательно выходить за последнего, чтобы не остаться без мужа совсем.

В такой игре оптимальной (в асимптотике) стратегией является стратегия с "обучением": сначала невеста просто просматривает первых n/e кандидатов, а потом соглашается на первого же попавшегося, который лучше всех, до того увиденных [Гусейн-Заде, 2003]. При этом есть масса обобщений и расширений этой задачи, в которых оптимальная стратегия выглядит похожим образом, но отличается в деталях.

Теперь два таких соображения по поводу вашего вопроса:

Для любого жениха существует порядок очереди, в котором невеста выберет именно его (даже ясно, как такую очередь составить), поэтому, если порядок в очереди случайный, то у каждого жениха (даже самого худшего) есть положительная вероятность быть выбранным. Соответственно, если повторять эксперимент много раз с разными невестами и одним и тем же набором женихов, каждый раз переставляя очередь случайным образом, у каждого жениха будет положительная частота побед (см. рисунок ниже -- распределение шансов выигрыша в зависимости от позиции жениха в отсортированном рейтинге при N = 100). То есть в этом смысле гарантированно отвергнутых не бывает.
В каждом же отдельном эксперименте около 1/e ≈ 37% женихов гарантированно уходят в отказ на периоде "обучения", а затем еще сколько-то -- на периоде отбора. В среднем в процессе отваливается около 72% всех женихов, пока не будет встречен тот, кого невеста выберет (см. распределение количества отброшенных при N = 100 на рисунке ниже).

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

Я бы лично порекомендовал вам почитать про задачу об устойчивом паросочетании (задача о марьяже), она лучше отражает то, что вам интересно. Там как раз встает вопрос о том, как организовать механизм, распределяющий N мужчин и N женщин на "брачные" пары так, чтобы никому не было выгодно изменять. И классическое решение этой задачи -- алгоритм Гейла--Шепли -- как раз устроен так, что никакие стратегии женихов не могут гарантированно улучшить их результат (под "стратегиями" тут понимается манипуляция списком предпочтений).

Более того, для механизма Гейла--Шепли при разном числе мужчин и женщин неверен вывод о том, что каждый мужчина имеет шанс на пару: тут работает своего рода аксиома болвана (как в векторе Шепли): если мужчина-болван остался без пары в каком-то одном устойчивом паросочетании, то он останется без пары и в любом другом.