Алгоритм Гейла – Шепли - Gale–Shapley algorithm

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

Фон

Основная статья: проблема стабильного согласования

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

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

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

Решение

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

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

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

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

Сложность выполнения этого алгоритма составляет куда это количество мужчин или женщин.[4]

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

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

Алгоритм

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

Оптимальность решения

Основная статья: Решетка стабильных соответствий
Доказательство того, что отсроченное принятие оптимально для мужчин

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

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

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

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

Стратегические соображения

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

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

Реализация в программных пакетах

  • р: Алгоритм Гейла – Шепли (также называемый алгоритмом отложенного принятия) для стабильного брака и проблема больниц / жителей доступен как часть сопоставление рынков[7][8] и MatchR[9] пакеты.
  • API: MatchingTools API предоставляет бесплатный интерфейс прикладного программирования для алгоритма Гейла – Шепли.[10]
  • Python: Алгоритм Гейла – Шепли включен вместе с несколькими другими хорошо известными игровыми алгоритмами в соответствие библиотека,[11] и QuantEcon / MatchingMarkets.py упаковка[12] включает несколько других для обобщенных игр на совпадение.
  • MATLAB: Алгоритм Гейла – Шепли реализован в assign2DStable функция, которая является частью Лаборатория военно-морских исследований США Бесплатная библиотека компонентов трекера.[13]

Заявление

В 1980-х годах Рот исследовал соответствие между интернами-интернами и больницами и показал, что алгоритм, который тогда использовался Национальная программа подбора жильцов Информационная служба, которая подбирала кандидатов на резидентство по больницам, была успешной, потому что она следовала принципам, аналогичным тем, которые кодируются алгоритмом Гейла-Шепли. В середине 1990-х Рот был призван улучшить алгоритм NRMP, чтобы сделать сопоставление более эффективным и лучше удовлетворить особые потребности, такие как размещение пар с двумя врачами в одной больнице. Рот разработал улучшенный алгоритм, работая с Эллиоттом Перансоном, основателем канадской компании National Matching Services Inc. в Торонто.[14]

Смотрите также

Рекомендации

  1. ^ Gale, D .; Шепли, Л. С. (1962). «Прием в колледж и стабильность брака». Американский математический ежемесячный журнал. 69 (1): 9–14. Дои:10.2307/2312726. JSTOR  2312726.
  2. ^ Гарри Майерсон: "Проблема стабильного брака", Обзор Брандейса 12, 1992 (онлайн ).
  3. ^ Бергстром, Теодор С. (июнь 1992 г.). "Обзор Двустороннее сопоставление: исследование теоретико-игрового моделирования и анализа А.Э. Рота и М.А.О. Сотомайора ". Журнал экономической литературы. 30 (2): 896–898. JSTOR  2727713.
  4. ^ Ивама, Кадзуо; Миядзаки, Шуичи (2008). «Обзор проблемы стабильного брака и его вариантов» (PDF). Международная конференция по образованию и исследованиям в области информатики для общества, распространяющего знания (icks 2008): 131–136. Дои:10.1109 / ICKS.2008.7. HDL:2433/226940. ISBN  978-0-7695-3128-1.
  5. ^ Дубинс, Л.; Фридман, Д.А. (1981). «Макиавелли и алгоритм Гейла – Шепли». Американский математический ежемесячный журнал. 88 (7): 485–494. Дои:10.2307/2321753. МИСТЕР  0628016.
  6. ^ Хуанг, Цзянь-Чжун (2006). «Обман со стороны мужчин в стабильном алгоритме сопоставления Гейла-Шепли». В Азаре, Йосси; Эрлебах, Томас (ред.). Алгоритмы - ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11-13 сентября 2006 г., Труды. Конспект лекций по информатике. 4168. Springer. С. 418–431. Дои:10.1007/11841036_39. МИСТЕР  2347162.
  7. ^ Кляйн, Т. (2015). «Анализ стабильных соответствий в R: Package MatchingMarkets» (PDF). Виньетка для R Package MatchingMarkets.
  8. ^ «MatchMarkets: Анализ стабильных совпадений». R Project.
  9. ^ "matchingR: алгоритмы сопоставления в R и C ++". R Project.
  10. ^ "MatchingTools API".
  11. ^ Wilde, H .; Рыцарь, В .; Гиллард, Дж. (2020). «Matching: библиотека Python для решения игр на совпадение». Журнал открытого программного обеспечения. Дои:10.21105 / joss.02169.
  12. ^ "matchingMarkets.py". Пакет Python.
  13. ^ «Библиотека компонентов трекера». Репозиторий Matlab. Получено 5 января, 2019.
  14. ^ "Идеальное соответствие Нобелевской премии по экономике". Научный журнал. Получено 5 декабря, 2020.

внешняя ссылка