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

UptoLike

ВУЗ: 

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

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

Рубрика: 

50 51
Оптимальные стратегии
*
x
и
*
y
игроков в игре с этой матрицей
равны
(
)
41,43
**
== yx
, при этом значение
v
игры равно
23
.
Последняя матрица получена вычеркиванием первых двух строк
и столбцов, поэтому оптимальными стратегиями игроков в исходной игре
являются расширения указанных стратегий на 1-м и 2-м местах, т. е.
(
)
41,43,0,0
*
12
*
12
== yx
.
Заметим, что поскольку в решении использовалось нестрогое до-
минирование, то могут быть потеряны другие оптимальные стратегии.
Самостоятельная работа № 5
Рассмотреть игру на доминирование и найти ситуацию равновесия.
ЗАНЯТИЕ № 7
Итеративные методы решения матричных игр
7.1. Итеративный метод Брауна – Робинсона (метод фиктивного
разыгрывания)
Идея метода – многократное фиктивное разыгрывание игры с
заданной матрицей выигрыша. Одно повторение игры будем называть
партией. Пусть разыгрывается игра с
(
)
nm
´
-матрицей
}{
ij
A
a
=
. В 1-й
партии оба игрока выбирают совершенно произвольные чистые
стратегии. В k-й партии каждый игрок выбирает ту чистую стратегию,
которая максимизирует его ожидаемый выигрыш против наблюдаемого
эмпирического вероятностного распределения противника за
(
)
1
-
k
партий.
Итак, предположим, что за первые k разыгрываний игрок 1
использовал i-ю стратегию
k
i
x
раз
(
)
mi ,1=
, а игрок 2 – j-ю стратегию
k
j
h
раз
(
)
nj ,1=
. Тогда в
(
)
1
+
k
-й партии игрок 1 будет использоватьать
1+k
i
-ю стратегию, а игрок 2 – свою
1+k
j
-ю стратегию, гдеде
å
å
ha=ha=
+
j
k
jj
k
i
j
k
jij
i
k
v
1
max
и
.min
1
å
å
xa=xa=
+
k
i
k
ij
k
iij
j
k
v
Пусть
v
– значение МИ
A
G
. Рассмотрим отношения
,max
1
å
å
ha=ha=
+
j
k
jj
k
i
j
k
jij
i
k
kkkv
(7.1)
.min
1
å
å
xa=xa=
+
k
i
k
ij
k
iij
j
k
kkkv
(7.2)
Векторы
(
)
kkx
k
m
kk
xx= ..,,.
1
и
(
)
kky
k
n
kk
hh= ...,,
1
являютсяся
смешанными стратегиями игроков 1 и 2 соответственно, поэтому по
определению значения игры имеем
.minmax kvvkv
k
k
k
k
££
Таким образом, получен некоторый итеративный процесс,
позволяющий находить приближенное решение МИ, при этом степень
близости приближения к истинному значению игры определяется длиной
интервала
][ min,max kvkv
k
k
k
k
. Сходимость алгоритма гарантируется
следующей теоремой.
Теорема 7.1.
.maxlimminlim vkvkv
k
k
k
k
kk
=
÷
ø
ö
ç
è
æ
=
÷
ø
ö
ç
è
æ
¥®¥®
Пример 7.1. Найти приближенное решение игры с матрицей
.
121
103
312
cba
A
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
g
b
a
=
Обозначим
g
b
a
,
,
– стратегии игрока 1 и
c
b
a
,
,
– стратегии игрока 2.
Пусть сначала игроки выбрали стратегии
a
и
a
соответственно. Если
игрок 1 выбрал стратегию
a
, то игрок 2 может потерять один из
выигрышей
(
)
3,1,2
-
-
-
. Если игрок 2 выбрал стратегию
a
, то игрок 1
может получить один из выигрышей
(
)
1,3,2
. Во 2-й и 3-й партиях игрок

Страницы