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

матрицы А = {аи}, где ау=К(хи yj), (i,j)eMxN, (xh y)eXxY,ieM,

jeN (отсюда и название игры — матричная). При этом игра Г ре­ ализуется следующим образом. Игрок 1 выбирает строку геМ, а игрок 2 (одновременно с ним) — столбец j eJV. После этого игрок 1 получает выигрыш ау, а второй — (—ау). Если выигрыш равен

отрицательному числу, то речь идет о фактическом проигрыше игрока.

Игру Г с матрицей выигрышей А обозначим Г^ и назовем (тхл)-игрой (по размерности матрицы А). Если из изложения понятно, об игре с какой матрицей идет речь, то индекс А будем опускать.

Нумерация стратегий в матричной игре может производиться различными способами, поэтому каждому отношению порядка, строго говоря, соответствует своя матрица. Таким образом, конеч­ ная антагонистическая игра может быть описана различными мат­ рицами, отличающимися друг от друга лишь порядком строк и сто­ лбцов.

1.3. Пример 1. (Оборона города.) Этот пример известен в литера­ туре под названием «игра полковника Блотто» [4]. Полковник Блотто имеет т полков, а его противник — п полков. Противник защи­ щает две позиции. Позиция будет занята полковником Блотто, если на ней наступающие полки окажутся в численном превосходстве. Противоборствующим сторонам требуется распределить полки между двумя позициями.

Определим выигрыш полковника Блотто (игрока 1) на каждой позиции. Если у него на позиции полков больше, чем у противника (игрока 2), то его выигрыш на этой позиции равен числу полков противника плюс один (занятие позиции равносильно захвату одно­ го полка). Если у игрока 2 полков на позиции больше, чем у игрока 1, то игрок 1 теряет все свои полки на этой позиции и еще единицу (за потерю позиции). Если обе стороны имеют одинаковое число полков на позиции, то имеет место ничья и каждая из сторон ничего не получит. Общий выигрыш игрока 1 равен сумме выигрышей на обеих позициях.

Игра, очевидно, антагонистическая. Опишем стратегии игроков. Пусть, для определенности, т>п. Игрок 1 имеет следующие страте­ гии: х0 = (т, 0) — послать все полки на первую позицию, xi=(m— 1, 1)—(т— 1) полков послать на первую позицию, а один — на вто­ рую, хг = (т—2,2),..., xm_i = (1, т — 1), хт=(0, т). Противник (игрок

2) имеет такие стратегии: у0 = (п, 0), у1 = (п — 1, 1), ..., у„ = (0, и). Пусть игрок 1 выбрал стратегию JC0, а игрок 2 — стратегию у0.

Вычислим выигрыш а00 игрока 1 в этой ситуации. Поскольку т>п, на первой позиции выигрывает игрок 1. Его выигрыш равен л-И (единица — за удержание позиции). На второй позиции — ничья. Поэтому а00 = и + 1. Вычислим а01. Так как т>п—\, то на первой

ю

позиции выигрыш игрока 1 равен п—1 + 1 =и. На второй позиции выигрывает игрок 2. Поэтому проигрыш игрока 1 на этой позиции равен единице. Таким образом, а01=л —1. Рассуждая аналогично, получаем a0J=n—J+1 — 1 =n—j, l^J^n. Далее, если т— \>п, то

а10=я + 1 + 1=л + 2, а11 = и-1 + 1=и, otl]=n-j+\-\-\=n-j-\, 2<у'<и. В общем случае (для любых m и л) элементы aijt i=0, m, ;=0, л матрицы выигрышей вычисляются следующим образом:

я+2, если m—i>n—j, i>j, п—j+\, если m—i>n—j, i=j, n—j—i, если m—i>n—j, i<j,

—m+i+j, если m—i<n—j, i>j, a,j=K(x„ yj) j+1, если m—i=n—j, i>j,

—m—2, если m—i<n—j, i<j,

—i— 1, если m—i=n—j, i<j, —m+i—l, если m—i<n—j, i=j,

Оесли m—i=n—j, i—j.

Так, при /я=4, и=3, рассмотрев всевозможные ситуации, полу­ чим матрицу выигрышей А этой игры:

Уо У1 Уг Уъ

* 0 " 4 2 1 0"

* 1	1 3		0	- 1
=*1	- 2	2	2	- 2
*э	- 1 0	3		1
х* _	0	1 2		4 _

Пример 2. {«Игра на уклонение») Игроки 1 и 2 выбирают целые числа i и у между 1 и и, при этом игрок 1 выигрывает величину \i—j\. Игра антагонистическая. Матрица выигрышей этой игры квадрат­ ная, размера (п х и), где ау= \i—j\. Так, если л=4, то матрица А игры

принимает вид

		1	2	3 4
	1 "о		1	2	3
	2	1	0	1	2
	А =3
		2	1	0	1
	4	3	2	1	0

И

Пример 3. (Дискретная игра типа дуэли.) Игроки продвигаются навстречу друг другу на п шагов. После каждого сделанного шага игрок может выстрелить или нет, но во время игры он может выстрелить только один раз. Считается, что вероятность того, что игрок попадает в своего противника, если выстрелит, продвинув­ шись на k шагов, равна fc/n (к^п).

Стратегия игрока 1(2) заключается в принятии решения стрелять на 1-м (/-м) шаге. Пусть i<j и игрок 1 принимает решение стрелять на /-м шаге, а игрок 2 — на у-м шаге. Тогда выигрыш atJ игрока

1 определяется формулой

» Л Л J n(i-j)+ij

Таким образом, выигрыш а^ — это разность вероятностей пораже­ ния противника и собственной гибели в дуэли. В случае i>j первым стреляет игрок 2 и <ху= — <xit. Если же i=j, то полагаем ау =0. Так,

если положить п=5, то матрица этой игры, умноженная на 25, имеет вид

0	- 3	- 7	- 11	- 15
3	0	;	- 2	- 5
А = 7	- 1	0	7	5
11	2	- 7	0	15
15	5	- 5	- 15	0

Пример 4. (Игра «нападение — защита».) Пусть игрок 1 намерен атаковать один из объектов с1, .... с„, которые имеют положитель­ ные ценности тх >0,..., т„>0. Игрок 2 защищает один из этих объек­ тов. Будем считать, что если атакован незащищенный объект с,, то он с достоверностью уничтожается (игрок 1 выигрывает т,), а защи­ щенный — поражается с вероятностью 1 >j8/>0 (объект с( выдержи­ вает нападение с вероятностью 1 — /J/>0), т. е. игрок 1 выигрывает (в

среднем) f}txit i= l, 2, ..., и.

Тогда задача выбора объекта нападения (для игрока 1) и объекта защиты (для игрока 2) сводится к матричной игре с матрицей выигрышей

'РхЧ

0Л

А =

• • Д л

12

Пример 5. (Игра дискретного поиска.) Имеется и ячеек. Игрок

2 прячет предмет в одной из п ячеек, а игрок 1 хочет его найти. При проверке г'-й ячейки игрок 1 тратит т,>0 усилий, при этом вероят­ ность найти предмет в г'-й ячейке (если там он спрятан) равна 0<Д<1, г=1, 2, ..., п. Если предмет найден, то игрок 1 получает доход а. Стратегиями игроков являются номера ячеек, в которых игроки соответственно прячут и ищут предмет. Выигрыш игрока 1 равен разности между ожидаемым доходом и усилиями, затрачен­ ными на поиск предмета. Таким образом, задача поиска и прятания предмета сводится к матричной игре с матрицей выигрышей

•otft-т, - т , - т .

<*Pi-ii -Ч

А =

-т„... а.Рп—4

Пример 6. (Поиск «шумного» объекта.) Предположим, что игрок

1 ведет поиск подвижного объекта (игрок 2) с целью его обнаруже­ ния. Игрок 2 преследует противоположную цель (т. е. стремится уклониться от обнаружения). Игрок 1 может двигаться со скоростя­ ми а, = 1, а,—2, аъ = Ъ, а игрок 2 — соответственно со скоростями Р1 = 1, Р2 = Х /}3 = 3. Дальность действия средства обнаружения иг­ рока 1 в зависимости от скоростей движения участников игры приведена в матрице

Pi Рг Рг

aj |~4 5 6~|

Z>=aJ 3 4 5 a3Ll 2 3J

Стратегиями игроков являются скорости движения, а в качестве выигрыша игрока 1 в ситуации (а,, Д) примем производительность поиска ^=0.^, i = l, 3,у=1, 3, где 8Ц — элемент матрицы D. Тогда

задача выбора скоростей игроков при поиске — уклонении может быть представлена матричной игрой с матрицей

Pi	Рг	Ръ
4	5	6
А = а2 6	8	10
L3	б	9.

13

§2. МАКСИМИННЫЕ И МИНИМАКСНЫЕ СТРАТЕГИИ

2.1.Рассмотрим антагонистическую игру Г=(Х, Y, К). Здесь каждый из игроков выбором стратегии стремится максимизировать свой выигрыш. Но для игрока 1 он определяется функцией К(х, у),

адля второго — (—К(х, у)), т. е. цели игроков прямо противополо­ жны. При этом заметим, что выигрыш игрока 1(2) определен на ситуациях (х, y)eXY, складывающихся в процессе игры. Но каж­ дая ситуация, а следовательно, и выигрыш игрока зависят не только от его выбора, но и от того, какая стратегия будет выбрана против­ ником. Поэтому, стремясь получить возможно больший выигрыш, каждый игрок должен учитывать поведение противника.

Поясним сказанное на примере игры «оборона города». Если игрок 1 хочет получить максимальный выигрыш, то он должен принять стратегию х0 (или х4 ). В этом случае, если игрок 2 приме­ нит стратегию у0(у3), то первый получит выигрыш, равный 4 еди­ ницам. Но если игрок 2 применит стратегию уг (соответственно у0), то игрок 1 получит выигрыш, равный 0, т. е. потеряет 4 единицы. Аналогичные рассуждения можно провести и для игрока 2.

В теории игр предполагается, что оба игрока действуют ра­ зумно, т. е. стремятся к получению максимального выигрыша, считая, что соперник действует наилучшим (для себя) образом. Что может себе гарантировать игрок 7? Пусть игрок 1 выбрал стратегию х. Тогда в худшем случае он выиграет min K(x, у).

Поэтому игрок 1 всегда может гарантировать себе выигрыш max min К(х, у). Если отказаться от предположения достижимости

*у

экстремума, то игрок 1 может всегда получить выигрыш, сколь угодно близкий к величине

r = supinf K(x, у),

(2.1)

- хеХ yeY

которую будем называть нижним значением игры. Если же внешний экстремум в (2.1) достигается, то величина v называется также максимином, принцип построения стратегии х, основанный на мак­ симизации минимального выигрыша,— принципом максимина, а вы­ бираемая в соответствии с этим принципом стратегия х — максиминной стратегией игрока 1.

Для игрока 2 можно провести аналогичные рассуждения. Пусть он выбрал стратегию у. Тогда в худшем случае он проиграет max K(x, у). Поэтому второй игрок всегда может себе гарантиро-

X

вать проигрыш — min max K(x, у). Число

У	х
	v = inf sup K(x, у)	(2.2)

yeY xeX

14

называется верхним значением игры Г, а в случае достижения вне­ шнего экстремума в (2.2) и минимаксом. При этом принцип постро­ ения стратегии у, основанный на минимизации максимальных по­ терь, называется принципом минимакса, а выбираемая в соответст­ вии с этим принципом стратегия у — минимаксной стратегией иг­ рока 2. Подчеркнем, что существование минимаксной (максиминной) стратегии определяется достижимостью внешнего экстремума в (2.2) ((2.1)).

Пусть задана матричная (т х и)-игра Г^. Тогда	экстремумы
в (2.1) и (2.2) достигаются, а нижнее и верхнее значения игры
соответственно равны
» = max mm <ху.	(2.3)
v	(2-4)
» = min max а.

Минимакс и максимин для игры Г^ могут быть найдены по следу­ ющей схеме:

Г<Хц	« и	•Л\п		mm a.\j
Я21	а11	••«2л		i
				min ay	max mm oty=».
					'	S
_*ml «m2		—«mnj		Ш1П СЦу,
	maxon max,2...maxa,n					v
	\ J			f	'
				~v	—
Так, в игре Г^ с матрицей			min max%=v
			j	'

р 0 4~

А =h 3 8

L6 0 1_

нижнее значение (максимин) v и максиминная стратегия i0 первого игрока равны i> = 3, /0=2, а верхнее значение (минимакс) v и мини­ максная стратегия у0 второго игрока — V = 3,j0 = 2.

2.2. Для любой игры Г=(Х, Y, К) справедливо следующее утверждение.

Лемма. В антагонистической игре Г

«<«

(2.5)

или

15

sup inf K(x, y) «ginf sup K(x, y).		(2.6)
xeX yeY	yeY xeX

Доказательство. Пусть xeX— произвольная стратегия игро­ ка ). Тогда имеем

К(х, у) <sup K(x, у).

хеХ

Отсюда получаем

inf K(x, у) <inf sup K(x, у).

yeY

yeY хеХ

Теперь заметим, что в правой части последнего неравенства стоит константа, а значение хеХ выбиралось произвольно. Поэтому вы­ полняется неравенство

sup inf К(х, у) < inf sup K(x, у).

хеХ yeY

yeY хеХ

§3. СИТУАЦИИ РАВНОВЕСИЯ

3.1.Рассмотрим вопрос об оптимальном поведении игроков

вантагонистической игре. Естественно считать оптимальной в игре Г= (X, Y, К) такую ситуацию (х*, у*) еХ- Y, от которой ни одному из игроков невыгодно отклоняться. Такая ситуация (JC*. у*) называ­ ется равновесной, а принцип оптимальности, основанный на постро­ ении равновесной ситуации,— принципом равновесия. Для антагони­ стических игр, как это будет показано ниже, принцип равновесия эквивалентен принципам минимакса и максимина. Конечно, для этого необходимо существование равновесия (т. е. чтобы принцип оптимальности был реализуем).

Определение. В антагонистической игре Г=(Х, Y, К) ситуация (х*, у*) называется ситуацией равновесия или седловой точкой, если

К{х,у*)<К(х*,у*);	(3.1)
К{х*. у)>К{х*. у*)	(3.2)

для всех хеХ и ye Y.

Множество всех ситуаций равновесия в игре Г обозначим через

Z(r),Z(r)cXY.

Для матричной игры Г^ речь идет о седловых точках матрицы выигрышей А, т. е. таких точках (/*, /*), что для всех ieM ujeN выполняются неравенства

а,/ < а^^оц*/.

16

В седловой точке элемент матрицы а,.^ является одновременно

минимумом в своей строке и максимумом в своем столбце. Напри-

"1 0 4~

мер, в игре с матрицей 5	3 8 ситуация (2.2) является равновес­
_6	0 1_
ной.

3.2.Множество ситуаций равновесия в антагонистической игре

Гобладает свойствами, которые позволяют говорить об оптималь­ ности ситуации равновесия и входящих в нее стратегий.

Теорема. Пусть (xf, yf), (jcf, yf) — две произвольные ситуации

равновесия в антагонистической игре Г. Тогда 1) ВД, yt) = K(x*2, yt); К(Х1, у1)=К{х*г, у\); 2)(x*1,y^Z(D,(xtyt)eZ(T).

Доказательство. Из определения ситуации равновесия для всех хеХ и у е Y имеем

Щх, Я)<ед, УГНЦХЬ у);	(3.3)
К(х, Я Х В Д . Я Н В Д . у).	(3.4)

Подставим в левую часть неравенства (3.3) х\,	в правую — у%,
в левую часть неравенства (3.4) — х* и в правую у\.	Тогда получим

ад, я х е д , yiHK(xi, >>!)<ВД, уп^км,	Уп
Откуда следует равенство
K(xl tf ) = В Д , yl)=K(xt, уХ)=К{хХ, yt).	(3.5)

Покажем справедливость второго из утверждений. Рассмотрим си­ туацию (xf, yf). Тогда из (3.3) — (3.5) имеем

К(х, yf)<K(xt, yt) = K(xt, yt) = K(xl y$)^K(xt у)

(3.6)

для всех хеХ, ye Y. Доказательство равновесности ситуации (х*, у*) проводится аналогично.

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

Определение. Пусть (х*, у*) — ситуация равновесия в игре Г. Тогда число

« = К(х*. у*)

(3.7)

называется значением игры Г.

Из второго утверждения теоремы следует, в частности, такой факт. Обозначим X* и Y* проекции множества Z(T) на X и Y соот­ ветственно, т. е.

X* = {х*\х* еX, Зу* е Y, (х*. у*) eZ(Y)},

17

у* = {у*\у* eY,3x*eX, (х*. у*) е	Z(T)}.
Тогда множество Z(T) можно представить в виде
Z ( D = P x P .	(3.8)

Доказательство (3.8), как следствие второго утверждения теоремы, предоставим читателю.

Определение. Множество X*(Y*) называется множеством, оптимальных стратегий игрока 1(2) в игре Г, а его элементы — оптимальными стратегиями игрока 1 (2).

Заметим, что равенство (3.S) указывает на взаимозаменяемость оптимальных стратегий, т. е. любая пара оптимальных стратегий образует ситуацию равновесия, а выигрыш в ней равен значению игры.

33. Оптимальность поведения игроков не изменится, если в игре множества стратегий остаются прежними, а функция выигрыша умножается на положительную константу (или к ней прибавляется постоянное число).

Лемма (о масштабе). Пусть Т=(Х, Y, К) и Г' = (Х, Y, К1) две антагонистические игры, причем

К = РК+ а, р> О, а=const, р=const.	(3.9)
Тогда
Z(T')=Z(r), vr=Pvr+a.	(3.10)

Доказательство. Пусть (х*. у*) — ситуация равновесия в игре Г. Тогда имеем

К'(х*. у*)=РЦх*. у*)+а^рК(х*, у)+а=К'(х*, у), К'(х, у*)=рК(х, у*) + <х*крК{х*, у*) + а=К'(х*, у*)

для всех хеХ и ye Y. Поэтому (х*, y*)eZ$"), Z(T)cZ(r'). Обратно, пусть (х, y)eZ(J"). Тогда

К(х,у)=(11Р)К'(х,у)-а1Р

и, рассуждая аналогично, получаем, что (х, y)eZ(T). Поэтому Z(t)=Z(J"), при этом выполняется равенство

vr=K'(x*, у*)=рК(х*. y*) + a=Pvr+u.

Содержательно данная лемма говорит о стратегической эквива­ лентности двух игр, отличающихся лишь началом отсчета выигры­ шей, а также масштабом их измерения.

3.4. Теперь установим связь между принципом равновесия и при­ нципами минимакса и максимина в антагонистической игре.

Теорема. Для того чтобы в игре Г=(Х, Y, К) существовала

18

ситуация равновесия, необходимо и достаточно, чтобы существова­
ли минимакс и максимин
	min sup К(х, у), max inf K(x, у)					(3.11)
	у	х	х	у
и выполнялось равенство
v=max		inf К(х, у)=min		sup K(x, у)=V.		(3.12)
~	х	у	у х
Доказательство. Необходимость. Пусть {x*,y*)eZ(T). То­
гда для всех хеХ	и ye Y выполняются неравенства
	К(х,у*)^К(х*,у*)^К(х*,у),					(3.13)
отсюда
		supK(x,y*)^K(x*,y*).				(3.14)
Вместе с тем имеем
	inf sup K(x, у) < sup K(x, у*).					(3.15)
	у	х	х
Сравнивая (3.14) и (3.15), получаем
inf sup Цк. y)<sup K(x, y*)^K{x*. у*).						(3.16)
у	х		х
Рассуждая аналогично, приходим к неравенствам
Цх*. у*НМ			К(х*. yHsap		inf K(x, у).	(3.17)
Таким образом,		у		х	у
	inf sup K(x, j>)<sup inf K(x, у).
	у	х	х	у
С другой стороны, всегда вьшолняется обратное неравенство (2.6).
Итак, получаем
	sup inf К(х, у)=inf			sup K(x, у),		(3.18)
	х	у	у	х
при этом неравенства (3.16), (3.17) выполняются как равенства
inf sup K(x, j>) = sup K(x, y*)=K(x*. у*),
у	х		х
sup inf K(x, >0=inf К(х*. у)=К(х*. у*),
х	у		у

19