Автоматика и телемеханика, № 6, 2014
Интеллектуальные системы управления
© 2014 г. С.Г. КИСЕЛЬГОФ (skiselgof@hse.ru) (Высшая школа экономики, Москва)
ОБОБЩЕННЫЕ ПАРОСОЧЕТАНИЯ ПРИ ПРЕДПОЧТЕНИЯХ, ЯВЛЯЮЩИХСЯ ПРОСТЕЙШИМИ ПОЛУПОРЯДКАМИ: СТАБИЛЬНОСТЬ И ОПТИМАЛЬНОСТЬ ПО ПАРЕТО1
Рассмотрено расширение классической модели обобщенных паросоче-таний Гейла - Шепли. Модель описывает двусторонний рынок: с одной стороны - вузы, каждый из которых имеет ограничение по числу зачисляемых студентов; с другой стороны - абитуриенты, каждый из которых может получить одно место в вузе. И абитуриенты, и вузы высказывают предпочтения относительно желаемого распределения. Предполагается, что каждый абитуриент выстраивает линейный порядок на множестве желаемых вузов, а каждый вуз имеет предпочтения, являющиеся простейшими полупорядками. Для данной модификации показано, что всегда существует устойчивое паросочетание. Кроме того, сформулированы необходимое и достаточное условия оптимальности по Парето устойчивого паросочетания.
1. Введение
В статье рассматривается задача поиска равновесия на двустороннем рынке в случае, когда заданы лишь ординальные предпочтения агентов и невозможно осуществление денежных трансфертов. К таким рынкам относятся рынок свадеб, приемная кампания по поступлению в университеты и др. Впервые рынки такого типа, с распределениями один к одному и один ко многим, где предпочтения агентов задавались линейными порядками, были рассмотрены Гейлом и Шепли в [1]. В настоящей статье рассматривается модификация классической модели Гейла и Шепли: предпочтения университетов на множестве абитуриентов заданы простейшими полупорядками. Показано существование устойчивого паросочетания и, более того, существование для любого устойчивого паросочетания линейного расширения профиля предпочтений университетов, не нарушающего устойчивости. Основной результат статьи — расширение теоремы Эрдила - Эрджина о Стабильных улучшающих циклах. Эта теорема предоставляет критерий проверки эффективности
1 Работа поддержана Международной лабораторией анализа и выбора решений Национального исследовательского университета Высшей школы экономики. Исследование осуществлено в рамках Программы фундаментальных исследований Национального исследовательского университета Высшей школы экономики в 2012-2013 гг.
устойчивого паросочетания. Полученные в статье результаты имеют и важное прикладное значение, поскольку позволяют организовать эффективную процедуру построения паросочетания (например, в рамках приемной кампании) в более широком, чем ранее, классе ситуаций. В разделе 2 приведена классическая модель Гейла - Шепли и обзор публикаций. В разделе 3 описана новая модель и основные результаты. Доказательство утверждений дано в Приложении.
2. Обзор классических исследований
Рассмотрим классическую задачу об обобщенных паросочетаниях, сформулированную Гейлом и Шепли. Пусть А - множество абитуриентов, В -множество вузов. Множества А и В конечны. Будем обозначать через а элементы множества абитуриентов, а через Ь - элементы множества вузов. Каждый абитуриент может быть зачислен не более чем в один университет, а каждый университет Ь € В имеет мест.
Абитуриенты и университеты высказывают свои предпочтения, которые устроены следующим образом.
• Профиль предпочтений абитуриентов Р = (Ра1,..., ) состоит из линейных порядков, т.е. ацикличных ($ х!,... ,хп : х!Рах2Ра ... РахпРах!), связных (V х,у (х = у) ^ (хРау V уРах)) и транзитивных (хРауРаг ^ ^ хРаг) бинарных отношений. Каждое отношение предпочтения задано на множестве В и {а}, состоящем из университетов и возможности остаться незачисленным2. Иначе говоря, каждый абитуриент составляет упорядоченный по предпочтительности получения места список университетов, причем университеты начиная с некоторой позиции в этом списке являются неприемлемыми для абитуриента (лучше не обучаться нигде, чем обучаться в таком вузе).
• Профиль предпочтений университетов ,..., >-Ь|В|) состоит из линейных порядков. Каждое такое отношение предпочтения задано на множестве А и {Ь}3, состоящем из всех абитуриентов и возможности оставить место незаполненным. С содержательной точки зрения это означает, что университет составляет упорядоченный по предпочтительности зачисления список абитуриентов; в этом же списке указывается граница, ниже которой зачисление абитуриентов для университета неприемлемо (хуже, чем оставить место пустым).
• Для любого университета существует также отношение предпочтения на множестве всех подмножеств абитуриентов. Это отношение не задается явно, однако известно, что оно согласовано с предпочтением на множестве отдельных абитуриентов, т.е. удовлетворяет требованию:
V Ь € В, V А' с А, V а!,а2 € А \ А': а! а2 верно, что А' и {а!} А и{а2}.
2 Элемент а в данном множестве соответствует ситуации, когда абитуриент не получает места ни в одном вузе.
3 Элемент Ь в данном множестве соответствует ситуации, когда место в вузе остается вакантным.
Теперь необходимо распределить абитуриентов для обучения в вузах. Получающееся распределение абитуриентов по вузам будем называть паросоче-танием.
Определение 1. Паросочетание [1] - это отображение ц : (А и В) ^ ^ 2(АиВ) такое, что
• ц(а) = {Ь} ^ а € ц(Ь) (абитуриент зачислен в вуз тогда и только тогда, когда вуз зачислил абитуриента);
• V а € А ц(а) = {Ь} (Ь € В) V ц(а) = {а}4 (абитуриент учится в вузе либо никуда не зачислен);
• V Ь € В ц(Ь)^А V ц(Ь) = {Ь}5 (вуз зачислил подмножество абитуриентов или не зачислил никого);
• V Ь € В \ц(Ь)\ ^ (число зачисленных абитуриентов не превышает числа мест в вузе).
Поскольку и университеты, и абитуриенты имеют предпочтения и являются независимыми агентами, возникает закономерный вопрос: существует ли такое распределение абитуриентов по вузам (паросочетание), которое не захотят нарушить отдельные вузы, абитуриенты или их группы. Гейл и Шепли предложили определение 2 устойчивого паросочетания.
Определение 2. Паросочетание ц будет устойчивым, если оно является:
• индивидуально 'рациональным для абитуриентов:
V а € А : ц(а) = {а} верно, что ц(а)Раа, т.е. ни один абитуриент не зачислен в неприемлемый для него вуз;
• индивидуально рациональным для университетов:
V Ь € В : ц(Ь) = {Ь} верно, что V а € ц(Ь) {а} Уь Ь, т.е. ни один университет не будет обучать неприемлемого для него студента;
• эффективным "по пустым местам":
$ (а € А, Ь € В), таких что ЬРац(а) Л а Уь Ь Л \ц(Ь)\ < дь, т.е. не существует такой блокирующей пары (абитуриента и университета), в которой абитуриент предпочел бы учиться в этом университете, данный университет считает абитуриента приемлемым для обучения и в университете есть свободное место;
• попарно устойчивым:
$ (а € А, Ь € В), таких что ЬРац(а) Л (За1 € ц(Ь) : а Уь а'), т.е. не существует такой блокирующей пары, в которой абитуриент предпочитает данный университет тому, куда он зачислен, а данный университет, в свою очередь, предпочитает абитуриента одному из уже зачисленных.
Гейл и Шепли показали, что множество устойчивых паросочетаний всегда непусто. Более того, они предложили конструктивное доказательство этого
4 Будем говорить, что абитуриент образует пару с самим собой ^(а) = {а}, если он не зачислен ни в один вуз.
5 Будем говорить, что университет образует пару с самим собой ^(Ь) = {Ь}, если он не принял ни одного абитуриента.
утверждения в форме механизма, позволяющего построить устойчивое паро-сочетание для заданного профиля предпочтений абитуриентов и вузов. Также было показано, что в классическом случае все паросочетания являются оптимальными по Парето (с точки зрения общих предпочтений абитуриентов и университетов). Если же рассматривать только мнение абитуриентов, то существует единственное наилучшее для всех абитуриентов устойчивое паросочетание.
Алгоритм, позволяющий найти устойчивое паросочетание, называется алгоритмом отложенного принятия и имеет две версии (в зависимости от того, какая сторона имеет преимущество при реализации алгоритма). Приведем здесь краткое описание механизма отложенного принятия с предлагающими абитуриентами. На первом шаге каждый абитуриент подает заявление в наиболее предпочтительный для него университет. Если число заявлений, полученных университетом, не превышает числа мест, то университет временно зачисляет всех подавших заявления. Если же число заявлений превышает число мест, то вуз временно зачисляет только дь лучших абитуриентов и отказывает остальным. На следующем шаге каждый абитуриент, получивший отказ, подает заявление в следующий по предпочтительности университет. Если на втором шаге общее число заявлений (временно принятых на первом шаге и вновь поступивших) превышает квоту, то вуз вновь оставляет только дь лучших и отказывает остальным. Таким образом, абитуриент, временно принятый в университет, может позднее потерять свое место. Этот шаг повторяется до тех пор, пока каждый абитуриент не будет зачислен в университет либо отвергнут всеми приемлемыми для него университетами. Последнее временное распределение и является искомым устойчивым паросочетанием.
Работа Гейла и Шепли породила целое направление в экономической литературе - теорию обобщенных паросочетаний. Далее рассмотрены работы, посвященные ослаблению предположений о структуре предпочтений агентов.
При практической реализации механизма отложенного принятия для распределения учеников по школам в городах США [2] возникла следующая проблема: школы не имеют права проводить вступительных испытаний и при формулировании предпочтений руководствуются лишь социальными характеристиками будущих учеников. Несколько учеников могут иметь одинаковые социальные характеристики (например, место проживания), тогда с точки зрения школы такие будущие ученики несравнимы. В этом случае предпочтения школы на множестве учеников представляют собой слабый порядок, т.е. ацикличное и транзитивное бинарное отношение. Абдулкадиро-глу и Сонмез [2] предложили такую процедуру: сначала все несравнимости в предпочтениях школ случайным образом устраняются (предпочтения школ из слабых порядков превращаются в линейные); затем
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.