Материал: Теория_игр_УП_ЭК_ЭлРесурс
11
В
0
В
1
В
2
В
3
В
4
А
0
1 -1 -1 -1 -1
А
1
1 1 -1 -1 -1
А
2
-1 1 1 -1 -1
А
3
-1 -1 1 1 -1
А
4
-1 -1 -1 1 1
А
5
-1 -1 -1 -1 1
Здесь
А
i
–
стратегия
фирмы
А
,
заключающаяся
в
выделении
i
условных
денежных
единиц
на
защиту
первого
рынка
;
В
j
–
стратегия
фирмы
В
,
заключающаяся
в
выделении
j
условных
денежных
единиц
на
завоевание
первого
рынка
.
Если
бы
на
защиту
или
завоевание
рынков
фирмы
могли
выделить
любое
количество
средств
из
имеющихся
,
то
игра
стала
бы
бесконечной
.
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
Всякая
конфликтная
ситуация
является
антагонистической
.
2.
Всякая
антагонистическая
ситуация
является
конфликтной
.
3.
Цель
теории
игр
–
выработка
рекомендаций
по
разумному
поведению
участников
конфликта
.
4.
Недостатком
теории
игр
является
предположение
о
полной
разумности
противников
.
5.
В
теории
игр
предполагается
,
что
не
все
возможные
стратегии
противника
известны
.
6.
Теория
игр
включает
элементы
риска
,
неизбежно
сопровождающие
разумные
решения
в
реальных
конфликтах
.
7.
В
теории
игр
нахождение
оптимальной
стратегии
осуществляется
по
многим
критериям
.
8.
Стратегические
игры
состоят
только
из
личных
ходов
.
9.
В
парной
игре
число
стратегий
каждого
участника
равно
двум
.
10.
Игры
,
в
которых
действия
игроков
направлены
на
максимизацию
выигрышей
коалиций
без
последующего
их
разделения
между
игроками
,
называются
коалиционными
.
11.
Исходом
кооперативной
игры
является
дележ
выигрыша
коалиции
,
который
возникает
не
как
следствие
тех
или
иных
действий
игроков
,
а
как
результат
их
наперед
определенных
соглашений
.
12.
По
виду
описания
игры
делятся
на
игры
с
полной
информацией
или
игры
с
неполной
информацией
.
13.
Конечная
множественная
игра
с
нулевой
суммой
называется
матричной
.
14.
Конечная
парная
игра
с
нулевой
суммой
называется
биматричной
игрой
.
(
Ответы
:
1-
Н
; 2-
В
; 3-
В
; 4-
В
; 5-
Н
; 6-
Н
; 7-
Н
; 8-
Н
; 9-
Н
; 10-
В
; 11-
В
; 12-
Н
; 13-
Н
; 14-
Н
).
12
2.
МАТРИЧНЫЕ
ИГРЫ
2.1.
Описание
матричной
игры
Наиболее
разработанной
в
теории
игр
является
конечная
парная
игра
с
нулевой
суммой
(
антагонистическая
игра
двух
лиц
или
двух
коалиций
),
называемая
матричной
игрой
.
Рассмотрим
такую
игру
G
,
в
которой
участвуют
два
игрока
А
и
В
,
имеющие
антагонистические
интересы
:
выигрыш
одного
игрока
равен
проигрышу
второго
.
Так
как
выигрыш
игрока
А
равен
выигрышу
игрока
В
с
обратным
знаком
,
можем
интересоваться
только
выигрышем
а
игрока
А
.
Естественно
,
игрок
А
хочет
максимизировать
а
,
а
игрок
В
–
минимизировать
а
.
Для
простаты
отождествим
себя
мысленно
с
одним
из
игроков
(
пусть
это
будет
игрок
А
),
тогда
будем
называть
игрока
В
–
“
противник
” (
разумеется
,
каких
-
то
реальных
преимуществ
для
А
из
этого
не
вытекает
).
Пусть
у
игрока
А
имеется
m
возможных
стратегий
А
1
,
А
2
, ...,
А
m
,
а
у
противника
–
n
возможных
стратегий
В
1
,
В
2
, ...,
B
n
(
такая
игра
называется
игрой
m
х
n
).
Обозначим
через
a
ij
выигрыш
игрока
А
,
в
случае
,
если
он
воспользуется
стратегией
А
i
,
а
игрок
В
–
стратегией
В
j
.
Предполагается
,
что
выигрыш
a
ij
известен
.
Тогда
мы
можем
составить
прямоугольную
таблицу
(
матрицу
),
в
которой
перечислены
стратегии
игроков
и
соответствующие
выигрыши
(
рис
. 2.1).
B
j
A
i
B
1
B
2
...
B
n
A
1
a
11
a
12
... a
1n
A
2
a
21
a
22
... a
2n
... ... ... ... ...
A
m
a
m1
a
m2
... a
mn
Рис
. 2.1.
Если
такая
таблица
составлена
,
то
говорят
,
что
игра
G
приведено
к
матричной
форме
.
Отсюда
рассматриваемая
игра
и
получила
название
матричная
.
Само
по
себе
приведение
игры
к
такой
форме
уже
может
составить
трудную
задачу
,
а
иногда
и
невыполнимую
,
из
-
за
необозримого
множества
возможных
стратегий
игроков
и
трудности
определения
выигрышей
a
ij
.
Рассмотрим
некоторые
задачи
,
решение
которых
сводится
к
решению
матричных
игр
.
Игра
1.
Вариант
игры
«
Морра
»
Игра
состоит
в
том
,
что
каждый
из
двух
игроков
независимо
друг
от
друга
выбирает
определенную
сторону
монеты
(“
герб
”
или
“
решка
”),
затем
одновременно
называют
свой
выбор
.
Если
игроки
выбрали
одну
и
ту
же
сторону
монеты
,
то
второй
игрок
платит
первому
одну
гривну
,
если
разные
,
то
первый
платит
второму
такую
же
сумму
.
Легко
видеть
,
что
матрица
выигрышей
(
платежная
матрица
)
этой
игры
имеет
вид
13
B
j
A
i
B
1
B
2
A
1
1 -1
A
2
-1 1
Здесь
стратегии
А
1
и
В
1
–
игроки
А
и
В
выбирают
“
герб
”,
а
А
2
и
В
2
–
игроки
А
и
В
выбирают
“
решку
”.
Нетривиальность
сформулированной
задачи
,
как
и
любой
матричной
игры
,
состоит
в
том
,
что
каждый
из
игроков
делает
свой
выбор
независимо
друг
от
друга
.
Игра
2.
Борьба
за
рынки
Фирмы
А
и
В
производят
одинаковый
товар
и
в
настоящее
время
каждая
«
контролирует
» 50%
рынка
.
Улучшив
качество
товара
,
обе
фирмы
собираются
развернуть
рекламные
кампании
.
При
этом
,
приобретение
новых
покупателей
одной
фирмой
сопровождается
потерей
этих
покупателей
другой
фирмой
.
Исследование
показало
,
что
60%
потенциальных
покупателей
получают
информацию
через
телевидение
,
30% –
через
газеты
и
10% –
через
радиовещание
.
Задача
каждой
фирмы
–
выбрать
стратегию
рекламной
кампании
.
В
данной
игре
у
каждого
из
игроков
по
три
стратегии
:
А
1
,
В
1
–
рекламировать
товар
через
телевидение
;
А
2
,
В
2
–
через
газеты
;
А
3
,
В
3
–
через
радиовещание
.
Поскольку
это
игра
с
нулевой
суммой
,
то
матрицу
выигрышей
фирмы
А
можно
представить
в
следующем
виде
:
B
1
B
2
B
3
A
1
0 30 50
A
2
-30 0 20
A
3
-50 -20 0
где
a
ij
–
количество
покупателей
товара
фирмы
А
в
процентах
,
на
которое
оно
увеличивается
,
если
фирма
А
применяет
стратегию
А
i
,
а
фирма
В
–
стратегию
В
j
.
2.2.
Принцип
максимина
в
антагонистических
играх
.
Седловая
точка
Как
отмечалось
,
важнейшим
вопросом
в
теории
игр
(
в
том
числе
и
матричных
)
является
вопрос
о
выборе
оптимальных
стратегий
для
каждого
из
игроков
.
Оптимальной
стратегией
игрока
в
матричной
игре
называется
такая
,
которая
обеспечивает
ему
максимальный
выигрыш
.
Если
игра
14
повторяется
неоднократно
,
то
оптимальная
стратегия
должна
обеспечивать
максимальный
средний
выигрыш
.
При
выборе
этой
стратегии
основой
рассуждений
является
предположение
,
что
противник
является
,
по
меньшей
мере
,
так
же
разумен
,
как
и
мы
сами
и
делает
все
,
чтобы
добиться
такой
же
цели
.
Расчет
на
разумного
противника
–
лишь
одна
из
возможных
позиций
в
конфликте
,
но
в
теории
игр
именно
она
кладется
в
основу
.
При
этом
для
выбора
оптимальной
стратегии
используют
принцип
максимина
:
выбирай
ту
стратегию
,
чтобы
при
наихудшем
для
нас
поведении
противника
получить
максимальный
выигрыш
.
Другими
словами
,
принцип
максимина
предполагает
выбор
той
стратегии
,
при
которой
наш
минимальный
выигрыш
для
различных
стратегий
максимален
.
Отсюда
и
название
«
принцип
максимина
».
Как
видно
,
принцип
максимина
–
это
принцип
крайне
осторожного
игрока
,
но
именно
он
является
основным
принципом
теории
матричных
игр
.
Для
пояснения
принципа
максимина
рассмотрим
пример
1
матричной
игры
G (4
х
5)
с
платежной
матрицей
,
приведенной
на
рис
. 2.2.
Пример
1.
B
j
A
i
B
1
B
2
B
3
B
4
B
5
i
A
1
5 6 7
4 5 4
A
2
3 10 6
5 6 3
A
3
12 5
3
9 8 3
A
4
6 7 5
6 10
5
максимин
max min
i
j
a
ij
j
12 10 7 9
10
минимакс
min max
j
i
a
ij
Рис
. 2.2.
Какой
стратегией
игроку
А
воспользоваться
?
Есть
соблазнительный
выигрыш
12,
при
применении
стратегии
А
3
.
Но
при
этом
противник
может
выбрать
стратегию
В
3
,
и
игрок
А
получит
выигрыш
,
равный
всего
трем
.
Для
определения
оптимальной
стратегии
в
соответствии
с
принципом
максимина
,
запишем
в
правом
добавочном
столбце
платежной
матрицы
минимальное
значение
i
в
каждой
строке
(
минимум
строки
).
Из
всех
значений
i
(
правый
столбец
)
выделим
наибольшее
.
Ему
соответствует
стратегия
А
4
.
Выбрав
эту
стратегию
,
мы
во
всяком
случае
можем
быть
уверены
,
что
при
любом
поведении
противника
выигрыш
будет
не
менее
пяти
.
15
Эта
величина
–
наш
гарантированный
выигрыш
.
Он
называется
нижней
ценой
игры
(
или
«
максимином
» –
максимальный
из
минимальных
выигрышей
).
Будем
обозначать
его
.
В
нашем
примере
=
j
i
min
max
a
ij
=5.
Теперь
станем
на
точку
зрения
игрока
В
и
порассуждаем
за
него
.
Выбирая
стратегию
,
он
хотел
бы
отдать
поменьше
,
но
должен
рассчитывать
на
наихудшее
для
него
поведение
игрока
А
.
Припишем
к
платежной
матрице
(
рис
. 2.2)
нижнюю
строку
и
в
ней
запишем
наихудшее
для
игрока
В
возможные
результаты
(
максимумы
столбцов
j
.
Очевидно
,
осторожный
противник
должен
выбрать
стратегию
,
при
которой
величина
j
минимальна
.
Эта
величина
называется
верхней
ценой
игры
(
или
“
минимаксом
” –
минимальный
из
максимальных
проигрышей
).
Будем
обозначать
ее
.
В
нашем
примере
=
min max
j
i
a
ij
= 7.
Итак
,
исходя
из
принципа
осторожности
,
игрок
А
должен
выбрать
стратегию
А
4
,
а
его
противник
–
В
3
.
Такие
стратегии
называются
максиминными
или
минимаксными
стратегиями
(
вытекающие
из
принципа
максимина
).
До
тех
пор
,
пока
обе
стороны
в
нашем
примере
будут
придерживаться
своих
максиминных
стратегий
,
выигрыш
игрока
А
и
проигрыш
игрока
В
будет
равен
а
43
=5.
Легко
показать
,
что
нижняя
цена
игры
никогда
не
превосходит
верхней
цены
игры
.
Лемма
1
.
Пусть
задана
матрица
выигрышей
А
=
ij
и
определены
=
ij
i
j
a
max
min
и
=
ij
j
i
a
min
max
.
Тогда
.
min
max
max
min
ij
j
i
ij
i
j
a
a
.
Доказательство
.
По
определению
максимума
и
минимума
для
любых
фиксированных
значений
i
и
j
имеем
.
min
max
j
i
j
ij
ij
i
a
a
a
(2.1)
Поскольку
левая
часть
неравенства
(2.1)
не
зависит
от
i
,
то
можем
записать
.
min
max
max
j
i
j
i
ij
i
a
a
(2.2)
Так
как
правая
часть
неравенства
(2.1)
не
зависит
от
j
,
то
.
min
max
min
ij
j
ij
i
j
a
a
(2.3)
Объединяя
неравенства
(2.2)
и
(2.3),
получаем
неравенство
(2.1),
что
и
требовалось
доказать
.
Итак
,
всегда
.
Случай
=
,
соответствует
наличию
у
платежной
матрицы
так
называемой
седловой
точки
.
Определение
.
Точка
(
i
*,
j
*)
называется
седловой
точкой
платежной
матрицы
||
a
ij
||,
если
для
всех
остальных
i
и
j
этой
матрицы
выполняется
условие
a
i*j
a
i*j*
a
ij*
,