Материал: Теория_игр_УП_ЭК_ЭлРесурс
21
S
A
= | | p
1
, p
2
, . . . , p
m
| | ,
S
B
= | | q
1
, q
2
, . . . , q
n
| | ,
где
p
i
–
вероятность
применения
игроком
А
чистой
стратегии
А
і
;
p
i
i
m
1
1
;
q
j
–
вероятность
применения
игроком
В
чистой
стратегии
B
j
;
q
j
j
n
1
1
.
В
частном
случае
,
когда
все
вероятности
,
кроме
одной
,
равны
нулю
,
а
эта
одна
–
единице
,
смешанная
стратегия
превращается
в
чистую
.
Применение
смешанных
стратегий
осуществляется
,
например
,
таким
образом
:
игра
повторяется
много
раз
,
но
в
каждой
партии
игрок
применяет
различные
чистые
стратегии
с
относительными
частотами
их
применения
,
равными
p
i
и
q
j
.
Смешанные
стратегии
в
теории
игр
представляют
собой
модель
изменчивой
,
гибкой
тактики
,
когда
ни
один
из
игроков
не
знает
,
какую
чистую
стратегию
выберет
противник
в
данной
партии
.
Если
игрок
А
применяет
смешанную
стратегию
S
A
= | | p
1
, p
2
, . . . ,
p
m
| | ,
а
игрок
В
смешанную
стратегию
S
B
= | | q
1
, q
2
, . . . , q
n
| | ,
то
средний
выигрыш
(
математическое
ожидание
)
игрока
А
определяется
соотношением
aijp q
j
n
i
j
i
m
1
1
. (2.6)
Естественно
,
что
ожидаемый
проигрыш
игрока
В
равен
такой
же
величине
.
Итак
,
если
матричная
игра
не
имеет
седловой
точки
,
то
игрок
должен
использовать
оптимальную
смешанную
стратегию
,
которая
обеспечит
максимальный
выигрыш
.
Естественно
возникает
вопрос
:
какими
соображениями
нужно
руководствоваться
при
выборе
смешанных
стратегий
?
Оказывается
принцип
максимина
сохраняет
свое
значение
и
в
этом
случае
.
Кроме
того
,
важное
значение
для
понимания
решения
игр
,
играют
основные
теоремы
теории
игр
.
2.4.
Основные
теоремы
матричных
игр
Если
игрок
А
выбирает
смешанную
стратегию
S
A
= | | p
1
, p
2
, . . . ,
p
m
| | ,
а
игрок
В
смешанную
стратегию
S
B
= | | q
1
, q
2
, . . . , q
n
| | ,
то
средний
выигрыш
математическое
ожидание
выигрыша
игрока
А
(
проигрыша
игрока
В
)
определится
суммой
aijp q
j
n
i
j
i
m
1
1
,
которая
может
рассматриваться
в
качестве
характеристики
выбранных
S
А
и
S
B
.
Формируя
свою
стратегию
S
А
в
антагонистической
игре
,
игрок
А
в
соответствии
с
принципом
максимина
должен
выбрать
такую
стратегию
,
при
которой
минимально
возможный
выигрыш
был
бы
максимален
,
т
.
е
.
такую
стратегию
,
которая
обеспечивает
22
m
i
A
j
i
j
ij
j
i
v
q
p
a
n
1
1
.
min
max
(2.7)
Аналогичные
рассуждения
,
связанные
с
поиском
оптимальной
смешанной
стратегии
игрока
В
,
приводят
к
рекомендации
выбрать
такую
стратегию
S
B
,
которая
обеспечивает
m
i
B
j
i
j
ij
i
j
v
q
p
a
n
1
1
max
min
. (2.8)
Весьма
важным
для
теории
и
практики
является
вопрос
о
том
,
связаны
ли
между
собой
v
А
и
v
B
.
Ответ
на
него
дает
теорема
о
максимине
.
Теорема
о
максимине
.
В
конечной
игре
двух
игроков
(
коалиций
)
с
нулевой
суммой
(
матричной
игре
)
при
имеет
место
равенство
B
A
. (2.9)
Теорема
о
максимине
указывает
на
существование
равновесия
для
случая
v
А
=
v
B
,
п р и
и
,
следовательно
,
существования
оптимальных
смешанных
стратегий
.
Поэтому
другая
формулировка
теоремы
о
максимине
,
называемая
основной
теоремой
матричных
игр
определяется
следующим
образом
.
Основная
теорема
матричных
игр
.
Любая
матричная
игра
имеет
,
по
крайней
мере
,
одно
оптимальное
решение
,
в
общем
случае
,
в
смешанных
стратегиях
и
соответствующую
цену
v .
Обе
эти
теоремы
эквивалентны
.
Из
этих
теорем
следует
,
что
любая
матричная
игра
имеет
цену
v
.
Цена
игры
v –
средний
выигрыш
,
приходящийся
на
одну
партию
, –
всегда
удовлетворяет
условию
, (2.10)
т
.
е
.
лежит
между
нижней
и
верхней
ценами
игры
.
Оптимальное
решение
игры
в
смешанных
стратегиях
,
также
как
и
решение
в
чистых
стратегиях
,
обладает
тем
свойством
,
что
каждый
из
игроков
не
заинтересован
в
отходе
от
своей
оптимальной
смешанной
стратегии
,
если
его
противник
применяет
свою
оптимальную
смешанную
стратегию
,
так
как
это
ему
невыгодно
.
Эта
пара
стратегий
образует
в
игре
положение
равновесия
:
один
игрок
хочет
обратить
выигрыш
в
максимум
,
другой
–
в
минимум
,
каждый
“
тянет
”
в
свою
сторону
и
,
при
оптимальном
поведение
обоих
,
устанавливается
равновесие
и
устойчивый
выигрыш
.
Определение
.
Те
из
чистых
стратегий
игроков
А
и
В
,
которые
входят
в
их
оптимальные
смешанные
стратегии
с
вероятностями
,
не
равными
нулю
,
называются
активными
стратегиями
.
Существует
теорема
об
активных
стратегиях
,
применение
которой
позволяет
упрощать
решение
некоторых
матричных
игр
.
Теорема
об
активных
стратегиях
.
Если
один
из
участников
матричной
игры
G
(
m
x
n
),
придерживается
своей
оптимальной
смешанной
стратегии
,
то
это
обеспечивает
ему
максимальный
средний
выигрыш
,
равный
цене
игры
,
независимо
от
того
,
какие
действия
предпринимает
другой
игрок
,
если
только
он
не
выходит
за
пределы
своих
активных
стратегий
(
т
.
е
.
пользуется
любой
из
них
в
чистом
виде
или
смешивает
их
в
23
любых
пропорциях
),
причем
число
активных
стратегий
каждого
игрока
,
входящих
в
их
оптимальные
смешанные
стратегии
,
не
превосходит
L,
где
L = min(m, n).
Использование
данной
теоремы
позволяет
в
частности
,
упрощать
решение
матричных
игр
2
x
n
и
m
x
2
.
ТЕСТЫ
(
В
–
Верно
,
Н
–
Неверно
)
1.
В
антагонистической
игре
пара
стратегий
(
A
i
,
B
j
)
называется
равновесной
или
устойчивой
,
если
ни
одному
из
игроков
не
выгодно
отходить
от
своей
стратегии
.
2.
Стратегии
,
соответствующие
седловой
точке
платежной
матрицы
,
не
обладают
свойством
равновесия
(
устойчивости
).
3.
Игра
решается
в
чистых
стратегиях
если
платежная
матрица
имеет
седловую
точку
.
4.
Игра
решается
в
чистых
стратегиях
,
если
нижняя
цена
платежной
матрицы
равна
верхней
.
5.
Игры
с
полной
информацией
всегда
имеют
седловую
точку
.
6.
Случайная
величина
,
значениями
которой
являются
чистые
стратегии
игрока
,
называется
его
смешанной
стратегией
.
7.
Если
игрок
А
применяет
смешанную
стратегию
S
A
=||p
1
, p
2
, ..., p
m
||,
а
игрок
В
смешанную
стратегию
S
B
=||q
1
, q
2
, ..., q
n
||,
то
средний
выигрыш
игрока
А
определяется
соотношением
.
1
m
i
i
p
ij
a
8.
Если
матричная
игра
не
имеет
седловой
точки
,
то
игроки
должны
использовать
оптимальные
смешанные
стратегии
.
9.
Оптимальные
смешанные
стратегии
в
отличие
от
оптимальных
чистых
стратегий
не
обладают
свойством
равновесия
(
устойчивости
).
10.
Те
из
чистых
стратегий
игроков
,
которые
входят
в
их
оптимальные
смешанные
стратегии
с
вероятностями
,
не
равными
нулю
,
называются
активными
стратегиями
.
11.
Любая
,
матричная
игра
имеет
по
крайней
мере
,
одно
оптимальное
решение
,
в
общем
случае
,
в
смешанных
стратегиях
и
соответствующую
цену
.
12.
Теорема
о
максимине
утверждает
,
что
maxmin
min max
i
j
ij
j
i
j
j
i
ij
j
i
j
i
i
a p q
a p q
v
n
n
m
m
1
1
1
1
.
13.
При
оптимальных
смешанных
стратегиях
цена
игры
удовлетворяет
условию
.
14.
Теорема
об
активных
стратегиях
утверждает
,
что
если
игрок
придерживается
свой
оптимальной
смешанной
стратегии
,
то
это
обеспечивает
ему
максимальный
средний
выигрыш
,
независимо
от
того
,
какие
действия
предпринимает
другой
игрок
,
если
только
тот
не
выходит
за
пределы
своих
активных
стратегий
.
(
Ответы
: 1-
В
; 2-
Н
; 3-
В
; 4-
В
; 5-
В
; 6-
В
; 7-
Н
; 8-
В
; 9-
Н
; 10-
В
; 11-
В
; 12-
В
; 13-
В
; 14-
В
).
24
2.5.
Решение
матричной
игры
(2
х
2)
Пусть
матричная
игра
G (2x2)
имеет
платежную
матрицу
B
j
A
i
B
1
B
2
A
1
a
11
a
12
A
2
a
21
a
22
Предположим
,
что
игра
не
имеет
седловой
точки
,
т
.
е
.
.
При
наличии
седловой
точки
решение
очевидно
.
В
соответствии
с
основной
теоремой
игра
имеет
оптимальное
решение
в
смешанных
стратегиях
: S
A
= | | p
1
, p
2
| |
и
S
B
= | | q
1
, q
2
| | ,
где
вероятности
применения
(
относительные
частоты
применения
)
чистых
стратегий
удовлетворяют
соотношениям
1
2
1
p
p
; (2.11)
1
2
1
q
q
. (2.12)
В
соответствии
с
теоремой
об
активных
стратегиях
,
оптимальная
смешанная
стратегия
обладает
тем
свойством
,
что
обеспечивает
игроку
максимальный
средний
выигрыш
,
равный
цене
игры
,
независимо
от
того
,
какие
действия
предпринимает
другой
игрок
,
если
тот
не
выходит
за
пределы
своих
активных
стратегий
.
В
частности
,
если
игрок
А
использует
свою
оптимальную
смешанную
стратегию
,
а
игрок
В
–
свою
чистую
активную
стратегию
В
1
,
то
цена
игры
равна
2
21
1
11
p
a
p
a
, (2.13)
а
при
использовании
игроком
В
чистой
активной
стратегии
В
2
,
выигрыш
будет
равен
2
22
1
12
p
a
p
a
. (2.14)
Уравнения
(2.11), (2.13)
и
(2.14)
образуют
систему
трех
линейных
алгебраических
уравнений
с
тремя
неизвестным
:
р
1
,
р
2
и
.
Решая
ее
,
легко
находим
,
что
12
21
22
11
21
22
1
a
a
a
a
a
a
p
. (2.15)
p
a
a
a
a
a
a
2
11
12
11
22
21
12
. (2.16)
a a
a a
a
a
a
a
11 22
12 21
11
22
21
12
. (2.17)
Если
игрок
В
использует
свою
оптимальную
смешанную
стартегию
,
а
игрок
А
–
свою
чистую
активную
стратегию
А
1
,
то
цена
игры
равна
2
12
1
11
q
a
q
a
, (2.18)
а
при
использовании
игроком
А
чистой
активной
стратегии
А
2
,
выигрыш
будет
равен
2
22
1
21
q
a
q
a
. (2.19)
25
Уравнения
(2.12), (2.18)
и
(2.19)
образует
систему
трех
линейных
алгебраических
уравнений
с
тремя
неизвестными
: q
1
; q
2
и
.
Решая
ее
,
легко
находим
,
что
q
a
a
a
a
a
a
1
22
12
11
22
21
12
. (2.20)
q
a
a
a
a
a
a
2
11
21
11
22
21
12
. (2.21)
a a
a a
a
a
a
a
11 22
12 21
11
22
21
12
. (2.22)
Естественно
,
что
в
обоих
случаях
цена
игры
(
выражения
(2.17)
и
(2.22))
получилась
одна
и
та
же
.
Чтобы
соотношения
(2.15), (2.16), (2.17), (2.20), (2.21), (2.22)
имели
смысл
,
необходимо
потребовать
,
чтобы
,
0
;
0
;
0
;
0
21
11
12
22
12
11
21
22
a
a
a
a
a
a
a
a
или
.
0
;
0
;
0
;
0
21
11
12
22
12
11
21
22
a
a
a
a
a
a
a
a
Тогда
0<p
1
<1; 0<p
2
<1; 0<q
1
<1; 0<q
2
<1.
Нетрудно
заметить
,
что
в
этих
неравенствах
отражено
предположение
об
отсутствии
в
рассматриваемой
игре
седловой
точки
.
Действительно
,
ни
один
из
четырех
выигрышей
а
11
,
а
12
,
а
21
,
а
22
не
может
удовлетворить
этим
неравенствам
,
будучи
минимальным
в
своей
строке
и
максимальным
в
своем
столбце
.
Решения
системы
уравнений
(2.15), (2.16), (2.17)
и
(2.20), (2.21),
(2.22),
полученные
алгебраическим
методом
,
удобно
получать
и
графическим
методом
(
рис
. 2.4).
Для
нахождения
вероятностей
р
1
,
р
2
и
цены
игры
v
в
прямоугольной
системе
координат
по
оси
абсцисс
откладывается
вероятность
р
1
[0,1],
а
по
оси
ординат
–
соответствующие
этой
вероятности
–
выигрыши
игрока
А
.
При
р
1
=0,
игрок
А
применяет
чистую
стратегию
А
2
.
Если
при
этом
игрок
В
применяет
чистую
стратегию
В
1
,
то
выигрыш
игрока
А
равен
а
21
(
уравнение
(2.13)),
а
если
игрок
В
применяет
чистую
стратегию
В
2
,
то
выигрыш
игрока
А
равен
а
22
[
уравнение
(2.14)].
При
р
1
=1,
игрок
А
применяет
чистую
стратегию
А
1
.