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

UptoLike

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

Рубрика: 

20
+=
=
),1(3
),1(3
qqw
qqw
получаем
1,
2
1
00
== wq
.
5-й шаг. Отыскание оптимальной смешанной стратегии игрока
A
.
Полагая
,0,1,
0
3
0
2
0
1
=
=
=
ppppp
приравниваем средние выигрыши игрока
A
, соответствующие чистым стратегиям игрока
: B
)1(3)1(3
p
p
p
p
+
=
,
и находим
2
1
=p
.
Таким образом, цена игры и оптимальные смешанные стратегии игроков
A
и со-
ответственно равны:
B
=
==
2
1
,
2
1
,0,
2
1
,
2
1
,1
00
QPw
.
2.3.
nm
×
игры
В принципе решение любой матричной игры сводится к решению стандартной задачи
линейного программирования и тем самым может быть найдено методами линейного про-
граммирования. При этом требуемый объем вычислений напрямую зависит от числа чистых
стратегий игроков (растет с его увеличением и, значит, с увеличением размеров матрицы иг-
ры). Поэтому любые приемы предварительного анализа игры, позволяющие уменьшать раз-
меры ее платежной матрицы или еще как-то упрощать эту матрицу, не нанося ущерба реше-
нию, играют на практике весьма важную роль.
a) Правило доминирования.
В целом ряде случаев анализ платежной матрицы обнаруживает, что некоторые чис-
тые стратегии не могут внести никакого вклада в искомые оптимальные смешанные страте-
гии. Отбрасывание подобных стратегий позволяет заменить первоначальную матрицу мат-
рицей выигрышей меньших размеров.
Опишем одну из таких возможностей более подробно.
Сравнение строк и столбцов матрицы
Будем говорить, что -я строка матрицы
i
A
inii
aaa ...
21
не больше
j
-й строки этой матрицы
jnjj
aaa ...
21
,
если одновременно выполнены следующие неравенств:
n
jninjiji
aaaaaa
...,,,
2211
.
При этом говорят также, что
-я строка доминирует
i
-ю строку или что стратегия игро-
ка
j
A
A
доминирует стратегию .
i
A
Замечание. Игрок
A
поступит разумно, если будет избегать стратегий, которым в
матрице игры отвечают доминируемые строки.
                                                                                       20

                                     ⎧w = 3q − (1 − q),
                                     ⎨
                                     ⎩w = −q + 3(1 − q),
получаем
                                            1
                                       q 0 = , w0 = 1 .
                                            2
5-й шаг. Отыскание оптимальной смешанной стратегии игрока A .
      Полагая
                             p10 = p,   p20 = 1 − p, p30 = 0,
приравниваем средние выигрыши игрока A , соответствующие чистым стратегиям игрока
B:
                             3 p − (1 − p) = − p + 3(1 − p) ,
и находим p = 1 .
               2
      Таким образом, цена игры и оптимальные смешанные стратегии игроков A и B со-
ответственно равны:
                                     ⎧1 1 ⎫          ⎧1 1 ⎫
                        w = 1, P 0 = ⎨ , , 0⎬, Q 0 = ⎨ , ⎬ .
                                     ⎩2 2 ⎭          ⎩2 2⎭

                                            2.3. m × n игры

       В принципе решение любой матричной игры сводится к решению стандартной задачи
линейного программирования и тем самым может быть найдено методами линейного про-
граммирования. При этом требуемый объем вычислений напрямую зависит от числа чистых
стратегий игроков (растет с его увеличением и, значит, с увеличением размеров матрицы иг-
ры). Поэтому любые приемы предварительного анализа игры, позволяющие уменьшать раз-
меры ее платежной матрицы или еще как-то упрощать эту матрицу, не нанося ущерба реше-
нию, играют на практике весьма важную роль.
       a) Правило доминирования.
       В целом ряде случаев анализ платежной матрицы обнаруживает, что некоторые чис-
тые стратегии не могут внести никакого вклада в искомые оптимальные смешанные страте-
гии. Отбрасывание подобных стратегий позволяет заменить первоначальную матрицу мат-
рицей выигрышей меньших размеров.
       Опишем одну из таких возможностей более подробно.
      Сравнение строк и столбцов матрицы
      Будем говорить, что i -я строка матрицы A
                                           ai1     ai 2 ... ain
не больше j -й строки этой матрицы
                                          a j1    a j 2 ... a jn ,
если одновременно выполнены следующие n неравенств:
                             ai1 ≤ a j1 , ai 2 ≤ a j 2 , ..., ain ≤ a jn .
При этом говорят также, что j -я строка доминирует i -ю строку или что стратегия Aj игро-
ка A доминирует стратегию Ai .
      Замечание. Игрок A поступит разумно, если будет избегать стратегий, которым в
матрице игры отвечают доминируемые строки.