Диссертация (1137447), страница 3
Текст из файла (страница 3)
Deferred AcceptanceMechanism). Существуют две симметричные версии механизма, отличающиеся тем, какое из подмножеств вершин ( или ) имеетпреимущество. Рассмотрим версию, где преимущество имеет подмножество (мужчины). Эту версию механизма будем называть механизмом отложенного принятия с предлагающими мужчинами. Механизм состоит из повторяющихся однотипных шагов, по итогам каждого из которых строится временное паросочетание . В течение работы механизма постепенно пополняется множество – множествомужчин, которые не будут поставлены в пару в итоговом устойчивомпаросочетании.1.1 Каждому ∈ поставим в пару наиболее предпочтительную1(в соответствии с отношением предпочтения ) женщину ∈1 .
Пусть 1 () = . Будем также говорить, что «сделал1предложение» .1.2 Изменим и достроим 1 так, чтобы это отображение стало индивидуально рациональным паросочетанием.Во-первых, чтобы избежать нарушения индивидуальной рациональности для женщин, если по итогам шага 1.1 = 1 (), но ( недопустим для ), изменим паросочетание и установим1 () = .17Во-вторых, заметим, что 1 не является взаимно-однозначнымотображением, т.к. одна и та же может быть поставлена в парунескольким .
Пусть 1 () = { : 1 () = }. Для каждой ,такой что |1 ()| > 0 выберем наиболее предпочтительного мужчину 1 из подмножества 1 () в соответствии с ее отношениемпредпочтения . Поставим в пару с 1 , т.е. 1 () = 1 . Вто же время, все остальные мужчины, выбравшие , не могутбыть поставлены с ней в пару, т.е. ∀′ ∈ 1 () ∖ {1 } установим(′ ) = ′ . Будем также говорить, что «отказалась от предложений» этих мужчин. Если 1 () = ∅, то 1 () = (опцияодиночества).Отображение 1 теперь является обобщенным паросочетанием,причем, по построению, не нарушает индивидуальной рациональности. Таким образом, по итогам первого шага построено временное паросочетание.2.1 Будем строить новое временное паросочетание 2 .
Пусть сначала2 = 1 . Для каждого ∈ , такого что 1 () = , найдем12, наиболее предпочтительную из множества ∖ {} в со2допустимаответствии с отношением предпочтения . Если 22для , установим 2 () = . Если недопустима для , то2 () = и пусть ∈ . Мужчин, добавленных во множество , в дальнейшем рассматривать не будем.2.2 Вновь изменим и достроим 2 так, чтобы оно стало паросочетанием. Повторим действия шага 1.2, основанные на предпочтениях женщин. Получим индивидуально рациональное паросочетание181 :2 :3 :4 :3 ,3 ,2 ,2 ,2 , 11 : 3 , 4 , 1 , 22 , 12 : 1 , 2 , 3 , (2 ),4(3 ),1 ,33 : 1 , 3 , 2 , 41 , (4 ), 3Таблица 1.1: Отношения предпочтения для Примера 1.12 ....n.1 Будем повторять шаги до тех пор, пока на некотором шаге неокажется, что все ∈ , такие что −1 () = , принадлежатмножеству .
Иначе говоря, работа механизма останавливается, когда каждый мужчина ∈ либо поставлен в пару снекоторой женщиной, либо получил отказ от всех допустимыхженщин.Полученное временное обобщенное паросочетание становитсяокончательным. Заметим, что поскольку множества и конечны,то механизм закончит свою работу за конечное число шагов. Полученное обобщенное паросочетание соответствует паросочетанию вграфе в следующем смысле: если () = , то = {, } ∈ .Следующий простой пример иллюстрирует работу механизма.Пример 1.1.
Пусть заданы множества мужчин = {1 , 2 , 2 ,4 } и женщин = {1 , 2 , 3 }. Применим механизм отложенного принятия, где мужчины первыми делают предложения, и найдемустойчивое паросочетание. Предпочтения даны в Таблице 1.1 (длякаждого ∈ ∪ просто запишем элементы в порядке убыванияпредпочтительности).Выполним шаги механизма отложенного принятия с предлагающими мужчинами191.1 1 и 2 делают предложение 3 , а 3 и 4 - 2 .1.2 3 получила два предложения.
В соответствии со своим отношением предпочтения 3 временно ставится в пару с 1 и откажетсяот предложения 2 . 2 отвергнет предложение 4 , т.к. этот мужчина не является для неё допустимым, и будет временно поставлена в пару с 3 и отвергнет предложение 4 .По итогам первого шага построено временное паросочетание1 , где 1 (1 ) = 3 , 1 (3 ) = 2 , 1 (2 ) = 2 , 1 (4 ) =4 , 1 (1 ) = 1 .2.1 Мужчины 2 и 4 делают следующие предложения (т.к. их предложения не были приняты на шаге 1.2). 2 делает предложение2 , а 4 - 1 .2.2 2 сравнивает временного партнера 3 и новое предложение от2 ; 2 предпочтительнее, чем 3 . Таким образом, предложение3 , временно принятое на первом шаге, на втором шаге оказалосьотклонено. 1 принимает предложение 4 , поскольку, согласно еёотношению предпочтения, 4 1 1 , и это единственное предложение.По итогам второго шага построено временное паросочетание 2 ,где 2 (1 ) = 3 , 2 (2 ) = 2 ,2 (3 ) = 3 , 2 (4 ) = 13.1 Единственный мужчина, который не поставлен в пару с женщиной в паросочетании 2 – это 3 .
Однако, согласно егоотношению предпочтения, 1 и 3 не являются допустимыми,поэтому 3 ∈ .20Работа механизма окончена, временное паросочетание 2 становитсяокончательным паросочетанием Нетрудно убедиться в том, что построенное паросочетание будет1 2 3 43 2 3 1Таблица 1.2: Результат работы механизма отложенного принятия спредлагающими мужчинами для Примера 1.1устойчивым, т.е. является индивидуально рациональным и не содержит блокирующих пар. Индивидуальная рациональность выполненапо построению.Тогда попробуем найти блокирующую пару. В блокирующую пару должен входить один мужчина и одна женщина. Покажем, что ни однаженщина не может составить блокирующую пару с кем-либо из мужчин.∙ 1 может составить блокирующую пару с 3 , т.к. 3 1 (1 ).Однако 3 не составит блокирующую пару с 1 , поскольку 1 ,согласно отношению предпочтения 3 является недопустимой.∙ 2 может составить блокирующую пару с 1 , т.к.
1 2 (2 ).Однако 1 не составит блокирующую пару с 2 , поскольку в паросочетании 1 состоит в паре с более предпочтительной длянего женщиной 3 .∙ Для 3 ( 3 ) является наиболее предпочтительным среди всехэлементов множества ∪ {}, поэтому 3 не может образоватьни с кем блокирующую пару.Таким образом, ни одна ∈ не может составить блокирующуюпару.21Паросочетание не содержит блокирующих пар и индивидуально рационально, следовательно, оно устойчиво.Теперь убедимся в том, что это не случайное совпадение.Теорема 1.1.1.[2] Паросочетание , полученное в результатеприменения механизма отложенного принятия, всегда являетсяустойчивым.Действительно, паросочетание могло бы быть неустойчивым, если нарушена индивидуальная рациональности или попарная устойчивость. Индивидуальная рациональность не может нарушаться ни длямужчин (т.к.
в рамках механизма мужчины не делают предложениенедопустимым для себя женщинам), ни для женщин (поскольку женщины всегда отвергают предложения недопустимых мужчин).Предположим, что в существует блокирующая пара: * и * ,которые в текущем паросочетании не поставлены в пару, т.е. (* ) ̸=* ), и им обоим предпочтительнее составить пару друг с другом, чемс предписанными в партнерами. Возможны два варианта:1. * ни на одном шаге механизма не был поставлен в пару с * .Однако он обязательно был поставлен в пару с (* ). Мужчину ставят в соответствие сначала с наиболее предпочтительной1, затем следующей по предпочтительности и так далее.
Значит,(* ) для * предпочтительнее, чем * .2. * был поставлен в пару с * на некотором шаге , однако на последующем, +-ом шаге ей был поставлен в пару другой мужчина′ (а + (* ) = * ). Это означает, что ′ * * . На последующих шагах механизма * могла получать новые предложения, и221 : 1 , 2 , 3 1 : 2 , 3 , 12 : 2 , 3 , 1 2 : 3 , 1 , 23 : 3 , 1 , 2 3 : 1 , 2 , 3Таблица 1.3: Отношения предпочтения для Примера 1.2.в окончательном паросочетании , возможно, (* ) ̸= ′ . Однакона каждом последующем шага механизма * выбирает из наиболее предпочтительного , поставленного ей в пару на предыдущих шагах, и новых предложений, т.е. ∀ () (), если0 < < . Поэтому в окончательном паросочетании ()* ′ .Учитывая, что ′ * * , а отношение предпочтения * транзитивно, получаем, что (* )* * .Таким образом, * и * не могут составлять блокирующую пару.Заметим, что существует и симметричный механизм, в которомпредложение первыми делают женщины.
Вообще говоря, как уже отмечалось выше, с точки зрения формальной модели, две стороны –мужчины, и женщины, – в данной задаче абсолютно симметричны, а названия условны и введены для удобства обсуждения.Пример 1.2. Пусть заданы множества = {1 , 2 , 3 } и ={1 , 2 , 3 }. Отношения предпочтения приведены в Таблице 1.3.Опция одиночества опущена во всех предпочтениях, поскольку в данном примере все считают опцию одиночества наименее предпочтительным вариантом.Если будет выполнен механизм отложенного принятия с предлагающими мужчинами, то на первом же шаге, в результате первоговыбора наиболее предпочтительных женщин будет получено окончательное обобщённое паросочетание , в котором (1 ) = 1 ,23 (2 ) = 2 , (3 ) = 3 .
Если же будет выполнен механизмотложенного принятия с предлагающими женщинами, то, также заодин шаг, будет получено обобщённое паросочетание , в котором (1 ) = 3 , (2 ) = 1 , (3 ) = 2 . Поскольку стороны симметричны, в соответствии с теоремой 1.1.1 оба паросочетания будутустойчивыми. Таким образом, получено два различных устойчивыхпаросочетания.Более того, нетрудно заметить, что в данном примере можно построить и третье устойчивое паросочетание, назовем его , в котором (1 ) = 2 , (2 ) = 3 , (3 ) = 1 .11 2 3 1 2 3 1 2 3 2 3 3 1 2 2 3 1Таблица 1.4: Устойчивые паросочетания в Примере 1.2.Итак, оказывается, что устойчивых паросочетаний может бытьнесколько. Из каких же соображений следует выбирать единственное?Можно попробовать усилить определение устойчивого паросочетания.Действительно, согласно классическому определению Гейла-Шепли,из предложенного распределения с выгодой для себя не может выйтиодин агент или пара агентов (мужчина и женщина).
А что, если целаягруппа ⊂ ∪ откажется от некоторого устойчивого паросочетания и составит друг с другом новые пары так, что для каждого ∈ новый полученный партнер будет предпочтительнее, чем партнер согласно ? Оказывается, что любое паросочетание, устойчивое котклонению индивидов или пар, устойчиво и к отклонению коалициипроизвольного размера. Задачу об обобщенных паросочетаниях можнорассмотреть как кооперативную игру с нетрансферабельной полезно24стью, где множество игроков = ∪ , а векторная характеристическая функция () задает для каждой коалиции ⊆ выигрышивходящих в нее игроков в соответствии с паросочетанием, котороеможет построить эта коалиция из своих членов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
