Сюжет «Права на сумку»

Актуальность и жизненность проблем, при решении которых могут эффективно применяться методы теории кооперативных игр, не вызывают особых сомнений. В литературном приложении это подчеркивается па примере сквозного сюжета о «справедливом определении нрав на сумку». Один из соавторов изначально считал, что сумка за 10 тыс. руб. с полным основанием может быть отнесена к разряду очень дорогих. Другой соавтор решительно утверждала, что десять тысяч для приличной сумки — это просто ничто. Ну, в самом крайнем случае, тысяч тридцать. В конце концов сошлись на двадцати, и то исключительно по причинам удобства изложения приводимых далее расчетных примеров. Присвоим конструируемой кооперативной игре условное наименование «Права на сумку» (для нее в дальнейшем будет сформулировано несколько альтернативных версий).

Итак, в общей сумме, равной 20 тыс. руб., доли подруг составили:

• • Маргарита — 9 тыс. руб.;
• • Алиса — 7 тыс. руб.;
• • Дарина — 4 тыс. руб.

Перед применением теории кооперативных игр полезно задуматься о путях решения проблемы справедливого распределения «прав на сумочку», подсказываемых нашим повседневным опытом.

Разумеется, первое, что он подсказывает, — это поделить пропорционально вложенным суммам. Одновременно с данной подсказкой появятся и возражения, что без минимальной доли Дарины никакой сумки вообще не было бы, а значит, и делить было бы нечего. На них, в свою очередь, найдутся контрдоводы, что Маргарита с Алисой могли бы как-нибудь «поднапрячься» и обойтись без Дарининых четырех тысяч. Это даст возможность читателям, симпатизирующим Дарине, возразить, что «поднапрячься» могли бы и Маргарита с Дариной без Алисы. Конечно, «поднапрягаться» пришлось бы уже на целых семь тысяч. Однако для Маргариты, с учетом того, что Дарина реально будет пользоваться сумочкой реже, чем Алиса, такой союз может оказаться более интересным. А как насчет союза Алисы с Дариной? Ну, это уже нереально, от одиннадцати тысяч до двадцати — это уж слишком далеко.

Попытаемся перевести эти более чем небесспорные рассуждения на язык теории кооперативных игр с трансферабельной полезностью. Первое, с чем необходимо определиться, — это то, что, собственно говоря, будет значениями характеристической функции. Если воспользоваться научной лексикой вымышленного гуру упроперсологии Мустафы Монда, что будем делить: пустыню, воду или верблюда? В рамках демонстрационного примера мы можем ограничиться допущением, что множеством значений характеристической функции служит интервал [0; 1], где 1 — полное владение сумкой, 0 — отсутствие прав на сумку. Значения между 0 и 1 — различные степени владения. Возможные версии и варианты конкретных содержательных интерпретаций для термина «степень владения» оставим на усмотрение читателя.

Коалиции, состоящие из одного участника, точно не получают никакой сумки:

Коалиция из Маргариты (игрок 1) и Алисы (игрок 2) «почти» получает сумку. Это «почти» как раз и может быть оценено отношением их суммарных затрат к стоимости сумки:

Коалиция из Маргариты (игрок 1) и Дарины (игрок 3)… тут, конечно, могут быть возражения, но, если уж очень сильно расстараются, то тоже могут получить сумку. Оценим степень владения для этой коалиции (с учетом необходимости «очень расстараться»), как.

Коалиция из Алисы (игрок 2) и Дарины (игрок 3)… тут уж как ни старайся — остается без сумки:

Полная (большая) коалиция получает сумку в полное владение:

Обратим внимание, что нами только что была решена крайне важная задача, а именно задача построения характеристической функции игры. Строго говоря, для теории кооперативных игр как для математической дисциплины проблематика построения характеристических функций является внешней. Собственно теоретико-игровые исследования начинаются с момента, когда определена некоторая игра (I, u), т. е. характеристическая функция u (S) («S I I) уже задана. Однако успешность практического применения игровых моделей и методов всецело зависит от ее адекватности. Подчеркнем, что конструирование характеристических функций — это неформальный процесс, основанный на понимании специфики изучаемой предметной области.

Игра, в которой u (I) = 1, u ({i}) = 0 ( I I), u (S) I [0,1], называется мажоритарной.

Найдем решение Шепли для построенной игры. В соответствии с выражением (14.3) имеем:

• доля (степень владения сумкой) Маргариты:

• доля (степень владения сумкой) Алисы:

• доля (степень владения сумкой) Дарины:

Следовательно, в соответствии с вектором Шепли степени (доли) владения сумкой между Маргаритой, Алисой и Дариной должны распределиться как (0,575; 0,25; 0,175).

Как нетрудно догадаться, зримое преимущество Маргариты проистекает из допущения, что «союз» с ней как для Алисы, так и для Дарины дает возможность приобретения сумки. При необходимости мы можем оценить «вклад допущения о продуктивности объединения Маргариты и Дарины», построив альтернативный вариант игры, в котором u ({1; 3}) = 0, и вычислив для него вектор Шепли. Если предположить, что ни одна из парных коалиций «не берет» сумку, то мы придем к тривиальному решению о равном распределении прав между всеми игроками.

* * *.

Говорят, что дележ х доминирует дележ у по коалиции S, если

• (14.4)
• (14.5) Условие (14.4) означает, что дележ х выгоднее, чем дележ у, для всех участников коалиции S, а из условия (14.5) вытекает, что коалиция S может действительно его обеспечить за счет своего выигрыша u (S).

Говорят, что дележ х доминирует дележ у, если найдется по меньшей мере одна коалиция, по которой это происходит.

Множество недоминируемых дележей в игре (I, u) называют С-ядром и обозначают как C (u).

Несложно показать, что.

Понятие С-ядра было введено канадским математиком Дональдом Джиллисом (Donald Bruce Gillies) в 1953 г.^[1]. В содержательном плане С-ядро представляет множество дележей, которые не могут быть объективно оспорены ни одной из коалиций. С данным решением связаны две принципиальные проблемы:

• • в определенных ситуациях С-ядро может быть «очень большим», что порождает неоднозначность выбора «предпочтительного» дележа из него;
• • также возможны ситуации, в которых С-ядро будет пустым.

Говоря о соотношении между вектором Шепли и С-ядром, следует отметить:

в случае выпуклости игры вектор Шепли всегда принадлежит С-ядру, однако в случае супераддитивности (но не выпуклости) он может не принадлежать С-ядру даже в случае его непустоты.

* * *.

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

(14.6).

Рис. 14.1. «Права на сумку», геометрическая характеризация С-ядра Ему соответствует плоскость в трехмерном пространстве (рис. 14.1), пересекающая координатные оси в точках (1; 0; 0), (0; 1; 0), (0; 0; 1).

Условия индивидуальной рациональности игроков в данной игре имеют вид.

(14.7).

Действительно, каждый игрок по отдельности «зарабатывает» нуль, из чего следует, что дележи не должны давать ему меньше нуля. Неравенства (14.7) «вырезают» из плоскости (14.6) треугольник. Таким образом, множество дележей в игре представляет собой 2-симплекс^[2] с вершинами (1; 0; 0), (0; 1; 0), (0; 0; 1).

Добавим, что множество точек, лежащих на плоскости.

(14.6), являются пред-дележами в данной игре.

Для получения С-ядра необходимо учесть ограничения на возможности коалиций. В рассматриваемой игре их два:

(14.8).

• — дележ, принадлежащий С-ядру, не должен давать коалиции из первого и второго игроков (Маргариты и Алисы) меньше, чем 0,8 (в противном случае им разумнее не вступать в «большую» коалицию, а действовать в рамках объединения S = {1; 2});
• (14.9)
• — дележ, принадлежащий С-ядру, не должен давать коалиции S = {1; 3} меньше, чем 0,65 (по аналогичным соображениям).

Поскольку коалиция S= {2; 3} «не получает сумки», то выполнение накладываемого ею ограничения (х{2; 3} = х₂ + х₂ ³ 0) автоматически следует из выполнения условий индивидуальной рациональности.

Множество дележей, удовлетворяющих условию (14.9), лежит «выше» плоскости + = 0,65, а множество дележей, удовлетворяющих условию (14.8), — в полупространстве, порожденном плоскостью + х₂ = 0,8, не содержащем начала координат. Результат их пересечения с плоскостью (14.6) дает параллелограмм, выделенный серым цветом. Он и является геометрическим местом точек, принадлежащих С-ядру игры.

Как можно заметить, исследуемая игровая модель относится к тем ситуациям, в которых С-ядро «достаточно велико». Его экстремальные точки соответствуют весьма спорным решениям:

• • (1; 0; 0) — все получает Маргарита;
• • (0,8; 0, 0;2) — сумку делят между собой Маргарита и Дарина, исключая Алису;
• • (0,45; 0,35; 0,2) — Алиса и Дарина предельно уменьшают долю Маргариты;
• • (0,65; 0,35; 0) — сумку делят между собой Маргарита и Алиса, исключая Дарину.

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

* * *.

К настоящему времени в теории кооперативных игр с трансферабельной полезностью существует немало различных концептуальных подходов к определению их решения. Среди наиболее известных могут быть названы решение по Нейману — Моргенштерну, переговорное множество, K-ядро, N-ядро.

Многие из концепций решений кооперативных игр основаны на понятии эксцесса.

Эксцессом коалиции S по дележу х называют величину.

Положительный эксцесс (e (S, х) > 0) является показателем меры недовольства коалиции дележом х, так как он дает ей меньше, чем она может получить самостоятельно (u (S) >х (S)).

Отрицательиый эксцесс, наоборот, отражает степень удовлетворенности (дополнительного выигрыша) коалиции от дележа, так как в соответствии с его предписаниями ее участники получают больше своих индивидуальных возможностей вне большой коалиции (u (S) < х (S)). Заметим, что для определения эксцесса, вообще говоря, не обязательно, чтобы вектор х обладал всеми свойствами дележа. Аналогичным образом данное определение может быть распространено и на преддележи.

LС-ядром (наименьшим С-ядром) называется такое множество пред-дележей, на котором достигается минимальное значение для максимального среди эксцессов, вычисленных по всем коалициям данной игры (S ¹ ?, I):

С содержательной точки зрения LC-ядро — это такое множество решений, на котором наиболее недовольная коалиция чувствует себя наименее обиженной. Предложенное определение LС-ядра никак не связано с фактом пустоты С-ядра. В случае если С-ядро не пусто, LC-ядро представляет собой некоторое подмножество, расположенное в нем. В противном случае LC-ядро — подмножество, «центрально» расположенное относительно системы гиперплоскостей несовместных ограничений (x (S) ³ u (S), S¹?, I).

LС-ядро (так же как и С-ядро) может быть неодноточечным. От данного недостатка свободно другое решение кооперативной игры, получившее название N-ядра. Впервые данный термин был предложен израильским математиком и экономистом Давидом Шмайдлером (David Schmeidler) [42]. Мы ограничимся исключительно содержательным представлением основной идеи, лежащей в основе концепции N-ядра. С более строгим с математической точки зрения изложением данных вопросов читатель может ознакомиться, например, в работах [13, 14].

Проблема неодноэлементности (многозначности) LC-ядра по существу определяется тем, что достижение минимума максимального эксцесса обнаруживается на некоторой конкретной коалиции S' по результатам сравнения значений u (S') и x (S'). В том случае, когда S' объединяет несколько игроков, может найтись много дележей, по-разному распределяющих выигрыши (полезность) между ними, по в сумме обеспечивающих x (S'). Для того чтобы уйти от данной неоднозначности, используется специальное правило сравнения дележей. Поясним его на конкретном примере. Рассмотрим два возможных дележа для игры «Права на сумку» :

В табл. 14.1 содержатся значения эксцессов, но данным дележам, рассчитанных по всем возможным коалициям за исключением ?, I.

Таблица 14.1

Значения эксцессов для дележей х¹ и х² по возможным коалициям.

Полученные значения эксцессов упорядочиваются по убыванию (табл. 14.2). В результате на первом месте оказывается дележ самой недовольной коалиции и т. д. по мере уменьшения недовольства.

Таблица 14.2

Значения эксцессов для дележей х¹ и х², упорядоченные по убыванию.

Далее производится лексикографическое сравнение рядов, упорядоченных по убыванию эксцессов: находится первый столбец с неравными значениями. По этим значениям определяется, какой из наборов (векторов) является большим, а какой — меньшим. В отличие от «стандартного» покомпонентного сравнения векторов остальные элементы в сравнении не участвуют.

Соответственно, лексикографически меньший ряд упорядоченных эксцессов определяет «лучший» из сопоставляемых дележей, по которым рассчитывались данные эксцессы. В нашем случае «победителем» явился дележ x¹, так как -0,35 < -0,2.

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

Вообще говоря, понятие N-ядра (от англ. nucleolus — ядрышко) может быть введено для произвольного множества, а не только для множества дележей. На принципиальном уровне его можно представить как некоторую «центральную» точку множества, получаемую в результате взаимного встречного движения его границ. Фундаментальным свойством N-ядра является то, что для компактного выпуклого множества (т.е., в частности, для множества дележей в кооперативной игре) оно всегда существует и состоит из одной точки.

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

На рис. 14.2 множество дележей игры «Права на сумку» показано на двумерной проекции плоскости х₁ + х₂ + х₃ = 1 на плоскость листа (соответствующее трехмерное изображение мы могли видеть на рис. 14.1). Рядом с «существенными» точками множества дележей указаны их координаты в трехмерном пространстве.

14.2. Сюжет «Права на сумку», геометрическая характеризация С-ядра, LC-ядра, N-ядра Представим процедуру, состоящую в последовательном параллельном сближении граней, образующих С-ядро, навстречу друг другу. В том случае, если какие-то грани «встречаются», их движение останавливается. Процесс продолжается до тех пор, пока не сойдется в одну точку. Данная точка и будет N-ядром.

В рассматриваемой нами игре (см. рис. 14.2) первыми «встретились» верхняя и нижняя граница С-ядра, образовав отрезок дележей между точками х¹ = (0,65; 0,25; 0,1) и х² = (0,8; 0,1; 0,1). Данный отрезок является LС-ядром игры, т. е. на всех его точках достигается минимальное значение наибольшего из эксцессов по всем возможным коалициям (-0,1) (см. табл. 14.2). Однако дележи, принадлежащие данному отрезку, «намертво» зафиксировав долю третьего игрока (Дарины) как 0,1, являются неравнозначными для первого и второго игроков (Маргариты и Алисы). В результате встречного движения левой и правой границ LС-ядра достигается средняя точка между х¹ и х², которая является N-ядром игры:

Заметим, что в случае пустоты С-ядра процесс нахождения N-ядра можно представить как взаимное встречное движение системы гиперплоскостей ограничений (x (S) ³ u (S), S ¹ ?, I).

Достаточно интересный и оригинальный пример, связанный с кооперативными играми, был предложен Р. Ауманном (Robert J. Aumann) и М. Машлером (Michael Bahir Maschler) [ 16]. В нем дастся теоретико-игровая интерпретация указаний Талмуда^[3] о правилах раздела наследства умершего мужа между тремя вдовами, предъявившими претензии в размере 100, 200 и 300 ед. соответственно. Согласно указанием Талмуда:

• • если имущество составило A = 100 ед., то его нужно поделить между претендентками поровну, т. е. 100/3 каждой;
• • если имущество составило A = 200 ед., предлагается дележ (50, 75, 75);
• • если имущество составило A = 300 ед., предлагается дележ (50, 100, 150).

Описанная ситуация с экономической точки зрения является одним из примеров задач о банкротстве: объем делимого имущества меньше, чем объем требований.

В работе [16] было показано, что при определении кооперативных игр с характеристическими функциями, устанавливающими выигрыши для каждой коалиции S в размере.

(14.10).

где, А — сумма имущества; R (IS) — сумма требовании всех игроков, не входящих в коалицию S, сформулированные выше рекомендации образуют N-ядра данных игр.

• [1] Исходное англоязычное наименование для С-ядра — «Core». Появление данного понятия датируется 1953 г. Однако в научной литературе традиционно в качестве источника указывается работа Д. Джиллиса 1959 г. [25]
• [2] Напомним, что определение для понятия «k-симплекс» давалось в гл. 2
• [3] Многотомный свод правовых и религиозно-этических положений иудаизма