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

Gareth Cook, School Assignment Flaws Detailed, Boston Globe, September 12, 2003. См. также: Atila Abdulkadiroğlu and Tayfun Sоnmez, School Choice: A Mechanism Design Approach, American Economic Review 93, no. 3 (June 2003): 729–747.

Yan Chen and Tayfun Sӧnmez, School Choice: An Experimental Study, Journal of Economic Theory 127 (2006): 202–231.

Объясню, почему. Представьте себе студента, поставившего первым номером своего списка программу ординатуры, которая не сочла его лучшим претендентом, но программа под номером два включила его в свой список первым. Эта вторая программа могла заполнить все свои вакансии на этапах 1–1 и 2–1 данного алгоритма, и у нее просто не осталось места для этого студента, то есть для соответствия 1–2. Следовательно, вполне возможно, что студента фактически накажут за то, что он поставил первой в своем рейтинге программу, с которой вероятность его паросочетания была крайне низка, даже несмотря на то что ординатура номер два в его списке предпочтений назвала лучшим кандидатом именно его.

Больше о британских больницах и клиниках см. A. E. Roth, A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the U.K., American Economic Review 81 (June 1991): 415–40.

David Gale and Lloyd Shapley, College Admissions and the Stability of Marriage, American Mathematical Monthly 69 (1962): 9–15.

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

Вы можете услышать эти фанфары, прозвучавшие в честь Ллойда Шепли, в конце двухминутного видео, в котором показано, как ученый получает Нобелевскую премию из рук короля Швеции: http://www.nobelprize.org/mediaplayer/index.php?id=1906. (А на этой записи можно послушать мое выступление: http://www.nobelprize.org/mediaplayer/index.php?id=1905.)

Программа Match работает быстро по двум причинам: во-первых, участники принимают решения о своих предпочтениях заранее, благодаря чему никому не приходится никого ждать; а во-вторых, алгоритм обрабатывает «цепочки отказа» автоматически. Поначалу для этого использовались машины для сортировки перфокарт, а теперь компьютеры. И то и другое чрезвычайно важно. Мы с Сяолинем Сингом исследовали рынок труда профессиональных психологов тогда, когда эти специалисты пытались реализовать нечто вроде алгоритма отложенного принятия по телефону. Данный рынок оказался слишком перенасыщенным для подбора устойчивых соответствий: все попытки пройти все этапы алгоритма отложенного принятия через длинные цепочки телефонных звонков требовали слишком много времени. См. A. E. Roth and X. Xing, Turnaround Time and Bottlenecks in Market Clearing: Decentralized Matching in the Market for Clinical Psychologists, Journal of Political Economy 105 (April 1997): 284–329. Сегодня психологи используют компьютеризованный координационный центр, подобный разработанному нами для программы Match.

Доказательство Гейла и Шепли (а именно: если в процессе подбора паросочетаний не участвуют семейные пары, то устойчивое соответствие непременно будет найдено) математики называют теоремой , а пример, показывающий, что при наличии семейных пар этот вывод неверен, называется контрпримером , потому что данный пример противоречит выводу, который, как мы ожидаем, должен следовать из теоремы. Это и другие ранние наблюдения о подборе паросочетаний на рынке труда молодых врачей описаны в работе A. E. Roth, The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory, Journal of Political Economy 92 (1984): 991–1016.1

Alvin E. Roth and Marilda A. Oliveira Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis (Cambridge: Cambridge University Press, 1990).