Изменения

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

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

Рассмотрим некоторое [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) = Алгоритм Гейла- паросочетание без неустойчивых пар.}}Шепли ==

Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений. == Агоритм Гейла-Шепли == Решение задачи было описано в <tex>1962 </tex> году математиками Девидом Гейлом (Университета Университет Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (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>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).

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

<font color="green">// Изначально все мужчины не женаты и все женщины не женаты (не замужем)незамужние.</font> '''while''' Существует m <- существует свободный мужчина M = некоторый свободный мужчина, не делавший предложения всем женщинам w <- = первая женщина из текущего списка m, которой m еще не делал предложенияM '''if''' w свободна помечаем m M и w помолвленными '''else if''' w предпочитает m M своему "текущему" жениху mM' помечаем m M и w помолвленными, m вычёркиваем w из списка предпочтений M' помечаем M' - свободным '''else''' вычёркиваем w отказывает mиз списка предпочтений M Время работы алгоритма {{---}} <tex>O(n^2)</tex>, так как количество итераций цикла <tex>\mathrm {while}</tex> не превосходит <tex>O(n^2)</tex>, где <tex>n</tex> равно размеру каждого из данных множеств.

|about=Наблюдение <tex>1</tex>|statement=Мужчины делают предложения женщинам в порядке убывания симпатии.

|about=Наблюдение <tex>2</tex>|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату).

|about=Лемма <tex>1</tex>

Алгоритм завершается после максимум <tex>n^2 </tex> итераций цикла '''<tex>\mathrm{\mathbf{while'''}}</tex>.

На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более <tex>n^2 </tex> предложений.

|about=Лемма <tex>2</tex>

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

2Аналогичные рассуждения применяем для женщин. Тогда некоторая Пусть какая-то женщинанезамужняя. Значит, Антонина не замужем  3. По [[#observation2|наблюдению 2]]есть мужчина, Антонине никто который остался не делал предложения  4женат. Но Ян сделал предложения всем женщинаммы доказали, тчто по завершении алгоритма все мужчины заняты.Снова пришли кпротиворечию. он остался не женат  5. Получаем противоречие 6. Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано

|about=Лемма <tex>3</tex>

Нет После завершения алгоритма не будет неустойчивых пар.

1. Предположим <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>) - — нестабильная пара в паросочетнаиипаросочетании, найденном алгоритмом Гейла-Шепли  2. Рассмотрим Возможны два случая:  2.1. # <tex>A </tex> не делал предложения предложение <tex>b  =</tex>. Значит, <tex> A </tex> находит <tex>a </tex> более привлекательной, чем <tex>b  =</tex>. Но чтобы рассматриваемая пара была неустойчивой, необходимо, чтобы <tex>b</tex> для <tex>A</tex> была более привлекательна, чем <tex>a</tex>. Следовательно, <tex> \langle A-, b - \rangle</tex> — устойчивая пара.  2.2. # <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> — устойчивая пара.

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

{{Лемма

|about=Лемма 4 (man-optimality)

{{Лемма

|about=Лемма 5 (woman-pessimality)

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

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

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

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