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

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

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

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

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

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

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

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

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

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

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

Следующее упрощение в представленном выше описании состоит в том, что учащимся позволено включать в свой рейтинг любое число школ. Мы, экономисты, действительно рекомендовали такой подход, но, признаться, в адаптации этой важной детали не преуспели. И нью-йоркские школьники сегодня имеют право подавать список максимум из двенадцати программ обучения, хотя в городе действуют сотни. В результате ребята, которым хотелось бы включить в перечень больше школ, сталкиваются со стратегическим выбором: какие двенадцать школ включить в свой рейтинг? Зато эти двенадцать можно бесстрашно перечислить в порядке очередности, так как это совершенно безопасно – что уже очень неплохо.