Нобелевскую премию по экономике вновь присудили американцам
Нобелевскую премию по экономике 2012 года получат выпускники
Установившуюся традицию награждения экономистов из США Нобелевский комитет, таким образом, решил не нарушать. В XXI веке американцы неизменно входили в число лауреатов, и обрывается эта последовательность лишь в 1999 году, когда Премию получил канадец
Элвин Рот (слева) и Ллойд Шепли (фотографии Pat Greenhouse, Konrad Jacobs / MFO).
В своих работах г-да Рот и Шепли рассматривали проблемы распределения ресурсов. Задачи такого рода, как известно, может решить система цен, сложившаяся в условиях совершенной конкуренции — на рынке, где действуют многочисленные и прекрасно осведомлённые покупатели и продавцы, ни один из которых не имеет контроля над ценой. Практика показывает, что эта идеализированная модель подходит для описания многих реальных рынков.
Очевидно также, что ситуация, близкая к совершенной конкуренции, на некоторых рынках не сложится никогда, а само появление ценовой системы может противоречить законодательству или этическим нормам. Проблемы распределения при этом никуда не уходят: «товарами» вроде мест в школах или человеческих органов для пересадки тоже нужно эффективно распоряжаться.
В шестидесятых годах Ллойд Шепли, которому недавно исполнилось 89 лет, занялся теоретическим анализом механизмов распределения, действующих в подобных случаях. Свою известнейшую
Согласно условию, все мужчины и женщины указывают свои предпочтения, приписывая каждому из своих возможных партнёров какое-то (уникальное) число в диапазоне от 1 до n. Задача же состоит в том, чтобы отыскать устойчивые соответствия — сформировать n пар и избежать таких сочетаний, после разрушения которых можно составить новые союзы, в большей степени удовлетворяющие запросам молодожёнов.
Гейл и Шепли доказали, что успех в таких условиях гарантирует один очень простой алгоритм. На первом его шаге мужчины должны сделать предложение женщинам, которые нравятся им больше всего. В результате у каждой женщины появляется (возможно, пустой) список мужчин, из которого она выбирает наилучшего кандидата, берёт его на заметку, а остальных — отвергает. Затем каждый из отвергнутых делает предложение женщине, находящейся на втором месте в его списке предпочтений, дамы вновь выбирают лучшее из имеющихся предложений (не забывая о кандидате, который, возможно, был найден ранее) и отклоняют все прочие. Аналогичную процедуру нужно повторять столько раз, сколько потребуется, и не более чем за n•(n – 1) + 1 шагов искомые пары будут найдены.
Вид итоговой таблицы соответствий, что важно, может зависеть от того, какая именно сторона проявляет инициативу. Если предложения, как в нашем примере, делают мужчины, то результат будет оптимальным для них: ни один мужчина не окажется в паре, по «качеству» уступающей сочетанию, которое сложилось бы, если бы предложения делали женщины. В обратном примере преимущество, естественно, получают женщины.
Можно заметить, что задача об устойчивом бракосочетании представима как частный случай проблемы приёма в какие-либо учебные заведения. В этом малореальном случае число поступающих равно количеству заведений, и в каждом из последних свободно ровно одно место.
О применении идей Гейла и Шепли на практике их более молодой коллега Элвин Рот, в прошлом декабре отметивший 60-летие, задумался в восьмидесятые, изучая механизм распределения выпускников медицинских факультетов в резидентуру (то есть на последипломную больничную подготовку, предусматривающую специализацию интерном и
Намереваясь исправить ситуацию, в начале пятидесятых в США запустили национальную программу
Алгоритмы, родственные оригинальному методу Гейла и Шепли, также помогают создавать эффективные схемы поиска органов для пересадки и набора учащихся в среднюю школу. Этим проектам г-н Рот посвятил полуторачасовую популярную лекцию, прочитанную им в 2007 году:
Подготовлено по материалам