В математике , экономике и информатике , то алгоритм Гейла-Шепли (также известный как отложенный алгоритм принятия или предложить, и режекторный алгоритм ) является алгоритм для нахождения решения проблемы стабильной согласования , названный в честь Дэвида Гейла и Ллойд Шепли который описал это как решение как проблемы поступления в колледж, так и проблемы стабильного брака . Это занимает полиномиальное время , и время линейно зависит от размера входных данных алгоритма. Этоправдивый механизм с точки зрения предлагающих участников, для которых решение всегда будет оптимальным.
Задний план
Задача стабильного сопоставления в своей самой простой форме принимает в качестве входных данных равное количество участников двух типов (например, n мужчин и n женщин или n студентов-медиков и n стажировок), а также порядок для каждого участника, отдавая предпочтение своему выбору. кого сравнивать среди участников другого типа. Устойчивое сопоставление всегда существует, и алгоритмическая проблема, решаемая алгоритмом Гейла – Шепли, заключается в его поиске. Соответствующий является не стабильным , если:
- Существует элемент A первого согласованного набора, который предпочитает некоторый данный элемент B второго согласованного набора элементу, с которым A уже согласован, и
- B также предпочитает A элементу, которому уже соответствует B.
Другими словами, соответствие стабильно, когда нет совпадения ( A , B ), когда оба участника предпочитают кого-то другого своему текущему партнеру.
Решение
В 1962 году Дэвид Гейл и Ллойд Шепли доказали, что для любого равного числа мужчин и женщин всегда возможно решить SMP и сделать все браки стабильными. Они представили алгоритм для этого. [1] [2] В 1984 году Элвин Э. Рот заметил, что, по сути, тот же алгоритм уже использовался на практике с начала 1950-х годов в Национальной программе подбора жильцов . [3]
Алгоритм Гейла-Шепли включает в себя ряд «раундов» (или « итераций »):
- В первом раунде сначала а ) каждый незанятый мужчина делает предложение женщине, которую он предпочитает больше всего, а затем б ) каждая женщина отвечает «может быть» своему поклоннику, которого она предпочитает больше всего, и «нет» всем остальным женихам. Затем она временно «обручена» с женихом, которого она до сих пор предпочитает больше всего, и этот жених также временно обручен с ней.
- В каждом последующем раунде сначала а ) каждый незанятый мужчина делает предложение наиболее предпочтительной женщине, которой он еще не сделал предложение (независимо от того, была ли женщина уже помолвлена), а затем б ) каждая женщина отвечает «возможно», если она в настоящее время не помолвлена или если она предпочитает этого мужчину своему нынешнему временному партнеру (в этом случае она отвергает своего нынешнего временного партнера, который становится незанятым). Временный характер помолвки сохраняет право уже обрученной женщины «обменять» (и, в процессе, «бросить» своего бывшего партнера).
- Этот процесс повторяется до тех пор, пока все не будут задействованы.
Сложность выполнения этого алгоритма составляет где это количество мужчин или женщин. [4] Поскольку списки входных предпочтений также имеют размер, пропорциональныйвремя выполнения линейно зависит от размера ввода.
Этот алгоритм гарантирует, что:
- Все женятся
- В конце концов, не может быть ни мужчины, ни женщины одновременно незанятыми, поскольку он должен был сделать ей предложение в какой-то момент (поскольку мужчина в конечном итоге сделает предложение всем, если это необходимо), и, получив предложение, она обязательно будет помолвлена ( кому-то) после этого.
- Браки стабильны
- Пусть Алиса и Боб оба помолвлены, но не друг с другом. По завершении алгоритма Алиса и Боб не могут предпочесть друг друга своим текущим партнерам. Если Боб предпочитает Алису своему нынешнему партнеру, он, должно быть, сделал предложение Алисе до того, как сделал предложение своему нынешнему партнеру. Если Алиса приняла его предложение, но в конце концов не вышла за него замуж, она, должно быть, бросила его ради того, кто ей больше нравится, и, следовательно, не любит Боба больше, чем ее нынешний партнер. Если Алиса отклонила его предложение, она уже была с кем-то, кто ей нравился больше, чем Боб.
Алгоритм
алгоритм stable_matching : Инициализировать m ∈ M и w ∈ W, чтобы освободить, пока ∃ свободный мужчина m, у которого есть женщина w, которую он должен сделать. w: = первая женщина в списке м, которой м еще не сделал предложения если ∃ некоторая пара (m ', w), то если w предпочитает m, а не m', тогда m 'становится свободным (m, w) становится зацепленным концом, если еще (m, w) становится зацепленным концом, если повторяется
Оптимальность решения
Существование различных стабильных сопоставлений поднимает вопрос: какое сопоставление возвращает алгоритм Гейла-Шепли? Подбор лучше для мужчин, для женщин или для среднего? В приведенном выше примере алгоритм сходится в одном раунде к оптимальному для мужчин решению, потому что каждая женщина получает ровно одно предложение и, следовательно, выбирает это предложение, гарантируя, что у каждого мужчины есть принятое предложение, и завершение матча.
Это общий факт: алгоритм Гейла-Шепли, в котором мужчины делают предложения женщинам, всегда дает стабильное соответствие, которое является лучшим для всех мужчин среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет лучшим среди всех стабильных совпадений для всех женщин . Эти два сопоставления являются верхним и нижним элементами решетки устойчивых сопоставлений .
Чтобы убедиться в этом, рассмотрите иллюстрацию справа. Пусть 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 является доказательством даже групповой стратегии для мужчин, т. Е. Никакая коалиция мужчин не может координировать искажение своих предпочтений так, чтобы все мужчины в коалиции были в строго более выгодном положении. [5] Тем не менее, некоторая коалиция может искажать свои предпочтения так, что одни мужчины живут лучше, а другие сохраняют того же партнера. [6]
Алгоритм GS не соответствует действительности для женщин (проверяющая сторона): каждая женщина может исказить свои предпочтения и получить лучшее соответствие.
Реализация в программных пакетах
- R : Алгоритм Гейла – Шепли (также называемый алгоритмом отложенного принятия) для стабильного брака и проблемы больниц / резидентов доступен как часть пакетов
matchingMarkets
[7] [8] иmatchingR
[9] . - API : API MatchingTools предоставляет бесплатный интерфейс прикладного программирования для алгоритма Гейла – Шепли. [10]
- Python : Алгоритм Гейла – Шепли включен вместе с несколькими другими хорошо известными игровыми алгоритмами на соответствие в
matching
библиотеке [11], аQuantEcon/MatchingMarkets.py
пакет [12] включает несколько других для обобщенных игр на сопоставление. - MATLAB : алгоритм Гейла-Шепли реализован в
assign2DStable
функции, которая является частью бесплатной библиотеки компонентов трекера Лаборатории военно-морских исследований США . [13]
Признание
Шепли и Рот были удостоены Нобелевской премии по экономическим наукам 2012 года «за теорию стабильного распределения и практику рыночного дизайна »; Гейл умер в 2008 году. [14]
Смотрите также
Рекомендации
- ^ Gale, D .; Шепли, LS (1962). «Прием в колледж и стабильность брака» . Американский математический ежемесячник . 69 (1): 9–14. DOI : 10.2307 / 2312726 . JSTOR 2312726 .
- ^ Харри Мэрсон : «Стабильный Брак проблема», Брандес Обзор 12, 1992 ( онлайн ).
- ^ Бергстром, Теодор К. (июнь 1992 г.). "Обзор двустороннего сопоставления: исследование теоретико-игрового моделирования и анализа, проведенное А. Э. Ротом и МАО Сотомайором". Журнал экономической литературы . 30 (2): 896–898. JSTOR 2727713 .
- ^ Ивама, Кадзуо ; Миядзаки, Шуичи (2008). "Обзор проблемы стабильного брака и ее вариантов" (PDF) . Международная конференция по образованию и исследованиям в области информатики для общества, распространяющего знания (icks 2008) : 131–136. DOI : 10,1109 / ICKS.2008.7 . ЛВП : 2433/226940 . ISBN 978-0-7695-3128-1.
- ^ Дубинс, Л. Е .; Фридман, Д.А. (1981). «Макиавелли и алгоритм Гейла – Шепли». Американский математический ежемесячник . 88 (7): 485–494. DOI : 10.2307 / 2321753 . Руководство по ремонту 0628016 .
- ^ Хуанг, Цзянь-Чжун (2006). «Обман со стороны мужчин в стабильном алгоритме сопоставления Гейла-Шепли». В Азаре Йоси; Эрлебах, Томас (ред.). Алгоритмы - ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11-13 сентября 2006 г., Материалы . Конспект лекций по информатике. 4168 . Springer. С. 418–431. DOI : 10.1007 / 11841036_39 . Руководство по ремонту 2347162 .
- ^ Кляйн, Т. (2015). «Анализ стабильных сопоставлений в R: рынки сопоставления пакетов» (PDF) . Виньетка к R Package MatchingMarkets .
- ^ «MatchMarkets: Анализ стабильных совпадений» . R проект .
- ^ «MatchingR: алгоритмы сопоставления в R и C ++» . R проект .
- ^ «MatchingTools API» .
- ^ Wilde, H .; Рыцарь, В .; Гиллард, Дж. (2020). «Matching: библиотека Python для решения игр на совпадение» . Журнал открытого программного обеспечения . DOI : 10,21105 / joss.02169 .
- ^ "MatchingMarkets.py" . Пакет Python .
- ^ «Библиотека компонентов трекера» . Репозиторий Matlab . Проверено 5 января 2019 года .
- ^ «Идеальное соответствие Нобелевской премии по экономике» . Science Mag . Проверено 5 декабря 2020 года .
Внешние ссылки
- Демонстрация Gale – Shapley JavaScript