Зинченко А.Б.

Техника вывода достаточных условий существования С-ядра классической кооперативной игры

Южный федеральный университет. Россия

Техника вывода достаточных условий существования

С-ядра классической кооперативной игры

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

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

Если выгодно объединение всех игроков, то наиболее популярной концепцией решения является -ядро (core) , где  - множество эффективных распределений  (predimputation set),  - множество собственных коалиций. При любом дележе из -ядра суммарный выигрыш каждой коалиции  не меньше ее собственной возможности . Игра, имеющая непустое -ядро, называется сбалансированной. Необходимое и достаточное условие сбалансированности игры [1]-[2] имеет вид

, , (1)

Таблица 1.

Условие существования -ядра игры четырех лиц

Имеются более простые, чем (1), но уже только достаточные условия существования -ядра, наиболее известным из которых является условие выпуклости

, . (2)

Описан метод вывода достаточных условий [3]. В данной заметке предлагается более простой способ, приводятся примеры его реализации.

Рассмотрим систему

,, , (3)

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

(4)

заменено неравенством . Если система (3) неразрешима, то игра не имеет -ядра. Пусть  - решение системы (3) . Если  удовлетворяет (4), то . В противном случае -ядру принадлежит дележ

(5)

являющийся проекцией  на гиперплоскость  .

Запишем (3) в виде

, (6)

где , , ,  для, . Первыми  строками матрицы  являются характеристические векторы  коалиций

(7)

Последняя строка  матрицы  соответствует максимальной коалиции . Очевидно .

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

. (8)

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

В примерах 1 и 2 (ниже) получен явный вид условия (8) для игры  лиц и двух базисов, один из которых не содержит строку , а другой – содержит.

Пример 1. Рассмотрим в начале самый простой базис , состоящий из характеристических векторов всех одноэлементных коалиций. Из (7) следует, что  и  - единичные матрицы порядка , . Условие (8) принимает вид

,, ,

и определяет множество сбалансированных игр, содержащее аддитивные игры.

Пример 2. Возьмем базис , полученный из базиса примера 1 заменой строки  на . Тогда

Вектор , где

принадлежит -ядру и совпадает с одной из крайних точек множества дележей (imputation set)  игры . При дележе  выигрыш каждого агента  минимален (он получает то, что может иметь без кооперации с остальными игроками). Выигрыш -го агента равен остатку кооперативной прибыли (surplus). Если  является игрой большого босса (big boss game) [4] с игроком  в качестве босса, то определенный (9) дележ является "точкой босса". Условие (8) принимает вид

, ,  .

и выделяет подмножество сбалансированных игр, -ядро которых содержит крайнюю точку  симплекса . Аналогично определяется подмножество игр, содержащих любой другой элемент из .

В следующем примере рассматриваются игры с фиксированным количеством участников . Описан класс игр, -ядро которых содержит одну из крайних точек , ,

(9)

множества двойственных дележей (dual imputation set) , где  - вклад игрока  в максимальную коалицию. Дана содержательная интерпретация неравенств системы (8).

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

, ,

.

Видно, что  совпадает с крайней точкой  (см. формулу (9)) множества . Подставив ,  и  в (8), имеем

.

Условие (8), соответствующее выбранному базису, состоит из 11 (вместо 41, составляющих систему (1)) неравенств, приведенных во втором столбце таблицы 2.

Таблица 2.

Достаточное условие существования -ядра игры четырех лиц

Первые 7 неравенств содержатся в системе (1). Они принадлежат классам , ,  (см. таблицу 1). Остальные 4 неравенства известны как "условие союза" и используются при определении игр большого босса. Преобразованные неравенства (третий столбец таблицы 2) допускают следующую интерпретацию. Значение  каждой коалиции , не содержащей четвертого игрока, должно быть не больше суммы вкладов ее участников в максимальную коалицию. Неравенства 8-11 означают, что вклад  каждой такой коалиции  () в , наоборот, должен быть не меньше суммы вкладов , . Умноженные на (-1) неравенства 9-11 содержатся в (2). Следовательно, для выбранного базиса, система (8) содержит часть неравенств из условия вогнутости игры. Неравенства 1-3 являются частью условия супераддитивности

+£,  ,  .

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

Литература:

1. Shapley L. S. On balanced sets and cores // Naval Research Logistics Quarterly. 1967. V. 14. P. 453-460.

2. Бондарева О.Н. Некоторые применения методов линейного программирования к теории кооперативных игр // Проблемы кибернетики. 1963. Вып. 10. М.: Физматгиз. С. 119-140.

3. Зинченко А.Б., Головань С.В. Достаточное условие существования с-ядра кооперативной игры // Известия высших учебных заведений. Северо-Кавказский регион. Естественные науки. 2001. №1. С. 8-11.

4. Muto S., Nakayama M., Potters J., Tijs S. On big boss games // The Economic Studies Quarterly. 1988. № 39. P. 303-321.