Диссертация (1137447), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

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

Разумеется, притаком назначении граничных оценок могут найтись абитуриенты, чьиоценки оказались выше граничных в нескольких вузах. За каждымиз этих абитуриентов остаётся только место в самом предпочтительном для такого абитуриента вузе, а из списков остальных вузов этотабитуриент вычеркивается.На каждом из последующих шагов каждый вуз проверяет, можноли опустить граничную оценку, ведь некоторые абитуриенты могли отказаться и быть вычеркнуты из списка поступающих в данный вуз напредыдущих шагах механизма. Вуз устанавливает граничную оценку– наименьшее число, при котором набор граничных оценок оставалсябы H-допустимым (соответственно, L-допустимым) в соответствии стекущим списком поступающих.

Если абитуриент в результаты понижения граничных оценок получает возможность быть зачисленным вболее предпочтительный для него вуз, чем тот, куда он временно былзачислен на предыдущих шагах, то абитуриент отказывается от менеепредпочтительного предложения и принимает новое.Опишем механизм формально. Пусть - набор граничных оценокна -м шаге. На следующем шаге, в каждом вузе , выбирается наибольшее целое число , такое что ≤ ( ) и (,− ) ≤ (соответственно, если (,− ) ≥ , то (,− +1 ) < ). То есть, уменьшаемграничную оценку на как можно большую величину , при которой решение остаётся H-допустимым (соответственно, L-допустимым),т.е., где количество абитуриентов, которое по установленной гранич-109ной оценке проходят в вуз и не вычеркнуты из списка, не превышает квоты (соответственно, может превышать квоту, но толькоесли без последней группы абитуриентов с одинаковыми оценкамиостаются пустые места), предполагая при этом, что граничные оценкиостальных вузов останутся неизменными.

Для каждого вуза зададим +1 ( ) := ,− ( ) - новая граничная оценка. Некоторые абитуриенты опять могут проходить со своими оценками сразу в нескольковузов, поэтому не все абитуриенты из списка, имеющие оценку выше граничной, будут временно зачислены в вуз: (+1 ) ≤ (,− ).Разумеется, новый набор граничных оценок остаётся H-допустимым(или L-допустимым, соответственно).Наконец, если ни один вуз не может уменьшить свою граничнуюоценку, механизм завершает работу.

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

Эту операцию выполняеткаждый абитуриент, у кого список вузов для подачи заявлений ещё неисчерпан. Некоторые вузы получат новые заявления. Если при текущей граничной оценке число временно зачисленных абитуриентов превысит квоту (соответственно, превысит квоту и без последней группыабитуриентов с одинаковыми оценками квота все равно выбрана), товуз устанавливает новую, более высокую граничную оценку +1 ( ).Вновь устанавливаемая граничная оценка - это снова минимальноечисло, при котором количество заявлений от абитуриентов, имеющихоценку не ниже выбранного числа, не превысит квоту (соответственно,для L-устойчивости количество абитуриентов с оценкой не ниже этогочисла может превышать квоту, но только если без последней группыабитуриентов, имеющих одинаковые оценки, в вузе остаются пустыеместа).

Это означает, что отказывает всем абитуриентам, которыеранее были временно зачислены в вуз, но имеют оценку ниже вновьустановленной границы.Механизм заканчивает работу, когда нет ни одного абитуриента,который хотел бы подать новое заявление.111Сформированный на последнем шаге механизма набор граничных оценок, очевидно, является H-допустимым (соответственно, Lдопустимым). Решение является также H-устойчивым (соответственно, L-устойчивым), поскольку после последнего повышения граничныхоценок в вузах потерявшие место абитуриенты отправились в менеепредпочтительные вузы или остались незачисленными никуда. Такимобразом, если бы вуз понизил свою последнюю граничную оценку хотябы на единицу (см. определение устойчивого набора граничных оценок), то он получил бы новых абитуриентов, и требования по квотамбыли бы нарушены.Обозначим полученный H-устойчивый и L-устойчивый наборы гра, соответственно.и ничных оценок через Указанные рассуждения можно сформулировать в виде теоремы., построенныеи Теорема 3.1.1.

Наборы граничных оценок в результате реализации вуз-ориентированного механизма, являются H-устойчивым и L-устойчивым, соответственно. Наборы граничных оценок и , построенные в результате реа-лизации абитуриент-ориентированного механизма, являются Hустойчивым и L-устойчивым, соответственно.3.1.2Два вида механизмов и эффективность паросочетанияМожно легко привести пример, демонстрирующий, что, во-первых,вуз, в котором будет обучаться абитуриент при наборе граничныхоценок , окажется предпочтительнее для него, чем вуз при и,во-вторых, количество зачисленных в данный вуз абитуриентов может быть больше при , чем при (аналогично для L-концепции).112Будем говорить, что набор граничных оценок предпочтительнее дляабитуриентов, чем ′ , если ≤ ′ , т.е., если ( ) ≤ ′ ( ) для каждоговуза .

В этом случае каждый абитуриент при получает место в томже или более предпочтительном вузе по сравнению с ′ . Это отношение является, по сути, отношением Парето между соответствующимипаросочетаниями при учёте предпочтений всех абитуриентов.Теорема 3.1.2. является худшим (по отношению Парето) дляабитуриентов, а – Парето-эффективным для абитуриентов H-устойчивым набором граничных оценок, т.е. для любого устойчивого набора граничных оценок выполняется ≤ ≤ .Доказательство.

Предположим противное: пусть существует H( ). При выустойчивый набор * и вуз такие, что * ( ) > полнении вуз-ориентированного механизма обязательно найдутся двапоследовательных шага, -ый и + 1-ый, и соответствующие им наборы граничных оценок и +1 , такие что * ≤ и * ( ) > +1 ( )для некоторого вуза .Очевидно, что ,− ( ) = +1 ( ) по определению. Также, (,− ) ≤ < (*,−1 ). Первое неравенство выполнено по определению , поскольку мы выбираем новую граничную оценку в вузе таким образом, чтобы число временно зачисленных в этот вуз абитуриентов не превышало квоту.

Второе неравенство выполняется в силуH-устойчивости * . Следовательно, обязательно найдется абитуриент,назовем его 1 , который зачислен в вуз (имеет оценку не ниже граничной и предпочитает этот вуз другим) при *,−1 , но не зачислен ввуз при ,− .113С другой стороны, по предположению выше ,− ( ) = +1 ( ) ≤* ( ) − 1 = *,−1 ( ). Абитуриент 1 получил оценку не ниже ,− ( )в вузе , чего достаточно для того, чтобы быть принятым в , поэтому для того, чтобы набор был устойчивым, при ,− ( ) абитуриент1 должен быть зачислен в вуз , более предпочтительный, чем .Очевидно, что 1 должен быть также зачислен в при . Но изH-устойчивости * следует, что * ( ) > ( ), что противоречит предположению о том, что * ≤ .Вторую часть двойного неравенства докажем также от противного.

Пусть существуют H-устойчивый набор граничных оценок * ивуз такие, что * ( ) < ( ). Тогда при выполнении абитуриент-ориентированного механизма обязательно найдутся два следующихдруг за другом шага с временными наборами граничных оценок and +1 , такие что * ≥ и * ( ) < +1 ( ) для некоторого вуза .На этом шаге причина повышения граничной оценки состоит в том,что как минимум абитуриентов с оценками не ниже * ( ) подали заявления в . Из этого следует, что как минимум один из этихабитуриентов, назовем его 2 , не зачислен в при * (но его оценка в этом вузе – как минимум * ( )).

Характеристики

Список файлов диссертации