Теория игр: Текст лекций. Саакян Г.Р. - 11 стр.

UptoLike

ВУЗ: 

ИСОиП ДГТУ | Шахты

Составители: 

Рубрика: 

10
),(),(),(
0000
QPMQPMQPM
AAA
≤
≤
.
Пояснение. Выписанные неравенства означают следующее:
левое неравенство – отклонение игрока
A
от оптимальной стратегии
0
P
при усло-
вии, что игрок придерживается стратегии , приводит к тому, что выигрыш отклонив-
шегося игрока
B
0
Q
A
может только уменьшиться;
правое неравенство – отклонение игрока от оптимальной стратегии при усло-
вии, что игрок
B
0
Q
A
придерживается стратегии
0
P
, приводит к тому, что выигрыш игрока
A
может только возрасти, и значит, выигрыш игрока – только уменьшиться. B
Приведенное условие оптимальности равносильно тому, что
2
),(maxmin),(),(minmax
00
QPMQPMQPM
A
P
Q
AA
Q
P
=
=
.
Величина
),(
00
QPMv
A
=
,
определяемая последней формулой, называется ценой игры.
Набор , состоящий из оптимальных смешанных стратегий игроков
),,(
00
vQP
A
и
и цены игры, называется решением матричной игры. B
Естественно, возникают два ключевых вопроса:
1) какие матричные игры имеют решение в смешанных стратегиях?
2) как найти решение матричной игры, если оно существует?
Ответы на эти вопросы дают следующие две теоремы.
1.3. Основная теорема теории матричных игр
Теорема 1 (Дж. фон Нейман). Для матричной игры с любой матрицей
A
величины
),(maxmin,),(minmax QPMQPM
A
P
Q
A
Q
P
существуют и равны между собой:
),(maxmin),(minmax QPMQPM
A
P
Q
A
Q
P
=
.
Более того, существует по крайней мере одна ситуация в смешанных стратегиях
, для которой выполняется соотношение
),(
00
QP
),(maxmin),(minmax),(
00
QPMQPMQPM
A
P
Q
A
Q
P
A
=
=
.
Иными словами, любая матричная игра имеет решение в смешанных стратегиях.
Поиск этого решения опирается на следующие установленные факты.
1.4. Основные свойства оптимальных смешанных стратегий
Теорема 2. Пусть
},...,,{
00
2
0
1
0
m
pppP =
и
},...,,{
00
2
0
1
0
n
qqqQ
=
― оптимальные смешанные стратегии и ― цена игры.
v
),(minmax QPM
A
Q
P
2
Экстремальные величины и всегда существуют вследст-
вие того, что функция является непрерывной на замкнутом множестве
),(maxmin QPM
A
P
Q
),( QPM
A
,1,0
1
=≥
∑
=
m
i
ii
pp .
∑
=
≥
n
k
kk
qq
1
,0
                                                                                                                   10

                                 M A ( P, Q 0 ) ≤ M A ( P 0 , Q 0 ) ≤ M A ( P 0 , Q ) .
       Пояснение. Выписанные неравенства означают следующее:
                                                                          0
       левое неравенство – отклонение игрока A от оптимальной стратегии P при усло-
                                             0
вии, что игрок B придерживается стратегии Q , приводит к тому, что выигрыш отклонив-
шегося игрока A может только уменьшиться;
                                                                          0
       правое неравенство – отклонение игрока B от оптимальной стратегии Q при усло-
                                                              0
вии, что игрок A придерживается стратегии P , приводит к тому, что выигрыш игрока A
может только возрасти, и значит, выигрыш игрока B – только уменьшиться.
       Приведенное условие оптимальности равносильно тому, что 2
               max min M A ( P, Q ) = M A ( P 0 , Q 0 ) = min max M A ( P, Q ) .
                        P    Q                                              Q           P

Величина
                                                  v = M A (P0 , Q0 ) ,
определяемая последней формулой, называется ценой игры.
                0   0
      Набор ( P , Q , v) , состоящий из оптимальных смешанных стратегий игроков A и
B и цены игры, называется решением матричной игры.
      Естественно, возникают два ключевых вопроса:
1) какие матричные игры имеют решение в смешанных стратегиях?
2) как найти решение матричной игры, если оно существует?
      Ответы на эти вопросы дают следующие две теоремы.

                                 1.3. Основная теорема теории матричных игр

         Теорема 1 (Дж. фон Нейман). Для матричной игры с любой матрицей A величины
                                     max min M A ( P, Q) , min max M A ( P, Q)
                                      P       Q                     Q               P

существуют и равны между собой:
                             max min
                                  Q
                                     M A ( P, Q) = min
                                                    Q
                                                       max M A ( P, Q) .
                                 P                                      P

       Более того, существует по крайней мере одна ситуация в смешанных стратегиях
( P , Q 0 ) , для которой выполняется соотношение
     0


                   M A ( P 0 , Q 0 ) = max min M A ( P, Q ) = min max M A ( P, Q ) .
                                             P     Q                        Q           P



Иными словами, любая матричная игра имеет решение в смешанных стратегиях.
     Поиск этого решения опирается на следующие установленные факты.

                        1.4.Основные свойства оптимальных смешанных стратегий

         Теорема 2. Пусть
                       P 0 = { p10 , p20 ,..., pm0 } и Q 0 = {q10 , q20 ,..., qn0 }
― оптимальные смешанные стратегии и v ― цена игры.


2
    Экстремальные величины   max min
                                  Q
                                     M A ( P, Q )         и   min
                                                               Q
                                                                  max M A ( P, Q)           всегда существуют вследст-
                                 P                                      P

вие того, что функция   M A ( P, Q )      является непрерывной на замкнутом множестве
                                                  m                             n
                                          pi ≥ 0, ∑ pi = 1, qk ≥ 0, ∑ qk .
                                                  i =1                      k =1

Страницы