Диссертация (1137447), страница 11
Текст из файла (страница 11)
Пусть (, ) = { ∈ : ()}, кроме того, пусть (, ) = { ∈ (, ) : ∀ ∈ (, ) ≻ }.Определение 2.3. Устойчивый улучшающий цикл в паросочетании – это последовательность различных абитуриентов 1 , ..., ≡ 0( ≥ 2) таких, что1. ( ) ∈ , т.е. каждый из них зачислен в вуз в паросочетании ;2. ∀ (+1 ) ( ), т.е. каждый предпочел бы учиться в вузе, вкотором учится соседний абитуриент с большим номером;3. ∀ ∈ ((+1 ), ), т.е. среди всех абитуриентов, которые хотели бы учиться в вузе абитуриента +1 , абитуриент находитсяв группе наилучших.Обозначим SIC( ) = +1 , SIC( ) = −1Если совершить передачу мест (от абитуриентов с большим номером абитуриентам с меньшим номером) в соответствии с построеннымциклом, то условие 2 будет гарантировать, что положение всех абитуриентов в цикле улучшится, а условие 3 обеспечит устойчивостьпаросочетания, построенного после обмена в соответствии с циклом.Пример 2.3. Рассмотрим профиль предпочтений из Примера 2.2 иустойчивое паросочетание .
Как обсуждалось в Примере 2.2, данноепаросочетание не является оптимальным по Парето для абитуриентов.Можно построить цикл, состоящий из двух абитуриентов 1 и 2 . Такой цикл будет устойчивым улучшающим циклом, поскольку обладаеттремя свойствами.771. 1 и 2 зачислены в вуз в паросочетании .2. (2 )1 (1 ) и (1 )2 (2 ), т.е. каждый абитуриент считает вуз,в который зачислен другой абитуриент, более предпочтительным,чем тот, куда зачислен он сам.3.
(1 , ) = (1 , ) = {1 } и (2 , ) = (2 , ) = {2 , 3 }, т.е. обаабитуриента являются наиболее предпочтительными из тех, ктожелает попасть в соответствующий вуз. В данном примере третье требование выполнено автоматически, поскольку множества( , ) и ( , ) совпадают для обоих вузов.Таким образом, мы можем совершить «обмен» местами между абитуриентами 1 и 2 . Будет получено паросочетание , которое слабодоминирует по Парето паросочетание для абитуриентов.Основная теорема формулируется следующим образом:Теорема 2.1.3. Пусть заданы отношения ⪰ и , и пусть – некоторое устойчивое паросочетание.
Если доминируется по Парето(для абитуриентов) другим устойчивым паросочетанием, то существует устойчивый улучшающий цикл.Доказательство. Для доказательства основной теоремы нам необходимо будет воспользоваться следующей леммой.Лемма 2.1. [34] Зафиксируем профили ⪰ и . Пусть – устойчивоепаросочетание, которое доминируемо по Парето (для абитуриентов)другим паросочетанием . Обозначим через ′ множество абитуриентов, которые предпочитают вуз, предписанный им в вузу, предписанному им в , а ′ = (′ ).
Иначе говоря, ′ – это множествовузов, каждый из которых в паросочетании обучает хотя бы одного78студента из множества ′ . В таком случае будут верны следующиеутверждения:1. Абитуриенты из ∖′ имеют одно и то же предписанное распределение в паросочетаниях и .2. Для любого вуза верно, что |()| = |()|, т.е. при обоих паросочетаниях занято одинаковое число мест.3. Любой абитуриент из множества ′ зачислен в вуз (а не оставленбез места в вузе) и в , и в .Доказательство этой леммы здесь не приводится, поскольку оригинальное доказательство [34], сделанное для модели со слабыми порядками, не использует свойство отрицательной транзитивности отношений предпочтения вуза.
Следовательно, утверждения леммы верныдля случая любых ацикличных и транзитивных отношений предпочтений вузов, т.е. для случая частичных порядков.Перейдем теперь к доказательству основных утверждений теоремы.Обозначим через ≻′ преобразованное отношение предпочтения вуза на множестве абитуриентов.
Для любых , ′ , ′′ таких, что(≻ )′ , ′ (≻ )′′ , ≻ ′′ ,преобразованное отношение предпочтения таково, что ≻′ ′ , ′ ≻′ ′′ , ≻′ ′′ .Заметим, что в частных случаях простейших полупорядков в построенном преобразованном отношении предпочтения ≻′ могут сохранять-79ся безразличия, однако такое отношение по построению будет являться слабым порядком.Обозначим через ′ множество абитуриентов, которые предпочитают вуз, предписанный им в , вузу, предписанному им в , а ′ = (′ ). Иначе говоря, ′ – это множество вузов, чьи абитуриенты из паросочетания принадлежат множеству ′ .Пусть ′ (, ) = { ∈ ′ : ()}.Также, пусть ′ (, ) = { ∈ ′ : ∀ ∈ ′ ≻′ }.Теперь построим ориентированный граф (, ), где множествовершин ′ соответствует подмножеству вузов ′ , а (( , ) ∈ ) ⇔(∃ ∈ ( ) : ∈ ′ ( , )). Другими словами, вуз указывает на вуз в графе , если и только если существует абитуриент , который∙ зачислен в вуз при паросочетании , но предпочел бы учитьсяв вузе ,∙ среди всех таких абитуриентов, которые предпочли бы учиться в (по сравнению с предписанным им при местом обучения),он принадлежит к группе наиболее предпочтительных для вуза абитуриентов (причем в соответствии с преобразованным отношением предпочтения ≻′ ).Присвоим имя такого абитуриента - ’’ - соответствующей дуге ( , )В графе всегда существует цикл, поскольку по построению множества ′ для каждого из входящих в него вузов существует хотя быодин абитуриент, который желает попасть в этот вуз больше, чем ввуз, предписанный при .
Возьмём любой такой цикл (а точнее, абитуриентов, чьи имена указаны на дугах, входящих в цикл) и покажем,что такой цикл будет устойчивым улучшающим циклом.80Первое и второе свойства устойчивого улучшающего цикла выполняются по построению. Покажем, что третье свойство также выполнено. По построению, ∀ и ∀ ∈ ′ ( ≻ ()) ⇒ ( ≻ SIC()). Такимобразом, ни один абитуриент из ′ не может образовать блокирующуюпару с вузом из ′ . Докажем теперь, что ни один абитуриент из ∖ ′также не сможет образовать блокирующую пару с вузом из ′Предположим противное: пусть ∃ ∈ ∖′ и ∈ ′ такие, что ≻ () ∧ ≻ SIC().
В этом случае абитуриент и вуз составили бы блокирующую пару и паросочетание, образованное послепроведения обмена в соответствии с построенным циклом, не было быустойчивым.Для любого вуза ∈ ′ из устойчивости паросочетаний и следует, что ∀ ∈ () ≻ , ∀ ∈ () ≻ (здесь использованоутверждение Леммы 2.1) и ∀ ∈ () SIC() ≻ . С другой стороны, SIC()∈ ′ , () ⊂ ′ и, по построению цикла, SIC()∈ ′ (, ),поэтому можно заключить, что ∀ ∈ () ≻ SIC().Поскольку ≻ является простейшим полупорядком, возможна следующая ситуация: ∃ ∈ () : (≻ ), (≻ ) SIC(), но ≻ SIC().Но SIC был построен на основе профиля преобразованных предпочтений ⪰′ . Таким образом, в рассмотренном случае дуга, соответствующая абитуриенту SIC(), не была бы включена в граф, т.к. в соответствии с преобразованное отношение предпочтения ≻′ было бы построено таким образом, что ≻′ SIC().
Таким образом, и никогда несоставят блокирующую пару. Итак, показано, что построенный циклобладает всеми свойствами устойчивого улучшающего цикла.81Эта теорема фактически дает критерий определения эффективностиполученного паросочетания, а также ключ к улучшению неэффективного устойчивого распределения.2.2Обобщенные паросочетания при предпочтениях, являющихся интервальными порядкамиДанная модель является расширением модели, построенной в разделе 2.1. Главное отличие состоит в том, что теперь профиль предпочтений вузов ⪰= (≻1 , ..., ≻|| ) состоит из интервальных порядков.Каждое такое отношение предпочтения, как и ранее, задано на множестве ∪ {}, состоящем из всех абитуриентов и возможности оставить место незаполненным.
Каждое бинарное отношение ≻ удовлетворяет требованию «отсутствия безразличия с незачислением», т.е.∀ ∈ ,∀ ∈ ( ≻ ) ∨ ( ≺ ). Таким образом, исключена ситуацию, когда для вуза неразличимо, зачислен ли абитуриент , илиместо оставлено пустым.Дадим формальное определение интервального порядка [61].Определение 2.4. . Бинарное отношение ≻⊆ 2 называется интервальным порядком на , если оно удовлетворяет условиям∙ антирефлексивности,∙ строгой интервальности: ∀, , , таких, что ≻ , ≻ верно,что ≻ или ≻ .Введем дополнительно функцию : −→ 2 , которая ставит всоответствие каждой альтернативе ее интервал. Для конкретного отношения предпочтения ≻ будем обозначать функцию как , а ниж82нюю и верхнюю границы интервала для каждой альтернативы – как () и (), соответственно.Теорема 2.2.1. [61], [59] Бинарное отношение ≻⊆ 2 являетсяинтервальным порядком, если и только если каждому элементу ∈ можно поставить в соответствие интервал [(), ()], так,что ≻ ′ если и только если () > (′ ).Для случая интервальных порядков также можно доказать, чтоустойчивое паросочетание всегда существует.Теорема 2.2.2.
В задаче распределения абитуриентов по вузам,где предпочтения абитуриентов заданы линейными порядками, апредпочтения вузов – интервальными порядками, устойчивое паросочетание всегда существует.Доказательство. Если в интервальном порядке есть пара альтернатив, неразличимых между собой (т.е. ≻ , ≻ , то эти безразличия можно устранить, дополнив интервальный порядок до линейного порядка. Действительно абитуриент неразличим с абитуриентом при истинных предпочтениях вуза , то это означает, что соответствующие интервалы () и () пересекаются.
Тогда построимновое бинарное отношение ≻′ , например, следующим образом: пусть ≻′ если и только если ( )+ ( )2> ( )+ ( ).2Это отношениебудет слабым порядком, причем если ≻ , то ≻′ . Дополнить этот слабый порядок до линейного порядка ≻′′ можно, любымобразом упорядочив оставшиеся неразличимыми альтернативы и добавив соответствующие упорядоченные пары к бинарному отношению.Множество блокирующих пар, в которые может вступать вуз с отношением предпочтения ≻′′ включает в себя множество блокирую83щих пар, которые может сформировать вуз с отношением предпочтения ≻ . Таким образом, паросочетание, которое является устойчивым(т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
