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

В математике, экономике и информатике, алгоритм Гейла – Шепли (также известный как алгоритм отложенного принятия ) - это алгоритм для поиска решения проблемы стабильного сопоставления, названный в честь Дэвида Гейла и Ллойда Шепли. Требуется полиномиальное время, а время линейное зависит от размера входных данных алгоритма. В зависимости от того, как он используется, он может найти либо решение, оптимальное для участников с одной стороны сопоставления, либо для участников с другой стороны. Это правдивый механизм с точки зрения участников, для которых он обеспечивает оптимальное решение.

• 1 Предпосылки
• 2 Решение
• 3 Алгоритм
• 4 Оптимальность решения
• 5 Стратегические соображения
• 6 Реализация в программных пакетах
• 7 См. Также
• 8 Ссылки
• 9 Внешние ссылки

Задача стабильного сопоставления в самой простой форме принимает на вход равное количество участников двух типов (n мужчин и n женщин или n студентов-медиков. и n стажировок, например), а также заказ для каждого участника с указанием их предпочтений, с кем он будет подбираться среди участников другого типа. Сопоставление является нестабильным, если:

1. существует элемент A первого сопоставленного набора, который предпочитает некоторый данный элемент B второго сопоставленного набора элементу, с которым уже сопоставлен A, и
2. B также предпочитает A элементу, с которым уже сопоставлен B.

Другими словами, сопоставление является стабильным, когда не существует никакого совпадения (A, B), которое оба предпочитают друг друга своему текущему партнеру при сопоставлении. Устойчивое сопоставление всегда существует, и алгоритмическая проблема, решаемая алгоритмом Гейла – Шепли, состоит в том, чтобы его найти.

Анимация, показывающая пример алгоритма Гейла – Шепли

В 1962 году Дэвид Гейл и Ллойд Шепли доказали, что для любого равного числа мужчин и женщин всегда можно решить СМП и сделать все браки стабильными. Для этого они представили алгоритм. В 1984 году Элвин Э. Рот заметил, что, по сути, тот же алгоритм уже использовался на практике с начала 1950-х годов в Национальной программе сопоставления жителей.

Алгоритм Гейла – Шепли. включает несколько «раундов» (или «итераций »):

• В первом раунде сначала а) каждый незанятый мужчина делает предложение женщине, которую он предпочитает больше всего, а затем б) каждый женщина отвечает «может быть» своему жениху, которого она предпочитает больше всего, и «нет» всем остальным женихам. Затем она временно «обручена» с женихом, которого она предпочитает больше всего, и этот жених также временно обручен с ней.
• В каждом последующем раунде сначала: а) каждый незанятый мужчина делает предложение наиболее предпочтительной женщине. которому он еще не сделал предложение (независимо от того, обручена ли женщина), и затем б) каждая женщина отвечает «возможно», если она в настоящее время не помолвлена ​​или предпочитает этого мужчину своему нынешнему временному партнеру (в данном случае, она отвергает своего нынешнего временного партнера, который теряет интерес). Временный характер помолвки сохраняет право уже обрученной женщины «обменять» (и, в процессе, «бросить» своего бывшего партнера).
• Этот процесс повторяется, пока все не станут

Сложность выполнения этого алгоритма составляет $O\; (n\; 2)\; \{\backslash \; displaystyle\; O\; (n\; ^\; \{2\})\}$, где $n\; \{\backslash \; displaystyle\; n\}$- количество мужчин или женщин.

Этот алгоритм гарантирует, что:

Все женятся

В конце концов, мужчина и женщина не могут быть незанятыми, поскольку он должен был сделать ей предложение в какой-то момент (поскольку мужчина в конечном итоге сделает предложение всем, если это необходимо), и, получив предложение, она обязательно будет обручена (с кем-то) после этого.

Браки стабильны

Пусть Алиса и Боб помолвлены, но не друг с другом. По завершении алгоритма Алиса и Боб не могут предпочесть друг друга своим текущим партнерам. Если Боб предпочитает Алису своему нынешнему партнеру, он, должно быть, сделал предложение Алисе до того, как сделал предложение своему нынешнему партнеру. Если Алиса приняла его предложение, но в конце концов не вышла за него замуж, она, должно быть, бросила его ради того, кто ей больше нравится, и, следовательно, не любит Боба больше, чем ее нынешний партнер. Если Алиса отклонила его предложение, то она уже была с кем-то, кто ей нравился больше, чем Боб.

алгоритм стабильное соответствие равно Инициализировать все m ∈ M и w ∈ W, чтобы освободить в то время как ∃ свободный мужчина m, у которого еще есть женщина w, чтобы сделать предложение сделать w: = первая женщина в списке m, которой m еще не сделал предложение, если w свободна затем (m, w) вступает в контакт else некоторая пара (m ', w) уже существует если w предпочитает m вместо m', то m 'становится свободным (m, w) становится включенным else (m', w) остается включенным end if end if repeat

Доказательство того, что отложенное принятие является оптимальным для мужчин

Существование различных стабильных сопоставлений поднимает вопрос: какое сопоставление возвращает алгоритм Гейла-Шепли? Подбор лучше для мужчин, для женщин или для среднего? В приведенном выше примере алгоритм сходится в одном раунде к оптимальному для мужчин решению, поскольку каждая женщина получает ровно одно предложение и, следовательно, выбирает это предложение как свой лучший выбор, гарантируя, что у каждого мужчины есть принятое предложение, и завершение матча.

Это общий факт: алгоритм Гейла-Шепли, в котором мужчины делают предложения женщинам, всегда дает стабильное соответствие, которое является лучшим для всех мужчин среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет лучшим среди всех стабильных совпадений для всех женщин. Эти два сопоставления являются верхним и нижним элементами более крупной структуры во всех стабильных сопоставлениях, решетки стабильных сопоставлений.

Чтобы увидеть это, рассмотрите иллюстрацию справа. Пусть A будет сопоставлением, сгенерированным алгоритмом предложения мужчин, а B - альтернативным стабильным сопоставлением, которое лучше, по крайней мере, для одного человека, скажем, m 0. Предположим, что m 0 совпадает в B с женщиной w 1, которую он предпочитает своему совпадению в A. Это означает, что в A m 0 посетил w 1, но она отвергла его (это обозначено зеленой стрелкой от m 0 до w 1). w 1 отвергла его в пользу какого-то мужчины, которого она предпочитает, скажем m 2. Таким образом, в B, w 1 соответствует m 0, но «тоскует» (хочет, но не соответствует) для m 2 (это обозначено красной стрелкой из от w 1 до m 2).

Поскольку B является стабильным соответствием, m 2 должно быть сопоставлено в B с какой-то женщиной, которую он предпочитает w 1, скажем, w 3. Это означает, что в A, m 2 посетил w 3, прежде чем достиг w 1, что означает, что w 3 отклонил его. По аналогичным соображениям и поскольку граф конечен, мы должны в конечном итоге иметь направленный цикл, в котором каждый мужчина был отвергнут в A следующей женщиной в цикле, которая отвергла его в пользу следующего мужчины в цикле. Но это невозможно, поскольку такой «цикл отказов» не может нигде начаться: предположим от противного, что он начинается, например, с m 0 - первый мужчина, отвергнутый соседней женщиной (w 1). По предположению, это отклонение происходит только после того, как m 2 переходит в w 1. Но это может произойти только после того, как w 3 отклонит m 2 - противоречие с тем, что m 0 является первым.

Алгоритм GS - это правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения. Более того, алгоритм GS является доказательством даже групповой стратегии для мужчин, т. Е. Никакая коалиция мужчин не может координировать искажение своих предпочтений так, чтобы все мужчины в коалиции были строго в лучшем положении. Тем не менее, некоторая коалиция может искажать свои предпочтения, так что одни мужчины живут лучше, а другие мужчины сохраняют того же партнера.

Алгоритм GS не соответствует действительности для женщин (проверяющая сторона) : каждая женщина может исказить свои предпочтения и найти лучший вариант.

• R : алгоритм Гейла – Шепли (также называемый алгоритмом отложенного принятия) для стабильного брака и проблемы больниц / резидентов доступен как часть пакеты matchingMarketsи matchingR.
• API : API MatchingTools предоставляет бесплатный интерфейс прикладного программирования для алгоритма Гейла – Шепли.
• Python : Алгоритм Гейла – Шепли включен вместе с несколькими другими хорошо известными игровыми алгоритмами сопоставления в библиотеку сопоставления, а пакет QuantEcon / MatchingMarkets.pyвключает несколько других для обобщенных игр сопоставления. 137>MATLAB : алгоритм Гейла – Шепли реализован в функции assign2DStable, которая является частью бесплатной библиотеки компонентов отслеживания Лаборатории морских исследований США.

• Аукцион с отсроченным акцептом

• Демонстрация JavaScript Гейла – Шепли