Материал: Теория_игр_УП_ЭК_ЭлРесурс
31
(
больше
или
некоторые
равны
)
соответствующих
элементов
другого
столбца
,
то
стратегия
В
i
называется
доминируемой
(
заведомо
невыгодной
).
Правило
.
Решение
матричной
игры
не
изменится
,
если
из
платежной
матрицы
исключить
строки
и
столбцы
,
соответствующие
дублирующим
и
доминируемым
стратегиям
.
Пример
.
Упростить
матричную
игру
,
платежная
матрица
которой
имеет
вид
:
B
j
A
i
B
1
B
2
B
3
B
4
B
5
A
1
5 9 3 4 5
A
2
4 7 7 9 10
A
3
4 6 3 3 9
A
4
4 8 3 4 5
A
5
4 7 7 9 10
Из
платежной
матрицы
видно
,
что
стратегия
А
2
дублирует
стратегию
А
5
,
потому
любую
из
них
можно
отбросить
(
отбросим
стратегию
А
5
).
Сравнивая
почленно
стратегии
А
1
и
А
4
,
видим
,
что
каждый
элемент
строки
А
4
не
больше
соответствующего
элемента
строки
А
1
.
Поэтому
применение
игроком
А
доминирующей
над
А
4
стратегии
А
1
всегда
обеспечивает
выигрыш
,
не
меньший
того
,
который
был
бы
получен
при
применении
стратегии
А
4
.
Следовательно
,
стратегию
А
4
можно
отбросить
.
Таким
образом
,
имеем
упрощенную
матричную
игру
с
платежной
матрицей
вида
:
B
j
A
i
B
1
B
2
B
3
B
4
B
5
A
1
5 9 3 4 5
A
2
4 7 7 9 10
A
3
4 6 3 3 9
Из
этой
матрицы
видно
,
что
в
ней
некоторые
стратегии
игрока
В
доминируют
над
другими
:
В
3
над
В
2
,
В
4
и
В
5
.
Отбрасывая
доминируемые
стратегии
В
2
,
В
4
и
В
5
,
получаем
игру
3x2,
имеющей
платежную
матрицу
вида
:
B
j
A
i
B
1
B
3
A
1
5 3
A
2
4 7
A
3
4 3
32
В
этой
матрице
стратегия
А
3
доминируется
как
стратегией
А
1
,
так
и
стратегией
А
2
.
Отбрасывая
стратегию
А
3
,
окончательно
получаем
игру
2x2
с
платежной
матрицей
:
B
j
A
i
B
1
B
3
A
1
5 3
A
2
4 7
Эту
игру
уже
упростить
нельзя
,
ее
надо
решать
рассмотренным
выше
алгебраическим
или
геометрическим
методом
.
Необходимо
отметить
,
что
отбрасывая
дублируемые
и
доминируемые
стратегии
в
игре
с
седловой
точкой
,
мы
все
равно
придем
к
игре
с
седловой
точкой
,
т
.
е
.
к
решению
в
чистых
стратегиях
.
Но
лучше
сразу
проверить
,
не
обладает
ли
игра
седловой
точкой
–
это
проще
,
чем
сравнивать
почленно
все
строки
и
все
столбцы
платежной
матрицы
.
Алгебраические
методы
решения
матричных
игр
иногда
производить
проще
,
если
использовать
также
следующие
свойства
матричных
игр
.
Свойство
1.
Если
ко
всем
элементам
платежной
матрицы
прибавить
(
вычесть
)
одно
и
тоже
число
С
,
то
оптимальные
смешанные
стратегии
игроков
не
изменятся
,
а
только
цена
игры
увеличится
(
уменьшится
)
на
это
число
С
.
Свойство
2.
Если
каждый
элемент
платежной
матрицы
умножить
на
положительное
число
k,
то
оптимальные
смешанные
стратегии
игроков
не
изменятся
,
а
цена
игры
умножится
на
k.
Отметим
,
что
эти
свойства
верны
и
для
игр
,
имеющих
седловую
точку
.
Эти
два
свойства
матричных
игр
применяются
в
следующих
случаях
:
1)
если
матрица
игры
наряду
с
положительными
имеет
и
отрицательные
элементы
,
то
ко
всем
ее
элементам
прибавляют
такое
число
,
чтобы
исключить
отрицательные
числа
в
матрице
;
2)
если
матрица
игры
имеет
дробные
числа
,
то
для
удобства
вычислений
элементы
этой
матрицы
следует
умножить
на
такое
число
,
чтобы
все
выигрыши
были
целыми
числами
.
Пример
.
Решить
матричную
игру
2
х
2
с
платежной
матрицей
вида
:
B
j
A
i
B
1
B
2
A
1
0.5 -0.2
A
2
0.1 0.3
Умножая
все
элементы
платежной
матрицы
на
10,
а
затем
прибавляя
к
ним
число
2,
получаем
игру
с
платежной
матрицей
:
33
B
j
A
i
B
1
B
2
A
1
7 0
A
2
3 5
Решая
эту
игру
алгебраическим
методом
,
получаем
9
2
0
3
5
7
3
5
1
p
;
9
7
2
p
;
9
5
0
3
5
7
0
5
1
q
;
9
4
2
q
;
9
35
0
3
5
7
3
0
5
7
v
.
В
соответствии
со
свойствами
1
и
2,
исходная
матричная
игра
имеет
те
же
оптимальные
смешанные
стратегии
:
9
7
:
9
2
A
S
и
9
4
:
9
5
B
S
.
А
для
получения
исходной
цены
игры
необходимо
из
полученной
цены
игры
вычесть
2,
а
затем
разделить
на
10.
Таким
образом
,
получаем
цену
исходной
игры
:
90
17
10
:
2
9
35
.
2.7.
Решение
игр
2xn
и
mx2
Как
уже
отмечалось
в
теореме
об
активных
стратегиях
,
любая
конечная
игра
mxn
имеет
решение
,
в
котором
число
активных
стратегий
каждого
игрока
не
превосходит
L
,
где
)
,
min(
n
m
L
.
Следовательно
,
у
игры
2xn
или
mx2
всегда
имеется
решение
содержащее
не
более
двух
активных
стратегий
у
каждого
из
игроков
)
2
)
2
,
(
min
)
,
2
(
(min
m
n
.
Если
эти
активные
стратегии
игроков
будут
найдены
,
то
игры
2xn
и
mx2
превращаются
в
игры
2x2
,
методы
решения
которых
рассмотрены
выше
.
Практически
решение
игры
2xn
осуществляется
следующим
образом
:
1)
строится
графическое
изображение
игры
для
игрока
А
;
2)
выделяется
нижняя
граница
выигрыша
и
находится
наибольшая
ордината
нижней
границы
(
максимин
),
которая
равна
цене
игры
v
;
3)
определяется
пара
стратегий
игрока
В
,
пересекающихся
в
точке
оптимума
.
Эти
стратегии
и
являются
активными
стратегиями
игрока
В
.
Таким
образом
,
игра
2xn
сведена
к
игре
2x2
,
которую
более
точно
можно
решить
алгебраическим
методом
.
Если
в
точке
оптимума
пересекается
более
двух
стратегий
,
то
в
качестве
активных
стратегий
может
быть
выбрана
любая
пара
из
них
.
Решение
игры
mx2
осуществляется
аналогично
.
Но
в
этом
случае
строится
графическое
изображение
игры
для
игрока
В
и
выделяется
не
нижняя
,
а
верхняя
граница
выигрыша
(
так
как
находится
оптимальная
смешанная
стратегия
игрока
В
)
,
и
на
ней
находится
точка
оптимума
с
наименьшей
ординатой
(
минимакс
).
Пример
.
Найти
решение
игры
,
платежная
матрица
которой
имеет
вид
:
34
B
j
A
i
B
1
B
2
B
3
A
1
2 5 8
A
2
7 4 3
Платежная
матрица
не
имеет
седловой
точки
,
поэтому
оптимальное
решение
должно
быть
в
смешанных
стратегиях
.
Строим
графическое
изображение
игры
для
игрока
А
(
рис
. 2.10).
2
4
6
8
10
10
8
6
4
2
0
0.2
0.4
0.5
0.6
0.8
3
7
5
v
A
v
A
p
1
N
B
3
B
2
B
1
Рис
. 2.10.
Точка
N
(
максимин
)
является
точкой
оптимума
.
В
этой
точке
пересекаются
линии
,
соответствующие
активным
стратегиям
В
1
и
В
2
игрока
В
.
Таким
образом
,
исключая
стратегию
В
3
,
получаем
матричную
игру
2x2
с
платежной
матрицей
вида
B
j
A
i
B
1
B
2
A
1
2 5
A
2
7 4
Используя
алгебраический
метод
решения
этой
игры
,
получаем
точное
решение
:
2
1
5
7
4
2
7
4
1
p
;
2
1
1
1
2
p
p
;
6
1
5
7
4
2
5
4
1
q
;
6
5
1
1
2
q
q
;
6
27
5
7
4
2
5
7
4
2
v
.
Ответ
:
2
1
,
2
1
A
S
;
0
,
6
5
,
6
1
B
S
;
6
27
v
.
35
Пример
.
Найти
решение
игры
,
платежная
матрица
которой
имеет
вид
:
B
j
A
i
B
1
B
2
:A
1
0 1
A
2
4 2
A
3
-1 4
A
4
1 -3
A
5
6 -2
A
6
1,5 3
Платежная
матрица
не
имеет
седловой
точки
.
Для
сведения
данной
игры
к
игре
2x2
строим
ее
графическое
изображение
для
игрока
В
(
рис
.
2.11).
Точка
М
(
минимакс
)
является
точкой
оптимума
.
В
этой
точке
пересекаются
отрезки
,
соответствующие
активным
стратегиям
А
2
,
А
6
и
А
3
игрока
А
.
Таким
образом
,
исключая
стратегии
А
1
,
А
4
и
А
5
и
выбирая
из
трех
активных
стратегий
две
(
например
,
А
2
и
А
3
или
А
2
и
А
6
),
приходим
к
матричной
игре
2x2
.
Выбор
стратегий
А
3
и
А
6
исключен
,
так
как
в
этом
случае
точка
М
перестанет
быть
точкой
минимакса
.
6
5
4
3
2
1
-1
-2
-3
6
5
4
3
2
1
-1
-2
-3
0.2
0.4
0.6
0.8
v
B
v
B
q
1
A
3
A
6
A
2
A
1
M
A
5
A
4
Рис
. 2.11.
Пусть
выбираются
стратегии
А
2
и
А
3
.
Тогда
игра
2x2
приобретает
вид
:
B
j
A
i
B
1
B
2
A
2
4 2
A
3
-1 4
Оптимальные
смешанные
стратегии
данной
игры
,
а
,
следовательно
,
и
исходной
игры
определяются
следующими
вероятностями
:
7
5
1
2
4
4
1
4
1
p
;
7
2
2
p
;
7
2
1
2
4
4
2
4
1
q
;
7
5
2
q
;
7
18
1
2
4
4
2
1
4
4
v
.
Ответ
:
0
,
0
,
0
,
7
2
,
7
5
,
0
A
S
;
7
5
,
7
2
B
S
;
7
18
v
.