До сих пор сегодня, на этой лекции, мы рассматривали с вами в основном теорию. Однако эта теория мэтчингов, оказывается, имеет важные практические применения. На самом деле алгоритм отсроченного принятия предложения — это, фактически, попытка формализовать сложившиеся в нашем обществе обычаи. Эта попытка достаточно успешна. Существуют исследования, в которых изучено поведение мужчин и женщин на разных сайтах, посвященных знакомствам, и оказывается, что то, что происходит в реальности, а именно то, как мужчины и женщины знакомятся друг с другом на этих сайтах, и то, какие пары в результате этого формируются, очень похоже на результаты, которые получаются в результате работы алгоритма отсроченного принятия предложения. В работе «Matching and sorting in online dating» авторы оценивают предпочтения пользователей некоторого популярного сайта знакомств на основании имеющихся у них данных о наблюдаемых характеристиках мужчин и женщин. Затем они используют алгоритм Гейла — Шепли, чтобы предсказать, какие стабильные мэтчинги должны были бы получиться с теоретической точки зрения. Они сравнивают тот мэтчинг, который получается в реальности, с тем мэтчингом, который предсказывала теория, и оказывается, что эти мэтчинги оказываются очень похожи друг на друга, то есть теория очень хорошо предсказывает реальные разбиения мужчин и женщин на пары. Эту теорию можно использовать и для дизайна механизма, который помог бы улучшить существующие распределения между двумя категориями агентов. Например, можно рассмотреть рынок новых докторов в Соединенных Штатах Америки. До середины ХХ века все было устроено на этом рынке следующим образом: в 40-е годы больницы Соединенных Штатов испытывали большой недостаток в студентах-медиках, и в условиях жесткой конкуренции они были вынуждены делать предложения о работе сильно заранее. В результате этого студенты могли долго медлить с ответом (не было жестких дедлайнов), и когда больницы сталкивались с тем, что предложение отвергалось, делать новое предложение о работе было уже некому. С середины ХХ века, с 1950-х годов, ситуация изменилась. Был введен централизованный институт распределения новых докторов по больницам. Он называется National Resident Matching Program. Алгоритм, который использовался в этой программе, очень похож на алгоритм Гейла — Шепли. В этом убедился Эл Рот. В результате работы этого алгоритма получались стабильные мэтчинги. Однако обнаружилось несколько проблем. Этот алгоритм систематически ставил больницы в более выигрышное положение по сравнению с самими докторами. Это как раз было связано с тем, что первыми предложения делали больницы. Таким образом, получающийся мэтчинг, фактически, приводил к тому, что больницы получали наилучших достижимых для них докторов, а вот доктора, соответственно, были не всегда довольны получающимися распределениями. Кроме того, не учитывались пожелания семейных пар, которые выпускаются из медицинских университетов, поэтому в таких парах росло недовольство и получила широкое распространение практика заключения договоров с больницами напрямую, в обход этого алгоритма. Поэтому в 1995 году Совет директоров программы обратился к Элу Роту с предложением разработать улучшенный алгоритм, который бы позволил решить обнаруженные проблемы. Разработкой этого алгоритма занялись, соответственно, Рот и Перансон, и в 1997 году новый алгоритм, в котором первыми предложения уже делали студенты и который позволял бы учитывать интересы семейных пар, был принят программой и теперь до сих пор используется для распределения выпускников медицинских университетов. Таким образом, теория стабильных мэтчингов нашла применение на практике и позволила улучшить ситуацию для выпускающихся студентов медицинских университетов. Еще один пример. Он будет касаться распределения учеников по школам в тех же Соединенных Штатах. До 2003 года все было устроено следующим образом: ученики, которые хотели поступить в старшие школы Нью-Йорка, должны были сделать список из пяти самых желанных для них школ и отправить свой список предпочтений в эти школы. Школы принимали решение по каждому ученику, которые отправляли им заявку, и они могли принять заявку, отклонить заявку или поставить ученика в лист ожидания. Далее, каждый ученик получал письмо, в котором ему сообщалось о принятых решениях, и он должен был принять не более одного предложения. Затем этот процесс повторялся. Школы, в которых оставались свободные места, снова принимали решения о приеме и отправляли письма с предложениями нераспределенным ученикам и так далее. Те ученики, которые после третьей итерации этой процедуры не были приняты ни в одну из школ, распределялись уже в некоторого... распределялись уже в результате работы некоторого специального административного процесса. Однако этот алгоритм обнаружил в себе несколько проблем. Около 30 000 учеников каждый год оказывались в школе, которой вообще не было в списке их предпочтений, то есть как минимум 30 000 человек были недовольны результатами работы этого алгоритма. В результате среди учеников получило широкое распространение стратегическое манипулирование. Они хитрили, указывали в заявке не свои настоящие предпочтения, а какие-то другие с тем, чтобы улучшить результат работы этого алгоритма, но в результате этого страдали те ученики, которые заявляли свои настоящие предпочтения и играли честно. Поэтому было принято решение о том, что этот алгоритм необходимо улучшать. В 2003 году Эл Рот и его коллеги помогли изменить процедуру приема в старшие школы Нью-Йорка. В этой новой системе распределения использовалась модифицированная версия алгоритма Гейла — Шепли. В ней первыми предложения делали ученики. В такой ситуации им выгодно заявлять свои настоящие предпочтения, а значит, получалось избегать стратегического манипулирования. В результате в первый год работы новой системы лишь 3 000 учеников оказались в тех школах, которые не были указаны в списке из пяти предпочтений. Это позволило существенно сократить количество недовольных учеников старших школ.