Стабильный марьяж
May. 23rd, 2013 02:38 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mathclimberНет, нет, и нет, это не про королей и дам одной и той же масти, а, скорее, про математику, и её применения в жизни. Однако же, незамедлительно выскажу большую просьбу к милым дамам, читающим мой журнал. Пожалуйста. Очень прошу. Дочитайте этот пост до конца, можно даже не очень вникать во всю нудятину, которая там будет в середине. Потому что в конце будет вывод, как-бы применимый к практическим взаимоотношениям между полами. И я почти уверен, что сей вывод будет для Вас интересен. Собственно, он для всех будет интересен, не только для дам.
Итак, задача:
Имеется N мужчин и N женщин, каждый(ая) из них имеет свой список предпочтений среди лиц противоположного пола. Требуется: разбить этих людей по парам (имеется в виду, гм, традиционный брак, конечно), так, чтобы получившееся разбиение было стабильным.
Что тут понимается под стабильностью, сейчас объясню.
Предположим, мы разбили всех на пары, и имеются мужчина (скажем) Роберт и женщина (к примеру) Алиса, такие, что
Каждый понимает, что такая ситуация чревата адюльтером - Алиса сбежит с Робертом, а их текущие партнёры останутся одни-одинёшеньки. Так вот, разбиение считается стабильным, если таких вот кандидатов на адюльтер там не наблюдается.
Пример. Пусть есть три мужика, Роберт, Джек, и Билл. И три дамы: Алиса, Моника, и Хиллари. Предположим, что списки преференций у них такие (в порядке убывания привлекательности):
Роберт: Моника, Алиса, Хиллари
Джек: Алиса, Моника, Хиллари
Билл: Моника, Хиллари, Алиса
Алиса: Джек, Роберт, Билл,
Моника: Джек, Билл, Роберт,
Хиллари: Билл, Джек, Роберт
Рассмотрим такой марьяж:
Билл-Хиллари
Джек-Алиса
Роберт-Моника
Прошу заметить, он нестабилен: Билл сбежит с Моникой, как легко было догадаться. Но вот такой вариант
Билл-Моника
Джек-Алиса
Роберт-Хиллари
уже стабилен, и пребудет он во времени, ибо.
Вот. Априори, кстати говоря, неясно почему такой стабильный марьяж вообще должен существовать. И, если он таки существует, то как его получить не перебирая все N! вариантов, что как-то многовато будет?
Решение задачи было получено Дэвидом Гейлом и Ллойдом Шепли уже довольно давно, в 1962 году. Между прочим, в прошлом году Шепли получил за это Нобелевскую премию (по экономике)! Разумеется, существует множество вариаций алгоритма Гейла-Шепли, для самых различных задач, не только для сватовства. Кстати говоря, мы с Маринкой шесть лет назад даже статью написали про одну из тех вариаций. И рекомендую еще вот это почитать: http://lenta.ru/articles/2012/
Итак, вот алгоритм Гейла-Шепли:
Натурально, всякое сходство с реальностью - есть простое совпадение, и вообще я тут ни сном, ни духом :)
Можно доказать, что в результате действительно получается стабильное разделение по парам.
Доказательство.
Во-первых, действительно получается разбиение по парам, поскольку
Во-вторых, докажем, что это разбиение стабильно. Действительно, предположим на минутку что у Роберта и Алисы есть склонность к адюльтеру (т.е., они не пара, но предпочитают друг друга своим текущим партнёрам). Раз Роберт предпочитает Алису своей текущей жене, он должен был сделать предложение Алисе раньше, чем жене той. Но раз уж Алиса это предложение отвергла, она это сделала ради кого-то, кто с её точки зрения лучше Роберта - противоречие.
QED
Естественно, стабильный марьяж можно, вообще говоря, осуществить разными способами, алгоритм Гейла-Шепли - не единственный метод его построения. Будем говорить, что Алиса и Роберт - возможные партнёры, если имеется хотя бы одно стабильное разбиение, в котором они - пара. Понятное дело, не всякий мужчина - возможный партнёр для данной женщины (и наоборот). К примеру, если в списке Марфы из Жмеринки на первом месте - Брэд Питт, а у Пантелея из Бобруйска - Анжелина Джоли, то вряд ли Марфе и Пантелею чего светит. Как их там не жени, а всё равно Анжелина сбежит с Питтом.
А вот теперь попрошу внимания аудитории, а задремавших - проснуться. Оказывается, сей modus operandi весьма выгоден для мужчин, и крайне невыгоден для женщин. Точнее, при вышеописанной процедуре
Это математический факт, доказать который совсем нетрудно; интересующиеся могут посмотреть доказательство под катом.
Доказательство.
В самом деле, пусть М - разбиение, полученное алгоритмом Гейла-Шепли, и предположим, что там есть хоть один мужчина, которому не досталась его наилучшая из возможных партнёрш. Пусть Роберт - это первый мужчина, которому отказала его наилучшая возможная партнёрша (натурально, её зовут Алиса). Если уж она его отвергла, то она сделала это ради кого-то другого (скажем, назовём его Томас). Но, поскольку Роберт - первый из тех, с кем случился такой упс, мы понимаем что, для Томаса, Алиса не хуже, чем его (Томаса) собственная наилучшая возможная партнёрша. Но тогда, если М' - какое-нибудь другое разбиение в котором Роберт с Алисой в законном браке, то будут опаньки: Алисе-то больше нравится Томас, а Томасу - Алиса. Противоречие.
Теперь, допустим что Гейл и Шепли решили, что Алиса будет таки с Робертом, и пусть M'' - еще какое-нибудь стабильное разбиение, в котором Алиса не с Робертом, а с Джоном. Докажем, что Джон для Алисы лучше, чем Роберт. В самом деле, предположим, что это не так. Мы уже знаем, что Алиса - это лучшая женщина, которая вообще может достаться Роберту. Раз уж Алиса там с Джоном, то Роберт - с какой-то другой женщиной, не с Алисой. Но Роберту больше нравится Алиса, а Алисе - Роберт (по нашему предположению), и значит M'' - нестабильно. Опять противоречие.
QED
Ну-с, и что теперь? Что предпочтительней - активный поиск, или пассивное ожидание? Каково оптимальное поведение, с точки зрения максимизации количества счастья от жизни? В общем, какие же мы сделаем из этого всего выводы?
А делайте их сами :)
Итак, задача:
Имеется N мужчин и N женщин, каждый(ая) из них имеет свой список предпочтений среди лиц противоположного пола. Требуется: разбить этих людей по парам (имеется в виду, гм, традиционный брак, конечно), так, чтобы получившееся разбиение было стабильным.
Что тут понимается под стабильностью, сейчас объясню.
Предположим, мы разбили всех на пары, и имеются мужчина (скажем) Роберт и женщина (к примеру) Алиса, такие, что
- они - не пара,
- но, при этом, Алиса предпочитает Роберта своему текущему партнёру,
- а Роберт предпочитает Алису своей текущей партнёрше.
Каждый понимает, что такая ситуация чревата адюльтером - Алиса сбежит с Робертом, а их текущие партнёры останутся одни-одинёшеньки. Так вот, разбиение считается стабильным, если таких вот кандидатов на адюльтер там не наблюдается.
Пример. Пусть есть три мужика, Роберт, Джек, и Билл. И три дамы: Алиса, Моника, и Хиллари. Предположим, что списки преференций у них такие (в порядке убывания привлекательности):
Роберт: Моника, Алиса, Хиллари
Джек: Алиса, Моника, Хиллари
Билл: Моника, Хиллари, Алиса
Алиса: Джек, Роберт, Билл,
Моника: Джек, Билл, Роберт,
Хиллари: Билл, Джек, Роберт
Рассмотрим такой марьяж:
Билл-Хиллари
Джек-Алиса
Роберт-Моника
Прошу заметить, он нестабилен: Билл сбежит с Моникой, как легко было догадаться. Но вот такой вариант
Билл-Моника
Джек-Алиса
Роберт-Хиллари
уже стабилен, и пребудет он во времени, ибо.
Вот. Априори, кстати говоря, неясно почему такой стабильный марьяж вообще должен существовать. И, если он таки существует, то как его получить не перебирая все N! вариантов, что как-то многовато будет?
Решение задачи было получено Дэвидом Гейлом и Ллойдом Шепли уже довольно давно, в 1962 году. Между прочим, в прошлом году Шепли получил за это Нобелевскую премию (по экономике)! Разумеется, существует множество вариаций алгоритма Гейла-Шепли, для самых различных задач, не только для сватовства. Кстати говоря, мы с Маринкой шесть лет назад даже статью написали про одну из тех вариаций. И рекомендую еще вот это почитать: http://lenta.ru/articles/2012/
Итак, вот алгоритм Гейла-Шепли:
- для начала, каждый мужчина делает предложение самой лучшей (с его точки зрения) женщине;
- каждая женщина из всей большой кучи поступивших предложений выбирает наилучшее (по отношению к своему списку) и отвечает на него "может быть", на все остальные отвечает "нет";
- мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, которым было сказано "может быть", ничего не делают и смиренно ждут;
- если женщине пришло предложение лучше предыдущих, то она прежнему претенденту (которому было сказано "может быть") говорит "нет", а новому претенденту говорит "может быть";
- и так далее, пока у всех мужчин не исчерпается список предложений (или не останется мужчин не в статусе претендента); в этот момент женщины говорят "да" своим претендентам, которые у них есть в настоящий момент.
Натурально, всякое сходство с реальностью - есть простое совпадение, и вообще я тут ни сном, ни духом :)
Можно доказать, что в результате действительно получается стабильное разделение по парам.
Во-первых, действительно получается разбиение по парам, поскольку
- если женщина кому-то уже сказала "может быть", то у неё уже всегда есть "кандидат" (он может меняться, но совсем без вариантов она остаться не может);
- а следовательно, в конце алгоритма не может оказаться так, что есть и женщина, которой никто не добивался, и мужчина, которому все отказали (он должен был в какой-то момент сделать предложение той женщине, и она должна была ему сказать "может быть").
Во-вторых, докажем, что это разбиение стабильно. Действительно, предположим на минутку что у Роберта и Алисы есть склонность к адюльтеру (т.е., они не пара, но предпочитают друг друга своим текущим партнёрам). Раз Роберт предпочитает Алису своей текущей жене, он должен был сделать предложение Алисе раньше, чем жене той. Но раз уж Алиса это предложение отвергла, она это сделала ради кого-то, кто с её точки зрения лучше Роберта - противоречие.
QED
Естественно, стабильный марьяж можно, вообще говоря, осуществить разными способами, алгоритм Гейла-Шепли - не единственный метод его построения. Будем говорить, что Алиса и Роберт - возможные партнёры, если имеется хотя бы одно стабильное разбиение, в котором они - пара. Понятное дело, не всякий мужчина - возможный партнёр для данной женщины (и наоборот). К примеру, если в списке Марфы из Жмеринки на первом месте - Брэд Питт, а у Пантелея из Бобруйска - Анжелина Джоли, то вряд ли Марфе и Пантелею чего светит. Как их там не жени, а всё равно Анжелина сбежит с Питтом.
А вот теперь попрошу внимания аудитории, а задремавших - проснуться. Оказывается, сей modus operandi весьма выгоден для мужчин, и крайне невыгоден для женщин. Точнее, при вышеописанной процедуре
- каждый мужчина получает наилучшую из возможных партнёрш,
- каждая женщина получает наихудшего из возможных партнёров.
Это математический факт, доказать который совсем нетрудно; интересующиеся могут посмотреть доказательство под катом.
В самом деле, пусть М - разбиение, полученное алгоритмом Гейла-Шепли, и предположим, что там есть хоть один мужчина, которому не досталась его наилучшая из возможных партнёрш. Пусть Роберт - это первый мужчина, которому отказала его наилучшая возможная партнёрша (натурально, её зовут Алиса). Если уж она его отвергла, то она сделала это ради кого-то другого (скажем, назовём его Томас). Но, поскольку Роберт - первый из тех, с кем случился такой упс, мы понимаем что, для Томаса, Алиса не хуже, чем его (Томаса) собственная наилучшая возможная партнёрша. Но тогда, если М' - какое-нибудь другое разбиение в котором Роберт с Алисой в законном браке, то будут опаньки: Алисе-то больше нравится Томас, а Томасу - Алиса. Противоречие.
Теперь, допустим что Гейл и Шепли решили, что Алиса будет таки с Робертом, и пусть M'' - еще какое-нибудь стабильное разбиение, в котором Алиса не с Робертом, а с Джоном. Докажем, что Джон для Алисы лучше, чем Роберт. В самом деле, предположим, что это не так. Мы уже знаем, что Алиса - это лучшая женщина, которая вообще может достаться Роберту. Раз уж Алиса там с Джоном, то Роберт - с какой-то другой женщиной, не с Алисой. Но Роберту больше нравится Алиса, а Алисе - Роберт (по нашему предположению), и значит M'' - нестабильно. Опять противоречие.
QED
Ну-с, и что теперь? Что предпочтительней - активный поиск, или пассивное ожидание? Каково оптимальное поведение, с точки зрения максимизации количества счастья от жизни? В общем, какие же мы сделаем из этого всего выводы?
А делайте их сами :)
