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

			Г-1/х2, x>y,
	H(x, y)- = <			0,	x=y,
			l	1/У,	x<y
имеет ситуацию равновесия (0, 0).			единичном квадрате с функцией выигрыша
5. Показать,	что игра	на
Н(х, у)*=(х—у)2	не имеет ситуации равновесия в чистых стратегиях.
6. Показать, что в игре на единичном квадрате с функцией выигрыша
			Х+у,	Х?И,		уфО,
	„,	ч	< Х11+У>	хш1>		" * 0 -
			1/2+х, хф\,			>=0,
			2,	х=1, у=0

пара (х„ >>,), где х, = 1 —e,yt=e, является ситуацией е-равновесия. Имеет ли эта игра

значение?
7. Решить игру «поиска шумного объекта», сформулированную в примере 6
п. 1.2.
8. Вычислить выигрыш игрока 1 в игре на единичном квадрате с функцией
выигрыша Н(х, у) в ситуации (F(x), G(y)) (FuG	— функции распределения), если:
а) Н(х, y)=(x+y)/(4xy), F(x)=x*, G(y)=>>2;
б) H(x,y) = \x-y\(l-\x-y\),	F(x) = x, G(y)=y;
в) H(x, y)={x-y)2, F(x) = l/2/0(x)+l/2/1(x),
G(y)=Im{x),
где /jt(x) — ступенчатая функция.

9. Игра дискретного поиска. Рассматривается следующая бесконечная игра. Стра­ тегия игрока 2 заключается в выборе точки, равномерно распределенной на окружно­ сти радиуса у, где у может принимать значения из интервала [0, 1]. Игрок 1 может просмотреть в единичном круге односвязную область Q, площадь которой

e ( 0 = e=const, где а<А, Л = п — площадь единичного круга. Его стратегия х за­ ключается в выборе формы области Q, имеющей площадь а, которая целиком лежит в единичном круге. Выигрыш Н(х, у) игрока 1 равен вероятности обнаружения, т. е. Н(х, y)=Ti(yeQ). Под смешанной стратегией g{y) игрока 2 будем понимать функ­ цию плотности распределения случайной величины >>е[0, 1]. Найти решение игры.

10. Доказать теорему Хелли п. 5.4.

11. Рассмотрим непрерывный аналог игры «обороны города» (п. 1.3 гл. 1). Игрок 1 должен направить силы х, хе[0, 1] в наступление на первую позицию и силы (1-х) — в наступление на вторую позицию. Игрок 2 должен направить силы.у, уе[0, 1] для обороны первой позиции и силы (1 —у) — для обороны второй, на которой уже расположены постоянные оборонительные силы размером 1/2. Один игрок платит другому единицу на каждой позиции, если его силы на этой позиции меньше сил противника, и ничего не платит, если их силы равны.

Построить функцию выигрыша Н(х, у) игры на единичном квадрате. Показать, что данная игра не имеет решения в смешанных стратегиях.

Указание. Воспользоваться результатом примера 10 п. 4.12. 12. Показать, что в непрерывной игре с функцией выигрыша

стратегии F*(x)=Ii/2(x), G*(y)=l/2I0(y) + l/2I2(y) — оптимальны для игроков

1 и 2 соответственно.

ПО

13.Доказать, что значение симметричной непрерывной игры на единичном квадрате равно нулю, а оптимальные смешанные стратегии совпадают (игра симмет­ ричная), если функция выигрыша кососимметрична, т. е. Я (х, у) = —Н(у, х).

14.Определить оптимальные стратегии и значение игры на единичном квадрате

сфункцией выигрыша Н(х, у)=у3 — 3ху+х3.

15.Показать, что в игре с функцией выигрыша

Н(х, у)=еУ y/l-^/y2, хе[х0, xj, уе\у0, ух], у>0,

игрок 2 имеет оптимальную чистую стратегию. Выяснить вид этой стратегии в зави­ симости от параметра у > 0. Что можно сказать об оптимальной стратегии игрока 1.

16. Проверить, что функция выигрыша из примера 11 п. 5.5

Н(х, у)=р(х, у), xeS(0, l), yeS(0, l),

где iS(0, /) — круг с центром в 0 и радиусом /, р(#) —расстояние в R2, строго выпукла по у при любом фиксированном х.

	17. Показать, что сумма двух выпуклых функций выпукла.
	18. Доказать, что если выпуклая функция <р: [а, Д-»/?1 ограничена, то она
	непрерывна в любой точке х е (а, fS). Вместе с тем на концах ни/1 промежутка (а, /J)
	выпуклая функция <р полунепрерывна сверху, т. е.
			lim <p(x)^<p(&)
	(аналогично при х-*Р).		х-*а
		Г=(ЛГ,	Y, Н), X=Y=[0,			1] с выпуклой ограниченной
	19. Пусть дана игра
	функцией выигрыша Н(х, •): [0, \]-*Р1. Показать, что игрок 2 в этой игре имеет либо
	оптимальную чистую стратегию, либо для каждого 8>0 чистую г-оптималъную
	стратегию. Относительно игрока 1 справедлив результат теоремы п. 5.6.
	Указание. Использовать результат упр. 18 и рассмотреть вспомогательную
	игру r0 = (JT, Y, Н0), где	г	я ( х	^	есш у е	^	^
		I lim Я(х, у„), если у=0					или у=\.

20. Решить игру «нападение — защита», сформулированную в упр. 1.

21. Рассматривается одновременная игра преследования на плоскости (см. при­ мер 1 п. 1.2), когда множества стратегий Sl=S2 — S, где S — некоторое замкнутое выпуклое ограниченное множество.

а) Показать, что значение рассматриваемой игры равно R, где R — радиус минимального круга S(0, R), содержащего 5, оптимальная стратегия игрока 2 явля­ ется чистой и заключается в выборе центра О круга S (О, К).

б) Показать, что оптимальная стратегия игрока 1 является смешанной и являет­ ся смесью либо двух диаметрально противоположных точек касания множества S с кругом S (О, R) (если такие точки xt и х2 существуют), либо таких трех точек касания x!v x"2, х'3, что точка О лежит внутри треугольника, вершинами которого являются данные точки.

22. Решить одновременную игру преследования на плоскости, рассмотренную в упр. 21, в предположении, что игрок 2 выбирает не одну точку у е S, а т точек ух ут е S. Функция выигрыша игры имеет вид

Н(х,у)=- 1 т £р2(х,Уд,

где р (•) — расстояние в R2. ты\

23. Игрок / выбирает системы х из т точек промежутка [—1, 1], т. е. х=(£,, ...

..., £„,, £,е[— 1, 1], /=1, ..., т. Одновременно и независимо от него игрок 2 выбирает

111

систему у из п точек того же промежутка [—1, 1], т. е. у = (г\и ..., ri„), ^е[—1, 1],у'=1, 2,

..., п. Функция выигрыша Н(х,	у) имеет вид
Н(х, y) = l/2	I max min |f,—fy|+max		min |£,—t\j\ J.
	^ ' У	j	i	'

Найти решение игры.

24. Рассмотреть обобщение задачи п. 8.3, а именно игру поиска, в которой игрок 2 выбирает систему у из к точек у = {уи ..., Ук) на сфере С, а игрок 1, как и прежде,

систему х из 5 точек x=(Xi, ..., xs) на сфере С. Функция выигрыша имеет вид

Я(х, у)-{М\М=\{у,}\ :yieS(Xj, г);у=1, ..., л},

где 5 (xj, г) — сферический сегмент с вершиной в точке Xj и радиусом основания г; (запись |{у,-}| означает количество точек множества {уг})- Точка >>,- считается об­ наруженной, если yteS{xj, г) хотя бы для одного Xj. Таким образом, значение

функции выигрыша имеет смысл числа обнаруженных точек в ситуации (х, у). Найти решение игры.

ГЛАВА III

НЕАНТАГОНИСТИЧЕСКИЕ ИГРЫ

§1. ОПРЕДЕЛЕНИЕ БЕСКОАЛИЦИОННОЙ ИГРЫ

ВНОРМАЛЬНОЙ ФОРМЕ

1.1.В предыдущих главах были рассмотрены антагонистические игры двух лиц, т. е. игры, в которых интересы сторон прямо

противоположны. Однако реальные задачи принятия решения в условиях конфликта характеризуются большим числом участ­ ников и, как следствие этого, неантагонистичностью конфликтной ситуации. Если говорить о конфликте двух лиц и его моделях, то можно заметить, что он также не исчерпывается только антагони­ стическим случаем. Дело в том, что интересы игроков могут пересе­ каться, но не быть обязательно противоположными. Это, в частно­ сти, может приводить к ситуациям, взаимовыгодным обоим игро­ кам (в антагонистическом конфликте это невозможно), что делает осмысленным кооперирование (выбор согласованного решения), приводящее к увеличению выигрыша обоих игроков. Однако воз­ можны такие конфликты, когда кооперация или соглашение невоз­ можны по правилам игры. Поэтому в неантагонистических играх различают бескоалиционное поведение, когда соглашения между игроками запрещены правилами (см. § 1 — 5), и кооперативное поведение игроков, когда разрешается кооперация типа выбора совместных стратегий (см. § 6 — 8) и совершения побочных плате­ жей (см. § 9 — 11). Рассмотрим первый случай.

1.2. Определение. Система

r=(N, {Xt}leN, {Ht}leN),

в которой N={1, 2, ..., п) — множество игроков, Xt — множество стратегий игрока i, Hi — функция выигрыша игрока i, определенная

п

на декартовом произведении множеств стратегий игроков Х= Y[ Xt

(множество ситуаций игры), называется бескоалиционной игрой.

Бескоалиционная игра и лиц происходит следующим образом. Игроки одновременно и независимо друг от друга выбирают свои стратегии xt из множеств стратегий Хи /=1, 2, ..., и, в результате

ш

чего формируется ситуация х=(х1г ..., хп), xteXt. После этого каж­ дый игрок i получает выигрыш Н, (х). На этом игра заканчивается.

Если множества чистых стратегий игроков X, конечны, то игра

называется конечной бескоалиционной игрой п лиц.

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

Т=(Хи Х2, Ни Н2), где Xt — множество стратегий первого игрока,
Хг — множество стратегий второго игрока, Ху х	Х2 — множество
ситуаций игры, a. H1:XlxX2->Rl, Н2:Хх хX2-*Rl	— функции вы­
игрыша соответственно 1 и 2 игроков. Конечная бескоалиционная

игра двух лиц называется биматричной. Это объясняется тем, что перенумеровав множества чистых стратегий игроков числами 1, 2,

..., т и 1, 2, ..., п соответственно, функции выигрыша можно записать в виде двух матриц

4 1 - •&\п
Ht=A =	н2=в=
_ * m l " "&mn	-.Рт\"'Ртп_

При этом элементы ау и /?у матриц А, В являются соответственно

выигрышами игроков 1я2в ситуации (i,j), ieM,jeN, M= {1,..., m},

#={1,...,й}.

В соответствии с изложенным выше биматричная игра проис­ ходит следующим образом. Первый игрок выбирает номер i строки, а второй (одновременно и независимо) номер j столбца матрицы. Тогда игрок 1 получает выигрыш щ=Нх (хи у^, а игрок 2 — выиг­

рыш #,-#2 (х,, у]).

Заметим, что биматричную игру с матрицами А и В можно также задать (т х и) матрицей (А, В), каждый элемент которой есть

пара (аф fiij),	г'=1, 2, ..., т; j=\,	2, ..., п. Игру, определяемую
матрицами An	В, будем обозначать Г {А, В).		такова, что Н1(х,
Если бескоалиционная игра Г двух лиц
у)=—Н2 (х, у) для всех хе Хи уеХ2, то Г оказывается антагонисти­
ческой игрой,	рассмотренной в	предыдущих	главах. В частном

случае, когда в биматричной игре ац=—^ц, мы получаем матрич­ ную игру, рассмотренную в гл. 1.

1.4. Пример 1. («Семейный спор».) Рассматривается биматричная

игра с матрицей
_	01	02 _
(Л л - в 1 Г ( 4 , 1 )		(0'0)
( Л ' * } - « 2 | ( 0 ,	0)	(1,4)

114

Имеются различные интерпретации этой игры, но наиболее извест­ ная [44] следующая. Муж (игрок 1) и жена (игрок 2) могут выбрать одно из двух вечерних развлечений: футбольный матч (а1; ^) или

театр (<х2, /J2). Если они имеют разные желания (al5 /J2) или (а2, /?t), то остаются дома. Муж предпочитает футбольный матч, а жена —

театр. Однако обоим гораздо важнее провести вечер вместе, чем участвовать в развлечении (хотя и предпочтительном) одному.

Пример 2. (Игра «перекресток» [10] J Два автомобилиста двига­ ются по двум взаимно перпендикулярным дорогам и одновременно встречаются на перекрестке. Каждый из них может остановиться (1-я стратегия ах или /^) и ехать (2-я стратегия а2 или /?2).

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

<х2[_(2, 1-е)

(0, 0)

(неотрицательное число е соответствует неудовольствию от того, что игрок остановился и пропустил партнера).

Пример 3. (Выбор способа передвижения /io городу [10]J Пусть число игроков п велико и каждое из множеств X, состоит из двух

элементов: ^,={0, 1} (для определенности: 0 — воспользоваться

автомобилем, 1 — использовать общественный транспорт). Функ­ ция выигрыша определяется следующим образом:

Hi(xu

..., л;„)=

a(t)

при х,=

1,

b(t)

при х, = 0,

где /=

:

'J-I

н

Пусть а и Ъ имеют вид, изобра­

4 но

женный на рис. 8. Из вида функций

a(t) и b{i) следует, что если доля иг­

/

роков,

выбирающих 1, больше

tv то

1

'

/ а(1)

уличное движение настолько свободно,

'

/

/

/

что водитель чувствует себя лучше,

чем пассажир в общественном транс­

а(0)

/ / 1

1

порте. Если же доля автомобилистов

больше

1 —/0, то

движение настолько

1(0)

/

1

1

интенсивное (при

естественном

при­

/

1

1

оритете

общественного

транспорта),

и

t„

t,

1 't

что сравнение теперь в пользу пасса­

жиров общественного транспорта.

Рис. 8

115

Пример 4. (Распределение ограниченного ресурса с учетом ин~ тересов потребителей [52]J Предположим, что п потребителей имеют возможность расходовать (накапливать) некоторый ресурс, объем которого ограничен величиной А>0. Обозначим объем ресурса, который расходует (накапливает) i-й потребитель, через х,.

В зависимости от значений вектора х=(хи х2, ..., х„) потребители

получают выигрыш, который оценивается для i-ro потребителя функцией hi{xu x2, ..., х„), если общий объем израсходованного

(накопленного) ресурса не превосходит заданной положительной величины 6<А, Т. е.

я

Если выполняется противоположное неравенство, то выигрыш г'-го

потребителя вычисляется с помощью функции gt(xlt x2

х„). При

этом предполагается, что полезность ресурса резко снижается, если

л

£ xt>0, т. е. в этом случае

i - l

gi(xt, x2,..., xa)<h,(xv x2,..., хя).

Рассмотрим неантагонистическую игру в нормальной форме Г=(#, {Х,},е„, {Ht}leN),

в которой функции выигрыша игроков имеют вид

	л
	Ы(х1г ..., х„), £	Xi^d,
" i V * l > *2> •"' ^л) =	1-1
	л
	i-l
	л	и}.
Х,=[0, а], 0<а,<Л, £ а,=А, N={1, 2

Игроками в этой игре являются потребители ресурса.

Пример 5. (Теоретико-игровая модель охраны воздушного бассей­ на от загрязнений [52]J В промышленном районе расположено

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

116

q= £ см, i=\, 2, ..., n, 0<*,<<!;.

1-Х

Пусть в < Y, c&i — значение предельно допустимой концентрации

(ПДК) вредной примеси.

Считая предприятия игроками, построим игру, моделирующую конфликтную ситуацию загрязнения атмосферы. Предположим, что каждое предприятие i может снижать свои эксплуатационные рас­ ходы, увеличивая выброс х,, однако если в зоне Q уровень загрязне­ ния превышает ПДК, на предприятие накладывается штраф 5,>0.

Пусть игрок / (предприятие) имеет возможность выбирать зна­ чения Л:, ИЗ множества Xt=[0, а]. Функции выигрыша игроков

имеют вид

{h,(xlt x2, ..., х„), q^d, ft,(*i> х2, ..., x„)-s{, q>V,

где A,(xl5 x2, ..., х„) — непрерывные и возрастающие по аргументу х, функции.

§ 2. ПРИНЦИПЫ ОПТИМАЛЬНОСТИ В БЕСКОАЛИЦИОННЫХ ИГРАХ

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

Естественно предположить, что в игре Г каждый из игроков стремится к достижению ситуации х, в которой значение его функ­ ции выигрыша было бы наибольшим. Однако функция выигрыша Я, зависит не только от стратегии /-го игрока, но и от стратегий, выбираемых другими игроками, поэтому ситуации {х}, дающие большее значение выигрыша для f-ro игрока, могут не быть таковы­ ми для других игроков. Таким образом, так же как и в случае антагонистической игры, стремление игроков получить наибольший выигрыш носит конфликтный характер и сама формулировка того, какое поведение является «хорошим» или оптимальным в игре, является проблематичной. Здесь имеется несколько подходов. Од-

117

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

Пусть х—{хх, ..., *;_!, х,, xi+i, ..., х„)— произвольная ситуация в игре Г, а х,- — некоторая стратегия игрока i. Построим ситуацию, которая отлична от х только тем, что стратегия х,- игрока i заменена на стратегию х\. В результате мы получаем ситуацию (х1;..., х,_], xj,

Xi+u —> х„), которую будем обозначать через (x||xj)- Очевидно, что если х, и xj совпадают, то (x||xj)=x.

Определение. Ситуация x*=(xf, ..., xf, ..., х*)	называется
ситуацией равновесия по Нэшу, если для всех x^XjU	i=l,.... п имеет
место неравенство
Я,(х*)^Я,(х*||х;).	(2.1)

Пример 6. Рассмотрим игру примера 3 п. 1.4. Равновесными по Нэшу здесь являются ситуации, для которых выполняется условие

	t0^t*-l/n, t* + l/n^tu	(2.2)
л	Из условия (2.2) следует, что	переключение
где f*=(l/n) Y, ХТ-
7-1	„

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

Пусть в игре реализовалась ситуация х, которой соответствует

t=(l/ri) £ Xj, te{t0, tj], и пусть величина «5 — доля игроков, реши­ вших переключиться со стратегии 0 на стратегию 1. Заметим, что если 8 таково, что b(t) = a(t)<a(t+8), то выигрыши этих игроков увеличиваются при таком переключении, если стратегии остальных игроков останутся прежними. Однако если это переключение дейст­ вительно произойдет, то у тех же игроков возникает желание пере­ ключиться со стратегии 1 на стратегию 0, поскольку выполнено условие a (t+8)<b(t+5). Если же это желание осуществится, то

доля (1/и) • £ xj игроков уменьшится и вновь попадет на отрезок

[*0, hi

Аналогично, пусть д — доля игроков, переключившихся по ка­ ким-либо причинам (например, из-за случайных ошибок) со страте­ гии 1 на стратегию 0, причем t—8<t0. Тогда в силу условия b(t—8)<a(t~ 8) у игроков появится желание переключиться обрат­ ив

но на стратегию 1. При осуществлении этого желания доля

л

1/и • Y, XJ увеличится и вновь вернется на отрезок [/0, /J.

2.2. Из определения ситуации равновесия по Нэшу следует, что ни один из игроков i не заинтересован в отклонении от стратегии х*, входящей в эту ситуацию (согласно (2.1) его выигрыш при исполь­ зовании стратегии xt вместо xf разве лишь уменьшится при усло­ вии, что остальные игроки придерживаются стратегий, образующих ситуацию равновесия х*). Таким образом, если игроки договори­ лись предварительно об использовании стратегий, входящих в ситу­ ацию равновесия JC*, TO индивидуальное отклонение от договора невыгодно отклонившемуся игроку.

Определение. Стратегия xfeXj называется равновесной, если
она входит хотя бы в одну ситуацию равновесия по Нэшу.
Для бескоалиционной игры двух лиц r = (Zl5 Х2, Ни		Н?) ситу­
ация (х*, у*) является ситуацией равновесия, если неравенства
Н, (х, y*HH, (х*, у*), Н2(х*, уНН2(х*, у*)		(2.3)
выполняются для всех xeXt	uyeY2.
В частности, для биматричной (т хи)-игры Г (Л, В) пара (г*, /*)
будет ситуацией равновесия по Нэшу, если неравенства
«<./<«!••/, &•></?•*/		(2-4)

выполняются для всех номеров строк ieM и столбцов jeN. Так,
в примере 1 равновесными являются ситуации (<х19	/?х) и (а2, /?2),
в примере 2 — (о^, fl2) и (а2, fix)-	Г1 г	, Н) пара
Напомним, что для антагонистической игры Г = (Л , Х
(х*, y*)eXt хХ2 является ситуацией равновесия, если

Н(х, у*НН(х*, у*)^Н(х*, у), хеХи уеХ2.

При этом имеют место следующие основные свойства антагонисти­ ческих игр.

I0'. Игроку невыгодно информировать своего противника о стратегии (чистой или смешанной), которую он собирается приме­ нить. (Конечно, если игрок собирается использовать оптимальную стратегию, то его выигрыш не уменьшится от того, что он объявит об этом, но он ничего и не выигрывает.)

2°. Если (х, y)eZ(T), (JC', / ) e Z ( r ) — ситуации равновесия в игре Г, a v — значение игры, то

V,y)eZ(T),(x,/)eZ<r);	(2.5)
v=H(x, y)=H(x', y') = H(x, /)=#(*', у).	(2.6)

3°. Игроки не заинтересованы в общении перед началом игры для выработки совместных действий.

119