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

В математике , экономике и информатике применяется алгоритм Гейла-Шепли (также известный как алгоритм отложенного принятия) . ^{[ 1 ]} алгоритм «предложить-отклонить» , ^{[ 2 ]} или алгоритм Бостонского пула ^{[ 1 ]}) — алгоритм поиска решения задачи устойчивого сопоставления . Он назван в честь Дэвида Гейла и Ллойда Шепли , опубликовавших его в 1962 году, хотя он использовался для Национальной программы подбора резидентов с начала 1950-х годов. Шепли и Элвин Э. Рот (указавшие на его предыдущее применение) получили Нобелевскую премию по экономике 2012 года за работу, включающую этот алгоритм.

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

Проблема устойчивого сопоставления и алгоритм Гейла-Шепли, решающий ее, имеют широкое практическое применение, в том числе сопоставление американских студентов-медиков с местами резидентуры и абитуриентов французских университетов со школами. Дополнительную информацию см. в разделе «Проблема стабильного брака» § Приложения .

Фон

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

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

Другими словами, совпадение стабильно, когда нет пары ( A , B ), в которой оба участника предпочитают друг друга своим подходящим партнерам. Если такая пара существует, сопоставление не является стабильным в том смысле, что члены этой пары предпочли бы покинуть систему и сопоставиться друг с другом, возможно, оставив других участников несопоставленными. Устойчивое паросочетание всегда существует, и алгоритмическая задача, решаемая алгоритмом Гейла – Шепли, состоит в его нахождении. ^{[ 3 ]}

Задачу стабильного соответствия также называют проблемой стабильного брака, используя метафору брака между мужчиной и женщиной, и многие источники описывают алгоритм Гейла-Шепли с точки зрения предложений руки и сердца. Однако эту метафору раскритиковали как сексистскую и нереалистичную: шаги алгоритма неточно отражают типичное или даже стереотипное человеческое поведение. ^{[ 4 ]}^{[ 5 ]}

Решение

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

В 1962 году Дэвид Гейл и Ллойд Шепли доказали, что для любого равного числа участников каждого типа всегда можно найти паросочетание, в котором все пары стабильны. Они представили алгоритм, позволяющий это сделать. ^{[ 6 ]}^{[ 7 ]} В 1984 году Элвин Э. Рот заметил, что по существу тот же алгоритм уже использовался на практике с начала 1950-х годов, как «алгоритм Бостонского пула», используемый Национальной программой сопоставления резидентов . ^{[ 1 ]}^{[ 8 ]}

Алгоритм Гейла-Шепли включает в себя несколько «раундов» (или « итераций »). С точки зрения соискателей и работодателей это можно выразить следующим образом: ^{[ 9 ]}

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

Детали реализации и временной анализ

Для эффективной реализации алгоритма каждый работодатель должен иметь возможность быстро найти следующего кандидата, а каждый кандидат должен иметь возможность быстро сравнивать работодателей. Один из способов сделать это — пронумеровать каждого заявителя и каждого работодателя от 1 до $n$ , где $n$ — количество работодателей и соискателей, а также хранить следующие структуры данных : ^{[ 10 ]}

Набор должностями работодателей с незаполненными
Одномерный массив , индексируемый работодателями, с указанием индекса предпочтений следующего заявителя, которому работодатель отправит предложение, первоначально по 1 для каждого работодателя.
Двумерный массив, индексированный работодателем и номером $i$ от 1 до $n$ , называя заявителя, который является сотрудником каждого работодателя $i$ мое предпочтение
Одномерный массив, индексируемый заявителями, с указанием их текущего работодателя, первоначально контрольное значение, например 0, указывает на то, что они безработные.
Двумерный массив, индексируемый заявителем и работодателем, определяющий позицию этого работодателя в списке предпочтений заявителя.

Настройка этих структур данных занимает $O(n^{2})$ время. С помощью этих структур можно найти работодателя с незаполненной вакансией, сделать предложение от этого работодателя следующему соискателю, определить, принято ли предложение, и обновить все структуры данных, чтобы отразить результаты этих шагов в постоянном режиме. время за предложение. После завершения работы алгоритма полученное совпадение можно считать из массива работодателей для каждого заявителя. Там может быть $O(n^{2})$ предложения до того, как у каждого работодателя закончатся предложения, поэтому общее время равно $O(n^{2})$ . ^{[ 10 ]}

Хотя эта временная граница является квадратичной по числу участников, ее можно рассматривать как линейное время, если измерять ее с точки зрения размера входных данных, двух матриц предпочтений размера $O(n^{2})$ . ^{[ 11 ]}

Гарантии правильности

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

Все совпадают: В конце концов, не может быть одинакового соискателя и работодателя. Работодатель, оставшийся непревзойденным в конце процесса, должен был сделать предложение всем заявителям. Но заявитель, получивший предложение, остается трудоустроенным до конца процесса, поэтому безработных соискателей быть не может. Поскольку количество претендентов и вакансий одинаково, открытых вакансий также не может остаться. ^{[ 9 ]}
Матчи стабильны: Ни один кандидат X и работодатель Y не могут отдать предпочтение друг другу по сравнению с их финальным совпадением. Если Y сделает предложение X , то X отклонит Y только после того, как получит еще лучшее предложение, поэтому X не может предпочесть Y своему последнему совпадению. И если Y перестанет делать предложения до того, как достигнет X в своем списке предпочтений, Y не сможет предпочесть X своему последнему совпадению. В любом случае X и Y не образуют нестабильную пару. ^{[ 9 ]}

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

Для одной и той же системы предпочтений может существовать множество устойчивых паросочетаний. Возникает вопрос: какое совпадение возвращает алгоритм Гейла – Шепли? Что лучше для соискателей, для работодателей или промежуточный вариант? Как оказывается, алгоритм Гейла-Шепли, в котором работодатели делают предложения соискателям, всегда дает одно и то же стабильное соответствие (независимо от порядка, в котором делаются предложения о работе), и его выбор – это устойчивое соответствие, наилучшее для всех работодателей. и худший для всех кандидатов среди всех стабильных совпадений. ^{[ 9 ]}

В обратной форме алгоритма каждый раунд состоит из того, что безработные соискатели пишут одно заявление о приеме на работу своему предпочтительному работодателю, а работодатель либо принимает заявление (возможно, увольняя для этого существующего сотрудника), либо отклоняет его. В результате получается совпадение, которое является лучшим для всех кандидатов и худшим для всех работодателей среди всех стабильных совпадений. Эти два паросочетания являются верхним и нижним элементами решетки устойчивых паросочетаний . ^{[ 12 ]}

В обеих формах алгоритма одна группа участников предлагает совпадения, а другая группа решает, принять или отклонить каждое предложение. Соответствие всегда лучше для группы, которая делает предложения, и хуже всего для группы, которая решает, как поступить с каждым предложением. ^{[ 12 ]}

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

Алгоритм Гейла-Шепли является правдивым механизмом с точки зрения предлагающей стороны. Это означает, что ни один предлагающий не сможет добиться лучшего соответствия, искажая свои предпочтения. Более того, алгоритм Гейла-Шепли даже является доказательством групповой стратегии для предлагающих, т. е. ни одна коалиция предлагающих не может координировать искажение своих предпочтений, так что все предлагающие в коалиции оказываются в строго лучшем положении. ^{[ 13 ]} Однако некоторые коалиции могут искажать свои предпочтения, в результате чего некоторые предлагающие оказываются в более выгодном положении, а другие сохраняют того же партнера. ^{[ 14 ]}

Алгоритм Гейла-Шепли неверен для участников, не предлагающих предложения. Каждый из них может исказить свои предпочтения и получить лучшее совпадение. ^{[ 15 ]} Особой формой манипуляции является усечение : представление только самых верхних альтернатив, подразумевая, что нижние альтернативы вообще неприемлемы. При полной информации достаточно рассмотреть искажения формы стратегий усечения. Однако успешное введение в заблуждение требует знания предпочтений других агентов; без таких знаний искажение фактов может дать агенту худшее задание. Более того, даже после того, как агент увидит окончательное совпадение, он не сможет вывести стратегию, которая в ретроспективе гарантировала бы лучший результат. Это делает алгоритм Гейла-Шепли безошибочным механизмом установления истины . Более того, в алгоритме Гейла-Шепли говорить правду — единственная стратегия, которая гарантирует отсутствие сожалений. Алгоритм Гейла-Шепли — единственный безотказный механизм в классе квантильно-устойчивых механизмов сопоставления. ^{[ 16 ]}

Обобщения

В своей первоначальной работе над этой проблемой Гейл и Шепли рассматривали более общую форму задачи устойчивого сопоставления, пригодную для поступления в университеты и колледжи . В этой задаче каждый университет или колледж может иметь свою собственную квоту , целевое количество студентов для приема, а количество студентов, подающих заявки на поступление, может отличаться от суммы квот, что обязательно приводит к тому, что либо некоторые студенты остаются несоответствующими, либо некоторые квоты остаться незаполненным. Кроме того, списки предпочтений могут быть неполными: если университет исключает студента из своего списка, это означает, что они предпочтут оставить свою квоту незаполненной, чем принять этого студента, а если студент исключит университет из своего списка, это означает, что он предпочтет остаться незачисленным, чем поступить в этот университет. Тем не менее, можно определить устойчивые паросочетания для этой более общей задачи, доказать, что устойчивые паросочетания всегда существуют, и применить тот же алгоритм для их поиска. ^{[ 6 ]}

Форма алгоритма Гейла-Шепли, выполняемая с помощью реального протокола, а не рассчитанная на компьютерах, используется для координации приема в высшие учебные заведения во Франции с 2018 года через систему Parcoursup . В этом процессе в течение лета перед началом школы абитуриенты получают предложения о зачислении и на каждом этапе процесса должны выбирать, принимать ли какое-либо новое предложение (и, если да, отклонить любое предыдущее предложение, которое они приняли). . Метод усложнен дополнительными ограничениями, из-за которых решаемая им задача не совсем является задачей устойчивого сопоставления. Его преимущество заключается в том, что студентам не нужно фиксировать свои предпочтения в начале процесса, а они могут определять свои собственные предпочтения по мере продвижения алгоритма на основе прямых сравнений между предложениями, которые они получили. . Важно, чтобы этот процесс включал небольшое количество раундов подачи предложений, чтобы он завершился до даты начала работы школ, но хотя теоретически может происходить большое количество раундов, на практике они, как правило, не происходят. ^{[ 17 ]} Теоретически было показано, что, если алгоритм Гейла-Шепли необходимо завершить досрочно, после небольшого количества раундов, в которых каждая вакантная позиция делает новое предложение, он, тем не менее, производит совпадения с высоким соотношением совпавших участников к нестабильным парам. . ^{[ 18 ]}

Признание

Шепли и Рот были удостоены Нобелевской премии по экономике 2012 года «за теорию стабильного распределения и практику проектирования рынка ». Гейл умер в 2008 году, что лишило его права на получение премии. ^{[ 19 ]}

См. также

Ссылки

^ Jump up to: ^а ^б ^с Рот, Элвин Э. (февраль 2003 г.). «Происхождение, история и дизайн постоянного матча». ДЖАМА . 289 (7): 909–912. дои : 10.1001/jama.289.7.909 .
^ Картер, Майкл В.; Прайс, Камилла К. (2000). Исследование операций: практическое введение . ЦРК Пресс. п. 102. ИСБН 9780849322563 .
^ Гасфилд, Дэн ; Ирвинг, Роберт В. (1989). Проблема стабильного брака: структура и алгоритмы . МТИ Пресс. п. 6. ISBN 9780262515528 .
^ Вагнер, Рой (апрель 2009 г.). «Математические браки: связь между математикой и семиотическим выбором». Социальные исследования науки . 39 (2): 289–308. дои : 10.1177/0306312708099443 . hdl : 20.500.11850/121579 .
^ Гиагкуси, Кириаки (март 2021 г.). Гендер и вычислительные алгоритмы: случай стабильного сопоставления (PDF) (магистерская диссертация). Афинский национальный университет имени Каподистрии, факультет истории и философии науки и факультет информатики и телекоммуникаций . Проверено 20 декабря 2023 г.
^ Jump up to: ^а ^б Гейл, Д .; Шепли, Л.С. (1962). «Поступление в колледж и стабильность брака» . Американский математический ежемесячник . 69 (1): 9–14. дои : 10.2307/2312726 . JSTOR 2312726 . Архивировано из оригинала 25 сентября 2017 г. Проверено 20 ноября 2019 г.
^ Мейрсон, Гарри (1992). «Проблема стабильного брака» . Обзор Брандейса . 12 .
^ Бергстром, Теодор К. (июнь 1992 г.). «Обзор двустороннего сопоставления: исследование теоретико-игрового моделирования и анализа, проведенное А.Э. Ротом и МАО Сотомайором». Журнал экономической литературы . 30 (2): 896–898. JSTOR 2727713 .
^ Jump up to: ^а ^б ^с ^д Эриксон, Джефф (июнь 2019 г.). «4.5 Стабильное соответствие» (PDF) . Алгоритмы . Университет Иллинойса. стр. 170–176 . Проверено 19 декабря 2023 г.
^ Jump up to: ^а ^б Кляйнберг, Джон ; Тардос, Ева (2006). «2.3 Реализация алгоритма устойчивого сопоставления с использованием списков и массивов». Алгоритм проектирования . Аддисон-Уэсли. стр. 42–47.
^ Гасфилд и Ирвинг (1989) , с. 182.
^ Jump up to: ^а ^б Кнут, Дональд Э. (1976). Стабильные браки и их связь с другими комбинаторными задачами (PDF) (на французском языке). Монреаль, Квебек: Les Presses de l'Université de Montréal. ISBN 0-8405-0342-3 . МР 0488980 . См., в частности, задачу 6, стр. 87–94.
^ Дубинс, Луизиана ; Фридман, Д.А. (1981). «Макиавелли и алгоритм Гейла – Шепли». Американский математический ежемесячник . 88 (7): 485–494. дои : 10.2307/2321753 . JSTOR 2321753 . МР 0628016 .
^ Хуанг, Чиен-Чунг (2006). «Обман мужчин в алгоритме стабильного сопоставления Гейла-Шепли». В Азаре, Йоси; Эрлебах, Томас (ред.). Алгоритмы – ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11–13 сентября 2006 г., Труды . Конспекты лекций по информатике. Том. 4168. Спрингер. стр. 418–431. дои : 10.1007/11841036_39 . МР 2347162 .
^ Гончаровский, Яннаи А.; Фридгут, Эхуд (апрель 2013 г.). «Сестринство в алгоритме сопоставления Гейла – Шепли» . Электронный журнал комбинаторики . 20 (2): П12:1–П12:18. arXiv : 1104.2217 . дои : 10.37236/3267 .
^ Фернандес, Марсело Ариэль (31 июля 2020 г.). «Отложенное принятие и откровение правды без сожалений» (Рабочий документ). Экономический факультет Университета Джонса Хопкинса.
^ Матье, Клэр (2018). «Алгоритмы поступления в колледж в реальном мире» (Приглашенная лекция на Европейском симпозиуме по алгоритмам). Университет Аалто.
^ Флорен, Патрик; Каски, Петтери; Полищук Валентин; Суомела, Юкка (август 2009 г.). «Почти стабильные сопоставления за счет усечения алгоритма Гейла – Шепли». Алгоритмика . 58 (1): 102–118. arXiv : 0812.4893 . дои : 10.1007/s00453-009-9353-9 .
^ Бхаттачарджи, Юдхиджит (15 октября 2012 г.). «Нобелевская премия по экономике присуждается за мастерство сватовства». Наука . 338 (6105): 314. doi : 10.1126/science.338.6105.314 . ПМИД 23087221 .

[roth-1] Jump up to: ^а ^б ^с Рот, Элвин Э. (февраль 2003 г.). «Происхождение, история и дизайн постоянного матча». ДЖАМА . 289 (7): 909–912. дои : 10.1001/jama.289.7.909 .

[carter-price-2] Картер, Майкл В.; Прайс, Камилла К. (2000). Исследование операций: практическое введение . ЦРК Пресс. п. 102. ИСБН 9780849322563 .

[gusfield-irving-3] Гасфилд, Дэн ; Ирвинг, Роберт В. (1989). Проблема стабильного брака: структура и алгоритмы . МТИ Пресс. п. 6. ISBN 9780262515528 .

[wagner-4] Вагнер, Рой (апрель 2009 г.). «Математические браки: связь между математикой и семиотическим выбором». Социальные исследования науки . 39 (2): 289–308. дои : 10.1177/0306312708099443 . hdl : 20.500.11850/121579 .

[giagkousi-5] Гиагкуси, Кириаки (март 2021 г.). Гендер и вычислительные алгоритмы: случай стабильного сопоставления (PDF) (магистерская диссертация). Афинский национальный университет имени Каподистрии, факультет истории и философии науки и факультет информатики и телекоммуникаций . Проверено 20 декабря 2023 г.

[gale-shapley-6] Jump up to: ^а ^б Гейл, Д .; Шепли, Л.С. (1962). «Поступление в колледж и стабильность брака» . Американский математический ежемесячник . 69 (1): 9–14. дои : 10.2307/2312726 . JSTOR 2312726 . Архивировано из оригинала 25 сентября 2017 г. Проверено 20 ноября 2019 г.

[mairson-7] Мейрсон, Гарри (1992). «Проблема стабильного брака» . Обзор Брандейса . 12 .

[bergstrom-8] Бергстром, Теодор К. (июнь 1992 г.). «Обзор двустороннего сопоставления: исследование теоретико-игрового моделирования и анализа, проведенное А.Э. Ротом и МАО Сотомайором». Журнал экономической литературы . 30 (2): 896–898. JSTOR 2727713 .

[jeffe-9] Jump up to: ^а ^б ^с ^д Эриксон, Джефф (июнь 2019 г.). «4.5 Стабильное соответствие» (PDF) . Алгоритмы . Университет Иллинойса. стр. 170–176 . Проверено 19 декабря 2023 г.

[kt-10] Jump up to: ^а ^б Кляйнберг, Джон ; Тардос, Ева (2006). «2.3 Реализация алгоритма устойчивого сопоставления с использованием списков и массивов». Алгоритм проектирования . Аддисон-Уэсли. стр. 42–47.

[FOOTNOTEGusfieldIrving1989182-11] Гасфилд и Ирвинг (1989) , с. 182.

[knuth-12] Jump up to: ^а ^б Кнут, Дональд Э. (1976). Стабильные браки и их связь с другими комбинаторными задачами (PDF) (на французском языке). Монреаль, Квебек: Les Presses de l'Université de Montréal. ISBN 0-8405-0342-3 . МР 0488980 . См., в частности, задачу 6, стр. 87–94.

[dubins-freedman-13] Дубинс, Луизиана ; Фридман, Д.А. (1981). «Макиавелли и алгоритм Гейла – Шепли». Американский математический ежемесячник . 88 (7): 485–494. дои : 10.2307/2321753 . JSTOR 2321753 . МР 0628016 .

[huang-14] Хуанг, Чиен-Чунг (2006). «Обман мужчин в алгоритме стабильного сопоставления Гейла-Шепли». В Азаре, Йоси; Эрлебах, Томас (ред.). Алгоритмы – ESA 2006, 14-й ежегодный европейский симпозиум, Цюрих, Швейцария, 11–13 сентября 2006 г., Труды . Конспекты лекций по информатике. Том. 4168. Спрингер. стр. 418–431. дои : 10.1007/11841036_39 . МР 2347162 .

[sisterhood-15] Гончаровский, Яннаи А.; Фридгут, Эхуд (апрель 2013 г.). «Сестринство в алгоритме сопоставления Гейла – Шепли» . Электронный журнал комбинаторики . 20 (2): П12:1–П12:18. arXiv : 1104.2217 . дои : 10.37236/3267 .

[16] Фернандес, Марсело Ариэль (31 июля 2020 г.). «Отложенное принятие и откровение правды без сожалений» (Рабочий документ). Экономический факультет Университета Джонса Хопкинса.

[mathieu-17] Матье, Клэр (2018). «Алгоритмы поступления в колледж в реальном мире» (Приглашенная лекция на Европейском симпозиуме по алгоритмам). Университет Аалто.

[almost-18] Флорен, Патрик; Каски, Петтери; Полищук Валентин; Суомела, Юкка (август 2009 г.). «Почти стабильные сопоставления за счет усечения алгоритма Гейла – Шепли». Алгоритмика . 58 (1): 102–118. arXiv : 0812.4893 . дои : 10.1007/s00453-009-9353-9 .

[nobel-19] Бхаттачарджи, Юдхиджит (15 октября 2012 г.). «Нобелевская премия по экономике присуждается за мастерство сватовства». Наука . 338 (6105): 314. doi : 10.1126/science.338.6105.314 . ПМИД 23087221 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]