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

UptoLike

ВУЗ: 

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

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

Рубрика: 

56 57
Теорема 7.2. Пусть
{
}
{
}
NN
xv ,
– итеративные последовательности,
определяемые (7.3), (7.5). Тогда справедливы следующие утверждения:
1)
1-
>
NN
vv
, т. е. последовательность
}{
1
-
N
v
строго монотонно
возрастает;
2)
;lim vvv
N
N
==
¥®
(7.6)
3)
*
lim xx
N
N
=
¥®
, где
*
I
*
SÎx
– оптимальная стратегия игрока 1.
Пример 7.2. Решим, используя монотонный алгоритм, игру с
матрицей
.
121
103
312
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=A
Итерация 0. Пусть игрок 1 выбрал 1-ю строку матрицы А, т. е.
(
)
0,0,1
0
=x
и
(
)
3,1,2
1
0
== ac
. Вычислим
{
}
2,1min
00
2
0
0
==g=g= Jv
j
j
.
Итерация 1. Рассмотрим подыгру
A
GG Ì
1
с матрицей
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
2
0
1
1
A
.
Оптимальной стратегией
1
~
игрока 1 является вектор
(
)
1,0,0
~
1
=x
. Тогдада
(
)
1,2,1
~
3
1
== ac
.
Решаем
(
)
32
´
-игру с матрицей
÷
÷
ø
ö
ç
ç
è
æ
121
312
. Заметим, что 3-й столбецец
матрицы доминируем, поэтому смотрим матрицу
÷
÷
ø
ö
ç
ç
è
æ
21
12
. В силу
симметрии оптимальной стратегией игрока 1 в этой игре является вектор
(
)
(
)
2
1
,
2
1
1, =a-a
NN
.
Вычисляем
1
и
1
c
по формулам (7.3), (7.4). Имеем
(
)
( )
.123min
;2,23,23
~
2121
;21,0,21
~
2121
0
1
2
1
1
1
1
101
101
=>=g=g=g=
=+=
=+=
vv
ccc
xxx
j
j
Множество индексов имеет вид
{
}
2,1
1
=J
.
Итерация 2. Рассмотрим подыгру
A
GG Ì
2
с матрицей
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
21
03
12
2
A
.
Первая строка в этой матрице доминируема, поэтому достаточно
рассмотреть подматрицу
÷
÷
ø
ö
ç
ç
è
æ
21
03
.
Оптимальной стратегией игрока 1 в этой игре является вектор
(
)
43,41
, поэтому
(
)
43,41,0
~
2
=x
. Вычислим
4341
~
32
2
=+= aac
(
)
1,23,23=
и рассмотрим
(
)
32
´
-игру с матрицей
÷
÷
ø
ö
ç
ç
è
æ
12323
22323
.
Первая стратегия игрока 1 доминирует вторую, поэтому
0
1
=
a
. Таким
образом, вычисления закончены:
(
)
21,0,21
1*
== xx
; значение v игры
равно
23
1
== vv
. Оптимальная стратегия игрока 2 имеет вид
(
)
0,21,21
*
=y
(см. пример 7.1, вторая строка в таблице).
Самостоятельная работа № 6
Найти значение игры в смешанных стратегиях с помощью итера-
тивных методов

Страницы