Автореферат (1137446), страница 3

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

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

Рассмотрены такие приложениятеории обобщенных паросочетаний, как организация распределения учениковпо школам, программы распределения выпускников медицинских вузов в интернатуру (с учетом предпочтений семейных пар), механизмы зачисления детейв ясли и детские сады с разновозрастными группами и др.Вторая глава посвящена исследованию модели обобщенных паросочетаний при предпочтениях, построенных на основе порогового выбора.В разделе 2.1 проанализирована модель обобщенных паросочетаний припредпочтениях, являющихся простейшими полупорядками. Простейшие полупорядки были впервые введены Ф.Т. Алескеровым как минимальное расширение линейного порядка.Дадим формальное определение простейшего полупорядка.

Для этогонам потребуется дать определение полупорядка.Определение 2.1. Бинарное отношение ≻ является полупорядком на ,если оно удовлетворяет условиям∙ ацикличности,∙ строгой интервальности (∀, , , ∈ таких что ≻ , ≻ верно, что ≻ или ≻ ),∙ полутранзитивности (∀, , , ∈ ( ≻ , ≻ ) ⇒ ≻ или ≻ )).Пусть (≻) – отношение безразличия для ≻, т.е. (≻) ⇔ ( ≻ ∧ ≻ ). Также обозначим множество доминируемых альтернатив как ( ≻) ={ : ≻ }, и множество доминирующих альтернатив как (≻ ) = { : ≻ }.Определение 2.2.

Полупорядок ≻ является простейшим полупорядком,если он удовлетворяет∙ слабой отрицательной транзитивности:12∀, ∈ ( ≻ ) ⇒ |{ : (≻) ∧ (≻)}| ≤ 1, т.е. существует не болееодного элемента, находящегося в отношении безразличия одновременно ис , и с ∙ слабому условию различия срезов: ∀, ∈ (≻ ) ̸= (≻ ) ∨ ( ≻) ̸=( ≻).Приведем пример для иллюстрации понятия простейшего полупорядка.Пусть в вуз поступают абитуриенты 1 , 2 , 3 . По результатам приемных испытаний профессора с уверенностью заключили, что абитуриент 1 подготовленлучше, чем абитуриент 3 .

В то же время про абитуриента 2 нельзя сказать, чтоон подготовлен лучше или хуже ни по сравнению с 1 , ни по сравнению с 3 .Тогда отношение предпочтения вуза, построенное на основе такого заключения,является простейшим полупорядком. Ключевой особенностью простейшего полупорядка является то, что существует не более одного такого абитуриента, как2 , который одновременно неразличим по предпочтительности и с 1 , и с 3 .Для модели обобщенных паросочетаний, где предпочтения игроков являются простейшими полупорядками, доказаны следующие теоремы.Теорема 2.1.1.

Если профили предпочтений абитуриентов и вузов ⪰состоят из простейших полупорядков, то устойчивое паросочетание всегдасуществует.Теорема 2.1.2. Для любого устойчивого паросочетания в модели с предпочтениями, заданными простейшими полупорядками, можно найти такой состоящий из линейных порядков профиль предпочтений вузов ⪰′ (где каждоеотношение предпочтения ≻′ является линейным расширением отношения ≻ ),что паросочетание является устойчивым при этом профиле ⪰′ .В случае предпочтений, являющихся линейными порядками, существуетединственное наилучшее (Парето-эффективное) для абитуриентов устойчивоепаросочетание, причем это паросочетание может быть найдено с помощью механизма отложенного принятия с предлагающими абитуриентами.

В случае же,когда предпочтения не являются линейными порядками, механизм отложенногопринятия с предлагающими абитуриентами может строить неэффективное дляабитуриентов паросочетание. Эрдилом и Эрджином для случая, когда предпо13чтения вузов являются слабыми порядками, введено понятие устойчивого улучшающего цикла.Пусть (, ) = { ∈ : ()}, кроме того, пусть (, ) = { ∈(, ) : ∀ ∈ (, ) ≻ }.Определение 2.3.

Устойчивый улучшающий цикл в паросочетании – этопоследовательность различных абитуриентов 1 , ..., ≡ 0 ( ≥ 2) таких, что1. ( ) ∈ , т.е. каждый из них зачислен в вуз в паросочетании ;2. ∀ (+1 ) ( ), т.е. каждый предпочел бы учиться в вузе, в которомучится соседний абитуриент с большим номером;3. ∀ ∈ ((+1 ), ), т.е.

среди всех абитуриентов, которые хотели быучиться в вузе абитуриента +1 , абитуриент находится в группе наилучших.Если обеспечить переход абитуриентов из вуза в вуз (каждый переходитна место абитуриента с большим на единицу номером) в соответствии с построенным циклом, то условие 2 будет гарантировать, что каждый абитуриентпредпочтет новый вуз старому, а условие 3 обеспечит устойчивость паросочетания, построенного после обмена в соответствии с циклом.Показано, что отсутствие устойчивого улучшающего цикла явдяется критерием эффективности паросочетания для абитуриентов в случае предпочтений,заданных простейшими полупорядками.Теорема 2.1.3.

Пусть предпочтения вузов ⪰ заданы простейшими полупорядками, а предпочтения абитуриентов – линейными порядками, и пусть – некоторое устойчивое паросочетание. Если доминируется по Парето (дляабитуриентов) другим устойчивым паросочетанием, то существует устойчивый улучшающий цикл.В разделе 2.2 проанализирована модель обобщенных паросочетаний припредпочтениях, являющихся интервальными порядками.Определение 2.4.

Бинарное отношение ≻⊆ 2 называется интервальнымпорядком на , если оно∙ антирефлексивно14∙ строго интервально (∀, , , ∈ таких, что ≻ , ≻ верно, что ≻ или ≻ )Введем дополнительно функцию : −→ 2 , которая ставит в соответствие каждой альтернативе некоторый интервал. Бинарное отношение ≻⊆ 2является интервальным порядком, если и только если каждому элементу ∈ можно поставить в соответствие интервал [(), ()], так, что ≻ ′ если итолько если () > (′ ).В случае, когда предпочтения вузов основаны на набранных абитуриентами экзаменационных баллах, естественно предположить, что предочтениявузов являются интервальными порядками.

Действительно, набранные абитуриентом на экзамене баллы не являются точной оценкой его уровня подготовки,и абитуриенты, чьи баллы незначительно отличаются, должны быть признанынеразличимыми.Результаты раздела 2.1 обобщены на случай интервальных порядков. Доказаны следующие теоремы.Теорема 2.2.2. Если профили предпочтений абитуриентов и вузов ⪰состоят из интервальных порядков, то устойчивое паросочетание всегда существует.Теорема 2.2.3. Для любого устойчивого паросочетания в модели спредпочтениями, заданными интервальными порядками, можно найти такойсостоящий из линейных порядков профиль предпочтений вузов ⪰′ (где каждоеотношение предпочтения ≻′ является линейным расширением отношения ≻ ),что паросочетание является устойчивым при этом профиле ⪰′ .Теорема 2.2.4.

Пусть предпочтения вузов ⪰ заданы интервальными порядками, а предпочтения абитуриентов – линейными порядками, и пусть – некоторое устойчивое паросочетание. Если доминируется по Парето (дляабитуриентов) другим устойчивым паросочетанием, то существует устойчивый улучшающий цикл.Последний результат позволяет построить устойчивый и Паретоэффективный для абитуриентов механизм, состоящий из следующих шагов. Вопервых, произвольным образом устраняются безразличия в предпочтениях каждого вуза. Во-вторых, применяется механизм отложенного принятия с предла15гающими абитуриентами.

Наконец, выполняется поиск устойчивого улучшающего цикла. Если цикл найден, производится перевод абитуриентов в соответствии с циклом и вновь выполняется поиск цикла в новом паросочетании. Механизм останавливается, когда построено паросочетание, в котором не существуетустойчивого улучшающего цикла. Данный механизм строит устойчивое и эффективное для абитуриентов (по теореме 2.2.4) паросочетание, однако обладаетсущественным недостатком: он подвержен манипулированию со стороны абитуриентов; иначе говоря, абитуриенту может быть выгодно не сообщать своиистинные предпочтения, а исказить их.Именно поэтому в разделе 2.3 предложен неманипулируемый устойчивый механизм с минимальной вероятностью построения неэффективного дляабитуриентов паросочетания.

Предложенный механизм основан на механизмеотложенного принятия с предлагающими абитуриентами, однако перед выполнением собственно механизма использует специальную обратную процедуруустранения безразличий в предпочтениях вузов.В дальнейшем будем рассматривать некоторый вуз , считая, что предпочтения остальных вузов и всех абитуриентов случайны. Пусть , предпочтенияабитуриента – это дискретная случайная величина, равномерно распределенная на множестве всех линейных порядков, заданных на ∪{}.

≻′ , предпочтения вуза ′ – это дискретная случайная величина, равномерно распределенная намножестве всех простейших полупорядков, заданных на ∪{′ }. Распределениявсех случайных величин независимы.Теорема 2.3.1. Пусть профиль предпочтений абитуриентов состоитиз линейных порядков, профиль предпочтений вузов ⪰ – из простейших полупорядков. Квота каждого вуза = 1.

Тогда вероятность получения неэффективного для абитуриентов паросочетания при использовании механизма отложенного принятия с предлагающими абитуриентами будет наименьшей, еслиустранение безразличий проведено по следующей процедуре:∙ Шаг 1. Рассматривается исходное отношение предпочтения ≻ и «лучшая» (т.е. состоящая из таких альтернатив, множество более пред-16почтительных элементов для которых пусто) максимальная антицепь31 ={1 , ..., }. Пусть ≻′ , если ( ≻ ) ⊂ ( ≻ ), т.е. доминирует в новом преобразованном отношении предпочтения ≻′ , если множество альтернатив, доминируемых альтернативой строго входит вомножество альтернатив, доминируемых альтернативой . Все остальные безразличия между альтернативами во множестве 1 устраняютсяпроизвольным образом.∙ Шаг ∈ [2, ].

Рассматривается «лучшая» максимальная антицепь вомножестве ∖ (∪−1=1 ). Повторяется процедура устранения предпочтений, описанная на шаге 1, для антицепи . Шаги повторяются до техпор, пока не будут исчерпаны элементы множества .∙ Шаг + 1. Для любых элементов ∈ , ′ ∈ пусть ≻′ ′ , если < .Стоит отметить, что впервые предложен механизм, сохраняющий весьмажелательное с теоретической и прикладной точки зрения свойство неманипулируемости и при этом имеющий меньшую, по сравнению с произвольным устранением безразличий, вероятность получения неэффективного паросочетания.В разделе 2.4 дано описание разработанного комплекса программ. В программном комплексе реализованы механизмы построения устойчивого паросочетания, предложенные в главе 2.

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

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