Материал: Математические методы и модели в экономике. Амелин С.В
Теорема 1. В любой матричной игре справедливо неравенство , т.е. нижняя цена игры никогда не превосходит верхнюю.
Игра с седловой точкой
Если в матричной игре нижняя и верхняя цены игры совпадают, то такая игра имеет «седловую точку» в чистых стратегиях, а число = = называют ценой игры. В этом случае решением игры, т.е. оптимальным поведением для обоих игроков являются их максиминная для игрока А и минимаксная для игрока В стратегии игры. Любое отклонение игроков от своих оптимальных стратегий не может оказаться им выгодным. Элемент платежной матрицы, отвечающий оптимальным стратегиям, называется седловой точкой.
Пример. Пусть игра задана следующей платежной матрицей:
|
В1 |
В2 |
В3 |
В4 |
i |
|
|
|
|
|
|
|
|
|
|
А1 |
9 |
3 |
8 |
2 |
2 |
|
|
|
max min - |
||||||
|
|
|
|
|
|
||
А2 |
4 |
2 |
7 |
3 |
2 |
лучшая |
|
стратегия |
|||||||
|
|
|
|
|
|
||
А3 |
6 |
4 |
7 |
8 |
4 |
для игрока |
|
|
А – (А3) |
||||||
|
|
|
|
|
|
||
А4 |
5 |
3 |
4 |
7 |
3 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
j |
9 |
4 |
8 |
8 |
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
цена игры = = = 4
min max - лучшая стратегия для игрока В – (В2)
165
Игра в смешанных стратегиях
Если платежная матрица не имеет седловой точки, то если игрок будет пользоваться смешанными стратегиями, т.е. при каждом ходе менять стратегию случайным образом, то игрок А выигрывает больше, чем , а игрок В проигрывает больше, чем .
Рассмотрим платежную матрицу (7.1). Пусть игрок А использует чистые стратегии А1, А2, … Аi,…Аm с вероятно-
m
стями p1, p2, … pi,…pm, причем pi =1, а игрок В использует
i 1
свои чистые стратегии В1, В2, … Вj,…Bn с вероятностями q1,
n
q2, … qj,… qn, причем q j = 1.
j 1
Тогда набор SA = (p1, p2, … pi,…pm) называется смешанной стратегией игрока А, а набор SB = (q1, q2, … qj,… qn) - смешанной стратегией игрока В.
Поскольку игроки выбирают свои стратегии случайным образом, то вероятность выбрать комбинацию АiВj по теории вероятности равна (Pi qj). При использовании смешанных стратегий игра становится случайной, тогда говорят о среднем значении выигрыша, который определяется платежной функцией
f(SA, SB) =
Смешанные стратегии
m |
n |
|
а ijpi q j . |
(7.2) |
|
i 1 |
j 1 |
|
S*A = ( p1* , p*2 ,… p*i … p*m ) и S*B =
( q1* , q*2 ,… q*j … q*n ) называются оптимальными, т.е. дающими
каждой стороне максимальный возможный для нее средний выигрыш (для А) или минимальный средний проигрыш (для В), если они образуют седловую точку для платежной функции (7.2), т.е. если выполняется следующее условие:
f(SA, S*B ) f( S*A , S*B ) f( S*A , SB).
166
Величина = f( S*A , SB) называется ценой игры.
Теорема 2. В смешанных стратегиях любая матричная игра имеет седловую точку, или каждая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.
Решение игры в смешанных стратегиях
Теорема 3. Для того чтобы смешанные стратегии S*A и S*B были оптимальными в игре с матрицей (7.1) и ценой игры
, необходимо и достаточно, чтобы выполнялись следующие неравенства:
m |
|
|
|
|
m |
|
аijp*i |
; j = |
1, n |
, причем p*i = 1; |
(7.3) |
||
i 1 |
|
|
|
|
i 1 |
|
n |
|
|
|
|
n |
|
а ijq*j |
; i = |
1, m |
, причем q*j = 1. |
(7.4) |
||
j 1 |
|
|
|
|
j 1 |
|
Нахождение оптимальной стратегии можно свести к решению задачи линейного программирования.
Пусть требуется найти оптимальные стратегии для игры с заданной платежной матрицей (7.1), для которой aij стро-
го больше нуля (аij >0, i=1, m ,j = 1, n ), тогда цена игры > 0. Найдем оптимальную стратегию игрока А – ( S*A ).
Разделим левую и правую части в выражении (7.3) на положительную величину :
m |
* |
|
|
|
|
|
|
|
m |
* |
|
|
|
|
|
|
а ij |
pi |
|
1; |
|
|
|
pi |
= |
|
1 |
. |
|
|
|||
|
|
|
|
|
|
|
||||||||||
i 1 |
|
|
|
|
|
|
i 1 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
p* |
|
|
|
|
|
|
|
|
|
|
||
Введем обозначение |
|
|
i |
|
= Хi, тогда |
|
|
|||||||||
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
m |
|
|
|
|
|
|
|
|
|
|
|
m |
1 |
|
||
а ij Хi 1; j = |
1, n |
; |
|
|
|
Xi = |
. |
|||||||||
|
|
|
|
|||||||||||||
i 1 |
|
|
|
|
|
|
|
|
|
|
|
i 1 |
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
167 |
|
|
|
|
|
|
|
|
|||||
Поскольку игрок А стремится сделать свой гарантированный выигрыш ( ) как можно большим ( max), то вели-
чина 1 должна быть как можно меньше ( min), тогда
имеем следующую задачу линейного программирования:
m |
|
||||
f(x) = Xi min, |
(7.5) |
||||
i 1 |
|
||||
m |
|
||||
а ij Хi 1; j = |
1, n |
, |
(7.6) |
||
i 1 |
|
||||
|
|
|
|
||
Хi 0; i = 1, m . |
(7.7) |
||||
Если Х* = ( X1* , X*2 ,… X*i … X*m ) – оптимальный план задачи (7.5) – (7.7), а минимум функции f(x) = f(x*) = f*, то цена игры при
этом составит = |
1 |
, а т.к. |
p*i |
= Хi, тогда S*A = ( X1* ,… X*m ) = |
|
f * |
|
||||
|
|
|
( p1* ,… p*m ) – оптимальная смешанная стратегия игрока А.
Для игрока В используя выражение (7.4), получим
n
g(y) = y j max.
j 1
n
а ij yj 1, i = 1, m .
j 1
yj 0; j = 1, n .
Решение игры = 1 ; g(Y*)
S*B = ( y1* ,… y*n ) = ( q1* ,… q*n ).
Пример. Найти оптимальные смешанные стратегии игры, заданной следующей платежной матрицей:
168
|
В1 |
В2 |
В3 |
А1 |
1 |
10 |
3 |
А2 |
8 |
4 |
5 |
нижняя цена игры = 4, верхняя цена игры = 5, т.е. – седловой точки нет.
Сведем данную задачу к задаче линейного программирования.
Найдем оптимальную стратегию игрока А – ( S*A ): f(x) = X1 + X2 min.
X1 + 8X2 1, 10X1 + 4X2 1,
3X1 + 5X2 1,
X1 , X2 0.
f(x) = 0,21; X1 = 0,026; X2 = 0,184,
отсюда
= |
1 |
= 4,76; |
P1 |
= 4,76 0,026 = 0,124; |
|
||||
0,21 |
||||
|
|
|
P2 |
= 4,76 0,184 = 0,876. |
Найдем оптимальную стратегию игрока В – ( S*B ): |
||||
|
|
g(y) = y1 + y2 + y3 max. |
||
|
|
y1 + 10y2 + 3y3 |
1, |
|
8y1 + 4y2 + 5y3 1, y1 , y2 , y3 0.
g(y) = 0,21; y1 = 0; y2 = 0,0526; y3 = 0,158,
отсюда
q1 = 0; q2 = 4,76 0,0526 = 0,25; q3 = 4,76 0,158 = 0,75.
169