Диссертация (1137447), страница 6
Текст из файла (страница 6)
В литературе рассматриваются модели, в которыхпредпочтения игроков заданы произвольными частичными порядками. Большое внимание и большое количество результатов полученодля частного случая, когда предпочтения заданы слабыми порядками.Этот частный случай интересен тем, что такие предпочтения нередковстречаются в практических приложениях, например, в задаче распределения учеников по школам.Определение 1.12. Слабым порядком называется бинарное отношение , заданное на множестве , если оно является частичным по-42рядком и удовлетворяет условию отрицательной транзитивности, т.е.∀, , : , верно, что .В случае, когда предпочтения заданы частичными порядками,устойчивое паросочетание всегда существует [9].
Однако множествоустойчивых паросочетаний, вообще говоря, не является решеткой. Более того, нарушаются доказанные выше свойства механизма отложенного принятия. Приведем простой пример, иллюстрирующий возникающие проблемы.Пример 1.5. Пусть = 1 , 2 , = {1 , 2 }. ≻1 и ≻2 пусты, чтоозначает, что и для 1 , и для 2 абитуриенты 1 и 2 между собойнесравнимы. Предпочтения абитуриентов таковы, что 1 1 2 ; 2 2 1 .В этой задаче существует два устойчивых паросочетания, назовем их1 и 21 (1 ) = 1 , 1 (2 ) = 2 ,1 (1 ) = 2 , 1 (2 ) = 1 .Паросочетание 1 доминирует по Парето с точки зрения абитуриентовпаросочетание 2 , однако с точки зрения вузов паросочетания несравнимы по Парето.
Таким образом, противоположность интересов, показанная в теореме 1.1.6 для случая предпочтений, заданных линейнымипорядками, здесь не сохраняется.В [27] было предложено изменить определение устойчивого паросочетания для случая, когда предпочтения не являются линейнымипорядками.
Помимо классической концепции устойчивости, предложено два новых понятия – супер-устойчивость и сильная устойчивость.43Отличия от классического определения устойчивого паросочетания вобоих случаях кроются в определении блокирующей пары.Определение 1.13. Блокирующая (в концепции супер-устойчивости)пара в паросочетании – это абитуриент и вуз , такие что () (вуз не менее предпочтителен, чем вуз, в который зачислен впаросочетании ) и выполнено одно из условий:∙ ∃ ′ ∈ () : ′ ≻ (один из абитуриентов, зачисленных в , непредпочтительнее, чем );∙ |() < |, ≻ (в вузе есть свободные места и абитуриент неявляется недопустимым).В концепции сильной устойчивости также требуют, чтобы либо (), либо ≻ ′ .Новое определение блокирующей пары является более слабым, чеморигинальное.
Легко показать, что как супер-устойчивое, так и сильноустойчивое паросочетание может не существовать – см. Пример 1.5.Однако показано, что когда предпочтения абитуриентов заданы линейными порядками, а предпочтения вузов заданы частичными порядками, и когда множество сильноустойчивых паросочетаний непусто, оно образует решетку [28] относительно отношений Паретодоминирования для каждой из сторон. Кроме того, если предпочтенияобеих сторон заданы частичными порядками, то множество сильноустойчивых паросочетаний может не образовывать решетку, но множество суперустойчивых паросочетаний (если оно непусто) [29] является решеткой относительно отношений Парето-доминирования сточки зрения каждой из сторон.
Предложенное изменение определе44ния устойчивого паросочетания позволяет получить красивые структурные результаты, но, в то же время, порождает серьезную проблемунесуществования решения. Кроме того, вызывает большие вопросытеоретико-игровая интерпретация такого определения устойчивости:если , понимать как безразличие игрока между альтернативам и (например, вуза между двумя абитуриентами), то почемупара блокирует паросочетание, когда одному из игроков, входящих впару, безразлично, вступать в блокирующую пару или остаться в текущем паросочетании? Соответственно, концепции супер-устойчивости исильной устойчивости, несмотря на важные теоретические результаты,не нашли пока большого отражения в прикладных задачах построенияраспределительных механизмов.Другое направление развития в моделировании предпочтений агентов связано с переходом от задания предпочтений бинарными отношениями к функциям выбора.
Впервые такой подход был предложен [7],и вскоре был серьезно развит в [23]. Расширяя возможности описания предпочтений, авторы расширяют и понятие обобщенного паросочетания. В этих моделях каждая пара в обобщенном паросочетанииимеет дополнительный (и вообще говоря, изменяемый) набор характеристик. Например, абитуриент может поступать в вуз с получениемобщежития или без получения общежития. Соответственно, функциивыбора (с помощью которых моделируются предпочтения сторон в модели) заданы на множестве таких «контрактов». В [23] и последующих работах [30,31], моделирующих предпочтения агентов с помощьюфункций выбора, обычно предполагается, что функция выбора удовлетворяет одному из вариантов свойства заменяемости (substitutability).45При выполнении предположений о заменяемости контрактов и соответствующих свойствах функций выбора устойчивое паросочетаниесуществует.
В зависимости от строгости сделанного предположенияо замещении показывают, что множество устойчивых паросочетанийобразует решетку [23, 31] и существуют аналоги механизма отложенного принятия Гейла-Шепли, порождающие лучшее для абитуриентови лучшее для вузов паросочетания; в то же время при более слабых предположениях [32] множество устойчивых паросочетаний также непусто, но не образует рещетку в соответствии с отношениемпредпочтения ни одной из сторон.1.3.2Механизмы построения устойчивого паросочетанияДля классической задачи в разделе 1.1 настоящей главы был описан механизм отложенного принятия, предложенный Гейлом и Шепли,и позволяющий построить устойчивое паросочетание в любое задаче.Построенное паросочетание является наиболее предпочтительным извсех устойчивых с точки зрения предлагающей стороны.
Кроме того,агенты предлагающей стороны не могут манипулировать предпочтениями.В случае, когда предпочтения заданы не линейными порядками, аслабыми порядками, частичными порядками или описываются функциями выбора, также существуют аналоги механизма отложенногопринятия [9, 31, 33](причем обеих версий, для каждой из предлагающих сторон). Фактически работа таких механизмов состоит из двухдействий: во-первых, если в предпочтениях существуют безразличия,46то они каким-либо образом устраняются; во-вторых, выполняются действия, предусмотренные механизмом отложенного принятия.Существенной проблемой здесь является то, что, в отличие от классической задачи в случае более общих предпочтений при использовании механизма отложенного принятия, как уже отмечалось выше, может быть построено неэффективное паросочетание, и даже для «предлагаюшей» стороны сообщение истинных предпочтений больше не является слабо доминирующей стратегий, т.е.
появляются возможностидля манипулирования предпочтениями. Если вернуться к Примеру1.5, нетрудно заметить, что обоим абитуриентам выгодно исказитьсвои предпочтения и сообщить, что допустимым для каждого из нихявляется только первый от предпочтительности вуз. В таком случаемеханизм отложенного принятия никогда не построит неэффективноеустойчивое паросочетание, как бы ни были устранены безразличия впредпочтениях вузов.В [34] был предложен критерий эффективности устойчивого паросочетания при предпочтениях, заданных слабыми порядками, и механизм, позволяющий построить гарантированно эффективное паросочетание. Недостатком предложенного механизма является то, что онсоздает возможности для манипулирования предпочтениями игрокамис обеих сторон.Оказывается, что в случае, когда предпочтения вузов заданы слабыми порядками (а, значит, и в более общих случаях) верно следующее.Теорема 1.3.1.
[35] Пусть предпочтения вузов заданы слабымипорядками, а предпочтения детей – линейными порядками. Тогданеманипулируемый механизм не может доминировать (по Парето с47точки зрения абитуриентов) никакой механизм отложенного принятия с предлагающими абитуриентами и заданной процедуройустранения безразличий.Таким образом, эффективный неманипулируемый устойчивый механизм можно искать только в классе механизмов отложенного принятия с различными способами устранения безразличий. В [36] этотрезультат был расширен для менее строго определения устойчивогопаросочетания.В [37] был предложен альтернативный подход к проблеме.
А именно, были предложены ограничения на профили предпочтений вузов иабитуриентов, при выполнении которых неманипулируемый, устойчивый и эффективный механизм. Для случая, когда предпочтения удовлетворяют свойству «ties in bottom», т.е. неразличимы друг с другомтолько несколько наименее предпочтительных альтернатив, полученынеобходимые и достаточные условия существования такого механизма. Недостатком полученных результатов является то, что полученные условия накладываются не на предпочтения отдельных агентов, аименно на профиль целиком, что затрудняет применение полученныхрезультатов в прикладных задачах.1.4Анализ централизованных механизмов распределения, используемых на практикеЗадача построения паросочетания при отсутствии денежных трансфертов между участниками возникает в большом количестве практических ситуаций: распределение учеников по школам, абитуриентовпо вузам, стажеров по организациям или отделам внутри организации,48молодых докторов по больничным интернатурам и т.п.
Во многих случаях для решения задачи распределения используется централизованный механизм, т.е. предпочтения сторон и информация о квотах собираются некоторым единым органом (вручную или с помощью информационной системы) и затем уже строится паросочетание (распределение). В других случаях используются псевдо-централизованные механизмы, когда устанавливаются единые правила взаимодействия междусторонами (например, абитуриентами и вузами), но итоговое распределение определяется в результате индивидуальных (хотя и ограниченных регламентом) взаимодействий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
