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

Из леммы п. 4.3 следует, что (х*. y*)eZ(YA) — ситуация равно­ весия в игре Гл< в смешанных стратегиях, а значение игры равно vA=vA — ^ = l/e—p. Теорема доказана.

Неформально факт существования решения в классе смешанных стратегий означает, что игроки всегда могут снять неопределен­ ность выбора стратегии, с которой они столкнулись перед началом игры, рандомизируя множество чистых стратегий. Следует отме­ тить, что не всегда в антагонистических играх существует решение в смешанных стратегиях. Примеры таких игр с бесконечным числом стратегий приведены в § 3, 4 гл. И.

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

1. По матрице А	строится строго положительная матрица
А = А' + В, где В={ри},	p,j=p>0.

2.Решаются задачи линейного программирования (6.1), (6.2). Находятся векторы х, у и число в [см. 6.3)].

3.Строятся оптимальные стратегии игроков 1 и 2 соответ­ ственно

х* = х1в,у*=у/в.

4. Вычисляется значение игры Г^

Пример 8. Рассмотрим матричную игру ГА, определенную мат­ рицей

-Б 3

Соответствующие ей задачи линейного программирования имеют следующий вид:

min^ + ^2,		max^+f/2,
4£	1+2£2>1,	4ij!<l,
3{	2>1,	2»h + 3ij2<l,

Заметим, что эти задачи в эквивалентной форме могут быть записа­ ны для ограничений типа равенств:

min^ + ij,	max ^+7/2,
4£1+2£2-£з = 1,	4 ^ + ^з = 1,

30

3£2-£4=1>	2 ^ + 3 ^ + ^ = 1 ,
£i>0, £2^0, Z3>0, £4>0,	п^О, t,2>0, т]2>0,

Таким образом, любой метод решения задач линейного про­ граммирования может быть приспособлен для решения матричных игр. Наиболее распространенным методом решения таких задач является симплекс-метод, систематическое изложение которого мо­ жно найти в [16, 25, 73].

6.2. Задача линейного программирования в определенном смыс­

ле эквивалентна матричной игре Гл.		Действительно, рассмотрим
следующие прямую и двойственную задачи линейного програм­
мирования
	minxu	(6.9)
	xA^w,
	х>0;
	maxyw	(6.10)
	Ау^и,
	у>0.
Пусть X и Y — множества оптимальных решений задач (6.9) и (6.10)
соответственно. _	Обозначим	(11в)Х={х/в\хеХ},

(\1в)¥={у1в\уе¥},в>0.

Теорема. Пусть Гл — (тхп)-игра с положительной матрицей А (все элементы положительны) и даны две двойственные задачи линейного программирования (6.9) и (6.10). Тогда имеют место сле­ дующие утверждения.

1. Обе задачи линейного программирования имеют решение (ХФ0 и УФ0), при этом

0=min хм=max yw.

ху

2.Значение vA игры ГА равно

астратегии

х* = х16,у*=у1в,

являются оптимальными, где хеХ — оптимальное решение прямой

задачи (6.9), ayef— двойственной задачи (6.10).

3. Любые оптимальные стратегии х*еХ* и y*eY* игроков мо­ гут быть построены указанным способом, т. е.

Х* = (1/в)Х, Г* = (1/в)?.

Доказательство. Утверждения 1, 2 и включения (\l&)XczX*,

31

l/OYczY* непосредственно следуют из доказательства теоремы п. 6.1.

Покажем обратное включение. Для этого рассмотрим векторы

х* = (Л*. •••> &)еХ* и х=(^, .... 1т), где х=0х*. Тогда для всех jeN имеем

xaJ=Bx*aJ> 0(1/0)= 1,

при этом х>0, так как б>0 и х*>0. Поэтому х— допустимое решение задачи (6.9).

Вычислим значение целевой функции

хи=вх*и = в=min xu,

X

т. е. хеХ— оптимальное решение задачи (6.9).

Аналогично доказывается включение Y*cz(l/0)Y. Теорема до­ казана.

§ 7. СВОЙСТВА ОПТИМАЛЬНЫХ СТРАТЕГИЙ И ЗНАЧЕНИЯ ИГРЫ

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

7.1. Пусть (х*, у*)еХх		Y— ситуация в смешанных стратегиях
в игре Г^. Оказывается, что для проверки ситуации (х*, у*) на
равновесность неравенства (4.7) достаточно проверять не для всех
хеХ и yeY,	а лишь для	ieM	и jeN, поскольку		справедливо
следующее утверждение.
Теорема. Для того чтобы ситуация (х*, у*) была равновесной
в игре ТА, а число v=K(x*. у*) —значением				игры Тл	необходимо
и достаточно выполнение следующих неравенств					для всех ieM
njeN:
	K(i,y*)*ZK(x*,y*)^K(x*,j),				(7.1)
Доказательство. Необходимость. Пусть (х*, у*) — ситу­
ация равновесия в игре Г^. Тогда
	К(х,у*)^К(х*,у*)*Щх*,у)
для всех xeX.yeY. Поэтому, в частности, для щеХл					и^е У имеем
K(i, y*)=K(uit y*)^K(x*,			у*НЦх*.	Wj) = K(x*,j)
для всех ieM	ujeN.

Достаточность. Пусть (х*, у*) — пара смешанных стратегий, для которой выполняются неравенства (7.1). Пусть также х=(£19 ...

..., £т)еХя y = (rjit .... q„)e Y— произвольные смешанные стратегии игроков 1 и 2 соответственно. Умножая первое и второе неравенства (7.1) на & и г\} соответственно и суммируя, получаем

32

£	{,Щ у*)^ Цх*. у*)% Ъ = К(х*, у*);	(7.2)
£	r,jK(x*,j)>K(x*, у*) £ r,j=K(x*, у*).	(7.3)
j-l	У-i
При этом имеем
	£ Mi, >*)=*(*, у»);	(7.4)
	/ - 1
	t^^*,;) =^*,j;).	(7.5)

j-i

Подставляя (7.4), (7.5) в неравенства (7.2) и (7.3) соответственно и учитывая произвольность стратегий хеХя ye Y, получаем равно­ весность ситуации (х*. у*).

Следствие 1. Пусть (f, j*) — ситуация равновесия в игре ГА. Тогда ситуация (/*, j*) равновесна и в игре ГА.

Пример 10. (Решение игры на уклонение.) Предполагается, что игроки выбирают целые числа / иУ между 1 и п, а игрок 1 выигрыва­ ет величину а.1Л=\1—j \ , т. е. расстояние между числами / и /

Пусть	первый игрок придерживается			стратегии х* = (1/2, 0, ...
..., 0, i/2).	Тогда
K(x*,j)=\l2\\-j\		+ l/2\n-j\	= \l2(j-l)	+	ll2(n-j)=(n-W
для всех 1</^и.		— нечетно. Тогда игрок 2 имеет чистую стра­
а) Пусть n=2k+1
тегию j * = (п +1 )/2 = к+1 такую, что
	o^ = |i-(n + l)/2| =		| i - * - l | < b = ( n - l ) / 2

для всех /=1, 2, ..., п.

б) Предположим, что п = 2к — четно. Тогда игрок 2 имеет та­

кую стратегию у* = (0, 0, ...,

х

2

.

1

2

к

2

+ =

1

/

2

>

/

/

, 0, ..., 0), где г\

=Ч

, >7*1

rij = 0,j^k + l,j^k, что

Щ У*) = 1/21i-k|.+1/21i-k-11<1/2*+

l/2(fc-1) = (л-1)/2

для всех 1</<и.

Теперь, используя теорему, нетрудно убедиться, что значение игры v = (n—1)/2, игрок / имеет оптимальную стратегию х*, а оп­ тимальная стратегия игрока 2 равна j * , если и=2£+1, и у*, если

п= 2к.

7.2.Приведем результаты, являющиеся непосредственным след­ ствием теоремы п. 7.1.

Теорема. Пусть ГА — (тхп)-игра. Для того чтобы ситуация в смешанных стратегиях (х*, у*) была равновесной в игре ГА, необ-

33

ходимо и достаточно выполнение равенства

max K(i, у*) = min K(x*. j).

(7.6)

Доказательство. Необходимость. Если (х*. у*) — ситуа­ ция равновесия, то согласно теореме п. 7.1 имеем

K(i,y*)^K(x*,y*HK(x*,j)

для всех /б{1, ..., m},je{l, ..., и}. Поэтому

K(i,y*HK(x*,j)

для каждого i и / Предположим противное, т. е. (7.6) не выполнено.

Т о г д а	max Щ, у*) < min K(x*. j).
Следовательно, имеют место неравенства
К(х*. у*)= £	£Щ y*)*Z max Щ, у*)< min K(x*,j)^
	^£ri;K(x\j)	= K(x*,y*).

j-1

Полученное противоречие и доказывает необходимость утвержде­ ния теоремы.

Достаточность. Пусть пара смешанных стратегий (х, у) тако­ ва, что max K(i, y)=min K(x, j). Покажем, что в этом случае

/j

(х, у) — ситуация равновесия в игре ГА. Справедливы соотношения

	л
min Щ,	j)^^fjj	K(x, J)=К(х, у) =
= £	№ • Ж	max Щ	у).
Поэтому имеем
Щ, JO^max K(i, y)=K(x, y)=min			K(j, x)^K(x,j)
i		J

для всех 1«% i^m и^.</<и, тогда по теореме п. 7.1 (х, у) — ситуация

равновесия в игре Г^.

Из доказательства следует, что любое из чисел в (7.6) равно значению игры. _

7.3. Теорема. Для матричной игры YA справедливы следующие соотношения:

max min K(x, j)=vA=min		max K(i, у),	(7.7)
x j	у	i

34

причем экстремумы по смешанным стратегиям хиу в (7.7) достига­ ются на оптимальных стратегиях игроков.

Теорема является следствием теорем п. 3.4, 7.2, и ее доказатель­ ство предоставляем читателю.

7.4. Теорема. В матричной игре ГА множества оптимальных смешанных стратегий X* и Y* игроков являются выпуклыми много­ гранниками.

Доказательство. Согласно теореме п. 7.1 множество X* явля­ ется множеством всех решений системы неравенств

xaJ'^vA,jeN, хи=1,

х>0,

где и=(1, ..., \)eRm, vA—значение игры. Таким образом, X*— выпуклое многогранное множество (п. 5.1). С другой стороны, Х*<^Х, где X — выпуклый многогранник (п. 5.3). Поэтому X* — ограничено. Следовательно, по теореме п. 5.3 множество X* — вы­ пуклый многогранник.

Аналогично доказывается, что У* — выпуклый многогранник. 7.5. 6 качестве примера использования теоремы п. 7.3 приведем геометрическое решение игр с двумя стратегиями у одного из игроков ((2 х и)- и (т х 2)-игры). Такой подход в литературе также

называется графоаналитическим методом решения игр. В основе графоаналитических методов лежит свойство оптимальных страте­ гий х* и у* доставлять внешние экстремумы в равенстве

»4=max min K(x,j)=mm max K(i, у).

X J У I

Пример 11. ((2 x п)-игра). Рассмотрим игру, в которой игрок 1 имеет две стратегии, а игрок 2 — и стратегий. Матрица имеет вид

а 1 1	«12 - а1»"|
[а 21	а 22 "• a2nJ

Пусть игрок 1 выбрал смешанную стратегию х=(£, 1 —£), а иг­ рок 2 чистую стратегию jeN. Тогда выигрыш игрока 1 в ситуации

(х, J) равен

Kix.j^faMl-Ovy. (7.8)

Геометрически он представляет собой прямую в координатах (€, К). Таким образом, каждой чистой сратегии j соответствует своя прямая. Графиком функции

H(£)=mmK(.x,j)

35

является нижняя огибающая семей­ ства прямых (7.8). Эта функция вог­ нута как нижняя огибающая семей­ ства вогнутых (в данном случае ли­ нейных) функций (п. 5.5). Точка £*, в которой достигается максимум фу­ нкции Н{£) по £ е [0, 1], и дает требу­ емое оптимальное решение х* = (£*, 1 — £*) и значение игры vA=H(£,*).

Для определенности рассмотрим игру с матрицей

			Л~	2	1 4 О
		Для каждого j= 1, 2, 3, 4 имеем:
	К(х, 1)= - £ + 2, /фс, 2) = 2£+1, /фс,
	3;= - 3^+4, Дх, 4J=4£. Нижняя
рис 1	огибающая			#(£)	семейства прямых
	{Щх, j)}		и	сами прямые		К(х, j),
	j=\,	2,	3,	4, изображены		на рис.
1. Максимум #(£*) функции //(О находится на пересечении первой
и четвертой прямых. Таким образом, £* — решение уравнения
Откуда получаем	оптимальную	стратегию х* = (2/5, 3/5)				игрока

1 и значение игры vA — S/5. Оптимальную стратегию игрока 2 най­ дем из следующих соображений. Заметим, что в рассматриваемом случае К(х*. 1)=К(х*. 4)=«< = 8/5.

Для оптимальной стратегии y* = (tj\, г\г, т/3, т/4) должно выпол­ няться равенство

vA = K{x*. у*) = ц\ К(х*. l) + ri'2 К{х*, 2)+т/3 К(х*. 3) + т,4 Цх», 4).

При этом К(х*, 2)>8/5, К(х*, 3)>8/5, следовательно, 7/2 = 1/3 = О, а г\\, т/4 можно найти из условия (7.1)

ц\ + 4т,;= 8/5,

27,1 = 8/5.

Таким образом, 7/1 = 4/5 и т/4=1/5 и оптимальная стратегия игрока 2 равная* = (4/5, 0, 0, 1/5).

Пример 12. ((т х Ту-игра.) В этом примере Две стратегии имеет игрок 2, а игрок 1 — т стратегий. Тогда матрица А имеет вид

^а1Х	а,
	4 2
*21	«•22
Л =
а т1	0^2

36

Анализ этой игры проводится аналогично. Действительно, пусть

У ==(?/, 1 — TJ) — произвольная смешанная стратегия игрока 2. Тогда выигрыш игрока 1 в ситуации (i, у) равен

K(i, у)=ацГ1 + ап(1-г1) = (ап-а,п)г1 + аа-

График функции K(i, у) — прямая. Рассмотрим верхнюю огиба­ ющую этих прямых, т. е. функцию

H(ri)=max [(a,, - аа)п + a j .

i

Функция H{r\) выпуклая (как верхняя огибающая семейства выпук­ лых функций).

Точка минимума п* функции Н(п) дает оптимальную стратегию у* = (?/*, l — ri*) и значение игры vA=H(n*) = min Н(п).

, , „	„	<J6 [0. 1]
7.6. Приведем результат, полезный при отыскании решения
игры.
Теорема. Пусть х* = (£\,.... О яу* = (п\,..., п'^ — оптимальные
стратегии в игре ГА	и vA — значение игры. Тогда для любого i, при
котором K(i, y*)<vA,	имеет место равенство £*=0, а для любого
j такого, что vA<K(x*,j), имеет место равенство п]=0.
Обратно, если £*>(), то K(i, y*)=vA,		а если n)>Q, то K(x*,j)=vA.

Доказательство. Допустим, что для некоторого /0еД/ выпол­ нено K(i0, y*)<vA и при этом £*0#0. Тогда получаем, что

K(i0,y*K<vAil

Для всех ieM K(i, y*)^vA, поэтому

K(i,y*)£^vAC

Следовательно, К(х*. y*)<vA, что противоречит тому, что vA — зна­ чение игры. Вторая часть теоремы доказывается аналогично.

Этот результат является аналогом теоремы о дополняющей нежесткости [73] или, как ее еще называют, канонической теоремой равновесия для задачи линейного программирования [25].

Определение. Чистая стратегия ieM(jeN) игрока 1 (2) назы­ вается существенной или активной стратегией, если существует оптимальная стратегия х* = (£,\, .... \*„) (у* = (п\, .... пп)) этого игрока, для которой £>0 (fy>0).

Из определения и последней теоремы следует, что для каждой существенной стратегии i игрока 1 и любой оптимальной стратегии y*eY* игрока 2 в игре Г^ выполняется равенство

K(i,y*)=ao>*=vA.

Аналогичное равенство имеет место для любой существенной стратегии j eN игрока 2 и оптимальной стратегии х* еХ* игрока 1

37

K(x*,j) = aJx*=vA.

Если для чистой стратегии ie M и смешанной стратегии уе У выпол­ няется равенство a{y=vA, то говорят, что стратегия i уравновешива­ ет смешанную стратегию у в игре Г^.

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

Знание спектра оптимальной стратегии упрощает нахождение решения игры. Действительно, пусть Мх> — спектр оптимальной

стратегии JC* игрока 1. Тогда каждая оптимальная стратегия у*= (г\\, .... г\*„) игрока 2 и значение игры v удовлетворяют системе

неравенств	aor*=v, ieM*.,

При этом в спектр М* любой оптимальной стратегии х* могут

входить лишь существенные стратегии.

7.7. В заключение параграфа приведем аналитическое решение игры «нападение — защита» (см. пример 4 п. 1.3)

Пример 13. Рассмотрим игру с(лхи) матрицей А

7*1*1 Ч ... Tj

А = чЯ2 ^ 2

ЧА. %.

Здесь	т,>0 — ценность,	а	0</?,<1—вероятность	поражения
объекта Q, /=1, 2, ..., л, при условии, что он защищен. Пусть
т1<т2	<...<т)1. Определим	функцию ср от целых чисел 1, 2, ...
..., п следующим образом:
	?(*)=[£ (WO^-lj^Ml-u)}-1,			(7.9)
и пусть /е{1, 2, ..., л} — целое число, доставляющее				максимум
функции (р(к), т. е.
	(р(1)=		max q>(k).	(7.10)

к~\, 2,

Установим свойства функции (р(к). Обозначим символом R один из знаков отношения порядка {>, =, <}. В этом случае

38

		<p(k)R(p(k+\)			(7.11)
тогда и только тогда, когда
	•zkR(p(k), k=\,		2, ..., п-1,	т0 = 0.	(7.12)
Действительно, из (7.9) получаем
<№	О - А)" 1	, ,.ч	,. , 1Ч ,	(1-АГ1

I	fofl-A)}-1	I fod-ft)}-1
i-Jfc+1		j-Jt-fl
Тогда имеем

И - l l	. " - М " +?(*)=.(*+!)•	(7.13)
L " J	Е Mi-ft»"'

i«*+l

Заметим, что коэффициент в (7.13), стоящий после квадратных скобок, положительный. Поэтому из (7.13) получаем эквивалент­ ность соотношений (7.11) и (7.12).

Теперь так как q>(l)^(p(l—l) или <р(/)>ф(/+1) (в этом случае т,_1<ф(/—1) или т,>ф(0), то из соотношений (7.10), (7.11) имеем

неравенство	(7.14)
т,_,<ф(0<тА

Найдем оптимальные стратегии в игре Г^. Напомним, что мы

предполагаем выполненными неравенства т1 <т2 ^...^тп . Тогда оп­
тимальными смешанными стратегиями х* = (£,\,		.... £*т) и y* = (t]\,
.... r\J игроков 1 и 2 соответственно являются следующие:
0, «=1, .... / - 1 ,
{	/"	(7 15)
Wi-ft)]"1 /! fed-/»/)]-1, '='--. «;
•	f<W=i / - 1 ,
^	ЦТУ-Ф((Я/М1-ДЙ, у-/, .... и.	( - J
а значение игры равно

«л = <?(%>•

л

Действительно, ^'^0, i= 1, 2,..., п и £ £*= 1 • Из определения <р(/)

л

и (7.14) получаем, что rjj^0,j=l, 2, ..., л и ^ ^*=1-

Пусть K{x*,j) — выигрыш игрока 1 в ситуации (x*,j), аналогич­ но K(i, у*) — выигрыш в ситуации (i, у*).

39