Википедия

Алгоритм Гэйла — Шепли: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
мНет описания правки
мНет описания правки
Строка 4:
Алгоритм обеспечивает '''честный механизм''' с точки зрения участников, поэтому предоставление участником неверных данных может только ухудшить его результат.
 
Алгоритм назван в честь [[ГейлГэйл, Дэвид|Дэвида ГейлаГэйла]] и [[Шепли, Ллойд|Ллойда Шепли]].
 
== Формулировка задачи ==
Строка 24:
* Этот алгоритм гарантирует, что все женятся и браки стабильны.
 
* Приведённый алгоритм даёт наилучший вариант для мужчин. То есть алгоритм Гейла-Гэйла — Шепли, в котором мужчины делают предложения женщинам, ''всегда'' дает стабильное соответствие, которое является ''лучшим для всех мужчин'' среди всех стабильных сопоставлений. Точно так же, если женщины делают предложение, то полученное соответствие будет ''лучшим для всех женщин'' среди всех стабильных совпадений. Множество всех стабильных паросочетаний образует [[Решётка (алгебра)|решётку]] относительно отношения «все мужчины предпочитают одно паросочетание другому», а вышеуказанные два решения являются верхним и нижним элементами этой решётки.
 
* Алгоритм обеспечивает правдивый механизм с точки зрения мужчин (предлагающей стороны). То есть ни один мужчина не может добиться лучшего соответствия для себя, искажая свои предпочтения.
Строка 32:
 
== История ==
Алгоритм был предложен в 1962 году. [[ГейлГэйл, Дэвид|Дэвид ГейлГэйл]] и [[Шепли, Ллойд|Ллойд Шепли]] доказали, что для любого равного числа мужчин и женщин всегда возможно решить задачу поиска стабильного паросочетания и сделать все браки стабильными. Они представили [[алгоритм]] для этого<ref>{{Cite journal|first=D.|author=Gale|title=College Admissions and the Stability of Marriage|journal=[[American Mathematical Monthly]]|volume=69|issue=1|pages=9–14|year=1962|doi=10.2307/2312726|url=http://www.dtic.mil/get-tr-doc/pdf?AD=AD0251958}}</ref><ref>Harry Mairson: «The Stable Marriage Problem», ''The Brandeis Review'' 12, 1992 ([http://www1.cs.columbia.edu/~evs/intro/stable/writeup.html online]).</ref>.
В 1984 году [[Рот, Элвин|Элвин Рот]] заметил, что, по сути, тот же алгоритм уже использовался на практике с начала 1950-х годов в Национальной программе подбора [[Клиническая ординатура|резидентов]]<ref>{{Cite journal|author=Bergstrom|first=Theodore C.|date=June 1992|issue=2|journal=Journal of Economic Literature|pages=896–898|title=Review of ''Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis'' by A. E. Roth and M. A. O. Sotomayor|volume=30}}</ref>.
Позднее Рот усовершенствовал алгоритм, работая с Эллиоттом Перансоном.
 
Шепли и Рот были удостоены [[Премия по экономике памяти Альфреда Нобеля|Нобелевской премии по экономическим наукам]] 2012 года «теорию стабильного распределения и практику устройства рынков»; ГейлГэйл умер в 2008 году<ref>{{Cite web|url=https://www.sciencemag.org/news/2012/10/economics-nobel-honors-perfect-match|title=Economics Nobel Honors Perfect Match|website=Science Mag|accessdate=December 5, 2020}} </ref><ref>{{cite web|title=Нобелевская премия по экономике досталась двум американским ученым|url=https://lenta.ru/news/2012/10/15/nobel/|website=Lenta.ru|date=2012-10-15|accessdate=2021-03-03}}</ref>.
 
== Примечания ==
Источник — https://ru.wikipedia.org/wiki/Алгоритм_Гэйла_—_Шепли