Петросян_Теория_игр
.pdf7.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 - 1 5 г |
|||
|
3 |
0 |
1 |
- 2 |
- 5 |
А' = |
7 |
- 1 |
0 |
7 |
5 |
11 |
2 |
- 7 |
0 |
15 |
|
|
15 |
5 |
- 5 |
- 15 |
0 |
Заметим, что 1-я стратегия каждого игрока (1-я строка и 1-й столбец матрицы) строго доминируема, поэтому она не может быть существенной и ее можно вычеркнуть. В полученной усеченной матрице
|
О |
1 |
- 2 |
- 5 " |
А' = |
- 1 |
0 |
7 |
5 |
2 |
- 7 |
0 |
15 |
|
|
5 |
- 5 |
- 1 5 |
0 |
не все стратегии являются существенными.
Действительно, из симметричности игры Г^ следует, что vA=0.
Если бы все стратегии были существенными, то оптимальная стра тегия х* была бы решением системы уравнений
x*aJ=0,j=2,3,4, 5,
1-7
которая решения не имеет.
Перебирая варианты, остановимся на существенной подматрице А", составленной из строк и столбцов матрицы А с номерами 2, Зи5:
r-[-i |
-5 |
0. |
|
1 |
- 5 |
|
О |
5 |
Игра с матрицей Л" является вполне смешанной и имеет единствен ное решение у=х=(5/11, 5/11, 1/11).
Теперь в исходной игре рассмотрим стратегии х*=у* = (0, 5/11, 5/11, 0, 1/П), которые и являются оптимальными.
Таким образом, окончательно имеем: vA = 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 — значение матричной игры Гл. Рассмотрим отношения
lk/k=max |
£ |
ayrfilk^a^yrfilk, |
1 |
J |
J |
52
vk/k=mm |
£ ctijg/k = Y, auk+i $lk- |
|
i |
; |
i |
Векторы х/с=(£'[/к, ..., ^„/k) и .y*=0/i/fc, .... rfjk) являются смешан ными стратегиями игроков 1 и 2 соответственно, поэтому по опре делению значения игры имеем
max vkjk4:V^.mai vk/k.
к - к
Таким образом, получен некоторый итеративный процесс, по зволяющий находить приближенное решение матричной игры, при этом степень близости приближения к истинному значению игры
определяется длиной интервала max vk/k, min vk/k\. Сходимость
алгоритма гарантируется теоремой [64].
Теорема.
lim I min vk/k l = lim I max vkjk ]=i;.
Пример 18. Найти приближенное решение игры с матрицей
a b с
2 1 з"
3 0 1
1 2 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. Основным недостатком рассмотренного метода является его малая скорость сходимости, которая уменьшается с ростом размерности матрицы. Это_является также следствием немонотонности последовательностей vk/k и vkjk.
Рассмотрим другой итеративный алгоритм, который избавлен от указанного недостатка.
53
10.2. Монотонный итеративный алгоритм решения матричных игр. Рассмотрим смешанное расширение Г^ = (X, Y, К) матричной игры с(шхи)-матрицей А.
Обозначим х?=($, .... £%) еX приближение оптимальной стра тегии первого игрока на N-и итерации и c^eR", cN=('vi'. •••, $) — вспомогательный вектор. Алгоритм позволяет находить (точно и приближенно) оптимальную стратегию игрока 1 и значение игры v.
В начале процесса игрок 1 выбирает произвольную чистую стратегию i0, т. е. х°=(0, ..., 1, ..., 0) = и,0 и вспомогательный вектор
вида c° = aio, где а,о — строка матрицы А, имеющая номер /0.
Итеративный процесс строится следующим образом. Пусть вы полнена N— 1 итерация и получены векторы дг1* , с1*-1. Тогда х? и с* вычисляются по следующим итеративным формулам:
xN=(l-aN)^-i |
+ aNxN; |
(10.1) |
ciV = (l-aiV)cN-1-|-aJvcw, |
(10.2) |
где параметр 0<aw < 1. Векторы Xя и с" будут получены ниже.
Таблица 10.1
Номер |
Выбор |
Выбор |
Выигрыш игрока 1 |
Проигрыш игрока 2 |
vKlk |
vKlk |
|||||
партии |
игрока |
игрока |
a |
Р |
У |
а |
Ь |
с |
|
|
|
|
1 |
2 |
|
|
|||||||
1 |
a |
а |
2 |
3 |
|
1 |
2 |
1 |
3 |
3 |
1 |
2 |
Р |
Ь |
3 |
3 |
|
3 |
5 |
1 |
4 |
3/2 |
1/2 |
3 |
Р |
Ь |
4 |
3 |
|
5 |
8 |
1 |
5 |
5/3 |
1/3 |
4 |
У |
Ь |
5 |
3 |
|
7 |
9 |
3 |
6 |
7/4 |
3/4 |
5 |
У |
Ь |
6 |
3 |
|
9 |
10 |
5 |
7 |
9/5 |
5/5 |
6 |
У |
Ь |
7 |
3 |
|
11 |
11 |
7 |
8 |
11/6 |
7/6 |
7 |
У |
Ь |
8 |
3 |
|
13 |
12 |
9 |
9 |
13/7 |
9/7 |
8 |
у |
с |
11 |
4 |
|
14 |
13 |
И |
10 |
14/8 |
10/8 |
9 |
У |
с |
14 |
5 |
|
15 |
14 |
13 |
11 |
15/9 |
11/9 |
10 |
У |
с |
17 |
6 |
|
16 |
15 |
15 |
12 |
17/10 |
12/10 |
11 |
a |
с |
20 |
7 |
|
17 |
17 |
16 |
15 |
20/11 |
15/11 |
12 |
a |
с |
23 |
8 |
|
18 |
19 |
17 |
18 |
23/12 |
17/12 |
Рассмотрим вектор |
<? 1 |
= ("^1 |
1, |
.... у% 1) и |
выберем |
такие |
|||||
индексы jk, |
на которых достигается минимум |
|
|
|
min tf-i.tf-i^-i-...^-!.
j - \ , ... я
Обозначим через
И-*= min yf"1 |
(10.3) |
и JN~i = {ii, —, jk} множество индексов, на которых (10.3) до стигается.
54
Пусть ГяаГл — подыгра игры ГА с матрицей Ал = {а£ '},/'= 1,
..., т, а индекср~ 1eJfl~1. Решаем подыгру и находим оптимальную стратегию х"еХ игрока 1. Пусть xN=(lN, ..., £*).
т
Вычислим вектор cN= ]Г £fa,-. Пусть вектор cN имеет компонен ты cN=(yN, ..., у„). Рассмотрим (2хи)-игру с матрицей
L П |
£ J |
Найдем оптимальную стратегию |
(aN, 1 — aN), 0<aw <l, игрока |
i в этой подыгре. |
|
Подставляя найденные значения х", с1*, а* в (10.1), (10.2), нахо |
дим х* и с". Процесс продолжаем до тех пор, пока не вьшолнится равенство aN=0 или не будет достигнута требуемая точность вычис лений. Сходимость алгоритма гарантируется следующей теоремой [65].
Теорема. Пусть {Vs}, {х?} — итеративные последовательности, определяемые (10.1), (10.3). Тогда справедливы следующие утвержде
ния. |
|
1. vN>vN~1, т. е. последовательность {vN~1} строго монотонно |
|
возрастает. |
|
2. |
(10.4) |
lim vN=v=v. |
№-•00
3.lim Xs=х*. где х*еХ* — оптимальная стратегия игрока 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 = о
L 2 J
Оптимальной стратегией Jc1 игрока 1 является вектор Jc1 = (0, 0, 1).
55
Тогда с1 = а3 = (1, 2, 1). Решаем (2 х 3)-игру с матрицей Заметим, что З^й столбелоец матрицы доминируем, :поэтому~'рас-
смотрим матрицу КЗ
В силу симметрии оптимальной стратегией игрока 1 в этой игре является вектор (лю 1 — aN) = (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 ^ m i n y} = y\=yi=3l2>v° = l.
Множество индексов имеет вид /х = {1, 2}.
Итерация 2. Рассмотрим подыгру Г4 с Г с матрицей
С • •
Первая строка в этой матрице доминируема, поэтому достаточ но рассмотреть подматрицу
[::)
Оптимальной стратегией игрока 1 в этой игре является вектор Си, 3 /Д поэтому f = (0, V4» 3 /Д
Вычислим c2 = 1/4.a2 + 3/4.a3 = (3/2, 3/2, 1) и рассмотрим (2x3)- |
|
„ Гз/2 3/2 |
Л |
игру с матрицей |
I. Вторая стратегия игрока 1 доминирует |
первую, поэтому а2 = 0. |
Таким образом, вычисления закончены |
х* = х1 = (1/2, 0, VJ), значение « игры равно v=v1 = 3/2, а оптималь ная стратегия игрока 2 имеет вид у* = (1/2, 1/г> 0) (см- пример 18).
Упражнения • задачи
1. Каждый из двух игроков показывает другому т пальцев на руке ( U m ^ 5 ) и одновременно называет число пальцев, которое, по его мнению, может показать противник. Если один игрок угадывает правильно, а другой неправильно, то тот, который угадал, выигрывает сумму, равную числу пальцев, показанных обоими игроками. Во всех остальных случаях выигрыши обоих игроков считаются ну левыми.
а) Сколько стратегий имеет каждый игрок при л=3? б) Построить матрицу игры для л=2.
2. Распределение поисковых усилий. В одной из п ячеек игрок 2 прячет предмет.
56
Игрок I имеет в распоряжении г ищущих, которые должны быть распределены по ячейкам для поиска предмета. Например, в первую ячейку могут быть направлены (г— 1) ищущих, один - во вторую ячейку, а в остальные ячейки — ни одного и т. п.
Предполагается, что известна вероятность обнаружения предмета в i'-й ячейке (если он там находится) при поиске одним ищущим. Обнаружение предмета каждым из ищущих — независимые события.
Выигрыш игрока 1 — вероятность обнаружения предмета при заданном рас пределении ищущих.
а) Вычислить число т чистых стратегий игрока 1. б) Построить матрицу игры.
3. Поиск многих предметов. Игрок 2 прячет т черных шаров в п урнах. Общее количество шаров (черных и белых), находящихся в >й урне, равно //, j=\, ..., п. Игрок 2 должен распределить т черных шаров между п урнами, при этом общее количество шаров в каждой урне постоянно и равно Ц, lj>m.
Противник (игрок 1) старается обнаружить максимальное число черных шаров, имея возможность проверить одну из урн. При проверке /-й урны игрок 1 наугад (равновероятно) выбирает т шаров из /,-, и его выигрыш равен математическому ожиданию количества черных шаров в выборке из т шаров.
а) Пусть в i'-й урне спрятаны pt черных шаров. Вычислить вероятность /?у того,
что выбранная из 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
Предполагается, что возможно нападение только одним из самолетов. Выигрыш игрока 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, I V соответственно. 8. Рассматривается игра Тл> с матрицей
57
- 1 3 - 3 А = 2 0 3
-2 1 О-
Значение игры vA = 1 и оптимальная стратегия игрока 1 есть х* —(1/3, 2/3, 0). Найти оптимальную стратегию у* игрока 2.
9. Решить графически игру с матрицей
4 0
3 - 2
5- 3
1- 1
10.Показать, что строго доминируемая стратегия не может быть существенной!
11.Показать, что 3-я строка матрицы А доминируема, где
~20 °1
А = 0 М
_ 4 5J
12.Показать, что выбор 1-го столбца эквивалентен смешанной стратегии >">(0,
1/3, 2/3), где матрица игры имеет видГ'3 "I
1.20 3J
13.Используя понятие доминирования, найти решение игры с матрицей
[:;:}
L.5 1 6 J
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. Игра поиска нескольких множеств на плоскости. Заданы набор п фиксированних компактных выпуклых множеств Kv K2, •••, KnaR2 а система т конгруэнтных между собой компактных выпуклых множеств Т., ..., TmczR2. Дискретная одновре менная игра поиска заключается в следующем. Игрок 2 прячет т множеств Т} (7 = 1,
..., т) в п множествах Kj (i= 1,..., п) таким образом, что они пересекают AT,-. Тот факт, что pi множеств спрятаны в Kh означает, что совокупность множеств {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 всегда имеет единственную оптимальную стратегию.