Код креативности. Как искусственный интеллект учится писать, рисовать и думать

Предположим теперь, что вначале мы предлагаем сочетать каждого из королей с дамой той же масти. Почему эта комбинация даст неустойчивые браки? Дама треф назвала короля треф наименее предпочтительным партнером, так что, честно говоря, она будет счастливее с любым другим королем. А теперь посмотрим на список короля червей: дама червей стоит у него на последнем месте. Он явно предпочел бы даму треф тому варианту, который ему предложили. В этом сценарии можно предположить, что дама треф и король червей сбегут от своих супругов друг с другом. Таким образом, подбор дам и королей по масти приводит к неустойчивым бракам.

Как же подобрать пары так, чтобы никакие две карты в конце концов не сбежали друг с другом? Вот какой механизм разработали Гейл и Шепли. Он состоит из нескольких раундов предложений от дам королям, которые повторяются до тех пор, пока не получится распределения по устойчивым парам. В первом раунде работы этого алгоритма все дамы делают предложение королям, которых они предпочитают больше всего. Первое место в списке дамы пик занимает король червей. У дамы червей первым стоит король треф. Дама бубен выбирает короля пик, а дама треф делает предложение королю червей. Похоже, что король червей – главный сердцеед в этой компании: он получил сразу два предложения. Он выбирает из двух дам ту, которую предпочитает больше, то есть даму треф, и отказывает даме пик. Итак, у нас есть три предварительные помолвки и один отказ.

Первый раунд

Дама, получившая отказ, вычеркивает из своего списка первого кандидата и в следующем раунде делает предложение второму – королю пик. Но теперь король пик получает два предложения. В первом раунде ему сделала предложение дама бубен, а теперь – еще и дама пик. Судя по его рейтингу, он предпочитает даму пик. Поэтому он довольно жестокосердно отвергает даму бубен (с которой у него была заключена предварительная помолвка в первом раунде работы алгоритма).

Второй раунд

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

Третий раунд

Наконец все участники разбиты по парам, и все браки устойчивы. Хотя мы изложили этот алгоритм в терминологии милой салонной игры с карточными дамами и королями, он применяется сейчас во всем мире: в Дании – для распределения детей по детским садам, в Венгрии – для записи учеников в школы, в Нью-Йорке – для назначения раввинов в синагоги, а в Китае, Германии и Испании – для подбора университетов для студентов. Национальная служба здравоохранения Великобритании использует его при подборе пациентов для получения донорских органов, что помогло спасти множество жизней.

Именно на основе задачи, которую решили Гейл и Шепли, построены современные алгоритмы, используемые службами знакомств. В их случае задача усложняется неполнотой информации. Предпочтения бывают непостоянными и относительными и могут меняться изо дня в день даже в рамках одних и тех же отношений. Но, по сути, эти алгоритмы стараются, исходя из предпочтений пользователей, подобрать им партнеров, с которыми они смогут образовать устойчивые и счастливые пары. Кроме того, имеющиеся данные говорят о том, что, может быть, в этой области лучше использовать алгоритмы, чем полагаться на человеческую интуицию.

Возможно, вы заметили в алгоритме, разработанном Гейлом и Шепли, любопытную асимметрию. В нашем примере дамы делали предложения королям. Изменится ли что-нибудь, если вместо этого мы предложим королям делать предложения дамам? Как это ни удивительно, изменится. В этом случае, поменяв королей и дам местами, мы получили бы в итоге другое распределение по устойчивым парам.

Дама бубен вышла бы замуж за короля червей, а дама треф – за короля бубен. То есть две дамы обменялись бы партнерами, но получили бы при этом немного менее предпочтительных супругов. Поскольку в обоих случаях пары получаются устойчивыми, когда предложения делают дамы, то дамы и получают самых лучших партнеров, на которых они могут рассчитывать. При смене ролей в более выгодном положении окажутся короли.

Американские студенты-медики, искавшие места в клинической ординатуре, узнали, что больницы использовали этот алгоритм для распределения таких мест, причем предложения исходили от больниц. Значит, студенты оказывались в менее выгодном положении. В течение некоторого времени студенты проводили агитацию, объясняя, насколько нечестной была эта система, и в конце концов алгоритм поменяли на обратный: теперь выбрать оптимальный вариант могут студенты.