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

Алгоритм Гэйла — Шепли находит стабильное паросочетание. Время выполнения линейно зависит от размера входных данных алгоритма. В зависимости от того, как он используется, он может найти либо решение, оптимальное для участников с одной стороны сопоставления, либо для участников с другой стороны. Алгоритм обеспечивает честный механизм с точки зрения участников, поэтому предоставление участником неверных данных может только ухудшить его результат.

Алгоритм назван в честь Дэвида Гэйла и Ллойда Шепли.

Формулировка задачиПравить

Задача о нахождении стабильного паросочетания принимает в качестве входных данных равное количество участников двух типов (например, $\text{[math]}$ n мужчин и $\text{[math]}$ n женщин или $\text{[math]}$ n студентов-медиков и $\text{[math]}$ n стажёров), а также порядок предпочтений для каждого участника. Паросочетание называется стабильным, когда нет ни одной пары элементов разных типов, не входящей в это паросочетание, в которой оба предпочитают друг друга своей текущей паре.

Алгоритм Гэйла — Шепли находит устойчивое паросочетание; в частности доказывает, что устойчивое паросочетание всегда существует (обычно оно не единственно).

АлгоритмПравить

Алгоритм Гэйла — Шепли:

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

Сложность выполнения этого алгоритма составляет $\text{[math]}$ $\text{[math]}$ $O(n^{2})$ , где $\text{[math]}$ $\text{[math]}$ $n$ — это количество мужчин или женщин^[1].

ЗамечанияПравить

Этот алгоритм гарантирует, что все женятся и браки стабильны.

Приведённый алгоритм даёт наилучший вариант для мужчин. То есть алгоритм Гэйла — Шепли, в котором мужчины делают предложения женщинам, всегда дает стабильное соответствие, которое является лучшим для всех мужчин среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет лучшим для всех женщин среди всех стабильных совпадений. Множество всех стабильных паросочетаний образует решётку относительно отношения «все мужчины предпочитают одно паросочетание другому», а вышеуказанные два решения являются верхним и нижним элементами этой решётки.

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

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

ИсторияПравить

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

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

ПримечанияПравить

↑ Iwama, Kazuo (2008). “A Survey of the Stable Marriage Problem and Its Variants” (PDF). International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008): 131—136. DOI:10.1109/ICKS.2008.7. Архивировано (PDF) из оригинала 2021-08-12. Дата обращения 2021-03-02. Используется устаревший параметр |deadlink= (справка)
↑ Dubins, L. E. (1981). “Machiavelli and the Gale–Shapley algorithm”. American Mathematical Monthly. 88 (7): 485—494. DOI:10.2307/2321753.
↑ Gale, D. (1962). “College Admissions and the Stability of Marriage”. American Mathematical Monthly. 69 (1): 9—14. DOI:10.2307/2312726. Архивировано из оригинала 2017-09-25. Дата обращения 2021-03-02. Используется устаревший параметр |deadlink= (справка)
↑ Harry Mairson: «The Stable Marriage Problem», The Brandeis Review 12, 1992 (online Архивная копия от 27 сентября 2011 на Wayback Machine).
↑ Bergstrom, Theodore C. (June 1992). “Review of Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis by A. E. Roth and M. A. O. Sotomayor”. Journal of Economic Literature. 30 (2): 896—898.
↑ Economics Nobel Honors Perfect Match (неопр.). Science Mag. Дата обращения: 5 декабря 2020. Архивировано 20 октября 2020 года.
↑ Нобелевская премия по экономике досталась двум американским ученым (неопр.). Lenta.ru (15 октября 2012). Дата обращения: 3 марта 2021. Архивировано 27 июля 2020 года.

СсылкиПравить

Демонстрация алгоритма Гэйла — Шепли
Никита Калинин Паросочетания и алгоритм Гэйла — Шэпли (часть 1) + (часть 2) на YouTube

[IwamaMiyazaki2008-1] Iwama, Kazuo (2008). “A Survey of the Stable Marriage Problem and Its Variants” (PDF). International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008): 131—136. DOI:10.1109/ICKS.2008.7. Архивировано (PDF) из оригинала 2021-08-12. Дата обращения 2021-03-02. Используется устаревший параметр |deadlink= (справка)

[2] Dubins, L. E. (1981). “Machiavelli and the Gale–Shapley algorithm”. American Mathematical Monthly. 88 (7): 485—494. DOI:10.2307/2321753.

[3] Gale, D. (1962). “College Admissions and the Stability of Marriage”. American Mathematical Monthly. 69 (1): 9—14. DOI:10.2307/2312726. Архивировано из оригинала 2017-09-25. Дата обращения 2021-03-02. Используется устаревший параметр |deadlink= (справка)

[4] Harry Mairson: «The Stable Marriage Problem», The Brandeis Review 12, 1992 (online Архивная копия от 27 сентября 2011 на Wayback Machine).

[5] Bergstrom, Theodore C. (June 1992). “Review of Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis by A. E. Roth and M. A. O. Sotomayor”. Journal of Economic Literature. 30 (2): 896—898.

[6] Economics Nobel Honors Perfect Match (неопр.). Science Mag. Дата обращения: 5 декабря 2020. Архивировано 20 октября 2020 года.

[7] Нобелевская премия по экономике досталась двум американским ученым (неопр.). Lenta.ru (15 октября 2012). Дата обращения: 3 марта 2021. Архивировано 27 июля 2020 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]