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

• Автор: Кисельгоф, Софья Геннадьевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 186 с. : ил.

Содержание
Введение

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

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

свадьбах

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

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

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

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

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

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

1.3.2 Механизмы построения устойчивого паросочетания .
1.4 Анализ централизованных механизмов распределения, используемых на практике
1.4.1 Механизм распределения в терапевтическую интернатуру США
1.4.2 Прием в школы и детские сады

1.4.3 Централизованные схемы зачисления абитуриентов в вузы
1.4.4 Пересадка почек: обмен донорами
1.4.5 Провалы централизованных механизмов
2 Обобщенные паросочетания при предпочтениях, построенных на основе порогового выбора
2.1 Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками
2.1.1 Существование устойчивого паросочетания
2.1.2 Механизм отложенного принятия и паросочетания, неэффективные для абитуриентов
2.1.3 Устойчивые улучшающие циклы и построение эффективного для абитуриентов устойчивого паросочетания
2.2 Обобщенные паросочетания при предпочтениях, являющихся интервальными порядками
2.3 Неманипулируемый механизм со обратным устранением безразличий
2.4 Комплекс программ
2.5 Заключение по Главе
3 Прикладные аспекты задачи распределения абитуриентов по вузам
3.1 Граничные оценки и устойчивые паросочетания
3.1.1 Механизмы построения устойчивого набора граничных оценок
3.1.2 Два вида механизмов и эффективность паросочетания
3.1.3 Сравнение Н-устойчивости и Ь-устойчивости

3.1.4 Манипулирование предпочтениями
3.2 Моделирование приемной кампании в РФ
3.2.1 Организация приемной кампании в российских государственных вузах
3.2.2 Математическая модель
3.2.3 Поведение абитуриента в зависимости от уровня подготовки
3.2.4Моделирование приемной кампании
3.3 Заключение по Главе
Заключение
Литература
А Доказательство утверждений о выборе абитуриентов . . .160 В Исходные коды разработанного программного комплекса .
В.0.1 Устранение безразличий в предпочтениях агентов
В.0.2Генерация предпочтений случайным образом
В.О.ЗМодуль проверки эффективности паросочетания .

Xі С М и не может исказить свои предпочтения так, чтобы при новом профиле предпочтений нашлось паросочетание, которое строго лучше для всех манипулирующих, чем исходное.
Следствие І.5. Если при данных предпочтениях существует ровно одно устойчивое паросочетание, то при использовании механизма отложенного принятия сообщение истинных предпочтений является слабо доминирующей стратегией для любого игрока. Более того, никакая группа игроков не может исказить свои предпочтения таким образом, чтобы положение каждого из них улучшилось.
1.2 Обобщенные паросочетания один ко многим
В предыдущем разделе была рассмотрена задача о построении устойчивого паросочетания в случае, когда стороны рынка симметричны и каждый из игроков составляет пару с (максимум) одним игроком из другой подгруппы. Эту модель можно расширить, предположив, что некоторые игроки могут составлять пары сразу с несколькими игроками. Такая модель позволяет описать реальную структуру отношений в таких ситуациях, как сопоставление фирм (предлагающих несколько вакансий) и работников (желающих получить по одному месту работы), школ и учеников, вузов и абитуриентов и др.
Начиная с [2] сложилась традиция называть такую задачу задачей распределения абитуриентов по вузам. Будем придерживаться сложившейся системы обозначений и терминов, что в некоторых случаях значительно упростит изложение материала. В то же время следует заметить, что рассматриваемая модель является по своей сути абстрактной, а результаты применимы к любым подобным системам. Например,