Журнал вычислительной математики и математической физики, 2023, T. 63, № 3, стр. 491-516

2.1. Основные понятия

Множество участников (агентов), принимающих решение о сотрудничестве и заключении договоров, обозначается как $I$. Типичный элемент этого множества – $i,j,..$. Множество $I$ предполагается конечным. Буквой $C$ будет обозначаться множество доступных для заключения договоров (или контрактов; в [97], [28] говорят о венчурах); типичный контракт обозначается как $c$. Для простоты множество $C$ тоже предполагается конечным.

Главная характеристика любого контракта $c$ – это множество $P(c) \subseteq I$ участников этого контракта, чье согласие (подпись) необходимо для заключения контракта. Для агента $i \in I$ символ $C(i)$ обозначает множество контрактов, участником которого является $i$; так что $i \in P(c) \Leftrightarrow c \in C(i)$. Пару $(I,C)$ можно понимать как гиперграф, понимая контракт $c$ как (гипер)ребро, связывающее вершины из $P(c)$. Договор $c$ называется бинарным (или парным), если $P(c)$ состоит из двух участников. До недавнего времени существовавшая литература имела дело исключительно с бинарными контрактами (марьяжи, руммэйт, найм на работу, договора займов и депозитов и т.п.). В этом случае гиперграф $(I,C)$ является просто графом. Подчеркнем, что две вершины могут связывать несколько ребер. Иначе говоря, мы не просто отмечаем, что пара вступила в брак, но подписала конкретный брачный договор, четко прописывающий права и обязанности сторон.

Договор с единственным участником называется автаркическим. Конечно, несколько странно называть его договором. Это просто указание на некую деятельность, которую агент может вести в одиночку (в марьяжной ситуации – остаться холостяком). В экономике говорят о “статус кво” или альтернативных возможностях. Мы предполагаем в дальнейшем, что у каждого участника имеется автаркический договор.

Произвольное подмножество $S \subseteq C$ мы называем сетью договоров. Это либо реально заключенные договора, либо спущенные сверху (предложенные свахой). $S(i) = S \cap C(i)$ – договора, подписанные агентом $i$. В принципе, каждый агент может заключить несколько договоров. Какие договора будут подписаны или заключены, а какие отвергнуты – зависит от “предпочтений” агентов. Это вторая главная структура модели.

Считается, что каждый агент $i$ как-то оценивает доступные ему договора. Так как он может заключать несколько договоров, он должен оценивать и сравнивать между собой не только элементы множества $C(i)$, но и произвольные подмножества этого множества. Один из общих способов сделать это – использовать функции выбора.

Функцией выбора (далее – ФВ) на произвольном множестве $X$ называется отображение $f{{:2}^{X}} \to {{2}^{X}}$ такое, что $f(A) \subseteq A$ для любого $A \subseteq X$. Интуитивно это означает, что имея доступ к множеству (“меню”) $A \subseteq X$, агент выбирает в нем подмножество $f(A)$. Считается, что при этом он руководствуется некими соображениями рациональности и выбирает “лучшие” варианты. Тематика рационального выбора выходит за рамки настоящего обзора (см., к примеру, книгу [1]), и мы ограничимся в основном примерами, нужными для дальнейшего. Гиперграф $(I,C)$, снабженный ФВ ${{f}_{i}}$ на множестве $C(i)$ для каждого $i \in I$, будем называет оснащенным. Можно даже считать, что ФВ ${{f}_{i}}$ определены на всем $C$, полагая ${{f}_{i}}(A) = {{f}_{i}}(A(i))$ для $A \subseteq C$.

Замечание. Хотя задание предпочтений агентов в форме ФВ выглядит достаточно общим, оно ограничительно в двух отношениях, которые стоит упомянуть. Во-первых, предполагается, что из заданного меню $A$ агент выбирает ОДНО подмножество ${{f}_{i}}(A)$. В принципе несколько подмножеств могли бы оказаться для него “равноценными”. И второе. Неявно предполагается, что агенту безразлично, какие договора заключены без его участия. Поясним на примере. Когда фирма нанимает на работу группу рабочих, для нее важен состав этой группы. Но считается, что для рабочего не важно, кто (кроме него) будет принят на работу в этой фирме (и тем более, кто будет работать в других фирмах). Иначе говоря, здесь нет “экстерналий”. Конечно, можно развивать теорию и с учетом экстерналий [63], [157], но пока это направление находится в зачаточном состоянии.

2.2. Стабильность

Теперь можно сформулировать основное понятие.

Определение. Сеть договоров $S \subseteq C$ называется стабильной, если выполнены два условия:

S1. ${{f}_{i}}(S(i)) = S(i)$ для любого $i \in I$.

S2. Если $c \in {{f}_{i}}(S(i) \cup c)$ для любого $i \in P(c)$, то $c \in S$. (Здесь и далее мы пишем $X \cup x$ вместо $X \cup \{ x\} $.)

В основе этого определения лежит предположение о добровольности и ненавязанности контрактов. Любой агент может отказаться от контракта, который кажется ему невыгодным. Это условие S1. И ничто не может помешать агентам подписать договор, который они единогласно хотят. Это условие S2. Если некоторый договор $c$ нарушает условие S2 (т.е. $c \in {{f}_{i}}(S(i) \cup c)$ для любого $i \in P(c)$, но $c \notin S$), говорят, что договор $c$ блокирует сеть $S$. Такой блокирующий договор вызывает соблазн заключить его (быть может, отказываясь от некоторых заключенных ранее договоров, как в ситуации с марьяжем) и тем самым разрушить предложенную сеть договоров $S$. Стабильная сеть договоров имунна к такого рода соблазнам.

Заметим, что условие S2 может (и даже должно) быть сформулировано в более общем варианте S2+.

S2+. Если $Z(i) \subseteq {{f}_{i}}(S \cup Z)$ для любого $i \in P(Z)$, то $Z \subseteq S$.

Иначе говоря, допускается возможность блокирования не отдельным договором, но некоторым пакетом договоров $Z$. В свое оправдание мы покажем ниже, что в большинстве случаев (более точно, в случае плоттовских ФВ) эти два варианта эквивалентны. И мы знаем только одну работу [157], где реально используется более общий вариант S2+.

Условие S1 называется индивидуальной рациональностью. Условие S2 можно понимать как нечто типа коалиционной рациональности (и даже коалиционного равновесия) из теории кооперативных игр. Вообще, понятие стабильной системы договоров близко по смыслу к понятию ядра. И в некоторых простых случаях типа марьяжа фактически совпадает с ядром. Но все же это разные вещи, как показывает следующий простой пример неоптимальности стабильной сети (более подробно связь с ядром обсуждается в [160], [168]).

Пример 0. Два участника, Анна и Борис. И два контракта, $A$ и $B$ между ними. Первый дает полезность 2 Анне и –1 Борису. Второй дает 2 Борису и –1 Анне. Если заключены оба контракта, каждый получает по 1. Автаркия понимается как отказ от заключения договоров и дает 0.

В этом примере пустая сеть стабильна. Но она не оптимальна по Парето, потому что доминируется системой $\{ A,B\} $. Заметим, что множество $Z = \{ A,B\} $ не блокирует стабильную сеть $S = \emptyset $.

Помимо приведенного выше определения стабильности, в литературе встречаются и другие варианты стабильности: парная, множественная, сильная и т.п. Мы не будем на них отвлекаться, отсылая к работам [126], [23].

2.3. Агрегирование

Иногда удобно предпочтения всех участников представить как поведение одного, совокупного Агента (с большой буквы). И описывать его с помощью одного оператора $F$, который произвольному подмножеству $A \subseteq C$ сопоставляет множество

Это уже не обязательно ФВ, так как этот оператор может как удалять элементы из $A$, так и добавлять новые. Его удобство в том, что с его помощью можно экономно переписать условия стабильности.

Лемма 2.1. Сеть $S$ стабильна тогда и только тогда, когда $S = F(S)$.

Доказательство. В одну сторону очевидно: если $S$ стабильна, то $S = F(S)$. Обратно, пусть $S = F(S)$. Проверим условие S1. Пусть $s \in S(i)$; так как $S(i) \subseteq S$, то $s \in S$ и поэтому выбирается любым участником из $P(s)$, включая $i$. Проверка S2 вообще тривиальна.

Похожая агрегация (в двудольном случае) производилась в [74], а в случае дополнительных контрактов – в [157]. Так что стабильные сети оказываются просто неподвижными точками оператора $F$. Поэтому для многих вопросов можно применять развитую теорию неподвижных точек. Имея какую-либо теорему о неподвижных точках, мы получаем соответствующую теорему о стабильных сетях. Есть три большие теории про неподвижные точки: сжимающие отображения полных метрических пространств, монотонные отображения в полных решетках (Тарский), и непрерывные отображения выпуклых компактов (Брауэр, Какутани, Скарф). Первая теория для нас не годится, вторая с успехом была применена в [74]. Мы увидим далее, что третья, наиболее глубокая теория также имеет применения к стабильности (полуматчинги, метастабильность).

Стабильность системы договоров – вещь достаточно приятная. Такие системы стабильны (устойчивы) в том смысле, что ни у кого нет стимулов их разрушать. По крайней мере при имеющихся предпочтениях. Конечно, если предпочтения меняются или появляются новые участники или контракты, стабильность может нарушиться. Это понятно, это статическое понятие. Но даже в этом случае можно рассчитывать, что сеть изменится не слишком сильно, см. [16], [132].

Как бы то ни было, первый вопрос, которым приходится заниматься, это вопрос о существовании стабильных сетей. И близкий к нему вопрос о том, как их строить или находить. Вопросу о сравнении стабильных сетей, их структуре, тоже посвящено немало работ и мы постараемся это осветить тоже. Но, повторю, первый вопрос – о существовании. Обсуждать свойства объектов, которые неизвестно когда существуют (или не существуют вообще) – не слишком продуктивное занятие. Довольно легко понять, что если ФВ агентов произвольны, то на существование стабильных сетей рассчитывать не приходится. Вот простой пример.

Пример 1. Два участника, производитель $F$ и покупатель $B$. И два товара $a$ и $b$, которые может производить $F$. Покупатель предпочитает $b$, т.е. его ФВ ${{f}_{B}}$ выбирает $a$ из $a$, $b$ из $b$, и $b$ из $\{ a,b\} $. Производителю не выгодно выпускать каждый продукт по отдельности, он хотел бы выпускать $a$ и $b$ вместе. Так что его ФВ ${{f}_{F}}$ пуста на одноэлементных меню и равна $\{ a,b\} $ на $\{ a,b\} $. Легко понять, что стабильных договоров тут нет.

Интуитивно ясно, что предпочтения покупателя достаточно рациональны. А вот поведение производителя хотя и объяснимо, но все же менее привычно. Для него товары $a$ и $b$ скорее дополнительны, чем заменимы. Ниже мы введем соответствующие понятия для ФВ.

Пример 2. Пусть у нас имеется одна женщина 0 и три претендента 1, 2 и 3. Каждый претендент хотел бы жениться на ней. Но ее предпочтения устроены так: 1 < 2 < 3 < 1, т.е. “циклические”. Ясно, что стабильного брака тут нет. И объясняется это крайне вздорным, нерациональным характером предпочтений агента 0.

2.4. Функции выбора Плотта

Посвятим некоторое время формулировке понятия “хорошей” или “рациональной” ФВ. Этой тематике посвящено много литературы (см. [1]); мы ограничимся нужным нам минимумом.

Определение 1. ФВ $f$ называется заменимой (или наследственной в [1]), если выполнено следующее: пусть $A \subseteq B$; тогда $A \cap f(B) \subseteq f(A)$.

Иначе говоря, если элемент $a$ из меньшего множества $A$ выбирается в большем множестве $B$, то он должен выбираться и в меньшем. Может быть это лучше понять на следующем примере. Пусть фирма из имеющегося меню рабочих $B$ выбрала $f(B)$. И по каким-то причинам некоторый принятый работник $b$ из $f(B)$ стал недоступен. Тогда фирма вместо него может нанять других работников, но не станет увольнять уже принятых. Заметим также, что предпочтения в Примере 1 нарушали это свойство.

Еще одно условие рассматривается как несомненное свойство рациональности поведения.

Определение 2. ФВ $f$ удовлетворяет условию отбрасывания (более развернуто – условию независимости от отвергнутых альтернатив), если $f(B) \subseteq A \subseteq B$ влечет $f(A) = f(B)$.

Иначе говоря, если какие-то отвергнутые альтернативы исчезают из меню, то это не сказывается на выборе. Грубо говоря, это условие означает, что агент приписывает каждому подмножеству $A \subset X$ некоторую полезность $u(A)$ и выбирает из меню $A$ подменю $B \subseteq A$ с наибольшей полезностью $u(B)$.

Определение 3. ФВ называется функцией Плотта, если она обладает свойствами заменимости и отбрасывания. Такие ФВ характеризуются следующим свойством “независимости от пути”:

Именно в такой форме они были введены Плоттом в [152]. Приводимые ниже примеры плоттовских ФВ часто использовались в литературе о стабильности.

Пример 3. Пусть < – линейный порядок на множестве $X$. Положим $f(A)$ состоящим из наибольшего элемента в $A$ относительно этого порядка. Очевидно, что $f$ является функцией Плотта. Такие ФВ мы называем линейными. И большая часть литературы о стабильных матчингах имела дело именно с такими ФВ.

Пример 4. Пусть $ \leqslant $ – предпорядок на $X$ (то есть рефлексивное и транзитивное бинарное отношение на множестве $X$). И пусть $f(A)$ состоит из (всех) максимальных элементов в $A$ относительно этого предпорядка. Это снова дает ФВ Плотта. Наиболее важный случай – когда $ \leqslant $ – слабый порядок (то есть полный предпорядок). Такие ФВ (и соотвествующие оснащения) будем называть слабо-порядковыми. Многие работы по стабильности посвящены переносу результатов с линейных оснащений на слабо-порядковые (при этом говорят о связках, ties).

Пример 5. Менее тривиальные примеры плоттовских ФВ возникают в такой постановке. Снова < – линейный порядок, но в $f(A)$ включают $b$ наилучших элементов из $A$, где $b$ – натуральное число (квота). Функции выбора такого вида будут называться квотируемыми. Уже в пионерской работе [81] использовались такие ФВ. Более интенсивное изучение стабильности с такими ограничениями на “мощность” или капасити было проделано в работах [44], [75], [67], [113], [43], см. ниже.

Условие плоттовости ФВ в задачах стабильности – стандартное в литературе. Во всяком случае, оно гарантирует существование стабильных систем в двудольной ситуации. И мы, следуя литературе, также будем (кроме разд. 6) считать ФВ агентов плоттовскими. Иногда накладывались дополнительные условия на ФВ, такие как кардинальная монотонность, отзывчивость, сепарабельность.

Пусть $f$ – функция Плотта на множестве $X$. Скажем, что элемент $x \in X$ неприемлем, если $f(x) = \emptyset $. Легко понять из условия S1, что неприемлемые договора не могут входить в стабильные системы. По этой причине можно их исключить и считать всюду, что неприемлемых договоров в $C$ нет. Кроме того, в плоттовской обстановке условие S2 эквивалентно сильной форме S2+. В самом деле, если $Z$ не содержится в $S$ и $z \in Z - S$, то из условия заменимости (и того, что $Z(i) \subseteq {{f}_{i}}(S \cup Z)$ для любого $i$ из $P(z)$) видно, что $z \in {{f}_{i}}(S \cup z)$.

2.5. Оптимальность

Первый простой факт про стабильные сети – это оптимальность по Парето (ср. с Примером 0). Но как говорить об оптимальности на языке ФВ? Оказывается, можно, потому что с каждой плоттовской ФВ $f$ (на множестве $X$) можно связать естественным способом (Блэр, [37]) некий гиперпорядок ${{ \preccurlyeq }_{f}}$ (приставка “гипер” указывает на то, что это бинарное отношение на множестве ${{2}^{X}}$), с помощью которого можно сравнивать подмножества в $X$. А именно, для $A,B \subseteq X$ положим

Заметим, что в этом случае $f(A \cup B) = f(B)$, так как $f(B) = f(B \cup f(A \cup B)) = f(A \cup B \cup $ $ \cup \;B) = f(A \cup B)$. Гиперотношение ${{ \preccurlyeq }_{f}}$ рефлексивно (что очевидно) и транзитивно (см. [37], [54]). Кроме того, ФВ $f$ однозначно восстанавливается по гиперотношению ${{ \preccurlyeq }_{f}}$; а именно, $f(A)$ – это наименьшее подмножество в $A$, эквивалентное $A$. В принципе, мы могли бы формулировать стабильность в терминах гиперпорядка Блэра вместо плоттовских ФВ; нужные для этого свойства приведены в [54]. Например, условие стабильности S2 означает, что $S \cup z$ не может быть строго лучше, чем $S$, для всех участников договора $z$.

Предложение 2.2. Предположим, что предпочтения всех агентов заданы плоттовскими ФВ ${{f}_{i}}$, и пусть $S$ – стабильная сеть. Пусть, далее, $T$ – произвольное подмножество в $C$, удовлетворяющее условию S1 (то есть ${{f}_{i}}(T) = T(i)$ для любого $i$). Если для любого $i \in I$ выполнено $S(i){{ \preccurlyeq }_{i}}T(i)$, то $T = S$.

Приведем сравнительно простое доказательство. Если $T(i) \subseteq S(i)$, то $S(i) = {{f}_{i}}(S) = $ $ = {{f}_{i}}(S \cup T) = T(i)$. Если же $T(0)$ не содержится в $S(0)$ для некоторого агента 0, то возьмем произвольный контракт $t$ из $T(0) - S(0)$. Пусть $j$ – произвольный участник контракта $t$, так что $t \in T(j)$. Контракт $t$ принадлежит $T(j) = {{f}_{j}}(T(j) \cup S(j))$, поэтому (в силу заменимости ФВ ${{f}_{j}}$) $t \in {{f}_{j}}(S(j) \cup t)$ для любого $j \in P(t)$. В силу условия S2 $t \in S$, вопреки предположению, что $t \notin S(0)$. Значит, $S(i) = T(i)$ для любого участника, откуда $S = T$.

2.6. Теорема о редукции

Плоттовские ФВ замкнуты относительно операции объединения выборов. И замечательная теорема Айзермана и Малишевского [1] состоит в том, что любая функция Плотта может быть получена как объединение нескольких линейных ФВ. Используя этот факт, в [55] была доказана следующая теорема о сведении общего (Плоттовского) случая к слабопорядковому. Идея состоит в расщеплении каждого агента на “слабопорядковых” суб-агентов.

Теорема 2.3. Пусть $(I,C,({{f}_{i}}))$ – гиперграф, оснащенный плоттовскими ФВ. Тогда существует другой гиперграф $(I{\kern 1pt} ',C{\kern 1pt} ',({{ \leqslant }_{{i'}}}))$, оснащеннный слабыми порядками ${{ \leqslant }_{{i'}}}$, и отображенние гиперграфов $\pi :(I{\kern 1pt} ',C{\kern 1pt} ') \to (I,C)$, обладающие следующими двумя свойствами:

а) для любой стабильной сети $S{\kern 1pt} '$ в $C{\kern 1pt} '$ ее образ $S = \pi (S{\kern 1pt} '{\kern 1pt} )$ стабилен в $C$;

б) для любой стабильной сети $S$ в $C$ существует (и явно строится) стабильная сеть $S{\kern 1pt} '$ в $C{\kern 1pt} '$, такая, что $\pi (S{\kern 1pt} ') = S$.

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

Повторим определение стабильности в случае, когда предпочтения участников задаются ФВ, порожденными слабыми порядками ${{ \leqslant }_{i}}$. Это такая сеть $S \subseteq C$, что

S1'. Для любого агента $i$ множество $S(i)$ непусто и состоит из эквивалентных (относительно порядка ${{ \leqslant }_{i}}$) договоров;

S2'. Если для $c \in C$ выполнены неравенства $c{{ \geqslant }_{i}}S(i)$ для любого $i \in P(c)$, то $c \in S$.

Иначе говоря, договор $c$ блокирует сеть $S$, если $c \notin S$ и $c{{ \geqslant }_{i}}S(i)$ для любого $i \in P(c)$. Заметим, что не во всех исследованиях блокирование понимается именно так. Приведенное выше понятие называется также суперстабильностью. Если все неравенста в определении блокирования строгие, мы получаем то, что называется слабой стабильностью. Наконец промежуточный случай дает сильную стабильность, см. [109], [113], [165]. И эти понятия реально различаются, как показывает следующий пример.

Пример 6. Двое мужчин $m$ и $m{\kern 1pt} '$ и две женщины $w$ и $w{\kern 1pt} '$, см. фиг. 1.

Договора изображены ребрами; числа около ребер указывают их полезность для соответствующего агента. Обе женщины предпочитают $m{\kern 1pt} '$, мужчина $m$ предпочитает женщину $w$, а $m{\kern 1pt} '$ безразличен между $w$ и $w{\kern 1pt} '$.

Ниже на фиг. 2 слева нарисованы два слабо стабильных матчинга. Ни один из них не является строго стабильным: первый блокируется ребром $m{\kern 1pt} 'w$, второй – ребром $m{\kern 1pt} 'w{\kern 1pt} '$. На правом рисунке изображена единственная стабильная сеть в нашем понимании.

Нюанс здесь в том, что Ирвинг рассматривает только матчинги, а у нас может быть несколько договоров у одного агента; в нашем случае – у $m{\kern 1pt} '$. Так что при рассмотрении матчингов со связками надо быть осторожным.

Еще более жестко определение стабильности выглядит в том случае, когда предпочтения всех агентов линейны. Тогда условия стабильности принимают следующий вид:

S1''. $S(i)$ состоит из одного элемента $s(i)$.

S2''. Не существует такого договора $c$, что $c{{ > }_{i}}s(i)$ для всех участников $c$.

В частности, в этом случае коалиции $P(s)$, $s \in S$, образуют разбиение $I$. Иначе говоря, каждый участник заключает один и только один (эксклюзивный) договор. Матчингом мы называем набор $S \subseteq C$, который однократно покрывает $I$ (то есть для любого $i \in I$ существует и при том единственный договор $s \in S$, что $i \in P(c)$). Именно так устроены стабильные сети договоров при линейных предпочтениях агентов.

3.1. Существование

Следующий результат существования был установлен в пионерской работе [81].

Теорема 3.1. В ситуации классического марьяжа стабильные матчинги всегда существуют.

Есть много способов доказывать этот результат. Отметим только, что тривиальная идея – если есть блокирующая пара $(m,w)$, то поженить их – не проходит, потому что возможны зацикливания. Пример приводится в [129]. Впрочем, позже [163] было показано, что если “правильно” (или даже случайно) выбирать блокирующие пары, то эта тривиальная идея работает.

Начнем с конструкции Гейла и Шепли. Они строят стабильный матчинг алгоритмически, шаг за шагом. На каждом шаге некоторые женщины держат под рукой “ангажированного” мужчину; остальные мужчины “свободны”. Свободные мужчины делают предложения наилучшим для них женщинам (точнее, тем из них, которые им еще не отказали) либо остаются одинокими (и уже до конца). В результате каждая женщина получает несколько предложений и из них (плюс ангажированный мужчина) оставляет (ангажирует) наилучшего, отказывая остальным. На этом шаг завершается, и если остаются свободные мужчины, начинается новый этап процедуры. Процедура начинается с того, что все женщины одиноки, а все мужчины – свободны. И заканчивается тогда, когда нет свободных мужчин.

Процедура заканчивается через несколько шагов (потому что после отказа положение мужчины ухудшается). И легко понять, что результирующий матчинг стабилен. Самое главное – что согласие на брак дается не сразу, а только по окончании процедуры, почему эта процедура и носит название “отложенного принятия” (deferred acceptance).

Построенный этим алгоритмом матчинг (обозначим его ${{S}_{M}}$) обладает многими замечательными свойствами, которые мы еще обсудим. Но в принципе стабильных матчингов может быть довольно много. Например, в книге [89] приводится пример с $n = 32$, который имеет 104  310  534  400 стабильных матчингов. Число стабильных матчингов может быть экспоненциально большим относительно размера популяции. Конечно, в очень специальных ситуациях стабильный марьяж один. В [25] утверждается, что в “общей ситуации” существует только один стабильный марьяж. В [64] приводятся условия единственности стабильного марьяжа. Что касается среднего числа стабильных матчингов (при большом размере популяции), то оно примерно равно размеру популяции при примерно равном числе мужчин и женщин, и стремится к 1, когда отношение полов стремится к бесконечности, см. [73] и более конкретные работы [59], [61], [121], [150], [149], [151], [176], [128]. Одним словом, кое-что известно, но не слишком много и точно. Ситуация с неопределенными линейными предпочтениями обсуждается в [22]. В [86] вводится расстояние от любого матчинга до стабильного и алгоритм его вычисления.

А раз стабильных матчингов много, можно ставить вопрос о выборе среди них какого-то особо интересного [34], [48], [49], [70], [84], [85], [117], [130], [41]. Как мы увидим, матчинг ${{S}_{M}}$ дает большое преимущество мужчинам; “противоположный” матчинг ${{S}_{W}}$ благоприятен для женщин. Можно искать в каком-то смысле “эгалитарный”, справедливый или “оптимальный”. Скажем об этом, приведя еще один способ конструкции стабильного матчинга.

Представим, что мы уже имеем стабильный матчинг. И “входит” новый мужчина $m$ (вариант – входит женщина) вместе с букетом новых договоров. Некоторые женщины оценивают некоторые его договора как лучшие (по сравнению с имеющимися у них до этого) и сообщают ему об этом. Среди них $m$ выбирает самый привлекательный для него договор с некоторой женщиной $w$ и (снова временно) заключает его. Как правило, это приводит к тому, что $w$ разрывает прежний договор (с мужчиной $m{\kern 1pt} '$), и теперь уже $m{\kern 1pt} '$ выступает в роли “новичка”. При удаче ему удается заключить новый договор, и так далее. Положение женщин монотонно улучшается (новые возможности), чего нельзя сказать о мужчинах (появляется конкурент). Поэтому процесс заканчивается и дает стабильный матчинг.

Так вот, если мужчины и женщины будут входить вперемешку и более или менее равномерно, мы получим стабильный матчинг, одинаково благоприятствующий обеим сторонам, в каком-то смысле “эгалитарный”. Интересное в этом смысле утверждение сделано в [174]; они показали, что существует стабильный матчинг, при котором каждый участник получает “медианного” партнера, см. также [106].

3.2. Оптимальность и решеточность

Вернемся к стабильному матчингу ${{S}_{M}}$, который дает алгоритм Гейла–Шепли. Он замечателен тем, что он дает наилучшие результаты ДЛЯ КАЖДОГО МУЖЧИНЫ в классе стабильных матчингов. Иначе говоря, верно следующее

Предложение 3.2 (см. [81]). Пусть $S$ – произвольный стабильный матчинг. Тогда для любого $m \in M$ выполнено $S(m){{ \leqslant }_{m}}{{S}_{M}}(m)$. Для женщин выполнено противоположное неравенство.

Вообще, будем говорить, что матчинг $S$ лучше матчинга $T$ для мужчин, если $T(m){{ \leqslant }_{m}}S(m)$ для любого $m \in M$; это “мужское” отношение (частичный порядок) обозначается $T{{ \preccurlyeq }_{M}}S$. Аналогичное “женское” отношение мы не будем рассматривать, потому что оно, как можно показать, противоположно “мужскому”.

Вскоре в [141] был обнаружен еще один интересный эффект. Представим, что женщин больше, чем мужчин. Тогда в стабильном (как и любом) матчинге некоторые женщины останутся незамужними. Теорема состоит в том, что эти же женщины останутся невостребованными в Л-ЮБОМ стабильном матчинге.

Рассуждение довольно простое и типичное. Пусть у нас есть два стабильных марьяжа, $S$ и $T$. И пусть агент ${{v}_{0}}$ одинок в $S$, но матчирован в $T$ с другим агентом ${{v}_{1}}$. Ясно, что ${{v}_{1}}$ не может быть одиночкой в $S$ (потому что в таком случае пара ${{v}_{0}}{{v}_{1}}$ блокирует $S$). Значит, ${{v}_{1}}$ в $S$ матчирован с ${{v}_{2}}$. И с точки зрения ${{v}_{1}}$ агент ${{v}_{2}}$ лучше, чем ${{v}_{1}}$ (если бы было наоборот, то снова пара ${{v}_{0}}{{v}_{1}}$ блокировала бы $S$). ${{v}_{2}}$ не может быть одиноким в $T$ и, значит, соединяется в $T$ с ${{v}_{3}}$ (при этом по тем же причинам ${{v}_{3}}$ лучше, чем ${{v}_{1}}$, для ${{v}_{2}}$). И так далее без конца, что невозможно.

Это важное наблюдение говорит о том, что можно исключить из рассмотрения “нематчевых” агентов и считать, что $M$ и $W$ имеют одинаковые размеры.

Третье важное свойство (замеченное Конвеем и обнародованное Кнутом [129]) состоит в том, что множество SM стабильных матчингов с порядком ${{ \preccurlyeq }_{M}}$ является решеткой. При этом супремум (джойн) $S \vee T$ двух стабильных матчингов $S$ и $T$ задается так: $(S \vee T)(m) = \max (S(m),T(m))$. Грубо говоря, мужчине $m$ достается лучшая из женщин в этих двух матчингах. Для женщин – наоборот. Рассуждение тут напоминает приведенное выше и основано на сравнении двух матчингов. Аналогичная формула верна для любого числа стабильных матчингов. Естественно, ${{S}_{M}}$ является наибольшим элементом этой решетки.

Отсюда можно увидеть, что решетка SM дистрибутивна. Блэр [36] показал, что таким образом может получиться любая (конечная) дистрибутивная решетка; см. также [90], [142]. Что тоже говорит о том, что стабильных матчингов может быть много. Более тонкая структура приведена в [174], см. также [18].

3.3. Манипулирование

Еще одна тема интенсивно обсуждалась в литературе, посвященной стабильным марьяжам. Мы уже говорили, что алгоритм Гейла–Шепли (в котором предложения делают мужчины) дает стабильный матчинг, наилучший с позиций мужчин. Поэтому интуитивно правдоподобно, что мужчинам невыгодно искажать свои предпочтения, пытаясь добиться лучшего матчинга. И это действительно так. Напротив, женщины могут так манипулировать своими предпочтениями (т.е. так отвергать полученные предложения), что в результате они получат наилучший с позиции женщин матчинг. Вот эти вопросы мы и хотим обсудить в этом подразделе.

Впервые к этому вопросу обратились Дубинс и Фридман в [60], см. также [82], [83]. Они рассматривали марьяжную обстановку (с линейными предпочтениями) и предполагали, что действует $M$-оптимальный механизм (алгоритм Гейла–Шепли с предложениями мужчин). Они показали, что для мужчин называть свои истинные предпочтения – это доминирующая стратегия. Иными словами, если некоторый мужчина будет называть другие (неистинные) предпочтения, он не получит более лучший результат. Более того, никакая коалиция мужчин не может получить в результате манипулирования своими страгегиями исход, который строго лучше для всех членов этой коалиции.

Напротив, при действии этого $M$-оптимального механизма женщины могут успешно манипулировать. Но может быть это было связано со спецификой именно механизма Гейла–Шепли? Назовем произвольный механизм назначения матчинга стабильным, если он при получении на входе набора предпочтений всех агентов (мужчин и женщин) выдает в качестве результата стабильный (относительно этих предпочтений) матчинг. Рот и Сотомайор [160] доказали следующее

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

Следующий результат устанавливает пределы успешной манипуляции.

Теорема 3.4 (см. [58]). Пусть $P$ – профиль предпочтений участников марьяжа, а профиль $P{\kern 1pt} '$ отличается от $P$ только для участников некоторой коалиции $K \subseteq M \cup W$. И пусть $S$ – некоторый матчинг, стабильный при профиле $P{\kern 1pt} '$. Тогда он не может быть лучше (для всех членов этой коалиции $K$), чем любой стабильный матчинг при профиле $P$.

Много других результатов такого сорта можно найти в [160], [175], см. также [125]. Однако мне кажется, что тема манипулирования чрезмерно педалируется. Дело в том, что для успешного манипулирования нужно очень точно знать предпочтения всех агентов (не говоря уже о трудностях вычислительного порядка). Проиллюстрируем это на простейшем примере.

Пример 7. Двое мужчин $m$ и $m{\kern 1pt} '$ и две женщины $w$ и $w{\kern 1pt} '$. Мужчине $m$ нравится $w$, $m{\kern 1pt} '$ – $w{\kern 1pt} '$. Но желания женщин противоположны: $w$ хотела бы $m{\kern 1pt} '$, а $w{\kern 1pt} '$ – $m$. При действии алгоритма Гейла–Шепли $m$ обращается к $w$, а $m{\kern 1pt} '$ – к $w{\kern 1pt} '$, и мы получаем стабильный марьяж, наилучший для мужчин и наихудший для женщин. Желая улучшить свое положение, женщина $w$ могла бы отвергнуть предложение $m$; и если аналогично поступит $w{\kern 1pt} '$, они получат лучший матчинг. Но для этого она должна точно знать предпочтение $w{\kern 1pt} '$. Потому что в случае, если $w$ отвергнет $m$, а $w{\kern 1pt} '$ любит $m{\kern 1pt} '$, то $w$ останется одиночкой, что для нее еще хуже.

3.4. Линейное программирование и дробные матчинги

Параллельно задаче о стабильном марьяже Шепли и Шубик [166] рассмотрели задачу о стабильном назначении (assignement). Ее можно рассматривать как вариант марьяжа с “побочными платежами” (или с трансферабельной полезностью). Снова есть множество мужчин $M$ и женщин $W$. Но вместо предпочтений относительно противоположного пола для каждой пары $(m,w)$ указано число $u(m,w)$. Эти числа надо понимать как выигрыш (в денежной форме), который получается при образовании такой пары и который может быть произвольным способом перераспределен внутри этой пары. Кроме того, имеются “автаркические” выигрыши мужчин и женщин (если они остаются одиночками), которые без ущерба для общности можно считать равными 0.

Здесь тоже можно говорить о стабильных назначениях. Некоторое время эти две теории (стабильных матчингов и стабильных назначений) развивались параллельно. Сходство результатов бросалась в глаза, хотя применяемая техника была различной (“эклектичной” в случае матчингов и линейное программирование в случае назначений). Это вызывало желание строить унифицированную теорию. Представленная выше модель с контрактами включает обе теории. Мы не будем останавливаться на этом подробнее, отсылая к статьям [164], [178], [144], [15].

Для нас важно здесь появление “дробных” матчингов. Дробный матчинг задается неотрицательной функцией $x:C \to {{\mathbb{R}}_{ + }}$, которая удовлетворяет линейным равенствам

для любого $i \in I$. Иначе говоря, вместо того, чтобы целиком отдаваться одному договору, участники “делят” себя между несколькими договорами. Еще лучше представлять, что каждый агент не является “индивидом” (неделимым), но представляет континуум одинаковых субагентов общей массой 1. И доля $x(c)$ субагентов участвует в договоре $x$. Множество таких дробных матчингов образует выпуклый многогранник; а известно, что выпуклые задачи проще, чем целочисленные. Каждый “настояший” матчинг $S \subseteq C$ дает точку ${{1}_{S}}$ (характеристический вектор подмножества $S$) в этом политопе; на самом деле даже вершину политопа.

Нас, однако, больше интересуют стабильные дробные матчинги. Они удовлетворяют дополнительным линейным ограничениям, по одному для каждого ребра $b \in C$. Грубо говоря, каждое такое неравенство говорит, что это ребро неблокирующее. Более точно, для (бинарного) договора $c$ (между участниками $i$ и $j$) пишем $c \preccurlyeq b$, если $b \in C(i)$ и $c{{ \leqslant }_{i}}b$ или если $b \in C(j)$ и $c{{ \leqslant }_{j}}b$. Так вот, если $S$ стабильный матчинг и $x{{ = 1}_{S}}$, то выполнены неравенства

для любого (бинарного) договора $c \in C$ (“реберные неравенства”). В самом деле, это неравенство говорит, что для любого договора $c$ выполнено одно из двух: либо $c$ принадлежит $S$, либо $c$ хуже некоторого $s$ из $S$ для одного из участников договора $c$. Что есть не что иное, как условие S2 стабильности.

Это побуждает рассмотреть выпуклый политоп (многогранник) ${{P}_{{SM}}}$ стабильных дробных матчингов в $\mathbb{R}_{ + }^{C}$, заданный “матчинговыми” равенствами (2) и “реберными” неравенствами (3). В [178] (см. также [164]) установлен такой принципиальный факт:

Теорема 3.5. Политоп ${{P}_{{SM}}}$ есть выпуклая оболочка множества векторов ${{1}_{S}}$ для стабильных матчингов $S$.

Доказательство можно разделить на две части. Первая часть говорит, что этот политоп непуст. Это утверждение носит общий характер и верно для любого графа (и даже гиперграфа); мы к нему еще вернемся. Вторая часть более проста и уже существенно использует двудольность, а точнее тот факт, что любой цикл в двудольном графе имеет четный размер.

В частности, любой дробный стабильный матчинг представляется как выпуклая комбинация стабильных матчингов; два канонических разложения такого рода строятся в [9]. Теорема 3.5 перебрасывает мостик между теорией стабильных матчингов в двудольных графах и теорией линейных задач. Потому что крайние точки (вершины) политопа ${{P}_{{SM}}}$ – это фактически стабильные матчинги. Из этого описания сравнительно просто получаются многие приведенные выше факты, полученные “эклектическими” (т.е. комбинаторными) методами: существование, решеточность, одиночество, оптимальность.

Описание граней политопа ${{P}_{{SM}}}$ приведено в [155]. См. также [164], [90], [142], [26], [33], [174], [56], [9], [42] и более недавний обзор [66].

3.5. Стабильные потоки и сети

Быть может, здесь стоит сказать про недавнее развитие теории стабильных матчингов в сетях. Начало этому направлению положила статья Байю и Балинского [25], которые ввели понятие стабильных потоков в ориентированных графах (сетях). Это направление было подхвачено в [146] и [77]; в последней работе эта задача сводилась к двудольному случаю. См. также [122]. Более экономическая постановка приводится в работах [99], [96], [78]; здесь используется вариант стабильности, называемый стабильностью вдоль пути (trail stability), или цепной стабильностью.

4.1. Существование

Удобно (см. разд. 2.3) агрегировать всех мужчин в одного агента $M$ с ФВ $F$, которая определяется так: для $A \subseteq C$

и аналогично агрегировать всех женщин в одного агента $W$ с ФВ $G$, устроенной аналогично. $F$ и $G$ снова плоттовские ФВ. И как легко понять, стабильная сеть договоров в исходной задаче эквивалентна стабильной сети между двумя “агрегированными” агентами $M$ и $W$. Иными словами, можно считать, что у нас всего два агента! Мы ничего не теряем в содержании, но экономим на записях.

Следующий результат о существовании стабильных сетей обобщает теорему Гейла–Шепли.

Теорема 4.1. В описанной выше ситуации стабильные сети договоров существуют.

Хотя эту теорему можно получить прямо из теоремы Гейла–Шепли с помощью теоремы о редукции, мы расскажем о другом подходе, связанном с теоремами о неподвижных точках.

Видимо, впервые идея о применении неподвижных точек к задачам о стабильности появилась в [72], [171]. Адачи [13] (в ситуации классического марьяжа) описал множество SM стабильных матчингов как множество неподвижных точек некоторого монотонного оператора. Применительно к общему случаю, о котором мы говорим, эту идею в наиболее полном виде реализовал Флейнер [74]. Ниже мы наметим эту идею в несколько ином (хотя и близком) исполнении.

Рассмотрим множество ${{2}^{C}} \times {{2}^{C}}$ пар $(A,B)$, снабженное следующим частичным порядком $ \leqslant $:

А в нем рассмотрим множество SS т.н. полустабильных пар. Пара $(Y,Z)$ называется полустабильной, если $Y \cup Z = C$ и $G(Y) \subseteq F(Z)$. Заметим, что если $G(Z) = F(Y)$, то $S = G(Z) = F(Y)$ является стабильным множеством. Так что такие стабильные пары можно отождествить со стабильными множествами.

Для каждой полустабильной пары $(Y,Z)$ определим новую пару $\Phi (Y,Z) = (Y{\kern 1pt} ',Z{\kern 1pt} '{\kern 1pt} )$, где

Очевидно, что $Y \subseteq Y{\kern 1pt} '$, а $Z{\kern 1pt} ' \subseteq Z$. Можно показать, что для полустабильной пары $(Y,Z)$ пара $\Phi (Y,Z)$ тоже полустабильна, так что отображение $\Phi $ задает монотонную динамику на множестве SS полустабильных пар.

Лемма 4.2. Если полустабильная пара $(Y,Z)$ неподвижна относительно оператора $\Phi $, то эта пара стабильна и тем самым дает стабильную сеть.

В самом деле, равенство $Z = Z{\kern 1pt} '$ означает, что $F(Z) = G(F(Z))$, а равенство $Y = Y{\kern 1pt} '$ – что $F(Z)$ содержится в $Y$. В частности, $G(Y) \subseteq F(Z) \subseteq Y$, откуда по свойству отбрасывания мы получаем $G(F(Z)) = G(Y)$. Таким образом, $F(Z) = G(Y)$ и является стабильной сетью контрактов.

В частности, каждая максимальная полустабильная пара дает стабильную сеть. На самом деле, каждая неподвижная точка отображения $\Phi $ дает стабильную сеть (и обратно). Это позволяет “строить” все стабильные сети. Надо начать с произвольной полустабильной пары ${{P}_{0}} = (Y,Z)$ и строить последовательные приближения ${{P}_{{k + 1}}} = \Phi ({{P}_{k}})$; эта последовательность ${{P}_{0}},{{P}_{1}},...$ стабилизируется через конечное число шагов (в силу монотонности) и застревает в неподвижной точке, которая фактически является стабильной сетью.

Отметим, что процесс $\Phi $ фактически реализует идею, заложенную в оригинальном алгоритме Гейла–Шепли. Множество $Y$ реализует все предложения, полученные $G$-агентом от $F$-агента, а $Z$ – доступные к текущему моменту контракты для $F$-агента (Мужчины). Последний выбирает из $Z$ самые хорошие для него $F(Z)$ и добавляяет их к $Y$, формируя $Y{\kern 1pt} '$. $G$-агент (Женщина) из $Y'$ оставляет наилучшие для нее $G(Y')$ (равное, между прочим, $G(Y \cup F(Z)) = G(G(Y) \cup F(Z)) = $ $ = G(F(Z)$) в силу включения $G(Y) \subseteq F(Z))$, отклоняя $F(Z) - G(F(Z))$ и уменьшая тем самым $Z$ до $Z{\kern 1pt} '$.

Вспоминая общее описание стабильных сетей как неподвижных точек (раздел 2), можно сказать, что удача тут связана с тем, что удается “общий” оператор разложить на убывающую и возрастающую компоненты.

4.2. Оптимальность и решеточность

Аналогичные факты имеют место и в общей ситуации (с плоттовскими ФВ). Здесь для оценки исходов мы будем использовать гиперпорядок Блэра ${{ \preccurlyeq }_{F}}$ (1), ассоциированный с “мужской” ФВ $F$ ($ = \bigcup\nolimits_m^{} {{{f}_{m}}} $). Вспомним динамику $\Phi $, использованную в доказательстве существования. Если мы начинаем процесс последовательного приближения с пары $(\emptyset ,C)$, то процесс сходится к некоторому стабильному состоянию ${{S}_{M}}$. Утверждается, что это состояние не хуже (в смысле ${{ \preccurlyeq }_{F}}$), чем любое другое стабильное состояние $T$. Это утверждение получается по индукции с помощью следующей леммы.

Лемма 4.3 (см. [54]). Пусть $(Y.Z)$ – полустабильная пара, $T$ – стабильное подмножество в $C$, и $T{{ \preccurlyeq }_{F}}Z$. Тогда $T{{ \preccurlyeq }_{F}}Z{\kern 1pt} '$, где $\Phi (Y,Z) = (Y{\kern 1pt} ',Z{\kern 1pt} '{\kern 1pt} )$, см. (4).

Таким образом, сеть ${{S}_{M}}$ наилучшая для мужчин (среди стабильных). Напротив, она наихудшая для женской половины. Это видно из следующого утверждения.

Предложение 4.4. На множестве St стабильных сетей “мужское” гиперотношение ${{ \preccurlyeq }_{F}}$ является гиперпорядком (то есть антисимметрично), причем противоположным “женскому” гиперпорядку ${{ \preccurlyeq }_{G}}$.

Последнее утверждение Рот [158] называл ‘поляризацией интересов’.

В силу свойства противоположности мы ограничимся рассмотрением только порядка ${{ \preccurlyeq }_{F}}$ на множестве St. То, что в этом посете (т.е. частично упорядоченном множестве) есть максимальный элемент ${{S}_{M}}$ (и минимальный ${{S}_{W}}$) намекает на то, что этот посет является решеткой. И это действительно так. Впервые на это обратил внимание Кнут, затем Рот; окончательную ясность внес Блэр [37], который именно для этой цели и ввел свой гиперпорядок. См. также [74], [54].

Теорема 4.5. Посет $(St,{{ \preccurlyeq }_{F}})$ является решеткой.

В общем случае решеточные операции $ \vee $ и $ \wedge $ устроены непросто. Однако при дополнительном требовании кардинальной монотонности можно описать их более явно.

ФВ $f$ (на абстрактном множестве $X$) называется кардинально монотонной (в [74] говорится о “возрастании”, а в [94] – о “законе агрегированного спроса”), если $A \subseteq B$ влечет ${\text{|}}f(A){\kern 1pt} {\text{|}} \leqslant {\text{|}}f(B){\kern 1pt} {\text{|}}$. Это своего рода монотонность, но не теоретико-множественная, а численная. Если ФВ $f$ к тому же заменимая, то кардинальная монотонность влечет условие отбрасывания, так что такие ФВ являются плоттовскими. Чтобы более ясно увидеть различие (или усиление), представим, что мы из множества $A$ удалили некоторый выбранный элемент $a \in f(A)$. Плоттовость влечет, что в этом случае все элементы $f(A) - a$ останутся в выборе из $A - a$, и быть может добавится несколько новых элементов. Так вот кардинальная монотонность состоит в том, что добавиться может не более одного нового элемента.

Например, выбор с квотой (см. пример 5) удовлетворяет этому требованию. А вот выбор, рационализируемый предпорядком (пример 4), не всегда. При условии, что ФВ $F$ и $G$ кардинально монотонные (и заменимые), верхняя грань стабильных сетей $S$ и $T$ устроена так: $S \vee T = F(S \cup T)$, а $S \wedge T = G(S \cup T)$.

Применительно к классическому марьяжу, матчинг $S \vee T$ сопоставляет мужчине $m$ лучшую для него женщину из матчингов $S$ и $T$. Можно показать, что решетка стабильных сетей в случае кардинально монотонных ФВ тоже дистрибутивна.

4.3. Феномен сельских больниц

Речь идет о т.н. феномене “сельских больниц” (rural hospital). Представим себе, что мы используем алгоритм Гейла–Шепли для распределения студентов-медиков по больницам. И студентов меньше, чем вакансий. Довольно естественно ожидать, что недоукомплектованными окажутся больницы, находящиеся в сельской местности, в силу их меньшей привлекательности. Но быть может другая процедура получения стабильных распределений окажется более благосклонной к сельским больницам?

Вспомним, что в ситуации классического марьяжа невостребованные агенты (одиночки) были одни и те же в любом стабильном матчинге. Оказывается, что аналогичное утверждение верно и в общем случае. Однако тут приходится требовать, чтобы ФВ агентов были не просто плоттовскими, но еще и кардинально монотонными. В этом случае верно

Предложение 4.6 (см. [159], [74]). Если ФВ мужчин и женщин кардинально монотонны, то в любой стабильной сети $S$ размер $S(m)$, как и $S(w)$, один и тот же.

Плоттовская ФВ $f$ называется заполняющей квоту (quota-filling; в [43] используется термин acceptance), если для некоторого числа $q$ выполнено свойство: $f(A)$ содержит $q$ элементов, если ${\text{|}}A{\kern 1pt} {\text{|}} \geqslant q$. Можно показать (см. [127]), что такая ФВ кардинально монотонна, и что $f(A) = A$, если ${\text{|}}A{\kern 1pt} {\text{|}} \leqslant q$.

Предложение 4.7. Если предпочтения мужчин и женщин заполняют квоты, то множество $S(a)$ для агента, не выбравшего квоту, одно и то же (не зависит от конкретной стабильной сети $S$).

В самом деле, пусть агент $a$ не выбрал квоту ${{q}_{a}}$, а $S$ и $T$ – две стабильные сети. Тогда размеры $S(a)$ и $T(a)$ одинаковы (и равны, скажем, $k < {{q}_{a}})$. И если эти множества различны, то размер $S(a) \cup T(a)$ больше $k$, а значит и размер ${{f}_{a}}(S(a) \cup T(a))$ больше $k$. Но мы знаем из предыдущего, то это множество равно $(S \vee T)(a)$ для стабильной сети $S \vee T$, и поэтому его размер должен равняться $k$.

Это означает, что агенты стратифицируются на две “лиги” – “высшую” и “низшую”. Высшая лига составлена из укомплектованных больниц и принятых в них врачей. И внутри этой лиги прикрепление врачей к больницам может варьироваться. Больницы же из низшей лиги получают одних и тех же врачей тоже из низшей лиги. Феномен “сельских больниц” в ситуации “мэни-ту-мэни” (и нужные для ее выполнения области предпочтений) обстоятельно обсуждается в работе [127].

Алгоритмы для нахождения всех стабильных матчингов см. в [140], [56].

5.1. Классический руммэйт

Ситуация классического руммэйта похожа на классический марьяж; различие лишь в том, что мы отказываемся от двудольности графа. Многие результаты переносятся, но главное отличие в том, что стабильные матчинги уже не всегда сушествуют. Это показывает уже простейший пример с тремя агентами, приведенный в [81]. В [10] утверждается, что существование стабильного руммэйта гарантировано только в двудольном случае. В связи с этим два направления деятельности представляются интересными. Первое – найти условия, когда стабильность имеет место. И второе – найти подходящее обобщение, которое существует уже всегда.

Собственно говоря, ситуация с руммэйтом двинулась с места после того, как Ирвинг в [108] предложил алгоритм (значительно более сложный, чем Гейла–Шепли), который по окончанию своей работы либо выдавал некоторый стабильный матчинг, либо утверждал, что такого матчинга не существует. Мы не будем описывать этот алгоритм, отсылая к оригинальной статье.

После этого последовали статьи о разных релевантных постановках (предпочтения со связками и три разных понимания стабильности в этом случае, с ограниченными списками и т.п.): [116], [107], [109], [112], [44], [137], [138], [139], [69], [57]. Многие успехи были подытожены в монографии [89]. См. также [69], [153], [47].

Алгоритмы – это хорошо, но они не всегда проясняют структуру. В 1991 г. Тан [173], основываясь на алгоритме Ирвинга, доказал существование некоторой структуры, названной им стабильным разбиением (stable partition), которая позволяет сразу и убедительно показать, существует стабильный матчинг или нет. Как пишет Тан, наличие “нечетной части” у этого разбиения позволяет просто убедиться в том, что стабильный матчинг невозможен. Тогда как подход Ирвинга требует понимания работы этого сложного алгоритма, предназначенного скорее для машинной проверки.

Хорошее изложение этого вопроса дано в [14]. Начнем с определения стабильного разбиения. Это некоторое подмножество $S$ ребер графа $C$, которое обладает следующими тремя свойствами.

1) Связные компоненты графа $S$ – циклы или ребра.

2) Каждая циклическая компонента может быть так циклически пронумерована, что для каждой вершины предыдущее ребро-договор хуже последующего (относительно линейного порядка < этой вершины-агента).

3) Для любого ребра $c$, не вошедшего в $S$, существует вершина-агент $i$, покрытый $S$ и участвующий в $c$ (так что $C(i)$ содержит $c$ и пересекается с $S(i)$) и такой, что $c{{ < }_{i}}S(i)$. (Последнее условие говорит, что $c$ не может блокировать $S$).

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

Предложение 5.1. У любого стабильного разбиения нечетные циклические компоненты одни и те же.

Как следствие мы получаем, что стабильного матчинга нет, если стабильное разбиение содержит нечетную циклическую компоненту.

Однако все эти замечания повисали бы в воздухе, если бы не следующий принципиальный факт.

Теорема 5.2 (см. [173]). В ситуации классичесекго руммэйта существует стабильное разбиение.

Тан конструктивно доказывал это с помощью некоторой модификации алгоритма Ирвинга. Более изящное и короткое рассуждение приведено в [14] с апелляцией к лемме Скарфа. Рассмотрим “дробную” версию стабильного матчинга, как в разделе 3. Согласно лемме Скарфа, существует “стабильный дробный матчинг”, т.е. такой дробный матчинг $x \in \mathbb{R}_{ + }^{C}$, что у каждого ребра $c \in C$ имеется конец $i$ ($ \in P(i)$), для которого $\sum\nolimits_{c{{ < }_{i}}s} \,x(s) = 1$. (Иначе говоря, договора агента $i$, которые хуже $c$, имеют нулевые веса.) В качестве $S$ возьмем носитель $x$, т.е. ребра с положительным весом. Если $x(s) = 1$, мы имеем изолированное ребро. Поэтому далее мы будем считать, что веса отличны от 0 и 1. Такие ребра можно ориентировать так, что конец ребра – это вершина $i$ с $\sum\nolimits_{c{{ < }_{i}}s} \,x(s) = 1$; ясно, что такая вершина только одна. Причем если такая стрелка входит в вершину, то другая выходит, и наоборот. Отсюда следует, что $S$ состоит из изолированных ребер и изолированных направленных циклов. Наконец, условие 3) определения стабильного разбиения выполнено в силу следующего замечания. Если $c$ не принадлежит $S$, т.е. $x(c) = 0$, то возьмем тот его конец $i$, для которого $\sum\nolimits_{c{{ < }_{i}}s} \,x(s) = 1$, т.е. $\sum\nolimits_{t{{ < }_{i}}c} \,x(t) = 0$. Последнее равенство означает, что если $s \in S(i)$, то $s$ лучше, чем $c$, для $i$.

Таким образом $S$ действительно стабильное разбиение.

Подводя итог этому направлению, можно сказать, что все агенты разбиваются на три группы (или фракции). Первая (“лед”) состоит из одиночек, вторая (“ламинарная”) состоит из пар, а третья (“турбулентная”) состоит из нечетных циклов. Если мы удаляем третью часть, то оставшиеся агенты могут образовать стабильный матчинг, быть может, не один. Одиночки в этом матчинге также канонически определены, как показывает то же рассуждение, что и для марьяжа.

В [174] показано, что множество стабильных руммэйтов обладает естественной структурой медианы, слабой замены структуры решетки для марьяжей.

Так как в общей ситуации стабильного руммэйта может не существовать, несколько работ было посвящено поиску “почти стабильных” или “приблизительно” стабильных матчингов, см. [12], [91–93].

5.2. Общий случай

Теперь перейдем к общему случаю, когда предпочтения агентов задаются плоттовскими ФВ. Подмножества в $C$ назывались иногда сетями партнерств, намекая, что партнеров может быть несколько. Хотя теорема о редукции говорит, что можно ограничиться слабо-порядковыми ФВ, наука развивалась не так. Первоначально внимание было уделено более частному (хотя и очень важному) случаю, когда предпочтения агентов были линейными с квотами. Иначе говоря, у каждого агента $i$ есть линейный порядок ${{ < }_{i}}$ (на множестве $C(i)$ доступных ему бинарных контрактов плюс автаркия), и есть квота ${{q}_{i}} \geqslant 1$ на допустимое число контрактов.

На эту тему была статья [113], где сети партнерств называались фикстюрами (fixture). Каждый агент заключает партнерство (контакты) с ${{q}_{i}}$ другими агентами; стабильность понимается как обычно. Если квоты равны 1, мы получаем ситуацию классического руммэйта. В [113] было предложено обобщение алгоритма Ирвинга.

Близкая постановка была изучена в [44]. Авторы говорили об активностях (когда граф имел параллельные ребра), и о партнерстве, когда агенты могли заключать несколько договоров, число которых ограничивалось квотой. Авторы показывают, как общая задача такого рода сводится к классическому руммэйту. Делается это, грубо говоря, за счет клонированияя агентов, примерно как в теореме 2.3 о редукции.

Еще интереснее работа Флейнера [76], где он предполагает, что предпочтения на $C(i)$ задаются кардинально монотонными плоттовскими ФВ. Он вводит понятие стабильного полу-партнерства, обобщая понятие стабильного разбиения Тана. Основная его теорема, обобщающая Тана, утверждает, что такое полу-партнерство всегда существует, что нечетные циклы любого стабильного полу-партнерства одни и те же, и отсутствие нечетных циклов необходимо и достаточно для существования стабильного партнерства (стабильной сети).

Кроме этого Флейнер устанавливает интересный структурный результат в стиле “сельских больниц” из 4.3. Что при тех же условиях на предпочтения число партнерств для каждого агента $i$ не зависит от выбора стабильной сети. А если ФВ квотируемые (см. пример 5), то партнеры у агента, не выбравшего квоту, одни и те же (его теорема 5.1). На самом деле, он доказывает даже более тонкое свойство. Пусть стабильные сети существуют. Тогда для любого агента $i$ можно разбить множество $C(i)$ на части ${{C}_{0}}(i),{{C}_{1}}(i),...,{{C}_{{k(i)}}}$ (где $k(i)$ – число партнерств $i$ в любой стабильной сети) так, что для любой стабильной сети $S$ пересечение $S(i)$ с ${{C}_{0}}(i)$ пусто, а пересечения $S(i)$ с ${{C}_{1}}(i),...,{{C}_{{k(i)}}}$ – одноэлементные. Это означает некоторое ранжирование партнеров (или договоров), и стабильная сеть дает каждому агенту по договору каждого ранга (исключая “совсем неприемлемые” из ${{C}_{0}}$).

Одним словом, читайте и перечитывайте Флейнера!

6.1. Равновесие и стабильность

Итак, пусть $(I,C)$ – гиперграф с множеством вершин-агентов $I$ и множеством гиперребер-договоров $C$. У каждого агента $i$ задан слабый порядок ${{ \leqslant }_{i}}$ на множестве $C(i)$, и выбор этого агента из меню $A \subseteq C(i)$ состоит из всех максимальных (относительно ${{ \leqslant }_{i}}$) элементов. Вместо порядков ${{ \leqslant }_{i}}$ можно работать с функциями полезности ${{u}_{i}}:C(i) \to \mathbb{R}$.

Напомним, что (в слабо-порядковой обстановке) сеть договоров $S \subseteq C$ являетсяя стабильной, если

1) для любого агента $i$ множество $S(i)$ состоит из эквивалентных (${{ \approx }_{i}}$) договоров;

2) если договор $c$ обладает тем свойством, что $S(i){{ \leqslant }_{i}}c$ для всех $i \in P(c)$, то $c \in S$.

Предполагая наличие автаркических договоров, мы видим из 2), что $S(i)$ непусто для любого $i$. Обозначая ${{u}_{i}}(S) = {{u}_{i}}(S(i))$, мы получаем вектор $u(S) = ({{u}_{i}}(S),i \in I)$ в ${{\mathbb{R}}^{I}}$, вектор полезностей при действии сети $S$. Этот вектор $u = u(S)$ позволяет описать систему $S$: она состоит из таких договоров $s$, что ${{u}_{i}}(s) = {{u}_{i}}$ для всех $i \in P(s)$. Такое описание наводит на мысль формулировать понятие стабильности в терминах вектора $u \in {{\mathbb{R}}^{I}}$. Скажем, что вектор $u$ равновесный, если

а) он достижим или обоснован: для любого $i \in I$ существует договор $c \in C(i)$, что ${{u}_{j}} \leqslant {{u}_{j}}(c)$ для любого $j \in P(c)$;

б) он недоминируем: если для договора $c$ выполнено ${{u}_{i}} \leqslant {{u}_{i}}(c)$ для всех $i \in P(c)$, то ${{u}_{i}} = {{u}_{i}}(c)$ (снова для всех $i$ из $P(c)$).

Первое требование говорит, что претензии агента $i$ на получение полезности ${{u}_{i}}$ обоснованы. Второе означает отсутствие блокирующих договоров: договор $c$ блокирует вектор $u$, если дает своим участникам не меньше, чем $u$, а некоторому даже строго больше.

Предложение 6.1. Если сеть $S$ стабильная, то вектор $u(S)$ равновесный. Обратно, если $u$ равновесный, то система $S = \{ s,{{u}_{i}}(s) = {{u}_{i}}\;{\text{для}}\;{\text{всех}}\;i \in P(s)\} $ стабильна.

Доказательство. Первое очевидно. Проверим второе. Начнем с условия 1). Пусть $s$ и $t$ принадлежат $S(i)$; нужно поверить, что ${{u}_{i}}(s) = {{u}_{i}}(t)$. Так как $s \in S$, а $i \in P(s)$, то ${{u}_{i}}(s) = {{u}_{i}}$; аналогично для t.

Проверим теперь условие 2). Пусть ${{u}_{i}} \leqslant {{u}_{i}}(c)$ для всех $i \in P(c)$; мы должны показать, что тут везде равенства и поэтому $c \in S$. Но это видно из условия б).

Как следствие получаем, что вместо стабильных сетей можно говорить о равновесных векторах. Что несколько проще. Особенно если заметить, что условия a) и б) “тянут” в разные стороны. Если вектор $u$ удовлетворяет условию a), то и любой меньший (нестрого) тоже удовлетворяет условию a). Напротив, если $u$ удовлетворяет б), то и любой больший удовлетворяет. Так что мы имеем два подмножества $A(C)$ и $B(C)$ в ${{\mathbb{R}}^{I}}$; первое состоит из векторов, удовлетворяющих a) и направленное “вниз”, тогда как второе – из удовлетворяющих б) и направленное “вверх”. Важно, что они не могут пересекаться по внутренним точкам. Потому что если вектор $u$ – внутренняя точка $A$ и $B$, то при малом $\varepsilon > 0$ вектор $u - \varepsilon $ (точнее, $u - \varepsilon {{1}_{I}}$) тоже принадлежит $A$ и $B$. В силу a) (для любого $i$) существует $c \in C(i)$, такой что $c$ дает не меньше $u$. Но тогда этот же $c$ дает строго больше, чем $u - \varepsilon $, что противоречит условию б) для $u - \varepsilon $.

Вывод такой: $A$ и $B$ могут пересекаться только по границе. И любые точки пересечения – это равновесные вектора. Но они могут вообще не пересекаться! Потому что мы знаем, что стабильных сетей может не быть. В этой связи видятся два пути или направления деятельности.

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

Второй – как-то разумно и осмысленно ослаблять условия стабильности, вводя понятия “полустабильности” или “ослабленной стабильности”.

6.2. Дробные системы договоров

Начнем с того, что условия “равновесности” очень напоминают условия, которые накладываются на элементы из ядра кооперативной игры. Условие a) – нечто типа достижимости вектора “платежей” или “выплат”. А условие б) – это условие недоминируемости. А в теории игр много занимались вопросами непустоты ядра. Там тоже вставали эти два вопроса. И ответы на оба оказались тем или иным образом связаны с теоремой (леммой) Скарфа. А именно, при условии некоторой сбалансированности Скарф показал, что ядро непусто.

Вот в этом направлении мы и пойдем, заодно вспоминая про дробные матчинги и системы договоров. Дробной системой договоров будем называть отображение $x:C \to {{\mathbb{R}}_{ + }}$, которое удовлетворяет линейным ограничениям

(Образно говоря, каждый участник долей $x(c)$ участвует с коалиции $c$.) Обозначим многогранник таких дробных договоров $P(I,C)$.

Определение. Пара $(x,u)$ (где $x$ – дробная система договоров, а $u \in {{\mathbb{R}}^{I}}$ – вектор платежей) называется равновесной, если

a*) $u$ достижим в том смысле, что если $x(c) > 0$, то $u\,{\text{|}}\,P(c) \leqslant u(c)$ (развернуто: для любого $j \in P(c)$ выполнено ${{u}_{j}} \leqslant {{u}_{j}}(c)$);

б*) $u$ неблокируем в том смысле, что нет такого договора $c$, что $u\,{\text{|}}\,P(c) \ll u(c)$ (строго меньше по всем компонентам).

Так вот, теорема Скарфа (в форме, приданной ей в работе [5]) утверждает, что такая равновесная пара всегда существует. Напрашивается положить $S = \{ c \in C,x(c) > 0\} $, т.е. взять носитель $x$. Такая сеть договоров похожа на стабильную. Единственное, что не хватает до стабильности – возможное нарушение свойства индивидуальной рациональности. Эта сеть может давать аген-ту $i$ несколько договоров $S(i)$, которые неравноценны для $i$. Вот здесь и начинается развилка.

Первый путь. Допустим, удалось найти подсистему $T \subseteq S$, которая дает разбиение $I$ (в том смысле, что каждый агент $i$ входит в $P(t)$ для единственного договора $t \in T$). Тогда система $T$ является стабильной в слабом смысле: нет договоров, которые давали бы их участникам строго больше.

Второй путь – отказаться от требования индивидуальной рациональности S1. Рассмотрим эти пути более подробно.

6.2.1. Первый путь. Теорема Скарфа говорит, что существуют равновесная пара $(x,u)$ и соответственно система $S = \operatorname{supp} (x)$. В принципе условие достижимости относится только к $S$, и мы могли бы рассмотреть многогранник тех $x$, которые являются дробными системами договоров и носитель которых лежит в $S$. В частности, интересоваться вершинами такого многогранника. И если эта вершина целая (т.е. значения $x(c)$ равны 0 или 1), мы получали бы разбиение $T$ множества $I$. Такая (“разбивающая”) система $T$ была бы (слабо) стабильной системой договоров.

Существование целых вершин у многогранника $P(I,C)$ тесно связано с совершенством графа $\Gamma = L(I,C)$ в обозначениях [3]. Вершинами этого графа служат договора (так что $V(\Gamma ) = C$); договора $c$ и $c{\kern 1pt} '$ соединены ребром, если $P(c)$ и $P(c{\kern 1pt} '{\kern 1pt} )$ пересекаются (т.е. когда есть агент $i$, участвующий в обоих договорах). Так вот, если этот граф совершенный (определение см., например, в [3]), то многогранник $P(I,C)$ имеет целые вершины. Поэтому такой гиперграф универсально стабилен (стабилен при любом слабо-порядковом оснащении).

Такие универсально стабильные гиперграфы (они называются также нормальными, см. [39], [136]) можно строить по совершенным графам. Пусть $\Gamma = (V,E)$ – произвольный граф; кликой в нем называется (максимальный по включению) полный подграф в $\Gamma $ (т.е. любые две вершины соединены ребром). Так вот, объявим клики агентами, а вершины графа – договорами. То есть образуем гиперграф $H$ с вершинами-агентами K (множество клик в $\Gamma $) и гиперребрами-договорами $V$ (т.е. $I = K,$ $C = V$). Понятно, что $L(H)$ вершинами имеет вершины из $V$, и эти вершины соседние, если лежат в одной клике графа $\Gamma $, то есть соседние в графе $\Gamma $. Так что $L(H) = \Gamma $. И если граф $\Gamma $ был совершенным, то гиперграф $H = (K,V)$ нормален и потому универсально стабилен.

В частности, двудольные графы совершенные и универсально стабильные; другой интересный универсально стабильный гиперграф – это гиперграф поддеревьев произвольного дерева. Подробнее об этом см. в [4], [39], [120], [124].

6.2.2. Второй путь предлагает понятие метастабильной системы договоров, см. [55].

Определение. Сеть договоров $S \subseteq C$ называется метастабильной (при заданном семействе $({{u}_{i}},i \in I)$ функций полезности агентов), если выполнены два условия:

MS1) Множество $S(i)$ непусто для любого $i \in I$. И мы полагаем $u(i) = \min \{ {{u}_{i}}(s),s \in S(i)\} $. Это как бы “гарантированный” уровень полезностей всех агентов.

MS2) Для любого договора $c$ существует участник $i$ этого договора, для которого ${{u}_{i}}(c) \leqslant u(i)$. Это условие типа отсутствия блокирования; договор $c$, дающий всем его участникам строго больше, чем $u$, явно блокирует гарантированный уровень полезности системы $S$.

В работе [55] доказывается существование метастабильных систем и обсуждается связь таких систем со стабильностью.

6.2.3. Трехполые семьи. Есть довольно много работ, посвященных исследованию стабильности для трехполых семей (т.е. трехдольных и $m$-дольных графов), см. [17], [20], [38], [52], [68], [102], [114], [143], [147], [50], [134], [170], [135].

6.2.4. Дополнительность. До сих пор мы предполагали, что ФВ, описывающие предпочтения агентов, заменимые (и даже Плоттовские). Это потому что в большинстве работ на тему стабильноти накладывались такие условия. И фактически есть лишь одна работа [157] (см. также [21], [104]), где накладывается в некотором смысле противоположное условие комплементарности (дополнительности). Поэтому стоит сказать об этой работе, упрощая в чем-то их модель, но оставляя главное.

Как и выше, мы имеем гиперграф $(I,C)$ и ФВ ${{f}_{i}}$ для каждого агента $i$. Назовем ФВ $f$ комплементарной (дополнительной), если она монотонна, т.е. если $A \subseteq B$ влечет $f(A) \subseteq f(B)$. Формально это условие тесно связано с заменимостью: если мы определим ФВ $g$ равенством $g(A) = A - f(A)$, мы получим заменимую ФВ, и наоборот. Но если заменимость говорила, что при выбытии нанятого работника все остальные нанятые продолжают быть нанятыми (выбранными), то дополнительность допускает увольнение некоторых других нанятых работников и не позволяет брать новых. Так что предпочтения тут носят кардинально иной характер.

В работе [157] устанавливается существование (и даже единственность) стабильных сетей при условии дополнительности.

Казалось бы, замечательный результат. Однако настораживают две вещи. Первая – доказательство существования настолько тривиально, что указываает на некую неглубину результата. И второе. Если договора дополняют друг друга в том смысле, что их совместное использование значительно повышает привлекательность и пользу, то это подсказываает, что мы должны эту совокупность рассматривать как новый договор (см. пример 0 из разд. 2). Тем самым за счет некоторого естественного расширения договоров можно надеяться вернуться в старую обстановку с заменимыми договорами.