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

UptoLike

ВУЗ: 

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

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

Рубрика: 

52 53
1 выбирает стратегию
b
, а игрок 2 –
b
, поскольку эти стратегии обеспе-
чивают наилучший результат и т. д.
Вычислим средний выигрыш за первые три шага:
(
)
=ha=
å
j
jij
i
v 1max1
11
(
)
(
)
(
)
{
}
=
×
+
×
+
×
×
+
×
+
×
×
+
×
+
×
=
010211;010013;030112max
i
{
}
;31;;2max
=
=
3
i
(
)
=xa=
å
i
iij
j
v 1min1
1
1
(
)
(
)
(
)
{
}
=
×
+
×
+
×
×
+
×
+
×
×
+
×
+
×
=
010113;020011;010312min
j
{
}
;13;;2max
=
=
1
i
(
)
=ha=
j
jij
i
v 2max2
22
(
)
(
)
(
)
{
}
=
×
+
×
+
×
×
+
×
+
×
×
+
×
+
×
=
01212211;01210213;03211212max
i
{
}
;2323;;23max
=
=
23
i
(
)
=xa=
å
i
iij
j
v 2min2
2
2
(
)
(
)
(
)
{
}
=
×
+
×
+
×
×
+
×
+
×
×
+
×
+
×
=
01211213;02210211;01213212min
j
{
}
;2124;;25max
=
=
21
i
(
)
=ha=
å
j
jij
i
v 3max3
33
(
)
(
)
(
)
{
}
{
}
;35;1;34max322311;313;321312max
=
=
×
+
×
×
×
+
×
=
35
ii
(
)
(
)
(
)
(
)
{
}
=×+×××+×=xa=
321313;311;323312min3min3
3
3
j
i
iij
j
v
{
}
.3135;;38max
=
=
31
i
В таблице приведены результаты разыгрываний, указаны страте-
гия игрока, накопленный и средний выигрыши.
Таким образом, за 12 партий мы получили приближение решения
(
)
127,61,41
12
=x
,
(
)
125,21,121
12
=y
, а точность может быть оценена
числом
21
. Основным недостатком рассмотренного метода является егоо
малая скорость сходимости, которая уменьшается с ростом размерности
матрицы. Это является также следствием немонотонности последова-
тельностей
kv
k
и
kv
k
.
Рассмотрим другой итеративный алгоритм, который избавлен от
указанного недостатка.
7.2. Монотонный итеративный алгоритм решения МИ
Рассмотрим смешанное расширение
(
)
KYXG
A
,,
=
МИ с
(
)
nm
´
-
матрицей А.
Обозначим
(
)
I1
,..., SÎxx=
N
m
NN
x
приближение оптимальной
стратегии игрока 1 на N-й итерации и
(
)
N
n
NNnN
cRc gg=Î ,...,,
1
– вспомо-
гательный вектор. Алгоритм позволяет находить (точно и приближенно)
оптимальную стратегию игрока 1 и значение игры
v
.
Итеративный процесс строится следующим образом. В начале
процесса игрок 1 выбирает произвольную чистую стратегию
0
i
, т. е.
(
)
0,...,1,...,0
0
0
i
x =
, и вспомогательный вектор вида
0
0
i
ac =
, где
0
i
a
–
строка матрицы А, имеющая номер
0
i
.
Пусть выполнена
1
-
N
итерация и получены векторы
11
,
-- NN
cx
.
Тогда
N
x
и
N
c
вычисляются по следующим итеративным
формулам:
(
)
,
~
1
1 N
N
N
N
N
xxx a+a-=
-
(7.3)
(
)
,
~
1
1 N
N
N
N
N
ccc a+a-=
-
(7.4)
где параметр
10
£
a
£
N
. Векторы
N
x
~
и
N
c
~
будут получены ниже.е.

Страницы