Диссертация (1137447), страница 4

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

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

Под выигрышем вданном случае понимается пара, которую получает игрок. Каждый игрок ∈ сравнивает выигрыши, получаемые в разных коалициях, всоответствии со своим отношением предпочтения .Определение 1.6. [14] Вектор выигрышей принадлежит C-ядруигры (, ), если он не доминируется никаким другим достижимымвектором выигрышей. Иначе говоря, не существует коалиции игроков ′ ⊂ и достижимого вектора выигрышей ′ , таких что ∀ ∈ ′′ .Теперь докажем следующее утверждение:Теорема 1.1.2.

[15] При каждом профиле предпочтений , состоящем из линейных порядков, вектор выигрышей (супругов) принадлежит ядру игры () тогда и только тогда, когда соответствующее ему паросочетание является устойчивым.Доказательство. 1. Ядро => устойчивость. Если паросочетание принадлежит ядру, то ни одна коалиция не может отклониться и получить для себя лучшие выигрыши, то есть лучшие пары. В том числене может отклониться ни одна коалиция, состоящая из одного игрока (требование индивидуальной рациональности) или двух игроков(требования попарной устойчивости). Следовательно, любому векторувыигрышей из ядра игры соответствует устойчивое паросочетание.2. Устойчивость => ядро.

Если паросочетание устойчиво, но существует коалиция, состоящая из более чем двух игроков, которой25выгодно отклониться от паросочетания и составить пары между собой, то в новом распределении, построенном внутри коалиции , длялюбой пары (, ) : (, ) = и (, ) = должно быть верно,что () и (). Однако в таком случае и образуютблокирующую пару в паросочетании . Противоречие.1.1.2Структура множества устойчивых паросочетанийЧто изменится, если организатор механизма захотел действоватьв интересах одной из сторон (например, женщин)? Можно ли выделить паросочетания, которые понравятся одной из сторон (например,женщинам ) больше остальных, или, говоря более строго, будутПарето-эффективными для женщин? Если вернуться к рассмотренному выше Примеру 1.2, то легко заметить, что устойчивое паросочетание, получившееся в результате применения механизма отложенногопринятия с предлагающими женщинами, является для них наилучшим из трёх возможных устойчивых паросочетаний.

Действительно,в паросочетании каждая женщина поставлена в пару с наиболее предпочтительным для неё мужчиной . Оказывается, что это неслучайное совпадение.Теорема 1.1.3.[2] При каждом профиле предпочтений , со-стоящем из линейных порядков, устойчивое паросочетание ,полученное при применении механизма отложенного принятияс предлагающими женщинами, является единственным Паретоэффективным для среди всех устойчивых паросочетаний.В силу симметрии аналогичное утверждение верно для мужчин.26Итак, паросочетание, полученное в результате выполнения механизма отложенного принятия, является наилучшим возможным устойчивым паросочетанием для той стороны, которая делает предложения.

Акак обстоят дела с интересами противоположной стороны? Оказывается, паросочетание является наихудшим из всех устойчивых длямужчин.Теорема 1.1.4. [2] Паросочетание слабо доминируется по Парето (для мужчин) любым другим устойчивым паросочетанием.Таким образом, устойчивых паросочетаний существует несколько;одно из них ( ) является Парето-оптимальным для мужчин (помножества ) и наихудшим для женщин (подмножества ), т.е. слабодоминируется по Парето для женщин любым другим устойчивым паросочетанием; другое ( ), наоборот, – наихудшим для мужчин инаилучшим для женщин. Непосредственно из этого можно сделатьтакой вывод:Следствие 1.1.

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

Оказывается, верно чуть более общее утверждение.Теорема 1.1.5. [16] Пусть заданы множества и и профильпредпочтений . Если в некотором устойчивом паросочетании 27для ∈ ∪ верно, что () = (будем говорить, что – одинок), то и в любом другом устойчивом паросочетании ′ одинок,т.е. ′ () = .Следующий интересный вопрос состоит в том, как устроено множество устойчивых паросочетаний. Оказывается, на множестве устойчивых паросочетаний можно задать отношение частичного порядка так,что будет образована решетка. Дадим определения частичного порядка и решетки.Определение 1.7. [13] Бинарное отношение на множестве является частичным порядком, если оно удовлетворяет свойствам∙ антирефлексивности, т.е.

∀ ∈ верно, что ;∙ транзитивности,∙ асимметричности.Определение 1.8. [17, 18] Решетка, или структура, – это множество , на котором задан частичный порядок ≻, такие что ∀, ∈ {, } ∈ и {, } ∈ .Пусть отношение частичного порядка ≻ – это отношение слабого доминирования по Парето для подмножества агентов (мужчин).Возьмём два различных устойчивых паросочетания, и ′ , и определим для них операцию нахождения точной верхней грани. Точнаяверхняя грань для двух устойчивых паросочетаний и ′ – это такое̂︀, чтоотображение ′̂︀():= (, ) =⎧⎪⎪⎨(),если () ′ () или () = ′ (),⎪⎪⎩(′ ),если () ′ ().28̂︀ поставим в пару более предпочтительИначе говоря, каждому в ̂︀ную из двух его партнерш в и ′ .

По построению очевидно, что доминирует по Парето для подмножества , мужчин, и паросочетание , и паросочетание ′ .По аналогии определим теперь операцию нахождения точной нижнейграни.′ˇ() := (, ) =⎧⎪⎪⎨(),если ′ () () или () = ′ (),⎪⎪⎩(′ ),если ′ () ().Заметим, что оба определения могут быть симметрично переформулированы для подмножества . Возникает закономерное сомнение:̂︀ и будут ли ˇ паросочетаниями, и если да, будут ли они устойчивыми? Иначе говоря, действительно ли предложенные операции определены на множестве устойчивых паросочетаний? Теперь сформулируемтеорему:̂︀ и Теорема 1.1.6.

[3, 9] ˇ, найденные в соответствии с данными выше определениями, являются паросочетаниями, и притомустойчивыми.̂︀Доказательство. 1. Если () = , то в ()=иˇ() = в силуутверждения теоремы 1.1.5.̂︀ не является паросочетанием (см. определение). Значит,2. Пусть некоторая женщина получает более одного супруга. Такое может произойти, если одновременно и ′ считают лучшейиз двух своих супруг из и ′ . Предположим (без ограниченияобщности), что () = , и ′ (′ ) = . Однако предпочтения заданы линейным порядком, поэтому она обязательно предпо29читает одного из мужчин другому. Пусть ′ , тогда, с учётомтого, что ′ (), в паросочетании ′ и образуют блокирующую пару.

Значит, ′ не является устойчивым. Случай ′ ̂︀ являетсясимметричен. Получаем противоречие, следовательно, паросочетанием.̂︀ будет устойчивым. Пусть это не3. Докажем, что паросочетание так и в паросочетании существует блокирующая пара и . То̂︀гда предпочтения должны быть устроены так, что ().̂︀Поскольку ()является наиболее предпочтительной из () и′ (), верно, что () и ′ (). Заметим, что не может стоять в паре с ни в , ни в ′ . Из устойчивости этихпаросочетаний следует, что и не образовывали ни в одномиз них блокирующую пару. Значит, () и () ′ .

Но па̂︀ выбирается из этих двоих (либора в новом паросочетании (), либо ′ ()). Таким образом, в любом случае женщина необразует с мужчиной блокирующую пару. Замечание: следуеттакже показать, что не могут образовывать блокирующую паруженщина и мужчина , являющегося одиноким. Схема доказа̂︀ не содержит блокирующейтельства аналогична. Следовательно, пары. Индивидуальная рациональность верна автоматически.̂︀ присваивает каждой ∈ худ4. Докажем, что паросочетание шего из ее партнеров в и ′ . Без ограничения общности поло̂︀жим, что ()= (). Предположим противное: пусть ()̂︀ верно, что ′ (). ′ (). Заметим, что по построению и не поставлены в пару в паросочетании ′ и образуют в нем30блокирующую пару; следовательно, паросочетание ′ не являетсяустойчивым.

Противоречие.Из части 4 доказательства следует, что паросочетание, являющеесяточной верхней гранью с точки зрения мужчин ( ), является точнойнижней гранью с точки зрения женщин ( ). В силу симметрии изэтого сразу следует справедливость утверждений теоремы.Помимо доказанной теоремы 1.1.6 можно сформулировать следующее полезное утверждение, являющееся ее следствием.Следствие 1.2. Рассмотрим два устойчивых паросочетания и ′ .Пусть ′ = { ∈ : () ′ ()}, ′ = { ∈ : ′ () ()}.Тогда в обоих паросочетаниях мужчины из ′ поставлены в парытолько с женщинами из ′ .1.1.3Сообщение предпочтений и манипулирование при построении обобщённых паросочатенийУже довольно много было сказано о структуре множества устойчивых паросочетаний, однако хотелось бы понять, насколько концепция поиска устойчивых паросочетаний заслуживает доверия.

Ведь модель рассматривает агентов, обладающих предпочтениями, а концепция поиска устойчивого паросочетания предполагает, что агенты обладают свободой воли при сообщении своих предпочтений и при принятии/непринятии предлагаемого паросочетания. Сформулируем вопросследующим образом: можно ли разработать механизм, выполнение которого приводит к устойчивому паросочетанию (будем называть егодля краткости устойчивым механизмом), при использовании которого для всех агентов наиболее предпочтительно сообщать свои истин31ные предпочтения? К сожалению, ответ на этот вопрос – отрицательный [4, 5]. Для доказательства приведем следующий простой пример.Пример 1.3.

[5] Пусть = {1 , 2 }, = {1 , 2 }. Предпочтенияданы в таблице 1.5.Истинные предпочтения1 : 1 , 2 1 : 2 , 12 : 2 , 1 2 : 1 , 2Искаженные предпочтения 11 : 1 , 2 1 : 2 , 12 : 2 , m2 2 : 1 , 2Искаженные предпочтения 21 : 1 , 2 1 : 2 , 12 : 2 , 1 2 : 1 , w2Таблица 1.5: Предпочтения сторон в Примере 1.3.При истинных предпочтениях в данном примере существует дваустойчивых паросочетания и : (1 ) = 1 , (2 ) = 2 (1 ) = 2 , (2 ) = 1Попытаемся построить устойчивый механизм.

Заметим, что устойчивый механизм обязан выбирать какое-то устойчивое паросочетаниедля любого профиля предпочтений. Если для какого-то профиля предпочтений существует единственное устойчивое паросочетание, то любой устойчивый механизм выбирает это паросочетание.Рассмотрим устойчивый механизм, который при данных предпочтениях выбирает паросочетание . Заметим, что если бы предпочтения 1 изменились так, как указано в таблице, то при таком новом32профиле предпочтений существовало бы единственное устойчивое паросочетание , которое выбиралось бы любым устойчивым механизмом.

Получается, что если истинные предпочтения 1 соответствуют исходному условию, то результат с искаженными предпочтениямиоказывается для него предпочтительнее, чем результат, получаемый систинными предпочтениями. Следовательно, построенный нами устойчивый механизм не удовлетворяет желаемому условию.Рассмотрим тогда устойчивый механизм, который при данных в таблице истинных предпочтениях выбирает другое устойчивое паросочетание . Очевидно, что здесь возможны симметричные рассужденияоб искажении предпочтений, см. искаженные предпочтения 2 в таблице.

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

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