Алгоритм Гэйла — Шепли находит стабильное паросочетание.
Время выполнения полиномиально зависит от размера входных данных алгоритма.
В зависимости от того, как он используется, он может найти либо решение, оптимальное для участников с одной стороны сопоставления, либо для участников с другой стороны.
Алгоритм обеспечивает честный механизм с точки зрения участников, поэтому предоставление участником неверных данных может только ухудшить его результат.
Задача о нахождении стабильного паросочетания принимает в качестве входных данных равное количество участников двух типов (например, n мужчин и n женщин или n студентов-медиков и n стажёров), а также порядок предпочтений для каждого участника.
Паросочетание называется стабильным, когда нет ни одной пары элементов разных типов, не входящей в это паросочетание, в которой оба предпочитают друг друга своей текущей паре.
Алгоритм Гэйла — Шепли находит устойчивое паросочетание; в частности доказывает, что устойчивое паросочетание всегда существует (обычно оно не единственно).
Алгоритм
Анимация, демонстрирующая пример работы алгоритма Гэйла—Шепли
Алгоритм Гэйла — Шепли:
Каждый мужчина делает предложение первой женщине в своём списке. Каждая женщина отвечает «может быть» своему поклоннику, которого она предпочитает больше всего, и «нет» всем остальным женихам. Затем она временно «обручена» с женихом, которого она до сих пор предпочитает больше всего, и этот жених также временно обручен с ней.
В каждом последующем раунде сначала каждый незанятый мужчина делает предложение наиболее предпочтительной женщине, которой он еще не сделал предложение (независимо от того, обручена ли женщина). Затем каждая женщина отвечает «возможно», если она в настоящее время не помолвлена или если она предпочитает этого мужчину своему нынешнему временному партнеру (в этом случае она отвергает своего нынешнего временного партнера, который становится незанятым). Временный характер помолвки сохраняет право уже обрученной женщины «бросить» своего бывшего партнера.
Этот процесс повторяется до тех пор, пока все не будут задействованы.
Сложность выполнения этого алгоритма составляет , где — это количество мужчин или женщин[1].
Замечания
Этот алгоритм гарантирует, что все женятся и браки стабильны.
Приведённый алгоритм даёт наилучший вариант для мужчин. То есть алгоритм Гэйла — Шепли, в котором мужчины делают предложения женщинам, всегда дает стабильное соответствие, которое является лучшим для всех мужчин среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет лучшим для всех женщин среди всех стабильных совпадений. Множество всех стабильных паросочетаний образует решётку относительно отношения «все мужчины предпочитают одно паросочетание другому», а вышеуказанные два решения являются верхним и нижним элементами этой решётки.
Алгоритм обеспечивает правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения.
Более того, алгоритм устойчив против групповой стратегии для мужчин, то есть никакая коалиция мужчин не может координировать искажение своих предпочтений так, чтобы все мужчины в коалиции были строго в лучшем положении[2]. Тем не менее, некоторая коалиция может искажать свои предпочтения так, что одни мужчины живут лучше, а другие мужчины сохраняют того же партнера.
Алгоритм не обеспечивает правдивый механизм для женщин (проверяющая сторона): каждая женщина может исказить свои предпочтения и получить лучшее соответствие.
История
Алгоритм был предложен в 1962 году. Дэвид Гэйл и Ллойд Шепли доказали, что для любого равного числа мужчин и женщин всегда возможно решить задачу поиска стабильного паросочетания и сделать все браки стабильными. Они представили алгоритм для этого[3][4].
В 1984 году Элвин Рот заметил, что, по сути, тот же алгоритм уже использовался на практике с начала 1950-х годов в Национальной программе подбора резидентов[5].
Позднее Рот усовершенствовал алгоритм, работая с Эллиоттом Перансоном.
