Задача об устойчивом паросочетании — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
м (rollbackEdits.php mass rollback)
 
(не показана 101 промежуточная версия 9 участников)
Строка 1: Строка 1:
 +
{{Определение
 +
|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'') — [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] без неустойчивых пар.
 +
}}
 +
{{Задача
 +
|definition=
 +
Найти полное устойчивое паросочетание между элементами двух множеств размера <tex>n</tex>, имеющими свои предпочтения.}}
 +
 
== Основная задача ==
 
== Основная задача ==
  
Есть N мужчин и N женщин. Они обладают следующими особенностями:
+
Есть <tex>n</tex> мужчин и <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) — паросочетание без неустойчивых пар.
 
}}
 
  
Задача заключается в нахождении полного устойчивого паросочетания по данным спискам предпочтений.
+
Рассмотрим некоторое [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]]
 +
в МЖ.
  
== Агоритм Гейла-Шепли ==
+
== Алгоритм Гейла-Шепли ==
  
Решение задачи было описано в 1962 году математиками Девидом Гейлом (Университета Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
+
Решение задачи было описано в <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>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия» (алгоритм предложи-и-откажи).
  
 
=== Интуитивное описание ===
 
=== Интуитивное описание ===
  
# мужчины делают предложение наиболее предпочитаемой женщине;
+
# Мужчины делают предложение наиболее предпочитаемой женщине.
# каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ)
+
# Каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ).
# мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
+
# Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают.
# если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
+
# Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть».
# шаги 1-4 повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
+
# Шаги <tex>1</tex>-<tex>4</tex> повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
  
 
=== Описание в псевдокоде ===
 
=== Описание в псевдокоде ===
  
  Изначально все мужчины и все женщины не женаты (не замужем)
+
  <font color="green">// Изначально все мужчины не женаты и все женщины незамужние.</font>
  '''while''' Существует m <- некоторый свободный мужчина, не делавший предложения всем женщинам
+
  '''while''' существует свободный мужчина
      w <- первая женщина из списка m, которой m еще не делал предложения
+
    M = некоторый свободный мужчина
      '''if''' w свободна
+
    w = первая женщина из текущего списка M
        помечаем m и w помолвленными
+
    '''if''' w свободна
      '''else if''' w предпочитает m своему "текущему" жениху m'
+
      помечаем M и w помолвленными
        помечаем m и w помолвленными, m' свободным
+
    '''else if''' w предпочитает M своему текущему жениху M'
      '''else'''
+
      помечаем M и w помолвленными
        w отказывает m
+
      вычёркиваем w из списка предпочтений M'
 +
      помечаем M' свободным
 +
    '''else'''
 +
      вычёркиваем w из списка предпочтений M
 +
 
 +
Время работы алгоритма {{---}} <tex>O(n^2)</tex>, так как количество итераций цикла <tex>\mathrm {while}</tex> не превосходит <tex>O(n^2)</tex>, где <tex>n</tex> равно размеру каждого из данных множеств.
  
 
=== Доказательство корректности ===
 
=== Доказательство корректности ===
Строка 49: Строка 60:
 
{{Утверждение
 
{{Утверждение
 
|id=observation1
 
|id=observation1
|about=Наблюдение 1
+
|about=Наблюдение <tex>1</tex>
|statement=Мужчины делают предложения женщинам в порядке убывания симпатии
+
|statement=Мужчины делают предложения женщинам в порядке убывания симпатии.
 
}}
 
}}
  
 
{{Утверждение
 
{{Утверждение
 
|id=observation2
 
|id=observation2
|about=Наблюдение 2
+
|about=Наблюдение <tex>2</tex>
|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату)
+
|statement=Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату).
 
}}
 
}}
  
Строка 63: Строка 74:
 
{{Лемма
 
{{Лемма
 
|id=lemma1
 
|id=lemma1
|about=Лемма 1
+
|about=Лемма <tex>1</tex>
 
|statement=
 
|statement=
Алгоритм завершается после максимум <tex>n^2</tex> итераций цикла '''while'''
+
Алгоритм завершается после максимум <tex>n^2</tex> итераций цикла <tex>\mathrm{\mathbf{while}}</tex>.
 
|proof=
 
|proof=
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более n^2 предложений.
+
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более <tex>n^2</tex> предложений.
 
}}
 
}}
  
Строка 74: Строка 85:
 
{{Лемма
 
{{Лемма
 
|id=lemma2
 
|id=lemma2
|about=Лемма 2
+
|about=Лемма <tex>2</tex>
 
|statement=
 
|statement=
 
Все мужчины и женщины будут заняты.
 
Все мужчины и женщины будут заняты.
 
|proof=
 
|proof=
1. Предположим, что некоторый мужчина, Ян, не женат по завершении алгоритма.
+
Предположим, что некоторый мужчина (<tex>A</tex>) не женат по завершении алгоритма. Тогда и некоторая женщина (<tex>a</tex>) незамужняя. По [[#observation2|наблюдению <tex>2</tex>]], <tex>a</tex> не получала предложений. Но <tex>A</tex> сделал предложения всем женщинам, так как он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты.
  
2. Тогда некоторая женщина, Антонина не замужем
+
Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина незамужняя. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию.
 
 
3. По [[#observation2|наблюдению 2]], Антонине никто не делал предложения
 
 
 
4. Но Ян сделал предложения всем женщинам, т.к. он остался не женат
 
 
 
5. Получаем противоречие
 
 
6. Аналогичные утверждения можно повторить и отталкиваясь от того, что не занята некоторая девушка, поэтому предложение доказано
 
 
}}
 
}}
 
  
 
{{Лемма
 
{{Лемма
 
|id=lemma3
 
|id=lemma3
|about=Лемма 3
+
|about=Лемма <tex>3</tex>
 
|statement=
 
|statement=
Нет неустойчивых пар.
+
После завершения алгоритма не будет неустойчивых пар.
 
|proof=
 
|proof=
1. Предположим A-b (A, B — мужчины; a, b — женщины; A женат на a, B женат на b) — нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли
+
Предположим <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> — устойчивая пара.
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> — устойчивая пара.
 
+
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
 
|id=lemma4
|about=Лемма 4 (man-optimality)
+
|about=man-optimality
 
|statement=
 
|statement=
 
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
 
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
 +
|proof=
 +
Докажем от противного, что для каждого мужчины не существует устойчивого паросочетания, в котором его супругой была бы более желанная для него женщина.
 +
 +
Предположим, для мужчины <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>, неустойчиво.
 +
 
}}
 
}}
  
{{Лемма
+
{{Лемма  
 
|id=lemma5
 
|id=lemma5
|about=Лемма 5 (woman-pessimality)
+
|about=woman-pessimality
 
|statement=
 
|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>. То есть для <tex>c</tex> есть мужчина, который более привлекателен, чем её муж.
 +
 
}}
 
}}
 
Эти две леммы оставим без доказательства, интересющиеся могут обратится к документу http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf (с.5)
 
  
 
== Обобщения задачи ==
 
== Обобщения задачи ==
  
Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. [[http://ru.wikipedia.org/wiki/Задача_о_соседях_по_комнате|Задача о соседях по комнате]])
+
Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть) <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>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>(K-1)</tex> "филиалов" для каждого университета (<tex>K</tex> — квота). И добавлением фиктивного университета (поступление в который означает, что кандидату придется попробовать поступить через год).
  
 
== Применения в реальной жизни ==
 
== Применения в реальной жизни ==
Строка 156: Строка 149:
 
* Распределение донорских органов по нуждающимся в них людям
 
* Распределение донорских органов по нуждающимся в них людям
  
Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в 2012 году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в 2008 году.
+
Решение данной задачи было отмечено при вручении Нобелевской премии по экономике в <tex>2012</tex> году за «теорию стабильного распределения и практическое применение рыночных моделей». Её получили один из создателей алгоритма, Ллойд Шепли, а также Элвин Рот, во многом развивший исследования Ллойда Шепли и Дэвида Гейла. Сам Гейл не был удостоен премии, вероятно, лишь в силу того, что умер в <tex>2008</tex> году.
 +
 
 +
== Примечания ==
 +
<references/>
  
== Ссылки ==
+
== См. также  ==
 +
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях|Паросочетания]]
 +
== Источники информации ==
  
 
* [http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf Stable matching, Prinston lecture's presentation]
 
* [http://www.cs.princeton.edu/courses/archive/spring05/cos423/lectures/01stable-matching.pdf Stable matching, Prinston lecture's presentation]
Строка 164: Строка 162:
 
* [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://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 Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]
 
* [http://ge.tt/api/1/files/4LU3zaD1/0/blob?download Устойчивость супружеских пар и другие комбинаторные задачи (Статья Дональда Кнута)]
 
+
* [http://kek.ksu.ru/eos/Lerner/KnuthRu.pdf Устойчивость супружеских пар и другие комбинаторные задачи - Казанский государственный университет]
  
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о паросочетании]]
 
[[Категория: Задача о паросочетании]]

Текущая версия на 19:05, 4 сентября 2022

Определение:
Пара [math]\langle A, b\rangle[/math] называется неустойчивой (англ. unstable pair), если:
  1. В паросочетании есть пары [math]\langle A, a\rangle[/math] и [math]\langle B, b\rangle[/math] ([math]A[/math] женат на [math]a[/math], [math]B[/math] женат на [math]b[/math]);
  2. [math]A[/math] предпочитает [math]b[/math] элементу [math]a[/math];
  3. [math]b[/math] предпочитает [math]A[/math] элементу [math]B[/math].


Определение:
Устойчивое паросочетание (англ. stable matching) — паросочетание без неустойчивых пар.


Задача:
Найти полное устойчивое паросочетание между элементами двух множеств размера [math]n[/math], имеющими свои предпочтения.


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

Есть [math]n[/math] мужчин и [math]n[/math] женщин. Они обладают следующими особенностями:

  1. Каждый человек оценивает лишь людей противоположного пола (все гетеросексуальны);
  2. Каждый мужчина может отсортировать женщин от наименее привлекательной к наиболее привлекательной, причем его предпочтения не меняются (у каждого мужчины своя функция оценки);
  3. Каждая женщина может отсортировать мужчин от наименее привлекательного к наиболее привлекательному, причем её предпочтения не меняются (у каждой женщины своя функция оценки).


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

Рассмотрим некоторое паросочетание в МЖ.

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

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

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

  1. Мужчины делают предложение наиболее предпочитаемой женщине.
  2. Каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть» (помолвка), на все остальные отвечает «нет» (отказ).
  3. Мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают.
  4. Если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть».
  5. Шаги [math]1[/math]-[math]4[/math] повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.

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

 // Изначально все мужчины не женаты и все женщины незамужние.
 while существует свободный мужчина
   M = некоторый свободный мужчина
   w = первая женщина из текущего списка M
   if w свободна
     помечаем M и w помолвленными
   else if w предпочитает M своему текущему жениху M'
     помечаем M и w помолвленными
     вычёркиваем w из списка предпочтений M'
     помечаем M' свободным
   else
     вычёркиваем w из списка предпочтений M

Время работы алгоритма — [math]O(n^2)[/math], так как количество итераций цикла [math]\mathrm {while}[/math] не превосходит [math]O(n^2)[/math], где [math]n[/math] равно размеру каждого из данных множеств.

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

Утверждение (Наблюдение [math]1[/math]):
Мужчины делают предложения женщинам в порядке убывания симпатии.
Утверждение (Наблюдение [math]2[/math]):
Как только женщина была помолвлена, она не может стать непомолвленной, она может только улучшить свой выбор (сказать «может быть» более предпочтительному кандидату).

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

Лемма (Лемма [math]1[/math]):
Алгоритм завершается после максимум [math]n^2[/math] итераций цикла [math]\mathrm{\mathbf{while}}[/math].
Доказательство:
[math]\triangleright[/math]
На каждой итерации мужчина делает предложение очередной женщине. Но всего может быть не более [math]n^2[/math] предложений.
[math]\triangleleft[/math]

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

Лемма (Лемма [math]2[/math]):
Все мужчины и женщины будут заняты.
Доказательство:
[math]\triangleright[/math]

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

Аналогичные рассуждения применяем для женщин. Пусть какая-то женщина незамужняя. Значит, есть мужчина, который остался не женат. Но мы доказали, что по завершении алгоритма все мужчины заняты. Снова пришли к противоречию.
[math]\triangleleft[/math]
Лемма (Лемма [math]3[/math]):
После завершения алгоритма не будет неустойчивых пар.
Доказательство:
[math]\triangleright[/math]

Предположим [math]\langle A, b\rangle[/math] (где [math]A[/math], [math]B[/math] — мужчины; [math]a[/math], [math]b[/math] — женщины; [math]A[/math] женат на [math]a[/math], [math]B[/math] женат на [math]b[/math]) — нестабильная пара в паросочетании, найденном алгоритмом Гейла-Шепли. Возможны два случая:

  1. [math]A[/math] не делал предложение [math]b[/math]. Значит, [math]A[/math] находит [math]a[/math] более привлекательной, чем [math]b[/math]. Но чтобы рассматриваемая пара была неустойчивой, необходимо, чтобы [math]b[/math] для [math]A[/math] была более привлекательна, чем [math]a[/math]. Следовательно, [math]\langle A, b\rangle[/math] — устойчивая пара.
  2. [math]A[/math] делал предложение [math]b[/math]. Тогда был такой момент, когда [math]b[/math] отказала [math]A[/math], значит, [math]b[/math] находит [math]B[/math] более привлекательным, чем [math]A[/math]. Снова получается, что [math]\langle A, b\rangle[/math] — устойчивая пара.
[math]\triangleleft[/math]

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

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

Лемма (man-optimality):
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
Доказательство:
[math]\triangleright[/math]

Докажем от противного, что для каждого мужчины не существует устойчивого паросочетания, в котором его супругой была бы более желанная для него женщина.

Предположим, для мужчины [math]A[/math] это свойство не выполняется. Так как он оказался женат не на лучшей из кандидатур, то существует женщина [math]a[/math], которая предпочла ему другого, более привлекательного мужчину [math]B[/math], при этом женщина [math]a[/math] для мужчины [math]B[/math] стоит на первом месте в его текущем списке. Предположим, существует устойчивое паросочетание, содержащее [math]\langle A, a\rangle[/math]. По определению, в устойчивом паросочетании нет неустойчивых пар. Пара [math]\langle B, a\rangle[/math] станет неустойчивой, если [math]B[/math] будет предпочитать [math]a[/math] своей супруге. Значит, [math]B[/math] женат на ком-то, кто лучше, чем [math]a[/math]. Но такое невозможно, так как [math]a[/math] стоит для него на первом месте. Таким образом, если женщина [math]a[/math] вычёркивается из списка предпочтений мужчины [math]A[/math], то любое паросочетание, содержащее [math]\langle A, a\rangle[/math], неустойчиво.
[math]\triangleleft[/math]
Лемма (woman-pessimality):
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
Доказательство:
[math]\triangleright[/math]

Пусть [math]A[/math], [math]B[/math] — мужчины; [math]c[/math], [math]d[/math] — женщины; [math]A[/math] женат на [math]d[/math], [math]B[/math] женат на [math]c[/math].

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

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

Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть) [2].

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

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

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

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

  • Распределение студентов по коллеждам в США
  • Распределение интернов по больницам
  • Распределение донорских органов по нуждающимся в них людям

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

Примечания

  1. https://ru.wikipedia.org/wiki/American_Mathematical_Monthly American Mathematical Monthly 69, 9-14, 1962.
  2. https://ru.wikipedia.org/wiki/Задача_о_соседях_по_комнате Задача о соседях по комнате

См. также

Источники информации