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

UptoLike

ВУЗ: 

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

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

Рубрика: 

46 47
существуют
(
)
0,1,0
=
¢
x
,
(
)
1,0,0
=
¢
¢
x
такие, что:о:
.
2
1
4
0
5
0
2
0
4
1
5
0
;
3
1
3
0
2
0
3
0
3
1
2
0
×
+
×
+
×
³
×
+
×
+
×
×
+
×
+
×
³
×
+
×
+
×
Аналогично, стратегия
y
¢
игрока 2 доминируетт его стратегию
y
, если для всех чистых стратегий
mi ,1=
игрока 1
.yaya
ii
£
(6.4)
Если неравенства (6.3), (6.4) выполняются как строгие, то говорят
о строгом доминировании. Частным случаем доминирования стратегий
является их эквивалентность.
Определение 6.5. Будем называть стратегии
x
и
x
игрока 1
эквивалентными в игре
A
G
, если для всех
nj ,1=
jj
a
x
a
x
¢¢
=
¢
(6.3¢)
и обозначать
x
~
x
. Для двух эквивалентных стратегий
x
и
x
выполняется (для каждого
II
S
Î
y
) равенствоо
(
)
(
)
yxEyxE ,,
¢
¢
=
¢
.
Аналогично, стратегии
y
¢
и
y
¢
¢
игрока 2 эквивалентны (
y
¢
~
y
¢
¢
)
в игре
A
G
, если для всех
mi ,1=
.
ii
ayay
=
(6.4¢)
Отсюда имеем, что для любой смешанной стратегии
I
S
Î
x
игрокаа
1 выполняется равенство
(
)
(
)
.,, yxEyxE
=
Для чистых стратегий введенные определения трансформируются
следующим образом. Если чистая стратегия
i
игрока 1 доминируетт
чистую стратегию
i
, а чистая стратегия
j
¢
игрока 2 – чистуюую
стратегию
j
¢
¢
того же игрока, то для всех
njmi ,1,,1 ==
выполняютсяся
неравенства
.,
jijijiji
¢¢¢¢¢¢
a
£
a
a
³
a
Покажем, что игроки могут не использовать доминируемые стра-
тегии. Этот факт устанавливает следующую теорему.
Теорема 6.1. Если в игре
A
G
стратегия
x
одного из игроков доми-
нирует оптимальную стратегию
*
x
этого игрока, то стратегия
x
такжее
оптимальна.
Отсюда вывод, что оптимальная стратегия может быть доминируе-
ма лишь оптимальной стратегией. С другой стороны, никакая оптималь-
ная стратегия не является строго доминируемой, поэтому строго доми-
нируемые стратегии не могут быть оптимальными.
Теорема 6.2. Если в игре
A
G
стратегия
*
x
одного из игроковов
оптимальна, то
*
x
– недоминируема строго.
Обратное утверждение неверно.
Пример 6.5. Так, в игре с матрицей
÷
÷
ø
ö
ç
ç
è
æ
20
01
1-я и 2-я чистые
стратегии игрока 1 недоминируемы строго, но они неоптимальны.
С другой стороны, если i-я строка (j-й столбец) матрицы А
доминируемы, то нет необходимости приписывать ей (ему)
положительную вероятность в ситуации равновесия. Таким образом, для
нахождения оптимальных стратегий вместо игры
A
G
достаточно решить
подыгру
A
G
¢
, где
A
¢
– матрица, получаемая из матрицы A вычеркиванием
доминируемых строк и столбцов.
Определение 6.6. Если
(
)
I1
,...,
S
Î
x
x
=
m
x
и
1
1
+
£
£
m
i
, тоо
расширением стратегии
x
на i-м месте будем называть вектор
(
)
1
11
,...,,0,,...,
+
-
Îxxxx=
m
miii
Rx
.
Пример 6.6. Так, расширением вектора
(
)
31,32,31
на 2-м месте
является вектор
(
)
31,32,0,31
; расширением на 4-м месте – вектор
(
)
0,31,32,31
; расширением на 1-м месте – вектор
(
)
31,32,31,0
.
Теорема 6.3. Пусть дана
A
G
–
(
)
nm
´
-МИ. Предположим, что о i-я
строка матрицы А доминируема (т. е. доминируема чистая стратегия i
первого игрока) и пусть дана
A
G
¢
– игра с матрицей
A
¢
, получаемой из
матрицы А вычеркиванием i-й строки. Тогда справедливы следующие
утверждения:
1.
A
A
vv
¢
=
.
2. Всякая оптимальная стратегия
*
y
игрока 2 в игре
A
G
¢
являетсяся
оптимальной и в игре
A
G
.

Страницы