Диссертация (1137447), страница 17
Текст из файла (страница 17)
.Доказательство. Часть I. Рассмотрим набор граничных оценок Заметим, что в некоторые (не обязательно все) вузы может быть зачислено больше абитуриентов, чем установленная квота, () > .Устраним безразличия в предпочтениях вузов случайным образом.Каждый абитуриент получает новую оценку ≥ в каждом вузе. Внутри вуза никакие два студента не имеют одинаковых новыхоценок. Кроме того, новые оценки основаны на исходных, т.е.
если < , то < ≤ . Оценки являются положительными действительными числами.После этого организуется следующая процедура. На первом шагекаждый вуз устанавливает новую граничную оценку ( ) ≥ ( )такую, что в соответствии с новыми оценками абитуриентов количество абитуриентов, имеющих (новую) оценку не ниже граничной,будет в точности равно . Новый набор граничных оценок ставитв соответствие каждому вузу неотрицательное действительное чис120ло.
Граничная оценка ( ) равна 0, если число зачисленных в вуз абитуриентов меньше квоты ; в противном случае ( ) равнонаименьшей новой оценке среди зачисленных в вуз абитуриентов.Некоторые абитуриенты в результате описанной выше процедурымогли остаться без места, которое им было выделено при наборе граничных оценок . Каждый отвергнутый абитуриент в таком случаеподаёт заявление в следующий по предпочтительности (после отвергнувшего) вуз. Bузы получают новые заявления и, если это необходимо, повышают граничную оценку так, чтобы число заявлений отабитуриентов с оценкой не ниже установленной границы в точностиравнялось числу мест.
После повышения граничных оценок какие-тоабитуриенты могут потерять место в вузе. Шаги механизма повторяются до тех пор, пока граничные оценки не окажутся зафиксированными во всех вузах. Заметим, что фактически выполняется механизмотложенного принятия с предлагающими абитуриентами. В конечномитоге будут получены новые граничные оценки , удовлетворяющиеусловию ≥ по построению.
Эта система граничных оценок и со-ответствующее ей паросочетание устойчивы в классическом смысле.Часть II. Для построенного ранее набора оценок абитуриентов исоответствующего ему профиля предпочтений вузов, заданных линейными порядками, можно выполнить механизм отложенного принятияс предлагающими вузами. Будет получено новое паросочетание и соответствующий ему набор граничных оценок , которые, разумеется,будут устойчивы.
Более этого, эти граничные оценки должны бытьминимальными среди всех граничных оценок, возможных в устойчивых паросочетаниях [2], так что ≥ .121Часть III. Теперь будем отталкиваться от набора граничных оценок . Для каждого вуза , верно , что ( ) ≤ при . В любомвузе граничная оценка равна нулю ( ( ) = 0), если количествозачисленных меньше квоты. Теперь вернёмся к исходных оценкам,полученным абитуриентами: .Из имеющегося (соответствующего набору граничных оценок )паросочетания построим H-допустимое паросочетание. Для этого организуем следующую процедуру типа отложенного принятия. На первом шаге каждый вуз устанавливает свою новую граничную оценку( ) ≥ ( ) так, чтобы в вуз, в соответствии с исходными оцен-ками проходило не больше абитуриентов, чем квота вуза (в точности в соответствии с определением H-допустимости).
Таким образом,некоторые абитуриенты могут получить отказ в вузе, куда ранее онибыли зачислены. Каждый отвергнутый абитуриент подает заявлениев вуз, следующий в его списке предпочтений за отвергнувшим. Вузыполучают новые заявления и, при необходимости, повышают граничные оценки так, чтобы число заявлений от абитуриентов с оценкойвыше граничной не превышало квоту этого вуза. Шаг повторяется дотех пор, пока не наступит ситуация, в которой ни один вуз не захочетповышать граничную оценку. Полученный набор граничных оценок удовлетворяет условию ≥ по построению. Этот новый наборграничных оценок является H-допустимым и H-устойчивым.Часть IV. Для любого H-устойчивого набора граничных оценок по теореме 3.1.2 известно, что ≥ , где - это H-устойчивыйнабор граничных оценок, который можно построить с помощью механизма, ориентированного на вузы.122Из частей I-IV доказательства получаем неравенства ≤ ≤≤ .
Можно сделать вывод о том, что при любых пред ≤ почтениях вузов и абитуриентов L-устойчивый вуз-ориентированныймеханизм лучше для абитуриентов (порождает более низкие граничные оценки), чем H-устойчивый вуз-ориентированный механизм.Следствие 3.1.
Лучшие для абитуриентов H-устойчивый и Lустойчивый наборы граничных оценок (и ) являются, соответ-ственно, верхней и нижней границами для граничных оценок в любомустойчивом паросочетании, построенном с помощью механизма отложенного принятия с предлагаюшими вузами и случайным устранениембезразличий в предпочтениях вузов. Аналогичное утверждение вернои для наборов граничных оценок, которые являются наихудшими дляабитуриентов (и ).Это очень важное следствие позволяет использовать предложенныеновые концепции устойчивости для анализа существующих механизмов распределения со случайным устранением безразличий.Наконец, доказательства теорем 3.1.4 и 3.1.5 позволяют получитьнесколько более общее утверждение. А именно, предположим, чтосуществует «настоящий» порядок абитуриентов по их готовности кобучению в каждом вузе, и соответствующие этому порядку истинные оценки : × ↦→ , которые ни у каких двух абитуриентовв рамках одного вуза не совпадают.
Однако используемая системаоценивания содержит недостаточно градаций оценки (например, необходимо оценить 100 студентов, используя 10-балльную шкалу). Истинные оценки приходится округлять, получая при этом некоторыеновые оценки . Применение округления приводит к появлению абиту123риентов с одинаковыми оценками (неразличимых между собой с точкизрения этих округленных оценок).
Будем называть оценки абитуриентов улучшением оценок , если хотя бы для одного абитуриента онине совпадают и для любой пары абитуриентов и и вуза есливерно, что ≤ ≤ и < , то обязательно выполнено < , < , и < . Можно охарактеризовать эти соотношения подругому: отношение слабого порядка, порождамое системой оценок ,включается в отношение слабого порядка, порождаемое системой оценок , а оно, свою очередь, входит в отношение линейного порядка,порождаемое оценками . Действительно, если существуют истинныеоценки , то одна система оценивания лучше другой, если получаемыеоценки ближе к истинным оценкам .Следствие 3.2.
Предположим, что абитуриенты в каждом вузе могутбыть оценены истинными оценками , и соответствующий абитуриенториентированный набор граничных оценок равен (). Пусть и оценки абитуриентов, такие что является улучшением , а яв() и () H-устойчивыйляется улучшением . Обозначим через и L-устойчивый абитуриент-ориентированные наборы граничных оценок при системе оценок . Тогда верно, что () ≤ ( ) ≤ () ≤ ( ) ≤ ().3.1.4Манипулирование предпочтениямиВ этом разделе будет показано, что все описанные механизмынеустойчивы к манипулированию. Вообще говоря, манипулируемостьвуз-ориентированных механизмов как абитуриентами, так и вузамиследует из манипулируемости классического механизма отложенного124принятия с предлагающими вузами [6].
По этой причине ниже будутприведены только примеры, демонстрирующие возможности манипулирования со стороны абитуриентов в абитуриент-ориентированныхмеханизмах.Пример 3.1. Рассмотрим два вуза, и , в каждом из которых естьпо одному месту, и двух абитуриентов 1 and 2 , каждый из которыхподаёт заявления в оба вуза и каждый из которых считает более предпочтительным вуз . Абитуриенты имеют одинаковые оценки в обоихвузах. Вся информация о предпочтениях сведена в таблице 3.1.Таблица 3.1: Пример манипулирования в H-устойчивомабитуриент-ориентированном механизме1 : , 2 : , 1 = 2 = 11 = 2 = 2В данном случае единственное H-устойчивое решение соответствует «пустому» паросочетанию, т.е. установлению граничных оценок вобоих вузах на уровне выше, чем оценки, набранные абитуриентами. Однако, если один из студентов (например, 1 ) исказит своипредпочтения и укажет в качестве более предпочтительного вуза , то единственным H-устойчивым набором граничных оценок будет ( ) = 1, ( ) = 2.
В соответствующем паросочетании студент 1зачислен в вуз , а абитуриент 2 - в вуз . Таким образом, предложенное искажение предпочтений 1 улучшает его результат и, следовательно, является выгодным для него манипулированием. Заметим,что в данном случае манипулирование оказалась выгодно не толькосамому абитуриенту, но и всем другим участникам.125Следующий пример, демонстрирующий возможность манипулирования предпочтениями в L-устойчивом абитуриент-ориентированноммеханизме, основан на примере из [31].Пример 3.2.
Рассмотрим два вуза, и , в каждом из которых квотаустановлена на уровне 1, и трёх абитуриентов 1 , 2 и 3 , считающихприемлемыми оба вуза и и получивших следующие оценки: 1 =1, 2 = 1, 3 = 2, 1 = 3, 2 = 2 и 3 = 1. .Таблица 3.2: Пример манипулирования в L-устойчивомабитуриент-ориентированном механизме1 : , 2 : , 3 : , : 3 , (1 , 2 ) : 1 , 2 , 3В данном случае единственный L-устойчивый набор граничных оценок: ( ) = 2 и ( ) = 3, ему соответствует паросочетание ={(1 , ), (3 , )} Однако, если абитуриент 2 исказит свои предпочтения, поставив на первое место , то на первом шаге L-устойчивогоабитуриент-ориентированного механизма вуз получит одно заявление от 3 , а вуз - два заявления от 1 и 2 .
Граничные оценкибудут установлены ( ) = 1, ( ) = 1, ни один абитуриент не получит отказ и на этом работа механизма завершится. Соответствующее указанному набору граничных оценок паросочетание будет иметьвид = {(1 , ), (2 , ), (3 , )}. Таким образом, манипулированиепредпочтениями со стороны абитуриента 2 оказалось выгодно ему (иостальным абитуриентам тоже).Таким образом, в отличие от классической модели Гейла-Шепли,при использовании концепций H-устойчивости и L-устойчивостиоказывается, что абитуриент-ориентированный механизм построения126устойчивого паросочетания созщает абитуриентам стимулы для манипулирования предпочтениями.3.2Моделирование приемной кампании в РФВ данном разделе будет построена модель выбора абитуриентом вузов для подачи заявлений в условиях псевдо-централизованного механизма организации приемной кампании, принятого в РФ.3.2.1Организация приемной кампании в российских государственных вузахВ РФ все абитуриенты, кроме редких особых случаев, оцениваютсявузом в соответствии с суммой баллов, набранных ими в сумме по 3либо 4 предметам на ЕГЭ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
