«ГЕННАДЬЕВНА ОБОБЩЕННЫЕ ПАРОСОЧЕТАНИЯ ПРИ ПРЕДПОЧТЕНИЯХ, НЕ ЯВЛЯЮЩИХСЯ ЛИНЕЙНЫМИ ПОРЯДКАМИ ...»

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

ВЫСШАЯ ШКОЛА ЭКОНОМИКИ

На правах рукописи

УДК xxx.xxx

КИСЕЛЬГОФ СОФЬЯ ГЕННАДЬЕВНА

ОБОБЩЕННЫЕ ПАРОСОЧЕТАНИЯ ПРИ ПРЕДПОЧТЕНИЯХ,

НЕ ЯВЛЯЮЩИХСЯ ЛИНЕЙНЫМИ ПОРЯДКАМИ

Специальность 05.13.18 — «Математическое моделирование, численные методы и комплексы программ»

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель:

доктор технических наук, с.н.с.

Алескеров Ф.Т.

Москва – Содержание Введение.............................. 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 Неманипулируемый механизм со обратным устранением 3 Прикладные аспекты задачи распределения абитуриентов 3.1 Граничные оценки и устойчивые паросочетания...... 3.1.1 Механизмы построения устойчивого набора граничных оценок........................ 3.1.2 Два вида механизмов и эффективность паросочетания 3.1.3 Сравнение H-устойчивости и L-устойчивости..... 3.1.4 Манипулирование предпочтениями.......... 3.2 Моделирование приемной кампании в РФ......... 3.2.1 Организация приемной кампании в российских государственных вузах.................... 3.2.3 Поведение абитуриента в зависимости от уровня подготовки.......................... 3.2.4 Моделирование приемной кампании.......... A Доказательство утверждений о выборе абитуриентов... B Исходные коды разработанного программного комплекса. B.0.1Устранение безразличий в предпочтениях агентов.. B.0.2Генерация предпочтений случайным образом..... B.0.3Модуль проверки эффективности паросочетания... Введение Рассмотрим следующую задачу: в некотором двудольном графе = (, ) необходимо найти паросочетание (множество несмежных дуг). Классическая задача состоит в поиске паросочетания максимальной мощности [1]. Решение этой задачи имеет прикладное значение при формировании комитетов, распределении работников по должностям и др. При этом вершинам рассматриваемого двудольного графа в некоторых приложениях соответствуют игроки – люди или организации, обладающие свободой воли. Одна из интересных модификаций задачи поиска паросочетания, в корне меняющая подход к ее решению, – поиск паросочетания с учетом предпочтений игроков, «отвечающих»

за отдельные вершины графа. Для анализа подобных ситуаций Д. Гейлом и Л. Шепли в 1962 году [2] была предложена теория обобщенных паросочетаний. Ими было введено новое понятие – устойчивое паросочетание, т.е. паросочетание, от которого не захотят отказаться отдельные игроки. Было показано, что устойчивое паросочетание всегда сушествует, и предложен механизм его построения. В отличие от классической задачи поиска паросочетания, была предложена также модель «один-ко-многим», в которой вершины (игроки) одного из подмножеств могут составлять не одну, а несколько пар. Эта модель имеет большое прикладное значение в задачах распределения абитуриентов по вузам, выпускников вузов на работу и т.п. Впоследствии Д. Гейлом, Э. Ротом, М. Сотомайор и другими [3–9] были исследованы различные аспекты данной задачи, рассмотрены разные походы к моделированию предпочтений и определению устойчивости. В г. Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике «за теорию устойчивого распределения и практики устройства рынков» [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, Брюсe сель, Бельгия, май 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 scorelimits»).

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

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

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

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концепции над H-концепцией с точки зрения абитуриентов).

Публикации. Основные результаты по теме диссертации изложены в 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.

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. Паросочетанием в двудольном графе называется подмножество ребер, такое что любая вершина инцидентна не более чем одному ребру.

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

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

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

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

транзитивности, т.е.,, если,, то ;

асимметричности, т.е., если, то.

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

Определение 1.3. Обобщенное паросочетание [2,13] – это взаимнооднозначное отображение : такое, что:

Обобщенное паросочетание соответствует паросочетанию в графе в следующем смысле: если () =, то ребро = {, }. 1В дальнейшем для краткости будем опускать определение «обобщенное» при упоминании обобщенного паросочетания.

Как же при построении паросочетания учесть предпочтения сторон?

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

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

1. индивидуальной рациональности: таких, что () = верно, что (), то есть для каждого игрока, который получил пару в паросочетании , полученный партнер () является допустимым;

2. попарной устойчивости: не существует и таких, что (одновременно) () и (), т.е. не существует такой пары, что каждый предпочитает другого по сравнению с полученным согласно партнером.

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

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

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

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

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

1.1 Каждому поставим в пару наиболее предпочтительную (в соответствии с отношением предпочтения ) женщину. Пусть 1 () =. Будем также говорить, что «сделал предложение».

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

Во-первых, чтобы избежать нарушения индивидуальной рациональности для женщин, если по итогам шага 1.1 = 1 (), но ( недопустим для ), изменим паросочетание и установим Во-вторых, заметим, что 1 не является взаимно-однозначным отображением, т.к. одна и та же может быть поставлена в пару нескольким. Пусть 1 () = { : 1 () = }. Для каждой, такой что |1 ()| > 0 выберем наиболее предпочтительного мужчину 1 из подмножества 1 () в соответствии с ее отношением предпочтения. Поставим в пару с 1, т.е. 1 () = 1. В то же время, все остальные мужчины, выбравшие, не могут быть поставлены с ней в пару, т.е. 1 () {1 } установим ( ) =. Будем также говорить, что «отказалась от предложений» этих мужчин. Если 1 () =, то 1 () = (опция одиночества).

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

2.1 Будем строить новое временное паросочетание 2. Пусть сначала 2 = 1. Для каждого, такого что 1 () =, найдем, наиболее предпочтительную из множества { } в соответствии с отношением предпочтения. Если допустима для, установим 2 () =. Если недопустима для, то 2 () = и пусть. Мужчин, добавленных во множество, в дальнейшем рассматривать не будем.

2.2 Вновь изменим и достроим 2 так, чтобы оно стало паросочетанием. Повторим действия шага 1.2, основанные на предпочтениях женщин. Получим индивидуально рациональное паросочетание Таблица 1.1: Отношения предпочтения для Примера 1. n.1 Будем повторять шаги до тех пор, пока на некотором шаге не окажется, что все, такие что 1 () =, принадлежат множеству. Иначе говоря, работа механизма останавливается, когда каждый мужчина либо поставлен в пару с некоторой женщиной, либо получил отказ от всех допустимых женщин.

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

Следующий простой пример иллюстрирует работу механизма.

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

Выполним шаги механизма отложенного принятия с предлагающими мужчинами 1.1 1 и 2 делают предложение 3, а 3 и 4 - 2.

1.2 3 получила два предложения. В соответствии со своим отношением предпочтения 3 временно ставится в пару с 1 и откажется от предложения 2. 2 отвергнет предложение 4, т.к. этот мужчина не является для неё допустимым, и будет временно поставлена в пару с 3 и отвергнет предложение 4.

По итогам первого шага построено временное паросочетание 2.1 Мужчины 2 и 4 делают следующие предложения (т.к. их предложения не были приняты на шаге 1.2). 2 делает предложение 2.2 2 сравнивает временного партнера 3 и новое предложение от 2 ; 2 предпочтительнее, чем 3. Таким образом, предложение 3, временно принятое на первом шаге, на втором шаге оказалось отклонено. 1 принимает предложение 4, поскольку, согласно её отношению предпочтения, 4 1 1, и это единственное предложение.

По итогам второго шага построено временное паросочетание 2, 3.1 Единственный мужчина, который не поставлен в пару с женщиной в паросочетании 2 – это 3. Однако, согласно его отношению предпочтения, 1 и 3 не являются допустимыми,

Работа механизма окончена, временное паросочетание 2 становится окончательным паросочетанием Нетрудно убедиться в том, что построенное паросочетание будет Таблица 1.2: Результат работы механизма отложенного принятия с предлагающими мужчинами для Примера 1. устойчивым, т.е. является индивидуально рациональным и не содержит блокирующих пар. Индивидуальная рациональность выполнена по построению.

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

1 может составить блокирующую пару с 3, т.к. 3 1 (1 ).

Однако 3 не составит блокирующую пару с 1, поскольку 1, согласно отношению предпочтения 3 является недопустимой.

2 может составить блокирующую пару с 1, т.к. 1 2 (2 ).

Однако 1 не составит блокирующую пару с 2, поскольку в паросочетании 1 состоит в паре с более предпочтительной для него женщиной 3.

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

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

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

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

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

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

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

1. * ни на одном шаге механизма не был поставлен в пару с *.

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

2. * был поставлен в пару с * на некотором шаге, однако на последующем, +-ом шаге ей был поставлен в пару другой мужчина (а + (* ) = * ). Это означает, что * *. На последующих шагах механизма * могла получать новые предложения, и Таблица 1.3: Отношения предпочтения для Примера 1.2.

в окончательном паросочетании, возможно, (* ) =. Однако на каждом последующем шага механизма * выбирает из наиболее предпочтительного, поставленного ей в пару на предыдущих шагах, и новых предложений, т.е. () (), если 0 < <. Поэтому в окончательном паросочетании ()*.

Учитывая, что * *, а отношение предпочтения * транзитивно, получаем, что (* )* *.

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

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

Пример 1.2. Пусть заданы множества = {1, 2, 3 } и = {1, 2, 3 }. Отношения предпочтения приведены в Таблице 1.3.

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

Если будет выполнен механизм отложенного принятия с предлагающими мужчинами, то на первом же шаге, в результате первого выбора наиболее предпочтительных женщин будет получено окончательное обобщённое паросочетание, в котором (1 ) = 1, (2 ) = 2, (3 ) = 3. Если же будет выполнен механизм отложенного принятия с предлагающими женщинами, то, также за один шаг, будет получено обобщённое паросочетание, в котором (1 ) = 3, (2 ) = 1, (3 ) = 2. Поскольку стороны симметричны, в соответствии с теоремой 1.1.1 оба паросочетания будут устойчивыми. Таким образом, получено два различных устойчивых паросочетания.

Более того, нетрудно заметить, что в данном примере можно построить и третье устойчивое паросочетание, назовем его, в котором (1 ) = 2, (2 ) = 3, (3 ) = 1.

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

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

Можно попробовать усилить определение устойчивого паросочетания.

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

Определение 1.6. [14] Вектор выигрышей принадлежит C-ядру игры (, ), если он не доминируется никаким другим достижимым вектором выигрышей. Иначе говоря, не существует коалиции игроков и достижимого вектора выигрышей, таких что Теперь докажем следующее утверждение:

Теорема 1.1.2. [15] При каждом профиле предпочтений, состоящем из линейных порядков, вектор выигрышей (супругов) принадлежит ядру игры () тогда и только тогда, когда соответствующее ему паросочетание является устойчивым.

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

2. Устойчивость => ядро. Если паросочетание устойчиво, но существует коалиция, состоящая из более чем двух игроков, которой выгодно отклониться от паросочетания и составить пары между собой, то в новом распределении, построенном внутри коалиции, для любой пары (, ) : (, ) = и (, ) = должно быть верно, что () и (). Однако в таком случае и образуют блокирующую пару в паросочетании. Противоречие.

1.1.2 Структура множества устойчивых паросочетаний Что изменится, если организатор механизма захотел действовать в интересах одной из сторон (например, женщин)? Можно ли выделить паросочетания, которые понравятся одной из сторон (например, женщинам ) больше остальных, или, говоря более строго, будут Парето-эффективными для женщин? Если вернуться к рассмотренному выше Примеру 1.2, то легко заметить, что устойчивое паросочетание, получившееся в результате применения механизма отложенного принятия с предлагающими женщинами, является для них наилучшим из трёх возможных устойчивых паросочетаний. Действительно, в паросочетании каждая женщина поставлена в пару с наиболее предпочтительным для неё мужчиной. Оказывается, что это не случайное совпадение.

Теорема 1.1.3. [2] При каждом профиле предпочтений, состоящем из линейных порядков, устойчивое паросочетание, полученное при применении механизма отложенного принятия с предлагающими женщинами, является единственным Паретоэффективным для среди всех устойчивых паросочетаний.

В силу симметрии аналогичное утверждение верно для мужчин.

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

Теорема 1.1.4. [2] Паросочетание слабо доминируется по Парето (для мужчин) любым другим устойчивым паросочетанием.

Таким образом, устойчивых паросочетаний существует несколько;

одно из них ( ) является Парето-оптимальным для мужчин (помножества ) и наихудшим для женщин (подмножества ), т.е. слабо доминируется по Парето для женщин любым другим устойчивым паросочетанием; другое ( ), наоборот, – наихудшим для мужчин и наилучшим для женщин. Непосредственно из этого можно сделать такой вывод:

Следствие 1.1. Пусть заданы множества и и профиль предпочтений. Если паросочетания и, полученные в результате выполнения двух версий механизма отложенного принятия, совпадают, то = = – единственное устойчивое паросочетание.

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

Теорема 1.1.5. [16] Пусть заданы множества и и профиль предпочтений. Если в некотором устойчивом паросочетании для верно, что () = (будем говорить, что – одинок), то и в любом другом устойчивом паросочетании одинок, т.е. () =.

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

Определение 1.7. [13] Бинарное отношение на множестве является частичным порядком, если оно удовлетворяет свойствам антирефлексивности, т.е. верно, что ;

транзитивности, асимметричности.

Определение 1.8. [17, 18] Решетка, или структура, – это множество, на котором задан частичный порядок, такие что, Пусть отношение частичного порядка – это отношение слабого доминирования по Парето для подмножества агентов (мужчин).

Возьмём два различных устойчивых паросочетания, и, и определим для них операцию нахождения точной верхней грани. Точная верхняя грань для двух устойчивых паросочетаний и – это такое отображение, что () := (, ) = Иначе говоря, каждому в поставим в пару более предпочтительную из двух его партнерш в и. По построению очевидно, что доминирует по Парето для подмножества, мужчин, и паросочетание, и паросочетание.

По аналогии определим теперь операцию нахождения точной нижней грани.

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

будут ли и паросочетаниями, и если да, будут ли они устойчивыми? Иначе говоря, действительно ли предложенные операции определены на множестве устойчивых паросочетаний? Теперь сформулируем теорему:

Теорема 1.1.6. [3, 9] и, найденные в соответствии с данными выше определениями, являются паросочетаниями, и притом устойчивыми.

Доказательство. 1. Если () =, то в () = и () = в силу утверждения теоремы 1.1.5.

2. Пусть не является паросочетанием (см. определение). Значит, некоторая женщина получает более одного супруга. Такое может произойти, если одновременно и считают лучшей из двух своих супруг из и. Предположим (без ограничения общности), что () =, и ( ) =. Однако предпочтения заданы линейным порядком, поэтому она обязательно предпочитает одного из мужчин другому. Пусть, тогда, с учётом того, что (), в паросочетании и образуют блокирующую пару. Значит, не является устойчивым. Случай симметричен. Получаем противоречие, следовательно, является паросочетанием.

3. Докажем, что паросочетание будет устойчивым. Пусть это не так и в паросочетании существует блокирующая пара и. Тогда предпочтения должны быть устроены так, что ().

Поскольку () является наиболее предпочтительной из () и (), верно, что () и (). Заметим, что не может стоять в паре с ни в, ни в. Из устойчивости этих паросочетаний следует, что и не образовывали ни в одном из них блокирующую пару. Значит, () и (). Но пара в новом паросочетании выбирается из этих двоих (либо (), либо ()). Таким образом, в любом случае женщина не образует с мужчиной блокирующую пару. Замечание: следует также показать, что не могут образовывать блокирующую пару женщина и мужчина, являющегося одиноким. Схема доказательства аналогична. Следовательно, не содержит блокирующей пары. Индивидуальная рациональность верна автоматически.

4. Докажем, что паросочетание присваивает каждой худшего из ее партнеров в и. Без ограничения общности положим, что () = (). Предположим противное: пусть () (). Заметим, что по построению верно, что ().

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

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

Помимо доказанной теоремы 1.1.6 можно сформулировать следующее полезное утверждение, являющееся ее следствием.

Следствие 1.2. Рассмотрим два устойчивых паросочетания и.

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

1.1.3 Сообщение предпочтений и манипулирование при построении обобщённых паросочатений Уже довольно много было сказано о структуре множества устойчивых паросочетаний, однако хотелось бы понять, насколько концепция поиска устойчивых паросочетаний заслуживает доверия. Ведь модель рассматривает агентов, обладающих предпочтениями, а концепция поиска устойчивого паросочетания предполагает, что агенты обладают свободой воли при сообщении своих предпочтений и при принятии/непринятии предлагаемого паросочетания. Сформулируем вопрос следующим образом: можно ли разработать механизм, выполнение которого приводит к устойчивому паросочетанию (будем называть его для краткости устойчивым механизмом), при использовании которого для всех агентов наиболее предпочтительно сообщать свои истинные предпочтения? К сожалению, ответ на этот вопрос – отрицательный [4, 5]. Для доказательства приведем следующий простой пример.

Пример 1.3. [5] Пусть = {1, 2 }, = {1, 2 }. Предпочтения даны в таблице 1.5.

Таблица 1.5: Предпочтения сторон в Примере 1.3.

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

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

Рассмотрим устойчивый механизм, который при данных предпочтениях выбирает паросочетание. Заметим, что если бы предпочтения 1 изменились так, как указано в таблице, то при таком новом профиле предпочтений существовало бы единственное устойчивое паросочетание, которое выбиралось бы любым устойчивым механизмом. Получается, что если истинные предпочтения 1 соответствуют исходному условию, то результат с искаженными предпочтениями оказывается для него предпочтительнее, чем результат, получаемый с истинными предпочтениями. Следовательно, построенный нами устойчивый механизм не удовлетворяет желаемому условию.

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

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

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

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

Теорема 1.1.8. [8] Пусть заданы и и профиль предпочтений. Если некоторое подмножество = заменило в профиле предпочтений свои истинные предпочтения на искаженные, то для любого паросочетания, устойчивого при новом профиле предпочтений, найдутся паросочетание, устойчивое при истинных предпочтениях, и, такие что () ().

На самом деле множество (из. Теоремы 1.1.8) может быть устроено по-разному. Пусть, например, множество состоит из одного мужчины. Согласно теореме, при любом искажении им предпочтений ни одно паросочетание, устойчивое при новом профиле предпочтений, не может оказаться строго предпочтительнее паросочетания для всех, т.е. для самого этого мужчины.

Следствие 1.3. Для каждого мужчины сообщение истинных предпочтений является слабо доминирующей стратегией при применении механизма отложенного принятия с предлагающими мужчинами.

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

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

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

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

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

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

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

Обозначим через множество абитуриентов, а через – множество вузов. Множества и конечны. Будем обозначать через элементы множества абитуриентов, а через – элементы множества вузов. Если и поставлены в пару в паросочетании, будем говорить, что абитуриент зачислен в вуз в паросочетании. Каждый абитуриент может быть зачислен не более, чем в один вуз (заметим, что в модели один к одному, рассмотренной в предыдущем разделе, аналогичное условие накладывалось на всех игроков.) Для каждого установлена квота – это целое положительное число, равное максимальному числу абитуриентов, которые могут быть зачислены в (поставлены в пару с). В дальнейшем будем говорить, что – это число мест в вузе. Дадим расширенное определение обобщённого паросочетания.

Определение 1.9. [2] Обобщенное паросочетание – это отображение такое, что:

4. |()| (число абитуриентов, зачисленных в, не превышает ) Также как и в изложенной в первом разделе модели, будем говорить, что игроки, т.е. абитуриенты и вузы, обладают предпочтениями относительно желаемого партнера в паросочетании. Профиль предпочтений абитуриентов = (1,..., || ) состоит из бинарных отношений, каждое из которых задано на множестве {} и является линейным порядком. Профиль предпочтений вузов = (1,..., || ) состоит из бинарных отношений, каждое из которых задано на множестве {} и является линейным порядком. Будем говорить, что абитуриент является допустимым для вуза, если ; вуз является допустимым для абитуриента, если.

Однако для того, чтобы иметь возможность сравнивать различные паросочетания по предпочтительности для некоторого, нужно также сделать предположения о том, как устроены его предпочтения на множестве всех подмножеств мощностью не больше, т.е. на возможных наборах абитуриентов. Вслед за [2] обычно предполагают, только если.3 В [20] показано, что при выполнении указанного предположения любой вуз всегда может сравнить между собой наборы абитуриентов, которые зачислены в этот вуз в разных устойчивых паросочетаниях. В более поздних работах показано, что для сохранения справедливости приведённых ниже результатов о существовании и структуре множества устойчивых паросочетаний достаточно более слабого предположения о том, между абитуриентами отсутствует дополняемость [9, 21]. [22] 3 Здесь и далее для того, чтобы не усложнять систему обозначений, один и тот же знак отношения предпочтения используется и для отношения, заданного на {}, и для отношения, заданного на множестве подмножеств 2{}.

Определение 1.10. Пара (, ) называется блокирующей паросочетание, если верно хотя бы одно из двух условий:

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

Теперь можно сформулировать полное определение устойчивого (по [2]) паросочетания.

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

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

Теорема 1.2.1. Пусть заданы,, квоты ( ) и профили предпочтений и, удовлетворяющие описанным выше условиям. Тогда устойчивое паросочетание всегда существует.

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

Кроме того, можно сформулировать в более общем виде аналог теоремы 1.1.5.

Теорема 1.2.2 (Rural hospital theorem). [16] Если в одном из устойчивых паросочетаний для некоторого верно, что |()| < (в вузе заполнены не все места), то в любом другом устойчивом паросочетании в зачислено то же подмножество абитуриентов (), и не зачислены никакие другие ().

Также (при выполнении предположения о том, что предпочтения вуза на множестве подмножеств абитуриентов строятся на основе его предпочтений на множестве абитуриентов) остается верным утверждение о структуре множества устойчивых паросочетаний [9, 23, 24].

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

Однако результаты, касающиеся сообщения предпочтений и манипулирования предпочтениями, не обобщаются на случай задачи один ко многим. В частности, оказывается, что вуз (игрок, имеющий квоту больше единицы) может с выгодой для себя исказить предпочтения даже в том случае, когда используется механизм отложенного принятия с предлагающими вузами. Следующий пример [6] иллюстрирует это утверждение.

Пример 1.4. Пусть = {1, 2, 3 }и = {1, 2, 3, 4 }. Квоты заданы следующим образом: 1 = 2,2 = 3 = 1. Предпочтения даны в таблице 1.6. Все абитуриенты допустимы для всех вузов и наоборот, поэтому соответствующий элемент опущен в упорядоченных списках.

Таблица 1.6: Пример манипулирования в модели один ко многим При этом профиле предпочтений существует только одно устойчивое паросочетание. Если 1 сообщит искаженные предпочтения, то при новом профиле предпочтений также существует единственное устойчивое паросочетание, причем 1 предпочтет получаемое в этом паросочетании подмножество абитуриентов – () – по сравнению с (). Таким образом, 1 может успешно исказить свои предпочтения таким образом, чтобы получить более предпочтительный набор пар в итоговом паросочетании; причем даже в случае, когда будет использован механизм отложенного принятия с предлагающими вузами.

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

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

В [25] показано, что верная следующая теорема.

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

Новый результат был получен в [26]. Доказано, что если некоторый механизм (при заданном профиле предпочтений и наборе квот) подвержен манипулированию с помощью искажения квот, то этот механизм манипулируем и путём искажения предпочтений.

Кроме того, в [26] предлагается разделение всех возможностей манипулирования с помощью квот на два типа. Манипулирование первого типа – это занижение своей квоты вузами, у которых в устойчивомм паросочетании |()| <, т.е. заполнены не все места. Манипулирование второго типа – это занижение своей квоты вузами, у которых |()| =, т.е. заняты все места.

Теорема 1.2.4. [26] Механизм отложенного принятия с предлагающими абитуриентами является единственным механизмом, устойчивым к манипулированию квотами 1-го типа.

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

1.3 Предпочтения сторон: расширения классической модели 1.3.1 Существование и эффективность устойчивого паросочетания На практике довольно легко представить ситуацию, в которой игроки не могут строго упорядочить игроков другой стороны по предпочтительности. В литературе рассматриваются модели, в которых предпочтения игроков заданы произвольными частичными порядками. Большое внимание и большое количество результатов получено для частного случая, когда предпочтения заданы слабыми порядками.

Этот частный случай интересен тем, что такие предпочтения нередко встречаются в практических приложениях, например, в задаче распределения учеников по школам.

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

В случае, когда предпочтения заданы частичными порядками, устойчивое паросочетание всегда существует [9]. Однако множество устойчивых паросочетаний, вообще говоря, не является решеткой. Более того, нарушаются доказанные выше свойства механизма отложенного принятия. Приведем простой пример, иллюстрирующий возникающие проблемы.

Пример 1.5. Пусть = 1, 2, = {1, 2 }. 1 и 2 пусты, что означает, что и для 1, и для 2 абитуриенты 1 и 2 между собой несравнимы. Предпочтения абитуриентов таковы, что 1 1 2 ; 2 2 1.

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

В [27] было предложено изменить определение устойчивого паросочетания для случая, когда предпочтения не являются линейными порядками. Помимо классической концепции устойчивости, предложено два новых понятия – супер-устойчивость и сильная устойчивость.

Отличия от классического определения устойчивого паросочетания в обоих случаях кроются в определении блокирующей пары.

Определение 1.13. Блокирующая (в концепции супер-устойчивости) пара в паросочетании – это абитуриент и вуз, такие что () (вуз не менее предпочтителен, чем вуз, в который зачислен в паросочетании ) и выполнено одно из условий:

() : (один из абитуриентов, зачисленных в, не предпочтительнее, чем );

|() < |, (в вузе есть свободные места и абитуриент не является недопустимым).

В концепции сильной устойчивости также требуют, чтобы либо Новое определение блокирующей пары является более слабым, чем оригинальное. Легко показать, что как супер-устойчивое, так и сильно устойчивое паросочетание может не существовать – см. Пример 1.5.

Однако показано, что когда предпочтения абитуриентов заданы линейными порядками, а предпочтения вузов заданы частичными порядками, и когда множество сильноустойчивых паросочетаний непусто, оно образует решетку [28] относительно отношений Паретодоминирования для каждой из сторон. Кроме того, если предпочтения обеих сторон заданы частичными порядками, то множество сильноустойчивых паросочетаний может не образовывать решетку, но множество суперустойчивых паросочетаний (если оно непусто) [29] является решеткой относительно отношений Парето-доминирования с точки зрения каждой из сторон. Предложенное изменение определения устойчивого паросочетания позволяет получить красивые структурные результаты, но, в то же время, порождает серьезную проблему несуществования решения. Кроме того, вызывает большие вопросы теоретико-игровая интерпретация такого определения устойчивости:

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

Другое направление развития в моделировании предпочтений агентов связано с переходом от задания предпочтений бинарными отношениями к функциям выбора. Впервые такой подход был предложен [7], и вскоре был серьезно развит в [23]. Расширяя возможности описания предпочтений, авторы расширяют и понятие обобщенного паросочетания. В этих моделях каждая пара в обобщенном паросочетании имеет дополнительный (и вообще говоря, изменяемый) набор характеристик. Например, абитуриент может поступать в вуз с получением общежития или без получения общежития. Соответственно, функции выбора (с помощью которых моделируются предпочтения сторон в модели) заданы на множестве таких «контрактов». В [23] и последующих работах [30,31], моделирующих предпочтения агентов с помощью функций выбора, обычно предполагается, что функция выбора удовлетворяет одному из вариантов свойства заменяемости (substitutability).

При выполнении предположений о заменяемости контрактов и соответствующих свойствах функций выбора устойчивое паросочетание существует. В зависимости от строгости сделанного предположения о замещении показывают, что множество устойчивых паросочетаний образует решетку [23, 31] и существуют аналоги механизма отложенного принятия Гейла-Шепли, порождающие лучшее для абитуриентов и лучшее для вузов паросочетания; в то же время при более слабых предположениях [32] множество устойчивых паросочетаний также непусто, но не образует рещетку в соответствии с отношением предпочтения ни одной из сторон.

1.3.2 Механизмы построения устойчивого паросочетания Для классической задачи в разделе 1.1 настоящей главы был описан механизм отложенного принятия, предложенный Гейлом и Шепли, и позволяющий построить устойчивое паросочетание в любое задаче.

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

В случае, когда предпочтения заданы не линейными порядками, а слабыми порядками, частичными порядками или описываются функциями выбора, также существуют аналоги механизма отложенного принятия [9, 31, 33](причем обеих версий, для каждой из предлагающих сторон). Фактически работа таких механизмов состоит из двух действий: во-первых, если в предпочтениях существуют безразличия, то они каким-либо образом устраняются; во-вторых, выполняются действия, предусмотренные механизмом отложенного принятия.

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

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

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

Теорема 1.3.1. [35] Пусть предпочтения вузов заданы слабыми порядками, а предпочтения детей – линейными порядками. Тогда неманипулируемый механизм не может доминировать (по Парето с точки зрения абитуриентов) никакой механизм отложенного принятия с предлагающими абитуриентами и заданной процедурой устранения безразличий.

Таким образом, эффективный неманипулируемый устойчивый механизм можно искать только в классе механизмов отложенного принятия с различными способами устранения безразличий. В [36] этот результат был расширен для менее строго определения устойчивого паросочетания.

В [37] был предложен альтернативный подход к проблеме. А именно, были предложены ограничения на профили предпочтений вузов и абитуриентов, при выполнении которых неманипулируемый, устойчивый и эффективный механизм. Для случая, когда предпочтения удовлетворяют свойству «ties in bottom», т.е. неразличимы друг с другом только несколько наименее предпочтительных альтернатив, получены необходимые и достаточные условия существования такого механизма. Недостатком полученных результатов является то, что полученные условия накладываются не на предпочтения отдельных агентов, а именно на профиль целиком, что затрудняет применение полученных результатов в прикладных задачах.

1.4 Анализ централизованных механизмов распределения, используемых на практике Задача построения паросочетания при отсутствии денежных трансфертов между участниками возникает в большом количестве практических ситуаций: распределение учеников по школам, абитуриентов по вузам, стажеров по организациям или отделам внутри организации, молодых докторов по больничным интернатурам и т.п. Во многих случаях для решения задачи распределения используется централизованный механизм, т.е. предпочтения сторон и информация о квотах собираются некоторым единым органом (вручную или с помощью информационной системы) и затем уже строится паросочетание (распределение). В других случаях используются псевдо-централизованные механизмы, когда устанавливаются единые правила взаимодействия между сторонами (например, абитуриентами и вузами), но итоговое распределение определяется в результате индивидуальных (хотя и ограниченных регламентом) взаимодействий. Примером использования такого подхода является приемная кампания в вузах России и Украины, подробный разбор которой проведен в настоящей работе. Наконец, третий подход предполагает использование полностью децентрализованной схемы, когда возможные взаимодействия никак не регламентированы. Примером третьего подхода является система поступления в вузы в США. В данном разделе проведен обзор исследований, посвященных анализу применяемых на практике централизованных схем распределения, их достоинств и недостатков, а также стимулов участия в централизованных схемах для агентов с обеих сторон рынка.

1.4.1 Механизм распределения в терапевтическую интернатуру США Первая работа в этой области [12] была посвящена истории развития программы NRMP (National Resident Matching Program, Национальная программа распределения резидентов). В [19] проанализирована история развития механизмов распределения в данной программе. История программы зачисления начинается с 1945 г., когда впервые были установлены единые правила распределения интернов по больницам. Высокая конкуренция госпиталей за потенциальных интернов привела к тому, что больницы старались сделать предложения заинтересовавшим их студентам как можно раньше. Дело доходило до того, что студенты выбирали распределение в интернатуру за 1,5-2 года до окончания основного курса. Для борьбы с такими «ранними предложениями» ввели ограничение по времени, когда больницы могут предлагать места студентам. Из-за этого ограничения от студентов стали требовать очень быстрого ответа на предложение (вплоть до нескольких часов). Для решения этой проблемы правила распределения неоднократно изменялись. Показано [12], что практики распределения будущих врачей, использовавшиеся до 1952 г., порождали распределения, не лежавшие в ядре соответствующей игры, и, соответственно, неустойчивые. Таким образом, было показано, что механизмы, порождающие неустойчивое распределение агентов, не могут долго существовать, поскольку после объявления распределения находятся группы недовольных, желающих изменить распределение.

Наконец, в 1952 г. был внедрен механизм, аналогичный механизму отложенного принятия. Этот централизованный механизм успешно использовался до 1995 г. Версия механизма 1952 г. работала в интересах больниц, то есть из всех возможных устойчивых паросочетаний выбирала наилучшее для больниц. Показано, что в механизме NRMP- интернам всегда выгодно честно сообщать свой наиболее предпочтительный госпиталь. Кроме того, невыгодно искажать свои предпочтения больницам, имеющим одну вакантную позицию. В остальном как больницы, так и будущие доктора имели возможности манипулирования, т.е. получения лучшего распределения путем сообщения в системе искаженных предпочтений. Позднее, в [19] проанализировали существующий механизм и предложили реформу механизма распределения интернов. Во-первых, была выбрана версия механизма отложенного принятия с предлагающими интернами, что сделало механизм ориентированным на интересы будущих докторов, а не больниц, как это было раньше. Во-вторых, были учтены новые проблемы и модификации, возникшие в системе распределения интернов с 50-х годов. Когда первоначальный механизм создавался, подавляющее большинство выпускников медицинских вузов составляли мужчины. Однако, к 90м годам женщины составляли значительную долю выпускников медицинских вузов, и это создало неожиданную проблему – среди будущих докторов нередко стали образовываться семейные пары. Молодожены, естественно, хотели получить не просто хорошее место в больнице, но два хороших места в больницах одного города. Это приводило к тому, что такие пары пытались договариваться с больницами в обход централизованной программы. Помимо появления семейных пар, в системе распределения появились и другие дополнительные ограничения, связанные с организацией интернатуры в различных больницах. Например, некоторые студенты получали распределение сразу на две программы, первого и второго года обучения, которые были связаны между собой. В [19] была предложена модификация механизма, которая позволила учесть предпочтения семейных пар с наложением некоторых ограничений на выбор супругов. Их механизм был основан на предложенной в [38] последовательной процедуре случайного устранения неустойчивостей. Однако первоначально процедура подразумевала случайный выбор объектов. Для выбора способа устранения случайности в процедуре было проведено специальное компьютерное моделирование на имевшихся исторических данных о предпочтениях больниц и интернов в NRMP. Было показано, что в общем случае, при произвольных предпочтениях супружеских пар и студентов, претендующих одновременно на две программы относительно желаемых мест, устойчивого распределения может не существовать. Однако, в случае программы NRMP для всех имевшихся в распоряжении исследователей исторических профилей предпочтений стабильное паросочетание существовало и могло быть найдено предложенным механизмом.

1.4.2 Прием в школы и детские сады Ещё одно приложение теории обобщенных паросочетаний – распределение детей по школам и детским садам. Особенность этой задачи и ее отличие от классической проблемы состоит в том, что школы при приеме учеников, как правило, не проводят специальных вступительных испытаний (особенно в младших классах). Некоторые дети получают приоритет при поступлении в школу на основании социальных льгот, проживания поблизости от школы или обучения в школе братьев и сестер. Таким образом, школы не могут сообщить строго упорядоченный по предпочтительности список потенциальных учеников, а могут лишь указать группы учеников по убыванию приоритетности обучения. Кроме того, эти приоритеты, как правило, установлены законом или муниципальным органом власти, и не являются, в строгом смысле, «предпочтениями» школ (детских садов). Соответственно, школы и детские сады не имеют ни возможностей, ни стимулов к искажению этих приоритетов. Таким образом, в некоторых прикладных проектах снимается проблема манипулирования предпочтениями со стороны учебных учреждений.

Впервые эта задача была поставлена в научной литературе, когда в [33, 35, 39] были проанализированы существующие системы распределения учащихся в школьных округах Нью-Йорка и Бостона и предложены реформы этих систем. До 2001 года в Бостоне использовался следующий механизм зачисления учащихся. Каждый учащийся (совместно с родителями) составлял список школ по убыванию привлекательности. На первом этапе рассматривались только школы, указанные первыми в списках учеников. Если поставивших школу на первом место оказывалось больше, чем мест, то учитывались социальные льготы учащихся в данной школе. В спорных случаях зачисляемые выбирались случайным образом. Для учеников, которые не получили места на первом этапе, рассматривались их вторые по предпочтительности школы. Однако, если школа, указанная учеником на втором месте, была заполнена другими желающими еще на первом этапе, то ученик снова не получал места. Распределение, к которому приводит такой механизм, вообще говоря, неустойчивое. Кроме того, при такой схеме распределения родителям и ученикам чаще всего было невыгодно сообщать свои настоящие предпочтения. Более того, сами руководители Бостонского образовательного округа в специальных брошюрах рекомендовали родителям «думать стратегически» при составлении списка предпочтений. Это приводило к тому, что «хитрые»

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

Первый вариант представлял собой модификацию механизма отложенного принятия с введением случайного устранения безразличий в предпочтениях [39]. Второй предложенный вариант – механизм Верхних Циклов Обмена (Top Trading Cycles, TTC) [33, 40]. Второй механизм порождает паросочетание, которое, вообще говоря, может доминировать по Парето (с точки зрения учеников) устойчивое паросочетание, построенное механизмом отложенного принятия с предлагающими учениками. Однако, в конечном итоге, руководителями Бостонского образовательного округа был выбран именно механизм отложенного принятия Гейла-Шепли. Основной причиной послужило то, что порождаемое им паросочетание всегда является устойчивым, а в контексте распределения в государственные школы устойчивость в некотором смысле эквивалентна справедливости и соблюдению установленных законом приоритетов. Действительно, если распределение устойчиво, то никакой ученик не может заявить, что в школе, куда он хотел бы попасть, учится ребенок с меньшим приоритетом.

К сожалению, в случае, когда предпочтения школ заданы слабыми порядками, то есть имеются группы детей, несравнимых между собой, (т.е. имеющие один уровень приоритета, например, проживающие одинаково близко от школы), могут существовать попарно-устойчивые паросочетания, которые не являются Парето-эффективными и не принадлежат ядру. Более того, как уже было сказано выше, в [35] показано, что любой неманипулируемый механизм – это механизм отложенного принятия с предварительным (и не зависящим от предпочтений учащихся) устранением безразличий.

В [35] также было проведено теоретическое, имитационное (расчетное) и экспериментальное сравнение разных процедур устранения безразличий. Было показано, что лучшими свойствам обладает процедура устранения безразличий, в которой для всех детей задается единый мастер-лист, и при необходимости устранения безразличий приоритет всегда получает ребенок с меньшим номером в мастер-листе.

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

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

Наиболее часто встречающаяся дополнительная специфика в задаче распределения детей – необходимость предотвращения сегрегации, обеспечение расового, национального разнообразия в школе, равного доступа и отсутствия разделения детей по доходу и социальным характеристикам их родителей. Впервые эта проблема была сформулирована еще в [33]. Были предложены модификации механизмов ГейлаШепли и TTC, позволяющие, помимо общего числа мест в школе, устанавливать отдельные квоты для детей разных национальностей и социальных групп. Причем было показано, что новые механизмы сохраняют важно свойство оригинальных версий – у учеников (точнее, у их родителей) по-прежнему нет стимулов для искажения истинных предпочтений. Проблема, впервые сформулированная в [33], вдохновила серию работ, посвященных положительной дискриминации в моделях обобщенных паросочетаний, выбору лучших механизмов и способов обеспечения (квоты, изменения предпочтений и т.п.) такой положительной дискриминации [41–43].

Распределение детей по яслям и детским садам – не менее важная задача, также решаемая в некоторых случаях с помощью теории обобщенных паросочетаний и соответствующих централизованных механизмов. Более того, во многих странах, например, в США, распределение в старшие группы детских садов проводится в рамках той же схемы, что и школьное распределение, и система не имеет существенных отличий. Однако в других странах, таких как Дания, в детских садах и яслях нет разделения на группы по возрасту, и дети разного возраста занимаются вместе. Соответственно, число мест в группе определяется в целом для детей разных возрастов. Возникает проблема пересекающихся поколений: каждый год на место в детском саду претендуют и новые малыши, и дети, уже посещавшие сад, но желающие, возможно, сменить сад. В [44] предложены механизмы для организации централизованного справедливого распределения детей в таком случае.

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

В [45] был проанализирован механизм, используемый в Турции для распределения абитуриентов (в основном выпускников школ) по бакалаврским программам вузов. В Турции прием в вузы проводится по конкурсу, причем основанием для отбора являются баллы, полученные на едином выпускном экзамене (отдаленном аналоге российского ЕГЭ). Абитуриент сдает экзамен по разным предметам; все бакалаврские программы разбиты на ограниченное количество так называемых предметных категорий. Для каждой категории установлена формула, по которой считается средний балл абитуриента. Например, в формуле для естественно-научного направления наибольший вес будет иметь результат экзамена по Science (Естественные науки), а для гуманитарного направления наибольший вес у экзамена по языку. Внутри направления любая программа обязана использовать одинаковый набор весов, т.е. внутри одного направления все абитуриенты упорядочены одинаково.

Для распределения абитуриентов в Турции [45] используется многокритериальный серийный диктаторский механизм (multi-categoriy serial dictatorship, MCSD). Механизм работает следующим образом.

На первом шаге в каждой предметной категории абитуриенты получают место в вузе в соответствии с процедурой серийного диктатора:

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

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

Хотя на первый взгляд этот механизм кажется отличным от механизма отложенного принятия и ориентированным на интересы студентов, в [45] показано, что MCSD эквивалентен механизму отложенного принятия с предлагающими вузами. Соответственно, механизм обладает всеми свойствами механизма отложенного принятия: порождает устойчивое паросочетание, наихудшее из всех устойчивых для абитуриентов и создает абитуриентам стимулы для искажения предпочтений.

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

Еще один интересный механизм распределения используется в Германии для набора абитуриентов на программы медицинских вузов и факультетов [46]. Централизованная процедура предусмотрена только для будущих медиков. Все места, выделенные для зачисления, делятся на три группы: места, зарезервированные для лучших абитуриентов (20% мест), места, зарезервированные для давно пытающихся поступить абитуриентов (20%) и свободные места (60%). Исследовательский интерес представляет процедура распределения абитуриентов. Первыми получают возможность поступления на выделенные для них 20% мест лучшие абитуриенты. Каждый (из числа лучших) абитуриент сообщает свои предпочтения. Затем абитуриенты зачисляются в вузы по Бостонскому механизму, или механизму немедленного принятия. Это означает, что сначала вузы рассматривают только абитуриентов, поставивших их на первое место. Затем, если остались свободные места (из квоты для лучших), рассматриваются абитуриенты, поставившие вуз на второе место и так далее. Если абитуриент поставил на первые два места сильные вузы, и не прошел в первый вуз, то он рискует не пройти во второй, потому что все места будут заполнены на первом же шаге. Такая же процедура проводится для группы взрослых абитуриентов. После проведения этих процедур для двух приоритетных групп все абитуриенты, не получившие места, и все незаполненные места (включая выделенные приоритетные) попадают в общий пул абитуриентов и мест. Затем для заполнения всех оставшихся мест используется механизм отложенного принятия с предлагающими вузами. Такая система создана для того, чтобы дать двум специальным группам: самым сильным абитуриентам и давно пытающимся поступить взрослым, – дополнительные возможности. В [46] показано, что существующая схема подвержена манипулированию предпочтениями со стороны абитуриентов из приоритетных групп. Более того, только манипулируя, т.е. изменяя упорядочение вузов по предпочтительности и/или исключая вузы из списка допустимых, абитуриент может использовать предоставленный ему приоритет в своих интересах. В любом равновесии соответствующей игры, где стратегия каждого абитуриента – сообщаемый упорядоченный список вузов, а выигрыш – получаемое место учебы, окончательное паросочетание будет устойчивым.

Значительный интерес представляют проведенные исследователями эксперименты [46, 47], показавшие, что абитуриенты не способны прийти к равновесным стратегиям, даже если проходят «обучение», т.е. участвуют в соответствующей игре большое количество раз. В конечном итоге то, что было предложено разработчиками механизма для предоставления дополнительных возможностей лучшим абитуриентам, оборачивается ухудшением положения этой группы абитуриентов.

1.4.4 Пересадка почек: обмен донорами Огромное количество людей во всем мире и, в частности, в США, ежегодно нуждаются в пересадке почки. Часть из них получает пересадку от трупного донора, однако число таких органов значительно меньше, чем потребность в пересадке. Поскольку здоровый человек имеет две почки и в принципе способен жить здоровой жизнью с только лишь одной из них, существует возможность пересадки от живого донора. В США пересадка почки разрешена от любого живого донора, который хочет безвозмездно пожертвовать ее нуждающемуся пациенту. Однако часто случается так, что добровольный донор и его нуждающийся в трансплантации родственник/друг несовместимы друг с другом по группе крови или другим факторам. Таким образом, несмотря на готовность донора помочь, пересадка оказывается невозможной. В [48, 49] предложена формальная модель системы обмена почками между такими несовместимыми парами (донор из первой пары отдает почку рецепиенту из второй, а донор из второй пары – рецепиенту из первой). Были получены теоретические результаты, показывающие существование неманипулируемого механизма обмена, а затем, совместно с трансплантологами региона Новая Англия (США), была спроектирована система обмена почками [50]. В дальнейшем похожие схемы были внедрены в нескольких регионах США, Канады и Великобритании. Это позволило существенно увеличить число проводимых трансплантаций и значительно сократить время ожидания трансплантации для больных. Разработаны различные типы механизмов в зависимости от законодательных и медицинских особенностей в различных регионах и странах. В самой простой схеме донор и рецепиент могут либо подходить, либо не подходить друг другу, при этом степень совместимости не оценивается. В таком случае исследователям удалось предложить два неманипулируемых механизма, позволяющих строить максимально возможное паросочетание, то есть схему перекрестной трансплантации. Под неманипулируемостью в данном случае понимается тот факт, что всем пациентам выгодно раскрывать информацию о своих потенциальных донорах (может быть несколько родных/друзей, готовых пожертвовать почку). Один из механизмов основан на традиционном для трансплантологии принципе очередей (приоритетов у больных). Второй предложенный механизм – стохастический, основан на принципе эгалитаризма. Механизм выбирает схему трансплантации таким образом, чтобы самая низкая среди всех пациентов вероятность получить почку была как можно выше.

Стохастический механизм не был применен в прикладных проектах, поскольку он сложнее для понимания пациентами, донорами и врачами, чем детерминированный механизм. Разработаны схемы обмена [51, 52], учитывающие совместимость по группе крови, а также учтывающие приоритеты пациентов в зависимости от сложности поиска донора для данного конкретного пациента и тяжести состояния.

1.4.5 Провалы централизованных механизмов В [53] проведен анализ системы распределения молодых гастроэнтерологов в США. Распределение гастроэнтерологов с середины 80-х до конца 90-х годов осуществлялось с помощью централизованного механизма, организованного аналогично рассмотренному нами выше механизму NRMP. Однако в конце 90-х годов централизованная схема была отменена, поскольку большинство больниц и интернов предпочитали договариваться задолго до официальной централизованной процедуры. В течение последующих нескольких лет никаких единых правил распределения по больницам для молодых гастроэнтерологов не существовало. В 2006 году при участии исследователей удалось восстановить централизованную схему распределения. Выделены три основные проблемы децентрализованного рынка: перегруженность, широта охвата и «безопасность». Первая проблема заключается в том, что в отсутствие централизованного механизма любое предложение позиции больницей производится «вручную», а ответ молодого доктора требует времени. Таким образом, больница может просто за счет дефицита времени не иметь возможности предложить работу всем кандидатам, в которых она заинтересована. Это приводит к тому, что больницы стараются делать предложения как можно раньше.

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

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

Третья проблема связана с первыми двумя. Каждая больница опасается стратегических действий других агентов, и поэтому сама старается всех «перехитрить». Причем эта проблема возникает и в том случае, если участникам предлагается вернуться к централизованной процедуре. Госпиталь опасается, что если он войдет в программу централизованного распределения, то может пострадать от действий других больниц, по-прежнему делающих предложения до начала централизованного распределения. Наконец, в [54] с использованием статистики заработных плат показано, что децентрализация распределения интернов не приводит к росту их заработных плат. Это результат был особенно важен в связи с исками некоторых выпускников медицинских вузов США к организаторам централизованной процедуры зачисления относительно неконкурентного назначения заработных плат. Таким образом, было показано, что такие иски не имеют под собой достаточного основания. Был проведен ряд экспериментов, моделирующих ситуацию, предшествовавшую отказу от централизованной процедуры в 1997 г. Было обнаружено, что произвольный отказ участников рынка от участия в централизованном механизме был вызван сочетанием двух факторов. Во-первых, из-за изменений в системе подготовки гастроэнтерологов сильно сократилось число выпускников, желающих получить место в интернатуре по этой специальности. Во-вторых, сами интерны не подозревали о том, что произошло такое значительно сокращение числа кандидатов, в то время как госпитали были прекрасно осведомлены о дефиците выпускников. Таким образом, в г., получая предложение до начала официальной централизованной процедуры, молодые врачи, как правило, не отказывались от него, т.к.

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

Распределение помощников федеральных судей Помощниками федеральных судей становятся молодые юристы после окончания вуза. И молодые выпускники, и судьи заинтересованы в таком распределении: молодежь получает возможность набраться опыта и установить контакты, а профессиональные судьи получают помощников в своей профессиональной деятельности. При этом процесс распределения происходит абсолютно нецентрализованно. На данном рынке неоднократно предпринимались попытки установления единой даты начала процесса распределения, однако всякий раз установленные сроки быстро начинают нарушаться. Эта проблема изучалась специалистами по дизайну экономических механизмов и экспериментальной экономике [55], а также профессиональными юристами [56]. В результате проведения масштабных опросов как судей, так и молодых выпускников (было проведено два больших раунда опросов, в 1999-2000 и 2004-2007 гг.) было выявлено, что основные проблемы при распределении помощников судей схожи с проблемами других децентрализованных рынков (см., например, выше рынок гастроэнтерологов). С помощью лабораторных экспериментов и компьютерного моделирования в [55] оценивалось влияние тех или иных изменений в процедуре распределения на его эффективность. Однако вывод неутешителен. Основной причиной невозможности избавиться от ускорения сроков поступления предложений и порождаемой этим неэффективности является вера как судей, так и молодых выпускников в то, что будущему клерку выгоднее всегда соглашаться на первое поступившее предложение. Таким образом, переходу к более эффективному распределению мешает уверенность каждого из участников рынка в том, что другие не согласятся на такой переход.

Глава Обобщенные паросочетания при предпочтениях, построенных на основе порогового выбора В настоящей главе будет рассмотрена модель обобщенных паросочетаний при предпочтениях, построенных на основе порогового выбора, а именно, предпочтениях, заданных простейшими полупорядками (раздел 2.1) и интервальными порядками (раздел 2.2). Будет показано существование устойчивого паросочетания, связь между линейными расширениями отношений предпочтения и устойчивыми паросочетаниями, а также сформулирован и доказан критерий Паретоэффективности устойчивого паросочетания. В разделе 2.3 будет предложен новый способ построения линейного расширения для отношений предпочтения. В разделе 2.4. дано описание разработанного комплекса программ, реализующего предложенные механизмы.

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

2.1 Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками Пусть – множество абитуриентов, – множество вузов. Множества абитуриентов и вузов конечны. Будем обозначать через элементы множества абитуриентов, а через – элементы множества вузов.

Каждый абитуриент может быть зачислен не более, чем в один вуз, а каждый вуз имеет мест.

Абитуриенты и вузы высказывают свои предпочтения, которые устроены следующим образом. Профиль предпочтений абитуриентов = (1,..., || ) состоит из линейных порядков. Отношение предпочтения каждого абитуриента задано на множестве {}, состоящем из вузов и возможности остаться незачисленным1. Иначе говоря, каждый абитуриент составляет упорядоченный по предпочтительности получения места список вузов, причём вузы начиная с некоторой позиции в этом списке являются недопустимыми для абитуриента (предпочтительнее не обучаться нигде, чем обучаться в таком вузе). Профиль предпочтений вузов = (1,..., || ) состоит из простейших полупорядков. Каждое такое отношение предпочтения задано на множестве2 {}, состоящем из всех абитуриентов и возможности оставить место незаполненным. Каждое такое бинарное отношение удовлетворяет требованию «отсутствия безразличия с 1 Элемент в данном множестве соответствует ситуации, когда абитуриент не получает места ни в одном вузе 2 Элемент в данном множестве соответствует ситуации, когда место в вузе остаётся вакантным незачислением»:

Таким образом, исключена ситуация, когда вузу безразлично, зачислен ли абитуриент, или место оставлено пустым.

Дадим формальное определение простейшего полупорядка. Сначала дадим определение полупорядка [57, 58].

Определение 2.1. Бинарное отношение является полупорядком на, если оно удовлетворяет условиям ацикличности, Как и главе 1, будем говорить, что, если (, ).

Пусть () – отношение безразличия для, т.е. () ( ). Также введем обозначения для множеств доминируемых и доминирующих альтернатив: ( ) = { : } и ( ) = { :

Определение 2.2. Полупорядок является простейшим полупорядком [59, 60], если он удовлетворяет условиям слабой отрицательной транзитивности:

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

Пример 2.1. Три абитуриента, 1, 2, 3, подали заявления на факультет экономики. Набранные ими баллы составили 65, 63, и 61 балл из 100 соответственно. Предпочтения факультета с учётом набранных абитуриентами баллов могут быть построены исходя из следующих соображений. Во-первых, практика рассматриваемого факультета показывает, что разницу в 2 балла между результатами абитуриентов следует считать несущественной, поскольку такое небольшое различие может быть связано с везением или быть попросту случайным.