ли способ поженить их таким образом, чтобы ни одна пара не имела
возможности развестись и соединиться с более предпочтительными
партнерами? Иначе говоря, требуется, чтобы каждый получил
наилучший вариант из тех, которые возможны. Та же самая задача
возникает и во многих других случаях. Например, абитуриенты хотят
поступать в лучшие университеты, а университеты хотят получить
хороших абитуриентов29.
Алгоритм для решения здесь очень простой. Предположим, что
мужчины начинают (кстати, в этом случае конечный результат
оказывается более выигрышным для мужчин). Мужчины делают
предложения тем женщинам, какие им нравятся. Часть женщин
принимает предложение, и тогда они выходят замуж и из дальнейшей
процедуры выбывают. Те, кто сразу не соглашается, ставят мужчин
как бы на лист ожидания и сохраняют этот список. На следующем
шаге оставшиеся мужчины опять делают предложение, опять кто-то
соглашается и т.д. Можно доказать, что этот процесс обязательно
заканчивается, и в результате возникает стабильное соединение. Это
значит, что если есть женщина, которой какой-то мужчина нравится
больше, чем ее муж, и она готова за него выйти, то этот мужчина не
готов на ней жениться (и наоборот).
Элвин Рот консультировал медицинские факультеты университетов.
Проблема заключалась в том, чтобы упорядочить процедуру выбора
места для интернатуры (медицинской последипломной практики).
Заканчивая медицинский факультет, выпускник-медик идет куда-то
работать в качестве интерна. Соответственно, больницы хотят
получить хороших интернов, а интерны хотят устроиться в хорошие
больницы. Анализируя различные реально существовавшие подходы,
Рот увидел, что в каких-то случаях система распределения налажена
удовлетворительно, а где-то она работает очень плохо. Чтобы
избежать сбоев, и студенты, и больницы пытались определиться как
можно раньше, в результате студенты распределялись по больницам
чуть ли не на первом курсе, когда даже не была определена
специализация студентов, и непонятно было, кто из них станет
хирургом, а кто невропатологом. В других же местах эта проблема
была решена. Рот увидел, что там, где дела обстоят хорошо, стороны
29
Наблюдая суету при поступлении в наши университеты, можно
предположить, что внедрение алгоритма Гейла-Шепли там не помешало бы.
Однако, как и в аналогичных случаях выше, следует заметить, что алгоритм
исходит из того, что и абитуриент, и университет заранее знают, чего они хотят,
и что их предпочтения не меняются в зависимости от третьих обстоятельств.