7.3. Приложения теории мэтчинга
7.3.1. Распределение абитуриентов по вузам
Конечно, несмотря на красивую историю о поиске невест, столь цинично спаривать математику и чувства в реальности не предлагается, и описанные выше механизмы используются для решения совсем иных практических задач. Этим, в частности, объясняется то, что модель жива, несмотря на многочисленные претензии к ее предпосылкам.
Например, модифицированный алгоритм Гейла-Шепли для случая многоженства может быть использован при поступлении выпускников школ в высшие учебные заведения. У каждого из выпускников в голове имеется упорядоченный список вузов, в которые он готовится поступать. Важно, что списки разных абитуриентов могут сильно различаться. Кто-то хочет уехать в столицы, а кто-то остаться дома (к сожалению, в провинции такое случается крайне редко); кто-то стремится поступить в топовый вуз и впахивать там, а кто-то предпочитает с минимальными издержками получить диплом; есть выбор друзей (этот факт ситуацию сильно осложняет, делая совсем игровой) и мнение родителей, с которыми нельзя не считаться, и т. д.
Аналогично большинство вузов предпочло бы принять сильных и мотивированных на обучение студентов. Конечно, информации об абитуриентах у вузов не так много, но даже ЕГЭ (при всех его недостатках) довольно много говорит о знаниях и серьезности намерений поступающего (кстати, заметим, что не все практики понимают, что информация о баллах ЕГЭ тоже многомерная и для одних вузов ЕГЭ по русскому языку важнее ЕГЭ по математике, а для других – наоборот). Ну а добавкой может выступать портфолио – победы на олимпиадах и конкурсах, спортивные достижения, рекомендации уважаемых людей и прочая дополнительная информация.
Таким образом, мы оказываемся в условиях классической задачи о марьяжах в ее множественной постановке – нужно «поженить» вузы на абитуриентах наилучшим образом, то есть так, чтобы ни один абитуриент не захотел перейти в другой вуз, который готов видеть того больше, чем кого-то из ныне обучающихся студентов. При этом максимальное количество студентов в каждом вузе должно быть задано заранее.
Элвин Рот, получивший Нобелевскую премию одновременно с Ллойдом Шепли, реализовал данный механизм поступления в университеты и высшие школы на практике. Так что с 2003 года в Нью-Йорке, с 2005 в Бостоне, а позже – в Денвере, Новом Орлеане и многих других городах США процедура подачи заявления, ответа образовательной организации, где помимо приема или отказа может быть постановка в лист ожидания, и возможной переподачи заявления в значительной степени согласуется с идеями Гейла и Шепли. Одним из уже выявленных результатов внедрения данного механизма можно назвать значимое сокращение числа последующих переходов обучающихся из одного учебного заведения в другое.
Да и российские две волны поступления в вузы на основе баллов ЕГЭ, существовавшие до 2020 года, – это сильно упрощенная версия процедуры Гейла-Шепли. Отличий по большому счету два. Во-первых, это всё-таки процедура мгновенного согласия, а не отложенного – в первую волну уже идет окончательное зачисление на 80 % бюджетных мест. А во-вторых, достижение равновесия за два раунда в любом случае крайне маловероятно, поэтому всегда будет определенный процент недовольных, кто неправильно оценил шансы и не попал в университет мечты при наличии такой возможности или же вообще остался без бюджетного места.
Правда, нужно понимать, что отмена в 2021 году второй волны хоть и облегчила вузам процедуру зачисления, но сделала результаты приемной кампании совсем далекими от оптимума, что очевидно всем, кто так или иначе знаком со сложившейся ситуацией. Вероятно, организаторы рассчитывали на то, что абитуриенты будут подавать свои согласия с самого начала приёмной кампании, а затем, видя, что не проходят, перекладывать их на другие программы. Однако этот расчёт не оправдался. У абитуриентов не было стимулов этого делать – они сидели и ждали до самого конца, и конец был печальным. Поэтому главный урок этой неудачи такой: если вы рассчитываете, что люди будут поступать желательным для вас способом, то удостоверьтесь, что они тоже этого хотят. При этом существующие вычислительные мощности уже достаточны для того, чтобы реализовать полноценную версию алгоритма Гейла-Шепли в масштабах всей страны. Была бы на то соответствующая воля!
7.3.2. Другие приложения механизмов мэтчинга
Поступление в вузы – это далеко не единственная сфера применения механизмов мэтчинга. Уже упоминавшийся в прошлом параграфе Элвин Рот имплементировал их во множество других практических областей. Среди них нельзя не отметить усовершенствование программы NRMP («National resident matching program») распределения докторов и интернов по клиникам. Данный централизованный институт распределения новых докторов по клиникам действовал в США еще с середины XX в., однако его реализация была сопряжена с рядом существенных проблем.
Первая проблема: классическая схема, в которой больницы предлагали вакансии лучшим выпускникам медицинских университетов, а те давали согласие или отказывались, систематически ставила больницы в более выигрышное положение по сравнению с самими докторами. Помним: кто ищет – тот находит! Кто делает предложение – тот выигрывает. Больницы делали предложение и получали лучших достижимых для них докторов, а вот доктора были не всегда довольны получающимся распределением.
Вторая проблема была еще серьезнее. При поступлении абитуриентов в университеты, как правило, приоритеты не очень сильно связаны с предпочтениями третьих лиц. А вот среди выпускников вузов было уже значительное число семейных пар, которые, разумеется, хотели работать исключительно вместе. Старая схема это не учитывала, поэтому широкое распространение получила практика заключения договоров с больницами напрямую, в обход алгоритма NRMP. А такие действия, в свою очередь, оказывали отрицательные внешние эффекты и на остальных участников взаимодействия.
Поэтому в 1995 году Совет директоров программы обратился к Элвину Роту с предложением разработать улучшенный алгоритм, который бы позволил решить обнаруженные проблемы. В 1997 году работа была завершена и новая версия алгоритма была принята программой. В этой версии первое слово уже было за молодыми докторами. Ну и желание влюбленных пар распределиться в один госпиталь также было учтено.
Еще одной актуальнейшей задачей является создание процедуры распределения донорских органов по больным. Эта задача особенно важна в связи с тем, что легального рынка органов не существует ни в одной стране, кроме Ирана. С одной стороны, причина понятна – люди боятся злоупотреблений, а «продажа на органы» является одной из самых распространенных страшилок. С другой стороны, легализация помогла бы спасти сотни тысяч жизней. Ведь только в США пересадки почки ожидают более 120 тысяч человек, и многие из них умирают, не дождавшись трансплантации.
Что можно сделать в существующей ситуации? Донорство органов существует, но только в формате безвозмездной передачи от родственников. При этом нужно понимать, что донорская почка может не подходить пациенту по группе крови или быть несовместимой по иммунитету, и успешную трансплантацию можно осуществить только в цикле обменов таких людей, иногда достаточно большом. Это означает, что первый донор передает свою почку родственнику второго донора, второй – родственнику третьего и т. д. Наконец, последний донор замыкает цикл, передавая свою почку родственнику первого. К слову сказать, реальные циклы иногда содержат несколько десятков пар, и их выявление – это нетривиальная математическая задача, ключевой составляющей которой является нахождение максимального числа тех самых устойчивых паросочетаний. Так что можно сказать, что механизмы мэтчинга уже не только повышают общественное благосостояние, но и спасают человеческие жизни.
