џндекс.Њетрика

Меня зовут Николай Саперов, я независимый преподаватель экономики. Данный образовательный проект посвящен обучению школьников экономике и финансовой грамотности, подготовке абитуриентов к олимпиадам по экономике и финансам (Всероссийской олимпиаде по экономике, олимпиаде Высшая проба и другим олимпиадам).


Пособие приведено на сайте в сокращенном варианте. В данном варианте не приведены тестирования, даны лишь избранные задачи и качественные задания, урезаны на 30%-50% теоретические материалы. Полный вариант пособия я использую на занятиях с моими учениками. На контент, содержащийся в данном пособии, установлено правообладание. Попытки его копирования и использования без указания ссылок на автора будут преследоваться в соответствии с законодательством РФ и политикой поисковиков (см. положения об авторской политике Yandex и Google).

2.1 Премия 2012 года: алгоритм составления устойчивых пар

Самую «свежую» премию 2012 года получили экономисты Элвин Рот и Ллойд Шепли за исследования в области формирования пар (английское слово matching) из элементов нескольких множеств. Другими словами, как свести экономических агентов друг с другом так, чтобы они образовали максимально устойчивые пары. Эти исследования являются наглядным примером того, как экономика может быть использована для решения насущных проблем. Основу этим исследованиям положила статья «Поступление в колледж и прочность семейных уз», которую Шепли опубликовал в 1962 году. Половину своей взрослой жизни Шепли не преподавал, а работал в корпорации RAND, американском центре стратегических исследований, который еще называют «фабрикой мысли». Эта корпорация была основана в 1948 году для проведения стратегических исследований в области вооружений, и в ней работали видные экономисты и математики, в том числе специалисты по теории игр. Результаты работы корпорации были использованы при создании самой мощной в мире ядерной бомбы, которой сейчас обладает США, а также предшествовали появлению многих технологических изобретений, например, набирающим сейчас популярность 3D-принтерам. Но вернемся к Ллойду Шепли. В статье 1962 года ученый провел параллели между процессом поиска колледжа абитуриентом и процессом поиска спутника жизни. Пусть дано два множества элементов – холостые мужчины и женщины. Требуется разбить этих людей на стабильные пары. В кинофильмах пары образуются по большой любви, в реальности же при образовании пар стороны идут на многочисленные компромиссы, что часто приводит ко множеству проблем в дальнейшем. Ллойд Шепли придумал алгоритм (а Элвин Рот нашел множество его применений), по которому мужчины и женщины так формируют пары друг с другом, что ни у кого нет стимулов что-то менять в дальнейшем. Равновесие, сформированное таким образом, будет более устойчивым, чем сформированное любым другим образом.
Алгоритм работает так: все партнеры присваивают рейтинги противоположной стороне. Например, если какой-то мужчина предпочитает определенную женщину, то она получает у него самый высокий рейтинг. Вторая по предпочитаемости женщина получает рейтинг чуть ниже и так далее до наименее предпочитаемого варианта. Таким образом, каждый из участников этой «игры» имеет свою таблицу с рейтингами. После этого каждый мужчина делает предложение женщине – естественно, той, которая имеет наиболее высокий рейтинг у данного мужчины. Женщина собирает все поступившие ей предложения от мужчин, и принимает предложение от мужчины с ее наивысшим рейтингом, а все остальные отклоняет. Таким образом, образуется первая устойчивая пара. Данный процесс повторяется до тех пор, пока все женщины и мужчины не будут разбиты по парам.
Конечно же, в реальной жизни женихи и невесты не образуют пары именно таким образом. Зато, как показал Элвин Рот, подобный алгоритм может быть успешно применен в таких областях, как распределение студентов по колледжам, докторов по клиникам и донорских органов по больным. Важным условием для работы алгоритма становится то, что информация об имеющихся вариантах выбора доступна всем индивидам, делающим выбор. А сами индивиды могут проранжировать свои предпочтения от максимального к минимальному. Например, учащиеся государственных школ Нью-Йорка давно зачислялись в колледжи на основании предпочтений, но школьникам часто приходилось делать выбор, не зная о всех возможных вариантах. В конечном итоге многие школьники оказывались в колледжах, которые они не упоминали в своих предпочтениях. Многие школьники были недовольны сложившейся ситуацией. Или возьмем другую область: распределение студентов медицинских университетов по клиникам. В середине XX века в США наблюдался дефицит на рынке труда профессиональных врачей, и многие клиники конкурировали за то, чтобы нанять выпускников медицинских университетов. Дефицит ощущался так остро, что студентам предлагалась работа задолго до того, как они закончат учебу и приобретут профессиональные навыки. Получалось, что клиники были вынуждены задорого нанимать на работу еще не окрепших студентов, многие из которых так и не превращались в настоящих профессионалов. Клиники были недовольны ситуацией, которая сложилась в условиях дефицита. Алгоритм Шепли-Рота помог решать проблемы и в колледжах, и в клиниках. Например, студенты медицинских университетов составляли свои предпочтения клиник, а клиники выбирали наиболее понравившихся им студентов, также как женщина в алгоритме выбирали наиболее понравившегося им мужчину из тех, кто пришел с предложением.
Но более всего алгоритм пригодился для решения проблем, существующих на рынке донорских органов. В медицинской практике часто возникают случаи, когда человеку нужно срочно заменить какой-либо орган, например почку. В этом случае необходим донор, который бы согласился пожертвовать свою почку (у человека от природы есть две почки, хотя для успешного функционирования организма вполне достаточно одной). И тут возникает много проблем в связи с тем, чтобы найти подходящего донора. Донор и реципиент должны подходить друг другу по многим параметрам. Многие реципиенты ищут возможности донорства у друзей или родственников. Но даже если они нашли донора, то трансплантация становится не всегда возможной из-за потенциальной несовместимости. В этом случае есть выход: найти другую пару «донор-реципиент» и предложить ей произвести обмен почками. Например, есть муж и жена Ивановы, жене требуется произвести операцию по замене почки. Ее муж согласен пожертвовать своей почкой, но их организмы несовместимы. Есть муж и жена Петровы с аналогичной проблемой, при этом почка мужа Петрова может подойти жене Ивановой, а почка мужа Иванова может подойти жене Петровой. В таком случае между ними можно произвести взаимный обмен. На практике же, в отсутствие дополнительных институтов, такой обмен очень трудно произвести, поскольку он должен быть одновременным. Если он не будет одновременным, то после совершения одной операции другая сторона может передумать отдавать почку, а сделать это против воли человека невозможно. Например, когда муж Петров первым отдал свою почку, и она успешно трансплантирована жене Ивановой, то муж Иванов может передумать отдавать свою почку. В США с середины XX века было произведено множество подобных одновременных операций. Но что делать, когда обменные отношения становятся возможными при наличии трех или более участников? Произвести одновременные операции очень затруднительно. И тут на помощь приходит опять же алгоритм Шепли, дополненный так называемым механизмом «отсроченного ожидания». Донор дает почку неизвестному ему реципиенту, получив гарантию, что близкий ему человек получит почку от донора спустя какое-либо время. Как вы понимаете, в механизме с таким дизайном главным элементом становится обеспечение данной гарантии.

Применение:

Элвин Рот применил алгоритм Шепли ко многим реальных рынках, и в отдельных случаях усовершенстоввал его. Рот проявил себя не только как исследователь, но и активно участвовал в реофрмировании системы подбора специалистов в клиники в США, реформированнии системы зачисления школьников в колледжи Нью-Йорка и в создании структурного рынка донорских почек в США.

ИНФОРМАЦИЯ О СВОБОДНЫХ МЕСТАХ

В настоящий момент активно набираю учеников на предстоящий учебный сезон. Есть около 10 мест

ТЕОРИЯ И ЗАДАНИЯ

Все задачи

ИНТЕРВЬЮ С УЧЕНИКАМИ

  • Интервью с Дмитрием Сорокиным, абсолютным победителем Всероссийской олимпиады по экономике 2009 года

    Первое интервью я взял, пожалуй, у своего самого неординарного ученика - Дмитрия Сорокина. Дмитрий являлся абсолютным победителем (1-е место) Всероссийской олимпиады школьников по экономике 2009 года. Я помню, что мне было приятно заниматься с Дмитрием, который с первого же занятия поставил максимальную планку уровня наших занятий, заявив, что его цель - победа во Всероссийской олимпиаде. С первых занятий мне показалось, что Дмитрий - будущий ученый-экономист. Траектория Дмитрия интересна: после года обучения на экономическом факультете ВШЭ, он перевелся на первый курс совместного бакалавриата ВШЭ-РЭШ, а сейчас уезжает на семестр в Нью-Йоркский университет. В данном интервью Дмитрий рассказывает об этом выборе, а также о том, почему он решил стать академическим ученым, какие задачи сейчас стоят перед молодым экономистом. подробнее…

Все интервью