Представим ситуацию, когда на одном потоке встречаются n студентов и n студенток. Обе половины потока непременно хотят найти себе партнера для создания семьи. Представим, что обе половины составили рейтинг всех потенциальных n партнеров. Задача: составить пары таким образом, чтобы не нашлось ни одной студентки и ни одного студента из разных пар, желающих друг друга больше, чем своих настоящих бойфрендов и подруг. Иными словами – надо найти стабильное распределение людей по парам – и чтобы без измен!
В январе 1962 года, Гейл и Шепли опубликовали в American Mathematical Monthly статью «College Admissions and Stability of Marriage», где как раз и объяснили, как поженить студентов. Алгоритм, предложенный учеными, получил название «алгоритма отложенного выбора или согласия» (deferred choice/acceptance algorithm). Идея заключалась в следующем.
Выбор стабильного партнера невозможен с первой попытки, если только это не получится случайно.
Поэтому процесс выбора – это путь проб и ошибок. Чтобы выбрать верную половину, каждый студент, который пока без девушки, предлагает руку и сердце той студентке, которая ему нравится больше остальных. Каждая студентка, однако, сравнивает всех воздыхателей и отказывает всем, кроме одного, того, кто ей больше всего напоминает Джеймса Бонда. Ему она отвечает «может быть». После этого девушки начинают встречаться со своими бондами. Но замуж, однако, они выйти не спешат! Далее, понимая, что почему-то в глазах своей первоочередной пассии до Шона Коннери или хотя бы Даниэла Крейга он не дотянул, каждый одинокий студент делает предложение второй девушке в своем списке, вне зависимости от того, есть ли у нее уже парень или нет. Девушка же, в отношениях она или нет, опять отвечает «может быть» тому из воздыхателей, кто больше всего в ее глазах похож на агента Ее Величества, – это может быть ее настоящий парень, а может и новый ухажер. Всем остальным девушка дает «от ворот поворот». Таким образом, у каждой девушки в отношениях всегда есть возможность найти кавалера покруче и «сменить окраину на центр». В итоге не останется ни одного одинокого студента или студентки. Более того – все они поженятся, их брак будет стабильным и проживут они долго и счастливо, пережив ошибки молодости.
Этот алгоритм оказался исключительно работоспособным в самых разнообразных жизненных ситуациях: например, и в ситуации, если бы девушки принимали предложения сразу двух ухажеров одновременно! Может, это выглядит уже и не совсем реалистично для описания процесса создания семьи (по крайней мере, в большинстве из тех стран, где работал Джеймс Бонд), однако реализм вернется, если «девушки» будут олицетворять собой приемные комиссии различных университетов, а «ухажеры» – суть абитуриенты, подающие документы в эти университеты. Здесь и «ухажеры» могут приударить сразу за несколькими «девушками», и «девушки» примут знаки внимания очень многих «ухажеров».
Что же хорошего в этом алгоритме? Во-первых, Гейл и Шепли доказали, что алгоритм действительно найдет решение в подобных задачах распределения, даже в ситуациях, когда фантазии в предпочтениях сторон очень разнообразны. Во-вторых, решение будет стабильно в том смысле, что какие бы ни были у сторон фантазии, дальнейший поиск будет неуместен. Иными словами, всегда будут мужчины, желающие чужих женщин, и женщины, желающие чужих мужчин, однако в стабильном распределении их желания не будут взаимными.
Далее на исторической сцене появился Алвин Рот, который показал, что стабильное распределение – не обязательно оптимальное с индивидуальной точки зрения – иногда и женщине, и мужчине нужно остановиться, не доходя до конца списка – затрат будет меньше.
Скажите Бонду «нет», и для души будет спокойнее.