«Задача о марьяже» или могла ли Лариса Гузеева получить Нобелевскую премию по экономике?

Всем привет! Сегодня я хочу рассказать о довольно интересное задаче, за решение которой была вручена Нобелевская премия по экономике в 2012 году.

Давайте представим, что к Ларисе Гузеевой в программу «Давай поженимся» пришли 10 мужчин и 10 женщин, чтобы она их распределила по парам… Ведущая шоу, обращается к астрологам, кандидаты танцуют и поют друг перед другом. И в итоге она распихивает кого смогла и как смогла: )

Но после шоу оказывается астрологи где-то прогадали, и есть две пары, в которых мужа из первой пары влечет в жене из второй пары, и это полностью взаимно. И в итоге две пары рушатся, появляется одна новая и еще двое остаются не у дел. Получается, что даже главная сваха страны не смогла создать устойчивые пар?

Но решение такой задачи смогли найти два математика Ллойд Шелли и Дэвид Гейл. Решение было опубликовано в далеком 1962 году в журнале American Mathematical Monthly в статье под названием «Поступление в колледж и стабильность браков».

Суть задачи

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

Несколько пояснений:

• Можно остаться холостяком/незамужней. К примеру какому-то мужчине нравятся только блондинки, а все женщины брюнетки, и он считает лучше я буду один, чем с брюнеткой. Хотя есть вариации задачи, когда нет такой возможности, т.е. пару необходимо обязательно выбрать (нравятся все всем, но в разной степени).
• Неразделенные чувства разрешены, запрещены только обоюдные. К примеру, Татьяна и Олег из Вязьмы – первая пара, и Моника Беллуччи и Венсан Кассель – вторая. Как бы Олега не тянуло к Монике, ему ничего не светит. А вот если, и Олега будет тянуть к Монике сильнее, чем к Татьяне, и Монику будет тянуть к Олегу сильнее, чем к Венсану, то такое распределение будет не устойчиво, т.к. в итоге Моника и Олег сбегут от своих пар и уедут счастливые в закат.

Предложенное решение (алгоритм Гейла-Шелли)

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

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

Женщины смотрят, кто к ним пришел, и самому предпочтительному из пришедших отвечает «Я подумаю», а всем остальным от ворот поворот.

Те, мужчины, которым отказали идут к следующим по списку женщинам. А те, которым обещали подумать, ждут у окошка потенциальной невесты.

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

Так повторяется, пока все мужчины не пройдут по своим спискам. Когда списки закончились (либо всем мужчинам сказали ждать, и ходить уже некому), женщины говорят тем, кто ждет под их окном «Я согласна!».

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

Вот и все решение задачи: )

Вы, наверное, подумали, ну и за что тут Нобелевскую премию давать? Нобелевскую премию получили два человека: Ллойд Шелли и Элвин Рот. Обоснование награды звучит так: «За теорию стабильного распределения и практики устройства рынков».

Элвин Рот разработал очень много практических механизмов, основанных на алгоритме Гейла-Шелли, за что и получил Нобелевскую премию.

Примеры механизмов, которые были внедрены:

• Распределение врачей по больницам;
• Распределение интернов по больницам;
• Набор спортсменов в команды;
• Набор стажеров в компании;
• Наем клерков в суды;
• Подбор школ для детей.

Уже задача не кажется такой бесполезной?:)

Доноры и реципиенты

Человеку нужна почка. У него есть донор, но почка этого донора ему не подходит. Продать эту почку и купить другую он не может (запрещено). Либо умирать, либо искать выход. Выход нашел Элвин Рот. Он адаптировал алгоритм Гейла-Шелли и создал многоступенчатый бартерный рынок донорских органов между госпиталями США.

Подбор школ для детей

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

Человеческий фактор

Представим, что у нас есть трое мужчин и трое женщин с приоритетом предпочтений представленным в двух таблицах ниже:

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

И получится три устойчивые пары:

• Коля – Оксана;
• Петя – Татьяна;
• Игорь – Елена.

Все мужчины получили свой идеал, а вот женщины получили наименее предпочитаемых мужчин. И получается, что мнение женщин никто не учитывает в таком случае. Будут тайно мечтать о других мужчинах, но т.к. тем мужчинам, о ком они будут мечтать они менее интересны, чем их жены, они не смогут «уйти к ним», т.е. пары будут устойчивы.

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

В общем, никто не может дать гарантию, что такой брак будет счастливым: )

Задача о соседях по комнате

Это модификация задачи о марьяже. Отличие в том, что нужно разбить не два множества на пары, а одно. В этой задаче может и не быть решения.

Пример: Есть четыре человека – Андрей, Валентин, Коля, Дима, которых необходимо расселить по двум комнатам, у каждого из них предпочтения с кем жить строго отсортированы.

Их можно расселить следующим образом:

1. Андрей + Валентин; Коля + Дима;
2. Андрей + Коля; Валентин + Дима;
3. Андрей + Дима; Валентин + Коля;

Но, каждый из вариантов расселения будет неустойчив. К примеру, в первом варианте Коля бы предпочел жить с Валентином вместо Димы, а Валентин с Колей вместо Андрея. И в оставшихся двух вариантах также будут находиться лучшие пары. Т.е. ни одно решение не будет устойчивым.

---

Как показывает практика, алгоритм решения данной задачи применяется в самых разнообразных сферах жизни. Если верить Коммерсанту, то даже ЦБ РФ начали применять этот алгоритм.

Надеюсь эта статья будет вам и полезной, и интересной!
Картинка с лицензией CC0.

С уважением, @veritas