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

Программный комплекс позволяет:∙ генерировать профиль предпочтений, заданных полупорядками или загружать сформированный пользователем профиль предпочтений из файлов;∙ строить линейные расширения отношений предпочтений со случайнымустранением безразличий;∙ строить линейные расширения отношений предпочтения с обратным устранением безразличий, предложенным в разделе 2.3;3Антицепью в бинарном отношении ≻⊆ 2 называется подмножество ′ ∈ , такое что любые две аль-тернативы в нем неразличимы между собой.

Антицепь ′ максимальна, если она не является подмножествомникакой другой антицепи.17∙ находить устойчивое паросочетание при предпочтениях, заданных интервальными порядками с использованием двух версий механизма отложенного принятия;∙ с помощью предложенного в разделе 2.2 критерия проверять, является липостроенное устойчивое паросочетание Парето-эффективным с точки зрения предлагающей стороны.Третья глава посвящена изучению прикладных аспектов задачи распределения по вузам.В разделе 3.1 рассмотрена задача распределения абитуриентов по вузам,в которой предпочтения вузов основаны на оценках, полученных абитуриентами на вступительных испытаниях, а распределение абитуриентов организованона основе граничных оценок, устанавливаемых вузами.

Поскольку несколькоабитуриентов могут получить одинаковые оценки, предпочтения вузов на множестве абитуриентов заданы слабым порядком. При этом если на одно местов вузе претендует более одного абитуриента, причем все претенденты получили одинаковые оценки, то вуз не имеет дополнительных критериев для выбора.Предложено две концепции принятия решений вузом. H-концепция (от high, высокий) предполагает повышение граничной оценки таким образом, чтобы числопрошедших абитуриентов не превышало числа мест в вузе. L-концепция (от low,низкий) предполагает возможность зачисления последней группы абитуриентов,получивших одинаковые оценки, даже если это приводит к превышению числазачисленных абитуриентов над номинальным числом мест в вузе.Показана взаимосвязь между устойчивыми обобщенными паросочетаниями и устойчивыми наборами граничных оценок в случае H- и L-концепцийзачисления; предложены механизмы, аналогичные двум версиям механизма отложеннного принятия, позволяющие строить эффективные для абитуриентов идля вузов устойчивые наборы граничных оценок.Кроме того, показано, что L-концепция зачисления обеспечивает болеепредпочтительное для абитуриентов распределение за счет установления болеенизких граничных оценок как в случае абитуриент-ориентированного, так и вслучае вуз-ориентированного механизма построения устойчивого набора граничных оценок.18Теоремы 3.1.4 и 3.1.5.

Граничные оценки, рассчитанные L-устойчивымабитуриент-ориентированным (вуз-ориентированным) механизмом, всегда невыше, чем граничные оценки, рассчитанные H-устойчивым абитуриенториентированным (вуз-ориентированным) механизмом, т.е. ≤ ( ≤ ).Доказательства приведенных теорем дают также важное следствие, устанавливающее связь между системами, основанными исключительно на полученных абитуриентами оценках, и системами, использующими случайное устранение безразличий в предпочтениях.Следствие 3.1 Лучшие для абитуриентов H-устойчивый и L-устойчивыйнаборы граничных оценок (и ) являются, соответственно, верхним и ниж-ним уровнями для граничных оценок в любом устойчивом паросочетании, построенном с помощью механизма отложенного принятия с предлагаюшими вузами с устранением безразличий в предпочтениях вузов. Аналогичное утверждение верно и для наборов граничных оценок, которые являются наихудшими дляабитуриентов (и ).В разделе 3.2 проанализирован используемый в настоящее время в России псевдо-централизованный механизм распределения абитуриентов по вузам.В рамках указанного механизма каждый абитуриент подаёт заявления в пятьвузов, а затем проходят две волны зачисления, на которых устанавливаются промежуточные проходные баллы.

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

Кроме того, сделаны предположения о квадратичной зависимостиполезности поступления в вуз от разницы между качеством образования в вузеи уровнем подготовки абитуриента, а также об экспоненциальном падении оцениваемой абитуриентом вероятности быть зачисленным в вуз с ростом качества19образования в вузе. Итоговое выражение для ожидаемой полезности абитуриента , подавшего заявления в пять вузов, выглядит следующим образом: = 2−1 * (1 + 1 )2 + (1 − 2−1 ) * (2−2 * (2 + 2 )2 ++ (1 − 2−2 ) * (2−3 (3 + 3 )2 + (1 − 2−3 ) * (2−4 * (4 + 4 )2 ++ (1 − 2−4 ) * 2−5 * ((5 + 5 )2 ))),где - уровень подготовки абитуриента, - категория по качеству образования -го из выбранных вузов, - оценка абитуриентом полезности от поступленияв выбранный вуз (от 0 до 1, в сравнении с другими вузами той же категории покачеству образования).Решена оптимизационная задача и показано, какие вузы абитуриенты будут выбирать для подачи заявлений.

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

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

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

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

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

Исследован механизм организации приемной кампании в России; показаны особенности и «узкие места» используемой псевдо-централизованнойсхемы. В частности, продемонстрировано, что механизм может порождатьнеустойчивое паросочетание.6. Разработан комплекс программ, реализующий предложенные механизмыпостроения устойчивого обобшенного паросочетания.Основные результаты по теме диссертации изложены в 6 печатных изданиях, 2 из которых изданы в журналах, рекомендованных ВАК:211. Кисельгоф С.Г. Обобщенные паросочетания при предпочтениях, являющихся простейшими полупорядками: стабильность и оптимальность по Парето // Автоматика и телемеханика. 2014. №6.

С. 103-114. 0,8 п.л.2. Кисельгоф С.Г. Моделирование приемной кампании: вузы различного качества и абитуриенты с квадратичной функцией полезности // Проблемыуправления. 2012. № 5. С. 33-40. 0,7 п.л.а также:3. Kiselgof S. G. College admissions with stable score - limits / Working papersby Hungarian Academy of Sciences. Series MT-DP «Discussion Papers ofHungarian Academy of Sciences». 2013. No. 6.

1,2 п.л. (в соавт. с Biro P.,вклад автора 0,6 п.л.)4. Кисельгоф С.Г. Модель выбора вузов абитуриентами приемной кампаниив России // В кн.: XII Международная научная конференция по проблемамразвития экономики и общества. В четырех книгах. Книга 2. / Отв. ред.: Е.Г. Ясин. . Кн. 2.