Элвин Рот - Кому что достанется – и почему. Книга о рынках, которые работают без денег
Если такое случается довольно часто, то в последующие годы работодатель может не подать в координационный центр сведения о некоторых, а то и обо всех вакантных рабочих местах, зная, что, действуя вне системы, он получает возможность нанять более подходящих сотрудников. (Вы, конечно, помните, что именно так происходило в Нью-Йорке: директора городских школ скрывали информацию о свободных местах при старом подходе к распределению детей в учебные заведения.) В конечном счете, если алгоритм выдает неустойчивые результаты, непременно появятся как кандидаты, так и программы ординатуры, которые предпочтут выбрать в пару друг друга, а не принять предложение центра. И это заставляет недовольные блокирующие пары пытаться обыграть систему.
Глядя на ситуацию с такой точки зрения, мы видим, что от любого высококонкурентного рынка, где каждый волен активно и энергично преследовать собственные цели, следует ожидать именно устойчивого результата. Что может остановить блокирующую пару – компанию и работника, желающих «сочетаться» друг с другом? Если ничего, то следует ожидать, что рынок не даст устойчивого результата, поскольку блокирующая пара не согласится на предложенный вариант. Но, как мы узнали из предыдущих глав, существует множество факторов, которые не позволят такой паре соединиться, например: недостаточная плотность или перенасыщенность рынка, а также высокий риск.
Конечно, пока это лишь теория. Однако утверждение, что устойчивые координационные центры работают лучше неустойчивых, подтверждается весьма убедительными доказательствами. Так, например, я обнаружил, что в 1960-х годах, когда британские рынки распределения молодых врачей в интернатуры страдали от чрезмерно ранних назначений специалистов в больницы, каждый регион, подведомственный Национальной службе здравоохранения Великобритании, создал собственный централизованный координационный центр. Некоторые из них использовали алгоритмы, очень похожие на первоначально предложенные американским выпускникам медицинских вузов, а этот способ, как вы помните, был отвергнут как небезопасный для студентов. Так вот, выдававшие неустойчивые результаты британские координационные центры постигла неудача; после того как многие недовольные предложенными соответствиями кандидаты и больницы (блокирующие пары) научились обходить их, услугами центров никто не хотел пользоваться. А вот британские координационные центры[51], выдававшие устойчивые паросочетания, процветали и продолжали работать.
Следует сказать, в далеком 1952 году экономисты всего этого еще не знали, поэтому можно только восхищаться проницательностью Харди Хендрена и достижениями его комитета. Само понятие устойчивости распределения по парам было четко сформулировано только десять лет спустя, в 1962 году, в статье Дэвида Гейла и Ллойда Шепли под интригующим названием «Прием в колледжи и проблема устойчивости браков»[52]. Авторы статьи ничего не знали о программе The Match, но сформулировали алгоритм подбора устойчивых паросочетаний, который, как я обнаружил позже, был эквивалентен тому, который использовали врачи для координации рынка труда в 1952 году. Гейл и Шепли назвали свою версию алгоритмом отложенного согласия; со временем он стал самым важным «лекарством» для исцеления давших сбой рынков соответствия – хотя бы потому, что они признали, что данный алгоритм всегда выдает устойчивые соответствия, по крайней мере для рынков без многочисленных осложнений, например для семейных пар, ищущих два рабочих места в одном городе. (Впрочем, я забегаю вперед.)
Ллойд Шепли был одним из основателей теории игр. Он написал много трудов, заложивших фундамент для целой новой области исследований, но именно за упомянутую выше статью в 2012 году ученому присудили Нобелевскую премию в области экономики. Дэвид Гейл, если бы он был к этому моменту жив, несомненно, разделил бы эту премию с Ллойдом и со мной. Гейл и Шепли открыли алгоритм отложенного согласия не первыми, но они были последними, кто это сделал: больше мы не выпустим это открытие из рук.
Вот как работает этот алгоритм. Я буду описывать его так, как будто кандидаты и работодатели предпринимают определенные действия, но имейте в виду, что их единственное реальное действие заключается в предоставлении ими своих предпочтений (этап 0). Все происходящее после этого (этап 1 и далее) происходит в компьютере без каких-либо задержек на принятие решений и донесение их до других сторон.
• Этап 0. Кандидаты и работодатели в конфиденциальном порядке подают ранжированные списки своих предпочтений в координационный центр.
• Этап 1. Каждый работодатель предлагает работу наиболее предпочтительным для него кандидатам, заполняя все имеющиеся вакансии. Каждый соискатель рассматривает полученные им предложения, выбирает наилучшее, по его мнению (то, которое значится первым в его списке), и отвергает все остальные (в том числе те, которые изначально были расценены им как неприемлемые и, следовательно, даже не были включены в его рейтинг).
• Этап…
• Этап n. Каждый работодатель, предложение которого было отвергнуто на предыдущем этапе, предлагает эту же работу следующему по списку кандидату, если он еще свободен. Каждый кандидат рассматривает это предложение в совокупности с остальными и принимает наиболее предпочтительное, по его мнению (с самым высоким рейтингом), отвергая остальные, включая и то, которое раньше, возможно, было им предварительно принято, но теперь не является, с его точки зрения, наилучшим из всех полученных предложений. (Обратите внимание, что кандидаты не учитывают, на каком этапе действия алгоритма получено предложение; они только оценивают, предпочтительно ли оно для них по сравнению с другими полученными предложениями).
• Финал наступает, когда не остается ни одного отвергнутого предложения и ни один работодатель не намерен выдвигать дополнительные. К этому моменту все кандидаты и работодатели (наконец-то) разбиваются на пары; каждый соискатель принимает то предложение, которое он предварительно принял последним. Таким образом, принятие решения откладывается; оно принимается в самом конце, когда становится очевидно, что новых предложений не предвидится.
Гейл и Шепли доказали поразительную вещь: применительно к предпочтениям работодателей и кандидатов на вакантные должности окончательное паросочетание всегда устойчиво, каковы бы ни были предпочтения. Иными словами, в конце алгоритма каждый соискатель принимает предложение, которое он не отверг (и все кандидаты, не получившие ни одного предложения, не находят себе пары, как и все предложения, которые никем не были приняты), а все подобранные в результате соответствия устойчивы. Нет ни одной блокирующей пары; это означает, что не осталось ни одного претендента на должность и ни одного нанимателя, которые хотели бы образовать друг с другом пару, но этого не случилось.
Откуда нам это известно? (Приготовьтесь выслушать подкрепленные математикой аргументы – настолько простые, что они не требуют применения формул и уравнений. Все основано на логическом мышлении. Кстати, именно эта аргументация помогла нам получить Нобелевскую премию.)
Предположим, некий кандидат, назовем его доктором Ароусмитом (А), и некий работодатель, скажем программа ординатуры со специализацией в области педиатрии Массачусетской больницы общего профиля (М), не сочетаются друг с другом. Откуда нам известно, что они оба не желали бы образовать пару?
Важный момент здесь – слово «оба». Возможно, А, которого объединили в пару с программой ординатуры, скажем, Раунсфилдской клиники (Р), предпочел бы работать в М (в своем рейтинге он поставил М перед P). Но в данном случае однозначно получается, что М не предложила ему работу в рамках действия нашего алгоритма, потому что, сделай она это, А отверг бы предложение Р, а он этого, очевидно, не сделал, потому что в итоге составил пару именно с Р. Почему же М не предложила ему работу? Дело в том, что эта ординатура заполнила все имевшиеся у нее вакантные должности кандидатами, которым сделала предложение еще до того, как получила возможность предложить работу А. Иными словами, М заполнила все рабочие места специалистами, которых она считала лучше А. Следовательно, хотя А предпочел бы оказаться в паре с М, эта больница явно не намерена отвечать ему любезностью за любезность. (Вот такой простой аргумент, но он основан на чистой математике и позволяет нам понять не самые очевидные истины[53].)
В ходе этой простой аргументации мы с вами довольно точно воспроизвели потрясающие наблюдения Гейла и Шепли. Мы показали, что в случае с каждым врачом, который предпочел бы быть включенным в другую программу, а не в ту, с которой его связал алгоритм распределения, наиболее желанная для него программа не отвечает ему взаимностью. (Точно так мы могли бы доказать, что фаворит ординатуры, предпочитающей другого претендента тому, которого ей выбрали, явно не готов платить ей той же монетой.) Оба этих факта демонстрируют устойчивость данного распределения, поскольку в нем отсутствуют блокирующие пары.
