Лекция 22. Ядро

 

Ядро. Ядром, коалиционной игры V называется множество всех допустимых недоминируемых распределений; обозначается оно C(V).

В силу важности этого понятия слегка перепишем определение. Пусть да­но распределение х. Скажем, что коалиция К отвергает х (или может его улучшить), если существует такой вектор у к из V(K)7 что для любого игрока / из коалиции К выполнено у; > х-,. Тогда ядро состоит из таких допусти­мых распределений (т.е. элементов V(N))7 которые не отвергаются никакой коалицией. Можно и так переписать: элемент х принадлежит ядру C(V) тогда и только тогда, когда

a. х £ V(N), и

b. Для любой (непустой) коалиции К проекция хк не принадлежит вну­тренности множества V(K).

Отсюда видно, что ядро - замкнутое и ограниченное подмножество в V(N).

Элементы из ядра могут претендовать на звание хорошего решения игры. Они оптимальны по Парето (лежат на границе Парето V(N))7 и индиви­дуально рациональны. Ядро может оказаться большим (и тогда предстоят приятных хлопоты с выделением какого-то "самого хорошего" элемента из ядра). Менее приятно, если ядро пусто. А так бывает довольно часто. Напри­мер, пусть трое делят 100 руб., и любая пара может обеспечить себе 100 руб. Тут ядро пусто, и они вряд ли договорятся. Ниже мы немного скажем, что делать при пустом ядре.

Ядро экономики. Понятие ядра интересно тем, что оно естественно возникает в эко­номике. Собственно, как и понятие равновесия, оно там впервые и появилось, хотя и в частном случае. У Эджворта, в 1881 г., за много лет до появления его в теории игр (Джил-лис, 1959).

Представим, что имеется экономика обмена. Это значит, что участники / имеют началь­ные запасы u>i, принадлежащие пространству товаров R" . Кроме того у каждого участника имеется функция полезности щ, определенная на этом ортанте.

Распределением (allocation) называется семейство векторов Х{ е R" , г G N, такое что V\ .r( = V( w'( (или <, в зависимости от постановки). Спрашивается, как им "правильно" перераспределить свои начальные запасы? Конечно, каждый участник откажется участ­вовать в обмене, если он в результате получит меньше (в смысле полезности), чем свой начальный запас и){. Но то же можно сказать и о любой коалиции. Коалиция К отвергнет распределение (.г(). если пользуясь только своими начальными запасами Ш{, где г 6 К, онаможет так перераспределить их, что полезность для ее членов будет больше, чем //((.г(). Это и есть ядро. Сам Эджворт говорил о кривой контракта, потому что рассматривал случай двух участников и рисовал "ящик Эджворта".

Большой удачей является то, что ядро экономики непусто при простых условиях. Ви­димо, проще всего убедиться в этом с помощью понятия конкурентных равновесий. На­помним, что так называется распределение (х{), для которого найдется цена (т.е. вектор р е К"), такой что для каждого / набор х, является наилучшим в бюджетном множестве В{(р) = {х,рх < рш{}. Как легко понять, любое равновесное распределение принадлежит ядру. Действительно, предположим, что коалиция К может так перераспределить свой начальный запас (//,-. У]( /ч- /// = У]( /ч- *;,•). что //,- стали лучше, чем х, (для г е К). Так как х, были наилучшими в бюджетных множествах, мы должны заключить, что их стоимости превышают стоимости начальных запасов, руг > ршг. Складывая по / е /\. мы получаем,

что р(^2{еКУг) > Р(^2цеКШ^1 ЧТ0 Противоречит равенству ^2{еКУг = У](  к ^'(. □

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

Интересная экономическая проблема, также поднятая Эджвортом, состоит в прибли­жении равновесий ядром. Дело в том, что в основе конкурентного поведения лежит по­стулат, что каждый участник настолько мал, что не может повлиять на цену. Поэтому можно ожидать, что когда участники малы, то ядро "почти" совпадает с конкурентными равновесиями. Имеется довольно много результатов, которые уточняют это утверждение. В наиболее чистом виде оно реализовано Ауманном: если имеется континуум участников, то ядро в точности совпадает с множеством конкурентных равновесий.

Решение Неймана-Моргенштерна. Вернемся к коалиционным играм. Возможная пустота ядра вынудила искать другие, более слабые понятия ре­шения. И тут нельзя не упомянуть исторически первое понятие решения по Нейману-Моргенштерну (или Н-М-решение).

Назовем дележом (импутацией) оптимальный и индивидуально рацио­нальный вектор х из иначе говоря, х должен лежать на границе Па-рето множества У(М) и для любого г должно выполняться неравенство х\ > тах(у,у £ = Щ- Обозначим через Е(¥) множество всех дележей игры V.

Определение. Н-М-решением игры V называется подмножество И С Е(У), которое удовлетворяет двум условиям:

(*) если у £ Е{у) \ Z) то найдется х £ Z, который доминирует у. (**) если же х и у из ^, то х не доминирует у.

Можно сказать, что (**) - это условие внутренней стабильности 2тогда как (*) - условие внешней стабильности. Грубо говоря, решение в совокупно­сти доминирует все, а внутри себя свободно от доминирования.

Например, в игре большинства (дележка 300 долларов; и(1,2,3) = 300, и(2-элементных коалиций)=300, г;(игрока) =0) множество из трех распреде­лений (150,150, 0), (150, 0,150), (0,150,150) образует Н-М-решение. В самом деле, как легко понять, никакой из этих дележей друг друга не доминирует. С другой стороны, возьмем произвольный дележ (ж1,Ж2,жз); это значит, что х\ неотрицательны и в сумме равны 300. Но тогда два числа из трех меньше или равны 150. Пусть х\. х-> < 150. Тогда этот дележ доминируется дележом (150,150,0).

Кстати, в этой игре есть много других НМ-решений.

Небольшой комментарий. Надо сказать, что Нейман и Моргенштерн, предложив­шие понятие НМ-решения, не упоминали о ядре (оно было введено явно лет через 15). Это выглядит поразительным. Мне представляется, что они сознательно не говорили про ядро, понимая, что часто ядро пусто. Они же хотели предложить такое решение, которое "всегда" существует. И ради этого они пошли на три жертвы. Во-первых, утаили поня­тие ядра. Во-вторых, смирились с тем, что решение - это не дележ, а система дележей (множество 2). В третьих, пришлось все еще допускать множественность решений.

Их надежды не оправдались. В 1967 г. был построен пример игры (10 лиц) без Н-М-решения. Это сильно подорвало интерес к Н-М-решениям.

Тем не менее понятие НМ-решения является фундаментальным, и должно бы всегда существовать. Мы вернемся еще к этому вопросу и покажем, что "дробный" вариант НМ-решения действительно существует всегда.

Нуклеолус. Это понятие применимо только к играм с побочными пла­тежами. Начнем с технического термина. Эксцесс коалиции Б при данном платежном векторе х есть число

Дележ х принадлежит ядру тогда и только тогда, когда все эксцессы < 0. £-ядро - когда все эксцессы < е. Около-ядро (near-core) - наименьшее непустое £-ядро. Это выпуклое множество. Если идти еще дальше (сдвигая стенки мно­гогранника, задающего ядро), мы придем к единственной точке, называемой нуклеолусом.

В отличие от вектора Шепли (о котором мы еще скажем подробнее), ну­клеолус является кусочно-линейной функцией на множестве всех игр. Гео­метрически это "центральная точка" ядра, когда оно непусто.

Переговорное множество. Переговорная точка игры v - это такая им-путация а, что для любых двух игроков / и j любое "возражение" г против j наталкивается на "контрвозражение" j против г. Здесь возражение (objection) - это коалиция S (содержащая г, но не j) и импутация /?, доступная S и луч­шая по сравнению с а для всех членов S. Контрвозражение - коалиция Т

 (содержащая у без г) и допустимая для Т импутация 7, которая (слабо) луч­ше, чем /?, для членов Б Г) Т, и (слабо же) лучше, чем а, для членов Т — Б.

Такое понятие было инспирировано наблюдением за игроками в экспери­ментальных ситуциях. По сравнению с НМ-решением, оно выражает стабиль­ность единственной импутации, а не целого множества. Существует вариант определения, где индивиды / и / заменяются коалициями.

В следующих двух лекциях мы более подробно остановимся на понятиях ядра и вектора Шепли.

Напоминания. Пусть N - множество игроков, и V = К С А") -

коалиционная игра. Напомним, что ядро С(У) состоит из таких векторов выигрышей х £ У(М)7 что хк не принадлежит внутренности У (К) ни для какой (непустой) коалиции К.

Как уже говорилось, ядро часто бывает пустым. Здесь мы займемся усло­виями, которые гарантируют непустоту ядра. И начнем с более простого слу­чая игр с побочными платежами. Это значит, что для каждой коалиции К задано число у (К) - "ценность" коалиции. Хотя это не так важно, можно считать, что у (г) = 0 для любого игрока г, что функция у монотонна и су­пераддитивна. Ядро в трансферабельном случае состоит из таких векторов х £ Шм, что

a) х(И) = г>(Л0, и

b) х(К) > у (К) для любой (непустой) коалиции К.

Здесь для коалиции К х(К) обозначает Отметим, что в данном

случае ядро задается набором линейных неравенств, и поэтому является вы­пуклым (ограниченным) множеством в пространстве К^.

Супермодулярные игры, функция у на булевой решетке 2^ (такие функции называют также функциями множеств) называется супермодуляр­ной (или выпуклой) игрой, если для любых двух коалиций К ж К' выполня­ется неравенство

у(К) + у(К') < у(К П К') + у(К и К'). (4)

Мы считаем также, что г>(0) = 0. Отметим, что супермодулярность влечет су­пераддитивность. В каком-то смысле это означает, что выгодно образовывать все большие коалиции.

Довольно легко проверить, что еубмодулярноеть эквивалентна выполнению более эко­номной системы неравенств:

+ и(5 и % и з) > «(5 и г) + и(5 и з)

(для любых >' с Л' н 1. ) (г М). Интерпретация через предельные ценности игроков (их рост).

Главный интерес выпуклых игр в том, что ядро всегда непусто.

Теорема (Шепли). Если игра у супермодулярна, то ядро С (у) непусто.

Более того, можно явно указать элемент из ядра (и даже целое семейство). Расскажем об этой конструкции более подробно.

Упорядочим как-то игроков, N = {1, 2,..., п}, и обозначим через А^ ко­алицию {1,2,...,г} первых г игроков. После этого определим дележ х по формуле

XI = у(К$ - у(К^1).

Смысл тут простой. Коалиции А^ образуются по очереди, путем присоедине­ния нового игрока, и этот игрок г получает всю дополнительную (или марги­нальную) прибыль и(1,..., г) — г>(1,..., г — 1). Очевидно, что х(Ы) = у(Х)7 и остается только проверить, что этот дележ устраивает любую коалицию К. Т.е. что выполнены неравенства х(К) > у (К). Это утверждение мы будем доказывать индукцией по числу членов К: для К = 0 оно очевидно.

Пусть г - наибольший номер участника, попавшего в коалицию К. Это значит, что А' С А/, и А' не содержится в Л',-_|. Из определения супермоду­лярности (4) мы имеем

у(К) + у{К^г) < у(К П К^г) + у(К и К^г).

При этом К и Къ-\ = А^, а К Г) К^-\ содержит меньшее число членов, и к нему применимо индуктивное предположение. Поэтому мы получаем

у(К) < и(^П^_1)+и№)-и№_1) < х^ПК^ + х^-х^г) = х(К).

На самом деле для любого упорядочивания тт множества N мы получаем свою точку хж из ядра, так что мы предъявили даже п\ точек из ядра (та­кие точки называются почему-то точками Вебера). Более принципиальным является следующее утверждение.

Предложение. Для выпуклой игры у ядро С (у) является выпуклой обо­лочкой точек хп. Более того, точки хп являются вершинами выпуклого многогранника С (у).

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

ПРИМЕРЫ выпуклых игр.

1) Игра "единогласия". Пусть = 1 и у (Б) = 0 для всех Б ^ N. Оче-

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

Найдите ее ядро.

2) Игра "заговор". Свяжем с коалицией Б такую странную игру 75:

, г,ч     Г  0,    если К С Б, 75 (-А ) = \

1—1,   в противном случае.

В этой игре появление хотя бы одного "плохого игрока" (не из Б) портит всю коалицию К (предатель, ложка дегтя). Довольно легко понять из определе­ния, что это тоже выпуклая игра. Пользуясь Предложением, покажите, что ядро этой игры равно — А(М — Б).

3) Игра "емкости". Пусть игроку г нужно (неэластично) некоторое "обще­ственное" благо в размере производство которого стоит с(у). Возникает игра г. для которой

Примеры таких ситуаций: строительство взлетной полосы, лифт, асфальти­рование дороги куда-то.

Утверждается, что если с монотонна (что естественно для издержек), то эта игра супермодулярна. Это довольно очевидно из критерия предельной ценности игрока, особенно если упорядочить игроков так, чтобы у\ < у2 < ••• < Уп- По другому это утверждение можно получить из представления такой игры как (положительной) линейной комбинации игр 75.

Стабильные системы коалиций. Интуитивно ясно, что ядро бывает пусто тогда, когда претензии "малых" коалиций велики по сравнению с воз­можностями тотальной коалиции N. В этом разделе мы рассмотрим тот слу­чай, когда некоторые коалиции вообще не могут образовываться (например, по той причине, что велики издержки их формирования, или по другим физи­ческим или юридическим причинам). В некоторых таких ситуациях непустота ядра следует уже из "супераддитивности".

Представим, например, что любая нетривиальная (неодноэлементная) коа­лиция должна содержать игрока 1 (организатор, или вето-игрок). Тогда мож­но отдать игроку 1 весь сюрплюс, то есть дать ему х\ = у(Щ —        ^О')? а

 

1,   если К I) 5, и

О   в остальных случаях.

у(К) с(тах(^, і Є К)).остальным дать х^ = у{з). Ядерность этого дележа (например, что х\ > у(1)) следует из супераддитивности: у(М) > ^2^у(г).

Теперь можно дать общее определение. Пусть задано семейство Т "допу­стимых" коалиций; мы будем считать, что {/} £ Т для любого игрока г £ N и что N £ Т. Назовем Т-игрой отображение у : Т —> К. Ядром ^"-игры называется дележ х = (а^), такой что х(М) = у(М) и х (Б) > у (Б) для любой "допустимой" коалиции Б £ Т. ^-"-игра у : Т —> К. называется суперадди­тивной, если для любого разбиения Б = Ц ■ Б у, где все Б у и Б "допустимы", выполнено неравенство у (Б) > '^2jV{Sj).

Определение. Семейство коалиций Т называется стабильным, если для любой супераддитивной ^-"-игры у ее ядро С (у) непусто.

Выше мы уже приводили простой пример стабильного семейства. Дадим два более интересных и сложных примера.

1. Пример - марьяж. Фактически это пример 2 из Лекции 20. В этой игре дележ х принадлежит ядру, если выполнены соотношения двух типов:

a) индивидуальная рациональность:     > 0 для любого / Е Д* = Д7 и II':

b) стабильность: нет такой пары (га, ги), что хт < ит{уо) и хи, < ии,(т). Короче - система браков должна быть стабильна: для любого потенци­ального брака (га, ии) либо жена га не хуже ъи, либо муж ии не хуже га.

В этом примере семейство коалиций Т состоит из всевозможных пар (г, ч), где г £ М, j £ ]¥ (а одиночек). Оказывается, что это семейство коалиций Т универсально стабильно, то есть всегда существует стабильный марьяж.

Для доказательства Гейл и Шепли предложили такую процедуру: каж­дый мужчина сватается к наилучшей (с его точки зрения) женщине; каждая женщина выбирает из женихов наилучшего для себя и временно ангажирует его. Оставшиеся мужчины повторяют сватовство (не обращаясь повторно к отвергнувшим их женщинам); женщины снова выбирают (среди новых жени­хов плюс ангажированный мужчина). И так далее. В результате получается стабильный марьяж. В самом деле, рассмотрим потенциальную пару (га, ги). Если и) более привлекательна для га, чем его жена, то по конструкции проце­дуры он уже делал предложение ии и получил отказ; это значит, что га хуже для и\ чем ее нынешний супруг.

2. Пример. Предположим, что участники расположены в вершинах некото­рого дерева Т. Тогда естественно считать, что "допустимые коалиции" долж­ны содержать всех "промежуточных" участников. Иначе говоря, семейство Т состоит из связных подграфов (поддеревьев) дерева Т. Хорошее упражнение

- проверить, что Т стабильно.

Сбалансированные игры. Условие супермодулярности игры с побочны­ми платежами достаточно для непустоты ядра, но не является необходимым. Иначе говоря, бывают невыпуклые игры с непустыми ядрами.

Оказывается, можно написать и необходимые условия непустоты ядра. На­чнем с простого случая игры трех лиц. Если вектор х = {х\/х2/х^) принад­лежит ядру, то

х; > /'(/) для і = 1, 2, 3, х\ + х2>      2), х\ + ж3 > и(1, 3), х2 + хз > у(2, 3),

и

х\ + х2 + ж3 = и(1, 2, 3).

Отсюда мы получаем, что

и(1) + и(2) + и(3)<и(1,2,3),

и(1,2) + и(3) < и(1,2,3),и(1,3) + и(2) < и(1, 2,3), и(2, 3) + и(1) < и(1,2,3),

и

и(1,2) + и(1,3) + и(2,3) < 2и(1,2,3).

Можно убедиться, что эти условия также и достаточны для непустоты ядра.

Перейдем теперь к общему случаю. Пусть дана игра т. т.е. семейство чи­сел (у(К), К С ./V). В пространстве рассмотрим многогранник Р(у) = Р, заданный неравенствами х(К) > у (К), К С N. Точки этого многогранни­ка изображают "претензии" коалиций, то есть такие распределения, которые устраивают все коалиции. Обозначим через Міп минимум линейной функции 1(х) = =     хі на Р- Очевидно, что Міп> у(Х)7 и что ядро непусто т.

и т. т., когда г (Л*) =Міп.

Основной факт выпуклого анализа (теорема двойственности) позволяет другим способом выразить этот минимум Міп. Для этого нужно всевозмож­ными способами представить функционал 1 в виде (неотрицательных) комби­наций функционалов 1% (1к(х) = х(К)). Пусть 1 = ^/ч Л/ч 1 /ч. где > 0. Так как для любого х Є Р выполнено 1к{%) _ т0 складывая эти нера-

венства, получаем 1(х) > ~^2к ^ку(К), откуда Міп> ^ку(К). Теорема двойственности утверждает, что

Міп = тахУ^ Хку{К).

Здесь удобно ввести следующие

Определения. Набор чисел Л = (\к,К С называется сбалансиро­ванным семейством, если      > 0, и      /ч      = 1 для любого г £ N.

Игра (с побочными платежами) называется сбалансированной, если для любого сбалансированного семейства Л выполняется       \ку(К) < г'(Л^).

Предыдущие рассуждения доказывают следующую теорему.

Теорема (Бондарева, 1963). Игра у имеет непустое ядро тогда и только тогда, когда она сбалансирована.

Можно также сказать, что сделав балансировку игры у (т.е. заменив на та,х(^2к \ку(К)) по всем сбалансированным Л), мы получим игру с непу­стым ядром.

Пример - сетевая игра. Вспомним игру с транспортной сетью (V, А, ф) из Лекции 20, где участники / владеют кусками (] [(. 1( = А) этой сети. Выигрыш г( /\') коали­ции К равнялся максимальному потоку по 1)^кА{. Удобно это представить так: мак­симальный поток в сети ф обозначить /Ц ■): тогда участники владеют подсетями ф{, и

<К) = }\^КФг).

Я утверждаю, что эта игра сбалансирована. Действительно, пусть А = (А/ч-) - сба­лансированный набор коэффициентов (т.е. 1дг = ^2 Хк^к)- Нам нужно показать, что < V А/ч г(7\'). Обозначим через фк максимальный поток через сеть фк = ^^кф^ Нам нужно проверить, что поток V \кфк допустим сетью ф = ф1 = ^ \кФк- Но это тривиально следует из сложения неравенств ф%<ф%.

Получаем, что ядро сетевой игры непусто.

На самом деле, предыдущее рассуждение показывает сбалансированность любой игры производства, производственная функция которой / вогнута и однородна.

Можно более явно предложить элементы из ядра. Разрезом в сети называется набор В стрелок (дуг) орграфа, такой что любой простой орпуть из истока 5 в сток I содержит одну из стрелок /). Сумма ф(а), а е В, пропускных способностей дуг разреза П называ­ется пропускной способностью разреза В (обозначим ее ф(В)). Очевидно, что величина потока в сети ф не превышает (.'(!)) для любого разреза. А замечательная теорема Фор.чн-Фалкерсона утверждает, что найдется (для данной сети ф) разрез В (т.н. минимальный разрез), что /(ф) = Ф(В)- Так вот, надо взять произвольный минимальный разрез В для сети ф = Х^г^ь и в качестве ядерного распределения дать участнику / ./■(/} = I.',(/)). Очевидно, что

1) х(М) = Х^'МД) = Ф(В)=(теорема Форда-Фалкерсона)=/(^) = у(М), и

2) у (К) (т.е. максимальный поток через сеть фк) не превышает фх(В) = х(К). Замечание. И то, и другое показывают, что ядерное распределение нужно понимать

как касательную (точнее, супердифференциал) к функции г в точке N.

Ядра игр без побочных платежей. После того, как мы разобрали слу­чай игр с трансферабельными полезностями, можно переходить к коалицион­ным играм без побочных платежей. Напомним, что они задаются семействоммножеств {V (К), К С ./V), У (К) С К . Мы видели, что (в трансферабельном случае) важную роль играет условие сбалансированности. Скарф перенес это понятие на общие игры и показал, что оно также влечет непустоту ядра.

Я приведу ниже некоторое общее утверждение, следствием которого будет теорема Скарфа. В его основе лежит идея, что результатом коалиционного взаимодействия должна быть пара (ж, А), где х = (а^, ? £ Ж) изображает дележ (распределение выигрыша), а А = (Х(К), К С ./V) отражает фор­мирование коалиций (Х(К) - это уровень, интенсивность функционирования коалиции К). Конечно, эта пара не произвольная. Прежде всего, должно вы­полняться условие сбалансированности,

I. Набор А сбалансирован.

То есть каждый игрок должен быть полностью занят действующими коали­циями. Это своеобразный баланс по труду.

Во вторых, вектор выигрышей х должен быть достижим усилиями сфор­мировавшихся коалиций. Под этим я понимаю, что если Х(К) > О для неко­торой коалиции К7 то хк £ У (К). (То есть если коалиция К функционирует, она должна обеспечивать своих членов предписанными полезностями.) Обо­значая через У(Х) множество векторов у7 таких что ук £ Для любой коалиции К с Х(К) > О, мы запишем второе условие как

II. х £ У(Х).

Наконец, если дележ х может быть улучшен некоторой коалицией К (т.е. хк £ 1пЬ(У(К))), сложившаяся структура коалиций А будет разрушена. Что­бы этого не происходило, введем требование недоминируемости

III. Для любой коалиции К точка хк не принадлежит внутренности У (К).

Набор (ж, А), удовлетворяющий 1-Ш, назовем В-ядерным (или равновес­ным) .

Теорема. Для любой игры существуют В-ядерные исходы.

Скарф называет игру У сбалансированной, если У(Х) С У{№) для лю­бого сбалансированного набора А. И очевидным следствием нашей теоремы является следующая теорема Скарфа.

Следствие (Скарф, 1967). Если игра У сбалансирована, то ее ядро непу­сто.

В качестве следствия мы снова получаем, что ядро в выпуклой модели экономики чистого обмена непусто. В самом деле, легко проверить, что соот­ветствующая игра является сбалансированной.

Доказательство теоремы. Будем смотреть на коалиционную игру с экономической точки зрения, понимая коалиции как некий фирмы, которые для своей работы приглаша­ют участников этой коалиции. Роль цен (или лучше - зарплат) будет выполнять вектор х. В зависимости от величины х (а точнее, хк) коалиция К либо бездействует (если не может платить такую зарплату), либо проявляет разумную активность, либо развивает бешеную активность (если может предложить всем участникам больше). В конечном итоге фирмы предъявляют спрос на участников. Если спрос на некоторого участника г превышает 1 (т.е. предложение), то Xi увеличивается, если нет, уменьшается. Неподвижная точка дает ядерный исход.

Более точно, мы обозначим через Л = {Л = (Х(К)),0 < Х(К) < 2 УК}. X - шар большого радиуса вокруг 0 в пространстве Шм, Мы определим сейчас (многозначное) ото­бражение F множества Л х X в себя, т.е. по паре (х, X) определим новую пару (х',Х').

Определение х'. Это Argmax на X линейной функции \(К)1к — Ijv- Это точка на границе шара X кроме того случая, когда Л сбалансировано.

Определение Л'. Для коалиции К положим

О, если хк не принадлежит V(K),

любое число между 0 и 2, если хк лежит на границе V(K), 2, если хк попадает строго внутрь V(K).

Ясно, что построенное отображение (соответствие) F замкнуто и имеет непустые вы­пуклые образы. Поэтому по теореме Какутани существует неподвижная точка (х*,Х*). Я утверждаю, что она /7-ячерная.

Действительно, если х* лежит на границе шара X. то некоторая координата х* "боль­шая". Но тогда никакая коалиция К, содержащая /. не может обеспечить участнику / такой большой выигрыш, и значит Х(К) = 0, спрос на этого участника г равен 0, и х* должен упасть. Аналогично если х* "сильно отрицательно", тогда х* 6 Inl I (/ ). значит А (г) = 2. "Спрос" на этого участника велик, и его зарплата х* > 0, что, конечно, противоречит исходному предположению "сильной отрицательности".

Таким образом, х* лежит внутри X. откуда Л сбалансировано. Если Х(К) > 0, то из определения Л' видно, что Хк G V(K), т.е. выполняется П. Наконец, в силу той же сбалансированности Х(К) < 1, т.е. хк не попадает строго внутрь V(K) ни для какой К, т.е. ПШ

Применение к НМ-решению. Пусть X - некоторое множество, и D - бинарное асимметричное отношение на X ("доминирование"). (Фактически это структура орграфа на X.) (Абстрактным) НМ-решением в этой ситуации естественно считать подмножество Z С X. которое удовлетворяет двум требованием:

1) внутренняя независимость: /) ■/ пусто (то есть элементы внутри Z несравнимы меж­ду собой);

2) совокупное доминирование: для любого х    Z существует z 6 Z, такой что zDx.

(В теории графов это называется kernel.) Чуть удобнее вместо D рассмотреть рефлексив­ное отношение D* = DU "диагональ". В этих терминах требования 1) и 2) переписываются как

1') D*\z - тождественное отношение на Z; и 2') для любого .г (г .V существует z G Z, ';!)'х.

Ясно, что НМ-решение существует не всегда. Достаточно взять цикл из трех элементов. Поэтому естественно обратиться к релаксации этого понятия, то есть к понятию дробного НМ-решения (ДНМР). Для его формулировки назовем цепью (для (X, Р*)) подмножество С С X. такое что индуцированное отношение Р*\С является полным порядком на С.

Определение. Дробным НМ-решением называется (неотрицательная) мера [л на X, которая обладает двумя свойствами: 1") для любой цепи С ц(С) < 1;

2") для любого .г (г .V существует цепь С с //(С) > 1, такая что сР*х для любого с (г С.

Например в цикле из трех элементов ДНМР является мера, при которой вес каждого из трех элементов равен 1/2.

Теорема. Если множество X конечно, то существует ДНМР.

Доказательство. Назовем "игроком" в нашей ситуации любую цепь С. Элементы .г (г V будем понимать как "коалиции" тех игроков-цепей С, которые содержат х. Такая коалиция х дает игроку С полезность, равную "высоте" х в цепи С (так что минимальный элемент имеет высоту 0, и т.д.). Кроме того, каждый игрок может "индивидуально", то есть не вступая ни в какие коалиции, получить полезность — 1.

Применяя полученную выше теорему о равновесных исходах, мы получаем существо­вание пары (и, Л), где и - некоторый вектор выигрышей наших игроков-цепей С, а Л : X —У К+ - вектор интенсивностей коалиций, причем эта пара обладает соответствую­щими свойствами 1-111, Сбалансированность (условие I) дает свойство 1"). Свойство II интерпретируется так: если .г (г С п Х(х) > О, то и(С) < "высоты" х в цепи С. Предста­вим теперь, что для любой цепи С, доминирующей х, А (С) < 1. Это значит, что уже для любой цепи С, содержащей х, полезность и(С) строго меньше, чем "высота" х в С. Но это противоречит свойству III, потому что тогда вектор выигрышей для игроков из "коалиции" х строго внутренний. □