Материал: Теория_игр_УП_ЭК_ЭлРесурс
16
т
.
е
.
а
ij
является
одновременно
минимумом
своей
строки
и
максимумом
своего
столбца
.
Приведем
без
доказательства
следующую
теорему
.
Теорема
1
.
Для
того
чтобы
.
min
max
max
min
ij
j
i
ij
i
j
a
a
необходимо
и
достаточно
,
чтобы
матрица
||
a
ij
||
имела
седловую
точку
.
Кроме
того
,
если
(
i
*
,
j
*
) –
седловая
точка
матрицы
||
a
ij
||,
то
.
min
max
max
min
*
*
ij
j
i
ij
i
j
j
i
a
a
a
(2.4)
Говорят
,
что
матричная
игра
имеет
седловую
точку
,
если
соответствующая
ей
матрица
выигрышей
(
платежная
матрица
)
имеет
седловую
точку
.
Пример
2.
Найти
решение
игры
G (3
х
3),
платежная
матрица
которой
имеет
следующий
вид
:
B
j
A
i
B
1
B
2
B
3
i
A
1
0 -1 -2 -2
A
2
3 2 -1 -1
A
3
6 3 0 0
j
6 3 0
Определим
ij
j
i
a
min
и
ij
i
j
a
max
и
запишем
их
в
таблицу
.
Нижняя
цена
игры
.
0
min
max
max
ij
j
i
i
i
a
Верхняя
цена
игры
.
0
max
min
min
ij
i
j
j
j
a
Так
как
=
=0,
то
платежная
матрица
и
матричная
игра
имеют
седловую
точку
.
Оптимальными
стратегиями
для
игрока
А
является
стратегия
А
3
,
а
для
игрока
В
–
В
3
.
Легко
заметить
,
что
отклонение
игрока
А
от
оптимальной
стратегии
приводит
к
уменьшению
его
выигрыша
,
а
одностороннее
отклонение
игрока
В
–
к
увеличению
его
проигрыша
.
Могут
встречаться
случаи
,
когда
платежная
матрица
имеет
несколько
седловых
точек
,
однако
это
не
изменит
характера
рекомендуемых
решений
,
поскольку
все
ситуации
равновесия
имеют
одну
и
ту
же
цену
,
а
следовательно
,
эквиваленты
.
Пример
3
.
Найти
решение
игры
G (3
х
4),
платежная
матрица
которой
имеет
вид
:
B
j
A
i
B
1
B
2
B
3
B
4
i
A
1
7 6 9 6
6
A
2
8 4 3 4 3
A
3
7 6 8 6 6
j
8
6 9 6
17
Определим
i
и
j
и
запишем
их
в
таблицу
.
Находим
нижнюю
и
верхнюю
цену
игры
:
6
max
i
i
;
6
min
j
j
.
Видно
,
что
игра
имеет
четыре
седловые
точки
с
соответствующими
парами
оптимальных
стратегий
:
А
1
В
2
;
А
1
В
4
;
А
3
В
2
и
А
3
В
4
.
Цена
игры
равна
6.
В
заключение
отметим
,
что
с
позиций
игрока
1
второй
игрок
руководствуется
принципом
минимакса
,
обеспечивающим
минимизацию
максимальных
потерь
.
Но
с
собственной
точки
зрения
игрока
2,
оценивающего
свой
выигрыш
,
он
также
руководствуется
принципом
максимина
.
Поэтому
,
как
правило
,
говорят
лишь
об
использовании
в
антагонистической
игре
принципа
максимина
обоими
игроками
.
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
Матричная
игра
является
антагонистической
,
поскольку
выигрыш
одного
игрока
равен
проигрышу
второго
(
выигрышу
второго
с
обратным
знаком
).
2.
Название
“
матричная
игра
”
произошло
из
-
за
того
,
что
такая
игра
описывает
платежной
функцией
в
виде
матрицы
.
3.
В
матричной
игре
каждый
из
игроков
делает
свой
ход
независимо
от
хода
противника
,
предполагая
лишь
,
что
противник
разумен
,
как
и
он
сам
.
4.
Оптимальной
стратегией
игрока
в
матричной
игре
называется
такая
,
которая
обеспечивает
ему
максимальный
средний
выигрыш
.
5.
Принципом
максимина
руководствуются
очень
азартные
и
рискованные
люди
(
оптимисты
).
6.
Принцип
максимина
предполагает
выбор
той
стратегии
,
при
которой
минимальный
выигрыш
для
различных
стратегий
максимален
.
7.
Стратегии
,
выбираемые
из
принципа
максимина
,
называются
максиминными
.
8.
Нижняя
цена
матричной
игры
всегда
равна
верхней
цене
.
9.
Случай
,
когда
нижняя
цена
матричной
игры
равна
верхней
цене
,
соответствует
наличию
у
платежной
матрицы
седловой
точки
.
10.
Платежная
матрица
игры
не
может
иметь
несколько
седловых
точек
.
11.
Если
платежная
матрица
игры
содержит
седловую
точку
,
то
ее
решение
сразу
находится
по
принципу
максимина
.
(
Ответы
: 1-
В
; 2-
В
; 3-
В
; 4-
В
; 5-
Н
; 6-
В
; 7-
В
; 8-
Н
; 9-
В
; 10-
Н
; 11-
В
).
ЗАДАЧИ
1.
Составьте
платежную
матрицу
игры
Морра
,
если
в
ней
участвуют
два
игрока
,
а
максимально
возможное
количество
«
выбрасываемых
»
пальцев
равно
i
(
i
=2,3,4,5,6,7,8,9,10).
Выигрыш
равен
сумме
пальцев
18
выброшенных
игроками
.
При
четной
сумме
выигрывает
первый
игрок
,
при
нечетной
–
второй
.
2.
Составьте
платежную
матрицу
игры
борьба
за
рынки
,
если
фирма
А
имеет
в
своем
распоряжение
а
условных
денежных
единиц
,
а
противник
–
в
.
а
=3,4,5,6,7,8,9,10;
а
соответствующие
в
=2,3,4,5,6,7,8,9.
3.
Найдите
седловую
точку
и
максиминные
стратегии
игроков
для
следующих
матричных
игр
:
3.1. 3
7 5 3.2.
3 6
1 8
3
8 4 3 4
4 9
1
8 3 6 8
5 9
2
1 9 7 2
3 5
3.3. 4
7 4 8 3 3.4.
5
9 7
7
6
5
6
9
5
10
6
9
9
6
8
8
3
10
5
5
7 3 4 3 4
3 11
4
8
2
3
7
3.5. 6
12
2 16
3.6.
7 13
3 17
6
8 8 18
7 9
9 19
1
2
16 10 18 15 17
11 19
1
4
4 6 10 15 5 7 11
3.7. 3
5 9 3.8.
3 5
6 4
4
7 8 4 8
4 3
2
1 5 6 8
5 5
2 7
4 2
3.9. 4 6 3.10. 1 3 8 4 2
5 2
8 5 5 9 11
8 7
8 3 6 7 2
3 1
3.11.
3 6 2 3 5
5 7 3 2 4
19
2.3.
Чистые
и
смешанные
стратегии
Если
в
игре
каждый
из
противников
применяет
только
одну
и
ту
же
стратегию
,
то
про
саму
игру
в
этом
случае
говорят
,
что
она
происходит
в
чистых
стратегиях
,
а
используемые
игроком
А
и
игроком
В
пара
стратегий
называются
чистыми
стратегиями
.
Определение
.
В
антагонистической
игре
пара
стратегий
(
А
i
,
В
j
)
называется
равновесной
или
устойчивой
,
если
ни
одному
из
игроков
не
выгодно
отходить
от
своей
стратегии
.
Применять
чистые
стратегии
имеет
смысл
тогда
,
когда
игроки
А
и
В
располагают
сведениями
о
действиях
друг
друга
и
достигнутых
результатах
.
Если
допустим
,
что
хотя
бы
одна
из
сторон
не
знает
о
поведении
противника
,
то
идея
равновесия
нарушается
,
и
игра
ведется
бессистемно
.
В
рассмотренном
в
§2.2
примере
1
максиминные
чистые
стратегии
А
4
и
В
5
неустойчивы
по
отношению
к
информации
о
поведении
противника
;
они
не
обладают
свойством
равновесия
.
Действительно
,
предположим
,
что
мы
узнали
,
что
противник
придерживается
стратегии
В
3
.
Используя
эту
информацию
,
выберем
стратегию
А
1
и
получим
больший
выигрыш
,
равный
7.
Но
если
противник
узнал
,
что
наша
стратегия
А
1
,
он
выберет
стратегию
В
4
,
сведя
наш
выигрыш
к
4.
Таким
образом
,
в
рассмотренном
примере
максиминные
чистые
стратегии
оказались
неустойчивы
по
отношению
к
информации
о
поведении
другой
стороны
.
Но
это
не
всегда
так
.
Рассмотрим
матричную
игру
G
(3
х
4),
платежная
матрица
которой
приведена
на
рис
2.3.
B
j
A
i
B
1
B
2
B
3
B
4
i
A
1
5 7 10 8 5
A
2
10 9 11 10 9
A
3
8 6 7 4 4
j
10
9 11 10
Рис
. 2.3.
В
этом
примере
нижняя
цена
игры
равна
верхней
:
=
=9,
т
.
е
.
игра
имеет
седловую
точку
.
Оказывается
,
что
в
этом
случае
максиминные
стратегии
А
2
и
В
2
будут
устойчивыми
по
отношению
к
информации
о
поведении
противника
.
Действительно
,
пусть
игрок
А
узнал
,
что
противник
применяет
стратегию
В
2
.
Но
и
в
этом
случае
игрок
А
будет
по
-
прежнему
придерживаться
стратегии
А
2
,
потому
что
любое
отступление
от
стратегии
А
2
только
уменьшит
выигрыш
.
Равным
образом
,
информация
,
полученная
игроком
В
,
не
заставит
его
отступить
от
своей
стратегии
В
2
.
20
Пара
стратегий
А
2
и
В
2
обладает
свойством
устойчивости
,
а
выигрыш
(
в
рассматриваемом
примере
он
равен
9),
достигаемый
при
этой
паре
стратегий
,
оказывается
седловой
точкой
платежной
матрицы
.
Признак
устойчивости
(
равновесности
)
пары
стратегии
–
это
равенство
нижней
и
верхней
цены
игры
.
Стратегии
А
i
и
В
j
(
в
рассматриваемом
примере
А
2
,
В
2
),
при
котором
выполняется
равенство
нижней
и
верхней
цены
игры
,
называются
оптимальными
чистыми
стратегиями
,
а
их
совокупность
–
решением
игры
.
Про
саму
игру
в
этом
случае
говорят
,
что
она
решается
в
чистых
стратегиях
.
Величина
,
(2.5)
называется
ценой
игры
.
Если
0,
то
игра
выгодна
для
игрока
А
,
если
0 –
для
игрока
В
;
при
=0
игра
справедлива
,
т
.
е
.
является
одинаково
выгодной
для
обоих
участников
.
Однако
наличие
седловой
точки
в
игре
–
это
далеко
не
правило
,
скорее
–
исключение
.
Большинство
матричных
игр
,
не
имеет
седловой
точки
,
а
следовательно
,
не
имеет
оптимальных
чистых
стратегий
.
Впрочем
,
есть
разновидность
игр
,
которые
всегда
имеют
седловую
точку
и
,
значит
,
решаются
в
чистых
стратегиях
.
Это
–
игры
с
полной
информацией
.
Теорема
2.
Каждая
игра
с
полной
информацией
имеет
седловую
точку
,
а
следовательно
,
решается
в
чистых
стратегиях
,
т
.
е
.
имеется
пара
оптимальных
чистых
стратегий
,
дающая
устойчивый
выигрыш
,
равный
.
Если
такая
игра
состоит
только
из
личных
ходов
,
то
при
применении
каждым
игроком
своей
оптимальной
чистой
стратегии
она
должна
кончаться
выигрышем
,
равным
цене
игры
.
Скажем
,
шахматная
игра
,
как
игра
с
полной
информацией
,
либо
всегда
кончается
выигрышем
белых
,
либо
всегда
–
выигрышем
черных
,
либо
всегда
–
ничьей
(
только
чем
именно
–
мы
пока
не
знаем
,
так
как
число
возможных
стратегий
в
шахматной
игре
огромно
).
Если
матрица
игры
содержит
седловую
точку
,
то
ее
решение
сразу
находится
по
принципу
максимина
.
Возникает
вопрос
:
как
найти
решение
игры
,
платежная
матрица
которой
не
имеет
седловой
точки
?
Применение
максиминного
принципа
каждым
из
игроков
обеспечивает
игроку
А
выигрыш
не
менее
,
игроку
–
проигрыш
не
больше
.
Учитывая
что
,
естественно
для
игрока
А
желание
увеличить
выигрыш
,
а
для
игрока
В
–
уменьшить
проигрыш
.
Поиск
такого
решения
производит
к
необходимости
применять
смешанные
стратегии
:
чередовать
чистые
стратегии
с
какими
-
то
частотами
.
Определение
.
Случайная
величина
,
значениями
которой
являются
чистые
стратегии
игрока
,
называется
его
смешанной
стратегией
.
Таким
образом
,
задание
смешанной
стратегии
игрока
состоит
в
указании
тех
вероятностей
,
с
которыми
выбираются
его
чистые
стратегии
.
Будем
обозначать
смешанные
стратегии
игроков
А
и
В
соответственно