Матвеев В.А. Конечные бескоалиционные игры и равновесия
Подождите немного. Документ загружается.
141
Рассмотрим ситуации, составленные из выделенных стратегий
первого и второго игроков. Каждой из них будет соответствовать набор
чистых стратегий, как объединение соответствующих чистых
стратегий игроков для этой ситуации. Тогда ситуация будет
равновесием по Нэшу тогда и только тогда, когда ей будет
соответствовать полный набор всех чистых стратегий в игре.
Действительно, в этом случае каждая
чистая стратегия либо не
используется в равновесии, либо является наилучшим чистым ответом
на выбор другого игрока. Такая ситуация и является равновесной.
В данной игре выделено пять стратегий первого игрока и четыре
стратегии у второго. Тогда рассматривается 20 ситуаций. Три из них
подходят под условие равновесия по Нэшу. Действительно,
)),(),,,((),(*)
*,(
15
01100YXyx →==
((
1,2,4); (3,5));
)),(),,,((),(),(
24
3
1
3
2
3
2
3
1
0YXyx →==
oo
((1,4,5); (2,3));
)),(),,,((),(),(
32
3
2
3
1
0
3
1
3
2
YXyx →==
⊗⊗
((3,4,5); (1,2)).
Отметим, что ситуация
))0,1(),1,0,0((*)*,(
=
yx
, как
равновесие по Нэшу, была выявлена вначале по определению
3.1 или замечанию 3.1. Вычислим выигрыши игроков в
равновесных ситуациях
);4 ,3() ,() ,(*) *,(*
*****
2
*
1
=⋅⋅⋅⋅== yBxyAxffyxf
TT
);
3
2
2 ,3() ,() ,() ,(
21
=⋅⋅⋅⋅==
ooooooooo
yBxyAxffyxf
TT
).
3
2
,4() ,() ,() ,(
21
=⋅⋅⋅⋅==
⊗⊗⊗⊗⊗⊗⊗⊗⊗
yBxyAxffyxf
TT
Таким образом в рассмотренном примере имеется три
равновесия по Нэшу.
Ответ:
);,(),(*)*,(**
⊗⊗
=× yxyxyxYX UU
oo
));0,1(),1,0,0((*)*,(
=
yx );4 ,3((*
=
f
142
));
3
1
,
3
2
(),
3
2
,
3
1
,0((),( =
oo
yx );
3
2
2 ,3((=
o
f
));
3
2
,
3
1
(),0,
3
1
,
3
2
((),( =
⊗⊗
yx ).
3
2
,4((=
⊗
f
Пример 16.2. Решить биматричную игру, используя алгоритм
Лемке - Хаусона
.
032
040
706
,
007
340
206
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
=
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
= BA
В игре у игроков нет доминируемых стратегий. Но здесь
имеется 9 ситуаций в чистых стратегиях и одна удовлетворяет
определению равновесия по Нэшу (3.1). Это ситуация
(x*, y*) = ((0, 1, 0), (0,1, 0))
∈
X
×
Y; f(x*, y*) = (4, 4).
В игре возможны и другие решения. Выделим их по алгоритму
Лемке – Хаусона.
В рассматриваемой задаче матрица B является
транспонированные для матрицы А, т.е. А
T
= В. В такой игре
равновесная ситуация состоят из одинаковых стратегии первого
и второго игрока. Поэтому рассмотрим игру с позиций первого
игрока, для второго игрока рассуждения аналогичны.
Множество смешанных стратегий первого игрока
представлено на рисунке 16.4. Это множество является
фундаментальным симплексом в пространстве
.
3
R
Каждой
смешанной стратегии первого игрока поставим в соответствие
выбранные чистые стратегии первого и второго игроков. Чистые
стратегии первого игрока будем отмечать
1 ,2 ,3 , а чистые
стратегии второго игрока отметим
4,5,6.
Каждой смешанной стратегии первого игрока
соответствуют, во-первых, чистые стратегии первого игрока, что
в этой смешанной стратегии используются с вероятностью 0, во-
вторых, чистые стратегии второго игрока, что являются лучшими
ответами на это действие первого. Так как биматричная игра
невырожденная, то каждой смешанной стратегии первого игрока
143
в итоге будет соответствовать не более, чем три чистые стратегии
(первого и второго игроков).
Для нахождений наилучших чистых ответов второго игрока
рассмотрим его варианты выбора в зависимости от смешанной
стратегии первого
).7 ,33 ,242(
032
040
706
)1 , ,(
12121
2121
xxxxx
xxxxBx
T
+−−+
=
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
⋅−−=
(16.3)
Каждая стратегия первого игрока однозначно соответствует
паре параметров
.0 ,2,1,0,),(
21
2
21
≤+=≥∈ xxixRxx
i
Пространство стратегий
2
21
),( Rxx ∈
представлено на рисунке 16.5.
Для нахождения лучших ответов второго игрока рассмотрим функции
A
K
E
H
D
F
C
G
1
x
2
x
3
x
B
O
1
2
3
Рис. 16.4.
144
,22
211
xxf −+=
,
212
33 xxf
+
−
=
.7
13
xf =
Эти функции получены в (16.3). Выберем те стратегии первого
игрока, на которые второй игрок ответит выбором своей первой,
второй или третьей чистой стратегии. Соответствующие условия
и преобразования приведены в таблице 16.1.
Таблица 16.1.
На рисунке 16.5 в пространстве параметров выделены области и
в них указаны наилучшие выборы второго игрока. На этой области
отмечены точки, которым поставлены в
соответствие два лучших ответа
второго игрока. Укажем на рисунке 16.5 те значения параметра (значит,
стратегии) у которых вероятность выбора i – ой чистой стратегии (i =
1, 2, 3) равна 0. Эти чистые стратегии также отмечены на рисунке 16.5.
Здесь выбранные чистые стратегии первого игрока представлены
соответственно
1,2,3, а у второго игрока стратегии отмечены, как 4,5,6.
Выберем те стратегии первого игрока, которым соответствуют
три чистые стратегии (первого и второго игроков). Эти стратегии,
точнее соответствующие им точки в пространстве параметров,
указаны на рисунке 16.5. Это точки А, B, C, D, F. У выделенных
точек отмечены два соответствующие параметра. По ним найдём
координаты этих точек в пространстве
.
3
R
Таким образом, получаем
145
),
7
6
,0,
7
1
(A →
(2,4,5);
),
3
1
,0,
3
2
(B →
(2,4,6);
),0,0,1(C → (2,3,6);
),0,
11
7
,
11
4
(D →
(3,5,6);
),0,1,0(E → (1,3,5);
),
23
4
,
23
11
,
23
8
(F →
(4,5,6). (16.4)
Так как матрица B
T
= A, то рассуждения для второго игрока будут
дословно повторять рассуждения с позиции первого игрока.
Выберем те стратегии второго игрока, которым соответствуют
три чистые стратегии (первого и второго игроков). Эти стратегии,
точнее соответствующие им точки в пространстве параметров, будут
1
1
0
5
5
6
4
4
6
A
B
GC
E
D
H
F
Рис. 16.5.
7
1
10
3
3
2
1
x
2
x
146
те же, что у первого игрока на рисунке 16.4. По ним найдём
координаты этих точек в пространстве
.
3
R
Для обозначения этих
точек будем использовать штрихи.
Каждой такой точке поставим в соответствие, во-первых,
чистые стратегии второго игрока, что в этой смешанной стратегии
используются с вероятностью 0, во-вторых, чистые стратегии
первого игрока, что являются лучшими ответами на это действие
второго. Из приведённых слов следует, что соответствующие чистые
стратегии можно получить из (16.4), поменяв
в обозначениях x и y
соответственно местами. Это является следствием взаимной
транспонированности матриц А, В. Итак, получаем
)
7
6
,0,
7
1
('A →
(1,2,5);
)
3
1
,0,
3
2
('B →
(1,3,5);
)0,0,1('C → (3,5,6);
)0,
11
7
,
11
4
('D →
(2,3,6);
)0,1,0('E → (2,4,6);
)
23
4
,
23
11
,
23
8
('F →
(1,2,3). (16.5)
Рассмотрим ситуации, составленные из выделенных стратегий
первого и второго игроков. Каждой из них будет соответствовать
набор чистых стратегий, как объединение соответствующих чистых
стратегий игроков для этой ситуации. Тогда ситуация будет
равновесием по Нэшу тогда и только тогда, когда ей будет
соответствовать полный набор всех чистых стратегий в игре.
В данной игре выделено по
шесть стратегий для первого и
второго игроков. Тогда рассматривается 36 ситуаций. Три из них
подходят под условие равновесия по Нэшу. Действительно,
))0,1,0(),0,1,0(()',(*)*,( EEyx →== ((1,3,5,);(2,4,6));
147
))
3
1
,0,
3
2
(),
3
1
,0,
3
2
(()',(),( BByx →==
oo
((2,4,6);(1,3,5));
))
23
4
,
23
11
,
23
8
(),
23
4
,
23
11
,
23
8
(()',(),( FFyx →==
⊗⊗
((4,5,6);(1,2,3));
Отметим, что ситуация
))0,1,0(),0,1,0((*)*,(
=
yx
, как равновесие
по Нэшу, была выявлена вначале по определению 3.1 или
замечанию 3.1. Вычислим выигрыши игроков в равновесных
ситуациях
);4 ,4() ,() ,(*) *,(*
*****
2
*
1
=⋅⋅⋅⋅== yBxyAxffyxf
TT
);
3
2
4 ,
3
2
4() ,() ,() ,(
21
=⋅⋅⋅⋅==
ooooooooo
yBxyAxffyxf
TT
).
23
10
2 ,
23
10
2(
) ,() ,() ,(
21
=⋅⋅⋅⋅==
⊗⊗⊗⊗⊗⊗⊗⊗⊗
yBxyAxffyxf
TT
Таким образом в рассмотренном примере имеется три
равновесия по Нэшу.
Ответ:
);,(),(*)*,(**
⊗⊗
=× yxyxyxYX UU
oo
));0,1,0(),0,1,0((*)*,(
=
yx );4 ,4((*
=
f
));
3
1
,
3
2
(),
3
1
,0,
3
2
((),( =
oo
yx
);
3
2
4 ,
3
2
4((=
o
f
));
23
4
,
23
11
,
23
8
(),
23
4
,
23
11
,
23
8
((),( =
⊗⊗
yx
).
23
10
2 ,
23
10
2((=
⊗
f
Задачи для самостоятельного решения
148
Задача 14.1. Решить биматричную игру, заданной матрицами
выигрыша первого игрока и второго игрока, используя алгоритм
Лемке – Хаусона
a) (А, В) =
);
130
201
,
123
321
(
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
б) (C, D) =
);
032
812
431
,
321
204
183
(
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
с) (E, F) =
).
113
112
133
222
132
,
323
233
211
133
123
(
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
⎟
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎜
⎝
⎛
149
ЗАДАНИЯ
ДЛЯ
САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
150
Задание 1. Графоаналитическим методом найти цену и седловую
точку матричной игры, заданную матрицей выигрышей первого
игрока.