Диссертация (Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками)

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕУЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГООБРАЗОВАНИЯНАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТВЫСШАЯ ШКОЛА ЭКОНОМИКИНа правах рукописиУДК xxx.xxxКИСЕЛЬГОФ СОФЬЯ ГЕННАДЬЕВНАОБОБЩЕННЫЕ ПАРОСОЧЕТАНИЯ ПРИ ПРЕДПОЧТЕНИЯХ,НЕ ЯВЛЯЮЩИХСЯ ЛИНЕЙНЫМИ ПОРЯДКАМИСпециальность 05.13.18 —«Математическое моделирование, численные методы и комплексыпрограмм»Диссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:доктор технических наук, с.н.с.Алескеров Ф.Т.Москва – 2014СодержаниеВведение . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . .51 Обобщенные паросочетания: классические результаты . . . 131.1 Обобщенные паросочетания один к одному, или задача освадьбах . . . . . . . . . . . . . . . . . . . . . . . . . . . .131.1.1 Устойчивое паросочетание: существование и механизм построения . . . . . . .

. . . . . . . . . . . . . .131.1.2 Структура множества устойчивых паросочетаний . .261.1.3 Сообщение предпочтений и манипулирование при построении обобщённых паросочатений . . . . . . . . .311.2 Обобщенные паросочетания один ко многим . .

. . . . . .351.3 Предпочтения сторон: расширения классической модели .421.3.1 Существование и эффективность устойчивого паросочетания . . . . . . . . . . . . . . . . . . . . . . . . .421.3.2 Механизмы построения устойчивого паросочетания .461.4 Анализ централизованных механизмов распределения, используемых на практике . . .

. . . . . . . . . . . . . . . .481.4.1 Механизм распределения в терапевтическую интернатуру США . . . . . . . . . . . . . . . . . . . . . . .491.4.2 Прием в школы и детские сады . . . . . . . . . . . .5221.4.3 Централизованные схемы зачисления абитуриентов ввузы . .

. . . . . . . . . . . . . . . . . . . . . . . . . .561.4.4 Пересадка почек: обмен донорами . . . . . . . . . . .601.4.5 Провалы централизованных механизмов . . . . . . .622 Обобщенные паросочетания при предпочтениях, построенных на основе порогового выбора . . . .

. . . . . . . . . 672.1 Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками. . . . . . . . . . . .682.1.1 Существование устойчивого паросочетания . . . . . .712.1.2 Механизм отложенного принятия и паросочетания,неэффективные для абитуриентов . . . . .

. . . . . .742.1.3 Устойчивые улучшающие циклы и построение эффективного для абитуриентов устойчивого паросочетания762.2 Обобщенные паросочетания при предпочтениях, являющихся интервальными порядками . . . . . . . . . . . . . .822.3 Неманипулируемый механизм со обратным устранениембезразличий . . . . .

. . . . . . . . . . . . . . . . . . . . .922.4 Комплекс программ . . . . . . . . . . . . . . . . . . . . . .982.5 Заключение по Главе 2. . . . . . . . . . . . . . . . . . . . . 1023 Прикладные аспекты задачи распределения абитуриентовпо вузам . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. 1043.1 Граничные оценки и устойчивые паросочетания . . . . . . 1043.1.1 Механизмы построения устойчивого набора граничных оценок . . . . . . . . . . . . . . . . . . . . . . . . 1083.1.2 Два вида механизмов и эффективность паросочетания 1123.1.3 Сравнение H-устойчивости и L-устойчивости . . . . . 11633.1.4 Манипулирование предпочтениями . . . . . . .

. . . 1243.2 Моделирование приемной кампании в РФ . . . . . . . . . 1273.2.1 Организация приемной кампании в российских государственных вузах . . . . . . . . . . . . . . . . . . . . 1273.2.2 Математическая модель . . . . . . . . . . . . . . . . . 1293.2.3 Поведение абитуриента в зависимости от уровня подготовки .

. . . . . . . . . . . . . . . . . . . . . . . . . 1333.2.4 Моделирование приемной кампании . . . . . . . . . . 1403.3 Заключение по Главе 3. . . . . . . . . . . . . . . . . . . . . 148Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. 150Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152A Доказательство утверждений о выборе абитуриентов . . . 160B Исходные коды разработанного программного комплекса . 180B.0.1Устранение безразличий в предпочтениях агентов . . 180B.0.2Генерация предпочтений случайным образом . . . . . 181B.0.3Модуль проверки эффективности паросочетания . . .

1834ВведениеРассмотрим следующую задачу: в некотором двудольном графе = ( ∪, ) необходимо найти паросочетание (множество несмежных дуг). Классическая задача состоит в поиске паросочетания максимальной мощности [1]. Решение этой задачи имеет прикладное значение при формировании комитетов, распределении работников по должностям и др. При этом вершинам рассматриваемого двудольного графав некоторых приложениях соответствуют игроки – люди или организации, обладающие свободой воли. Одна из интересных модификацийзадачи поиска паросочетания, в корне меняющая подход к ее решению,– поиск паросочетания с учетом предпочтений игроков, «отвечающих»за отдельные вершины графа.

Для анализа подобных ситуаций Д. Гейлом и Л. Шепли в 1962 году [2] была предложена теория обобщенных паросочетаний. Ими было введено новое понятие – устойчивоепаросочетание, т.е. паросочетание, от которого не захотят отказаться отдельные игроки.

Было показано, что устойчивое паросочетаниевсегда сушествует, и предложен механизм его построения. В отличиеот классической задачи поиска паросочетания, была предложена также модель «один-ко-многим», в которой вершины (игроки) одного изподмножеств могут составлять не одну, а несколько пар. Эта модельимеет большое прикладное значение в задачах распределения абиту-5риентов по вузам, выпускников вузов на работу и т.п. ВпоследствииД. Гейлом, Э.

Ротом, М. Сотомайор и другими [3–9] были исследованы различные аспекты данной задачи, рассмотрены разные походык моделированию предпочтений и определению устойчивости. В 2012г. Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике «за теорию устойчивого распределения и практики устройстварынков» [10, 11].Актуальность темы Важное направление в развитии теории обобщенных паросочетаний: разработка моделей и механизмов, учитывающих специальные особенности предпочтений игроков. В классической теории обобщенных паросочетаний предпочтения агентов задаются линейными порядками [2, 4, 9, 12], то есть предполагается, чтокаждый игрок может строго упорядочить игроков противоположнойстороны по предпочтительности. В реальных приложениях предпочтения одной или обеих сторон часто основаны на неточных измерениях(таких, как экзаменационные оценки, тесты, результаты собеседований) и поэтому представляется актуальным исследование моделей, вкоторых предпочтения сторон не являются линейными порядками.При разработке и внедрении механизмов на практике важно, чтобыигроки не могли злоупотреблять свободой выбора, предоставленнойим в рамках механизма.

По этой причине особенно актуальной является разработка неманипулируемых механизмов, т.е. таких, в которыхучастникам не выгодно искажать свои предпочтения.Целью данной работы является исследование модели обобщенныхпаросочетаний при предпочтениях, не являющихся линейными порядками.6Для достижения поставленной цели были решены следующие задачи:1. Написан аналитический обзор классических результатов в области теории обобщенных паросочетаний при предпочтениях, заданных линейными порядками, а также исследований используемыхна практике централизованных механизмов распределения.2.

Исследовано существование и возможность построения эффективного устойчивого паросочетания в модели «один ко многим», когдапредпочтения заданы интервальными порядками.3. Разработан неманипулируемый устойчивый механизм, при использовании которого риски построения неэффективного паросочетания будут минимальны.4. Исследована модель обобщенных паросочетаний, описана концепция устойчивости и доказано существование устойчивого паросочетания в случае, когда предпочтения заданы слабыми порядками,а устойчивость предполагает одинаковый результат для неразличимых между собой игроков.5. Исследован механизм организации приемной кампании в России; показаны особенности и «узкие места» используемой псевдоцентрализованной схемы.6.

Разработан комплекс программ, реализующий предложенные механизмы.Научная новизна:1. Впервые исследована модель обобщенных паросочетаний с предпочтениями, заданными простейшими полупорядками.72. Впервые исследована модель обобщенных паросочетаний с предпочтениями, заданными интервальными порядками.3. Впервые предложен механизм построения устойчивого паросочетания, не создающий возможностей манипулирования, и при этомобеспечивающий меньшую, по сравнению со случайным устранением безразличий, вероятность построения неэффективного паросочетания.4. Впервые показана взаимосвязь централизованных систем распределения, основанных на граничных оценках, и устойчивых обобщенных паросочетаний.5.