Диссертация (Обобщенные паросочетания при предпочтениях, не являющихся линейными порядками), страница 5

Следовательно, и этот механизм не удовлетворяет желаемомусвойству.Таким образом, этот пример показывает, чтоТеорема 1.1.7. Не существует устойчивого механизма, при использовании которого сообщение истинных предпочтений является длякаждого ∈ ∪ слабо-доминирующей стратегией.Однако оказывается, что при применении механизма отложенногопринятия с предлагающими мужчинами для каждого ∈ сообщение истинных предпочтений является слабо доминирующей стратегией.Мы не будем приводить доказательство этого результата, а докажем сразу более общую теорему, из которой приведенный выше фактявляется прямым следствием.Теорема 1.1.8.

[8] Пусть заданы и и профиль предпочтений⋃︀ . Если некоторое подмножество ′ = ′ ′ заменило в про33филе предпочтений свои истинные предпочтения на искаженные′ ′ , то для любого паросочетания ′ , устойчивого при новом профиле предпочтений ′ , найдутся паросочетание , устойчивое приистинных предпочтениях , и ∈ ′ , такие что ′ () ().На самом деле множество ′ (из. Теоремы 1.1.8) может быть устроено по-разному. Пусть, например, множество ′ состоит из одногомужчины. Согласно теореме, при любом искажении им предпочтенийни одно паросочетание, устойчивое при новом профиле предпочтений,не может оказаться строго предпочтительнее паросочетания длявсех ∈ ′ , т.е. для самого этого мужчины.Следствие 1.3.

Для каждого мужчины сообщение истинных предпочтений является слабо доминирующей стратегией при применениимеханизма отложенного принятия с предлагающими мужчинами.Пусть ′ является подмножеством , то согласно теореме, входящие в это множество мужчины никогда не смогут исказить своипредпочтения так, чтобы одновременно строго улучшить положениекаждого ∈ ′ по сравнению с паросочетанием , то есть результатом работы механизма отложенного принятия при истинных предпочтениях.2Следствие 1.4.

Никакая коалиция ′ ⊆ ( ′ ⊆ ) не может с выгодой для каждого из ее членов исказить предпочтения в том случае,когда используется механизм отложенного принятия с предлагающимимужчинами (женщинами).Наконец, заметим, что если при исходных предпочтениях существует ровно одно устойчивое паросочетание, то ни одна коалиция2 Фактическиэто означает, что при невозможности платежей между агентами такая фальсификация не будет совершена.34 ′ ⊆ ∪ не может исказить свои предпочтения так, чтобы приновом профиле предпочтений нашлось паросочетание, которое строголучше для всех манипулирующих, чем исходное.Следствие 1.5. Если при данных предпочтениях существует ровно одно устойчивое паросочетание, то при использовании механизма отложенного принятия сообщение истинных предпочтений является слабодоминирующей стратегией для любого игрока.

Более того, никакаягруппа игроков не может исказить свои предпочтения таким образом,чтобы положение каждого из них улучшилось.1.2Обобщенные паросочетания один ко многимВ предыдущем разделе была рассмотрена задача о построенииустойчивого паросочетания в случае, когда стороны рынка симметричны и каждый из игроков составляет пару с (максимум) одним игрокомиз другой подгруппы. Эту модель можно расширить, предположив, чтонекоторые игроки могут составлять пары сразу с несколькими игроками.

Такая модель позволяет описать реальную структуру отношений втаких ситуациях, как сопоставление фирм (предлагающих нескольковакансий) и работников (желающих получить по одному месту работы), школ и учеников, вузов и абитуриентов и др.Начиная с [2] сложилась традиция называть такую задачу задачейраспределения абитуриентов по вузам. Будем придерживаться сложившейся системы обозначений и терминов, что в некоторых случаях значительно упростит изложение материала. В то же время следует заметить, что рассматриваемая модель является по своей сути абстрактной, а результаты применимы к любым подобным системам.

Например,35многие работы А.Рота ( [12, 19] и др.) по тематике обобщенных паросочетаний посвящены анализу систем распределения интернов наработу в больницы.Обозначим через множество абитуриентов, а через – множество вузов. Множества и конечны.

Будем обозначать через элементы множества абитуриентов, а через – элементы множествавузов. Если и поставлены в пару в паросочетании , будем говорить, что абитуриент зачислен в вуз в паросочетании . Каждыйабитуриент может быть зачислен не более, чем в один вуз (заметим,что в модели один к одному, рассмотренной в предыдущем разделе,аналогичное условие накладывалось на всех игроков.) Для каждого ∈ установлена квота – это целое положительное число, равное максимальному числу абитуриентов ∈ , которые могут бытьзачислены в (поставлены в пару с) . В дальнейшем будем говорить,что – это число мест в вузе . Дадим расширенное определениеобобщённого паросочетания.Определение 1.9. [2] Обобщенное паросочетание – это отображение : ( ∪ ) → 2(∪)такое, что:1.

() = {} ⇔ ∈ ()2. ∀ ∈ () = {} или () = {}3. ∀ ∈ () ⊆ или () = {}4. ∀ ∈ |()| ≤ (число абитуриентов, зачисленных в , непревышает )36Также как и в изложенной в первом разделе модели, будем говорить, что игроки, т.е. абитуриенты и вузы, обладают предпочтениямиотносительно желаемого партнера в паросочетании. Профиль предпочтений абитуриентов = (1 , ..., || ) состоит из бинарных отношений, каждое из которых задано на множестве ∪ {} и являетсялинейным порядком. Профиль предпочтений вузов ⪰= (≻1 , ..., ≻|| )состоит из бинарных отношений, каждое из которых задано на множестве ∪ {} и является линейным порядком.

Будем говорить, чтоабитуриент является допустимым для вуза , если ≻ ; вуз является допустимым для абитуриента , если .Однако для того, чтобы иметь возможность сравнивать различныепаросочетания по предпочтительности для некоторого , нужно также сделать предположения о том, как устроены его предпочтения намножестве всех подмножеств мощностью не больше , т.е. на возможных наборах абитуриентов. Вслед за [2] обычно предполагают,что ∀′ ⊂ , |′ | < , ′ ∈ ∖ ′ ′ ∪ {} ≻ ′ ∪ {′ } если итолько если ≻ ′ .3 В [20] показано, что при выполнении указанногопредположения любой вуз всегда может сравнить между собой наборы абитуриентов, которые зачислены в этот вуз в разных устойчивыхпаросочетаниях.

В более поздних работах показано, что для сохранения справедливости приведённых ниже результатов о существованиии структуре множества устойчивых паросочетаний достаточно болееслабого предположения о том, между абитуриентами отсутствует дополняемость [9, 21]. [22]3 Здесь и далее для того, чтобы не усложнять систему обозначений, один и тот же знак отношения предпочтения ≻используется и для отношения, заданного на ∪ {}, и для отношения, заданного на множестве подмножеств 2∪{} .37Определение 1.10. Пара (, ) называется блокирующей паросочетание , если верно хотя бы одно из двух условий:∙ (), ≻ , |()| < ∙ () и ∃′ ∈ () : ≻ ′ ,.Первое условие означает, что квота не исчерпана (имеются свободные места), абитуриент является подходящим для вуза , а дляабитуриента вуз предпочтительнее вуза, в который зачисленсогласно .

Второе условие практически полностью аналогично определению блокирующей пары для обобщенных паросочетаний один кодному.Теперь можно сформулировать полное определение устойчивого (по[2]) паросочетания.Определение 1.11. Обобщенное паросочетание будет устойчивым,если оно является∙ индивидуально рациональным для , т.е. ∀ ∈ верно, что ();∙ индивидуально рациональным для , т.е. ∀ ∈ верно, что ∀ ∈() ≻ ;∙ в паросочетании отсутствуют блокирующие пары.Многие результаты, сформулированные и доказанные для задачио свадьбах, остаются верны и в рассматриваемой здесь более общеймодели.

В задаче один ко многим также всегда существует устойчивоепаросочетание.38Теорема 1.2.1. Пусть заданы , , квоты ( ) и профили предпочтений и ≻, удовлетворяющие описанным выше условиям. Тогдаустойчивое паросочетание всегда существует.Доказательство этой теоремы также конструктивно: в случае одинко многим при сделанных выше предположения о предпочтениях также может применяться механизм отложенного принятия.

Мы не будемприводить здесь полное описание механизма, т.к. логика практическиполностью повторяет таковую для случай один к одному. Единственное различие состоит в том, что для всех вузов в течение работымеханизма устанавливается (или отбирается, если предлагающей стороной являются абитуриенты) не один партнер, а партнеров.Кроме того, можно сформулировать в более общем виде аналог теоремы 1.1.5.Теорема 1.2.2 (Rural hospital theorem).

[16] Если в одном из устойчивых паросочетаний для некоторого верно, что |()| < (в вузе заполнены не все места), то в любом другом устойчивомпаросочетании в зачислено то же подмножество абитуриентов(), и не зачислены никакие другие ∈/ ().Также (при выполнении предположения о том, что предпочтениявуза на множестве подмножеств абитуриентов строятся на основе егопредпочтений на множестве абитуриентов) остается верным утверждение о структуре множества устойчивых паросочетаний [9, 23, 24].Относительно отношения частичного порядка «предпочтительнее дляабитуриентов» множество устойчивых паросочетаний представляет собой решетку, операции нахождения точной верхней и точной нижнейграни задаются аналогичным образом.39Однако результаты, касающиеся сообщения предпочтений и манипулирования предпочтениями, не обобщаются на случай задачи одинко многим.

В частности, оказывается, что вуз (игрок, имеющий квотубольше единицы) может с выгодой для себя исказить предпочтениядаже в том случае, когда используется механизм отложенного принятия с предлагающими вузами. Следующий пример [6] иллюстрируетэто утверждение.Пример 1.4.

Пусть = {1 , 2 , 3 }и = {1 , 2 , 3 , 4 }. Квоты заданы следующим образом: 1 = 2,2 = 3 = 1. Предпочтения даны втаблице 1.6. Все абитуриенты допустимы для всех вузов и наоборот,поэтому соответствующий элемент опущен в упорядоченных списках.Таблица 1.6: Пример манипулирования в модели один ко многимИстинные предпочтения1 : 3 , 2 , 1 1 : 1 , 2 , 3 , 42 : 2 , 1 , 3 2 : 1 , 2 , 3 , 43 : 1 , 3 , 2 3 : 3 , 1 , 2 , 44 : 1 , 2 , 3Искаженные предпочтения1 : 2 , 4 , b1 , 3 , 1При этом профиле предпочтений существует только одно устойчивое паросочетание . Если 1 сообщит искаженные предпочтения,то при новом профиле предпочтений также существует единственноеустойчивое паросочетание ′ , причем 1 предпочтет получаемое в этомпаросочетании подмножество абитуриентов – ′ () – по сравнению с().

Таким образом, 1 может успешно исказить свои предпочтениятаким образом, чтобы получить более предпочтительный набор пар в40итоговом паросочетании; причем даже в случае, когда будет использован механизм отложенного принятия с предлагающими вузами.Заметим, что полученное таким образом паросочетание не будетустойчивым при исходных предпочтениях.Ещё одна существенная проблема совместимости стимулов возникает при появлении игроков, которые могут иметь больше одного партнера в обобщенном паросочетании: манипулирование квотами. Действительно, предпочтения вуза на множестве всех подмножеств определяются не только отношением предпочтения на множестве абитуриентов, но и установленной квотой.

Если вузы устанавливают квотысамостоятельно, то они способны искажать их, так же, как и отношения предпочтения, для получения более предпочтительного набораабитуриентов.В [25] показано, что верная следующая теорема.Теорема 1.2.3. Не существует механизма нахождения устойчивого паросочетания, который исключал бы возможность манипулирования квотами со стороны игроков, имеющих квоту более 1.Новый результат был получен в [26]. Доказано, что если некоторый механизм (при заданном профиле предпочтений и наборе квот)подвержен манипулированию с помощью искажения квот, то этот механизм манипулируем и путём искажения предпочтений.Кроме того, в [26] предлагается разделение всех возможностей манипулирования с помощью квот на два типа.

Манипулирование первого типа – это занижение своей квоты вузами, у которых в устойчивомм паросочетании |()| < , т.е. заполнены не все места. Ма-41нипулирование второго типа – это занижение своей квоты вузами, укоторых |()| = , т.е. заняты все места.Теорема 1.2.4.[26] Механизм отложенного принятия с пред-лагающими абитуриентами является единственным механизмом,устойчивым к манипулированию квотами 1-го типа.Данный результат является ещё одним подтверждением предпочтительности использования данного механизма в прикладных проблемах, особенно в тех случаях, когда манипулирование квотами для игроков (например, вузов или больниц) по организационным причинамболее доступно, чем манипулирование предпочтениями.1.31.3.1Предпочтения сторон: расширения классической моделиСуществование и эффективность устойчивого паросочетанияНа практике довольно легко представить ситуацию, в которой игроки не могут строго упорядочить игроков другой стороны по предпочтительности.