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

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

Заметим, что совместная смешанная стратегия М* =Г'о У

является оптимальной по Парето и ей соответствует вектор выиг­ рышей (5/2, 5/2). Таким образом, М* может быть рекомендована в качестве решения игры «семейный спор».

Определение. Для биматричной (тхи)-игры Г {А, В) обозна­ чим через М= {цу} совместное вероятностное распределение на п рах (i, j), f=l, ..., т; 7=1, ..., п. Через /*,(/) обозначим условную

вероятность реализации стратегии] при условии, что реализовала стратегия i. Аналогично, через Vj(i) обозначим условную вероят ность реализации стратегии i при условии, что реализовалась ст тегия]. Тогда

% / Ё	РФ если £ /ty*0»
ft</>="	если fjL,j=0,j=l, .... и;
0,

У / ( 0 =1	/ty/E Иц, ее™ £ n,j^0,
		/ - 1
	0,	если Htj=0, i—l, ..., т.

Будем говорить, что A/* = {/xJ} — ситуация равновесия в со­ вместных смешанных стратегиях в игре Г (А, В), если выполнены

следующие неравенства:

twr(j)>£*tjtf(f), Ем*(о>ЕИ(0 (6.1)
j-i	j - \	t-i	i-i
для всех i, fell, 2, ..., т) ш],]'е{\,		2, ..., я}.

6.2. Игру Г (Л, 5) в совместных смешанных стратегиях можно интерпретировать следующим образом. Пусть игроки договори­ лись об использовании стратегии М*={ц^} и пусть также в резуль­ тате реализации случайного механизма выпала пара (/', /), т. е. первый (второй) игрок получил номер i(j) стратегии. Заметим, что каждый из игроков знает только свою реализацию. Этот игрок, вообще говоря, может не согласиться с реализацией г (соответствен­ но У) совместной стратегии и выбрать стратегию f (/'). Тогда, если М* — равновесная ситуация, то каждому из игроков невыгодно отклоняться от предложенной реализации г (соответственно ]), что следует из (6.1), где в левой части неравенства стоит ожидаемый

140

выигрыш игрока 1 (игрока 2) в случае согласия с реализцией i(j). Теперь предположим, что стратегия i игрока 1 такова, что %=0

для всех 7=1, 2, ..., п. Тогда первое из неравенств (6.1), очевидно, выполняется. Аналогично, если /ху=0 для всех i=\, m, то второе из

неравенств (6.1) выполняется. Подставим выражения для ц{{]) и уДО через Цу в формулы (6.1). Тогда получаем, что необходимым и до­ статочным условием равновесности ситуации М*={ц^} является выполнение неравенств

я	я	/я я
1-Х	J-\	i-l ]-\	с6-2)
zw>i^./'*>o
i-i	(-1
для всех /, /'е{1, 2, ..., m)jaj,j		'е{1, 2, .... и}.

Обозначим через Zc(r) множество равновесных ситуаций в со­

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

Теорема. Справедливы следующие утверждения.

1. Множество ZC(T) равновесных ситуаций в совместных сме­ шанных стратегиях в биматричной (тхп)-игре Г (А, В) является

непустым выпуклым компактом пространства 1Гхп.

2) Если (х, у) — ситуация в смешанных стратегиях игры Г (А, В), то определяемая по ней ситуация М={цу) в совместных смешан­ ных стратегиях будет равновесной тогда и только тогда, когда (х, у) — ситуация равновесия по Нэшу в смешанных стратегиях в игре Т{А, В).

Доказательство. Пусть (х, у), x=*(gv ..., <!;«), y=(nlt ..., п„) — ситуация в смешанных стратегиях игры Г (А, В), а М = {ци} — соот­

ветствующая ситуация в совместных стратегиях, т. е. Цц—Zt'nj, »= 1,

..., m;j=\ л. Необходимым и достаточным условием равновес­ ности М является система неравенств (6.2), т. е.

ЬК&у^ЬК^у), n}K2{x,j)>VjK2(x,j'), (6.3) где i, Гб{1,2,..., m};j,j'e{l,..., и}. Если &=0 (fy=0), то неравенства

очевидны. Поэтому система неравенств (6.3) эквивалентна следу­ ющей:

К, (I, у)>К, (/', у), Кг(х, J)>K2 (x, / ) ,

(6.4)

г, i'e{l, ..., т}; j , j'e{l, ..., и}, где i и j принадлежит спектрам стратегий х и у. Предположим, что (х, у) — ситуация равновесия по

141

Нэшу в смешанных стратегиях в игре Г (А, В). Тогда согласно теореме п. 5.2

K,(i, у) = К1(х, у), K2(x,J) = K2(x, у)

для всех / и j из спектров оптимальных стратегий. Поэтому неравен­ ства (6.4) выполнены и MeZc(T).

Обратно, если (6.3) выполнено, то, суммируя неравенства (6.3) по i a. j соответственно и применяя теорему п. 5.1, получаем, что ситуация (х, у) равновесна по Нэшу.

Выпуклость и компактность множества ZC(F) следует из того, что Zc (Г) — множество решений системы линейных неравенств

(6.2), которое ограничено, а непустота — из существования ситу­ ации равновесия по Нэшу в смешанных стратегиях (см. п. 4.1). Теорема доказана.

Отметим, что совместная смешанная стратегия М*	Р/2	0 1
	1 0	1/а.

равновесна в игре «семейный спор» (см. пример 1 п. 1.4), что просто установить проверкой неравенств (6.2).

§7. ЗАДАЧА О ПЕРЕГОВОРАХ

7.1.Основной вопрос, который мы рассмотрим в данном параг­ рафе, заключается в том, как прийти к соглашению разумным игрокам при совместном выборе решения в ходе переговоров. Пе­ ред тем как сформулировать задачу, еще раз вернемся к игре «семейный спор».

Пример 14. Рассмотрим множество R, соответствующее возмож­ ным векторам выигрышей в совместных смешанных стратегиях для игры «семейный спор» (область, заштрихованная на рис. 11). Дейст­

	вуя совместно, игроки могут реализо­
	вать любой выигрыш в смешанных
	стратегиях в области R. Однако это не
	означает, что они могут договориться
	о любом исходе игры. Так, игроку 1 на­
	иболее предпочтительна точка (4, 1),
%WM)	а игроку 2 — точка (1, 4). Ни один из
	игроков не согласится с результатами
	переговоров, если его выигрыш будет
	меньше максиминного значения, по­
	скольку этот выигрыш он может полу­
	чить самостоятельно	(независимо от
	партнера). Максиминные смешанные
	стратегии игроков в этой игре х° = (1/5,
	4/5) и у0 = (4/5, 1/5)	соответственно,
Рис. 11	а вектор выигрышей	в максиминных

142

стратегиях («°,«°) равен (4/5,4/5). Поэтому множество S, возможное для переговоров, ограничено точками а, Ь, с, d, е (см. рис. 11). Н&зовем его переговорным множеством игры. Далее, действуя со­ вместно, игроки всегда могут договориться выбирать точки на отрезке ab, поскольку это выгодно обоим (отрезок ab соответствует ситуациям, оптимальным по Парето).

7.2. Назовем задачу выбора точки (vu v2) из S в результате переговоров задачей о переговорах. Таким образом, мы пришли к следующей проблеме. Пусть для биматричной игры Г {А, В) задано переговорное множество S и вектор максиминных выигры­ шей («х» v2). Требуется найти правило, решающее задачу о перегово­ рах, т. е. необходимо найти функцию ср, такую, что

ФМ . «2)=(«1,^) . (7-1)

Оказывается, что при некоторых разумных предположениях за­ дача (7.1) разрешима в силу справедливости следующей теоремы.

Теорема. Пусть S — выпуклый компакт в R2, (v°, v\) — вектор максиминных выигрышей в игре Г (А, В). Множество S, пара (vu v2) и функция <р удовлетворяют следующим условиям:

2) (vltv2)eS.

2

)eS

и («

lf

2

т о

v

i>

v

v

i>

v

z)-

3) Если (»!, v

«2»(«xi »)>

(

z) = (

4) Если (vu v2)e!Sc:S и (vlt v2)=q>(S, «?, i>°), то fo, v2) = <p(S, v?,

Ǥ).

5) Пусть Т получается из S с помощью линейного преобразования »1 = <х1ю1+/?1, v2 = a2v2 + fi2, ах>0, а2>0. Тогда, если q>(S, v\, v2b) = {vl,

«г), то

<р(Т, arf + fii, «2«2+/*2)=(«i*i + /*i, a2i2 + p2).

6)Если из (vlt v2) е S следует (v2,1>х) е S для всех (vu v2) e S;«°=v%

и(p(S, «1, v2)=(vlt v2), то v1=v2.

Тогда существует единственная функция ср такая, что (p(S, v°lt «г)=(«1, v2).

Функция (р, которая отображает игру с переговорами (S, v°, v2) в множество векторов выигрышей (vlt v2) и удовлетворяет условиям 1) — 6), называется арбитражной_схемой Нэша [11], условия 1) —

6) — аксиомами Нэша, а вектор (vlt v2) — арбитражным вектором выигрышей. Таким образом, арбитражная схема — это реализуемый принцип оптимальности в игре с переговорами.

Прежде чем перейти к доказательству теоремы, обсудим ее условия на примере игры «семейный спор» (см. рис. 11). Условия 1 и 2 означают, что вектор выигрышей («ls v2) находится в множест-

143

ве, ограниченном точками а, Ь, с, d, е. Ограничение 3 показывает, что (vt, v2) лежит в множестве точек, оптимальных по Парето. Условие 4 говорит о независимости функции q> от посторонних стратегий, т. е. если (»15 v2) — арбитражный вектор выигрышей для множества 7>, то при расширении множества переговоров до S реше; нием будет либо (vv v2), либо другая точка, но не принадлежащая £! Ограничение 5 говорит о том, что если функции выигрыша отлича­ ются лишь масштабом измерения и началом отсчета, то также отличаются и результаты переговоров. Свойство 6 указывает на равноправность обоих игроков.

Доказательство теоремы п. 7.2 основано на следующих вспомо­ гательных результатах.

7.3. Лемма. Если существуют точки (vlt v2)eS, что i>i>«?

и v2>v2, то существует единственная точка (vlt v2), максимизиру­ ющая функцию

на подмножестве SY<^S, Sx = {(vv v2)\(vt, v2)eS, ю^»?}. Доказательство. По условию S^ —непустой компакт, а в —

непрерывная функция, поэтому она достигает на нем своего мак­ симума д. По предположению, 6 положительно.

Пусть существуют две точки максимума {о\, v'2) и {v\, v'2) функ­ ции в на St. Заметим , что ч\Ф%Рг, поскольку в противном случае из вида функции в имеем v'2=v2.

Если v'i<vl, то v'2>v2. Так как множество 5Х —выпукло, то fo, v2)eSl9 где »1 = (»'i+»i)/2, v2=(v'2+v2)j2. Имеем

_	(с;-^)+(^-«;)	ц—»ж»;-«°)
0O>i. «2)=	'	=

=К-«;)(^2-^) | („;-«,>;-„?) |		к-<)(«;-v'2)
2	2	4

Каждое из первых двух слагаемых последней суммы равно в/2, а третье слагаемое положительно, что невозможно, поскольку в — максимум функции в. Таким образом, точка (йи v2), максимизиру­ ющая функцию в на множестве Slt единственна.

J7.4. Лемма. Пусть S удовлетворяет условиям леммы п. 7.3, а («и v2) — точка максимума функции в (vlf v2) и пусть

<5(«i» v2) = (v2-vl)vl

+

(v1-v4)v2.

Если («lf v2)eS, то имеет место неравенство

5(vu v2)^8(vy, v2).

Доказательство. Предположим, что существует такая точка

(vlt v2)eS, что 8(vlt v2)>5(pl, Z2). Из выпуклости S имеем:

144

(v\, v'2)eS, где v'^ — v^ziv^ — vj и V'2 = V2 + E(V2—V2), 0<е<1. В силу линейности div^ — v^ v2—v2)>0. Имеем

e(v'i, v'2) = 0(vlt «2) + £^(i;1-«1, v2-v2) + az(v1-v1)(v2-v2).

Последнее слагаемое — бесконечно малая величина порядка 0 (е). Поэтому при достаточно малом е>0 получаем неравенство Q(v\, v'2)>6(vy, v2), но это противоречит максимальности 0(«l5 v2).

7.5. Перейдем к доказательству теоремы п. 7.2. Для этого пока­ жем, что точка (уи v2), которая максимизирует 6{vu v2), является решением задачи о переговорах.

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

мы п. 7.3. Тогда определена точка G>vy2), которая максимизирует
Q(vi> vi)- Можно проверить, что $и v2) удовлетворяет	условиям
1) — 4) теоремы п. 7.2. Она также удовлетворяет условию 5 этой
теоремы, так как если v'1 = a1v1 + pl и v'2 = a2v2 + f}2, то	v2),
04*1, ^^-("А+Ш^-^А+Р^а^в^,

и если («l5 v2) максимизирует в(ь1г v2), то (v'lt v'2) максимизирует

&Wi> v'i)- Покажем, что (vlt v2) удовлетворяет условию 6. Пусть множество S симметрично в смысле условия 6 и v°=v2. Тогда (у>2,

«1)е5'1 и 0(»lf v2)=6(v2, Zj). Так как (ои v2) —^единственная точка, которая максимизирует 0(vit v2) на Slt то (ии v2)=(v2, «Д т. е.

Таким образом, точка (vlt v2) удовлетворяет условиям 1) — 6). Покажем, что это единственное решение задачи о переговорах. Рассмотрим множество

Л = {(»!, v2)\S(vlt v2)^S(Zt, Z2)}.

(7.2)

По лемме п. 7.4 имеет место включение ScR. Пусть Т получается из Л с помощью преобразования

* i == -0,»2=z

-•

(7.3)

Выражая vt и v2 из (7.3) и подставляя в (7.2), получаем, что

T={(v'l,v2)\v'1+v2^2}

и t)i°=t)20 = 0. Так как Г симметрично, то из свойства 6 имеем, что решение (если оно существует) должно лежать на прямой v'l=v'2, а согласно свойству 3 оно должно быть точкой (1, 1), т. е. (1, 1) = ф (Г, 0, 0). Обращая преобразование (7.3) и применяя свойство 5,

получаем, что (й1г v2) = cp(R, v°, v2). Так как (vlt v2)eS, a S(^R, на

основании свойства 4 пара («15 v2) является решением для (S, «?, v2). Предположим теперь, что условия леммы п. 7.3 не выполнены,

145

т. е. не существует точек (vlt v2)eS, для которых vt>v° и v2>v2. Тогда возможны следующие случаи.

а) Существуют точки, у которых «^«"и v2 =v2. Тогда в качест­ ве (vv, v2) возьмем точку в S, которая максимизирует vt при ограни­ чении v2=v2.

б) Существуют точки, у которых vl=v1 и v1>«2- В этом случае в качестве (vt, v2) возьмем точку в S, которая максимизирует v2 при ограничении «х =v°.

в) Переговорное множество 5 вырождается в точку («°, v2) максиминных выигрышей (например, случай матричных игр). Полагаем

-о - о

Непосредственно можно проверить, что эти решения удовлет­ воряют свойствам 1) — 6), при этом из свойств 1) — 3) следует единственность. Теорема доказана.

Вигре «семейный спор» (см. пример 14) схема Нэша дает арбитражный выигрыш (t>lt ю2)=(5/2, 5/2) (см. рис. 11).

§8. ИГРЫ В ФОРМЕ ХАРАКТЕРИСТИЧЕСКОЙ ФУНКЦИИ

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

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

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

В § 8 — 10 рассмотрена кооперативная теория игр и лиц. В ней исследуются условия, при которых объединение игроков в мак­ симальную коалицию является целесообразным, а отдельные игро­ ки не будут иметь желания создавать меньшие группировки или действовать индивидуально.

8.1. Пусть N= {1,..., и} — множество всех игроков. Любое непус­ тое подмножество SczN называется коалицией.

Определение. Характеристической функцией игры п лиц будем называть вещественную функцию v, определенную на коалициях SczN, при этом для любых непересекающихся коалиций Т, S (TczN,

146

S<zN) выполняется неравенство
v(T) + v(S)^v(T[jS),v(0)	= O.	(8.1)

Свойство (8.1) называется свойством супераддитивности. Оно необходимо для содержательной интерпретации числа v(T) как гарантированного выигрыша коалиции Т в случае, когда она дей­ ствует независимо от остальных игроков. При такой интерпретации неравенство (8.1) означает, что коалиция S\jT имеет не меньше возможностей, чем две непересекающиеся коалиции S и Т, дейст­ вующие независимо.

Из супераддитивности v получаем, что для любых непересека­ ющихся коалиций Su ..., Sk

2>№)<*(Л0-

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

8.2. Рассмотрим бескоалиционную игру r=(N, {Xi\ieN, {H,}ieN).

Пусть игроки, составляющие некоторую коалицию ScN, объ­ единяют свои усилия с целью увеличения своего суммарного выиг­ рыша. Установим, какой наибольший выигрыш они могут себе гарантировать. Совместные действия игроков из коалиции S оз­ начают, что коалиция S, действуя от имени своих членов как один игрок (обозначим его 1), имеет в качестве множества чистых страте­ гий всевозможные комбинации стратегий, составляющих ее игроков из S, т. е. элементы декартового произведения

ATs=n*i.

ieS

Общность интересов игроков из S означает, что выигрыш коалиции S (игрока 1) есть сумма выигрышей игроков из S, т. е.

tfs(*)=£ #,(*),

ieS

где xeXN, x=(xu ..., д:я) — ситуация в чистых стратегиях.

Нас интересует тот наибольший выигрыш, который игроки из S могут себе гарантировать. В худшем для игрока / случае оставши­ еся игроки из N \S могут также объединиться в коллективного

игрока 2 с множеством стратегий Х^3= П ^>и интересом, диаме-

ieN \S

трально противоположным игроку 7 (т. е. выигрыш игрока 2 в ситу-

147

ации х равен — Hs (x)). В результате таких рассуждений вопрос 0 наибольшем гарантированном выигрыше коалиции S превратился в вопрос о наибольшем гарантированном выигрыше игрока 1 в ан­ тагонистической игре Г8=(Х8, XN\S, HS). В смешанном расширении

TS=(XS, XN\S, KS) игры Г5 гарантированный выигрыш v(S) игрока

1 может разве лишь увеличиться по сравнению с игрой Г5, поэтому в дальнейшем будем рассматривать смешанное расширение игры Ts. Заметим, в частности, _что при такой интерпретации v (S) со­ впадает со значением игры Г8 (если оно существует), a v (N) — мак­ симальный суммарный выигрыш игроков. Очевидно, что v (S) зави­ сит в результате только от коалиции S (и еще от самой исходной бескоалиционной игры, которая в наших рассуждениях остается одной и той же), являясь ее функцией. Убедимся, что эта функция является характеристической функцией бескоалиционной игры. Для этого достаточно показать выполнение условия (8.1).

Заметим, что для каждой бескоалиционной игры, построенной выше, ю(0)=О. Действительно, по определению,

Я0(х)=£Я,(х),

(60

но последняя сумма не содержит слагаемых, откуда Н0 (х) тождест­

венно равно нулю, поэтому и «(0)=О.

Лемма (о супераддитнвности). Для бескоалиционной игры Г=(Ы, {Xt}tsN, {Ht},eN) построим функцию

	v(S)=sup inf Ks 0is, v^s), ScN,		(8.2)
где nseXs,	v^eA^s, rs=(Xs, X^s,	Ks)— смешанное расширение
антагонистической игры Г5. Тогда для всех S, TcN,			для которых
Sf\T=0,	имеет место неравенство
	v(S[)T)>v(S)+v(T).		(8.3)
Доказательство. Заметим, что
	v(S[jT) = sap inf £	KifasyT, v^s^n),

^SUr yN \CS|J7) ''eS(Jr

где Htfjr — смешанные стратегии коалиции S[jT, т. е. произвольные вероятностные меры на X#jT, V№,(S\JT) — вероятностные меры на XN\{S\JT), KI — выигрыш игрока i в смешанных стратегиях. Если ограничиться только такими вероятностными мерами на Xs\jT, ко­ торые являются произведениями независимых распределений fis

148

и vT на декартовом произведении Xs х Хт, то область изменения переменной, по которой производится максимизация, сузится и суп­ ремум разве лишь уменьшится. Таким образом, имеем

v (S\J T) ^ sup sup	inf	Y Kt (jis x цт, vN V(sUn).
Отсюда
v(S(JT)> inf	Y	Ki(fisxnT, v ^ =

= inf ( Y K'0*s x Pr. V/A(SUD)+ E -KiO*s x A*r. vM(sim )•

Так как сумма инфимумов не превосходит инфимум суммы, имеем

v (S\J Т) > inf Y *. 0*s х 0г. v*\(*im)+

+ inf £ К,(ц8хцт, vM(SUn).

Минимизация первого слагаемого в правой части неравенства по /*г, а второго — по fis (для единообразия переименуем их соответст­ венно vT и vs) приводит к соотношениям

v (S[j 7) > inf		inf Y Kt 0*s x vr, vM(5UT))+
+ inf	inf	Y £,-(vsx/iT, vM(sU„)>
>inf £	^ ( ^ s , v^sj+inf Y Ki{nT, v^r).

Последнее неравенство справедливо при любых значениях мер fis в первом слагаемом и цт — во втором. Следовательно, по этим мерам можно перейти к супремумам

v(S{jT)>sup	inf	Y	KiiVs, vjv\5) + sup inf	X£,(/ir, у ^г ).
H	y^s	ieS	<h v^r	ie T

Откуда, используя (8.2), получаем v(S\jT)>v(S)+v(T)

и супераддитивность доказана.

Заметим, что неравенство (8.3) также справедливо, если функция v (S) строится по правилу

»(5)=sup inf Hs(xs, x^s), ScN,

149