Изменения

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

Требуется найти Найти полное устойчивое паросочетание между элементами двух множеств размера <tex>Nn</tex>, имеющих имеющими свои предпочтения.}}

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

в МЖ. Пара A-b называется неустойчивой (unstable pair), если:# В паросочетании есть пары A-a и B-b (A женат на a, B женат на b)# A считает b привлекательней, чем a# b считает A привлекательней, чем B(неформально это означает потенциальную возможность измены)

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

Решение задачи было описано в <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">// Изначально все мужчины не женаты и все женщины не женаты (не замужем) незамужние.<tex/font>\mathrm{\textbf{ '''while}}</tex> Существует 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>

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

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

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

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

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

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

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

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

{{Лемма

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

{{Лемма

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

# Предположим A-c (Пусть <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> {{---c — }} нестабильная пара в паросочетании <tex>S</tex>. То есть для <tex>c</tex> есть мужчина, который более привлекателен, чем её муж.

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