Исследование операций. Теория игр. Лекция 8

1.

Исследование операций
Теория игр
Свойства оптимальных смешанных стратегий матричных игр
Теорема 1. Для матричной игры с платёжной матрицей H имеют место соотношения
n
m
I max min hij pi min max hij q j ,
j
p
q
i 1
i
j 1
причём внешние экстремумы достигаются на оптимальных смешанных стратегиях игроков.
Доказательство. По определению значения игры и теоремы фон Неймана
n
m
m
n
I max min hij pi q j min max hij pi q j ,
q
p
Имеем
n
q
i 1 j 1
m
p
j 1 i 1
n
min hij pi q j min hij pi R ( p ), p .
q
j
i 1 j 1
i 1
n
n
m
m
n
i 1
i 1
j 1
j 1
i 1
R ( p ) min h ij pi hij pi , R ( p ) R ( p )q j ( hij pi ) q j , q.
j
Отсюда
n
m
n
n
m
min hij pi q j min hij pi R ( p ) min hij pi q j .
q
j
i 1 j 1
Следовательно,
n
m
i 1 j 1
n
min hij pi q j min hij pi .
q
Окончательно,
q
i 1
j
i 1 j 1
i 1
n
m
I max min hij pi q j max min hij pi .
p
q
i 1
p
j
j 1
Аналогично доказывается второе равенство формулировки теоремы.
21.09.2011
Исаченко А.Н.
Лекция 6
1

2.

Исследование операций
Теория игр
Теорема 2. Для матричной игры с платёжной матрицей H имеют место соотношения
n
m
max min hij I min max hij .
j
i
j
i 1
i
j 1
Доказательство. По теореме 1 .
n
Аналогично
m
I max min hij pi max min hij .
j
p
n
j
i
i 1 j 1
m
I min max hij q j min max hij .
q
i
j
i 1 j 1
i
Теорема 3. Если p и q стратегии игроков, а v некоторое число, причём
m
n
max hij q j min hij pi ,
i
j
j 1
i 1
то p и q оптимальные стратегии игроков и I=v.
Доказательство. Из теоремы 1 имеем
n
m
min hij pi I max hij q j .
j
i 1
i
j 1
Из неравенства в формулировке теоремы получим
m
n
min hij q j I min hij pi .
i
19.09.2011
j
j 1
Исаченко А.Н.
i 1
Лекция 5
2

3.

Исследование операций
Теория игр
Следствие 1. Если p и q стратегии игроков, а v – число, причём
m
h q
j 1
ij
n
hij pi , i , j .
j
i 1
то p и q оптимальные стратегии и v=I.
Следствие 2. Если p и q стратегии игроков, то для их оптимальности достаточно выполнения
m
n
неравенства
max hij q j min hij pi .
i
j
j 1
i 1
Теорема 4. Каждая пара оптимальных смешанных стратегий игры с платёжной матрицей
является парой оптимальных смешанных стратегий игры с платёжной
H hij
n m
матрицей
, где k – произвольная константа.
H ' hij k
n m
Доказательство. Пусть p*,q* -пара оптимальных стратегий для игры с платёжной
матрицей H. Тогда по определению значения игры получим
n
m
I (hij k ) p q I k ,
'
* *
i j
i 1 j 1
n
(h
i 1
ij
n
k ) p hij p k ,
*
i
i 1
*
i
m
(h
j 1
ij
m
k )q hij q *j k .
*
j
j 1
Получим
m
(h
j 1
ij
k )q
*
j
n
m
(h
i 1 j 1
ij
k) p q
* *
i j
n
(h
i 1
ij
k ) pi* ,
что по следствию 1 доказывает теорему.
21.09.2011
Исаченко А.Н.
Лекция 6
3

4.

Исследование операций
Теория игр
Доминирование стратегий
Пусть конечная игра представлена платёжной матрицей H. Говорим, что для первого игрока
стратегия p’ доминирует стратегию p’’, если
n
h
ij
i 1
n
p hij pi'' , j 1, m .
'
i
i 1
Иными словами для любой чистой стратегии второго игрока выигрыш первого игрока при
применении им стратегии p’ не меньше выигрыша при применении им стратегии p’’. Если
все неравенства в системе строгие, то говорим о строгом доминировании, а при наличии
хотя бы одного равенства – о нестрогом доминировании.
Аналогично, для второго игрока стратегия q’ доминирует стратегию q’’, если
m
m
h q h q
j 1
ij
'
j
ij
j 1
''
j
, i 1, n .
При этом говорят о строгом доминировании, если все неравенства строгие, и о нестрогом
доминировании в противном случае.
В частности, чистая стратегия Ai1 первого игрока доминирует его чистую стратегию Ai2 ,
если hi j hi j , j 1, m .
Чистая стратегия второго игрока B j доминирует чистую стратегию B j , если
1
2
1
2
hij1 hij2 , i 1, n .
21.09.2011
Исаченко А.Н.
Лекция 6
4

5.

Исследование операций
Теория игр
Теорема 1. Если для первого игрока стратегия p’ доминирует стратегию p’’ и стратегия p’’
оптимальна, то стратегия p’ также оптимальна.
Доказательство. В силу доминирования выполняются неравенства
n
h
Откуда получим
n
ij
i 1
p hij pi'' , j 1, m .
'
i
i 1
n
n
min hij p min hij pi'' .
j
'
i
i 1
В силу оптимальности p
j
i 1
n
получим I min hij pi' . Поэтому p ' также оптимальна.
''
j
i 1
Аналогичное утверждение справедливо для стратегий второго игрока.
Лемма 1. Если чистая стратегия Ai первого игрока строго (нестрого) доминируется его
0
стратегией p, отличной от стратегии Ai , то для стратегии Ai0 существует строго
0
'
’
(нестрого) доминирующая стратегия p с вероятностью pi0 0 .
Доказательство. Так как стратегия p отлична от чистой стратегии Ai0 , то pi0 1 . По
вектору p составим вектор p’ с компонентами pi' 0 , pi' pi , i i0 . Очевидно p’ является
0
1 pi0
стратегией первого игрока с нулевой вероятностью применения чистой стратегии Ai0 .
Из условия строгого доминирования получим
n
1 p 0 , получим
h p' h , j .
i0
i 1
ij
i
n
n
i 1
i 1
hij pi hi0 j pi , j . Разделив обе части на
i0 j
Случай нестрогого доминирования доказывается аналогично.
21.09.2011
Исаченко А.Н.
Лекция 6
5

6.

Исследование операций
Теория игр
Теорема 2. Если чистая стратегия Ai0 первого игрока строго доминируется его стратегией
p, то Ai0 входит с нулевой вероятностью в любую оптимальную стратегию.
Если чистая стратегия Ai0 нестрого доминируется его стратегией p, отличной от стратегии
Ai0 , то существует оптимальная стратегия первого игрока, в которую Ai0 входит с
нулевой вероятностью.
Доказательство. Рассмотрим случай строгого доминирования. Пусть игра задаётся
платёжной матрицей H. Предположим, что существует оптимальная стратегия p* первого
*
игрока, причём pi0 0 . В соответствии с леммой 1 мы можем считать, что в стратегии p
Вероятность pi0 0 . В силу строгого доминирования
n
h
i 1
Получим
n
I hij pi* hij pi* ( hij pi ) pi*0 hij ( pi* pi pi*0 ) , j .
i 1
i i0
i i0
i i0
zi p pi p 0 при всех i i и
0
h z I , j,
ij i
pi' hi0 j , j .
n
i 1
Так как
ij
*
i
*
i0
n
z 1 , то положив
i 1
i
zi0 0 , получим
что противоречит оптимальности p* . Следовательно, у любой оптимальной
стратегии первого игрока p* координата
pi*0 0 .
Заменой строгих неравенств на нестрогие доказывается вторая часть теоремы.
21.09.2011
Исаченко А.Н.
Лекция 6
6

7.

Исследование операций
Теория игр
Следствие 1. Пусть игра задана платёжной матрицей H и чистая стратегия Ai0
первого
игрока доминируется некоторой его стратегией p, отличной от Ai0 . Положим, что H’ –
матрица, полученная из H отбрасыванием её строки с номером i0 и p’ стратегия
оптимальная в игре с платёжной матрицей H’. Тогда стратегия p*, полученная из p’ вставкой
нуля на место i0-ой компоненты, является оптимальной для исходной игры. Причём
значения игр совпадают.
Доказательство. Пусть q* - оптимальная стратегия второго игрока в игре с платёжной
матрицей H’. Тогда
m
n 1
h q I h
j 1
ij
*
j
'
i 1
'
ij
pi'
при всех i i0 и j. Здесь I’ – значение игры с платёжной матрицей H’. С другой стороны, так
как Ai0 доминируется p, то
Далее
m
m
j 1
j 1 i i0
m
hij q*j ( hij pi )q*j pi hij q*j pi I ' I ' , i .
i i0
j 1
i i0
n 1
n
I hij p hij' pi' , j.
'
i 1
*
i
i 1
Cледовательно p*, q* является парой оптимальных стратегий в игре с платёжной матрицей
H, со значением игры I’.
21.09.2011
Исаченко А.Н.
Лекция 6
7

8.

Исследование операций
Теория игр
Связь матричных игр с линейным программированием.
Рассмотрим матричную игру с матрицей выигрышей H hij
. Не нарушая общности
n m
будем считать, что hij 0 , i 1, n , j 1, m . Построим две двойственные задач ЛП:
m
y
n
x min ,
i
i 1
n
h x 1,
ij i
i 1
j 1
max ,
m
h y
(З1)
j 1, m ,
j
j 1
ij
j
1, i 1, n ,
(З2)
y j 0 , j 1, m .
xi 0 , i 1, n .
Все элементы матрицы H по предположению положительны, поэтому многогранные
множества задач (З1) и (З2) ограничены соответственно снизу и сверху. Многогранник
задачи (З2) не пуст, так как y = 0 является допустимым планом. Следовательно, задача (З2),
а с ней (по первой теореме двойственности) и задача (З1) разрешимы, и их функционалы в
n
оптимальных планах x* , y* совпадают (вторая теорема двойственности):
n
Из условий задачи 1 следует, что
1
x
i 1
i 1
*
j
*
i
i 1
j 1
*
j
.
0 . Обозначим
*
i
*
j
*
i
n
m
Получим p 0 , i 1, n , p 1, q 0 , j 1, m , q *j 1 , т.е.
i 1
j 1
стратегиями игроков.
*
i
26.09.2011
x y
0 , p i x , i 1, n , q y , j 1, m .
*
n
x
m
*
i
*
i
*
j
Исаченко А.Н.
p * , q * являются смешанными
Лекция 7
8

9.

Исследование операций
Имеем,
n
Теория игр
n
h x h
i 1
*
ij i
i 1
ij
pi*
m
m
h y h
1, j 1, m ,
j 1
ij
*
j
j 1
q *j
ij
1, i 1, n .
Или
n
h
i 1
ij
m
h q
p , j 1, m ,
*
i
j 1
ij
*
j
, i 1, n .
Умножим каждое из неравенств первой (второй) группы на компоненты произвольной
смешанной стратегии q j ( pi ) второго (первого) игрока и сложим результаты. Получим
n
m
h
i 1 j 1
Следовательно
ij
n
m
p q j hij pi q *j , p , q .
*
i
i 1 j 1
p * , q * оптимальные стратегии игроков, а
- значение игры.
Таким образом, чтобы найти решение матричной игры надо перейти к задаче с тем же
оптимальным решением, что и у исходной задачи, но с положительными элементами,
затем построить пару двойственных задач линейного программирования и найти их
решение (например симплекс-методом). По полученному решению вычислить значения
компонент оптимальных стратегий игроков и найти значение игры.
26.09.2011
Исаченко А.Н.
Лекция 7
9

10.

Исследование операций
Пример.
Теория игр
24 0
H
0
.
8
Переходим к матрице
H
25 1
1
9
.
Строим пару двойственных задач ЛП:
x1 x2 min,
y1 y2 max ,
25 x1 x2 1,
Получим:
25 y1 y2 1,
x1 9 x2 1,
y1 9 y2 1,
x1 , x2 0.
y1 , y2 0 .
x1* 0,0357 ,
y1* 0,0357 ,
x2* 0,107 ,
y2* 0,107 ,
0,1427 .
Перейдём к оптимальным стратегиям игроков:
p1* 0,0357 / 0,1427 0,2502 ,
q1* 0,2502 ,
p2* 0,107 / 0,1427 0,7498 ,
q2* 0,7498 ,
I 1 / 0,1427 1 6,008 .
26.09.2011
Исаченко А.Н.
Лекция 7
10