Нобелевскую премию по экономике вновь присудили американцам

Нобелевскую премию по экономике 2012 года получат выпускники Принстонского и Гарвардского университетов Элвин Рот (Alvin Roth) и Ллойд Шепли (Lloyd Shapley).

Установившуюся традицию награждения экономистов из США Нобелевский комитет, таким образом, решил не нарушать. В XXI веке американцы неизменно входили в число лауреатов, и обрывается эта последовательность лишь в 1999 году, когда Премию получил канадец Роберт Манделл.


Элвин Рот (слева) и Ллойд Шепли (фотографии Pat Greenhouse, Konrad Jacobs / MFO).

В своих работах г-да Рот и Шепли рассматривали проблемы распределения ресурсов. Задачи такого рода, как известно, может решить система цен, сложившаяся в условиях совершенной конкуренции — на рынке, где действуют многочисленные и прекрасно осведомлённые покупатели и продавцы, ни один из которых не имеет контроля над ценой. Практика показывает, что эта идеализированная модель подходит для описания многих реальных рынков.

Очевидно также, что ситуация, близкая к совершенной конкуренции, на некоторых рынках не сложится никогда, а само появление ценовой системы может противоречить законодательству или этическим нормам. Проблемы распределения при этом никуда не уходят: «товарами» вроде мест в школах или человеческих органов для пересадки тоже нужно эффективно распоряжаться.

В шестидесятых годах Ллойд Шепли, которому недавно исполнилось 89 лет, занялся теоретическим анализом механизмов распределения, действующих в подобных случаях. Свою известнейшую статью, написанную в 1962-м в соавторстве с математиком Дэвидом Гейлом, учёный посвятил абстрактной задаче об устойчивом бракосочетании, в которой требуется установить соответствия между элементами двух множеств. Для наглядности принимается, что одно множество образуют n мужчин, а другое — n женщин, которые могут заключать моногамные браки.

Согласно условию, все мужчины и женщины указывают свои предпочтения, приписывая каждому из своих возможных партнёров какое-то (уникальное) число в диапазоне от 1 до n. Задача же состоит в том, чтобы отыскать устойчивые соответствия — сформировать n пар и избежать таких сочетаний, после разрушения которых можно составить новые союзы, в большей степени удовлетворяющие запросам молодожёнов.

Гейл и Шепли доказали, что успех в таких условиях гарантирует один очень простой алгоритм. На первом его шаге мужчины должны сделать предложение женщинам, которые нравятся им больше всего. В результате у каждой женщины появляется (возможно, пустой) список мужчин, из которого она выбирает наилучшего кандидата, берёт его на заметку, а остальных — отвергает. Затем каждый из отвергнутых делает предложение женщине, находящейся на втором месте в его списке предпочтений, дамы вновь выбирают лучшее из имеющихся предложений (не забывая о кандидате, который, возможно, был найден ранее) и отклоняют все прочие. Аналогичную процедуру нужно повторять столько раз, сколько потребуется, и не более чем за n•(n – 1) + 1 шагов искомые пары будут найдены.

Вид итоговой таблицы соответствий, что важно, может зависеть от того, какая именно сторона проявляет инициативу. Если предложения, как в нашем примере, делают мужчины, то результат будет оптимальным для них: ни один мужчина не окажется в паре, по «качеству» уступающей сочетанию, которое сложилось бы, если бы предложения делали женщины. В обратном примере преимущество, естественно, получают женщины.

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

Поиск устойчивых сочетаний для двух трёхэлементных множеств (студентов-медиков и клиник). Обычными белыми (чёрными) линиями со стрелками обозначены наилучшие варианты для студентов (клиник), а пунктирными — варианты, которые стоят на втором месте в списке предпочтений. Если предложения делают люди, то набор сочетаний оказывается таким: (1 + a, 2 + b, 3 + c). В противном случае второй и третий студенты меняются местами. (Иллюстрация Johan Jarnestad / The Royal Swedish Academy of Sciences.)

О применении идей Гейла и Шепли на практике их более молодой коллега Элвин Рот, в прошлом декабре отметивший 60-летие, задумался в восьмидесятые, изучая механизм распределения выпускников медицинских факультетов в резидентуру (то есть на последипломную больничную подготовку, предусматривающую специализацию интерном и резидентом). В первой половине ХХ века жёсткая «борьба» за молодых специалистов, которых явно не хватало, вынуждала клиники предлагать студентам варианты поступления в резидентуру задолго до выпуска. Чтобы сохранить возможности для манёвра, времени на размышление студентам давали не много, и те были вынуждены принимать неоптимальные решения.

Намереваясь исправить ситуацию, в начале пятидесятых в США запустили национальную программу NRMP, которая должна была регулировать отношения студентов медицинских школ и клиник. Программа оказалась вполне успешной, а анализ, проведённый г-ном Ротом, подтвердил, что в её основе лежит алгоритм, близкий к алгоритму Гейла — Шепли и нацеленный на поиск устойчивых сочетаний. Когда NRMP потребовалась модернизация, чиновники обратились к Элвину Роту, и он (вместе с Эллиотом Перансоном) сформулировал новый алгоритм, который предусматривал возможность поиска вариантов для молодых пар и подбирал соответствия, оптимальные уже не для клиник, а для студентов.

Алгоритмы, родственные оригинальному методу Гейла и Шепли, также помогают создавать эффективные схемы поиска органов для пересадки и набора учащихся в среднюю школу. Этим проектам г-н Рот посвятил полуторачасовую популярную лекцию, прочитанную им в 2007 году:

Подготовлено по материалам Нобелевского комитета.


Дмитрий Сафин, Компьюлента





Интересные новости
Вплине на вимірювання часу: танення льодовиків сповільнило обертання ЗемліВплине на вимірювання часу: танення льодовиків сповільнило обертання Землі
Вчені розповіли, чому «зірки-невдахи» часто самотніВчені розповіли, чому «зірки-невдахи» часто самотні
Блок рекламы


Похожие новости

Нобелівську премію з медицини присудили за дослідження еволюції людиниНобелівську премію з медицини присудили за дослідження еволюції людини
Нобелевскую премию по химии дали за разработку органокатализа
Нобелевскую премию по физике получили трое ученых за моделирование сложных систем
Нобелевскую премию по медицине присудили за открытие рецепторов осязания и температуры
Украинец получил Шнобелевскую премию по экономике за исследование связи коррупции с ожирением
Нобелевскую премию по химии вручили за новый метод изменения генома
Нобелевскую премию по физике присудили за изучение черных дыр
Нобелевскую премию по медицине получили трое вирусологов из США и Великобритании
Украинские ученые получили "Шнобелевскую премию"
Астрономы вновь пожаловались на Starlink
Последние новости

Подгружаем последние новости