Теория игр

    Условие предпочтительности отражает необходимость  “единодушия” в предпочтении со стороны коалиции: если хотя бы одно из неравенств x_i > y_i будет нарушено, т.е. если хотя бы для одного из членов коалиции K выигрыш в условиях дележа  y  будет не меньшим, чем в условиях дележа  x, то можно будет говорить о предпочтении дележа x дележу  y  не всей коалицией K, а только теми её членами, для которых соответствующее неравенство x_i > y_i соблюдается.

    Соотношение доминирования  x  над y  по коалиции K обозначается через

    

.

    Определение. Делёж x  доминирует  y, если существует такая коалиция K, для которой делёж x  доминирует  y. Это доминирование обозначается так:

    x > y.

    Наличие доминирования x > y означает, что в множестве игроков N найдётся коалиция, для которой  x  предпочтительнее  y. Отношение доминирования не обладает полностью свойствами рефлексивности, симметрии, транзитивности, возможна только частичная симметрия и транзитивность. Соотношение доминирования возможно не по всякой коалиции. Так, невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков.

    Справедлива следующая теорема.

    Теорема. Если u и u¹ – две стратегически эквивалентные характеристические функции,  причём дележам  x  и y  соответствуют дележи и , то из  x > y  следует > .

    Очевидно, все явления, описываемые в терминах доминирования дележей, относятся к классам стратегической эквивалентности, поэтому достаточно изучать эти классы (а не сами игры) для существенных игр по их (0,1)-редуцированной форме, а для несущественных игр – по нулевым играм.

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

    Рассмотрим  доминирование дележей в существенной игре на следующем примере.

    Пример. Пусть имеется (0,1)-редуцированная форма существенной игры трёх игроков с постоянной суммой (равной 1). Поскольку доминирование невозможно ни по одной из одноэлементных коалиций 1,2,3, а также по коалиции, состоящей из всех трёх игроков, то доминирование возможно только по одной из двухэлементных коалиций {1,2}, {1,3}, {2,3}.

    Для наглядности доминирования дележей  введём понятие бароцентрических координат. Осями координат служат три оси x₁, x₂, x₃, составляющие между собой одинаковые углы 60^о, ось x₃ находится на расстоянии единицы от точки пересечения осей  x₁ и x₂ (рис.1), координаты точки x = (x₁, x₂, x₃) – соответственно расстояния от этой точки до осей x₁, x₂, x₃, взятые с такими знаками, как указано на рис.1. (Например, для точки x на рис.1.   x₁ < 0,  x₂ > 0,  x₃ > 0). 

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

    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₁.