sonin1-13

Теория и практика двусторонних рынков

рынки и не на все товары можно установить цены. Работы, отмеченные Нобелевским комитетом по экономике в 2012 г., посвящены исследо­ ванию взаимодействий и рынков, на которых деньги не используют- ся, не могут использоваться или не играют ключевой роли. Основное внимание направлено именно на связи между экономическими аген- тами. На так называемых двусторонних рынках (two-sided markets) агенты на одной стороне рынка (например, продавцы какого-то това- ра) взаимодействуют только с некоторым небольшим числом агентов на другой стороне, и важно то, кто с кем в итоге будет связан. Самое простое взаимодействие происходит в ситуации, когда агенты разби- ваются на пары.

Классические примеры двусторонних рынков, встречающиеся во многих областях экономической науки, выглядят так: женщины-­ мужчины, работники-фирмы, школьники-школы и студенты-универ­- ­сите­ты, производители-магазины, а также доноры-больные, нуждаю­ щиеся­ в пересадке органов. Обычно любое такое взаимодействие назы- вают рынком, хотя как таковой торговли нет и цены на «товар» может и не существовать. Когда необходимо подчеркнуть, сколько участни- ков взаимодействия с каждой стороны, про рынки говорят «один-на- один», «один-на-много» или «много-на-много». Женщины-мужчины и больные-доноры — примеры рынков один-на-один; работникфирма, студенты-университеты — примеры рынков один на много; поставщики-магазины — пример рынка много-на-много.

Естественный вопрос для таких рынков: «Кто оказывается в паре с кем?». Или, более формально, какие связи (matches) будут сфор- мированы на таких рынках. А главный вопрос, на решении которо- го сконцентрированы усилия экономистов — и теоретиков, и практи- ков, — выглядит так: существует ли устойчивое размещение аген- тов (matching) на таких рынках? Когда такое размещение (разбиение агентов на пары на рынках типа один-на-один) существует, естествен- но ожидать, что именно оно (или одно из них, если размещений не- сколько) сложится в реальной жизни.

В этой статье мы разберем часть основных результатов, получен- ных Ллойдом Шепли и Элвином Ротом, лауреатами Нобелевской пре- мии по экономике 2012 г., и проиллюстрируем их с помощью простых примеров (в значительной степени опирающихся на примеры из ци- тируемой литературы).

Модель Гейла—Шепли

В 1962 г. американские ученые Дэвид Гейл и Л. Шепли предло- жили математическую модель двусторонних рынков, сформулировали задачу об устойчивости и решили ее. В приложении к рынкам типа один-на-один эта задача получила название «stable marriage problem (SMP)», или задача марьяжа. В данной модели рассматриваются два типа участников: мужчины и женщины. Каждая женщина по-своему ранжирует мужчин, а каждый мужчина по-своему ранжирует женщин. Размещение агентов — это набор пар, состоящих из одного мужчины

Е. Железова, С. Измалков, К. Сонин, И. Хованская

и одной женщины, и индивидуальных агентов (холостяков). Основной вопрос об устойчивости сформулирован так: существует ли стабиль- ное размещение (stable matching), или стабильный набор связей, на таком рынке? Набор стабилен, если нет пары, которая не связана уза- ми брака между собой и хочет пожениться, или индивида, который связан, но хочет быть холостяком.

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

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

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

представим себе, что фирма А, рассмотрев документы работника S, ре- шила сделать ему предложение. Если работника S полностью устраива- ет предложение и фирма А очень ему нравится, он может просто согла- ситься, и на этом дело закончится. Но если у работника S есть другие предложения или он ожидает их появления? Тогда S захочет отложить ответ на предложение от А. Если А не согласится, то S придется риск- нуть: согласившись, он, вероятно, упустит лучшую возможность, а от- казавшись, он, быть может, не получит лучшее предложение в дальней- шем. Если фирма А будет ждать, то она рискует: S может не согласить- ся, и ей придется искать другого кандидата. Пока А ждет, она не может по-настоящему рассматривать других кандидатов. Получается, что на рынке будут происходить серьезные задержки с наймом для многих ра-

Теория и практика двусторонних рынков

ботников, потому что и работники, и фирмы будут тянуть время в на- дежде получить наилучший для них вариант.

Эта проблема координации на некоторых рынках породила дру- гую проблему. Чтобы получить лучших выпускников, фирмы могут делать предложения заблаговременно, надеясь опередить остальных. В Америке на рынке молодых юристов, а в начале ХХ в. — на рынке врачей-стажеров, дело дошло до того, что фирмы подписывали контрак- ты после первого (из четырех) лет обучения, когда еще ничего про вы- пускника не известно. Именно из-за проблемы координации некоторые­ университеты проводят ранний набор студентов, пытаясь заполучить­ лучших студентов до того, как на них посмотрят другие вузы.

Возможное решение этой проблемы — централизация координа- ционного (распределительного) процесса. В середине ХХ в. амери- канские госпитали договорились использовать централизованную си- стему распределения врачей-стажеров: все будущие врачи и госпита- ли сообщают свои пожелания, и, основываясь на сообщенных пред- почтениях, алгоритм предлагает возможные пары стажер—госпиталь. Эта система была признана очень эффективной и существует в моди- фицированном виде до сих пор. Удивительно, но в основе этой си- стемы лежит алгоритм Гейла—Шепли. Они, не зная об этой системе, теоретически­ доказали ее эффективность.

Размещение врачей по клиникам

Вначале ХХ в. больницы приглашали выпускников медицинских коллед- жей работать в качестве интернов для прохождения практики (cм.: Roth, 1984; Roth, Sotomayor, 1992). После нескольких неудачных попыток организовать рас- пределение­ интернов по больницам, в основном путем ограничения времени на принятие­ решения, было обнаружено, что проблемы с путаницей и неорганизован- ностью процесса так решить нельзя. Вместо этого было принято решение исполь- зовать специальный­ алгоритм для распределения стажеров по больницам. Работал он следующим образом.

1. Будущие интерны и больницы обменивались информацией друг о друге. 2. Каждый из участников эксперимента составлял собственный лист предпочте­

ний.

3. После выполнения первых двух этапов, на основании списка предпочтений каждого из участников эксперимента алгоритм автоматически распределял студен- тов по больницам.

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

Данная система распределения не была обязательной, но в эксперименте при- няли участие больше 95% студентов и больниц. Эта цифра оставалась неизменной до 1970 г. Чем дольше алгоритм использовался, тем больше росло недовольство им со стороны студентов. С одной стороны, алгоритм был составлен так, чтобы опти- мизировать распределение с точки зрения госпиталей. А с другой стороны, достаточ- но много участников (порядка 1000 из 20 000) хотели найти работу вместе с кем-то еще (например, мужем или женой). В базовом виде алгоритм не учитывал совмест- ные предпочтения. В 1995 г. Роту предложили модифицировать алгоритм, чтобы учесть семейные связи, и с 1997 г. используется новый модифицированный алго- ритм (см.: Roth, Peranson, 1999).

Теория и практика двусторонних рынков

P(m1) = w2 w1 w3; P(w1) = m2 m1 m3;

P(m2) = w1 w2 w3; P(w1) = m3 m1 m2;

P(m3) = w1 w2 w3; P(w1) = m1 m2 m3;

Распределение по парам можно также задать самими парами. Пусть μ1 = {(m1 w3), (m2 w2), (m3 w1)}. Легко заметить, что данное распределение по парам нестабильно. Действительно, оно блокируется парой (m1 w2). А распределение μ2 = {(m1 w2), (m2 w3), (m3 w1)} стабильное.

Согласно теореме Гейла—Шепли, множество стабильных распре-

делений по парам не пустое (Gale, Shapley, 1962). Для доказатель-

ства этой теоремы был предложен алгоритм, который и получил на- звание «алгоритм Гейла—Шепли». Он включает ряд итераций, или этапов, и работает следующим образом.

1.На первом этапе каждый холостой мужчина делает предложе- ние наиболее привлекательной для него женщине. Если одиночество для него предпочтительнее, то он выходит из игры. Каждая женщи- на рассматривает все сделанные ей предложения. Самому достойно- му кандидату, в соответствии со своими предпочтениями, она гово- рит «может быть», всем остальным «нет». Теперь она «помолвлена» с самым приглянувшимся из женихов, и этот жених считается «по- молвленным» с ней, а все остальные остаются «свободными». Если женщина предпочитает одиночество текущему лучшему кандидату, то она отвергает его. Женщинам, у которых нет предложений, ­остается ждать.

2.На следующем этапе каждый «свободный» (отвергнутый) муж- чина делает предложение следующей в его списке предпочтений жен- щине. Затем каждая женщина сравнивает «старое» и новые предло- жения, и отвергает все, кроме одного, самого привлекательного.

3.Так, этап за этапом, отвергнутые мужчины делают предложе- ния женщинам, двигаясь вниз по своим спискам.

4.Алгоритм прекращает работу, когда больше нет мужчин, же- лающих сделать предложения, то есть каждый «свободный» мужчина сделал предложение всем женщинам, которых он предпочитает оди- ночеству, и был отвергнут.

5.Все «помолвленные» пары сходятся, а все остальные, если та- кие имеются, остаются одиночками.

Доказательство стабильности полученного размещения почти три- виально. Действительно, по конструкции алгоритма не может существо- вать мужчина, который связан с женщиной, но предпочитает остать- ся холостяком, так как он не должен был делать предложение такой женщине, или женщина, которая связана с мужчиной, но предпочи- тает одиночество, так как она должна была отвергнуть такого мужчи- ну. Допустим, что существует пара, которая хочет порвать текущую связь и установить новую. Так как мужчина предпочитает женщину в новой паре своей паре, полученной в результате алгоритма, то это означает, что он по ходу процесса делал предложение этой женщи- не. Но его предложение было отвергнуто и это означает, что текущий партнер данной женщины лучше данного мужчины с ее точки зре- ния. Значит, блокирующих пар нет.

Е. Железова, С. Измалков, К. Сонин, И. Хованская

(Алгоритм Гейла—Шепли; см.: Roth, Sotomayor, 1992). Пусть предпочтения мужчин заданы следующим образом:

Этап 1. На этом этапе каждый мужчина делает предложение самой предпо- читаемой женщине, а женщины принимают предложение самого предпочитаемого мужчины. Слева показаны предложения, а справа, в таблице, кто какие предложе- ния получил и кого выбрал.

Этап 2. На этом этапе все отвергнутые мужчины, а именно Валерий и Борис, делают новые предложения следующим в их списках женщинам.

На этом алгоритм закончил свою работу. Получившиеся пары: Валерий—Катя, Антон—Лена, Борис—Маша, Денис—Нина и Геннадий—Оля.

Несложно заметить, что результат работы алгоритма не зави- сит от того, делают мужчины предложения одновременно или после- довательно, и если последовательно, то в каком порядке, а также от того, в каком порядке женщины отказываются от худших предложе-

Е. Железова, С. Измалков, К. Сонин, И. Хованская

Оптимальное стабильное распределение для мужчин μM: Павел—Зина, Роман— Жанна, Сергей—Ира. Оптимальное стабильное распределение для женщин μW: Павел—Ира, Роман—Жанна, Сергей—Зина.

Сравним полученные пары. Действительно, для мужчин распределение μM луч-

ше, чем μW. Получаем, что сторона, которая делает предложения, оказывается в большем выигрыше. Можно отметить еще несколько интересных фактов. Роман и Жанна связаны друг с другом и в μM, и в μW. Из оптимальности этих распределе- ний следует, что если одна и та же пара сформирована в этих двух распределениях­, то она будет сформирована во всех стабильных распределениях1.

Мы рассмотрели модель рынков один-на-один, но все результаты легко обобщить на рынки один-на-много, которые Гейл и Шепли так- же анализировали. Модель один-на-много обычно называют моделью распределения студентов по университетам (college admissions problem,

см.: Roth, 1985; Roth, Sotomayor, 1989; Roth, 2003).

Задача распределения студентов по университетам

Как и в предыдущей модели, существует два конечных непересека- ющихся множества колледжей (или университетов) и студентов. Пусть

A = {a1, a2, ..., an} — множество абитуриентов, а C = {C1, C2, ..., Cm} —

множество университетов. У каждого абитуриента свои предпочтения среди университетов — список P(ai) из элементов множества C   {ai}. А у университетов имеются предпочтения среди студентов — список P(Cj) из элементов множества A  {Cj}. Cu >ai Cw означает, что абиту- риент ai предпочитает университет Cw университету Cu. Каждый аби- туриент может быть зачислен только в один университет, но каждый университет может принять несколько студентов. Пусть qj > 0 обо- значает максимальное количество (квоту) студентов, которых может принять университет Cj.

В этой модели предпочтения университетов на группах студен- тов полностью определяются списком индивидуальных предпочтений. Для любого подмножества студентов S   A, состоящего из не более чем qj – 1 студентов, и для любых двух студентов a1, a2   S,

S   {a1} >cj S   {a2} {a1} >cj {a2},  S   {a1} >cj S   {Cj } {a1} >cj {Cj }.

При наличии места университет Cj всегда предпочтет взять сту- дента, которого он предпочитает в индивидуальном порядке, вне за- висимости от того, какие студенты поступили в Cj.

Как и для модели марьяжа, ключевое понятие — стабильность распределения. Распределение студентов по университетам стабиль- но, если не существует блокирующего индивидуального агента или пары, состоящей из университета и группы студентов.

1 Отметим также, что если работа алгоритма начинается с того, что предложения делают мужчины, а не женщины, то ни одному из мужчин не выгодно сообщать неправду о своих истинных предпочтениях, независимо от того, каковы предпочтения других участников алгоритма (Roth, 1982).

Теория и практика двусторонних рынков

Результаты Гейла и Шепли прямо обобщаются на модель поступ­ ления абитуриентов в университеты. Существует стабильное распре- деление студентов по университетам, которое может быть найдено конструктивно, в результате работы слегка подправленного алгорит- ма Гейла—Шепли. В версии алгоритма, в которой предложения дела- ют абитуриенты, единственное отличие заключается в том, что уни- верситеты могут временно принимать более одного предложения, но в пределах квоты. А в версии алгоритма, в которой предложения де- лают университеты, последние могут посылать несколько предложе- ний одновременно, но в пределах квоты. Рассмотрим работу алгорит- ма на конкретном примере.

Рассмотрим алгоритм Гейла—Шепли для распределения студентов по универ- ситетам, в котором предложения делают студенты.

Предпочтения студентов:

Предпочтения университетов (в скобках квота):

Этап 1. На этом этапе каждый абитуриент подает документы в свой самый предпочитаемый университет, а университеты оставляют предложения самых пред- почитаемых студентов. Слева показаны предложения, а справа, в таблице, выбор и отклоненные заявки.

На этом алгоритм закончил свою работу.

Полученное распределение: в Совместный бакалавриат ВШЭ/РЭШ поступа- ют Костя и Анна, в Йель — Наташа, в Беркли — Макар, в Гарвард — Татьяна.