ссс

Математика/4. Прикладная математика

К.ф.-м.н. Зинченко А.Б., Глыбин Г.Ю., Аль Джабери Х.С.

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

Двухэтапные решения кооперативной CS-игры

Кооперативная игра с коалиционной структурой (-игра) состоит из классической игры , где , , , , и коалиционной структуры

, , , , , .

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

Коалиционный оператор значения (-оператор) ставит в соответствие каждой игре вектор выигрышей агентов (-значение).

Понятие -игры было введено в [1]. Решение , предложенное Ауманном и Дрезом, обобщает значение Шепли . Оно компонентно-эффективно

, .

-игра распадается игр

, , , (1)

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

Эффективное -значение реализует другой сценарий: разыгрывается внешняя игра

, , , , (2)

дележа между компонентами структуры и внутренние игры между партнерами каждого союза . Первое эффективное -значение , предложенное Оуэном [2], использует во внешней и внутренних играх значение Шепли. При вычислении внутренние (редуцированные) игры имеют более сложный вид, чем (1). Вес каждой коалиции равен ее выигрышу во вспомогательной игре между компонентами структуры , полученной из удалением игроков принадлежащих ,

, ,

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

После были введены и аксиоматизированы алогичные -значения, сочетающие с взвешенным значением Шепли, значением Банзафа [3], консенсус-значением [4-6]. Эффективные -значения подходят для игр , удовлетворяющих условию

, (3)

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

Большинство -значений удовлетворяет аксиоме нулевого игрока: агент , присоединение которого к любой коалиции , не увеличивает прибыль партнеров, получает нулевой выигрыш. Этот "жесткий" принцип не всегда сочетается с моделируемой ситуацией [7].

Данная статья посвящена сравнению двух CS-значений, не удовлетворяющих аксиоме нулевого игрока: двухэтапного значения Шепли [8] и двухэтапного консенсус-значения [9]. Оба решения были предложены недавно и еще недостаточно исследованы. Формулируются необходимые и достаточные условия, при которых нулевой агент получает положительный выигрыш. Доказывается, что двухэтапное значение Шепли может не принадлежать не только непустому С-ядру, но и множеству дележей. Вводится новая аксиома для двухэтапного консенсус-значения.

Двухэтапное значение Шепли определяется формулой

, . (4)

Внешняя игра для такая же, как и для значения Оуэна. Внутренние игры аналогичны играм (1), использующимся при вычислении значения Ауманна-Дреза. Двухэтапное значение Шепли однозначно определяется тремя стандартными для -значения аксиомами эффективности EF, аддитивности AD, внешней (коалиционной) симметричности CSy и двумя дополнительными аксиомами, сформулированными в [8].

(IE) Внутреннее равенство. Если агенты симметричны в игре , то .

(CNP) Свойство коалиционного нулевого игрока. Если нулевой агент в , а союз - нейтральный игрок в , то .

Двухэтапное консенсус-значение определяется формулой

, , (5)

где

, , (6)

и отличается от двухэтапного значения Шепли тем, что в (4) значение Шепли заменено консенсус-значением [10]. Двухэтапное консенсус-значение является единственным -значением, удовлетворяющий аксиомам аддитивности, внешней симметричности, внутренней симметричности и следующим двум аксиомам.

(F) Допустимость. .

(MCNP) Модифицированное свойство коалиционного нулевого игрока. Если нулевой агент в , а союз - нейтральный игрок в , то

Известно, что значение Шепли может не принадлежать не только непустому -ядру , но и непустому множеству дележей . Покажем, что это свойство сохраняется и для , а реже, чем , не принадлежит .

Теорема 1. Пусть игра 0-нормализованна, удовлетворяет (3) и для всех . Если и , то , но обратное не верно.

Доказательство. Выразим вначале через . Возьмем . Из 0-нормализованности игры и формул (5)-(6) следует

, .

Получаем

. (7)

Для 0-нормализованной игры, . По предположению . Значит, для всех . Из последнего неравенства, (3), (7) и , , имеем , . По аксиоме эффективности . Получили, что . Рассмотрим теперь игру , где

(8)

Из следует . Данная игра удовлетворяет всем предположениям теоремы. Двухэтапное значение Шепли не принадлежит множеству дележей. Подставив в (7), получаем . ÿ

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

Теорема 2. Пусть игра имеет 0-форму. Если нулевой агент в , то

- тогда и только тогда, когда ;

- тогда и только тогда, когда .

Доказательство. Нулевой с исходной игре агент будет также нулевым в игре внутри союза . Согласно аксиоме нулевого игрока и определению игры , Шепли-выигрыш агента равен нулю. Значит, , т.е. справедливо первое утверждение теоремы. Подставив выражение для в (7), поучаем

т.е. справедливо второе утверждение. ÿ

В [11] предложена новая аксиоматизация двухэтапного значения Шепли, использующая EF, AD, CSy и следующие три аксиомы.

(NC) Свойство нулевой коалиции. Если - нулевой игрок в , то .

(Coh) Согласованность. , где и - тривиальные коалиционные структуры.

(PS) Солидарность внутри союза. Для любых и , ,

где .

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

(MNC) Модифицированное свойство нулевой коалиции. Если , то .

Теорема 3. Двухэтапное консенсус-значение удовлетворяет аксиомам Coh, PS и MNC, но не удовлетворяет аксиоме NC .

Доказательство. Для , внешняя игра состоит из одного игрока , поэтому , а внутренняя игра совпадает с . Значит, , . Из формулы (5) получаем . Если , то внешняя игра совпадает с , поэтому , . Все внутренние игры , , состоят из одного агента. Значит, , . Окончательно, , т.е. справедлива аксиома Coh. Пусть и , , тогда по формуле (5)

где , если , в противном случае. Очевидно, последнее выражение равно , т.е. удовлетворяет аксиоме PS. Из (5) следует

, .

Консенсус-значение удовлетворяет аксиоме эффективности, поэтому

Если , то и . Значит,

т.е. удовлетворяет аксиоме MNC. Рассмотрим теперь игру :

, , , для остальных .

Четвертый агент – нулевой в , а также является одноэлементной компонентой данной структуры. - нулевой, а также нейтральный игрок во внешней игре . По аксиоме MNC, , т.е. не удовлетворяет аксиоме NC. ÿ

Литература:

1. Aumann R.J., Dreze J.H. Cooperative Games with Coalition Structure // International Journal of Game Theory. 1974. N. 3. P. 217-237.

2. Owen G. Values of games with a priory unions. Essays in mathematical economics and game theory. Berlin, 1977, pp. 76-88.

3. Gomez-Rua M., Vidal-Puga J. The axiomatic approach to three values in games with coalition structure // MPRA paper. 2008. N. 8904. P. 1-30.

4. Зинченко А.Б., Мироненко Г.В., Провоторова П.А. Консенсус-значение для игр с коалиционной структурой // Математическая теория игр и ее приложения. Том 2. Выпуск 1. 2010. С. 93-106.

5. Zinchenko A.B., Provotorova P.A., Mironenko G.V. Efficient CS-values based on consensus and Shapley values // Contributions to Game Theory and Management. Vol. 4. 2011. P. 502-513.

6. Зинченко А.Б. Аксиоматическое обоснование новых операторов значения для игр с коалиционной структурой // Известия вузов. Сев.-Кавказ. регион. Естественные науки. 2011. № 1. С. 5-8.

7. Van den Brink R. Null or nullifying players: the difference between the Shapley value and equal division solutions // Journal of Economic Theory. 2007. Vol. 136. P. 767-775.

8. Kamijo Y. A two-step Shapley value for cooperative games with coalition structures // International Game Theory Review. 2009. Vol. 11. P. 207-214.

9. Зинченко А.Б. Двухэтапный CS-оператор, использующий консенсус-значение // Известия вузов. Сев.-Кавказ. регион. Естественные науки. 2013. № 4. С.10-13.

10. Ju Y., Born P., Rays P. The consensus value: a new solution concept for cooperative games // Social Choice and Welfare. 2006. Vol. 28. N. 4. P. 85-703.

11. Calvo E., Gutierrez M.E. Solidarity in games with a coalition structure // Discussion Papers in Economic Behaviour from University of Valencia. N. 810. 2010. P. 1-22.