Просмотр исходного текста страницы Задача об устойчивом паросочетании

{{Определение
|definition='''Устойчивое паросочетание''' (англ. ''stable matching'') — [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] без неустойчивых пар.
}}
{{Задача
|definition=
Найти полное устойчивое паросочетание между элементами двух множеств размера <tex>N</tex>, имеющими свои предпочтения.}}

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

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


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

Рассмотрим некоторое [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]]
в МЖ.
{{Определение
|definition = 
 Пара <tex>\langle A, b\rangle</tex> называется '''неустойчивой''' (англ. ''unstable pair''), если:
# В паросочетании есть пары <tex>\langle A, a\rangle</tex> и <tex>\langle B, b\rangle</tex> (<tex>A</tex> женат на <tex>a</tex>, <tex>B</tex> женат на <tex>b</tex>)
# <tex>A</tex> считает <tex>b</tex> ''привлекательней'', чем <tex>a</tex>
# <tex>b</tex> считает <tex>A</tex> ''привлекательней'', чем <tex>B</tex>
}}

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

Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly
<ref>https://ru.wikipedia.org/wiki/American_Mathematical_Monthly American Mathematical Monthly 69, 9-14, 1962.</ref>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).

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

# Мужчины делают предложение наиболее предпочитаемой женщине.
# Каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ).
# Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают.
# Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть».
# Шаги 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=
	Алгоритм завершается после максимум <tex>n^2</tex> итераций цикла <tex>\mathrm{\mathbf{while}}</tex>.
|proof=
	На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более <tex>n^2</tex> предложений.
}}

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

{{Лемма
|id=lemma2
|about=Лемма 2
|statement=
	Все мужчины и женщины будут заняты.
|proof=
Предположим, что некоторый мужчина (<tex>A</tex>) не женат по завершении алгоритма. Тогда некоторая женщина (<tex>a</tex>) не замужем. По [[#observation2|наблюдению 2]], <tex>a</tex> не получала предложений. Но <tex>A</tex> сделал предложения всем женщинам, так как он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты.

Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина не замужем. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию.
}}


{{Лемма
|id=lemma3
|about=Лемма 3
|statement=
	После завершения алгоритма не будет неустойчивых пар.
|proof=
Предположим <tex>\langle A, b\rangle</tex> (где <tex>A</tex>, <tex>B</tex> — мужчины; <tex>a</tex>, <tex>b</tex> — женщины; <tex>A</tex> женат на <tex>a</tex>, <tex>B</tex> женат на <tex>b</tex>) — нестабильная пара в паросочетании, найденном алгоритмом Гейла-Шепли. Рассмотрим два случая:
# <tex>A</tex> не делал предложения <tex>b</tex>. Значит, <tex>A</tex> находит <tex>a</tex> более привлекательной, чем <tex>b</tex>. Следовательно, <tex>\langle A, b\rangle</tex> — устойчивая пара.
# <tex>A</tex> делал предложение <tex>b</tex>. Тогда был такой момент, когда <tex>b</tex> отказала <tex>A</tex>, значит, <tex>b</tex> находит <tex>B</tex> более привлекательным, чем <tex>A</tex>. Снова получается, что <tex>\langle A, b\rangle</tex> — устойчивая пара
	
}}

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

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

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

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

{{Лемма 
|id=lemma4
|about=man-optimality
|statement=
	Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
|proof=
Если женщина <tex>a</tex> вычёркивается из списка предпочтений мужчины <tex>A</tex>, то ни одно устойчивое паросочетание не будет содержать пары <tex>\langle A, a\rangle</tex>.
}}

{{Лемма 
|id=lemma5
|about=woman-pessimality
|statement=
	Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
|proof= 
Пусть <tex>A</tex>, <tex>B</tex> — мужчины; <tex>c</tex>, <tex>d</tex> — женщины; <tex>A</tex> женат на <tex>d</tex>, <tex>B</tex> женат на <tex>c</tex>.

Предположим, <tex>\langle A, c\rangle</tex>  — стабильная пара в паросочетании <tex>S'</tex>, найденном алгоритмом Гейла-Шепли, но <tex>A</tex> не самый худший выбор для <tex>c</tex>. Тогда существует стабильная пара в паросочетании <tex>S</tex>, в которой <tex>c</tex> замужем за <tex>B</tex>, который менее привлекателен, чем <tex>A</tex>. Тогда пусть мужем <tex>d</tex> будет <tex>A</tex> в паросочетании <tex>S</tex>. Получается <tex>A</tex> считает <tex>c</tex> более привлекательной, чем <tex>d</tex>. Соответственно <tex>\langle A, c\rangle</tex> {{---}} нестабильная пара в паросочетании <tex>S</tex>.

}}

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

Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см.
[https://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 году.

== Примечания ==
<references/>

== См. также  ==
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|Паросочетания]]
== Источники информации ==

* [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 Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]



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