Диссертация (1137447), страница 10
Текст из файла (страница 10)
существуетне более одного элемента, находящегося в отношении безразличияодновременно и с , и с 69∙ слабому многообразию контуров: ∀, (≻ ) ̸= (≻ ) ∨ ( ≻) ̸=( ≻).Отношения предпочтения, подобные простейшим полупорядкам,оказываются довольно естественными в том случае, когда рассматриваются предпочтения вуза на множестве абитуриентов, формируемыена основе баллов, полученных абитуриентами за экзамен.
Рассмотримпример.Пример 2.1. Три абитуриента, 1 , 2 , 3 , подали заявления на факультет экономики. Набранные ими баллы составили 65, 63, и 61 балл из100 соответственно. Предпочтения факультета с учётом набранныхабитуриентами баллов могут быть построены исходя из следующихсоображений. Во-первых, практика рассматриваемого факультета показывает, что разницу в 2 балла между результатами абитуриентовследует считать несущественной, поскольку такое небольшое различие может быть связано с везением или быть попросту случайным.По этой причине абитуриентов 1 и 2 нельзя однозначно сравнить поуровню подготовки; они будут признаны неразличимыми (равно как2 и 3 ).
В то же время разница в 3 и более набранных балла оказывается, как правило, показателем отличия в уровне подготовке, и врядли может быть объяснена случайностью. Таким образом, факультетбудет считать абитуриента 1 более подготовленным, чем абитуриента 3 . Получено отношение предпочтения на множестве абитуриентов,являющееся простейшим полупорядком.Таким образом, простейший полупорядок – это наиболее слабоеобобщение линейного порядка, в котором между парой альтернатив,70одна из которых предпочтительнее другой, может быть вставленатолько одна альтернатива, неразличимая с ними обеими.Заметим, что вуз принимает, в общем случае, более одного абитуриента, поэтому необходимо также задать предпочтения вузов на множестве всех подмножеств абитуриентов.
Эти предпочтения не определяются явно. Здесь используется стандартное предположение теорииобобщенных паросочетаний: предпочтения на множестве всех подмножеств абитуриентов соответствуют предпочтениям на множестве абитуриентов, т.е. удовлетворяют следующему требованию:∀ ∈ , ∀′ ⊂ , ∀1 , 2 ∈ ∖ ′ : 1 ≻ 2 верно, что ′ ∪ {1 } ≻′ ∪ {2 }.2.1.1Существование устойчивого паросочетанияИз [2] известно, что в случае предпочтений, заданных линейнымипорядками, всегда существует устойчивое паросочетание.
Легко показать, что устойчивое паросочетание всегда существует и в нашеймодифицированной модели.Теорема 2.1.1. Если предпочтения абитуриентов заданы линейными порядками, а предпочтения вузов – простейшими полупорядками, то устойчивое паросочетание всегда существует.Доказательство. Для отношения предпочтения, являющего простейшим полупорядком, можно построить линейное расширение, т.е. такое отношение предпочтения, являющееся линейным порядком, чтовсе пары, входящие в исходное бинарное отношение, будут сохранены в преобразованном, но новое отношение станет связным.
Например, пусть истинные предпочтения вуза устроены так, что 1 (≻ )2 ,712 (≻ )3 , 1 ≻ 3 , тогда линейное расширение ≻′ может быть, например, таким: 1 ≻′ 2 , 2 ≻′ 3 , 1 ≻′ 3 .Покажем, что паросочетание, которое является устойчивым при линейных расширениях, является устойчивым и при исходных предпочтениях. Ясно, что если индивидуальная рациональность не нарушенапри расширенных предпочтениях, то не нарушена и для исходныхпредпочтений. Далее, если при линейном расширении не существуетпары, абитуриента и вуза, где вуз готов был бы взять абитуриента насвободное место, то её не найдется и при исходных предпочтенияхв силу того, что абитуриент не может быть безразличен для вуза посравнению с незаполненным местом ни при исходных, ни при преобразованных предпочтениях.
Наконец, если при линейном расширениине существует блокирующей пары, в которой вуз строго предпочитал бы одного из незачисленных абитуриентов уже зачисленному, тотакой блокирующей пары тем более не найдется при возврате к исходному профилю предпочтений, включающему простейшие полупорядки(число строго предпочитаемых друг другу абитуриентов уменьшится).Механизм отложенного принятия позволяет найти устойчивое паросочетание для любого профиля предпочтений, состоящего из линейных порядков.
Следовательно, устойчивое паросочетание всегда существует.Возникает следующий естественный вопрос: можно ли построитьвсе устойчивые паросочетания, если будем рассматривать различныелинейные расширения исходных предпочтений вузов? Отношение ≻′является линейным расширением отношения ≻ , если оно является72линейным порядком, и ∀, ( ≻ ) ⇒ ( ≻′ ). Фактически припостроении линейного расширения исходное отношение предпочтениямодифируется таким образом, чтобы любые две альтернативы былиразличимы между собой. Оказывается, что можно показать следующее.Теорема 2.1.2.
Для любого устойчивого паросочетания в моделис предпочтениями, заданными простейшими полупорядками, можно найти такой состоящий из линейных порядков профиль предпочтений вузов ⪰′ (где каждое отношение предпочтения ≻′ является линейным расширением отношения ≻ ), что паросочетание является устойчивым при этом профиле ⪰′ .Доказательство. Рассмотрим паросочетание , которое устойчивопри исходном профиле предпочтений(⪰, ).
Построим такой профильлинейных расширений предпочтений вузов ⪰′ , при котором паросочетание останется устойчивым. Заметим, что выбор линейного расширения для одного из вузов никак не ограничивает возможности выборалинейного расширения для других вузов, т.к. при проверке устойчивости паросочетания важны только предпочтения вуза и абитуриентов,желающих попасть в этот вуз.Пусть абитуриент зачислен в вуз в паросочетании . В силусвойств простейшего полупорядка ≻ любой элемент множества может состоять в отношении безразличия (≻ ) не более чем с двумядругими элементами.
Таким образом, может существовать не болеедвух абитуриентов , таких что (≻ ).В силу устойчивости паросочетания любой абитуриент , неразличимый по предпочтительности для вуза с каким-либо из зачис73ленных абитуриентов и предпочитающий вуз по сравнению с предписанным ему вузом (), должен быть также неразличим с такимабитуриентом (назовем его «последним по предпочтительности»),который имеет наибольшее множество (≻ ) среди всех абитуриентовв (). В силу свойств простейшего полупорядка не может существовать более двух абитуриентов (назовем их ′ и ′′ ), неразличимыхс последним абитуриентом и не зачисленных в вуз , присутствиекоторых необходимо учитывать при построении линейного расширения для простейшего полупорядка.
Пусть ′ (≻ ), (≻ )′′ , ′ ≻ ′′В этом случае отношение предпочтения ≻′ может быть построенотак, что ≻′ ′ ≻′ ′′ . Так как абитуриент является последнимпо предпочтительности среди зачисленных в вуз , абитуриенты ′ и′′ окажутся в линейном расширении ниже по предпочтительности,чем любой из зачисленных в вуз студентов. Остальные безразличияв предпочтениях могут быть устранены произвольным образом.
Паросочетание останется устойчивым, поскольку в результате переходак таком линейному расширению не будет образовано блокирующихпар.2.1.2Механизм отложенного принятия и паросочетания, неэффективныедля абитуриентовСледующее важное свойство устойчивых паросочетаний – Паретооптимальность. В классической модели, где предпочтения заданы линейными порядками, все паросочетания являются эффективными, адля абитуриентов существует наилучшее устойчивое паросочетание.При разработке механизмов на практике интересы абитуриентов, какправило, учитываются в первую очередь. Как следует из доказатель74ства Теоремы 2.1, для поиска устойчивого паросочетания можно использовать модифицированную процедуру с устранением безразличий,предложенную в [33].
Однако важно понимать, будем ли мы в этомслучае получать эффективное для абитуриентов паросочетание.Пример 2.2. Рассмотрим следующий простой пример с тремя абитуриентами = {1 , 2 , 3 } и тремя вузами = {1 , 2 , 3 }, в каждом изкоторых квота равна 1, т.е. имеется по одному месту.Таблица 2.1: Предпочтения для примера 2.21 : 1 2 3 1 : 3 ≻1 1 , 3 (≻1 )2 , 2 (≻1 )12 : 2 1 3 2 : 1 ≻2 2 , 1 (≻2 )3 , 3 (≻2 )23 : 2 3 1 3 : 1 ≻3 3 , 1 (≻3 )2 , 2 (≻3 )3Найдем устойчивые паросочетания, применив процедуру с предварительным устранением безразличий в предпочтениях. Сравним результат работы механизма в случае двух разных профилей линейныхрасширений: ⪰′ и ⪰′′ .Пусть ⪰′ таково, что 1 ≻′2 2 ≻′2 3 .
На первом шаге 1 подаётзаявление в 1 , а абитуриенты 2 и 3 - в 2 . Вуз 2 , получив двазаявления на одно место, отклоняет заявление 3 (в соответствии срасширением предпочтений). Тогда 3 подаёт заявление в вуз 3 и наэтом работа механизма завершена. Найдено устойчивое паросочетание (см. Таблицу 2.2).Пусть ⪰′′ таково, что 1 ≻′′2 3 ≻′′2 2 , и 3 ≻′′1 2 ≻′′1 1 . На первомшаге 1 подаёт заявление в 1 , а абитуриенты 2 и 3 - в 2 . Вуз 2 ,получив два заявления на одно место, отклоняет заявление 2 (в соответствии с расширением предпочтений). Тогда абитуриент 2 подаётзаявление в вуз 1 .
Вуз 1 , получив два заявления на одно место, отклоняет заявление 1 (в соответствии с расширением предпочтений).75Таблица 2.2: Устойчивые паросочетания для Примера 2.2112 3 1 2 32 3 2 1 3Теперь 1 подаёт заявление в вуз 2 . Вуз 2 , снова имеющий избытокзаявлений, отклоняет заявление 3 . Наконец, 3 подаёт заявление ввуз 3 и на этом работа механизма завершается. Найдено устойчивоепаросочетание (см. Таблицу 2.2).Нетрудно заметить, что с точки зрения абитуриентов паросочетание лучше, чем .
Действительно, для абитуриента 1 вуз 1 предпочтительнее, чем 2 , а для абитуриента 2 , наоборот, вуз 2 предпочтительнее, чем 1 . Третий абитуриент зачислен в один и тот же вуз в обоихпаросочетаниях.Этот простой пример показывает, что даже при использованиипроцедуры отложенного принятия, ориентированной на абитуриентов, могут быть построены паросочетания, не являющиеся Паретооптимальными для абитуриентов. Наш следующий результат позволяет установить критерий для проверки эффективности для абитуриентов устойчивого паросочетания, а также построить механизм трансформации произвольного устойчивого паросочетания в эффективноедля абитуриентов.2.1.3Устойчивые улучшающие циклы и построение эффективного дляабитуриентов устойчивого паросочетанияЭрджин и Эрдил [34] первыми ввели определение устойчивогоулучшающего цикла (Stable Improvement Cycle, SIC).76Для того, чтобы дать определение устойчивого улучшающего цикла, введем дополнительные обозначения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
