Изменения

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

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

# Шаги <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>

|about=Наблюдение <tex>2</tex>

|about=Лемма <tex>1</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>) — нестабильная пара в паросочетании, найденном алгоритмом Гейла-Шепли. Рассмотрим Возможны два случая:# <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> — устойчивая пара.# <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>A</tex> это свойство не выполняется. Так как он оказался женат не на лучшей из кандидатур, то существует женщина <tex>a</tex>, которая предпочла ему другого, более привлекательного мужчину <tex>B</tex>, при этом женщина <tex>a</tex> для мужчины <tex>B</tex> стоит на первом месте в его текущем списке. Предположим, существует устойчивое паросочетание, содержащее <tex>\langle A, a\rangle</tex>. По определению, в устойчивом паросочетании нет неустойчивых пар. Пара <tex>\langle B, a\rangle</tex> станет неустойчивой, если <tex>B</tex> будет предпочитать <tex>a</tex> своей супруге. Значит, <tex>B</tex> женат на ком-то, кто лучше, чем <tex>a</tex>. Но такое невозможно, так как <tex>a</tex> стоит для него на первом месте. Таким образом, если женщина <tex>a</tex> вычёркивается из списка предпочтений мужчины <tex>A</tex>, то ни одно устойчивое любое паросочетание не будет содержать пары , содержащее <tex>\langle A, a\rangle</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>. То есть для <tex>c</tex> есть мужчина, который более привлекателен, чем её муж.

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

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