Кооперативные игры (стр. 3 из 4)

В барицентрической системе координат всегда выполняется равенство

x₁ + x₂ + x₃ = 1.

В плоскости всегда имеется точка с координатами x₁, x₂, x₃, удовлетворяющими равенству (6). По этому бароцентрическая система координат автоматически удовлетворяет одному из условий, определяющих исход игры трёх игроков. С другой стороны, поскольку игра в (0, 1)-редуцированной форме, то точка x должна находиться в заштрихованном треугольнике (см. рис. 2). Дележи x₁, x₂, x₃ должны удовлетворять неравенствам

x₁ + x₂ £ u(1, 2), x₁ + x₃ £ u(1, 3), x₂ + x₃ £ u(2, 3).

Очевидно, из условия дополнительности, что

x₁ + x₂ = 1 - x₃ £ 1 = u(1, 2), x₁ + x₃ £ 1, x₂ + x₃ £ 1.

Делёж x = (x₁, x₂, x₃) доминирует дележ y = (y₁, y₂, y₃)

по коалиции {1, 2}, если x₁ > y₁, x₂ > y₂;

по коалиции {1, 3}, если x₁ > y₁, x₃ > y₃;

по коалиции {2, 3}, если x₂ > y₂, x₃ > y₃,

т.е. если делёж y находится в одном из заштрихованных параллелограммов (за исключением трёх граничных прямых, проходящих через точку x) на рис. 3, то делёж x доминирует делёж y, а всякая точка находящаяся в не заштрихованных треугольниках, является предпочтительнее исхода x.

x₃ = - 1 x₂ = - 1

x = (x₁, x₂, x₃)

x₃ = 1 - C₃

x₁ = 0

x₁ = 1 - C₁ x₂ = 1 - C₂

Рис.3 Рис. 4

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

Пример. Пусть имеется (0, 1)-редуцированная игра трёх игроков с ненулевой суммой.

Рассмотрим сначала условия доминирования дележа x = (x₁, x₂, x₃) над дележём y = (y₁, y₂, y₃) по коалиции {1, 2}. В этом случае имеем :

Поскольку может быть, что C₃ < 1 , то первое из условий (7) нельзя отбросить, как это делает- ся в играх с постоянной суммой. Это значит что, x должна быть не ниже прямой

x₁ + x₂ = C₃.

Или, учитывая (6), последнее уравнение принимает вид

x₃ = 1 + C₃ .

Таким образом, если делёж x таков, что

x₁ ³ 1 - C₁, x₂ ³ 1 - C₂, x₃ ³ 1 - C₃,

то имеется три параллелограмма, заштрихованных на рис. 4, находясь в которых, точки x доминируют y.

Если в (8) одно из неравенств, например, третье не имеет места, то есть только 2 парал- лелограмма, заштрихованных на рис. 5, находясь в некоторых точках x доминирует y.

x₁ = 1 - C

₁ x₂ = 1 - C ₂ x₂ = 1 - C ₂ x₁ = 1 - C ₁

x₃ = 1 - C₃

x

Рис. 5 Рис. 6

Из рассмотренного примера видно, что возможно много вариантов, которые возникают при изучении вопросов, связанных с доминированием дележей в кооперативных играх. С ростом числа игроков чрезвычайно быстро растёт количество таких вариантов. В связи с этим возникает необходимость выделения вполне устойчивых дележей, т.е. таких дележей, которые не доминируются никакими другими дележами. Множество вполне устойчивых дележей в кооперативной игре называется с-ядром этой игры.

Теорема. Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией u, необходимо и достаточно, чтобы для любой коалиции K выполнялось неравенство

Поскольку неравенства (9) линейны относительно x, то из последней теоремы следует, что с-ядро в любой кооперативной игре является выпуклым многогранником.

К особенностям кооперативных игр относительно существования с-ядра относятся :

1) в несущественной игре с-ядро существует и состоит из единственного дележа этой игры;

2) во всякой существенной игре с постоянной суммой с-ядро пусто.

Для общей игры трёх игроков в (0; 1)-редуцированной форме имеем следующее (рис. 7).

Её характеристическая функция имеет вид :

u(Æ) = u(1) = u(2) = u(3) = 0;

u(1, 2, 3) = 1,

u(1, 2) = С₃; u(1, 3) = С₂; u(2, 3) = С₁,

где 0 £ С₁, С₂, С₃ £ 1.

На основании последней теоремы для принадлежности дележа x с-ядру необходимо и достаточно выполнение неравенств

x₁ + x₂ ³ C₃, x₁ + x₃ ³ C₂, x₂ + x₃ ³ C₁

или, используя равенство x₁ + x₂ + x₃ = 1, получим

x₃ £ 1 - C₃, x₂ £ 1 - C₂, x₃ £ 1 - C₁.

3

1 2

Рис. 7

Это означает, что точка x должна лежать ближе к i-й вершине основного треугольника (см. рис. 7), чем прямая

x_i = 1 - С_i (i = 1,2,3)

Из неравенства (10) путём суммирования получим

x₁ + x₂ + x₃ £ 3 - (С₁ + С₂ + С₃)

или, учитывая, что x₁ + x₂ + x₃ = 1, получим

С₁ + С₂ + С₃ £ 2.

Неравенство (12) является необходимым условием существования непустого с-ядра. С другой стороны, если (12) выполняется, то можно взять такие неотрицательные e₁, e₂, e₃, чтобы

,

и положить

x_i = 1 - C_i - e_i (i =

)

Такие значения x_i и удовлетворяют неравенствам (10), т.е. такой делёж x = (x₁, x₂, x₃) принад- лежит с-ядру.

Геометрически непустое с-ядро является заштрихованным треугольником (рис. 7), со сто- ронами, выраженными уравнениями (11)

3 3

1 2 1 2

Рис. 8 Рис. 9

при условии, что выполняется соотношение

x₁ + x₂ + x₃ = 1,

и решения любой пары уравнений (11) являются неотрицательными. Так, например, рассмот- рим систему

x₁ = 1 - С₁, x₂ = 1 - С₂.

Поскольку 0 £ С₁ £ 1, 0 £ С₂ £ 1, то x₁, x₂ ³ 0. Отсюда получаем

x₃ = 1 - x₁ - x₂ = 1 - (1 - С₁) - (1 - С₂) = С₁ + С₂ - 1.

Для того, чтобы было x₃ ³ 0, необходимо чтобы

С₁ + С₂ - 1 ³ 0

или

С₁ + С₂ ³ 1.

В этом случае с-ядро представлено на рис.7 в виде заштрихованного треугольника внутри основного треугольника. Аналогично рассматриваются остальные возможные варианты сочета- ний неравенств. Например, если С₁ + С₂ < 1, то с-ядро имеет вид заштрихованного четырёх- угольника внутри основного треугольника (рис.8). Вообще многогранник, представляющий с‑ядро, образуется как выпуклый многогранник пересечением прямых (11) и строк основного треугольника. Если, например, выполняются неравенства

С₁ + С₂ < 1; С₂ + С₃ < 1; С₁ + С₃ < 1,

то с-ядро представляется в виде шестигранника, заштрихованного на рис.9.

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

Дж. фон Нейман и О. Моргенштерн предложили потребовать от множества дележей, которое принимается в качестве решения кооперативной игры следующие два свойства: внут- реннюю устойчивость, состоящую в том, чтобы дележи из решений нельзя было противопоста- вить друг другу, и внешнюю устойчивость, состоящую в возможности каждому отклонению от решения противопоставлять некоторый делёж, принадлежащий решению. В результате мы приходим к следующему определению.

Определение. Решением по Нейману-Моргенштерну (Н-М-решением) кооперативной игры называется множество R дележей в нём, обладающее следующими свойствами :

1) внутренняя устойчивость: никакие два дележа из R не доминируют друг друга;

2) внешняя устойчивость: каков бы ни был делёж S не принадлежащий R, найдётся делёж r, принадлежащий R, который доминировал бы S.

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