Петросян_Теория_игр

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 - 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 всегда имеет единственную оптимальную стратегию.