Кому что достанется – и почему. Книга о рынках, которые работают без денег - Элвин Рот

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

А теперь сравним старую систему распределения с новой. Представим себе двух вымышленных братьев, Амоса и Зака. Амос подавал заявление о приеме в среднюю школу в 2003 году, в последний год работы прежней системы, в Зак – в 2004-м, сразу после введения новой. Амосу больше всего хотелось учиться в селективной{12} средней школе Таунсенд-Харрис в Квинсе, которая по старой системе рассматривала только тех кандидатов, которые поставили ее первым пунктом в своем рейтинге. На втором месте в списке мальчика стояла еще одна селективная школа, Бикон-скул на Манхэттене, расположенная недалеко от компании, где работает его мама. Эта школа также рассматривала кандидатуры только тех учеников, которые сочли ее наиболее предпочтительной. Третьим по очередности вариантом Амоса была школа Кардосо, которая находилась недалеко от его дома в Квинсе, а четвертым – Форест-Хиллз, тоже в Квинсе. Амос понимал, что, подав заявление и в Таунсенд-Харрис, и в Бикон, он автоматически лишается одного из этих шансов, поскольку школа, которую он запишет в списке второй, даже не станет рассматривать его кандидатуру. Поэтому он включил в перечень школу Таунсенд-Харрис первым пунктом, Кардосо вторым, а Форест-Хиллз третьим. В первую он чуть-чуть не прошел, и в итоге оказался в Кардосо, школе своего третьего выбора, которой присвоил в рейтинге второй номер. Оценки в предыдущих классах у Амоса были хорошие, поэтому ему хотя бы не пришлось волноваться и мучиться неопределенностью все лето, ожидая распределения департамента образования перед самым учебным годом.

Зак, подававший заявление на следующий год, уже при новой системе, знал, что школам не будет известно, как он расставил их в своем рейтинге, и, значит, они не смогут «наказать» его за то, что он не выбрал их в первую очередь. Поэтому мальчик перечислил школы в истинном порядке своих предпочтений, который был таким же, как и у старшего брата: Таунсенд-Харрис, Бикон, Кардосо и Форест-Хиллз. (Чтобы гарантировать, что он не останется после распределения без места, Зак на всякий случай включил в список еще несколько школ, но, поскольку он тоже учился хорошо, особых причин для беспокойства у него не было.) На этот раз популярная Таунсенд-Харрис снова получила больше заявлений, чем в ней было свободных мест, и Зак, как и его брат Амос, в эту школу не попал. Но на следующем этапе новый алгоритм автоматически распределил его в Бикон.

Эта школа тоже считалась очень популярной; при старой системе она получала около 1300 заявлений на 150 свободных мест, поэтому на первом этапе действия алгоритма отложенного согласия сразу же отвергала всех кроме 150 наилучших кандидатов. Но поскольку теперь принятие решения откладывалось, Бикон пока не зачисляла детей, подававших заявление на первом этапе. Таким образом, получив на втором этапе заявление Зака, школа сравнила его с теми полутора сотнями школьников, чьи заявления были приняты на этапе номер один, и со всеми теми, кто подавал заявления на этапе номер два, а затем составила общий рейтинг всех кандидатов и приняла полторы сотни лучших из этой новой группы.

Заку не отказали ни на втором, ни на последующих этапах. И когда действие алгоритма закончилось, мальчика зачислили в престижную Бикон. В отличие от своего брата, он получил возможность спокойно перечислить свои истинные предпочтения, указав эту школу второй. И это не помешало ему быть принятым в Бикон после того, как ему не хватило места в Таунсенд-Харрис.

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

То же самое относится ко всем вариантам выбора; учащийся, которого не зачислили в первые семь школ из его списка, имеет столько же шансов попасть в восьмую, как будто он поставил ее на первое место в своем рейтинге. А если школьники могут включать список любое количество школ, их наилучшей стратегией будет одновременно самая простая – перечислить школы в порядке своих истинных предпочтений. По этой причине мы с Эллиоттом Перансоном в свое время перевернули с ног на голову алгоритм Match – чтобы студенты-медики подавали заявления о приеме на работу в больницы, а программы ординатуры принимали либо не принимали их заявления, а не наоборот. Благодаря этому студентам гарантировалась полная безопасность при раскрытии координационному центру своих настоящих предпочтений. (Кстати, на самом деле программы ординатуры, как и школы, тоже могут без опасения объявлять о своих пожеланиях. Но это уже совсем другая история, которая, согласно математической логике, обусловлена тем, что при любом устойчивом соответствии большинство людей оказываются в одной и той же паре.)

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

Предположим, некий директор школы обнаруживает, что к окончанию распределения ему хотелось бы взять многих ребят, которые в его школе не оказались. Стоит ли ему надеяться на то, что их родители придут к нему просить записать их детей в школу? Нет. Если эти учащиеся подавали заявления, пока действовал алгоритм, то их заявления уже приняли, поскольку, как мы знаем, данная школа высоко оценивает их способности. Но поскольку они пошли в другое место, значит, к моменту завершения действия алгоритма эти ученики заявления в нашу школу не подавали. Следовательно, их уже зачислили в школу, которая нравится им больше, куда они подавали заявление раньше.

Таким образом, когда действие алгоритма заканчивается, не остается ни одного ученика и ни одной школы, не образующих паросочетания, которое они оба предпочли бы образовать. Например, Заку нравилась Кардосо, но не так, как Бикон, куда его зачислили, поэтому он, конечно же, не станет подавать заявление о приеме в Кардосо после того, как его приняли в Бикон.

Обратите внимание, что мы с вами проанализировали ту же логическую цепочку, использованную в предыдущей главе для наглядной демонстрации открытия Гейла и Шепли, суть которого состоит в том, что окончательные паросочетания, полученные в результате действия алгоритма отложенного согласия устойчивы.

Детали, детали

Раньше, объясняя, как мы с коллегами адаптировали алгоритм отложенного согласия для системы распределения детей в школы Нью-Йорка, я несколько все упростил[64]. Теперь стоит уделить больше внимания некоторым из этих моментов, потому что, как уже не раз говорилось, детали в дизайне рынка чрезвычайно важны.

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