Диссертация (1137447), страница 13
Текст из файла (страница 13)
Более того, с помощью этой теоремы получен устойчивыйи эффективный (для абитуриентов) механизм построения паросочетания:1. Построить произвольное линейное расширение для предпочтенийабитуриентов.2. Применить механизм отложенного принятия с предлагающимиабитуриентами и получим некоторое устойчивое паросочетание.3.
Выполниь поиск устойчивого улучшающего цикла в построенномпаросочетании. Если он существует, произвести обмен местами ввузах в соответствии с циклом. Повторять этот шаг до тех пор,пока построение нового цикла станет невозможным.По теореме 2.2.4 данное паросочетание будет устойчивым и эффективным для абитуриентов. К сожалению, такой механизм не устойчивк манипулированию со стороны абитуриентов.
В [34] возможностьманипулирования абитуриентами показана для случая, когда предпочтения являются слабыми порядками, поэтому, естественно, манипу91лирование возможно и в более общем случае предпочтений, заданныхинтервальными порядками.2.3Неманипулируемый механизм со обратным устранениембезразличийПостроенные выше для случая простейших полупорядков и интервальных порядков механизмы, основанные на случайном устранениибезразличий и поиске УУЦ, всегда находят эффективное для абитуриентов паросочетание. Однако существенным недостатком этих механизмов, особенно при практическом внедрении на небольших рынках,является их неустойчивость к манипулированию.
В этом разделе будетпредложен новый механизм, основанный на механизме отложенногопринятия и специальном способе устранения безразличий в предпочтениях вузов. Достоинством предлагаемого механизма является то,что он порождает неэффективные для абитуриентов паросочетания сменьшей вероятностью по сравнению со случайным устранением безразличий в предпочтениях вузов. При этом, поскольку устранение безразличий в нашем механизме будет проводиться до реализации механизма отложенного принятия, предлагаемый механизм будет устойчивк манипулированию, как и исходный механизм отложенного принятия в случае предпочтений, заданных линейными порядками.
Заметим, что для сохранения устойчивости механизма к манипулированиюсо стороны абитуриентов необходимо при устранении безразличий неиспользовать информацию о предпочтениях абитуриентов. Действительно, если такая информация используется, то предпочтения абитуриента оказывают влияние на принимаемое решение (выбираемое92паросочетание) не только в рамках механизма отложенного принятия,но и при устранении безразличий.Если предпочтения вузов заданы слабыми порядками, то без учётапредпочтений абитуриентов никаких дополнительных выводов сделатьнельзя. Более того, из [35] известно, что никакой механизм отложенного принятия с предлагающими абитуриентами и некоторой схемойустранения безразличий не доминируется другим неманипулируемыммеханизмом.Если же предпочтения вузов являются интервальными порядками,то неразличимые между собой (с точки зрения отношения предпочтения вуза) абитуриенты не обязательно являются эквивалентными.Поэтому доля профилей, на которых механизм отложенного принятияпостроит неэффективное паросочетание, может отличаться в зависимости от способа устранения безразличий в предпочтениях вузов.В предыдущем разделе было показано, что при любом неэффективном для абитуриентов паросочетании в графе существует устойчивый улучшающий цикл.
Рассмотрим произвольный вуз . Чем меньшеабитуриентов «указывают» на данный вуз в графе (т.е. создаютребра в данном графе), тем менее вероятно (при прочих равных условиях), что найдется устойчивый улучшающий цикл.Итак, пусть задано множество абитуриентов и множество вузов , эти множества конечны. Предпочтения абитуриентов являютсялинейными порядками, предпочтения вузов ≻ – простейшими полупорядками. Квота каждого вуза = 1.В дальнейшем будем рассматривать некоторый вуз , считая, чтопредпочтения остальных вузов и всех абитуриентов случайны. Пусть93 , предпочтения абитуриента – это дискретная случайная величина, равномерно распределенная на множестве всех линейных порядков, заданных на ∪ {}. ≻′ , предпочтения вуза ′ – это дискретнаяслучайная величина, равномерно распределенная на множестве всехпростейших полупорядков, заданных на ∪ {′ }. Распределения всехслучайных величин независимы.Пусть используется некоторый механизм, который строит устойчивое паросочетание по заданному профилю предпочтений.
Нас будетинтересовать вероятность того, что, при зафиксированном отношениипредпочтения вуза , паросочетание, построенное механизмом, окажется эффективным для абитуриентов. Фактически в нашем случаеуказанная вероятность соответствует доле профилей, на которых механизм с конкретной процедурой устранения безразличий построитнеэффективное для абитуриентов паросочетание.Рассмотрим следующий пример.Пример 2.4. Имеется три абитуриента: = {1 , 2 , 3 }, а отношениепредпочтения вуза устроено следующим образом:1 ≻ 3 , 1 (≻ )2 , 2 (≻ )3 .Квота вуза = 1.
Предпочтения остальных вузов произвольным образом преобразованы в линейные порядки.Был применен механизм отложенного принятия с предлагающимиабитуриентами, и в течение работы механизма вуз получил предложения (одновременно или на разных шагах) от всех трёх абитуриентов.94Рассмотрим три возможных линейных расширения для отношенияпредпочтения вуза и последствия применения этих расширений сточки зрения неэффективности:∙ 1 ≻′ 2 ≻′ 3 .
В этом случае 1 будет зачислен в вуз . Двадругих абитуриента получат отказ в этом вузе и, следовательно,каждый из них будет зачислен в менее предпочтительный вуз.Поскольку 2 и 3 неразличимы между собой, то они оба создадутдуги от «своих» вузов к вузу в графе улучшений .∙ 1 ≻′ 3 ≻′ 2 . Также как и в предыдущем случае, 1 будет зачислен в вуз и оба абитуриента, 2 and 3 , создадут дуги в .∙ 2 ≻′ 1 ≻′ 3 .В этом случае место в вузе получит 2 . В этом случае только 1 создаст дугу в графе (Поскольку 1 предпочтительнее, чем 3 при исходных предпочтениях вуза , 3 не можетсоставить пару с вузом в устойчивом улучшающем цикле).В последнем случае в графе появляется только одна дуга, в то времякак в первых двух случаях появляется две дуги.
Таким образом, припрочих равных условиях, вероятность существования УУЦ в последнем случае будет меньше.Для того, чтобы сформулировать общий результат, введем понятияантицепи и максимальной антицепи в бинарном отношении ≻.Определение 2.5. Антицепью в бинарном отношении ≻⊆ 2 называется подмножество ′ ∈ , такое что для любых двух элементов′ , ′′ ∈ ′ верно что ′ (≻)′′ . Антицепь ′ называется максимальной антицепью, если она не является подмножеством никакой другойантицепи.95Теперь сформулируем основной результат данного раздела.Теорема 2.3.1. Вероятность получения неэффективного для абитуриентов паросочетания при использовании механизма отложенного принятия с предлагающими абитуриентами наименьшая, если устранение безразличий проведено по следующей процедуре:∙ Шаг 1. Рассмотрим исходное отношение предпочтения ≻ и«лучшую» (т.е. состоящую из таких альтернатив, множество более предпочтительных элементов для которых пусто)максимальную антицепь 1 ={1 , ..., }.
Пусть ≻′ , если( ≻ ) ⊂ ( ≻ ), т.е. доминирует в новом преобразованном отношении предпочтения ≻′ , если множество альтернатив, доминируемых альтернативой строго входит во множество альтернатив, доминируемых альтернативой . Всеостальные безразличия между альтернативами во множестве1 устраняются произвольным образом.∙ Шаг ∈ [2, ]. Рассмотрим «лучшую» максимальную антицепь во множестве ∖ (∪−1=1 ). Повторим процедуру устраненияпредпочтений, описанную на шаге 1, для антицепи . Повторим шаги до тех пор, пока не переберем все элементы множества .∙ Шаг + 1.
Для любых элементов ∈ , ′ ∈ положим ≻′ ′ , если < .Доказательство. Пусть – множество всех абитуриентов, которыеподавали заявление в вуз хотя бы на одном шаге механизма отложенного принятия с предлагающими абитуриентами. Заметим, что если96предпочтения остальных вузов и абитуриентов сформированы случайно, к предпочтениям всех вузов, кроме , применена любая нейтральная (не учитывающая «имена» абитуриентов) процедура устранениябезразличий, то вероятности получения какого-то конкретного набора предложения (множества ) не зависят от предпочтений самоговуза.
Более того, для любых двух множеств абитуриентов ′ ⊆ и′′ ⊆ равной мощности |′ | = |′′ | вероятность того, что = ′равна вероятности того, что = ′′ . Действительно, если это былобы неверно, это означало бы, что вероятность получения конкретногонабора предложений зависит от имен абитуриентов.Способ устранения безразличий повлияет на вероятность построения неэффективного паросочетания только тогда, когда самый слабый из зачисленных в вуз абитуриентов (назовем его ) неразличим скем-то из тех, кто тоже подавал заявление в вуз (то есть делал предложение в течение работы механизма), но в итоге не был зачислен.Поскольку ≻ является простейшим полупорядком, возможны следующие ситуации:1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
