Диссертация (1137447), страница 12
Текст из файла (страница 12)
не содержит блокирующих пар) при модифицированном профилепредпочтений ⪰′′ = {≻′′ },∈ , состоящем из линейных порядков, также является устойчивым при исходном профиле предпочтений вузов⪰. Поскольку предпочтения абитуриентов также являются линейными порядками, то по теореме Гейла-Шепли устойчивое паросочетаниевсегда существует и может быть построена с помощью механизма отложенного принятия (после преобразования интервальных порядков влинейные).Таким образом, показано, что устойчивое паросочетание всегда существует и может быть найдено с помощью механизма отложенногопринятия. На самом деле, утверждение этой теоремы следует из болееобщего утверждения: попарно-устойчивое паросочетание существуетпри любом профиле предпочтений, заданных частичными порядками.Следующий важный вопрос состоит в следующем: все ли паросочетания, которые устойчивы при исходном профиле предпочтений, устойчивы и при каком-то линейном расширении предпочтений вузов? Положительные ответ на этот вопрос означает, что любое устойчивоепри исходном профиле паросочетание, вообще говоря, можно найти,использовав какое-либо линейное расширение интервальных порядков.Теорема 2.2.3.
Для любого паросочетания , которое устойчивопри исходном профиле предпочтений (заданных линейными порядками для абитуриентов и интервальными порядками для вузов)существует модифицированный профиль предпочтений ⪰′ , состо84ящий из линейных расширений предпочтений из профиля ⪰, такойчто остается устойчивым (т.е. не образуется новых блокирующих пар).Доказательство. Рассмотрим некоторое паросочетание , котороеустойчиво при исходных предпочтениях (⪰, ).
Построим профиль линейных расширений ⪰′ , при котором в паросочетании не образуютсяновые блокирующие пары. Поскольку блокирующая пара включает одного абитуриента и один вуз, линейные расширения могут строитьсявуза независимо.Рассмотрим некоторый вуз . Новый линейный порядок ≻′ должен обладать, помимо свойств линейного порядка, следующими двумясвойствами:∙ являться линейным расширением исходного отношения, т.е.
если ≻ , то ≻′ ,∙ не создавать новых блокирующих пар, т.е. если абитуриент предпочитает вуз своему текущему месту обучения, то согласноотношению ≻′ вуз должен предпочитать любого из зачисленных в этот вуз абитуриентов абитуриенту . Формально, если ( ), то ∀ ∈ () ≻ .Определим множество ′ , как множество абитуриентов, неразличимых с или доминируемых по отношению предпочтения ≻ всемиабитуриентами, зачисленных в вуз в паросочетании .
Формально,′ ={′ ∈ ∖ () : ∀ ∈ () ≻ ′ }. Кроме того, определим множество тех абитуриентов, которые не зачислены в вуз и не входят в⋃︀′ : ′′ = ∖ (′ ()). Нетрудно заметить, что множества ′′ , (), ′задают разбиение множества абитуриентов.85Любой абитуриент ′ из множества ′ может быть (теоретически)заинтересован в вузе больше, чем в текущем месте обучения (′ ).Таким образом, чтобы при построении линейного расширения не образовалось блокирующий пары (′ , ), любой абитуриент из множества′ должен доминироваться любым абитуриентом из числа зачисленных в вуз (т.е.
из ()) согласно линейному расширению ≻′ .Заметим, что любой абитуриент из множества ′′ должен быть зачислен в вуз, который для этого абитуриента предпочтительнее, чем .В противном случае и этот абитуриент образовали бы блокирующуюпару в паросочетании .Теперь преобразуем исходную функцию () в новую * () такимобразом, чтобы в отношении интервального порядка ≻* , построенномна основе этой функции, любой абитуриент из ′ будет доминироваться любым абитуриентом из () и при этом новое отношение непротиворечит исходном отношению предпочтения вуза, т.е.
≻ ⊆≻* .Для всех абитуриентов из () и ′′ () значения * () и * (), определяемые функцией * () остаются такими же, как и при исходнойфункции (). В то же время, верхние и нижние границы интерваловдля абитуриентов из ′ будут изменены.Определим две вспомогательные переменные: минимальное значение нижней границы интервала для всех абитуриентов, уже зачисленных в : = min∈() ( ()); и максимальное значение верхней границы интервала для всех абитуриентов, не зачисленных в, но предпочитающих этот вуз текущему месту обучения при : = ∈′ ( ()).86Если < , то преобразование не требуется и * () ≡ (),поскольку любой абитуриент в () предпочтительнее любого абитуриента в ′ при исходных предпочтениях ≻ вуза .
В противномслучае, присвоим абитуриенту ′ ∈ ′ новые верхнюю и нижнюю границы интервала следующим образом: * (′ ) = (′ ) − ( − ) − 1,* (′ ) = (′ ) − ( − ) − 1. Фактически, интервалы всех абитуриентов ′ сдвинуты ниже нижней границы для всех зачисленных в абитуриентов.Покажем, что новый интервальный порядок ≻* , основанный нафункции * (), является расширением исходного отношения предпочтения ≻ .1. Взаимное расположение объектов внутри множеств ′′ , ′ , ()остается неизменным.2.
Для любых абитуриентов ′ ∈ ′ и ∈ ():∙ если ≻ ′ , то () > (′ ) и, естественно, () > (′ ) −( − ) − 1,∙ если (≻ )′ , то (′ ) ≥ () и () ≤ (′ ). По построению* * (′ ) < (), поскольку из (′ ) вычитается число, которое больше максимальной разницы (′ )− () среди всех пар(, ′ ),∙ по построению ′ () невозможно ′ ≻ .3. Для любых абитуриентов ′ ∈ ′ и ′′ ∈ ′′ :∙ если ′′ ≻ ′ , то (′′ ) > (′ ) и, естественно, (′′ ) > (′ )−( − ) − 1,87∙ если ′′ (≻ )′ , то немедленно (′ ) ≥ (′′ ) и (′′ ) ≤ (′ ).При новом интервале [* (′′ ), * (′′ )] абитуриенты либо остаются неразличимыми, либо ′′ становится предпочтительнее ′ .∙ ′′ ≻ ′ невозможно, потому что, по построению множеств ′и ′′ существует такой что (′′ ) > (), но ∀ () ≥ (′ ).Это означает, что (′′ ) > (′ ). Используя (′′ ) ≥ (′′ ),получим, что (′′ ) > (′ ), поэтому ′′ никогда не можетбыть доминируем абитуриентом ′ .Таким образом, построена новая функция * (), такая что соответствующий ей интервальный порядок ≻* не противоречит исходномуотношению предпочтения и, более того, каждый абитуриент, которыймог бы (потенциально) составить блокирующую пару с вузом в паросочетании , теперь строго доминируется любым абитуриентом из().
Теперь отношение ≻* можно преобразовать в линейный порядоклюбым образом, и в любом случае не будет нарушена устойчивостьпаросочетания .Теперь можно сформулировать и доказать теорему об устойчивыхулучшающих циклах, которая является обобщением соответствующейтеоремы для простейших полупорядков.Теорема 2.2.4. Пусть задан профиль предпочтений (⪰, ), и найдено устойчивое при данном профиле паросочетание .
Если доминируется по Парето (для абитуриентов) другим устойчивым паросочетанием , то существует устойчивый улучшающий цикл.Доказательство. Пусть множество ′ включает всех абитуриентов,которые предпочитают свой вуз в паросочетании своему вузу в па88росочетании . Тогда пусть ′ = (′ ), то есть множество вузов,в которые зачислены абитуриенты из ′ в паросочетании . Пусть ′ (, ) – подмножество ′ , в котором каждый абитуриент предпочитает быть зачисленным в вуз вместо распределения в паросочетании . Формально, ′ (, ) = { ∈ ′ | ()}.
Кроме того, обозначим через ′ (, ) подмножество множества ′ (, ), в котороевойдут только абитуриенты с максимальной верхней границей ()интервала, сопоставленного отношению ≻ функцией . Формально,′ (, ) = { ∈ ′ (, )|() = ∈ ′ (,) (())}. Заметим, что множество ′ (, ) всегда непусто.Теперь построим = (, ) – ориентрованный граф, в котороммножество вершин = ′ . Дуга (1 , 2 ) входит в граф , если существует абитуриент, который∙ распределен в вуз 1 в паросочетании , но предпочитает вуз 2вузу 1 ,∙ среди всех абитуриентов, которые предпочитают вуз 2 своему текущему месту обучения в паросочетании , этот абитуриент принадлежит группе абитуриентов с наибольшей верхней границей интервала, определённого функцией .Формально, дуга (1 , 2 ) ∈ , если и только если существует ∈(1 ) такой, что ∈ ′ (2 , ).Будем говорить, что дуге (1 , 2 ) присвоен «ярлык» с именем абитуриента .Граф всегда содержит цикл, поскольку каждый вуз во множестве ′ (по построению этого множества) хотя бы для одного абитуриента предпочтительнее текущего (здесь используется утверждение89Леммы 2.1).
Возьмём любой такой цикл (точнее, тех абитуриентов,которые дали «ярлыки» дугам, входящим в этот цикл) и покажем, чтоэтот цикл является устойчивым улучшающим циклом.Первое и второе свойства устойчивого улучшающего цикла выполнены по построению.Покажем, что третье свойство также выполнено. Абитуриент предпочтительнее для вуза , чем некоторый другой абитуриент ′ ,если и только если (′ ) > (). По построению цикла, ∀ абитуриент =SIC() имеет максимальную верхнюю границу интервала ()среди всех абитуриентов из множества ′ (, ), то есть среди всехабитуриентов из ′ , которые хотели бы перевестись в вуз при паросочетании . Таким образом, ни один абитуриент из ′ (, ) не можетбыть предпочтительнее для вуза , чем .Остается показать, что никакой абитуриент из ∖ ′ (множествотех, чей вуз не меняется при переходе от к ) не предпочтительнеедля вуза , чем абитуриент =SIC().
Предположим противное: пустьсуществует абитуриент ∈ ∖ ′ и некоторый вуз ∈ ′ такие, что ≻ () и ≻ SIC() (т.е. выполнено () > (SIC())). В этомслучае абитуриент и вуз сформировали бы блокирующую пару вновом паросочетании, которое образуется после обмена в цикле SIC.Из устойчивости паросочетания следует, что для всех абитуриентов ∈ () верно, что ≻ или (≻ ). (здесь используется утверждение Леммы 2.1). Для границ, заданных функцией , этоозначает, что () ≥ ().
С другой стороны, SIC() и любой абитуриент () ∖ () принадлежат множеству ′ (, ), и, к тому же, SIC()∈90′ (, ) таким образом, по построению множества ′ , (SIC()) максимально, следовательно ∀ ∈ () ∖ () (SIC()) ≥ ().Из двух неравенств выше получим, что (SIC()) ≥ () ≥ .Противоречие: не может быть предпочтительнее абитуриента SIC()для вуза . Таким образом, и не образуют блокирующую пару.Построенный цикл является устойчивым улучшающим циклом, т.к.обладает всеми тремя свойствами.Доказанная теорема фактически предоставляет критерий для проверки эффективности (для абитуриентов) любого устойчивого паросочетания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
