Ллойд Шепли, наверное, главный классик кооперативной теории игр. При этом он приложил руку не только к механизмам справедливого распределения доходов, но и к такой не денежной проблематике, как правильная организация браков. Более того, именно за эту задачу он в 2012 году (спустя ровно полвека после ее решения) получил Нобелевскую премию по экономике. Конечно же, дело не только и не столько в матримониальных процессах. Есть множество иных сфер приложения построенных алгоритмов, и о них мы, несомненно, еще поговорим. Но именно на примере любовных отношений нагляднее всего продемонстрировать проблему, которая по-английски называется словом «мэтчинг», а на русский лучше, чем «паросочетание» или «соответствие» (что отражает смысл далеко не в полном объеме), к сожалению, не переводится.
7.1.2. Постановка задачи о марьяжах
Итак, как и было сказано в предыдущем параграфе, пусть имеются два множества элементов – парни и девушки. Для каждого из них существует определенная система приоритетов в выборе партнера. То есть каждый парень может ранжировать всех девушек от самой любимой через компромиссные варианты до самой непривлекательной. Кстати, где-то может проходить нулевая черта, ниже которой парень вообще не захочет жениться, и никакая девушка, стоящая ниже, не имеет шансов стать его женой. Аналогично, каждая девушка в состоянии ранжировать всех парней на деревне, от первого до последнего, с той же оговоркой про одиночество.
Например, предпочтения могут выглядеть следующим образом (рис. 7.1):
Рис. 7.1. Пример предпочтений нескольких молодых людей и девушек
Это означает, что Петя влюблен в Веру, но, если этот сценарий окажется нереалистичным, он в принципе готов жениться в порядке убывания предпочтений на многих девушках – от Нади до Любы. В то же время, с его точки зрения, лучше навечно остаться холостяком, чем провести жизнь с Машей, Глашей и т. д. Любимая девушка Васи – Маша, но и у него есть некоторое число «запасных вариантов». А вот Надю устраивает только Петя, и если тот найдет свою Веру и любовь окажется взаимной, то Надя останется одна. В противном случае у Нади все шансы завоевать сердце своего принца.
Требуется разбить этих привередливых людей на идеально устойчивые пары. Механизм может быть любой – от свободного волеизъявления (правда, нужно понимать, что, хотя в реальной жизни идеальные совпадения и резонансы, как и чудеса, иногда случаются, но относиться к этому нужно так же, как к чуду) до жесткого диктаторского предписания, кому с кем жить. Однако даже в последнем случае мы верим, что этот диктатор просвещенный, и он хочет, чтобы после выполнения его предписаний никто (совсем никто!) не пожалел о сделанном выборе и не захотел развестись.
Подумаем, что в такой постановке создает угрозу развода. Только следующая ситуация: когда, например, парень любит девушку больше своей жены, а та, в свою очередь, любит его больше своего мужа, либо она одинока, а парень находится в ее «положительной области». Заметим, что парень не обязан быть для нее самым лучшим, он должен быть просто лучше, чем «статус-кво». То же самое мы можем сказать и в симметричной ситуации про девушку – не обязательно быть самой лучшей, достаточно просто быть лучше. И главное здесь – взаимность: чтобы не было угрозы распада брака, ни один из супругов не должен испытывать взаимного притяжения к чужому партнеру. Такова тайная формула вечной любви.
Неразделенные страсти, кстати, никто не запрещает – вполне допускается мечтать о чужих супругах, главное, чтобы без взаимности. Например, если моя любовь абсолютно счастлива со своим мужем и меня ни при каких обстоятельствах не полюбит, то как рациональный homo economicus я не буду разрушать идиллию со своей «номер два», любящей меня, и просто порадуюсь, что не оказался в куда менее приятной ситуации. Например, я мог оказаться выше нулевой черты только у девушки под номером 100500 из моего списка. Кстати, это тоже вполне устойчивое сочетание, поскольку я совсем не хочу одиночества, а предыдущие 100499 не хотят меня видеть в качестве мужа.
7.1.3. Алгоритм отложенного согласия Гейла-Шепли
Казалось бы, гарантировать, что среди тысяч или даже миллионов счастливых пар не найдется ни одной, где приведенная выше угроза реализуется, может только наивный мечтатель, но математика может прийти таким романтикам на помощь. Как это ни удивительно, имеется конструктивное решение этой задачи – алгоритм, который приведет к устойчивому разбиению на пары при абсолютно любых предпочтениях участников процесса.
Алгоритм отложенного согласия, предложенный Дэвидом Гейлом и Ллойдом Шепли, заключается в следующем. В первый вечер каждый жених идет с предложением руки и сердца к номеру один из своего списка. Для невест результаты данного действия могут сильно различаться. Под балконом первой красавицы будет петь серенады половина деревни, к какой-то девушке пришел единственный ухажер, а иная вообще никого не дождалась, что, однако, как мы увидим дальше, вовсе не повод накладывать на себя руки или даже просто впадать в уныние.
Что делают девушки? К некоторым не пришел никто или пришли только столь отвратительные персонажи из отрицательной области (вспоминаем про нулевую черту), что выдворить их восвояси и остаться в одиночестве – это меньшее из зол. Им ничего не остается, кроме как ждать и надеяться. А все остальные могут выбирать. Помним, что по мифологии циничных экономистов у каждой из них имеется индивидуальный список предпочтений. Итак, девушки прогоняют всех пришедших, кроме одного самого понравившегося кандидата. Правда, пока никаких обещаний – с ним можно погулять, пофлиртовать, назначить свидание на завтра, но не более того.
Итак, на следующий день ангажированные женихи, получившие расплывчатое «может быть», надеются на укрепление связи. А «свободные» (то есть посланные своими избранницами, поскольку не смогли конкурировать с более удачливыми соперниками, или вовсе оказавшиеся у избранниц «ниже черты») зализывают раны и готовятся постучаться в двери своих вице-фавориток – девушек, стоящих под номером два.
Как результат, кому-то из невест может сильно повезти именно на второй вечер. Скажем, девушка ни у кого не является номером один, но многие ставят ее на второе место. Это означает, что после одиночества первого вечера у нее будет аншлаг на второй день и не исключено, что среди визитеров окажется и ее «главный принц».
Во второй вечер девушки снова раздают желанные «может быть». Кстати, если новый жених понравился больше предыдущего, они легко разрывают «помолвку» первого этапа, сказав прошлому герою «Извини!», и обнадеживают нового избранника все тем же «может быть». И далее этот сценарий продолжается: ангажированные ждут и надеются, а посланные идут к следующим по списку. Однако на какой-то день неудачливый жених может обнаружить, что у него в списке не осталось девушек, находящихся выше нулевой черты. И это печальное событие означает, что он навсегда остается холостяком.
