Помощь студентам в учебе
Ситуации равновесия в задачах о назначениях
|
Введение 5
1. Описание системы ЕГЭ 8
1.1. Постановка задачи 8
1.2. Текущие правила поступления по ЕГЭ 8
1.3. Реальные проявления несовершенств системы поступления на примере приемной кампании в СПбГУ 11
2. Алгоритмы 15
2.1. Трактовка текущих правил поступления по ЕГЭ для сравнения работы различных алгоритмов поступления в вузы 15
2.1.1. Алгоритм распределения абитуриентов по вузам по текущим правилам поступления с помощью математического ожидания в одну волну 15
2.1.2. Алгоритм поступления в две волны по правилу математического ожидания 18
2.1.3. Алгоритм поступления в три волны по правилу математического ожидания 20
2.1.4. Принцип выбора kj (qj) 20
2.2. Другие алгоритмы поступления абитуриентов в вузы 23
2.2.1. Алгоритм Гейла-Шепли 23
2.2.2. Алгоритм поступления в одну волну с одним приоритетом 25
3. Исследование результатов 26
3.1. Результаты при одинаковых квотах у вузов 26
3.1.1. Абитуриентов в два раза больше, чем суммарная квота во всех вузах 26
3.1.2. Абитуриентов столько же, сколько суммарная квота во всех вузах 28
3.2. Результаты при разных квотах у вузов 30
3.2.1. Абитуриентов в два раза больше, чем суммарная квота во всех вузах 30
3.2.2. Абитуриентов столько же, сколько суммарная квота во всех вузах 32
Заключение 35
Список литературы 37
Приложение 39
1. Описание системы ЕГЭ 8
1.1. Постановка задачи 8
1.2. Текущие правила поступления по ЕГЭ 8
1.3. Реальные проявления несовершенств системы поступления на примере приемной кампании в СПбГУ 11
2. Алгоритмы 15
2.1. Трактовка текущих правил поступления по ЕГЭ для сравнения работы различных алгоритмов поступления в вузы 15
2.1.1. Алгоритм распределения абитуриентов по вузам по текущим правилам поступления с помощью математического ожидания в одну волну 15
2.1.2. Алгоритм поступления в две волны по правилу математического ожидания 18
2.1.3. Алгоритм поступления в три волны по правилу математического ожидания 20
2.1.4. Принцип выбора kj (qj) 20
2.2. Другие алгоритмы поступления абитуриентов в вузы 23
2.2.1. Алгоритм Гейла-Шепли 23
2.2.2. Алгоритм поступления в одну волну с одним приоритетом 25
3. Исследование результатов 26
3.1. Результаты при одинаковых квотах у вузов 26
3.1.1. Абитуриентов в два раза больше, чем суммарная квота во всех вузах 26
3.1.2. Абитуриентов столько же, сколько суммарная квота во всех вузах 28
3.2. Результаты при разных квотах у вузов 30
3.2.1. Абитуриентов в два раза больше, чем суммарная квота во всех вузах 30
3.2.2. Абитуриентов столько же, сколько суммарная квота во всех вузах 32
Заключение 35
Список литературы 37
Приложение 39
В данной работе будут рассматриваться различные модели приема абитуриентов в вузы. Начиная с 2009 года, система приема абитуриентов в вузы в Российской Федерации изменилась: абитуриенты стали поступать в вузы по результатам ЕГЭ, при этом каждый абитуриент имеет право подать документы в несколько вузов, причем прием осуществляется в несколько волн: например, в 2011 поступление производилось в три волны, но с 2012 поступление в большинство вузов стало происходить в две волны. Однако до сих пор в ряде вузов существует приемные кампании в одну волну, например, поступление в магистратуру в СПбГУ [15].
Существуют и другие модели распределения абитуриентов по вузам. Например, в советские времена при обязательном распределении выпускников по организациям, подавшим свои заявки, использовался следующий алгоритм [3]: все выпускники ранжировались по среднему баллу зачетной книжки и, в порядке убывания среднего балла, выбирали по очереди наиболее предпочтительную организацию среди тех, в которых еще остались свободные места (считалось, что каждый выпускник имеет свое линейное упорядочение на множестве всех организаций). В действительности, этот алгоритм являлся модернизированным алгоритмом Гейла-Шепли в задаче о назначении [9], который можно применять для задачи распределения абитуриентов по вузам.
В 1962 году Дэвид Гейл и Ллойд Шепли предложили алгоритм распределения мужчин и женщин на брачные пары [10]. Этот алгоритм всегда давал устойчивое распределение в том смысле, что не находилось никакой пары, которая, разорвав свои союзы, образовывала бы новую пару, в которой оба партнера были более счастливыми. Алгоритм нахождения устойчивых паросочетаний, помимо задачи распределения выпускников по организациям, применяется в задаче выбора соседей по комнате, распределении донорских органов по реципиентам и в других задачах. В дальнейшем за решение таких задач о назначениях Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике 2012 года [1, 6].
Модернизированный алгоритм Гейла-Шепли можно также применять для случая, когда выпускники соответствуют абитуриентам, а организации — вузам [12, 13]. Поскольку истинное качество абитуриентов неизвестно, то вуз имеет предпочтение только в соответствии с формируемым вузом рейтингом, который получается благодаря результатам ЕГЭ и вступительным экзаменам, если они есть. Таким образом, вуз заинтересован в абитуриентах, находящихся как можно выше в рейтинге. При выполнении алгоритма Гейла-Шепли образуются устойчивые пары [10]: если поступивший в некоторый вуз абитуриент мечтал о другом вузе больше, чем о том, в который поступил, то другой вуз предпочтет абитуриента, находящегося выше в рейтинге, и наоборот, если среди непоступивших в некоторый вуз есть абитуриенты, находящиеся выше в общем рейтинге, чем последний поступивший в этот вуз, то они предпочитают другой вуз, а этого вуза нет списке приемлемых для рассматриваемых абитуриентов. Кроме того, эта процедура устойчива относительно манипулирования (никто не получает выгоды от искажения своих истинных предпочтений [2, 11]). К сожалению, в России данная процедура поступления не используется ввиду ее сложности и недостатка матобеспечения.
Для остальных описанных правил возможны варианты неустойчивости результатов приема [2, 11, 7, 8]: могут быть ситуации, когда место в более приоритетном для некоторого абитуриента вузе может быть занято другим абитуриентом, находящимся в рейтинге ниже, то есть не будет соблюдаться условие истинной устойчивости, но эти правила приема абитуриентов в вузы применяются в Российской Федерации, а алгоритм Гейла-Шепли — нет.
Цель работы состоит в исследовании различных правил распределения абитуриентов по вузам, а также в разработке квазиоптимальных стратегий поведения абитуриентов. В данной работе эталонным считается распределение по модернизированному алгоритму Гейла-Шепли, и сравнение результатов работы других алгоритмов будет производиться с ним.
Предлагается оценивать результаты рассматриваемых алгоритмов по количеству неустойчивых пар вида университет-абитуриент (то есть сравнение с результатами алгоритма Гейла-Шепли путем пересчета отличающихся пар), а также по номеру последних поступивших абитуриентов в каждый вуз или по среднеарифметическому количеству заполненных мест в каждом вузе (в зависимости от начальных данных модели). Для сравнения производится имитационное моделирование всех этих алгоритмов, начиная с построения предпочтений абитуриентов на множестве вузов, затем происходит применение каждого алгоритма к текущему построению, в конце — сравнение с алгоритмом Гейла-Шепли и получение статистических данных для различных начальных условий модели.
Существуют и другие модели распределения абитуриентов по вузам. Например, в советские времена при обязательном распределении выпускников по организациям, подавшим свои заявки, использовался следующий алгоритм [3]: все выпускники ранжировались по среднему баллу зачетной книжки и, в порядке убывания среднего балла, выбирали по очереди наиболее предпочтительную организацию среди тех, в которых еще остались свободные места (считалось, что каждый выпускник имеет свое линейное упорядочение на множестве всех организаций). В действительности, этот алгоритм являлся модернизированным алгоритмом Гейла-Шепли в задаче о назначении [9], который можно применять для задачи распределения абитуриентов по вузам.
В 1962 году Дэвид Гейл и Ллойд Шепли предложили алгоритм распределения мужчин и женщин на брачные пары [10]. Этот алгоритм всегда давал устойчивое распределение в том смысле, что не находилось никакой пары, которая, разорвав свои союзы, образовывала бы новую пару, в которой оба партнера были более счастливыми. Алгоритм нахождения устойчивых паросочетаний, помимо задачи распределения выпускников по организациям, применяется в задаче выбора соседей по комнате, распределении донорских органов по реципиентам и в других задачах. В дальнейшем за решение таких задач о назначениях Ллойд Шепли и Элвин Рот получили Нобелевскую премию по экономике 2012 года [1, 6].
Модернизированный алгоритм Гейла-Шепли можно также применять для случая, когда выпускники соответствуют абитуриентам, а организации — вузам [12, 13]. Поскольку истинное качество абитуриентов неизвестно, то вуз имеет предпочтение только в соответствии с формируемым вузом рейтингом, который получается благодаря результатам ЕГЭ и вступительным экзаменам, если они есть. Таким образом, вуз заинтересован в абитуриентах, находящихся как можно выше в рейтинге. При выполнении алгоритма Гейла-Шепли образуются устойчивые пары [10]: если поступивший в некоторый вуз абитуриент мечтал о другом вузе больше, чем о том, в который поступил, то другой вуз предпочтет абитуриента, находящегося выше в рейтинге, и наоборот, если среди непоступивших в некоторый вуз есть абитуриенты, находящиеся выше в общем рейтинге, чем последний поступивший в этот вуз, то они предпочитают другой вуз, а этого вуза нет списке приемлемых для рассматриваемых абитуриентов. Кроме того, эта процедура устойчива относительно манипулирования (никто не получает выгоды от искажения своих истинных предпочтений [2, 11]). К сожалению, в России данная процедура поступления не используется ввиду ее сложности и недостатка матобеспечения.
Для остальных описанных правил возможны варианты неустойчивости результатов приема [2, 11, 7, 8]: могут быть ситуации, когда место в более приоритетном для некоторого абитуриента вузе может быть занято другим абитуриентом, находящимся в рейтинге ниже, то есть не будет соблюдаться условие истинной устойчивости, но эти правила приема абитуриентов в вузы применяются в Российской Федерации, а алгоритм Гейла-Шепли — нет.
Цель работы состоит в исследовании различных правил распределения абитуриентов по вузам, а также в разработке квазиоптимальных стратегий поведения абитуриентов. В данной работе эталонным считается распределение по модернизированному алгоритму Гейла-Шепли, и сравнение результатов работы других алгоритмов будет производиться с ним.
Предлагается оценивать результаты рассматриваемых алгоритмов по количеству неустойчивых пар вида университет-абитуриент (то есть сравнение с результатами алгоритма Гейла-Шепли путем пересчета отличающихся пар), а также по номеру последних поступивших абитуриентов в каждый вуз или по среднеарифметическому количеству заполненных мест в каждом вузе (в зависимости от начальных данных модели). Для сравнения производится имитационное моделирование всех этих алгоритмов, начиная с построения предпочтений абитуриентов на множестве вузов, затем происходит применение каждого алгоритма к текущему построению, в конце — сравнение с алгоритмом Гейла-Шепли и получение статистических данных для различных начальных условий модели.
В данной работе были рассмотрены различные алгоритмы распределения абитуриентов по вузам, а также проведено сравнение с эталонным — алгоритмом Гэйла-Шепли. Разработан новый алгоритм поведения абитуриентов, который дает приемлемые результаты при некоторых параметрах.
Исходя из полученных результатов, сделаны следующие выводы:
1. При моделировании различных вариантов приемной кампании (количество квот, абитуриентов) наиболее близким по результатам к алгоритму Гейла-Шепли во всех случаях является алгоритм поступления по правилу математического ожидания с А = S — 1.
2. Нельзя определенно сказать, какое количество волн является наиболее оптимальным. Чем больше волн, тем среднеарифметический номер последнего поступившего абитуриента меньше, однако количество неустойчивых пар меньше при поступлении в одну волну. Поступление в три волны не дает значительного преимущества по сравнению с поступлением в одну и две волны, поэтому отказ от приема в три волны в РФ можно считать правильным, ввиду сложности и необходимости дополнительных расходов на проведение дополнительной волны.
3. Стратегии абитуриентов с небольшой степенью степенью риска (А = (S-1)/2, А = (v-1)/v) ведут к неприемлемому результату как для абитуриентов (поступление в вузы, которые не являются наиболее приоритетными, а поступление по принципу хотя бы куда-нибудь из множества приемлемых вузов), так и для вузов (высокое среднеарифметическое места последнего поступившего абитуриента по сравнению с алгоритмом Гейла-Шепли, как следствие — сильно различающийся уровень абитуриентов).
4. Однако и стратегии с высокой степенью риска (поступление в одну волну с одним приоритетом) неприемлемы. Данный алгоритм является частным случаем модифицированного алгоритма Гейла- Шепли, где абитуриенты хотят поступить только в один вуз. Оба алгоритма моделировались на одинаковых данных, однако полученные результаты у алгоритма Гейла-Шепли существенно лучше.
Исходя из полученных результатов, сделаны следующие выводы:
1. При моделировании различных вариантов приемной кампании (количество квот, абитуриентов) наиболее близким по результатам к алгоритму Гейла-Шепли во всех случаях является алгоритм поступления по правилу математического ожидания с А = S — 1.
2. Нельзя определенно сказать, какое количество волн является наиболее оптимальным. Чем больше волн, тем среднеарифметический номер последнего поступившего абитуриента меньше, однако количество неустойчивых пар меньше при поступлении в одну волну. Поступление в три волны не дает значительного преимущества по сравнению с поступлением в одну и две волны, поэтому отказ от приема в три волны в РФ можно считать правильным, ввиду сложности и необходимости дополнительных расходов на проведение дополнительной волны.
3. Стратегии абитуриентов с небольшой степенью степенью риска (А = (S-1)/2, А = (v-1)/v) ведут к неприемлемому результату как для абитуриентов (поступление в вузы, которые не являются наиболее приоритетными, а поступление по принципу хотя бы куда-нибудь из множества приемлемых вузов), так и для вузов (высокое среднеарифметическое места последнего поступившего абитуриента по сравнению с алгоритмом Гейла-Шепли, как следствие — сильно различающийся уровень абитуриентов).
4. Однако и стратегии с высокой степенью риска (поступление в одну волну с одним приоритетом) неприемлемы. Данный алгоритм является частным случаем модифицированного алгоритма Гейла- Шепли, где абитуриенты хотят поступить только в один вуз. Оба алгоритма моделировались на одинаковых данных, однако полученные результаты у алгоритма Гейла-Шепли существенно лучше.
