Бескоалиционные игры в нормальной форме. Часть 1. Григорьева К.В. - 21 стр.

UptoLike

ВУЗ: 

СПбГАСУ | Санкт-Петербург

Составители: 

Рубрика: 

40 41
является выпуклой на М, а нижняя огибающая (в (5.3) берется минимум
по i) является вогнутой.
Теорема 5.1. В МИ
A
G
множества оптимальных смешанных
стратегий
*
I
S
и
*
II
S
игроков являются выпуклыми многогранниками.
Вернемся к теореме 3.7. В качестве примера использования теоремы
приведем геометрическое решение игр с двумя стратегиями у одного из
игроков (
(
)
n
´
2
- и
(
)
2
´
m
-игры). Такой подход называется графоанали-
тическим методом решения
(
)
n
´
2
- либо
(
)
2
´
m
-МИ. В основее
графоаналитических методов лежит свойство оптимальных стратегий
*
x
и
*
y
доставлять экстремумы в критических точкахах
(
)
(
)
.,maxmin,minmax yiEjxEv
i
yj
x
A
=
=
Пример 5.1. (
(
)
n
´
2
-игра). Рассмотрим игру, в которой игрок 1 имеет
две стратегии, а игрок 2 – п стратегий. Матрица имеет вид
.
...
...
22221
11211
÷
÷
ø
ö
ç
ç
è
æ
aaa
aaa
=
n
n
A
Пусть игрок 1 выбрал смешанную стратегию
(
)
x
-
x
=
1,x
, а игрок
2 чистую –
j
Î
. Тогда выигрыш игрока 1 в ситуации
(
)
jx,
равенен
(
)
(
)
.1,
21 jj
jxE
a
x
-
+
xa
=
(5.4)
Геометрически он представляет собой прямую в координатах
(
)
E,
x
.
Таким образом, каждой чистой стратегии j соответствует своя прямая.
Графиком функции
(
)
(
)
jxEH
j
,min
=
x
является нижняя огибающая
семейства прямых (5.4). Эта функция вогнута как нижняя огибающая
семейства вогнутых (в данном случае линейных) функций (лемма 5.1).
Точка
*
x
, в которой достигается максимум функции
(
)
x
H
по
[
]
1,0
Î
x
,
дает требуемый оптимальный набор стратегий
(
)
***
1, x-x=x
и значение
игры
(
)
*
x= Hv
A
.
Для определенности рассмотрим игру с матрицей
.
0412
4131
÷
÷
ø
ö
ç
ç
è
æ
=A
Для каждого
4,1=j
имеем:
(
)
(
)
122,,21,
+
x
=
+
x
-
=
xExE
,
(
)
433,
+
x
-
=
xE
,
(
)
.44,
x
=
xE
Нижняя огибающая
(
)
x
H
семействаа
прямых
(
)
{
}
jxE ,
и сами прямые
(
)
jxE ,
,
4,1=j
, изображены на рис. 5.1.
Рис. 5.1. Геометрическая интерпретация
выигрыша первого игрока
Максимум
(
)
*
xH
функции
(
)
x
H
находится на пересечении первойой
и четвертой прямых. Таким образом,
*
x
– решение уравнения
.24
**
A
v=+x-=x
Откуда получаем оптимальную стратегию
(
)
53,52
*
=x
игрока 1
и значение игры
58
=
A
v
. Оптимальную стратегию игрока 2 найдем из
следующих соображений. Заметим, что в рассматриваемом случае
(
)
(
)
.584,1,
**
===
A
vxExE
Для оптимальной стратегии
(
)
*
4
*
3
*
2
*
1
*
,,, hhhh=y
должно
выполняться равенство
(
)
(
)
(
)
(
)
(
)
.4,3,2,1,,
**
4
**
3
**
2
**
1
**
xExExExEyxEv
A
h+h+h+h==
При этом
(
)
(
)
583,,582,
**
>> xExE
, следовательно,
0
*
3
*
2
=h=h
,
а
*
4
*
1
, hh
можно найти из условия (5.3):

Страницы