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

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

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

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

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

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

Алгоритм

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

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

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

Замечания
  • Этот алгоритм гарантирует, что все женятся и браки стабильны.
  • Приведённый алгоритм даёт наилучший вариант для мужчин. То есть алгоритм Гэйла — Шепли, в котором мужчины делают предложения женщинам, всегда дает стабильное соответствие, которое является лучшим для всех мужчин среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет лучшим для всех женщин среди всех стабильных совпадений. Множество всех стабильных паросочетаний образует решётку относительно отношения «все мужчины предпочитают одно паросочетание другому», а вышеуказанные два решения являются верхним и нижним элементами этой решётки.
  • Алгоритм обеспечивает правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения.
    • Более того, алгоритм устойчив против групповой стратегии для мужчин, то есть никакая коалиция мужчин не может координировать искажение своих предпочтений так, чтобы все мужчины в коалиции были строго в лучшем положении[2]. Тем не менее, некоторая коалиция может искажать свои предпочтения так, что одни мужчины живут лучше, а другие мужчины сохраняют того же партнера.
  • Алгоритм не обеспечивает правдивый механизм для женщин (проверяющая сторона): каждая женщина может исказить свои предпочтения и получить лучшее соответствие.

История

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

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

Примечания
  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.
  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.
  4. Harry Mairson: «The Stable Marriage Problem», The Brandeis Review 12, 1992 (online).
  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.
  7. Нобелевская премия по экономике досталась двум американским ученым. Lenta.ru (15 октября 2012). Дата обращения: 3 марта 2021.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.