Потрясающие факты и истории Опции

[Александр Вакуров]

Дворняжка по кличке Вера, которая родилась без двух передних лап путешествует по Америке со своей хозяйкой Джуди Стрингфелоу пытаясь зажечь в сердцах людей мысль что преодоление невзгод возможно и как пример ее собака, которая научилась ходить на задних лапах как человек

[Александр Вакуров]

18 октября 2012
Поступить в хорошую школу, удачно жениться, рационально распределить ресурсы

Нобелевская премия по экономике 2012 года досталась математикам Ллойду Шепли – за разработанную теорию, а Элвину Роту – за применение ее на практике.

Традиционный экономический анализ исследует механизмы изменения цен на товары или услуги в зависимости от потребностей участников. Теоретические расчеты в этой области работают достаточно неплохо и подтверждаются практикой. Однако в определенных ситуациях требуется найти ответ на задачу о распределении неких ресурсов, не связанных с товарно-денежными отношениями. Анализ подобных задач основан на так называемой теории кооперативных игр, изучающей задачи взаимовыгодного распределения ресурсов. Автором этой теории был американский ученый Ллойд Шепли. Расскажем о ней подробней.

Допустим, у нас есть группа рациональных – то есть знающих собственные интересы и поступающих согласно им – субъектов, которые неограниченно обмениваются некими ресурсами. В итоге получившееся распределение этих ресурсов должно быть взаимовыгодным. Если кто-то из участников недоволен результатом, он продолжает обмен, до тех пор, пока результат не станет выгодным для всех. Ситуация, в которой ни один участник при дальнейшем совершении обмена не получит дополнительной выгоды, называется стабильной. Понятие стабильности – это основа теории кооперативных игр.

В 1962 году Шепли совместно с Дэвидом Гейлом изучал случаи парного совпадения – то есть те ситуации, когда индивиды в группе разбивались по парам, руководствуясь только собственными интересами. В качестве наиболее распространенного примера такого распределения ученые решили смоделировать процесс образования семейных пар. Был разработан простой механизм, который помогал создавать стабильные совпадения, при которых ни одна пара не испытывала желания распасться и начать новые поиски партнеров. Набор простых правил, соблюдение которых всегда вело к созданию стабильных пар, получил название «алгоритм отложенного согласия», так же он известен как алгоритм Гейла-Шепли.

При использовании этого алгоритма одна сторона (например мужчины) делает выбор, а другая сторона (женщины) – соглашается с ним либо отклоняет. Каждый мужчина делает предложение той женщине, которая нравится ему больше всего. Затем женщины изучают полученные предложения (их может быть и несколько, и ни одного), выбирают наиболее понравившиеся (но, пока не принимая его), и отклоняют остальные. Мужчины, получившие отказ, выбирают второй по привлекательности вариант, а женщины опять выбирают наиболее понравившегося им мужчину. Этот процесс заканчивается тогда, когда мужчины прекратят дальнейший выбор. Когда этот момент наступит, женщины принимают все отложенные предложения, и на этом алгоритм заканчивается. Гейл и Шепли математически доказали, что их алгоритм всегда ведет к стабильным парам. Однако у этого алгоритма есть одна особенность – та сторона, которая выбирает пары, оказывается в итоге с большей выгодой, чем та, которая принимает предложения.

Простота и изящество алгоритма Гейла-Шепли привела к широкому его распространению в литературе для студентов-экономистов. Однако долгое время он оставался лишь теорией, не подкрепленной практикой. Использовать его для решения задач в реальной жизни удалось лишь в 1980-х годах, и тем, кто это сделал, был американский экономист Элвин Рот. Ему было поручено решить проблему, связанную с распределением выпускников медицинских учебных заведений. Для того, чтобы понять ее суть, придется немного углубиться в историю.

В 1940-х годах нехватка молодых врачей в США привела к тому, что больницы стали резервировать места в интернатуре для еще не закончивших обучение студентов. Получалось, что за студентом закреплялось рабочее место еще до того, как он определялся со специализацией и начинал осваивать профессию. Если в дальнейшем выпускник отказывался от этого рабочего места, то больница уже не имела возможности найти другого кандидата. Понятно, что такой механизм создания пар (а именно он имел место быть с точки зрения математики) не мог создавать стабильные совпадения из-за недостатка предложений. Ситуация усугублялась тем, что больницы стали определять крайние сроки, до наступления которых студент должен был согласиться или отказаться от рабочего места. Это заставляло студентов принимать поспешные решения, так как они не знали о том, что им могут предложить позднее.
Проблему отчасти помогла решить Национальная программа назначения врачей (National resident matching program), которая была основана в 50-х годах прошлого века. Механизм работы этой программы был очень похож на алгоритм Гейла-Шепли, и, в полном соответствии с теорией, этот алгоритм порождал стабильные совпадения.

Но через некоторое время и эта система начала давать сбои. Дело в том, что в работу «идеального» алгоритма стал вмешиваться человеческий фактор. Стало расти число медиков-женщин, и, как следствие, стало появляться все больше семейных пар, состоящих из врачей, которые, естественно, желали работать поблизости друг от друга. Как мы уже говорили, предлагающая сторона в алгоритме Гейла-Шепли оказывалась в большей выгоде. В нашем случае предлагающей стороной были больницы, поэтому программа назначения врачей стала подвергаться критике из-за того, что она играла на руку больницам, не учитывая интересы самих врачей. Молодые доктора стали отказываться от вроде бы выгодных для них предложений, а это значило, что система стала нестабильной. Создать новый алгоритм, который учитывал бы интересы обеих сторон, было поручено Элвину Роту. Он начал работать над этим алгоритмом в 1995 году совместно со своим коллегой Эллиотом Перансоном. Новая система назначения врачей учитывала интересы семейных пар и, благодаря ей, ежегодно возникало около 20000 стабильных совпадений.

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

В 2003 году Рот с коллегами усовершенствовал систему приема студентов в старшие школы (high school – приблизительный аналог наших старших классов). Метод, по которому студенты отбирались в нью-йоркские школы, был несовершенен. Абитуриенты должен были составлять список из пяти наиболее желанных школ. Эти списки рассылались затем по школам, которые решали, кого принять, кому отказать, а кого поместить в список ожидающих. Этот процесс повторялся еще два раза, и студенты, которых в итоге никуда не взяли, распределялись в принудительном порядке. Этот метод не обеспечивал поступающим достаточно возможностей высказывать свои пожелания, а школы, в свою очередь, не имели возможности делать достаточно предложений. В итоге ежегодно около 30000 студентов оказывались в тех школах, которых не было в их списках. Более того, этот алгоритм тоже имел шансы быть искаженным. Школы предпочитали брать тех студентов, которые указали их в начале списка, студенты же часто записывали на первом месте не самую желанную школу, а ту, в которую было больше шансов попасть. Те же, кто действительно указывал свои предпочтения, в итоге оказывались в невыгодной ситуации. Новый алгоритм, разработанный Ротом, оказался успешным, в результате его работы 90 процентов студентов были назначены именно в те школы, в которые они желали попасть.

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

Источник: www.nkj.ru



Подробнее см.: http://www.nkj.ru/news/21251/ (Наука и жизнь, Поступить в хорошую школу, удачно жениться, рационально распределить ресурсы)