Задача о марьяже

Если тебе уже чуть-чуть не за двадцать или чуть-чуть не за тридцать, то выйти замуж в Южной Корее даже с хорошим приданым - задача явно не из разряда простых. Об этом свидетельствует случай с 49-летней одинокой бизнесвуман, которой не смогла оказать содействие в сватовстве даже известная в стране брачная контора "Сонъу". Не помогло даже то, что невеста обладает приданным, превышающим 16 млн долларов. Камнем преткновения стало условие клиентки, чтобы будущий муж был на десять лет моложе. В огромном списке потенциальных женихов не оказалось никого, кто бы согласился на такое условие.

 Массовая свадьба в Южной Корее

Задача о марьяже — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам. Решение задачи было описано в 1962 году математиками Девидом Гейлом и Ллойдом Шепли в статье «Поступление в колледж и стабильность браков» в журнале American Mathematical Monthly. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия».

Множество практических механизмов на основе алгоритма Гейла-Шепли разработал нобелевский лауреат Элвин Рот.

Ллойд Шепли и Элвин Рот

Решение задачи:

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

Для алгоритма требуется порядка n² шагов, где n — число мужчин и женщин.