http://www.ras.ru/digest/showdnews.aspx?id=d0f8e7ab-d7e3-4ab6-b85e-6123ab9e701e&print=1© 2024 Российская академия наук
Их объединяют закономерности, за исследования которых в контексте темы «Рыночные инструменты на практике» американцы Элвин Рот и Ллойд Шепли получили Нобелевскую премию по экономике 2012 года. Комментирует кандидат физико-математических наук Сергей Гелиевич Коковин (Институт математики им. С.Л. Соболева СО РАН).
- На самом деле эта премия стоит особняком: ее присуждает не тот Нобелевский комитет, который определяет лауреатов по химии, физике и другим направлениям, а Sveriges Riksbank – Шведский государственный банк. Один из ее обладателей, Ллойд Шепли, находится в преклонном возрасте, ему 89 лет. Элвин Рот – здравствующий, активный профессор Гарвардского и Стэнфордского университетов одновременно. Премию они получили за развитие кооперативной теории игр в области нахождения так называемого матчинга. Это одна из задач конструирования делового взаимодействия людей – переговоров, аукционов, и прежде всего найма, взаимоотношений «наниматель-работник».
Проблема проявилась еще в 1920-х годах в США при распределении выпускников-медиков в интернатуры разных госпиталей. Желающих пойти интернами было значительно меньше больниц, которые в них нуждались. Госпитали начали соревноваться за выпускников, всё раньше и раньше публикуя объявления и напрямую обращаясь к студентам – на последнем году обучения, а затем всё раньше и раньше. Потом договорились о том, чтобы это прекратить. Но к началу Второй мировой войны наладить распределение интернов по госпиталям так и не сумели. В 1952 году Муленом и Стаклнером был предложен алгоритм создания единой системы распределения выпускников. Каждый из них писал, в каком именно госпитале он хотел бы работать, заявки попадают в единый банк данных, затем их делят на пять категорий, происходит многоступенчатая процедура. Заслуга Ллойда Шепли, по моему мнению, заключается в том, что в 1962-м году он и его соавторы доказали, что на самом деле существует более эффективный алгоритм взаимодействия между желающими наняться и потенциальными работодателями.
Впрочем, учёные думали не столько о распределении выпускников, сколько о marriage problem, проблеме женитьбы. Предположим, в каком-то городе открывается брачный сезон: в старой Москве XVIII-XIX веков это было начало зимы, сезон балов. Съезжаются женихи и невесты; у каждого жениха есть ранжир предпочтений девушек: вот эту бы он хотел прежде всего, если она откажется – то вон ту, и так далее.
Если, положим, из первой пятёрки ему никто не достаётся, то он предпочтет остаться в одиночестве. И у каждого есть такой же список. Оказалось, что тот механизм, который исторически сложился и действовал, по крайней мере, в высшем свете, был эффективным инструментом формирования стабильных пар. После того, как все находят себе избранниц и избранников, никто из оставшихся в одиночестве не способен разбить сложившиеся союзы. Все не вступившие в брак не могут разрушить эти пары и не желают новых попыток друг с другом.
Это, в принципе, типичные взаимоотношения людей, в том числе нанимателей и нанимаемых. Алгоритм Гейла-Шепли выглядит таким образом: одна из сторон, например, женихи, делает предложения, другая предложения не делает, то есть между двумя категориями алгоритм не симметричен. Каждый жених делает обращается к одной из девушек, первой - к той, которая ему больше всех нравится. Каждая невеста говорит «Может быть » одному из N человек, сделавших ей предложение, а остальным отказывает. Следующий тур: отвергнутые женихи могут обратиться к девушкам, ранее сказавшим «нет» другим. Естественно, один обращается к одной. Ситуация повторяется, формируются следующие пары. В этом процессе доказано, что от одного тура к другому (скажем, от бала к балу) оценка оставшихся женихов у девушек будет повышаться. Вчера мне сделал предложение не очень симпатичный кавалер, завтра получше… А у женихов, естественным образом, рейтинг оставшихся невест тур за туром снижается. Сначала было обращение к самой-самой, затем к более-менее и так далее… В результате возникает оптимальное с социальной точки зрения распределение на стабильные пары при, как правило, некотором нераспределенном остатке.
В Соединенных Штатах и Канаде алгоритм Гейла-Шепли не был принят медицинском сообществом при подборе специалистов, зато во Франции стал использоваться для распределения по университетам экономистов, защитивших PhD. Постдоки передают в министерство списки своих предпочтений с ранжиром: на первом месте такой-то университет, на втором такой-то…И университеты, как невесты, проводят отбор в несколько туров: одним, у которых стоят на первом месте, дают согласие, другим отказывают. Так возникает устойчивое распределение: ни один специалист не хочет сменить свое место работы, и ни один университет не желает поменять пришедшего сотрудника на другого. Здесь возникают те же «стабильные пары», как и после балов.
Второй нобелевский лауреат, Элвин Рот, провел большую работу по практической адаптации таких алгоритмов во многих сферах найма и шире – взаимодействия людей и групп. В нашей стране похожий механизм наблюдается при поступлении в вузы. Я один из редких людей, которые не против, а за ЕГЭ, потому что у способных ребят из глубинки появляется алгоритм выбора, хотя схема взаимодействия «абитуриент – вуз» не вполне соответствует механизму Гейла-Шепли. Ещё один пример, весьма дискуссионный – рынок трансплантации органов, в США чаще всего это почки. Здесь тоже есть две стороны, донор и реципиент. Обычно, в первую очередь органы для пересадки предлагают родственники, но принять их не всегда позволяет группа крови, другие факторы совместимости. Тогда появляется следующий человек, предлагающий почку, свои условия и так далее. Есть общеамериканский банк данных, где все эти субъекты взаимодействуют – вот еще один пример матчинга.
Так или иначе, по важности для всех сфер деятельности, тема, начатая Шепли и развитая Ротом, заслуживает Нобелевской премии. Я уже слышал вопрос: «А почему в области экономики?». Так случилось, что всю теорию принятия индивидуальных и групповых решений (последнюю называют также теорией игр) развивают экономисты. Здесь есть и математика, но традиционно они бытуют на экономических кафедрах университетов. Да и в целом экономика – это наука о системах человеческих отношений.