Задача об устойчивом паросочетании

2016-12-19T09:40:46Z

212.116.101.78: /* Основная задача */

== Основная задача ==

Есть N мужчин и N женщин. Они обладают следующими особенностями:
# Каждый человек оценивает лишь людей противоположного пола (все гетеросексуальны)
# Каждый мужчина может отсортировать женщин от "наименее привлекательной" к "наиболее привлекательной", причем его предпочтения не меняются (у каждого мужчины своя функция оценки)
# Каждая женщина может отсортировать мужчин от "наименее привлекательного" к "наиболее привлекательному", причем её предпочтения не меняются (у каждой женщины своя функция оценки)

Очевидным образом по такому определению строится полный двудольный граф (левая доля — мужчины, правая — женщины), назовем его МЖ.

Рассмотрим некоторое [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B8_%D0%B4%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D1%8F%D1%8E%D1%89%D0%B8%D1%85_%D1%86%D0%B5%D0%BF%D1%8F%D1%85#matching_def паросочетание] в МЖ. Пара A — b называется неустойчивой (unstable pair), если:
# В паросочетании есть пары A — a и B — b (A женат на a, B женат на b)
# A считает b привлекательней, чем a
# b считает A привлекательней, чем B
(неформально это означает потенциальную возможность измены)

{{Определение
|definition=Устойчивое паросочетание (stable matching) — паросочетание без неустойчивых пар.
}}

Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений.

== Агоритм Гейла-Шепли ==

Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).

=== Интуитивное описание ===

# мужчины делают предложение наиболее предпочитаемой женщине;
# каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)
# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
# шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.

=== Описание в псевдокоде ===

Изначально все мужчины и все женщины не женаты (не замужем)
'''while''' Существует m <- некоторый свободный мужчина, не делавший предложения всем женщинам
w <- первая женщина из списка m, которой m еще не делал предложения
'''if''' w свободна
помечаем m и w помолвленными
'''else if''' w предпочитает m своему "текущему" жениху m'
помечаем m и w помолвленными, m' - свободным
'''else'''
w отказывает m

=== Доказательство корректности ===

{{Утверждение
|id=observation1
|about=Наблюдение 1
|statement=Мужчины делают предложения женщинам в порядке убывания симпатии
}}

{{Утверждение
|id=observation2
|about=Наблюдение 2
|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату)
}}

Для начала покажем, что алгоритм завершит свою работу.

{{Лемма
|id=lemma1
|about=Лемма 1
|statement=
Алгоритм завершается после максимум n^2 итераций цикла '''while'''
|proof=
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.
}}

Теперь покажем, что по завершении алгоритма задача будет решена.

{{Лемма
|id=lemma2
|about=Лемма 2
|statement=
Все мужчины и женщины будут заняты.
|proof=
1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.

2. Тогда некоторая женщина, Антонина не замужем

3. По [[#observation2|наблюдению 2]], Антонине никто не делал предложения

4. Но Ян сделал предложения всем женщинам, т.к. он остался не женат

5. Получаем противоречие

6. Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано
}}

{{Лемма
|id=lemma3
|about=Лемма 3
|statement=
Нет неустойчивых пар.
|proof=
1. Предположим A-b (A, B - мужчины; a, b - женщины; A женат на a, B женат на b) - нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли

2. Рассмотрим два случая:

2.1. A не делал предложения b

=> A находит a более привлекательной, чем b

=> A-b - устойчивая пара

2.2. A делал предложение b

=> b отказала A (сразу или на одной из последующих итераций)

=> b находит B более привлекательным, чем A

=> A-b - устойчивая пара
}}

=== Асимптотика алгоритма ===

Не представляет проблемы реализовать внутренний цикл while за <tex>O(1)</tex> (с предварительным предпроцессингом не более, чем за <tex>O(n^2)</tex>). Таким образом, итоговая асимптотика составляет <tex>O(n^2)</tex>.

=== Анализ полученного алгоритмом паросочетания ===

Агоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом.

{{Лемма
|id=lemma4
|about=Лемма 4 (man-optimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
}}

{{Лемма
|id=lemma5
|about=Лемма 5 (woman-pessimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
}}

Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf (с.5)

== Обобщения задачи ==

Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. [[http://ru.wikipedia.org/wiki/Задача_о_соседях_по_комнате|Задача о соседях по комнате]])

Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M - N</tex> фиктивных мужчин, которые являются наименее привлекательными с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем.

Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин - множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидно сводится к основной добавлением <tex>(K-1)</tex> "филиалов" для каждого университета (<tex>K</tex> - квота). И добавлением фиктивного увниерситета (поступление в который означает, что кандидату придется попробовать поступить через год).

== Применения в реальной жизни ==

Задача о нахождении устойчивого паросочетания и её решение имеют множество применений в реальной жизни, лишь некоторые из них:
* Распределение студентов по коллеждам в США
* Распределение интернов по больницам
* Распределение донорских органов по нуждающимся в них людям

Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в 2008 году.

== Ссылки ==

* [http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf Stable matching, Prinston lecture's presentation]
* [http://en.wikipedia.org/wiki/Stable_marriage_problem Stable marriage problem]
* [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BC%D0%B0%D1%80%D1%8C%D1%8F%D0%B6%D0%B5 Задача о марьяже]
* [http://ge.tt/api/1/files/4LU3zaD1/0/blob?download Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

Викиконспекты - Вклад участника [ru]

Задача об устойчивом паросочетании