Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Кисельгоф, Софья Геннадьевна

• Кисельгоф, Софья Геннадьевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Кисельгоф, Софья Геннадьевна

Содержание

Введение

1 Обобщенные паросочетания: классические результаты

1.1 Обобщенные паросочетания один к одному, или задача о

свадьбах

1.1.1 Устойчивое паросочетание: существование и механизм построения

1.1.2 Структура множества устойчивых паросочетаний

1.1.3 Сообщение предпочтений и манипулирование при построении обобщённых паросочатений

1.2 Обобщенные паросочетания один ко многим

1.3 Предпочтения сторон: расширения классической модели

1.3.1 Существование и эффективность устойчивого паросочетания

1.3.2 Механизмы построения устойчивого паросочетания

1.4 Анализ централизованных механизмов распределения, используемых на практике

1.4.1 Механизм распределения в терапевтическую интернатуру США

1.4.2 Прием в школы и детские сады

1.4.3 Централизованные схемы зачисления абитуриентов в вузы

1.4.4 Пересадка почек: обмен донорами

1.4.5 Провалы централизованных механизмов

2 Обобщенные паросочетания при предпочтениях, построенных на основе порогового выбора

2.1 Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками

2.1.1 Существование устойчивого паросочетания

2.1.2 Механизм отложенного принятия и паросочетания, неэффективные для абитуриентов

2.1.3 Устойчивые улучшающие циклы и построение эффективного для абитуриентов устойчивого паросочетания

2.2 Обобщенные паросочетания при предпочтениях, являющихся интервальными порядками

2.3 Неманипулируемый механизм со обратным устранением безразличий

2.4 Комплекс программ

2.5 Заключение по Главе 2

3 Прикладные аспекты задачи распределения абитуриентов

по вузам

3.1 Граничные оценки и устойчивые паросочетания

3.1.1 Механизмы построения устойчивого набора граничных оценок

3.1.2 Два вида механизмов и эффективность паросочетания

3.1.3 Сравнение Н-устойчивости и Ь-устойчивости

3.1.4 Манипулирование предпочтениями

3.2 Моделирование приемной кампании в РФ

3.2.1 Организация приемной кампании в российских государственных вузах

3.2.2 Математическая модель

3.2.3 Поведение абитуриента в зависимости от уровня подготовки

3.2.4 Моделирование приемной кампании

3.3 Заключение по Главе 3

Заключение

Литература

А Доказательство утверждений о выборе абитуриентов

В Исходные коды разработанного программного комплекса

В.0.1 Устранение безразличий в предпочтениях агентов

В.0.2Генерация предпочтений случайным образом

В.О.ЗМодуль проверки эффективности паросочетания

Введение диссертации (часть автореферата) на тему «Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками»

Введение

Рассмотрим следующую задачу: в некотором двудольном графе С = (Ми\¥,Е) необходимо найти паросочетание (множество несмежных дуг). Классическая задача состоит в поиске паросочетания максимальной мощности [1]. Решение этой задачи имеет прикладное значение при формировании комитетов, распределении работников по должностям и др. При этом вершинам рассматриваемого двудольного графа в некоторых приложениях соответствуют игроки - люди или организации, обладающие свободой воли. Одна из интересных модификаций задачи поиска паросочетания, в корне меняющая подход к ее решению, - поиск паросочетания с учетом предпочтений игроков, «отвечающих» за отдельные вершины графа. Для анализа подобных ситуаций Д. Гей-лом и Л. Шепли в 1962 году [2] была предложена теория обобщенных паросочетаний. Ими было введено новое понятие - устойчивое паросочетание, т.е. паросочетание, от которого не захотят отказаться отдельные игроки. Было показано, что устойчивое паросочетание всегда сушествует, и предложен механизм его построения. В отличие от классической задачи поиска паросочетания, была предложена также модель «один-ко-многим», в которой вершины (игроки) одного из подмножеств могут составлять не одну, а несколько пар. Эта модель имеет большое прикладное значение в задачах распределения абиту-

риентов по вузам, выпускников вузов на работу и т.п. Впоследствии Д. Гейлом, Э. Ротом, М. Сотомайор и другими [3-9] были исследованы различные аспекты данной задачи, рассмотрены разные походы к моделированию предпочтений и определению устойчивости. В 2012 г. Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике «за теорию устойчивого распределения и практики устройства рынков» [10,11].

Актуальность темы Важное направление в развитии теории обобщенных паросочетаний: разработка моделей и механизмов, учитывающих специальные особенности предпочтений игроков. В классической теории обобщенных паросочетаний предпочтения агентов задаются линейными порядками [2,4,9,12], то есть предполагается, что каждый игрок может строго упорядочить игроков противоположной стороны по предпочтительности. В реальных приложениях предпочтения одной или обеих сторон часто основаны на неточных измерениях (таких, как экзаменационные оценки, тесты, результаты собеседований) и поэтому представляется актуальным исследование моделей, в которых предпочтения сторон не являются линейными порядками.

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

Целью данной работы является исследование модели обобщенных паросочетаний при предпочтениях, не являющихся линейными порядками.

Для достижения поставленной цели были решены следующие задачи:

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

2. Исследовано существование и возможность построения эффективного устойчивого паросочетания в модели «один ко многим», когда предпочтения заданы интервальными порядками.

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

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

5. Исследован механизм организации приемной кампании в России; показаны особенности и «узкие места» используемой псевдоцентрализованной схемы.

6. Разработан комплекс программ, реализующий предложенные механизмы.

Научная новизна:

1. Впервые исследована модель обобщенных паросочетаний с предпочтениями, заданными простейшими полупорядками.

2. Впервые исследована модель обобщенных паросочетаний с предпочтениями, заданными интервальными порядками.

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

4. Впервые показана взаимосвязь централизованных систем распределения, основанных на граничных оценках, и устойчивых обобщенных паросочетаний.

5. Впервые предложены верхняя и нижняя оценки возможных граничных оценок для классического механизма Гейла-Шепли со случайным устранением безразличий.

6. Выполнено оригинальное исследование российского псевдоцентрализованного механизма организации приемной кампании и показаны источники неэффективности получаемого распределения абитуриентов по вузам.

Методы исследования Теория принятия решшений, кооперативные игры с нетрансферабельной полезностью, оптимизационные модели, теория бинарных отношений, теория экономических механизмов.

Апробация работы. Основные результаты работы докладывались на следующих семинарах и конференциях:

1. The 24-th Stony Brook Game Festival of the Game Theory Society, Стони Брук, США, июль 2013 г. (доклад «Matchings with interval order preferences: stability and Pareto-efficiency»).

2. Семинар Matching in Practice, Université Libre de Bruxelles, Брюссель, Бельгия, май 2013 г.(доклад: «Efficiency vs strategy-proofness for matching with interval order preferences»).

3. Общемосковский семинар «Экспертные оценки и анализ данных», ИПУ РАН, Москва, март 2013 г. (доклад: «Обобщенные паросоче-тания: эффективность и неманипулируемость при предпочтениях, являющихся полупорядками»).

4. 11th Meeting of Society for Social Choice and Welfare, Дели, Индия, август 2012 г. (доклад: «College admissions with stable score-limits»).

5. 8th Spain-Italy-Netherlands Meeting on Game Theory (SING8), Будапешт, Венгрия, июль 2012 г. (доклад: «College admissions with stable score-limits»).

6. XIII Международная конференция по проблемам развития экономики и общества, Москва, апрель 2012 г. (доклад: «Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками: устойчивость и оптимальность по Парето»),

7. Семинар «Математическая экономика» ЦЭМИ РАН, декабрь 2011 г. (доклад: «Модели обобщенных паросочетаний: классические работы и новые результаты»),

8. Совместный российско-финский семинар «Современные исследования в области коллективного принятия решений и общественного выбора» (Joint PCRC-DeCAn Workshop), Университет Турку, Финляндия, ноябрь 2011 г. (доклад: «Matchings with preferences being simplest semiorders»).

9. Общемосковский семинар «Экспертные оценки и анализ данных», ИПУ РАН, Москва, октябрь 2011 г. (доклад «Модели обобщенных паросочетаний с предпочтениями, не являющимися линейными порядками»),

10. 7th Spain-Italy-Netherlands Meeting on Game Theory (SING7), Париж, Франция, июль 2011 г. (доклад: «Обобщенные паросочета-ния с предпочтениями, являющимися простейшими полупорядками: стабильность и эффективность по Парето»),

11. XII Международная конференция по проблемам развития экономики и общества, Москва, апрель 2011 г. (доклад: «Модель выбора вузов абитуриентами и приемной кампании в России»),

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

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

Автором проанализирована российская псевдо-централизованная процедура проведения приемной кампании в государственных вузах.

Автор принимал участие в:

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

• исследовании модели обобщенных паросочетаний, основанных на одинаковом рассмотрении абитуринтов с равными оценками (анализ L-концепции устойчивости, демонстрация возможности манипулирования, доказательство теоремы о преимуществе L-концепции над Н-концепцией с точки зрения абитуриентов).

Публикации. Основные результаты по теме диссертации изложены в 6 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК:

1. Кисельгоф С.Г. Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками: стабильность и оптимальность по Парето // Автоматика и телемеханика. 2014. №6. С. 103-114.

2. Кисельгоф С.Г. Моделирование приемной кампании: вузы различного качества и абитуриенты с квадратичной функцией полезности // Проблемы управления. 2012. № 5. С. 33-40.

а также:

3. Biro P., Kiselgof S. G. College admissions with stable score - limits / Working papers by Hungarian Academy of Sciences. Series MT-DP «Discussion Papers of Hungarian Academy of Sciences». 2013. No. 6

4. Кисельгоф С.Г. Модель выбора вузов абитуриентами приемной кампании в России // В кн.: XII Международная научная конференция по проблемам развития экономики и общества. В четырех книгах. Книга 2. / Отв. ред.: Е. Г. Ясин. . Кн. 2. М.:Издательский дом НИУ ВШЭ, 2012. С. 422-430.

5. Kiselgof S. Matchings with Simplest Semiorder Preference Relations, in: Game Theory and Management. Collected abstracts of papers presented on the Fifth International Conference Game Theory and Management / Ed. by L. A. Petrosyan,N. A. Zenkevich. St. Petersburg: Graduate School of Management, St. Petersburg University, 2011. P. 119-121.

6. Кисельгоф С.Г. Выбор вузов абитуриентами с квадратичной функцией полезности / Препринты. М.:Высшая школа экономики. Серия WP7 «Математические методы анализа решений в экономике, бизнесе и политике». 2011. № 01.

Объем и структура работы. Диссертация состоит из введения, трех глав, заключения и одного приложения. Полный объем диссертации составляет 185 страниц с 5 рисунками и 11 таблицами. Список литературы содержит 62 наименования.

Глава 1

Обобщенные паросочетания: классические результаты

Эта глава представляет собой обзор классических результатов теории обобщенных паросочетаний, на которых основано оригинальное исследование настоящей диссертации.

1.1 Обобщенные паросочетания один к одному, или задача о свадьбах

1.1.1 Устойчивое паросочетание: существование и механизм построения

Рассмотрим неориентированный двудольный граф С = (МиИ^Е1), где М и IV - конечные и непересекающиеся между собой подмножества вершин графа, а Е - множество ребер, соединяющих вершины графа. В двудольном графе ребро может связывать только вершины, принадлежащие разным подмножествам. У каждого ребра е € Е есть две концевые вершины т 6 М и ги Е \¥, таким образом, е = {т,ги}. Вершина инцидентна ребру е, если является одним из его концов.

Определение 1.1. Паросочетанием в двудольном графе называется подмножество ребер Р Е Е, такое что любая вершина х Е М и V/ инцидентна не более чем одному ребру.

Классической задачей математического моделирования является задача поиска паросочетания максимальной мощности в заданном графе. Традиционно в литературе [1,3] эта задача называется задачей о назначении на работы или задачей о свадьбах. Для удобства дальнейшего изложения будет называть подмножество вершин графа М множеством мужчин, а подмножество V/ - множеством женщин. Если ребро е = {т,ъи} входит в паросочетание Е, будем говорить, что мужчина т и женщина т поставлены в пару друг с другом.

Гейл и Шепли [2] предложили рассмотреть расширение классической модели. Пусть теперь необходимо не просто найти паросочетание максимальной мощности, но найти такое паросочетание, которое учитывает предпочтения вершин (или, точнее, соответствующих вершинам рациональных агентов). Предпочтения будут описываться бинарными отношениями.

Будем говорить, что на множестве X задано бинарное отношение Р, если Р С X х X. Если пара (ж, у) Е Р, будем также обозначать это как хРу.Если же (х, у) ф Р, обозначим это как хРсу.

Определение 1.2. Линейным порядком [13] называется бинарное отношение Р, заданное на некотором множестве X и обладающее свой-

о

ствами:

• связности, т.е. Ух,у Е X, если х ф у, то или хРу, или уРх\

• транзитивности, т.е. Ух, у, г Е X если хРу, уРг, то хРг\

• асимметричности, т.е. \/х, у если хРу, то уРсх.

Фактически задание на множестве отношения предпочтения, являющегося линейным порядком означает, что все элементы этого множества упорядочены от наиболее предпочтительного до наименее предпочтительного. В [2] предпочтения каждой вершины (мужчины) т Е М описываются бинарным отношением Рт, которое задано на множестве IV и га и является линейным порядком. Иначе говоря, мужчина упорядочивает по предпочтительности всех женщин и опцию «остаться в одиночестве». Аналогично, отношение предпочтения Рю каждой вершины и) Е V/ задано на множестве Мигу и является линейным порядком. Совокупность всех отношений предпочтения будем называть профилем предпочтений и обозначать Р. Будем говорить, что га(гу) допустим(а) для т (га), если тРи,ги (соответственно, тРтт). Ребра в графе С связывают вершины га и т, только если они являются допустимыми друг для друга.

Определение 1.3. Обобщенное паросочетание ¡л [2,13] - это взаимнооднозначное отображение ¡л : М и V/ —> М и V/ такое, что:

• \/и> € IV если ¡л(и>) — т, то ¡л{т) = гу, и, аналогично, \/га Е М если 1л(т) = гу, то [л(ъи) — га;

• \/га Е М 1л(гп) = гу или [л(т) = га, и, аналогично, Угу Е IV 1л(и)) = га или 1л(т) = го

Обобщенное паросочетание д соответствует паросочетанию ^ в графе С в следующем смысле: если (л(т) = гу, то ребро е = {га, гу} Е

'В дальнейшем для краткости будем опускать определение «обобщенное» при упоминании обобщенного паросочетания.

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

Определение 1.4. Обобщенное паросочетание ц устойчиво, если оно удовлетворяет требованиям:

1. индивидуальной рациональности: \/х Е MUW таких, что fi(x) ф х верно, что fi(x)Pxx, то есть для каждого игрока, который получил пару в паросочетании ц, полученный партнер ц(х) является допустимым;

2. попарной устойчивости: не существует т Е М и w Е W таких, что (одновременно) mPw/j,(w) и wPmfi(m), т.е. не существует такой пары, что каждый предпочитает другого по сравнению с полученным согласно ц партнером.

Дадим еще одно определение.

Определение 1.5. Пара m:w называется блокирующей паросочетание ¡1, если ее присутствие нарушает устойчивость паросочетания ц в соответствии с пунктом 2 определения устойчивого паросочетания.

В [2] доказано, что устойчивое паросочетание всегда существует. Более того, в [2] предложено конструктивное доказательство этого

утверждения в форме механизма, позволяющего построить устойчивое паросочетание для заданного профиля предпочтений мужчин и женщин.

Механизм, позволяющий найти устойчивое паросочетание, называется механизмом отложенного принятия (англ. Deferred Acceptance Mechanism). Существуют две симметричные версии механизма, отличающиеся тем, какое из подмножеств вершин (М или W) имеет преимущество. Рассмотрим версию, где преимущество имеет подмножество М (мужчины). Эту версию механизма будем называть механизмом отложенного принятия с предлагающими мужчинами. Механизм состоит из повторяющихся однотипных шагов, по итогам каждого из которых строится временное паросочетание ¡Лк- В течение работы механизма постепенно пополняется множество Maione - множество мужчин, которые не будут поставлены в пару в итоговом устойчивом паросочетании.

1.1 Каждому т G М поставим в пару наиболее предпочтительную (в соответствии с отношением предпочтения Рт) женщину w^ 6 W. Пусть pi(m) = w1г. Будем также говорить, что т «сделал предложение» wln.

1.2 Изменим и достроим ¡ii так, чтобы это отображение стало индивидуально рациональным паросочетанием.

Во-первых, чтобы избежать нарушения индивидуальной рациональности для женщин, если по итогам шага 1.1 w = ^i(m), но wPwm (т недопустим для w), изменим паросочетание и установим /¿i(m) = т.

Во-вторых, заметим, что ц\ не является взаимно-однозначным отображением, т.к. одна и та же ш может быть поставлена в пару нескольким т. Пусть М^ги) = {т : 1±\{т) = ии}. Для каждой и), такой что |М1(гу)| > 0 выберем наиболее предпочтительного мужчину т^ из подмножества М^т) в соответствии с ее отношением предпочтения Рю. Поставим ии в пару с ш^, т.е. Ц\{уи) — т^. В то же время, все остальные мужчины, выбравшие т, не могут быть поставлены с ней в пару, т.е. \/т' £ М^ъи) \ {тустановим /¿(го') = т!. Будем также говорить, что ги «отказалась от предложений» этих мужчин. Если Му(ио) = 0, то /-¿1(10) = ии (опция одиночества).

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

2.1 Будем строить новое временное паросочетание Ц2. Пусть сначала /¿2 = М1- Для каждого т Е М, такого что (1\{т) = т, найдем ■ш^, наиболее предпочтительную из множества IV \ {ги^} в соответствии с отношением предпочтения Рт. Если допустима для ш, установим /¿2(го) — ^г- Если недопустима для т, то /•¿2(го) — т и пусть т Е Ма10пе. Мужчин, добавленных во множество Ма10пе, в дальнейшем рассматривать не будем.

2.2 Вновь изменим и достроим /¿2 так, чтобы оно стало паросочетанием. Повторим действия шага 1.2, основанные на предпочтениях женщин. Получим индивидуально рациональное паросочетание

тп\. г^з, ии2, и) 1 ъиI. шз, т4, гп\, т2

т2: го3, ги2, т ги2: ть т2) т3, (ги2),га4

т3: ги2, (тз),м;1,гиз ги3: ть га3, т2> т4

га4: ги2, гиь ("14).

Таблица 1.1: Отношения предпочтения для Примера 1.1

п.1 Будем повторять шаги до тех пор, пока на некотором шаге п не окажется, что все т Е М, такие что (га) = т, принадлежат множеству Ма10пе. Иначе говоря, работа механизма останавливается, когда каждый мужчина т Е М либо поставлен в пару с некоторой женщиной, либо получил отказ от всех допустимых женщин.

Полученное временное обобщенное паросочетание цп становится окончательным. Заметим, что поскольку множества М и VI/ конечны, то механизм закончит свою работу за конечное число шагов. Полученное обобщенное паросочетание соответствует паросочетанию Р в графе С в следующем смысле: если /¿(т) = ии, то е = {т, ги} Е Р. Следующий простой пример иллюстрирует работу механизма.

Пример 1.1. Пусть заданы множества мужчин М = {777,1, т2> ^2. га4} и женщин IV — {^1, ъио, ги^}. Применим механизм отложенного принятия, где мужчины первыми делают предложения, и найдем устойчивое паросочетание. Предпочтения даны в Таблице 1.1 (для каждого х Е М и IV просто запишем элементы в порядке убывания предпочтительности).

Выполним шаги механизма отложенного принятия с предлагающими мужчинами

1.1 т\ и т2 делают предложение и>з, а 7773 и т4 - г^.

1.2 г^з получила два предложения. В соответствии со своим отношением предпочтения иоз временно ставится в пару стп! и откажется от предложения 7772. 11)2 отвергнет предложение 7774, т.к. этот мужчина не является для неё допустимым, и будет временно поставлена в пару стз и отвергнет предложение ттц.

По итогам первого шага построено временное паросочетание цъ где /¿1(7711) = и)з, ¿¿1(7713) = ги2,М1(т2) = ш2,/¿1(7714) = 7774,^1(^1) = у)1.

2.1 Мужчины т2 и 777,4 делают следующие предложения (т.к. их предложения не были приняты на шаге 1.2). т2 делает предложение 11)2, а 777,4 ■

2.2 ии2 сравнивает временного партнера 7773 и новое предложение от 7772; 7772 предпочтительнее, чем 7773. Таким образом, предложение 7773, временно принятое на первом шаге, на втором шаге оказалось отклонено, п) 1 принимает предложение 7774, поскольку, согласно её отношению предпочтения, т^Р^тх, и это единственное предложение.

По итогам второго шага построено временное паросочетание ти2, ГДе /¿2(^1) = 11)з, /¿2(пг2) = = ГПз, /¿2(«74) =

3.1 Единственный мужчина, который не поставлен в пару с женщиной в паросочетании /¿2 - это 7773. Однако, согласно его отношению предпочтения, и)\ и и>з не являются допустимыми, поэтому 7773 € Ма/опе.

Работа механизма окончена, временное паросочетание ¡12 становится окончательным паросочетанием ¡1 Нетрудно убедиться в том, что построенное паросочетание будет

777,1 ™>2 т>3 т4 •ш3 ии2 777,3 го1

Таблица 1.2: Результат работы механизма отложенного принятия с предлагающими мужчинами для Примера 1.1

устойчивым, т.е. является индивидуально рациональным и не содержит блокирующих пар. Индивидуальная рациональность выполнена

!

по построению.

Тогда попробуем найти блокирующую пару. В блокирующую пару должен входить один мужчина и одна женщина. Покажем, что ни одна женщина не может составить блокирующую пару с кем-либо из мужчин.

• и>1 может составить блокирующую пару с 777,3, т-к- ^з Ршх [¿{иц)-Однако 777,3 не составит блокирующую пару с поскольку тх, согласно отношению предпочтения Рпч является недопустимой.

• и>2 может составить блокирующую пару с ть т.к. гпх РШ2 /¿(к^)-Однако 777,1 не составит блокирующую пару с Ю2, поскольку в па-росочетании ¡х т\ состоит в паре с более предпочтительной для него женщиной гУз.

• Для и>з Ц(1Пз) является наиболее предпочтительным среди всех элементов множества М и {го}, поэтому не может образовать ни с кем блокирующую пару.

Таким образом, ни одна ии £ V/ не может составить блокирующую пару.

Паросочетание не содержит блокирующих пар и индивидуально рационально, следовательно, оно устойчиво.

Теперь убедимся в том, что это не случайное совпадение.

Теорема 1.1.1. [2] Паросочетание р, полученное в результате применения механизма отложенного принятия, всегда является устойчивым.

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

Предположим, что в р существует блокирующая пара: га* и ги*, которые в текущем паросочетании не поставлены в пару, т.е. р(т*) ф и)*), и им обоим предпочтительнее составить пару друг с другом, чем с предписанными в р партнерами. Возможны два варианта:

1. га* ни на одном шаге механизма не был поставлен в пару с ги*. Однако он обязательно был поставлен в пару с р(т*). Мужчину ставят в соответствие сначала с наиболее предпочтительной ■ш^, затем следующей по предпочтительности и так далее. Значит, р(т*) для га* предпочтительнее, чем ъи*.

2. га* был поставлен в пару с ии* на некотором шаге к, однако на последующем, к+1-ом шаге ей был поставлен в пару другой мужчина га' (а /и^+/(га*) = га*). Это означает, что т'Р^т*. На последующих шагах механизма и>* могла получать новые предложения, и

т\ : ш 1,-Ш2,и>з : т2,т3,7П1

га2 : ъи2, и>1 гу2 : тз, шь ш2

7713:^3,^1,^2 гу3 : 7771,7772,7773

Таблица 1.3: Отношения предпочтения для Примера 1.2.

в окончательном паросочетании д, возможно, ф т'. Однако

на каждом последующем шага механизма и)* выбирает из наиболее предпочтительного гп, поставленного ей в пару на предыдущих шагах, и новых предложений, т.е. если О < в < г. Поэтому в окончательном паросочетании /л(ги)Рш*77т/. Учитывая, что т'Рш*т*, а отношение предпочтения Рш* транзи-тивно, получаем, что ц{т*)Рш*т*.

Таким образом, ттт* и ги* не могут составлять блокирующую пару.

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

Пример 1.2. Пусть заданы множества М = {777.1,7712,7773} и = ^з}- Отношения предпочтения приведены в Таблице 1.3. Опция одиночества опущена во всех предпочтениях, поскольку в данном примере все считают опцию одиночества наименее предпочтительным вариантом.

Если будет выполнен механизм отложенного принятия с предлагающими мужчинами, то на первом же шаге, в результате первого выбора наиболее предпочтительных женщин будет получено окончательное обобщённое паросочетание /¿м. в котором 1) = т\,

2) = 'Ш2, Цм{™>з) — ги3. Если же будет выполнен механизм отложенного принятия с предлагающими женщинами, то, также за один шаг, будет получено обобщённое паросочетание/^, в котором /¿и^(гох) = и)з, /¿иК77^) = /¿иКтз) = 11)2. Поскольку стороны симметричны, в соответствии с теоремой 1.1.1 оба паросочетания будут устойчивыми. Таким образом, получено два различных устойчивых паросочетания.

Более того, нетрудно заметить, что в данном примере можно построить и третье устойчивое паросочетание, назовем его в котором ЦМШ{ГП1) = 1П2, = 11)3, = 11)1.

Рм /¿И ' РМIV

7711 7772 т3 777-х т2 7773 7771 7772 777з

Юг 11) 2 11) з 11) з 11) 1 УО 2 11)2 'Ш3 11)\

Таблица 1.4: Устойчивые паросочетания в Примере 1.2.

Итак, оказывается, что устойчивых паросочетаний может быть несколько. Из каких же соображений следует выбирать единственное? Можно попробовать усилить определение устойчивого паросочетания. Действительно, согласно классическому определению Гейла-Шепли, из предложенного распределения с выгодой для себя не может выйти один агент или пара агентов (мужчина и женщина). А что, если целая группа X С М и IV откажется от некоторого устойчивого паросочетания ¡1 и составит друг с другом новые пары так, что для каждого х Е X новый полученный партнер будет предпочтительнее, чем партнер согласно /¿? Оказывается, что любое паросочетание, устойчивое к отклонению индивидов или пар, устойчиво и к отклонению коалиции произвольного размера. Задачу об обобщенных паросочетаниях можно рассмотреть как кооперативную игру с нетрансферабельной полезно-

Список литературы диссертационного исследования кандидат наук Кисельгоф, Софья Геннадьевна, 2014 год

Литература

1. Ope О. Графы и их применение. — М.: Изд-во «Мир», 1965.

2. Gale D., Shapley L.S. College admissions and the stability of marriage // American Mathematical Monthly. — 1962. — Vol. 69. — P. 916.

3. Knuth D.E. Mariages stable et leurs relations avec d'autres problemes combinatoires. — Les Presses de l'Universie de Monteal, 1976.

4. Dubins L., Freedman D. Machiavelli and the Gale-Shapley Algorithm // Naval Research Logistics Quarterly. — 1981.— Vol. 88,— P. 485-494.

5. Roth A.E. The Economics of Matching: Stability and Incentives // Mathematics of Operations Research. - 1982. - Vol. 7. - P. 617-628.

6. Roth A.E. The college admissions problem is not equivalent to the marriage problem // Journal of Economic Theory.— 1985, —August. - Vol. 36. - P. 277-288.

7. Roth A.E. Conflict and Coincidence of Interest in Job Matching: Some New Results and Open Questions // Mathematics of Operations Research. - 1985. - Vol. 10. - P. 379-389.

8. Demange G., Gale D., Sotomayor M.O. A further note on the stable matching problem // Discrete Applied Mathematics.— 1987. — March. - Vol. 16. - P. 217-222.

9. Roth A.E., Sotomayor M.O. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. — Cambridge University Press, 1992.

10. Алескеров Ф.Т., Кисельгоф С.Г. Лауреаты Нобелевской премии - 2012: Ллойд Шепли и Элвин Рот // Экономический журнал Высшей школы экономики. — 2012. — № 4. — С. 433-443.

11. Теория и практика двусторонних рынков (Нобелевская премия по экономике 2012 года) / Е.Б. Железова, С.Б. Измалков, К.И. Со-нин, И.А. Хованская // Вопросы экономики,— 2013.— Т. 1.— С. 4-26.

12. Roth А.Е. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory // Journal of Political Economy. - 1984. - Vol. 92. - P. 991-1016.

13. Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения, — М.: Физматлит, 2012.

14. Aumann R.J. A Survey of Cooperative Games without Side Payments // Essays in Mathematical Economics in Honor of Oskar Morgenstern / Ed. by M. Shubik. — Princeton University Press, 1967. — P. 3-27.

15. Roth A.E. Common and Conflicting Interests in Two-Sided Matching Markets // European Economic Review. — 1985. — Vol. 27. — P. 7596.

16. Roth A.E. On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets // Econometrica. — 1986,- Vol. 54,- P. 425-427.

17. Скорняков Jl.А. Элементы теории структур. — М.: Издательство «Наука», 1970.

18. Биркгоф Г. Теория решеток, — М.: Издательство иностранной литературы, 1984.

19. Peranson Е., Roth A.E. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design // American Economic Review.— 1999,— Vol. 89,— P. 748780.

20. Roth A.E., Sotomayor M.O. College admission problem revisited // Econometrica. - 1989. - Vol. 57, no. 3. - P. 559-570.

21. Kelso A.S.Jr., Crawford V.P. Job Matching, Coalition Formation, and Gross Substitutes // Econometrica.- 1982,- Vol. 50,- P. 14831504.

22. Danilov V., Koshevoy G., Murota K. Discrete convexity and equilibria in economies with indivisible goods and money // Mathematical Social Sciences. - 2001.-May. - Vol. 41, no. 3,- P. 251-273.

23. Blair C. The lattice structure of the set of stable matchings with multiple partners // Mathematics of Operations Research. — 1988. — November. - Vol. 13. - P. 619-628.

24. On the Lattice Structure of the Set of Stable Matchings for a Many-to-one Model / R. Martinez, J. Masso, A. Neme, J. Oviedo // Optimization. - 2001. - Vol. 50. - P. 439-457.

25. Sonmez T. Manipulation via capacities in two-sided matching markets 11 Journal of Economic Theory. - 1999. - Vol. 77. - P. 197-204.

26. Ehlers L. Manipulation via capacities revisited // Games and Economic Behavior. - 2010. - Vol. 69. - P. 302-311.

27. Irving R.W. Stable marriage and indifference // Discrete Applied Mathematics. - 1994. - Vol. 48. - P. 261-272.

28. Manlove D. The structure of stable marriage with indifference // Discrete Applied Mathematics. - 2002. - October. - Vol. 122, no. 1-3,- P. 167-181.

29. Spieker B. The set of super-stable marriages forms a distributive lattice // Discrete Applied Mathematics. - 1995. - Vol. 58. - P. 7984.

30. Alkan A. A class of multipartner matching markets with a strong lattice structure // Economic Theory. - 2002,- Vol. 19,- P. 737746.

31. Hatfield W., Milgrom P. Matching with Contracts // American Economic Review. - 2005. - Vol. 95. - P. 913-935.

32. Hatfield J.W., Kojima F. Substitutes and Stability for Matching with Contracts // Journal of Economic Theory. — 2010,— Vol. 145. — P. 1704-1723.

33. Abdulkadiroglu A., Sonmez T. School Choice: A Mechanism Design Approach // The American Economic Review. — 2003. — June. — no. 93. - P. 729-747.

34. Erdil A., Ergin H. What's the matter with tie-breaking? Improving Efficiency in School Choice // American Economic Review. — 2008. — June. - Vol. 98, no. 3. - P. 669-689.

35. Abdulkadiroglu A., Pathak P.A., Roth A.E. Strategy-proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match // American Economic Review. — 2009. — Vol. 99,- P. 1954-1978.

36. Strategy-Proofness makes the Difference: Deferred-Acceptance with Responsive Priorities : Cahiers de recherche : 2012-12 / Universite de Montreal, Departement de sciences économiques ; Executor: L. Ehlers, B. Klaus : 2012,— URL: http://ideas.repec.org/ p/mtl/montde/2012-12.html.

37. Strategy-Proof Tie-Breaking : Cahiers de recherche : 2011-07 / Université de Montreal, Departement de sciences économiques ; Executor: L. Ehlers, A. Westkamp : 2011.— URL: http ://ideas. repec.org/p/mtl/montde/2011-07.html.

38. Roth A.E., Vande Vate J.H. Random Paths to Stability in Two-Sided Matching // Econometrica. - 1990. - Vol. 58. - P. 1475-1480.

39. The Boston Public School Match / A. Abdulkadiroglu, P.A. Pathak, A.E. Roth, T. Sonmez // American Economic Review Papers and Proceedings. - 2005. - Vol. 95. - P. 368-371.

40. Shapley L.S., Scarf H. On cores and indivisibility // Journal of Mathematical Economics. - 1974. - Vol. 1. - P. 23-37.

41. Kojima F. School choice: Impossibilities for affirmative action // Games and Economic Behavior. — 2012. — Vol. 75. — P. 685-693.

42. Kojima F. The "rural hospital theorem" revisited // International Journal of Economic Theory. - 2012. - March. - Vol. 8. - P. 67-76.

43. Hafalir I.E., Yenmez M.B., Yildirim M.A. Effective affrimative action in school choice // Theoretical Economics. — 2013.— Vol. 8.— P. 325-363.

44. Kennes J., Monte D., Tumennasan N. The Daycare Assignment Problem.- 2011.

45. Balinski M., Sonmez T. A Tale of Two Mechanisms: Student Placement // Journal of Economics Theory. - 1999. - Vol. 84. - P. 73-94.

46. Implementing quotas in university admissions: An experimental analysis / S. Braun, N. Dwenger, D. Kübler, A. Westkamp. — 2012.— Discussion Paper SP II 2012-201, Social Science Research Center Berlin(WZB).

47. Dwenger N., Kubler D., Weizsaker G. Flipping a Coin: Theory and Evidence.— 2013.— Working Paper. URL: http://www.wiwi.hu-berlin.de/professuren/vwl/ mt-anwendungen/team/flipping-a-coin.

48. Roth A.E., Sonmez T., Unver U.M. Kidney Exchange // Quarterly Journal of Economics. - 2004. - Vol. 119. - P. 457-488.

49. Roth A.E., Sonmez T., Unver U.M. Pairwise Kidney Exchange // Journal of Economic Theory. - 2005. - Vol. 125. - P. 151-188.

50. Roth A.E., Sonmez T., Unver U.M. A Kidney Exchange Clearinghouse in New England // American Economic Review Papers and Proceedings. - 2005. - Vol. 95. - P. 376-380.

51. Roth A.E., Sonmez T., Unver M.U. Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences // American Economic Review. - 2007. - Vol. 97, no. 3. - P. 828-851.

52. The Need for (long) Chains in Kidney Exchange / I. Ashlagi, D. Gamarnik, M.A. Rees, A.E. Roth. - 2012.

53. Niederle M., Roth A.E. The Gastroenterology Fellowship Match: How it failed, and why it could succeed once again // Gastroenterology. - 2004. - Vol. 127. - P. 658-666.

54. Niederle M., Roth A.E. Relationship Between Wages and Presence of a Match in Medical Fellowships // Journal of the American Medical Association. - 2003. - Vol. 290, no. 2. - P. 1153-1154.

55. Haruvy E., Roth A.E., Unver M.U. The Dynamics of Law Clerk Matching: An Experimental and Computational Investigation of Proposals for Reform of the Market // Journal of Economic Dynamics and Control. - 2006. - Vol. 30. - P. 457-486.

56. The New Market for Federal Judicial Law Clerks / C. Avery, C. Jolls, R.A. Posner, A.E. Roth // University of Chicago Law Review.— 2007. - Vol. 74. - P. 447-486.

57. Luce D. Semiorders and a Theory of Utility Discrimination // Econo-metrica. - 1956. - Vol. 24, no. 2. - P. 178-191.

58. Aleskerov F. Simple and Simplest Semiorders // Dokl. Mathematics. - 2002. - Vol. 387. No. 2. - P. 175-177.

59. Aleskerov F., Bouyssou D., Monjardet B. Utility Maximization, Choice and Preference. — Berlin : Springer Verlag, 2007.

60. Алескеров Ф.Т. Простые и простейшие полупорядки в задаче экс-тремизационного выбора с аддитивной погрешностью // Автоматика и телемеханика. — 2002. — Т. 2. — С. 137-145.

61. Fishburn Р.С. Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. - New York: Wiley, 1985.

62. A supply and demand framework for two-sided matching markets : Rep. / Harvard University Working Paper ; Executor: E.M. Azevedo, J. Leshno : 2012. — URL: http: //fmwww.bc.edu/ ec-j/SemF2011/azevedo.pdf.