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

Содержание к диссертации

Введение

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 Сравнение H-устойчивости и L-устойчивости 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

• Сообщение предпочтений и манипулирование при построении обобщённых паросочатений
• Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками
• Два вида механизмов и эффективность паросочетания
• Моделирование приемной кампании

Введение к работе

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

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

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

В оригинальном исследовании Д. Гейла и Л. Шепли, а также в большинстве работ А. Рота, М. Сотомайор и др. принимается предположение о том, что предпочтения игроков заданы линейными порядками, иначе говоря, каждый игрок может строго упорядочить потенциальных партнеров по предпочтительности. В реальных приложениях предпочтения игрока часто основаны на неточных измерениях (таких, как экзаменационные оценки, тесты, результаты собеседований) или недостаточной информации. В связи с этим представляется актуальным исследование моделей, в которых некоторые альтернативы могут быть неразличимы для игрока по предпочтительности, т.е. предпочтения игрока не могут быть представлены в виде линейного порядка. Проблема построения устойчивого обобщенного паросочетания в случае, когда отношения предпочтения игроков Pi являются слабыми порядками, т.е. антирефлексивными (Ух xPfx ), транзитивными (Vx,y,z : xPj,y,yPiZ верно, что xP{Z) и отрицательно транзитивными (Vx,y,z : хР?у,уР![Х верно, что xPfz) бинарными отношениями, впервые поставлена в работе А. Рота, а затем развита в работах Р. Ирвинга, предложившего модификацию определения устойчивого паросочетания, а также в работах А. Аблукадироглу, Т. Сонмеза, П. Патака, Д. Манлова, А. Эрджила и Х. Эрдила в 2003-2009 гг.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, этот пример показывает, что

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

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

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

Теорема 1.1.8. [8] Пусть заданы М и W и профиль предпочтений Р. Если некоторое подмножество X = М J W заменило в про филе предпочтений свои истинные предпочтения на искаженные Р х,, то для любого паросочетания //, устойчивого при новом профиле предпочтений Р , найдутся паросочетание \±, устойчивое при истинных предпочтениях Р, и х є Xі, такие что (і (х)Р (і(х).

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

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

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

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

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

Пусть А - множество абитуриентов, В - множество вузов. Множества абитуриентов и вузов конечны. Будем обозначать через а элементы множества абитуриентов, а через Ь - элементы множества вузов. Каждый абитуриент может быть зачислен не более, чем в один вуз, а каждый вуз Ь имеет дь мест.

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

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

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

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

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

строгой интервальности: Ух y,z У-1 = х У-1 или z У- у.

полутранзитивности: Vx,y,z,w EA(x y,y z)= x w или w У- z).

Как и главе 1, будем говорить, что х с у, если (ж, у) -.

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

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

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

Уж, у Є А (х у) = \{z : xl( )z Л yl( )z}\ 1, т.е. существует не более одного элемента, находящегося в отношении безразличия одновременно и с х, и с у слабому многообразию контуров: Уж, у (V х) Ф (V у) V (х -) т (у -).

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

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

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

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

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

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

Будем говорить, что набор граничных оценок / предпочтительнее для абитуриентов, чем I , если / I , т.е., если l{bu) l (bu) для каждого вуза Ьи. В этом случае каждый абитуриент при / получает место в том же или более предпочтительном вузе по сравнению с / . Это отношение является, по сути, отношением Парето между соответствующими паросочетаниями при учёте предпочтений всех абитуриентов.

Теорема 3.1.2. Щ является худшим (по отношению Парето) для абитуриентов, а 1д - Парето-эффективным для абитуриентов H-устойчивым набором граничных оценок, т.е. для любого устойчивого набора граничных оценок I выполняется 1д 1 Щ.

Доказательство. Предположим противное: пусть существует Н-устойчивый набор I и вуз Ьи такие, что U(bu) Щ(Ъи). При выполнении вуз-ориентированного механизма обязательно найдутся два последовательных шага, k-ът и к + 1-ый, и соответствующие им наборы граничных оценок Ik и lk+і, такие что U h и h(bu) lk+i(bu) для некоторого вуза Ьи.

Очевидно, что ll tu(bu) = h+i(bu) по определению. Также, %u(ll tu) Яи хи(1 ) Первое неравенство выполнено по определению tu, поскольку мы выбираем новую граничную оценку в вузе Ьи таким образом, чтобы число временно зачисленных в этот вуз абитуриентов не превышало квоту. Второе неравенство выполняется в силу Н-устойчивости U. Следовательно, обязательно найдется абитуриент, назовем его а\, который зачислен в вуз Ьи (имеет оценку не ниже граничной и предпочитает этот вуз другим) при С , но не зачислен в вуз Ъи при Гк 1и.

С другой стороны, по предположению выше Гк и(Ъу) = lk+l(bu) h(bu) — 1 = С (bu). Абитуриент d\ получил оценку не ниже 1 и(Ьи) в вузе Ьи, чего достаточно для того, чтобы быть принятым в Ьи, поэтому для того, чтобы набор был устойчивым, при ll tu(bu) абитуриент аг должен быть зачислен в вуз bv, более предпочтительный, чем Ьи. Очевидно, что а\ должен быть также зачислен в bv при 4. Но из Н-устойчивости U следует, что U(bv) h(bv), что противоречит предположению о том, что U 1к Вторую часть двойного неравенства докажем также от противно го. Пусть существуют Н-устойчивый набор граничных оценок U и вуз Ъи такие, что l (bu) 1д(Ьи). Тогда при выполнении абитуриент ориентированного механизма обязательно найдутся два следующих друг за другом шага с временными наборами граничных оценок 4 and 4+ь такие что 4 4 и l (bu) lk+i(bu) для некоторого вуза Ъи. На этом шаге причина повышения граничной оценки состоит в том, что как минимум qu абитуриентов с оценками не ниже l (bu) пода ли заявления в Ьи. Из этого следует, что как минимум один из этих абитуриентов, назовем его а , не зачислен в Ьи при 4 (но его оцен ка в этом вузе - как минимум U(bu)). Из Н-устойчивости 4 следует, что абитуриент а при наборе граничных оценок 4 должен быть за числен в некоторый вуз bv, который предпочтительнее для этого аби туриента, чем Ъи. Т.к. рассматривается абитуриент-ориентированный механизм, абитуриент а должен был получить отказ в вузе bv на предыдущих (до к-го) шагах механизма. Это возможно, только если l (bv) h(bv), что противоречит сделанному выше предположению о том, что 4 4-

Теорема 3.1.3. / является худшим (по отношению Парето) для абитуриентов, а \\ - Парето-эффективным для абитуриентов L-устойчивым набором граничных оценок, т.е. для любого L-устойчивого набора граничных оценок I выполнено 1\ 1 1\.

Доказательство. Сначала докажем, что построенное в результате вуз-ориентированного механизма паросочетание является наихудшим для абитуриентов. Предположим противное: пусть существуют набор граничных оценок / и вуз Ьи такой что l (bu) 1в(Ьи). При выполнении вуз-ориентированного механизма найдутся два последовательных шага 4 и lk+і, такие что 4 и h(bu) h+i(bu) для некоторого вуза Ъи.

Из сделанного предположения следует, что xu(ll tu+ ) qu хи(1 ). Первое неравенство выполнено из-за L-допустимости lk+і, а второе неравенство - из-за L-устойчивости / . В то же время, по нашему предположению, l (bu) h+i(bu), таким образом l (bu) h+i(bu) + 1 = Ik " {К) Из этих двух утверждений следует, что существует абитуриент, назовем его 2ь который имеет оценку slu U(bu) в вузе с(и), зачислен в вуз Ьи при / , но не зачислен в Ьи при - «+!_ Значит, при L " абитуриент аг должен быть зачислен в некоторый вуз bv, который для него предпочтительнее, чем с(и), т.е. bvPaibu. Очевидно, что а\ также должен быть зачислен в bv при наборе граничных оценок /&. Но а\ не зачислен в bv при / , следовательно h(bv) h(bv), противоречие. Чтобы доказать вторую часть утверждения теоремы, предположим, что существуют устойчивый набор граничных оценок I и вуз bw такие, что ЦЬт) lLA{bw). При выполнении абитуриент-ориентированного ме 115 ханизма должны обязательно найтись два следующих друг за другом шага с временными (L-допустимыми) наборами граничных оценок 1к и 4+ь такие что I 4 и l {bu) lk+i{bu) для некоторого вуза Ъи. При переходе на к + 1 шаг причина повышения граничной оценки в вузе Ьи состоит в том, что как минимум qu абитуриентов с оценками не ниже U(u) у каждого подали заявления в Ьи, и Ьи может назначить более высокую граничную оценку lk+i(bu) = lt tu(bu), где tu h(bu) — h(bu), отвергнув таким образом последнюю группу абитуриентов с одинаковыми оценками. Это означает, что один из абитуриентов, зачисленных в Ъи при 1к+\, назовем его а 2, не зачислен в Ьи при / . Но его оценка в этом вузе не ниже граничной оценки ЦЬи). Значит, в силу L-устойчивости /,, при этом наборе граничных оценок абитуриент а должен получить место в более предпочтительном вузе bv. Раз этот вуз более предпочтителен для абитуриента, то при выполнении абитуриент-ориентированного механизма а должен был быть отвергнут этим вузом до шага к. В силу этого h(bv) h(bv), противоречие.

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

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

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

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

количество абитуриентов разного уровня подготовленности.

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

Обозначим через г число заявлений, которые получает вуз из группы Bj от абитуриентов категории А{. В силу способа моделирования предпочтений абитуриентов очевидно, что Vi, j : і j имеет место r = 0. Таким образом, абитуриенты не подают заявление в вузы более слабых категорий, следовательно, вуз не имеет возможности получить абитуриента из категории с номером выше, чем его собственная. Обозначим через s1j число абитуриентов категории А{, рекомендованных в вуз группы Bj на первом этапе, а через s2j - число рекомендованных на втором этапе.

Наконец, обозначим через t13 число абитуриентов категории Аг, принесших подлинники документа о среднем образовании и считающихся зачисленными в вуз группы Bj на первом этапе, а через t2j - аналогичную величину к концу второго этапа.

Равномерное распределение абитуриентов. Числовой пример.

Рассмотрим следующий пример.

M = 10, то есть 10 категорий абитуриентов и 11 категорий вузов,

n = 20, число вузов в категории,

Число абитуриентов совпадает с числом мест в вузах,

Абитуриенты распределены по категориям равномерно.

Общее число вузов будет равно 20 11 = 220, а мест - 220 L. Абитуриенты распределены по категориям равномерно, поэтому УІ\АІ\ =

10 = 22L. На первом этапе каждый абитуриент категорий 2 і 8 подаст заявление в вуз своей категории, в два вуза категории В{+2 и два вуза категории Д+3. Абитуриенты из двух верхних категорий, в принципе не имеющие категории вузов Д+3, также сделают выбор, максимизирующий их ожидаемую полезность. Для абитуриента из лучшей категории A10 набор будет включать вуз своей категории и четыре вуза категории Вп. Для абитуриента из категории А9 набор будет включать один вуз своей категории, один вуз категории ю и три вуза категории ВЦ. Для абитуриента из группы А\ наилучшим будет выбор, не включающий гарантированный вуз: один вуз из В2, два вуза из з и два вуза из В .

Подача заявлений Какой же набор заявлений получит каждый вуз? Во-первых, число заявлений от абитуриентов собственной категории равно числу абитуриентов, считающих вуз лучшим . Поскольку число абитуриентов, считающих данный вуз лучшим в своей категории, одинаково для любого вуза, то общее число таких заявлений будет Vi, 7 : і = 7 1 І = 4k = І.ІЬ. Вузы категории Вл в нашей моде-ли не получают ни одного заявления. Значения остальных г у можно легко вычислить исходя из описанного выше поведения студентов. Матрица R будет выглядеть следующим образом:

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

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

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