Петросян Л.А. и др. Теория игр

Подождите немного. Документ загружается.

Г-1/х

, x>y,

H(x, y)-

= <

0, x=y,

l 1/У, x<y

имеет ситуацию равновесия (0, 0).

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

Н(х,

у)*=(х—у)

не имеет ситуации равновесия в чистых стратегиях.

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

Х+у, Х?И, уфО,

„,

ч <

У>

хш1

> "*

1/2+х,

хф\, >=0,

х=1, у=0

пара (х„

>>,),

где

х,

—e,y

=e, является ситуацией е-равновесия. Имеет ли эта игра

значение?

Решить игру «поиска шумного объекта», сформулированную в примере 6

п. 1.2.

8. Вычислить выигрыш игрока 1 в игре на единичном квадрате с функцией

выигрыша Н(х, у) в ситуации (F(x), G(y)) (FuG

—

функции распределения), если:

а) Н(х, y)=(x+y)/(4xy), F(x)=x*, G(y)=>>

;

б) H(x,y)

\x-y\(l-\x-y\),

F(x) =

G(y)=y;

в) H(x, y)={x-y)

, F(x) = l/2/

(x)+l/2/

(x),

G(y)=I

{x),

где /jt(x) — ступенчатая функция.

Игра дискретного

поиска.

Рассматривается следующая бесконечная игра. Стра-

тегия игрока

заключается

выборе точки, равномерно распределенной на окружно-

сти радиуса у, где у может принимать значения из интервала [0, 1]. Игрок 1 может

просмотреть в единичном круге односвязную область Q, площадь которой

e(0

e=const, где а<А,

Л = п

— площадь единичного круга. Его стратегия х за-

ключается

выборе формы области

имеющей площадь

а,

которая целиком лежит

в единичном

круге.

Выигрыш Н(х, у) игрока

равен вероятности обнаружения, т. е.

Н(х, y)=Ti(yeQ). Под смешанной стратегией g{y) игрока 2 будем понимать функ-

цию плотности распределения случайной величины

>>е[0,

1].

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

10.

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

11.

Рассмотрим непрерывный аналог игры «обороны города» (п. 1.3 гл.

1).

Игрок

1 должен направить силы х, хе[0, 1] в наступление на первую позицию и силы

(1-х)

—

в наступление на вторую позицию. Игрок

должен направить силы.у, уе[0,

1] для обороны первой позиции и силы

(1 —у) —

для обороны второй, на которой

уже расположены постоянные оборонительные силы размером 1/2. Один игрок

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

сил противника, и ничего не платит, если их силы равны.

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

что данная игра не имеет решения в смешанных стратегиях.

Указание. Воспользоваться результатом примера 10 п. 4.12.

12.

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

стратегии F*(x)=Ii/

(x),

G*(y)=l/2I

(y)

l/2I

(y)

— оптимальны для игроков

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

ПО

13.

Доказать, что значение симметричной непрерывной игры на единичном

квадрате равно нулю, а оптимальные смешанные стратегии совпадают (игра симмет-

ричная), если функция выигрыша кососимметрична, т. е. Я

(х,

у) =

—Н(у,

х).

14.

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

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

—

3ху+х

15.

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

Н(х, у)=е

y/l-^/y

хе[х

, xj, уе\у

, у

], у>0,

игрок 2 имеет оптимальную чистую стратегию. Выяснить вид этой стратегии в зави-

симости от параметра

у > 0.

Что можно сказать об оптимальной стратегии игрока 1.

16.

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

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

l),

yeS(0, l),

где iS(0, /)

—

круг с центром в 0 и радиусом /, р(

) —расстояние в R

, строго

выпукла по у при любом фиксированном х.

17.

Показать, что сумма двух выпуклых функций выпукла.

18.

Доказать, что если выпуклая функция

<р:

[а, Д-»/?

ограничена, то она

непрерывна в любой точке х

(а,

fS).

Вместе с тем на концах ни/1 промежутка (а, /J)

выпуклая функция

<р

полунепрерывна сверху, т. е.

lim

<p(x)^<p(&)

х-*а

(аналогично при

х-*Р).

19.

Пусть дана игра Г=(ЛГ, Y, Н), X=Y=[0, 1] с выпуклой ограниченной

функцией выигрыша Н(х,

•):

[0,

\]-*Р

. Показать, что игрок

в этой игре имеет либо

оптимальную чистую стратегию, либо для каждого 8>0 чистую г-оптималъную

стратегию. Относительно игрока 1 справедлив результат теоремы п. 5.6.

Указание. Использовать результат упр. 18 и рассмотреть вспомогательную

игру r

(JT,

Y, Н

), где г

я(х

есш уе

^ ^

I lim Я(х,

у„),

если у=0 или у=\.

20.

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

21.

Рассматривается одновременная игра преследования на плоскости (см. при-

мер 1 п. 1.2), когда множества стратегий

—

где S

—

некоторое замкнутое

выпуклое ограниченное множество.

а) Показать, что значение рассматриваемой игры равно R, где R — радиус

минимального круга S(0, R), содержащего 5, оптимальная стратегия игрока 2 явля-

ется чистой и заключается в выборе центра О круга S

(О,

К).

б) Показать, что оптимальная стратегия игрока

является смешанной и являет-

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

S с кругом S

(О,

R) (если такие точки x

и х

существуют), либо таких трех точек

касания x!

х'

, что точка О лежит внутри треугольника, вершинами которого

являются данные точки.

22.

Решить одновременную игру преследования на плоскости, рассмотренную

в упр.

21,

в предположении, что игрок 2 выбирает

не

одну точку у

точек у

Функция выигрыша игры имеет вид

Н(х,у)=-

£р

(х,Уд,

ы\

где

(•)

—

расстояние в R

23.

Игрок / выбирает системы х из т точек промежутка

[—1,

1], т. е. х=(£,, ...

..., £„,, £,е[—

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

111

систему у из п точек того же промежутка [—1,

1],

т. е. у

(г\

...,

ri„),

^е[—1,

1],у'=1,

..., п. Функция выигрыша Н(х, у) имеет вид

Н(х, y)

l/2 I max min |f,—fy|+max min |£,—t\j\ J.

^ ' У j i '

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

24.

Рассмотреть обобщение задачи п. 8.3, а именно игру поиска, в которой игрок

2 выбирает систему у из к точек у

{у

...,

Ук)

на сфере С, а игрок 1, как и прежде,

систему х из 5 точек x=(Xi, ..., x

) на сфере С. Функция выигрыша имеет вид

Я(х, у)-{М\М=\{у,}\

:yieS(

г);у=1,

..., л},

где 5

(xj,

г) — сферический сегмент с вершиной в точке Xj и радиусом основания г;

(запись

|{у,-}|

означает количество точек множества {уг})- Точка >>,- считается об-

наруженной, если y

eS{xj, г) хотя бы для одного Xj. Таким образом, значение

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

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

ГЛАВА III

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

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

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

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

игры двух лиц, т. е. игры, в которых интересы сторон прямо

противоположны. Однако реальные задачи принятия решения

в условиях конфликта характеризуются большим числом участ-

ников и, как следствие этого, неантагонистичностью конфликтной

ситуации. Если говорить о конфликте двух лиц и его моделях, то

можно заметить, что он также не исчерпывается только антагони-

стическим случаем. Дело в том, что интересы игроков могут пересе-

каться, но не быть обязательно противоположными. Это, в частно-

сти,

может приводить к ситуациям, взаимовыгодным обоим игро-

кам (в антагонистическом конфликте это невозможно), что делает

осмысленным кооперирование (выбор согласованного решения),

приводящее к увеличению выигрыша обоих игроков. Однако воз-

можны такие конфликты, когда кооперация или соглашение невоз-

можны по правилам игры. Поэтому в неантагонистических играх

различают бескоалиционное поведение, когда соглашения между

игроками запрещены правилами (см. §

— 5), и кооперативное

поведение игроков, когда разрешается кооперация типа выбора

совместных стратегий (см. § 6 — 8) и совершения побочных плате-

жей (см. § 9 — 11). Рассмотрим первый случай.

1.2. Определение.

Система

r=(N,

}

leN

}

leN

которой

N={1, 2, ..., п) —

множество

игроков,

—

множество

стратегий игрока

—

функция выигрыша игрока

определенная

на

декартовом произведении множеств стратегий игроков

Х=

(множество ситуаций

игры),

называется бескоалиционной

игрой.

Бескоалиционная игра и лиц происходит следующим образом.

Игроки одновременно и независимо друг от друга выбирают свои

стратегии x

из множеств стратегий Х

/=1, 2, ..., и, в результате

чего формируется ситуация х=(х

1г

..., х

После этого каж-

дый игрок i получает выигрыш

Н,

(х).

На этом игра заканчивается.

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

называется

конечной бескоалиционной игрой

п лиц.

1.3. Бескоалиционная игра Г, в которой принимают участие два

игрока, называется игрой двух лиц. Таким образом, бескоалицион-

ная игра двух лиц Г в нормальной форме определяется системой

Т=(Х

, Н

), где X

— множество стратегий первого игрока,

— множество стратегий второго игрока, Х

х Х

— множество

ситуаций игры,

->R

:Х

хX

-*R

— функции вы-

игрыша соответственно 1 и 2 игроков. Конечная бескоалиционная

игра двух лиц называется

биматричной.

Это объясняется тем, что

перенумеровав множества чистых стратегий игроков числами 1, 2,

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

записать в виде двух матриц

41-

•&\п

_*ml" "&mn

=в=

-.Рт\"'Ртп_

При этом элементы а

и /?

матриц А, В являются соответственно

выигрышами игроков 1я2в ситуации

(i,j),

ieM,jeN,

{1,...,

m},

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

В соответствии с изложенным выше биматричная игра проис-

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

строки,

а второй (одновременно и независимо) номер j столбца матрицы.

Тогда игрок 1 получает выигрыш

щ=Н

(х

у^, а игрок 2 — выиг-

рыш #,-#2

(х,,

у]).

Заметим, что биматричную игру с матрицами А и В можно

также задать

(т

и)

матрицей (А, В), каждый элемент которой есть

пара (а

fiij),

г'=1, 2, ..., т; j=\, 2, ..., п. Игру, определяемую

матрицами An В, будем обозначать Г

{А,

В).

Если бескоалиционная игра Г двух лиц такова, что Н

(х,

у)=—Н

(х,

у) для всех хе Х

уеХ

то Г оказывается антагонисти-

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

случае, когда в биматричной игре а

=—^

, мы получаем матрич-

ную игру, рассмотренную в гл. 1.

1.4. Пример 1.

(«Семейный спор».)

Рассматривается биматричная

игра с матрицей

_ 01 02 _

(Л

л-

в1

(4,1)

(Л

}

-«

|(0,

0) (1,4)

114

Имеются различные интерпретации этой игры, но наиболее извест-

ная [44] следующая. Муж (игрок 1) и жена (игрок 2) могут выбрать

одно из двух вечерних развлечений: футбольный матч (а

^) или

театр (<х

, /J

). Если они имеют разные желания (a

) или (а

, /?

то остаются дома. Муж предпочитает футбольный матч, а жена —

театр.

Однако обоим гораздо важнее провести вечер вместе, чем

участвовать в развлечении (хотя и предпочтительном) одному.

Пример 2. (Игра «перекресток» [10] J Два автомобилиста двига-

ются по двум взаимно перпендикулярным дорогам и одновременно

встречаются на перекрестке. Каждый из них может остановиться

(1-я стратегия а

или /^) и ехать (2-я стратегия а

или /?

Предполагается, что каждый из игроков предпочитает остано-

виться, а не пострадать в аварии и проехать, если другой сделал

остановку. Этот конфликт может быть формализован биматричной

игрой с матрицей

<х

[_(2,

1-е) (0, 0)

(неотрицательное число е соответствует неудовольствию от того,

что игрок остановился и пропустил партнера).

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

число игроков п велико и каждое из множеств X, состоит из двух

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

автомобилем, 1 — использовать общественный транспорт). Функ-

ция выигрыша определяется следующим образом:

Hi(x

..., л;„)=

a(t) при

b(t) при

х,=

х,

= 0,

где /=

'J-I

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

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

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

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

то

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

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

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

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

больше

—/

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

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

оритете общественного транспорта),

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

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

а(0)

1(0)

/ 4

1 '/

' /

/ /

/ 1 1

t„

t, 1

но

а(1)

Рис.

115

Пример 4.

(Распределение ограниченного

ресурса с учетом ин~

тересов

потребителей

[52]J Предположим, что п потребителей

имеют возможность расходовать (накапливать) некоторый ресурс,

объем которого ограничен величиной А>0. Обозначим объем ресу-

рса, который расходует (накапливает) i-й потребитель, через х,.

В зависимости от значений вектора х=(х

, ...,

х„)

потребители

получают выигрыш, который оценивается для i-ro потребителя

функцией hi{x

, ..., х„), если общий объем израсходованного

(накопленного) ресурса не превосходит заданной положительной

величины 6<А,

Т.

е.

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

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

х„). При

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

£ x

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

i-l

gi(x

,...,

)<h,(x

,...,

Рассмотрим неантагонистическую игру в нормальной форме

Г=(#,

{Х,},

„,

}

leN

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

Ы(х

1г

..., х„), £ Xi^d,

1-1

i-l

Х,=[0,

а], 0<а,<Л, £ а,=А, N={1, 2 и}.

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

Пример 5.

(Теоретико-игровая модель охраны воздушного

бассей-

на от загрязнений [52]J В промышленном районе расположено

л предприятий, каждое из которых имеет один источник, выбрасы-

вающий в атмосферу вредную примесь. В районе имеется экологи-

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

превышать предельно допустимого значения. Усредненное по вре-

мени и области значение концентрации вредной примеси в атмос-

фере при наличии и источников можно приближенно рассчитать по

формуле

116

"iV*l> *2> •"' ^л)

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

1-Х

Пусть

в <

c&i

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

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

Считая предприятия игроками, построим игру, моделирующую

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

каждое предприятие i может снижать свои эксплуатационные рас-

ходы, увеличивая выброс х,, однако если в зоне Q уровень загрязне-

ния превышает ПДК, на предприятие накладывается штраф 5,>0.

Пусть игрок / (предприятие) имеет возможность выбирать зна-

чения Л:, ИЗ множества X

=[0, а]. Функции выигрыша игроков

имеют вид

{

h,(x

, ..., х„), q^d,

ft,(*i>

..., x„)-s

{

, q>V,

где A,(x

, ..., х„) — непрерывные и возрастающие по аргументу

х,

функции.

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

ИГРАХ

2.1.

Известно, что для антагонистических игр принципы минима-

кса, максимина и равновесия совпадают (если они реализуемы, т. е.

существует равновесие, а максимин и минимакс достигаются). В та-

ком случае они определяют единое понятие оптимальности и реше-

ния игры. В теории неантагонистических игр нет единого подхода

к выработке принципов оптимальности. По существу имеется целое

множество таких принципов, каждый из которых основывается на

некоторых дополнительных предположениях о поведении игроков

и структуре игры.

Естественно предположить, что в игре Г каждый из игроков

стремится к достижению ситуации х, в которой значение его функ-

ции выигрыша было бы наибольшим. Однако функция выигрыша

Я,

зависит не только от стратегии /-го игрока, но и от стратегий,

выбираемых другими игроками, поэтому ситуации {х}, дающие

большее значение выигрыша для f-ro игрока, могут не быть таковы-

ми для других игроков. Таким образом, так же как и в случае

антагонистической

игры,

стремление игроков получить наибольший

выигрыш носит конфликтный характер и сама формулировка того,

какое поведение является «хорошим» или оптимальным в игре,

является проблематичной. Здесь имеется несколько подходов. Од-

117

ним из них является равновесие по Нэшу и его различные обобще-

ния. В случае, когда игра Г является антагонистической, равновесие

по Нэшу совпадает с понятием равновесия, которое представляет

собой основной принцип оптимальности в антагонистической игре.

Пусть х—{х

, ..., *;_!, х,,

i+i

..., х„)— произвольная ситуация

в игре Г, а

х,-

— некоторая стратегия игрока i. Построим ситуацию,

которая отлична от х только тем, что стратегия

х,-

игрока

заменена

на стратегию х\. В результате мы получаем ситуацию (х

...,

х,_],

xj,

Xi+u —>

х„),

которую будем обозначать через (x||xj)- Очевидно, что

если х, и xj совпадают, то (x||xj)=x.

Определение. Ситуация

x*=(xf,

..., xf, ..., х*) называется

ситуацией

равновесия по

Нэшу,

если

для

всех

x^XjU

i=l,....

имеет

место неравенство

Я,(х*)^Я,(х*||х

;

). (2.1)

Пример 6. Рассмотрим игру примера 3 п. 1.4. Равновесными по

Нэшу здесь являются ситуации, для которых выполняется условие

^t*-l/n,

l/n^t

(2.2)

где

f*=(l/n)

Т- Из условия (2.2) следует, что переключение

7-1 „

каждого отдельного игрока

одной чистой стратегии на другую при

условии, что другие игроки своих стратегий не изменяют, не влияет

на его выигрыш.

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

t=(l/ri) £

Xj,

te{t

, tj], и пусть величина

«5

— доля игроков, реши-

вших переключиться со стратегии 0 на стратегию 1. Заметим, что

если 8 таково, что b(t) = a(t)<a(t+8), то выигрыши этих игроков

увеличиваются при таком переключении, если стратегии остальных

игроков останутся прежними. Однако если это переключение дейст-

вительно произойдет, то у тех же игроков возникает желание пере-

ключиться со стратегии 1 на стратегию 0, поскольку выполнено

условие a (t+8)<b(t+5). Если же это желание осуществится, то

доля (1/и)

•

£ xj игроков уменьшится и вновь попадет на отрезок

[*0,

Аналогично, пусть д — доля игроков, переключившихся по ка-

ким-либо причинам (например, из-за случайных ошибок) со страте-

гии 1 на стратегию 0, причем

t—8<t

Тогда в силу условия

b(t—8)<a(t~

у игроков появится желание переключиться обрат-

ив

но

на

стратегию

1. При

осуществлении этого желания доля

1/и

•

увеличится

вновь вернется

на

отрезок

, /J.

2.2.

Из

определения ситуации равновесия

по

Нэшу следует,

что

ни один из игроков

i не

заинтересован в отклонении от стратегии

х*,

входящей

в эту

ситуацию (согласно (2.1)

его

выигрыш

при

исполь-

зовании стратегии

вместо

разве лишь уменьшится

при

усло-

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

ситуацию равновесия

х*).

Таким образом, если игроки договори-

лись предварительно об использовании стратегий, входящих

ситу-

ацию равновесия

JC*,

индивидуальное отклонение

от

договора

невыгодно отклонившемуся игроку.

Определение.

Стратегия

xfeXj

называется

равновесной,

если

она входит

хотя

бы

одну ситуацию равновесия

по Нэшу.

Для бескоалиционной игры двух

лиц

r =

, Н

Н?) ситу-

ация (х*, у*) является ситуацией равновесия, если неравенства

Н,

(х, y*HH,

(х*,

у*), Н

(х*, уНН

(х*,

у*) (2.3)

выполняются для всех

xeX

uyeY

В частности,

для

биматричной

(т

хи)-игры Г (Л,

В)

пара

(г*,

/*)

будет ситуацией равновесия по Нэшу, если неравенства

«<./<«!••/,

&•></?•*/

(2-4)

выполняются

для

всех номеров строк

ieM и

столбцов

jeN. Так,

в примере

равновесными являются ситуации

(<х

) и (а

, /?

в примере 2 —

(о^,

)

и (а

, fix)-

Напомним, что для антагонистической игры Г =

(Л

Н) пара

(х*,

y*)eX

хХ

является ситуацией равновесия, если

Н(х, у*НН(х*,

у*)^Н(х*,

у), хеХ

уеХ

При этом имеют место следующие основные свойства антагонисти-

ческих игр.

'. Игроку невыгодно информировать своего противника

о стратегии (чистой или смешанной), которую он собирается приме-

нить.

(Конечно, если игрок собирается использовать оптимальную

стратегию,

то

его выигрыш не уменьшится

от

того,

что он

объявит

об этом,

но он

ничего

не выигрывает.)

2°.

Если (х, y)eZ(T),

(JC',

/)eZ(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