Решение игр в смешанных стратегиях.
Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. Так, в примере 1 α ≠ β
, седловая точка отсутствует. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.
Смешанной стратегией
SA
игрока А
называется применение чистых стратегий A1
, A2
, ..., Am
с вероятностями p1
, p2
, ..., pi
, ..., pm
причем сумма вероятностей равна 1:
Смешанные стратегии игрока А
записываются в виде матрицы
или в виде строки SA
= (p1
, p2
, ..., pi
, ..., pm
)
Аналогично смешанные стратегии игрока В
обозначаются:
 , или, SB
= (q1
, q2
, ..., qi
, ..., qn
),
где сумма вероятностей появления стратегий равна 1:
Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1
соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение
(или решение
) игры: это пара оптимальных стратегий S*
A
, S*
B
в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры v
. Цена игры удовлетворяет неравенству:
α ≤ v ≤ β
где α
и β
— нижняя и верхняя цены игры. Справедлива следующая основная теорема теории игр — теорема Неймана
. Каждая конечная игра имеет по крайней мере одно оптимальное решение
, возможно, среди смешанных стратегий
. Пусть S*
A
= (p*
1
, p*
2
, ..., p*
i
, ..., p*
m
)
и S*
B
= (q*
1
, q*
2
, ..., q*
i
, ..., q*
n
)
— пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.
Справедлива теорема
об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v
, если второй игрок не выходит за пределы своих активных стратегий
.
Эта теорема имеет большое практическое значение
— она дает конкретные модели нахождения оптимальных стратегий при отсутствии седловой точки.
Рассмотрим игру размера 2×2
, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение — это пара чистых стратегий, соответствующих этой точке.
Игра, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий
S*
A
= (p*
1,
p*
2
)
и S*
B
= (q*
1
, q*
2
).
Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если игрок А
придерживается своей оптимальной стратегии S'A
, то его средний выигрыш будет равен цене игры v
, какой бы активной стратегией ни пользовался игрок В
. Для игры 2×2
любая чистая стратегия противника является активной, если отсутствует седловая точка. Выигрыш игрока А
(проигрыш игрока В
) — случайная величина, математическое ожидание (среднее значение) которой является ценой игры. Поэтому средний выигрыш игрока А
(оптимальная стратегия) будет равен v
и для 1
-й, и для 2
-й стратегии противника.
Пусть игра задана платежной матрицей
Средний выигрыш игрока А
, если он использует оптимальную смешанную стратегию
 ,
а игрок В
— чистую стратегию B1
(это соответствует 1
-му столбцу платежной матрицы Р
), равен цене игры v
: a11
p*
1
+ a21 p*
2
= v
. Тот же средний выигрыш получает игрок А
, если 2
-й игрок применяет стратегию B2
, т.е. a12
p*
1
+ a22
p*
2
= v
. Учитывая, что p*
1
+ p*
2
= 1
, получаем систему уравнений для определения оптимальной стратегии S'A
и цены игры v
:
Решая эту систему, получим оптимальную стратегию
и цену игры
Применяя теорему об активных стратегиях при отыскании S*
B
- оптимальной стратегии игрока В
, получаем, что при любой чистой стратегии игрока А
(А1
или А2
) средний проигрыш игрока В
равен цене игры v
, т.е.
Тогда оптимальная стратегия определяется формулами:
Пример 1.
Игра «поиск»
Игрок А
может спрятаться в одном из двух убежищ (I
и II
); игрок В
ищет игрока А
, и если найдет, то получает штраф 1
ден. ед. от А
, в противном случае платит игроку А 1
ден. ед. Необходимо построить платежную матрицу игры.
Решение
. Для составления платежной матрицы следует проанализировать поведение каждого из игроков. Игрок А
может спрятаться в убежище I
– обозначим эту стратегию через A1
или в убежище II
— стратегия A2
.
Игрок В
может искать первого игрока в убежище I
— стратегия B1
, либо в убежище II
— стратегия B2
. Если игрок А
находится в убежище I
и там его обнаруживает игрок В
, т.е. осуществляется пара стратегий (A1
, B1
),
то игрок А
платит штраф, т.е. a11
= - 1
. Аналогично получаем a22
= - 1 (A2
, B2
)
. Очевидно, что стратегии (A1
, B2
) и (A2
, B1
) дают игроку А
выигрыш 1
, поэтому a12
= a21
=
1. Таким образом, для игры "поиск" размера 2×2
получаем платежную матрицу
Применим полученные результаты для отыскания оптимальных стратегий для игры, рассмотренной в примере 1.
Пример 2.
Найти оптимальные стратегии игры, приведенной в примере 1.
Решение
. Игра "поиск" задана платежной матрицей без седловой точки:
Поэтому ищем решение в смешанных стратегиях; для игрока А
средний выигрыш равен цене игры v
(при B1
и B2
)
; для игрока В
средний проигрыш равен цене игры v
(при A1
и B2
). Системы уравнений в данном случае имеют вид:
 
Решая эти системы, получаем 
Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью 1/2
, при этом средний выигрыш равен 0
.
РЕФЕРАТ ПО ДИСЦИПЛИНЕ «МАТЕМАТИКА»
НА ТЕМУ: «Решение игры в смешанных стратегиях».
|
