Задача о марьяже: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Mercury (обсуждение | вклад) |
Tosha (обсуждение | вклад) Нет описания правки |
||
Строка 22:
}}</ref> — математическая задача из области [[Кооперативная игра (математика)|кооперативных игр]]. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам<ref>[[Коняев, Андрей Юрьевич|Андрей Коняев]]. [http://lenta.ru/articles/2012/10/15/nobel/ Давай поженимся. Нобелевскую премию по экономике дали за стабильность выбора] // Lenta.ru 15.10.2012, 21:12:16</ref>. Решение задачи отмечено [[Нобелевская премия|Нобелевской премией]] по экономике 2012 года.
Решение задачи было описано в 1962 году математиками [[Гейл, Дэвид|Дэвидом Гейлом]] ([[Университет Брауна]]) и [[Шепли, Ллойд|Ллойдом Шепли]] ([[Принстонский университет]]) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly<ref>D. Gale and L. S. Shapley: «College Admissions and the Stability of Marriage», ''[[American Mathematical Monthly]]'' 69, 9-14, 1962.</ref>. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название '''[[Алгоритм Гэйла — Шэпли|алгоритма
Множество практических механизмов на основе алгоритма Гейла-Шепли разработал нобелевский лауреат [[Рот, Элвин|Элвин Рот]].
| |||