Составители:
Рубрика:
48 49
3. Если
*
x
– произвольная оптимальная стратегия игрока 1 в игре
A
G
¢
и
*
i
x
– расширение стратегии
*
x
на i-м месте, то о
*
i
x
– оптимальная
стратегия этого игрока в игре
A
G
.
4. Если i-я строка матрицы А строго доминируема, то оптимальная
стратегия
*
x
игрока 1 в игре
A
G
может быть получена из оптимальной
стратегии
*
x
в игре
A
G
¢
расширением на i-м месте.
Сформулируем теорему о доминировании для второго игрока.
Теорема 6.4. Пусть дана
A
G
–
(
)
nm
´
-МИ. Предположим, что о j-й
столбец матрицы А доминируем и пусть дана
A
G
¢
– игра с матрицей
A
¢
,
получаемой из матрицы А вычеркиванием j-го столбца. Тогда
справедливы следующие утверждения:
1.
A
A
vv
¢
=
.
2. Всякая оптимальная стратегия
*
x
игрока 1 в игре
A
G
¢
являетсяся
оптимальной и в игре
A
G
.
3. Если
*
y
– произвольная оптимальная стратегия игрока 2 в игре
A
G
¢
и
*
j
y
– расширение стратегии
*
y
на j-м месте, то о
*
j
y
– оптимальная
стратегия этого игрока в игре
A
G
.
4. Далее, если j-й столбец матрицы А строго доминируем, то
оптимальная стратегия
*
y
игрока 2 в игре
A
G
может быть получена из
оптимальной стратегии
*
y
в игре
A
G
¢
расширением на j-м месте.
Обобщим полученные результаты. Теоремы 5.3–5.4 дают алгоритм
понижения размерности матрицы игры. Так, если строка (столбец) мат-
рицы не больше (не меньше) некоторой выпуклой линейной комбина-
ции остальных строк (столбцов) этой матрицы, то для нахождения ре-
шения игры можно эту строку (столбец) вычеркнуть. При этом соответ-
ствующее расширение оптимальных стратегий в игре с усеченной мат-
рицей даст оптимальное решение исходной игры. Если неравенства вы-
полнялись как строгие, то множество оптимальных стратегий в перво-
начальной игре можно получить расширением множества оптимальных
стратегий усеченной игры, в противном случае при такой процедуре
оптимальные стратегии можно потерять.
Пример 6.7. Рассматривается игра с матрицей
.
6030
0213
3132
0112
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
=A
Так как каждое значение 3-й строки
3
a
превосходит соот-
ветствующее значение первой
(
)
13
aa
³
, то, вычеркивая первую строку,,
получаем
.
6030
0213
3132
1
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=A
В этой матрице каждое значение 3-го столбца
3
a
не превосходит
соответствующее значение 1-го столбца
1
a
. Поэтому получаем
.
603
021
313
2
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=A
В последней матрице никакая строка (столбец) не доминируется
другой строкой (столбцом). Вместе с тем 1-й столбец
1
a
превосходит
выпуклую линейную комбинацию столбцов
2
a
и
3
a
, так какак
321
2121 aaa +³
, поскольку
,321213
×
+
>
,0212211
×
+
×
=
6212103
×
+
×
=
. Исключая 1-й столбец, получаем
.
60
02
31
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
В этой матрице 1-я строка эквивалентна смешанной стратегии
(
)
21,21,0
=
x
, поскольку
2162103,2102211
×
+
×
=
×
+
×
=
. Таким
образом, исключая 1-ю строку, получаем матрицу
.
60
02
÷
÷
ø
ö
ç
ç
è
æ
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
