«Марьяж»: Нобелевка за правильную организацию женитьбы
Правила: Даны два множества элементов — мужчины и женщины. Для каждого из них существует определенная система приоритетов в выборе партнера. Требуется разбить этих привередливых людей на идеально устойчивые пары: ни один из супругов не должен испытывать взаимного притяжения к чужому партнеру (неразделенные страсти никто не запрещает). В разных вариантах правил меняются выбирающая сторона (матриархат/патриархат), количество мужчин и женщин или разрешается многоженство.
История
Статья «Поступление в колледж и стабильность браков» Дэвида Гейла и Ллойда Шепли появилась в научном журнале American Mathematical Monthly в 1962 году. А в 2012-м Шепли получил за эту работу Нобелевскую премию по экономике.
Для решения задачи они предложили следующий патриархальный алгоритм. Сначала каждый жених идет с предложением руки и сердца к номеру один своего списка. Дальше женщины отвечают самым понравившимся кандидатам расплывчатым «может быть», а остальных отправляют восвояси. После этого неудачливые женихи стучатся в дверь своих вице-фавориток, и девушки вновь раздают желанные «может быть» (если новый жених понравился больше предыдущего, они даже могут разорвать «помолвку» первого этапа). Этот сценарий повторяется до тех пор, пока все женихи не смогут добиться целомудренного согласия невест, которое в конце игры магическим образом превращается в твердое «согласна».
Неизвестно, пытался ли кто-то именно так искать себе жену в реальности. Зато разработанный в статье алгоритм с успехом использовался для распределения студентов по колледжам, докторов по клиникам и даже донорских органов по больным. За это, собственно, и дали премию имени Нобеля.
Человеческие качества
Кажется, в этом несложном алгоритме можно вечно находить все новые детали. Так, игра заканчивается на первом же раунде, если всем мужчинам нравятся разные женщины. Феминистки тут должны возмутиться, ведь в этом случае мнение невест вообще не учитывается. К тому же стабильность разбиения еще совсем не означает всеобщего счастья: многие мужчины и женщины могут мечтать о чужих супругах, главное — чтоб без взаимности. И еще: алгоритм как будто специально создавался в духе последних решений Госдумы, ведь он подразумевает абсолютную гетеросексуальность.
— Это разбиение для задачи о марьяже отлично работает для студентов и колледжей, для интернов в госпиталях, для семейных пар, но не работает для голубых! — Профессор РЭШ Алексей Савватеев начинает увлеченно рисовать на бумаге схему: — У нас есть четыре гомосексуалиста A, B, C и D. У каждого, как водится, свои предпочтения. Например, A больше всего нравится B, потом C и потом D. Этот D вообще никого не интересует, и поэтому его предпочтения нам не важны. И, видишь, они не могут разбиться на устойчивые пары. Вот она, математика и жизнь. Разбивка на пары идет не для элементов двух множеств, а для элементов одного — и сразу все неустойчиво.