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

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

КИСЕЛЬГОФ Софья Геннадьевна

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

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

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

2 4 ИЮЛ 2014

Москва — 2014

005550895

Работа выполнена в федеральном государственном автономном образовательном учреждении; высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики»

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

доктор технических наук, старший научный сотрудник

заведующий кафедрой высшей математики на факультете экономики Национального

исследовательского университета «Высшая школа экономики»

Алескеров Фуад Таги оглы

Официальные оппоненты: доктор физико-математических наук,

ведущий научный сотрудник

Вычислительного центра имени А.А, Дородницына

Российской академии наук Кукушкин Николай Серафимович

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

Ведущая организация:

Санкт-Петербургский экономико-математический институт Российской академии наук

Защита состоится 18 сентября 2014 г. в 16й0 на заседании диссертационного совета 212 048 09 при Национальном исследовательском университете «Высшая школа экономики» по адресу: 105187, г. Москва, Кирпичная ул., д. 33, ауд. 503.

С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики» по адресу: 101000, Москва,

ул. Мясницкая, д.20 и на сайте http://www.hse.ru/sci/diss/.

Автореферат разослан «_£_» июля 2014 года.

Ученый секретарь диссертационного совета, доктор технических наук

Назаров Станислав Викторович

Общая характеристика работы

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

ребер) максимальной мощности в двудольном графе.

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

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

В оригинальном исследовании Д. Гейла и Л. Шепли, а также в большинстве работ А. Рота, М. Сотомайор и др. принимается предположение о том, что предпочтения игроков заданы линейными порядками, иначе говоря, каждый игрок может строго упорядочить потенциальных партнеров по предпочтительности. В реальных приложениях предпочтения игрока часто основаны на неточных измерениях (таких, как экзаменационные оценки, тесты, результаты собеседований) или недостаточной информации. В связи с этим представляется актуальным исследование моделей, в которых некоторые альтернативы могут быть неразличимы для игрока по предпочтительности, т.е. предпочтения игрока не могут быть представлены в виде линейного порядка. Проблема построения устойчивого обобщенного паросочетания в случае, когда отношения предпочтения игроков Рг являются слабыми порядками, т.е. антирефлексивными (Ух хР£х '), транзитивными (Ух,у,г : хР^^Ргг верно, что хР^) и отрицательно транзитивными (Ух, у, г : хР£у,уР?г верно, что хР?г) бинарными отношениями, впервые поставлена в работе А. Рота, а затем развита в работах Р. Ирвинга, предложившего модификацию определения устойчивого паросочетания, а также в работах А. Аблукадироглу, Т. Сонмеза, П. Патака, Д. Манлова, А. Эрджила и X. Эрдила в 2003-2009 гг.

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

' Будем говорить, что т.Рсу если (х,у) <£ Р

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

а механизмы с таким свойством существуют.

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

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

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

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

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

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

нимальна.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание работы

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

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

В разделе 1.1 рассмотрены классические результаты для модели обобщенных паросочетаний «один к одному». Дано понятие устойчивого обобщенного паросочетания для модели «один к одному» и приведен предложенный Д. Гейлом и Л. Шепли механизм отложенного принятия, позволяющий построить устойчивое паросочетание. В рамках работы механизма игроки одной из групп делают предложения, а игроки другой группы рассматривают поступившие предложения и временно принимают наилучшее из них. Существуют две симметричные версии данного механизма, отличающиеся тем, какая группа игроков делает предложения и за счет этого имеет преимущество. Механизм строит устойчивое паросочетание, которое является наилучшим (оптимальным по Парето) среди всех устойчивых для предлагающей группы. Кроме того, при использовании механизма предлагающие игроки не заинтересованы в манипулировании, т.е. для каждого из игроков предлагающей группы слабо доминирующей стратегией является сообщение своих истинных предпочтений.

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

Обозначим через А конечное множество абитуриентов, а через В - конечное множество вузов. Каждый абитуриент может быть зачислен не более, чем в один вуз. Для каждого 6 € В установлена квота - это целое положительное число, равное максимальному числу абитуриентов а € А, которые могут быть зачислены в (поставлены в пару с) Ь.

Определение 1.9. Обобщенное паросочетание - это отображение

такое, что 2

1. ц(а) - {6} <=> а е /х(£>) (если абитуриент зачислен в вуз, то вуз зачислил этого абитуриента)

2. \/а <= А ц(а) = {Ь} или ^(а) = {а} (абитуриент либо зачислен в вуз, либо оставлен без места, т.е. поставлен в пару с самим собой)

3. € Я /х(Ь) С А или ц(Ь) = {Ь} (вуз либо зачислил подмножество абитуриентов, либо все места остались незаполненными)

4. \/Ь € В |м(Ь)| < Чь (число абитуриентов, зачисленных в Ь, не превышает его квоты дь)

Профиль предпочтений абитуриентов Р = (Раи ...,Ра|/4|) состоит из бинарных отношений, каждое из которых задано на множестве В и {а} и является линейным порядком. Это означает, что каждый абитуриент упорядочивает все вузы по предпочтительности поступления. Некоторые вузы могут оказаться менее предпочтительными, чем а («опция одиночества») т.е. обучение в таком вузе недопустимо для данного абитуриента. Профиль предпочтений вузов (>-Ьп ..., >-ь1В|) состоит из бинарных отношений, каждое из которых задано на множестве А и {Ь} и является линейным порядком. Это означает, что каждый вуз упорядочивает абитуриентов по предпочтительности зачисления, некоторые абитуриенты могут оказаться недопустимыми для данного вуза.

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

• индивидуально рациональным, т.е. ни один абитуриент не зачислен в недопустимый для себя вуз (Уа £ А верно, что аРасд(а)), а ни один вуз не зачислил недопустимого абитуриента (\/Ь £ В верно, что У а € ¡л(Ь) а >-ь Ь);

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

2Обозначим через 2'Лив> множество всех подможесгв Ли В

- ЬРац{а),а УЬ Ь, \ц{Ь)\ < дь (абитуриент а предпочитает вуз Ь по сравнению с тем, куда зачислен, а вуз считает абитуриента допустимым и имеет свободное место),

- ЬРац(а) и За' € ¡л(Ь) : а >-ь а' (абитуриент а предпочтитает вуз Ь по сравнению с тем, куда зачислен, а для вуза Ь абитуриент а предпочтительнее кого-то из уже зачисленных абитуриентов).

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

Для модели «один ко многим» особый интерес представляет проблема манипулирования. А. Рот показал, что в любом механизме, который строит устойчивое паросочетание, вузам (т.е. игрокам, которые могут получать более одной пары в обобщенном паросочетании) может быть выгодно искажать свои предпочтения на множестве абитуриентов. Кроме того, в работах Т. Сонмеза и Л. Эхлерса показано, что вузы в любых механизмах, строящих устойчивое паросочетание, также могут искажать свои квоты, гарантируя себе получение более предпочтительного, чем при сообщении истинной квоты, набора абитуриентов. Таким образом, не существует механизма, который строил был устойчивое паросочетание и при этом был бы неманипулируем вузами.

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

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

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

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

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

Дадим формальное определение простейшего полупорядка. Для этого нам потребуется дать определение полупорядка.

Определение 2.1. Бинарное отношение >- является полупорядком на А, если оно удовлетворяет условиям

• ацикличности,

• строгой интервальности (\/ж, у, г, т е А таких что х У у, г >- -ш верно, что

х У и> или г у у),

• полутранзитивности (\/х, у, г, ш 6 Л (х У у, у У г) х У ш или го >- г)).

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

Определение 2.2. Полупорядок >- является простейшим полупорядком, если он удовлетворяет

• слабой отрицательной транзитивности:

Ух,у 6 А (х У у) \{г : х1(у)г Л у1(у)г}\ < 1, т.е. существует не более одного элемента, находящегося в отношении безразличия одновременно и с х, и с у

• слабому условию различия срезов: Ух, у 6 А (>- х) ф (>- у) V (х >-) ^

(у>-).

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

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

Теорема 2.1.1. Если профили предпочтений абитуриентов Р и вузов > состоят из простейших полупорядков, то устойчивое паросочетание всегда существует.

Теорема 2.1.2. Для любого устойчивого паросочетания ¡л в модели с предпочтениями, заданными простейшими полупорядками, можно найти такой состоящий из линейных порядков профиль предпочтений вузов (где каждое отношение предпочтения >-'ь является линейным расширением отношения >ь). что паросочетание р, является устойчивым при этом профиле

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

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

Пусть C{b,fi) = {а € А : ЬРа/л(а)}, кроме того, пусть D(b,n) = {а € С{Ь,ц) &C(b,fj,) x>~cba}.

Определение 2.3. Устойчивый улучшающий цикл в паросочетании ц - это последовательность п различных абитуриентов а\, ...,ап = ао (п > 2) таких, что

1. /Li(ai) € В, т.е. каждый из них зачислен в вуз в паросочетании ¡х\

2. Vaj n{a,i+i) Рщ ¡л{сц), т.е. каждый предпочел бы учиться в вузе, в котором учится соседний абитуриент с большим номером;

3. Mai ai ^ D(fj.(ai+i), fï), т.е. среди всех абитуриентов, которые хотели бы учиться в вузе абитуриента Oj+i, абитуриент ы находится в группе наилучших.

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

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

Теорема 2.1.3. Пусть предпочтения вузов >; заданы простейшими полупорядками, а предпочтения абитуриентов Р - линейными порядками, и пусть ц - некоторое устойчивое паросочетание. Если ¡л доминируется по Парето (для абитуриентов) другим устойчивым паросочетанием, то существует устойчивый улучшающий цикл.

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

Определение 2.4. Бинарное отношение >-С А2 называется интервальным порядком на А, если оно

• антирефлексивно

• строго интервалыю (Vz, y,z,t€ А таких, что х >- у, z >- t верно, что х >- t или z > у)

Введем дополнительно функцию J : А —> R2, которая ставит в соответствие каждой альтернативе некоторый интервал. Бинарное отношение хС А2 является интервальным порядком, если и только если каждому элементу а € А можно поставить в соответствие интервал [i(a),u(a)], так, что а >- а' если и только если 1{а) > и(а').

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

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

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

Теорема 2.2.3. Для любого устойчивого паросочетания ц в модели с предпочтениями, заданными интервальными порядками, можно найти такой состоящий из линейных порядков профиль предпочтений вузов У' (где каждое отношение предпочтения >-'ь является линейным расширением отношения >~ъ), что паросочетание р является устойчивым при этом профиле

Теорема 2.2.4. Пусть предпочтения вузов h заданы интервальными порядками, а предпочтения абитуриентов Р - линейными порядками, и пусть р - некоторое устойчивое паросочетание. Если ц доминируется по Парето (для абитуриентов) другим устойчивым паросочетанием, то существует устойчивый улучшающий цикл.

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

15

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

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

В дальнейшем будем рассматривать некоторый вуз Ь, считая, что предпочтения остальных вузов и всех абитуриентов случайны. Пусть Ра, предпочтения абитуриента а - это дискретная случайная величина, равномерно распределенная на множестве всех линейных порядков, заданных наби{а}>у, предпочтения вуза Ь' - это дискретная случайная величина, равномерно распределенная на множестве всех простейших полупорядков, заданных на Аи{'Ь}. Распределения всех случайных величин независимы.

Теорема 2.3.1. Пусть профиль предпочтений абитуриентов Р состоит из линейных порядков, профиль предпочтений вузов У - из простейших полупорядков. Квота каждого вуза дь = 1. Тогда вероятность получения неэффективного для абитуриентов паросочетания при использовании механизма отложенного принятия с предлагающими абитуриентами будет наименьшей, если устранение безразличий проведено по следующей процедуре:

• Шаг 1. Рассматривается исходное отногиение предпочтения >ь и «лучшая» (т.е. состоящая из таких альтернатив, множество более пред-

почтительных элементов для которых пусто) максимальная антицепь 3 Л1={аь ..., а/.}. Пусть <ц >-{, а^, если (сц >-(,) С (а;- >-ь), т.е. Ог доминирует сц в новом преобразованном отношении предпочтения если множество альтернатив, доминируемых альтернативой сц строго входит во множество альтернатив, доминируемых альтернативой аВсе остальные безразличия между альтернативами во множестве устраняются произвольным образом.

• Шаг £ € [2, Т]. Рассматривается «лучшая» максимальная антицепь Аг во множестве А \ (и 1^}хАе). Повторяется процедура устранения предпочтений, описанная на шаге 1, для антицепи Шаги повторяются до тех пор, пока не будут исчерпаны элементы множества А.

• Шаг Т 4- 1. Для любых элементов а € Ап, а' £ Ат пусть а а', если п < т.

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

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

• генерировать профиль предпочтений, заданных полупорядками или загружать сформированный пользователем профиль предпочтений из файлов;

• строить линейные расширения отношений предпочтений со случайным устранением безразличий;

• строить линейные расширения отношений предпочтения с обратным устранением безразличий, предложенным в разделе 2.3;

3Антицепью в бинарном отношении >~С А2 называется подмножество А' е А, такое что любые две альтернативы в нем неразличимы между собой. Антицепь А! максимальна, если она не является подмножеством никакой другой антицепи.

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

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

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

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

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

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

Теоремы 3.1.4 и 3.1.5. Граничные оценки, рассчитанные Ь-устойчивым абитуриент-ориентированным (вуз-ориентированным) механизмом, всегда не выше, чем граничные оценки, рассчитанные Н-устойчивым абитуриент-ориентированным (вуз-ориентированным) механизмом, т.е. 1д<1д(1д< 1д)-

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

Следствие 3.1 Лучшие для абитуриентов Н-устойчивый и Ь-устойчивый наборы граничных оценок (1д и /д) являются, соответственно, верхним и нижним уровнями для граничных оценок в любом устойчивом паросочетании, построенном с помощью механизма отложенного принятия с предлагаюшими вузами с устранением безразличий в предпочтениях вузов. Аналогичное утверждение верно и для наборов граничных оценок, которые являются наихудшими для абитуриентов (Щ и 1д).

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

Анализ проведен для случая зачисления абитуриентов на одну специальность в разные вузы по результатам единого экзамена, поэтому предпочтения всех вузов считаются одинаковыми. Для моделирования выбора абитуриентов были сделаны некоторые предположения об их предпочтениях. Предполагается, что существует общеизвестное разбиение вузов на М + 1 категорию по качеству образования. Кроме того, сделаны предположения о квадратичной зависимости полезности поступления в вуз от разницы между качеством образования в вузе и уровнем подготовки абитуриента, а также об экспоненциальном падении оцениваемой абитуриентом вероятности быть зачисленным в вуз с ростом качества

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

В0 = 2'"* * (¿1 + 51)2 + (1 - 24"Л) * (2'-« * (¿2 + зг)2+ + (1 _ г1"») * (2{"а0'З + 5з)2 + (1 - 2<_Л) * (2^4 * 0'4 + ¿4)2+

где г - уровень подготовки абитуриента, - категория по качеству образования к-го из выбранных вузов, вк - оценка абитуриентом полезности от поступления в выбранный вуз (от 0 до 1, в сравнении с другими вузами той же категории по

качеству образования).

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

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

В заключении приведены основные результаты работы, которые состоят

в следующем:

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

20

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

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

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

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

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

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

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

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

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

а также:

3. Kiselgof S. G. College admissions with stable score - limits / Working papers by Hungarian Academy of Sciences. Series MT-DP «Discussion Papers of Hungarian Academy of Sciences». 2013. No. 6. 1,2 п.л. (в соавт. с Biro P., вклад автора 0,6 п.л.)

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

5. Kiselgof S.G. Malchings 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. 0,3 п.л.

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

Лицензия ЛР № 020832 от «15» октября 1993 г. Подписано в печать «5» О? 2014 г. Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1.

Тираж 100 экз. Заказ мЗрГипография издательства НИУ ВШЭ, 125319, г. Москва, Кочновский пр-д., д. 3.

\

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

ОБРАЗОВАНИЯ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ВЫСШАЯ ШКОЛА ЭКОНОМИКИ

На правах рукописи УДК ххх. ххх

04201460712

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

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

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

программ»

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

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

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

Москва - 2014

Содержание

Введение.............................. 5

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

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

свадьбах........................................................13

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

по вузам.............................104

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

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

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

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

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

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

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

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

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

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

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

Заключение...........\.................150

Литература.............................152

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а также:

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

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

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

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

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

Глава 1

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

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

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

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

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

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

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

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

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

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

о

ствами:

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

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

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

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