Петросян Л.А. и др. Теория игр
Подождите немного. Документ загружается.
Пусть стратегия х* оптимальна в игре Г,, тогда (см. теорему п.
7.1)
х*А^0.
Однако отсюда следует, что х*(—А
т
)~^0, поэтому х*4
г
<0. Таким
образом, получаем
Ах*^0.
Значит, по той же теореме п. 7.1 х* — оптимальная стратегия
игрока
2.
Таким образом, доказано, что Г*сУ*. Обратное включе-
ние доказывается аналогично.
В дальнейшем на основании равенства
X*
=
Y*,
говоря об оп-
тимальной стратегии игрока в симметричной игре, мы не будем
указывать, о каком именно игроке идет речь.
Пример 16. Решим игру с матрицей
А =
[:
•:.;}
L-i 1 oJ
Пусть
х*=(£,\,
£
2
, £з) — оптимальная стратегия в игре Г
А
. Тогда
должны выполняться неравенства
Й-Гз>о,
Й-Га>0, (9-8)
Й + Й + Гз =
1,
&>0, &>0, Гз>0.
Покажем, что эта игра вполне смешанная. Действительно, пусть
£1
=
0.
Тогда из системы неравенств (9.8) получаем систему
Й>о,
-&>о,
Й + Й + Й =
1,
которая не имеет неотрицательного решения. Аналогичные рассуж-
дения показывают невозможность случаев £1=0 или
£
3
=
0.
Поэто-
му игра Г
А
— вполне смешанная. Следовательно, компоненты &,
£
2
, £з являются решением системы
Й-Й=о,
£*
—£*
=0
Й + Й + Й = 1,{«>0,1=1,2,3.
Эта система имеет единственное решение. Оптимальной стратегией
является вектор х* =
(1/3,
1/3, 1/3).
50
Пример 17. Решим дискретную игру типа дуэли с пяти шагов
и одним выстрелом у каждого игрока, сформулированную в п. 1.4
(см.
пример 3). Матрица А выигрышей игрока 1 является симмет-
ричной и имеет вид
"О -3-7 -11 -15
г
А'
=
Заметим, что 1-я стратегия каждого игрока (1-я строка и 1-й
столбец матрицы) строго доминируема, поэтому она не может быть
существенной и ее можно вычеркнуть. В полученной усеченной
матрице
О 1 -2 -5"
А'
=
3
7
11
15
0
-1
2
5
1
0
-7
-5
-2
7
0
-15
-5
5
15
0
-1
2
5
0
-7
-5
7
0
-15
5
15
0
не все стратегии являются существенными.
Действительно, из симметричности игры Г^ следует, что v
A
=0.
Если бы все стратегии были существенными, то оптимальная стра-
тегия х* была бы решением системы уравнений
x*a
J
=0,j=2,3,4, 5,
1-7
которая решения не имеет.
Перебирая варианты, остановимся на существенной подматрице
А",
составленной из строк и столбцов матрицы А с номерами 2,
Зи5:
r
-[-i
1 -5
О 5
-5 0.
Игра с матрицей Л" является вполне смешанной и имеет единствен-
ное решение у=х=(5/11, 5/11,
1/11).
Теперь в исходной игре рассмотрим стратегии х*=у* = (0, 5/11,
5/11,
0, 1/П), которые и являются оптимальными.
Таким образом, окончательно имеем: v
A
= 0, ситуация равнове-
51
сия (х*, у*) единственная. С точки зрения правил игры получаем,
что дуэлянту не следует стрелять на 1-м шаге, он должен стрелять
с равной вероятностью после 2-го и 3-го шагов, никогда после 4-го
шага и лишь с малой вероятностью стрелять в упор.
§ 10. ИТЕРАТИВНЫЕ МЕТОДЫ РЕШЕНИЯ
МАТРИЧНЫХ ИГР
Распространенный способ решения матричной игры путем сведе-
ния ее к задаче линейного программирования обладает тем недо-
статком, что процесс решения задачи линейного программирования
существенно усложняется для матриц большой размерности. В та-
ких случаях обычно используют методы декомпозиции задачи ли-
нейного программирования, когда вместо решения задачи с ис-
ходной матрицей строится координирующая задача с матрицей,
у которой мало строк, но много столбцов. На каждой итерации
координирующей задачи решается некоторая совокупность вспомо-
гательных задач линейного программирования с матрицами мень-
ших размерностей. К сожалению, декомпозиционные методы эф-
фективны лишь для матриц специального вида (например, блочно-
диагональных).
10.1.
Итеративный метод Брауна — Робинсона (метод фиктивного
разыгрывания). Идея метода — многократное фиктивное разыгры-
вание игры с заданной матрицей выигрыша. Одно повторение игры
будем называть партией. Пусть разыгрывается игра с
(т
х ^-мат-
рицей А =
{а
и
).
В 1-й партии оба игрока выбирают совершенно
произвольные чистые стратегии. В к-й партии каждый игрок выби-
рает ту чистую стратегию, которая максимизирует его ожидаемый
выигрыш против наблюдаемого эмпирического вероятностного
распределения противника за
(к—
1)
партий.
Итак, предположим, что за первые к разыгрываний игрок
/ использовал i-ю стратегию
<!;*
раз (i=l, ..., /и), а игрок 2—j-ю
стратегию rfj раз (j=\, ..., и). Тогда в (£+1)-й партии игрок
1 будет использовать fjt+i-K) стратегию, а игрок 2—свою Л+г
ю
стратегию, где
й*=тах £ «i/^=X \
+
ui/
i
J J
и
j l i
Пусть
v
— значение матричной игры Г
л
. Рассмотрим отношения
l
k
/k=max £ ayrfilk^a^yrfilk,
1
J J
52
v
k
/k=mm £ ctijg/k
=
Y,
a
u
k
+i
$l
k
-
i ; i
Векторы
х/
с
=(£'[/к,
..., ^„/k) и .y*=0/i/fc, .... rfjk) являются смешан-
ными стратегиями игроков 1 и 2 соответственно, поэтому по опре-
делению значения игры имеем
max v
k
jk4:V^.mai v
k
/k.
к - к
Таким образом, получен некоторый итеративный процесс, по-
зволяющий находить приближенное решение матричной игры, при
этом степень близости приближения к истинному значению игры
определяется длиной интервала max v
k
/k, min
v
k
/k\.
Сходимость
алгоритма гарантируется теоремой [64].
Теорема.
lim
I
min v
k
/k
l
=
lim I
max
v
k
jk
]=i;.
Пример 18. Найти приближенное решение игры с матрицей
a b с
2
3
1
1
0
2
з"
1
1
Обозначим а,
/?,
у стратегии игрока 1 иа.Ь, с — стратегии игрока 2.
Пусть сначала игроки выбрали стратегии а и а соответственно. Если
игрок 1 выбрал стратегию а, то игрок 2 может получить один из
выигрышей (2, 1, 3). Если игрок 2 выбрал стратегию а, то игрок
1 может получить один из выигрышей (2, 3, 1). Во 2-й и 3-й партиях
игрок 1 выбирает стратегию
/?,
а игрок 2 —
Ь,
поскольку эти страте-
гии обеспечивают наилучший результат и т. д.
В табл. 10.1 приведены результаты разыгрываний, в этой табли-
це указаны стратегия игрока, накопленный выигрыш и средний
выигрыш.
Таким образом, за 12 партий мы получили приближение реше-
ния х
12
=(1/4, 1/6, 7/12),>>
12
= (1/12,1/2, 5/12), а точность может быть
оценена числом 1/2. Основным недостатком рассмотренного метода
является его малая скорость сходимости, которая уменьшается
с ростом размерности матрицы.
Это_
является также следствием
немонотонности последовательностей v
k
/k и
v
k
jk.
Рассмотрим другой итеративный алгоритм, который избавлен
от указанного недостатка.
53
10.2.
Монотонный итеративный алгоритм решения матричных игр.
Рассмотрим смешанное расширение
Г^
= (X, Y, К) матричной игры
с(шхи)-матрицей А.
Обозначим х?=($, ....
£%)
еX приближение оптимальной стра-
тегии первого игрока на N-и итерации и c^eR", c
N
=('vi'. •••, $) —
вспомогательный вектор. Алгоритм позволяет находить (точно
и приближенно) оптимальную стратегию игрока
1
и значение игры v.
В начале процесса игрок 1 выбирает произвольную чистую
стратегию i
0
, т. е. х°=(0, ..., 1, ..., 0) = и,
0
и вспомогательный вектор
вида
c°
=
a
io
,
где а,
о
— строка матрицы А, имеющая номер /
0
.
Итеративный процесс строится следующим образом. Пусть вы-
полнена
N—
1
итерация и получены векторы
дг
1
*
, с
1
*
-1
. Тогда х?
и с* вычисляются по следующим итеративным формулам:
x
N
=(l-a
N
)^-
i
+
a
N
x
N
;
(10.1)
c
iV
= (l-a
iV
)c
N
-
1
-|-a
Jv
c
w
, (10.2)
где параметр 0<a
w
<
1.
Векторы X
я
и с" будут получены ниже.
Таблица 10.1
Номер
партии
1
2
3
4
5
6
7
8
9
10
11
12
Выбор
игрока
1
a
Р
Р
У
У
У
У
у
У
У
a
a
Выбор
игрока
2
а
Ь
Ь
Ь
Ь
Ь
Ь
с
с
с
с
с
Выигрыш игрока 1
a
2
3
4
5
6
7
8
11
14
17
20
23
Р
3
3
3
3
3
3
3
4
5
6
7
8
У
1
3
5
7
9
11
13
14
15
16
17
18
Проигрыш игрока 2
а
2
5
8
9
10
11
12
13
14
15
17
19
Ь
1
1
1
3
5
7
9
И
13
15
16
17
с
3
4
5
6
7
8
9
10
11
12
15
18
v
K
lk
3
3/2
5/3
7/4
9/5
11/6
13/7
14/8
15/9
17/10
20/11
23/12
v
K
lk
1
1/2
1/3
3/4
5/5
7/6
9/7
10/8
11/9
12/10
15/11
17/12
Рассмотрим вектор <?
1
=
("^1
1
, .... у%
1
) и выберем такие
индексы
j
k
,
на которых достигается минимум
min
tf-i.tf-i^-i-...^-!.
j-\,
... я
Обозначим через
И-*= min yf"
1
(10.3)
и J
N
~
i =
{ii, —, jk} множество индексов, на которых (10.3) до-
стигается.
54
Пусть
Г
я
аГ
л
— подыгра игры Г
А
с матрицей А
л
=
{а£
'},/'=
1,
..., т, а индекср~
1
eJ
fl
~
1
.
Решаем подыгру и находим оптимальную
стратегию х"еХ игрока 1. Пусть x
N
=(l
N
, ..., £*).
т
Вычислим вектор c
N
=
]Г
£fa,-. Пусть вектор c
N
имеет компонен-
ты c
N
=(y
N
, ...,
у„).
Рассмотрим (2хи)-игру с матрицей
L П £ J
Найдем оптимальную стратегию (a
N
,
1
— a
N
), 0<a
w
<l, игрока
i в этой подыгре.
Подставляя найденные значения х", с
1
*, а* в (10.1), (10.2), нахо-
дим х* и с". Процесс продолжаем до тех пор, пока не вьшолнится
равенство
a
N
=0
или не будет достигнута требуемая точность вычис-
лений. Сходимость алгоритма гарантируется следующей теоремой
[65].
Теорема.
Пусть
{V
s
},
{х?} —
итеративные
последовательности,
определяемые
(10.1), (10.3).
Тогда справедливы следующие
утвержде-
ния.
1.
v
N
>v
N
~
1
, т. е.
последовательность
{v
N
~
1
}
строго монотонно
возрастает.
2.
lim v
N
=v=v. (10.4)
№-•00
3.
lim
X
s
=х*.
где
х*еХ*
—
оптимальная стратегия игрока
1.
N-aa
Пример
19.
Решим, используя монотонный алгоритм, игру с мат-
рицей
~2 1 3"
А =
з о 1
_1 2 1-
Итерация 0. Пусть игрок 1 выбрал 1-ю строку матрицы А, т. е.
х°=(1,
0, 0) и с°=а
1
=(2,1, 3). Вычислим «°=min
ц,°=у2
=
1,
J° =
{2).
~ j
Итерация 1. Рассмотрим подыгру Г
1
с Г' с матрицей
А
1
=
1
о
L2J
Оптимальной стратегией Jc
1
игрока 1 является вектор
Jc
1
=
(0,
0, 1).
55
лоец матрицы доминируем, :
КЗ
Тогда
с
1
= а
3
=
(1,
2, 1). Решаем (2 х 3)-игру с матрицей
Заметим, что З^й столбец матрицы доминируем, поэтому~'рас-
смотрим матрицу
В силу симметрии оптимальной стратегией игрока 1 в этой игре
является вектор (л
ю
1 —
a
N
) = (
1
/
2
,
1
/
2
).
Вычисляем х
1
и с
1
по формулам (10.1), (10.2). Имеем
х
1
=
112х°+112х
1
=
(1/2,
0, 1/2),
с
1
=
1/2с° +1
/2с
1
=
(3/2,
3/2, 2),
i^min
y} =
y\=yi=3l2>v°
=
l.
Множество индексов имеет вид /
х
=
{1,
2}.
Итерация 2. Рассмотрим подыгру Г
4
с Г с матрицей
С
•
•
Первая строка в этой матрице доминируема, поэтому достаточ-
но рассмотреть подматрицу
[::)
Оптимальной стратегией игрока 1 в этой игре является вектор
Си,
3
/Д поэтому f =
(0,
V4»
3
/Д
Вычислим c
2
=
1
/
4
.a
2
+
3
/
4
.a
3
=
(3/2,
3/2, 1) и рассмотрим (2x3)-
„ Гз/2 3/2 Л
игру с матрицей
I.
Вторая стратегия игрока
1
доминирует
первую, поэтому а
2
= 0. Таким образом, вычисления закончены
х*
=
х
1
= (
1
/
2
, 0,
VJ),
значение « игры равно v=v
1
=
3/2,
а оптималь-
ная стратегия игрока 2 имеет вид
у*
= (
1
/
2
,
1
/г> 0) (
см
- пример 18).
Упражнения • задачи
1.
Каждый из двух игроков показывает другому т пальцев на руке (Um^5)
и одновременно называет число пальцев, которое, по его мнению, может показать
противник. Если один игрок угадывает правильно, а другой неправильно, то
тот, который угадал, выигрывает сумму, равную числу пальцев, показанных обоими
игроками. Во всех остальных случаях выигрыши обоих игроков считаются ну-
левыми.
а) Сколько стратегий имеет каждый игрок при л=3?
б) Построить матрицу игры для л=2.
2.
Распределение поисковых усилий. В одной из п ячеек игрок 2 прячет предмет.
56
Игрок I имеет в распоряжении г ищущих, которые должны быть распределены по
ячейкам для поиска предмета. Например, в первую ячейку могут быть направлены
(г—
1) ищущих, один - во вторую ячейку, а в остальные ячейки — ни одного и т. п.
Предполагается, что известна вероятность обнаружения предмета в i'-й ячейке
(если он там находится) при поиске одним ищущим. Обнаружение предмета каждым
из ищущих — независимые события.
Выигрыш игрока 1 — вероятность обнаружения предмета при заданном рас-
пределении ищущих.
а) Вычислить число т чистых стратегий игрока 1.
б) Построить матрицу игры.
3.
Поиск многих предметов. Игрок 2 прячет т черных шаров в п урнах. Общее
количество шаров (черных и белых), находящихся в >й урне, равно //, j=\, ..., п.
Игрок 2 должен распределить т черных шаров между п урнами, при этом общее
количество шаров в каждой урне постоянно и равно
Ц,
lj>m.
Противник (игрок 1) старается обнаружить максимальное число черных шаров,
имея возможность проверить одну из урн. При проверке /-й урны игрок 1 наугад
(равновероятно) выбирает т шаров из /,-, и его выигрыш равен математическому
ожиданию количества черных шаров в выборке из т шаров.
а) Пусть в i'-й урне спрятаны p
t
черных шаров. Вычислить вероятность /?у того,
что выбранная из i'-й урны группа г шаров содержит ровное черных.
б) Построить матрицу игры.
4 Противовоздушная оборона. В системе ПВО объекта могут применяться три
типа средств поражения воздушной цели (1, 2, 3), которые должны быть рас-
пределены между двумя стартовыми установками. У противника (игрока 2) имеется
два типа самолетов (тип 1 и тип 2). Вероятности поражения самолетов одним
средством сведены' в матрицу
1 2.
1Г0,3 0,5~|
2 0,5 0,3
3
1_0,1 0.6J
2
3
Предполагается, что возможно нападение только одним из самолетов.
Выигрыш игрока 1 — вероятность поражения самолета системой ПВО.
а) Построить матрицу игры.
б) Выяснить, имеется ли решение в чистых стратегиях.
5.
Найти ситуации равновесия и значения следующих игр:
"СО
*[
1/2 0 1/2
1 3/2 1/2
0 -1 7/4-J
6. Проверить, что »=2 и пара (х*, у*), где
дг*
=
(0,
0, 1), У*=(2/5, 3/5, 0)-
соответственно значение и ситуация равновесия в игре с матрицей
L 2 2 6J
7.
Пусть А'(А") — подматрица матрицы А, получающаяся вычеркиванием ряда
строк (столбцов) А. Показать, что выполняются неравенства «л'^и^ил", где «^,
»л'
— значения игр IV, IV соответственно.
8. Рассматривается игра
Т
л
>
с матрицей
57
-1 3
2 0
- 2 1
-3
3
О-
А =
Значение игры
v
A
=
1
и оптимальная стратегия игрока
1
есть
х*
—(1/3,
2/3, 0). Найти
оптимальную стратегию у* игрока 2.
9. Решить графически игру с матрицей
4
3
5
1
0
-2
-3
-1
10.
Показать, что строго доминируемая стратегия не может
быть
существенной!
11.
Показать, что 3-я строка матрицы А доминируема, где
А =
12.
Показать, что выбор 1-го столбца эквивалентен смешанной стратегии >">(0,
1/3, 2/3), где матрица игры имеет вид
~20
0
_ 4
°1
М
5
J
Г'
3
"I
1.2 0 3J
13.
Используя понятие доминирования, найти решение игры с матрицей
[:;:}
L.5 1 6J
14.
Доказать теорему п. 7.3.
15.
Решить игру поиска с одной попыткой. Игрок 2 прячет предмет в одну из
п ячеек. Игрок
1
ищет его в одной из этих ячеек, при этом вероятность обнаружения
предмета в i-й ячейке равна /f/>0, i=l, ..., л (при условии, что он там находится).
Показать, что рассматриваемая игра вполне смешанная. Найти решение игры.
16.
Решить игру дискретного поиска (пример 5, п. 1.3) в предположении
а/?,-т,э*0,1
=
1,
..., п.
Указание. Воспользоваться результатом п. 7.7.
17.
Игра
поиска
двух
предметов.
Игрок 2 прячет два предмета в л ячейках
(можно оба в одной ячейке). Цель игрока 1 — обнаружить хотя бы один предмет,
при этом он имеет возможность проверить одну ячейку
(/?,->
0
— вероятность об-
наружения одного предмета в i-й ячейке) (при условии, что он там находится). Если
в i-й ячейке находятся одновременно два предмета, то вероятность их одновремен-
ного обнаружения равна /if. Таким образом, матрица
А =
{сц
аг
},
a=(i,j), i,j=\, ..., п,
имеет вид
04ь,=/?
(
,
i=k,
1ф),
58
4k»-A(2-W, «'=/=*•
Решить игру.
18.
Решить игру поиска многих предметов (см. упр. 3).
19.
Игра поиска нескольких множеств на
плоскости.
Заданы набор
п
фиксирован-
них компактных выпуклых множеств K
v
K
2
, •••, K
n
aR
2
а система т конгруэнтных
между собой компактных выпуклых множеств Т., ...,
T
m
czR
2
.
Дискретная одновре-
менная игра поиска заключается в следующем. Игрок 2 прячет т множеств Т
}
(7
=
1,
...,
т)
в п
множествах
Kj
(i=
1,...,
п) таким образом, что они пересекают
AT,-.
Тот факт,
что pi
множеств спрятаны в K
h
означает, что совокупность множеств
{7}}
в количест-
ве
pi
единиц бросается на плоскость случайно. Чистая стратегия а игрока 2 имеет вид
л
a=iPi.Pi Л.)е-К". Е Pi=m.
i-i
где Pi —
количество множеств
Tj,
спрятанных в множестве к,.
Игрок / может проверить одно из множеств Кь бросая случайно в Kt точку х.
Выигрыш игрока 1 — математическое ожидание числа множеств {Tj, которым при-
надлежит х.
Найти решение игры.
20.
Игра поиска
с
двумя попытками
у
ищущего.
Игрок 2 прячет предмет в одной
из п ячеек, а игрок 1 (ищущий) производит поиск в одной из этих ячеек, имея
возможность просмотреть две ячейки (повторный просмотр ячейки не допускается).
Множество чистых стратегий игрока 1 состоит из несовпадающих пар
(/,
]),
i =
1,
..., п, ]=\, ..., п, и содержит С
2
элементов. Множество чистых стратегий игрока
2 определяется индексом k, k= 1,..., п, и содержит
п
элементов. Матрица выигрышей
имеет вид £={£(,, д
*},
г
Д
е
(ок, если i=k или j=k,
(О
— в противном случае.
Решить игру в предположении
а
1
><х
2
>...
>а„>О
и
1/а
1
+
1/а
2
>
1/<г
в
.
21.
В игре поиска с двумя попытками у ищущего рассмотреть случай, когда
множество чистых стратегий игрока
1
состоит из всевозможных пар
(i,
J)
и содержит
я
2
элементов. Решить игру в предположении
л-1
Е
ff
»/
ff
*
<1
-
22.
В
игре на уклонение (п. 7.1) показать, что игрок
1
всегда имеет единственную
оптимальную стратегию.