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

На правах рукописиКИСЕЛЬГОФ Софья ГеннадьевнаОбобщенные паросочетания при предпочтениях,не являющихся линейными порядкамиСпециальность 05.13.18 — Математическое моделирование,численные методы и комплексы программАВТОРЕФЕРАТдиссертации на соискание учёной степеникандидата физико-математических наукМосква — 2014Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики»Научный руководитель:доктор технических наук,старший научный сотрудникзаведующий кафедрой высшей математикина факультете экономики Национальногоисследовательского университета«Высшая школа экономики»Алескеров Фуад Таги оглыОфициальные оппоненты: доктор физико-математических наук,ведущий научный сотрудникВычислительного центра имени А.А.

ДородницынаРоссийской академии наукКукушкин Николай Серафимовичдоктор физико-математических наукпрофессор, заместитель заведующегокафедрой исследования операцийМосковского государственного университетаимени М.В. ЛомоносоваВасин Александр АлексеевичВедущая организация:Санкт-Петербургский экономико-математическийинститут Российской академии наукЗащита состоится 18 сентября 2014 г. в 1600 на заседании диссертационногосовета 212.048.09 при Национальном исследовательском университете «Высшаяшкола экономики» по адресу: 105187, г.

Москва, Кирпичная ул., д. 33, ауд. 503.С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики» по адресу: 101000, Москва,ул. Мясницкая, д.20 и на сайте http://www.hse.ru/sci/diss/.Автореферат разослан «» июля 2014 года.Ученый секретарьдиссертационного совета,доктор технических наукНазаров Станислав Викторович2Общая характеристика работыАктуальность темы. В практике часто возникает задача распределенияобъектов или людей в пары друг с другом. Примерами таких задач являютсяраспределение вакансий между работниками, формирование комитетов, распределение абитуриентов по вузам и др. Общим для таких задач является наличие двух групп объектов, которые необходимо поставить в пары друг с другом,причём не все пары разрешены (например, не каждый работник может занятьконкретную вакансию).

С 30-х гг. XX века в работах Д. Кенига, Ф. Холла и др.для решения указанных проблем было предложено использовать теорию графов.Задача формулируется как задача поиска паросочетания (множества несмежныхребер) максимальной мощности в двудольном графе.Однако во многих приложениях осуществляется распределение людейили организаций, обладающих предпочтениями относительно возможных пар, атакже свободой не соглашаться на предписанное распределение. В таком случаеэтих людей или организации можно рассматривать как игроков в теоретикоигровом смысле. Д. Гейлом и Л. Шепли в 1962 году была предложена теорияобобщенных паросочетаний, которая предполагает учёт предпочтений отдельных игроков при выборе распределения.

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

Эта модель имеет большое прикладное значение в задачахраспределения абитуриентов по вузам, учеников по школам и т.п. ВпоследствииД. Гейл, Э. Рот, Л. Дубинс, Д. Фридман, М. Сотомайор, Р. Ирвинг, Ч. Блэр, Д.Хатфильд, П. Милгром и другие исследовали различные аспекты данной задачи, предлагая разные подходы к моделированию предпочтений и определениюустойчивости. В теории обобщенных паросочетаний сложилась традиция использовать для именования групп игроков в моделях «один ко многим» названия«абитуриенты» и «вузы».

В то же время следует заметить, что модели являют-3ся по своей сути абстрактными, а результаты применимы к любым подобнымсистемам.В оригинальном исследовании Д. Гейла и Л. Шепли, а также в большинстве работ А. Рота, М. Сотомайор и др. принимается предположение о том,что предпочтения игроков заданы линейными порядками, иначе говоря, каждый игрок может строго упорядочить потенциальных партнеров по предпочтительности. В реальных приложениях предпочтения игрока часто основаны нанеточных измерениях (таких, как экзаменационные оценки, тесты, результатысобеседований) или недостаточной информации. В связи с этим представляется актуальным исследование моделей, в которых некоторые альтернативы могутбыть неразличимы для игрока по предпочтительности, т.е.

предпочтения игрокане могут быть представлены в виде линейного порядка. Проблема построенияустойчивого обобщенного паросочетания в случае, когда отношения предпочтения игроков являются слабыми порядками, т.е. антирефлексивными (∀ 1), транзитивными (∀, , : , верно, что ) и отрицательно тран-зитивными (∀, , : , верно, что ) бинарными отношениями,впервые поставлена в работе А. Рота, а затем развита в работах Р.

Ирвинга,предложившего модификацию определения устойчивого паросочетания, а такжев работах А. Аблукадироглу, Т. Сонмеза, П. Патака, Д. Манлова, А. Эрджила иХ. Эрдила в 2003-2009 гг.Для механизмов, разрабатываемых и внедряемых на пратике, особенно важно обеспечить неманипулируемость, т.е. отсутствие возможности у отдельного игрока улучшить результат своего распределения за счет сообщениянеистинных предпочтений.

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

Эхлерса показано,что не существует механизма построения устойчивого паросочетания, которыйбыл бы неманипулируем всеми игроками. Однако в прикладных задачах зача1Будем говорить, что если (, ) ∈/4стую достаточно обеспечить неманипулируемость для одной из групп игроков,а механизмы с таким свойством существуют.Целью данной работы является построение моделей обобщенных паросочетаний при предпочтениях, не являющихся линейными порядками.Для достижения поставленной цели были решены следующие задачи:1.

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

Разработан неманипулируемый устойчивый механизм, при использованиикоторого вероятность построения неэффективного паросочетания будут минимальна.5. Исследована модель обобщенных паросочетаний «один ко многим» припредпочтениях, основанных на балльных оценках. Для двух концепцийустойчивости: допускающей (L) и не допускающей (H) нарушения квоты вслучае равенства оценок, – доказано существование устойчивых паросочетаний и изучены свойства соответствующих устойчивых наборов граничных оценок.6.

Исследован механизм организации приемной кампании в России; показаны особенности и «узкие места» используемой псевдо-централизованнойсхемы.7. Разработан комплекс программ, реализующий предложенные механизмы.Научная новизна:51. Впервые исследована модель обобщенных паросочетаний с предпочтениями, заданными простейшими полупорядками.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»).62. Семинар Matching in Practice, Université Libre de Bruxelles, Брюссель, Бельгия, май 2013 г. (доклад: «Efficiency vs strategy-proofness for matching withinterval order preferences»).3. Общемосковский семинар «Экспертные оценки и анализ данных», ИПУРАН, Москва, март 2013 г.