Реферат: Кооперативные игры

--PAGE_BREAK--, т.е. имеется <img width=«75» height=«20» src=«ref-1_598735433-528.coolpic» v:shapes="_x0000_i1051"> произвольных параметров.

Рассмотрим теперь кооперативные игры без условия постоянства суммы.

1. Для игр 2-х игроков множество N={1,2}, условия редуцированности дают

u(Æ) = u(1) = u(2) = u(1,2) = 1.

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

2. Для игр 3-х игроков множество N={1,2,3}, условия редуцированности дают

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

Значения характеристической функции на множествах коалиций двух игроков произвольные (здесь нет условия дополнительности)

u(1,2) = C3, u(1,3) = C2, u(2,3) = C1,

но удовлетворяющие условию

0 £C1, C2, C3£1.

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

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

Определение. Пусть имеется два дележа x= (x1, ..., xn) и y= (y1, ..., yn) в кооперативной игре G= {N,u}, и KÌN–некоторая коалиция. Тогда делёж xдоминирует yпо коалиции K, если

1) <img width=«40» height=«36» src=«ref-1_598736489-585.coolpic» v:shapes="_x0000_i1052">£u(K) (свойство эффективности доминирующего платежа)

2) xi> yiдля всех iÎK(свойство предпочтительности)
Свойство эффективности означает, что сравниваемый коалицией делёж xдолжен быть, реализуемым этой коалицией: сумма выигрышей каждого из членов коалиции не должна превосходить уверенно получаемое ею количество. В противном случае коалиция, встретившись с дележём, дающим ей столько, сколько она самостоятельно не в состоянии добиться, должна согласиться на него и не заниматься его сравнением с какими либо другими дележами.

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

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

<img width=«52» height=«27» src=«ref-1_598737074-514.coolpic» v:shapes="_x0000_i1053">.

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

x> y.

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

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

Теорема. Если uи u1– две стратегически эквивалентные характеристические функции, причём дележам xи yсоответствуют дележи <img width=«19» height=«20» src=«ref-1_598734113-300.coolpic» v:shapes="_x0000_i1054"> и <img width=«12» height=«21» src=«ref-1_598737888-169.coolpic» v:shapes="_x0000_i1055"><img width=«19» height=«24» src=«ref-1_598738057-329.coolpic» v:shapes="_x0000_i1056">, то из x> yследует <img width=«19» height=«20» src=«ref-1_598734113-300.coolpic» v:shapes="_x0000_i1057">><img width=«19» height=«24» src=«ref-1_598738057-329.coolpic» v:shapes="_x0000_i1058">.

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

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

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

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

Для наглядности доминирования дележей введём понятие бароцентрических координат. Осями координат служат три оси x1, x2, x3, составляющие между собой одинаковые углы 60о, ось x3находится на расстоянии единицы от точки пересечения осей x1и x2(рис.1), координаты точки x= (x1, x2, x3) –соответственно расстояния от этой точки до осей x1, x2, x3, взятые с такими знаками, как указано на рис.1. (Например, для точки xна рис.1. x1 < 0, x2 > 0, x3 > 0).
<img width=«538» height=«262» src=«ref-1_598739015-14537.coolpic» v:shapes="_x0000_i1059">

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

x1+ x2+ x3= 1.  <img width=«21» height=«31» src=«ref-1_598753552-432.coolpic» v:shapes="_x0000_i1060">

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

x1+ x2£u(1, 2), x1+ x3£u(1, 3), x2+ x3£u(2, 3).

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

x1+ x2= 1 -x3£1 = u(1, 2), x1+ x3£1, x2+ x3£1.

Делёж x= (x1, x2, x3) доминирует дележ y= (y1, y2, y3)

по коалиции {1, 2}, если x1> y1, x2> y2;

по коалиции {1, 3}, если x1> y1, x3> y3;

по коалиции {2, 3}, если x2> y2, x3> y3,

т.е. если делёж yнаходится в одном из заштрихованных параллелограммов (за исключением трёх граничных прямых, проходящих через точку x) на рис. 3, то делёж xдоминирует делёж y, а всякая точка находящаяся в не заштрихованных треугольниках, является предпочтительнее исхода x.
 x3= -1 x2= -1
<img width=«532» height=«251» src=«ref-1_598753984-8659.coolpic» v:shapes="_x0000_s1026 _x0000_s1027 _x0000_s1028 _x0000_s1029 _x0000_s1030 _x0000_s1031 _x0000_s1032 _x0000_s1033 _x0000_s1034 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1039 _x0000_s1040 _x0000_s1041 _x0000_s1042 _x0000_s1043 _x0000_s1044 _x0000_s1045">   x= (x1, x2, x3)
        x3= 1 -C3

    x1= 0
    x1= 1 -C1    x2= 1 -C2

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

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

Рассмотрим сначала условия доминирования дележа x= (x1, x2, x3) над дележём y= (y1, y2, y3) по коалиции {1, 2}. В этом случае имеем :

<img width=«147» height=«47» src=«ref-1_598762643-1182.coolpic» v:shapes="_x0000_i1061">   <img width=«21» height=«31» src=«ref-1_598763825-402.coolpic» v:shapes="_x0000_i1062">

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

x1+ x2= C3.

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

x3= 1 + C3.

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

x1³1 -C1, x2³1 -C2, x3³1 -C3,  <img width=«21» height=«31» src=«ref-1_598764227-439.coolpic» v:shapes="_x0000_i1063">

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

Если в (8) одно из неравенств, например, третье не имеет места, то есть только 2 парал- лелограмма, заштрихованных на рис. 5, находясь в некоторых точках xдоминирует y.
x1= 1 -C<img width=«558» height=«225» src=«ref-1_598764666-8767.coolpic» v:shapes="_x0000_s1046 _x0000_s1047 _x0000_s1048 _x0000_s1049 _x0000_s1050 _x0000_s1051 _x0000_s1052 _x0000_s1053 _x0000_s1054 _x0000_s1055 _x0000_s1056 _x0000_s1057 _x0000_s1058 _x0000_s1059 _x0000_s1060 _x0000_s1061 _x0000_s1062 _x0000_s1063 _x0000_s1064 _x0000_s1065 _x0000_s1066 _x0000_s1067 _x0000_s1068 _x0000_s1069 _x0000_s1070">1  x2= 1 -C<img width=«558» height=«225» src=«ref-1_598764666-8767.coolpic» v:shapes="_x0000_s1071 _x0000_s1072 _x0000_s1073 _x0000_s1074 _x0000_s1075 _x0000_s1076 _x0000_s1077 _x0000_s1078 _x0000_s1079 _x0000_s1080 _x0000_s1081 _x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1085 _x0000_s1086 _x0000_s1087 _x0000_s1088 _x0000_s1089 _x0000_s1090 _x0000_s1091 _x0000_s1092 _x0000_s1093 _x0000_s1094 _x0000_s1095">2  x2= 1 -C<img width=«558» height=«225» src=«ref-1_598764666-8767.coolpic» v:shapes="_x0000_s1096 _x0000_s1097 _x0000_s1098 _x0000_s1099 _x0000_s1100 _x0000_s1101 _x0000_s1102 _x0000_s1103 _x0000_s1104 _x0000_s1105 _x0000_s1106 _x0000_s1107 _x0000_s1108 _x0000_s1109 _x0000_s1110 _x0000_s1111 _x0000_s1112 _x0000_s1113 _x0000_s1114 _x0000_s1115 _x0000_s1116 _x0000_s1117 _x0000_s1118 _x0000_s1119 _x0000_s1120">2  x1= 1 -C<img width=«558» height=«225» src=«ref-1_598764666-8767.coolpic» v:shapes="_x0000_s1121 _x0000_s1122 _x0000_s1123 _x0000_s1124 _x0000_s1125 _x0000_s1126 _x0000_s1127 _x0000_s1128 _x0000_s1129 _x0000_s1130 _x0000_s1131 _x0000_s1132 _x0000_s1133 _x0000_s1134 _x0000_s1135 _x0000_s1136 _x0000_s1137 _x0000_s1138 _x0000_s1139 _x0000_s1140 _x0000_s1141 _x0000_s1142 _x0000_s1143 _x0000_s1144 _x0000_s1145">1
        x3= 1 -C3

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

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

  <img width=«91» height=«36» src=«ref-1_598799734-886.coolpic» v:shapes="_x0000_i1064">   <img width=«21» height=«31» src=«ref-1_598800620-429.coolpic» v:shapes="_x0000_i1065">

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

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

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

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

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

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

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

u(1, 2, 3) = 1,

u(1, 2) = С3; u(1, 3) = С2; u(2, 3) = С1,

где 0 £С1, С2, С3£1.

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

x1+ x2³C3, x1+ x3³C2, x2+ x3³C1

или, используя равенство x1+ x2+ x3 = 1, получим

  x3£1 -C3, x2£1 -C2, x3£1 -C1.  <img width=«28» height=«31» src=«ref-1_598801049-446.coolpic» v:shapes="_x0000_i1066">    продолжение
--PAGE_BREAK--