Первый алгоритм, принесший своим создателям Нобелевскую премию, был изначально сформулирован двумя математиками, Дэвидом Гейлом и Ллойдом Шепли, в 1962 году. Они использовали алгоритм подбора партнеров для решения так называемой «Задачи о марьяже». Гейл умер в 2008-м, так и не успев получить своей награды, но Шепли разделил премию 2012 года с экономистом Элвином Ротом, который разглядел важность этого алгоритма не только в вопросе личных связей, но и в применении к социальным проблемам, в том числе к справедливому предоставлению услуг здравоохранения или мест для обучения в вузах.
Шепли эта награда развеселила. «Я считаю себя математиком, а премию получил по экономике, – сказал он, явно удивленный решением комитета. – Я никогда, никогда в жизни не учился экономике». Но из его математических построений были выведены важные экономические и социальные следствия.
Задача о марьяже, которую решили Шепли и Гейл, больше похожа на салонную игру, чем на элемент передовой экономической теории. Чтобы понять, в чем именно состоит эта задача, представим себе четырех гетеросексуальных мужчин и четырех гетеросексуальных женщин. Всем им предложили расположить четырех представителей противоположного пола в порядке личных предпочтений. Алгоритм должен распределить их по парам так, чтобы получить устойчивые браки. Это означает, что в результате ни один мужчина и ни одна женщина не должны стремиться друг к другу больше, чем к назначенным им партнерам. В противном случае вполне вероятно, что в какой-то момент они оставят своих супругов и сбегут друг с другом. На первый взгляд не вполне ясно, можно ли вообще решить эту задачу – даже при наличии всего четырех пар.
Возьмем один конкретный пример и рассмотрим, как Гейлу и Шепли удалось гарантировать стабильность этих союзов, причем систематическим и алгоритмическим образом. Роли четырех мужчин у нас будут играть четыре короля из карточной колоды: король пик, король червей, король бубен и король треф. Женщинами будут соответствующие дамы. Все короли и дамы выразили свои предпочтения:
Для королей:
Для дам:
Предположим теперь, что вначале мы предлагаем сочетать каждого из королей с дамой той же масти. Почему эта комбинация даст неустойчивые браки? Дама треф назвала короля треф наименее предпочтительным партнером, так что, честно говоря, она будет счастливее с любым другим королем. А теперь посмотрим на список короля червей: дама червей стоит у него на последнем месте. Он явно предпочел бы даму треф тому варианту, который ему предложили. В этом сценарии можно предположить, что дама треф и король червей сбегут от своих супругов друг с другом. Таким образом, подбор дам и королей по масти приводит к неустойчивым бракам.
Как же подобрать пары так, чтобы никакие две карты в конце концов не сбежали друг с другом? Вот какой механизм разработали Гейл и Шепли. Он состоит из нескольких раундов предложений от дам королям, которые повторяются до тех пор, пока не получится распределения по устойчивым парам. В первом раунде работы этого алгоритма все дамы делают предложение королям, которых они предпочитают больше всего. Первое место в списке дамы пик занимает король червей. У дамы червей первым стоит король треф. Дама бубен выбирает короля пик, а дама треф делает предложение королю червей. Похоже, что король червей – главный сердцеед в этой компании: он получил сразу два предложения. Он выбирает из двух дам ту, которую предпочитает больше, то есть даму треф, и отказывает даме пик. Итак, у нас есть три предварительные помолвки и один отказ.
Первый раунд
Дама, получившая отказ, вычеркивает из своего списка первого кандидата и в следующем раунде делает предложение второму – королю пик. Но теперь король пик получает два предложения. В первом раунде ему сделала предложение дама бубен, а теперь – еще и дама пик. Судя по его рейтингу, он предпочитает даму пик. Поэтому он довольно жестокосердно отвергает даму бубен (с которой у него была заключена предварительная помолвка в первом раунде работы алгоритма).
Второй раунд
Это подводит нас к третьему раунду. В каждом раунде каждая отвергнутая дама делает предложение следующему королю из своего списка, а каждый король всегда выбирает лучшее из полученных предложений. В третьем раунде получившая отказ дама бубен делает предложение королю бубен (который до этого грустно стоял у стеночки, как тот мальчик, которого никто не берет к себе в команду на уроке физкультуры). Хотя дама бубен находится в нижней части его списка, у него нет лучшего варианта, так как остальные три дамы предпочли других королей, а те приняли их предложения.
Третий раунд
Наконец все участники разбиты по парам, и все браки устойчивы. Хотя мы изложили этот алгоритм в терминологии милой салонной игры с карточными дамами и королями, он применяется сейчас во всем мире: в Дании – для распределения детей по детским садам, в Венгрии – для записи учеников в школы, в Нью-Йорке – для назначения раввинов в синагоги, а в Китае, Германии и Испании – для подбора университетов для студентов. Национальная служба здравоохранения Великобритании использует его при подборе пациентов для получения донорских органов, что помогло спасти множество жизней.
Именно на основе задачи, которую решили Гейл и Шепли, построены современные алгоритмы, используемые службами знакомств. В их случае задача усложняется неполнотой информации. Предпочтения бывают непостоянными и относительными и могут меняться изо дня в день даже в рамках одних и тех же отношений. Но, по сути, эти алгоритмы стараются, исходя из предпочтений пользователей, подобрать им партнеров, с которыми они смогут образовать устойчивые и счастливые пары. Кроме того, имеющиеся данные говорят о том, что, может быть, в этой области лучше использовать алгоритмы, чем полагаться на человеческую интуицию.
Возможно, вы заметили в алгоритме, разработанном Гейлом и Шепли, любопытную асимметрию. В нашем примере дамы делали предложения королям. Изменится ли что-нибудь, если вместо этого мы предложим королям делать предложения дамам? Как это ни удивительно, изменится. В этом случае, поменяв королей и дам местами, мы получили бы в итоге другое распределение по устойчивым парам.
