Диссертация (1137447), страница 16
Текст из файла (страница 16)
Из H-устойчивости * следует,что абитуриент 2 при наборе граничных оценок * должен быть зачислен в некоторый вуз , который предпочтительнее для этого абитуриента, чем . Т.к. рассматривается абитуриент-ориентированныймеханизм, абитуриент 2 должен был получить отказ в вузе напредыдущих (до -го) шагах механизма. Это возможно, только если* ( ) < ( ), что противоречит сделанному выше предположению отом, что * ≥ .114Теорема 3.1.3. является худшим (по отношению Парето) дляабитуриентов, а – Парето-эффективным для абитуриентовL-устойчивым набором граничных оценок, т.е. для любого Lустойчивого набора граничных оценок выполнено ≤ ≤ .Доказательство. Сначала докажем, что построенное в результатевуз-ориентированного механизма паросочетание является наихудшимдля абитуриентов.
Предположим противное: пусть существуют наборграничных оценок * и вуз такой что * ( ) > ( ). При выполне-нии вуз-ориентированного механизма найдутся два последовательныхшага и +1 , такие что * ≤ и * ( ) > +1 ( ) для некоторого вуза .Из сделанного предположения следует, что (,− +1 ) < ≤ (* ). Первое неравенство выполнено из-за L-допустимости +1 , авторое неравенство - из-за L-устойчивости * . В то же время, понашему предположению, * ( ) > +1 ( ), таким образом * ( ) ≥+1 ( ) + 1 = ,− +1 ( ).Из этих двух утверждений следует, что существует абитуриент, назовем его 1 , который имеет оценку 1 ≥ * ( ) в вузе (), зачисленв вуз при * , но не зачислен в при ,− +1 . Значит, при ,− +1абитуриент 1 должен быть зачислен в некоторый вуз , который длянего предпочтительнее, чем (), т.е.
1 . Очевидно, что 1 такжедолжен быть зачислен в при наборе граничных оценок . Но 1 незачислен в при * , следовательно ( ) < * ( ), противоречие.Чтобы доказать вторую часть утверждения теоремы, предположим,что существуют устойчивый набор граничных оценок * и вуз такие,что * ( ) < ( ). При выполнении абитуриент-ориентированного ме-115ханизма должны обязательно найтись два следующих друг за другомшага с временными (L-допустимыми) наборами граничных оценок и +1 , такие что * ≥ и * ( ) < +1 ( ) для некоторого вуза .При переходе на + 1 шаг причина повышения граничной оценки ввузе состоит в том, что как минимум абитуриентов с оценкамине ниже * () у каждого подали заявления в , и может назначитьболее высокую граничную оценку +1 ( ) = ,− ( ), где > * ( )− ( ), отвергнув таким образом последнюю группу абитуриентов содинаковыми оценками.Это означает, что один из абитуриентов, зачисленных в при +1 ,назовем его 2 , не зачислен в при * .
Но его оценка в этом вузе нениже граничной оценки * ( ). Значит, в силу L-устойчивости * , приэтом наборе граничных оценок абитуриент 2 должен получить местов более предпочтительном вузе . Раз этот вуз более предпочтителендля абитуриента, то при выполнении абитуриент-ориентированногомеханизма 2 должен был быть отвергнут этим вузом до шага . Всилу этого ( ) > * ( ), противоречие.3.1.3Сравнение H-устойчивости и L-устойчивостиИнтуитивно кажется, что L-устойчивость - более дружелюбная поотношению к абитуриентам концепция, чем H-устойчивость. Оказывается, можно доказать следующие теоремы.Теорема 3.1.4. Граничные оценки, рассчитанные L-устойчивымабитуриент-ориентированным механизмом, всегда не выше, чемграничные оценки, рассчитанные H-устойчивым абитуриенториентированным механизмом, т.е.
≤ .116Доказательство. Часть I. При наборе граничных оценок число за-численных в каждый вуз абитуриентов меньше либо равно квоте этоговуза, т.е. − () ≥ 0. У каждого вуза есть «лист ожидания»:абитуриенты, которые предпочли бы учиться в вузе по сравнениюс тем, куда каждый из них был зачислен.Применим к предпочтениям вузов процедуру устранения безразличий в предпочтениях. Каждый абитуриент получит новую оценку ≥ такую, что никакие два абитуриента не будут иметь одинаковой оценки в новой системе. Оценки будут назначены с сохранением существовавшего порядка, то есть если < , то < .Эти оценки будут положительными действительными числами.
Например, если в вузе рассматривают трёх абитуриентов с оценками1 = 2 = 1, 3 = 2, то новые оценки могут быть такими: 1 = 1,2 = 1.5, 3 = 2.После этого проводится следующая процедура: если число абитуриентов в «листе ожидания» вуза больше, чем число свободныхмест, то вуз снижает граничную оценку и устанавливает новую ( ) ≤ ( ), равную новой оценке последнего абитуриента, за-числяемого из листа ожидания. В противном случае вуз устанавливает ( ) = 0. Заметим, что новый набор граничных оценок - этонеотрицательные действительные числа.
Фактически, вуз заполняетоставшиеся свободными места, делая предложения (путём сниженияграничной оценки) абитуриентам из «листа ожидания».Некоторые абитуриенты при таком снижении оценок могут получить предложения (то есть иметь оценку не ниже установленной)более, чем в одном вузе. Каждый такой абитуриент выбирает из всех117доступных вузов наилучший и отказывается от предложений остальных. Если в каких-то вузах остались свободные места, то второй шагорганизуется по той же схеме и т.д. Фактически здесь работает процедура отложенного принятия с предлагающими вузами с учётом новыхоценок, устранивших безразличия в предпочтениях вузов.
В конецконцов, формируется новый набор граничных оценок , причем попостроению ≤ . Этот новый набор граничных оценок и со-ответствующее ему паросочетание устойчивы по построению.Часть II. В первой части для вузов на основе набранных оценокбыли построены отношения предпочтения, являющиеся линейнымипорядками на множестве абитуриентов.
Таким образом, была получена классическая задача о распределении абитуриентов по вузам. Вэтой задаче может быть использован механизм отложенного принятияс предлагающими абитуриентами (который, в случае предпочтений,заданных линейными порядками, эквивалентен и L-устойчивому, и Hустойчивому абитуриент-ориентированным механизмам).
В результате применения механизма будет получено паросочетание , которое,разумеется, является устойчивым при построенных в части I предпочтениях. Более того, можно определить набор граничных оценок ,в котором ( ) равно самой низкой оценке зачисленного в вуз абитуриента, , если в вузе заняты все места, или 0 в противном случае.Этот набор граничных оценок должен быть наименьшим средивсех устойчивых наборов граничных оценок (это следует как из теоремы Гейла-Шепли об эффективности , так и из доказанной вышеболее общей теоремы о наборах граничных оценок).
Следовательно,верно, в частности, и следующее: ≤ .118Часть III. Теперь рассмотрим набор граничных оценок . Вернёмся к исходным оценкам, набранным абитуриентами в вузах ( ) исоответствующим отношениям слабого порядка. Для каждого вуза, вкотором заполнены все места, т.е. ( ) = можно построить «листожидания» из абитуриентов, предпочитающих вуз своему текущемуместу учёбы при .Применим теперь концепцию L-допустимости. На первом шаге каждый вуз «опустит» свою граничную оценку ( ) ≤ ( ) до такогонаибольшего возможного значения, при котором в вуз зачислено или больше абитуриентов в соответствии с исходными оценками абитуриентов. Например, если имеется два абитуриента, и с одинаковой оценкой = , такие что один из них зачислен в принаборе граничных оценок , а другой находится в листе ожидания,то в соответствии с концепцией L-устойчивости должны быть зачислены оба абитуриента.
Таким образом, каждый вуз приглашает такихабитуриентов из листа ожидания, если таковые есть.Некоторые абитуриенты могут получить более одного приглашения;в этом случае каждый абитуриент выбирает наиболее предпочтительный вуз. Если после этого остались вузы, в которых заполнены не всеместа, начинается следующий шаг механизма. Каждый вуз выбираетновую, L-допустимую граничную оценку, и т.д. Таким образом, запущена процедура, аналогичная вуз-ориентированному L-устойчивомумеханизму. В результате её выполнения будет получен новый наборграничных оценок , причём ≤ по построению. Этот новыйнабор граничных оценок является, очевидно L-устойчивым.119Часть IV.
Для каждого L-устойчивого набора граничных оценок известно, что ≤ по теореме 3.1.3, где - устойчивый наборграничных оценок, полученный в результате применения абитуриенториентированного L-устойчивого механизма.Получаем следующий набор неравенств: ≤ ≤ ≤ ≤ .Теорема доказана.Теорема 3.1.5. Граничные оценки, рассчитанные L-устойчивымвуз-ориентированным механизмом, всегда не выше, чем граничныеоценки, рассчитанные H-устойчивым вуз-ориентированным меха.≤ низмом, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
