Задача о марьяже
Материал из Википедии — свободной encyclopedia
Задача о марьяже или задача о стабильных браках[1] — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам[2]. Решение задачи отмечено Нобелевской премией по экономике 2012 года.
Решение задачи было описано в 1962 году математиками Дэвидом Гэйлом и Ллойдом Шепли[3]. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гэйла — Шепли или «алгоритма отложенного согласия».
Множество практических механизмов на основе алгоритма Гэйла — Шепли разработал нобелевский лауреат Элвин Рот. Эти механизмы были внедрены в деятельность больниц по набору врачей[4] и интернов[5], в правила многих американских профессиональных спортивных ассоциаций по набору спортсменов в команды[6]. В соответствии с предложенными институциональными механизмами фирмы набирают на стажировку сотрудников[7], суды нанимают секретарей[8], родители находят подходящие школы для детей[9]. Модель марьяжа в целом описывает последовательность действий индивидов при формировании пар на «рынках попутчиков» для совместных поездок, в некоторых видах спорта (парное фигурное катание, спортивные танцы), поведение участников в интерактивных реалити-шоу и пр.[10]