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

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

Сначала докажем существование ситуации равновесия в смешан-

ных стратегиях для биматричной игры. Это доказательство опира-

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

Какутани

о неподвижной точке, кото-

рую приведем без доказательства [49].

Теорема. Пусть S — компактное выпуклое множество в R иф — многозначное

отображение,

переводящее

точки S в компактные выпуклые подмножества S и удов-

летворяющее условию: если

x„eS,

-*х,

у„еф(х

), у„-*у, то у еф (х).

Тогда существует такое x*eS, что х*еф (х*).

Теорема. Пусть Г

(А,

В) —

биматричная

(тхп)-шр&. Тогда

существуют смешанные стратегии

x*eX

и у*е Х

игроков

1 и 2

со-

ответственно,

такие,

что

пара

(х*, у*) является

ситуацией

равно-

весия

по Нэшу.

Доказательство. Множества смешанных стратегий X

и Х

игроков 1 я 2 — выпуклые многогранники, поэтому множество

ситуаций

хХ

— компактное выпуклое множество.

Пусть

— многозначное отображение,

ф-.Х^Х^Х^хХ»

определяемое соотношением

Ф-(.х

,у

)^<(х',у')

{(*,.

Kiix

, j;

)=max ^(x, y

y')=max K

, y),

т. е. образ отображения ф состоит из пар наилучших ответов

игроков на стратегии у

и х

соответственно.

Функции K

и К

как математические ожидания выигрышей

в ситуации (х, у) билинейны по х и у, а следовательно, образ

(х

)

ситуации (х

, у

) при отображении

представляет собой выпук-

лое компактное подмножество в^х Х

. Более того, если последо-

вательности пар

{(хЪ,

уЬ)},

(Х"

yb)eXi. хХ

{(х?

у'

)},

у'п)еф(х%,

Уо)

имеют предельные точки, т. е.

lim

(х"

уЬ)=(х

УО\

In» М, Ул) = (

У%

то в силу билинейности функций К

К?

и компактности множеств

и Х

имеем, что (х', у')еф(х

, у

). Тогда по теореме Какутани

существует ситуация (х*,

y^eXj^xX^

для которой (х*, у*)еф(х*,

у*),

т. е.

(х*,

у*)>К, (х, у*), К

(х*,

у*)>К

(х*,

у)

для всех хвХ±

ye Y

. Теорема доказана.

4.2.

Предыдущая теорема может быть обобщена на случай не-

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

и Н

. При доказательстве этого

130

результата потребуется хорошо известная теорема о неподвижной

точке, принадлежащая Брауэру [49].

Теорема. Пусть S

—

компактное выпуклое множество в R , имеющее внутрен-

ность.

Если

—

непрерывное

отображение S в себя, то существует неподвижная

точка х* отображения

ср,

т. е. x*eS и х*=(р{х*).

Теорема. Пусть

Г=(Х

, Н

)—

бескоалиционная

игра

двух лиц,

пространства стратегий

(^R

—

компактные

выпуклые

подмножества,

а множество Х

х Х

имеет внутрен-

ность.

Пусть также функции выигрыша

(х, у) и Н

(х,

у)

непреры-

вны на X

х Х

, причем H

(х, у) вогнута по х при каждом фик-

сированном

у, а функция Н

{х, у) вогнута по у при каждом фик-

сированном

х.

Тогда

игре

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

Нэшу

(х*,

у*).

Доказательство. Пусть р

(х,

у)еХ

хХ

и q

(x,

y)eX

— две ситуации игры Г. Рассмотрим функцию

в(р,д)=Н

(х,у)+Н

(х,у).

Покажем прежде всего, что существует ситуация q*=(x*, у*), для

которой

max 0(p,q*)=e(q*,q*).

Действительно, пусть это не так. Тогда для каждого

qeX

x.X

найдется такое

реХ

p¥=q,

что в(р, q)>6(q, q). Введем в рас-

смотрение множество

={q\e(p,q)>e(q,q)}.

Так как функция в непрерывна (Н

и Н

непрерывны по совокуп-

ности переменных), a X

х Х

— выпуклый компакт, то множества

открыты. Более того, согласно сделанному предположению,

х Х

покрыто множествами G

Из компактности Х

х Х

следует, что найдется конечная совоку-

пность этих множеств, которая покрывает X

x Х

. Пусть это мно-

жества

...,

Обозначим

<Pj(q)=max.{0(pj,

q)-9(q, q), 0}.

Функции

q>j(q)

не отрицательны, и по определению

G>.

в каждой

точке q по крайней мере одна из функций

cpj

принимает положитель-

ное значение.

Определим отображение

множества X

x Х

в себя следующим

образом:

131

</>(я)

где

q>(q)

(Pj(q).

Функции ^непрерывны, поэтому

— непрерыв-

ное отображение Х

хХ

в себя. Согласно теореме Брауэра^) непо-

движной точке, найдется такая точка

qeX

хХ

что

^(c[)=q,

т.

е.

?=(!/<? («))Х>Л?ХР./-

Следовательно,

0(q,q)=e(~Vcpj(q)Pj,q\

\Нч)

J )

Но функция 0(р,

вогнута по

при фиксированном q и, следовате-

льно,

e(q,q)>-^l<PjW(Pj,~q). (4.1)

<р(я)у

С другой стороны, если %О)>0,

то

6(q, q)<d(pj, q),

если

<pj(q)=О,

то

<Pj(q)e(pj,

(pj(q)eQ,

q). Поскольку

<pj(q)>0

для

некоторого

мы приходим

неравенству

0(5,

9)<-^.

<PjG)0(py,

q),

ч>(.я)У

которое противоречит (4.1).

Таким образом, всегда существует

q*,

для которого

max 9(p, q*) =

e(q*,

q*).

Это означает,

что

(х, у*)+Н

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

у*)

(х*,

у*)

при всех хеХу

yeY

Последовательно полагая

последнем

неравенстве х=х* и у=у*, получаем неравенства

(х*,

у)^Н

(х*,

у*),

(х,

у*)^ {х\

у*),

справедливые для всех xeX

уеХ

Теорема доказана.

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

ных множествах

(в

частности,

на

единичном квадрате)

непрерыв-

ной функцией выигрыша, справедлив следующий результат.

Теорема. Пусть

Г=(Х

, Н

)

—

бескоалиционная

игра

двух

лиц,

где

—

непрерывные функции

на

;

—

132

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

странств.

Тогда игра

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

(ц, v)

смешан-

ных

стратегиях.

Эту теорему приведем

без

доказательства, поскольку

оно ос-

новывается

на

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

билинейности функций

K,(ji,

v)= J J H,(x,

y)dv(x)dv(y), i =

l, 2,

на множестве

почти дословно повторяет доказательство

предыдущей теоремы.

Мы не будем подробно останавливаться

на

построении смешан-

ных стратегий

бескоалиционных играх

п лиц с

бесконечным

числом стратегий

доказательстве существования ситуации равно-

весия

по

Нэшу. Отметим только,

что

если функции выигрыша

игроков Hi (х) непрерывны

на

декартовом произведении А

=]~[

f-i

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

то в

такой бескоалицион-

ной игре всегда существует ситуация равновесия по Нэшу

смешан-

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

Для

существования ситуаций, оптимальных

по

Парето, достаточно компактности множества

{#(*)},

хеХ, что,

в свою очередь, может быть обеспечено компактностью

некото-

рой топологии множества всех ситуаций X и непрерывностью в этой

же топологии всех функций выигрыша

i=l, 2, ..., п.

Очевидно,

что для конечных бескоалиционных игр

это

всегда имеет место.

СВОЙСТВА ОПТИМАЛЬНЫХ РЕШЕНИЙ

5.1.

Приведем свойства ситуации равновесия, которые помогают

находить решение бескоалиционной игры двух лиц.

Теорема.

Для

того чтобы ситуация

(/**, v*) в

смешанных

стратегиях

игре Г =

(Л

, Н

)

была

ситуацией

равновесия,

необходимо

достаточно,

чтобы

для

всех

чистых стратегий

xeX

уеХ

игроков выполнялись следующие неравенства:

^(x.v-X^Oi'.v*);

(5.1)

(n*,y)^K

Qi*,

*).

(5.2)

Доказательство. Необходимость очевидна, поскольку каждая

чистая стратегия является частным случаем смешанной

и,

следова-

тельно, должны быть выполнены неравенства (5.1), (5.2).

Для до-

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

смешанным

стратегиям игроков 1

я2

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

неравенствах (5.1), (5.2).

Эта теорема (как

и в

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

что для доказательства равновесности ситуации

смешанных стра-

тегиях достаточно проверить неравенства (5.1),

(5.2)

только

для

чистых стратегий партнера.

Для

биматричной (/ихи)-игры Г

(А,

В)

133

эти неравенства принимают соответственно

вид

К,

{г,

y*)

^х*Ау*=К,

(x*,

у*);

(5.3)

(х*,

j)=x*l/^x*By* =

(x*,

у*),

(5.4)

где ai(ff) — строки (столбцы) матрицы

(В),

...,

т\

..., п.

5.2. Напомним,

что для

матричных

игр

каждая существенная

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

противника

(см. п. 7.6 гл. I).

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

для

биматричных

игр.

Теорема. Пусть

(А,

В) —

биматричная

(тхп)-игра

пусть

(х, y)eZ(T)

—

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

по Нэшу

смешанных

страте-

гиях.

Тогда выполняются равенства

К^у^К^у);

(5.5)

(x,j)=K

(x,y)

(5.6)

для всех

ieM

ujeN

, где

)

—

спектр смешанной стратегии

х(у).

Доказательство.

По

теореме

п. 5.1

имеем

К^уХК^у)

(5.7)

для всех

ieM

Пусть выполняется хотя

бы

одно строгое неравенст-

во

(5.7),

т. е.

К^уХК^ъу),

(5.8)

где

Обозначим

компоненты вектора

х=(£

...,

). Тогда

(x,y)=f

(i,y) =

i-i

(i,y)=K

(x,y)

b=K

(x,y).

ieM

Противоречие доказывает справедливость (5.5). Равенства

(5.6) до-

казываются аналогично.

Данная теорема дает способ нахождения оптимальных смешан-

ных стратегий игроков

игре Г

(А,

В).

Действительно, предполо-

жим,

что мы

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

(х, у),

считая спектры

стратегий М„ N

заданными. Тогда оптимальные стратегии должны

удовлетворять системе линейных уравнений

y=v

(5.9)

}34

где

ieM

,jeN

— некоторые числа. Если же ситуация равно-

весия (х, у) вполне смешанная, то система уравнений (5.9) принима-

ет вид

u, (5.10)

xB=v

где

(1,

..., 1),

и>

(1,

..., 1) — векторы соответствующей размер-

ности, составленные из единиц, числа v

xAy, v

xBy — выигры-

ши игроков в ситуации равновесия (х, у).

5.3.

Теорема. Пусть Г (А, В) — биматричная (тхп)-игра и ма-

трицы А, В — невырожденные. Если игра Г имеет вполне смешанную

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

мулам

x=v

uB~

; (5.11)

A-

u, (5.12)

где

= \l{uA-

u), ь

= \1(иВ-

и). (5.13)

Обратно, если для векторов х, у е

FT,

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

(5.11) — (5.13), справедливо х^О, у^О, то пара (х, у) образует

ситуацию равновесия в смешанных стратегиях в игре Г (А, В) с век-

тором равновесных выигрышей (v

Доказательство. Если (х, у) — вполне смешанная ситуация

равновесия, то х и у с необходимостью удовлетворяют системе

(5.10).

Умножая первое из равенств (5.10) на А'

, а второе — на

В'

получаем (5.11), (5.12). С другой стороны, поскольку хи=1

и уи=1, находим значения для v

и v

. Единственность вполне

смешанной ситуации (х, у) следует из единственности решения

системы (5.10) в условиях теоремы.

Докажем обратное утверждение

теоремы. По построению векторов

х,

у согласно (5.11) — (5.13) имеем

хи=уи=\.

Отсюда и из условия

х^О,

у^О следует, что (х, у) — си-

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

в игре Г.

Согласно теореме п. 5.1 для того,

чтобы ситуация (х, у) являлась ситу-

ацией равновесия в смешанных стра-

тегиях в игре Г (А, В), достаточно

выполнения условий

(i, y)^xAy, i=T7rh,

хУ=К

(х,

^ xBy, j=T7m,

•(5/2,5/2)

135

или

Ау^(хАу)и, хВ ^(хВу)и.

иВ-

Проверим справедливость этих соотношений для х=

иВ~

1и

тя

и у= . Имеем

иА'

У=~7^Т

„-1 » ,-i

хА

У)

иА

и (иВ

и)(иА '«)

uB~

u (иВ-

и)(иА-

и)

что и требовалось доказать.

Проиллюстрируем применение теоремы на примере игры «се-

мейный спор» п. 1.4. Рассмотрим смешанное расширение игры.

Множество точек, соответствующих векторам выигрышей в сме-

шанных стратегиях, можно изобразить графически (рис. 9, упр. 6).

Нетрудно заметить, что игра удовлетворяет условиям теоремы,

поэтому здесь имеется единственная вполне смешанная ситуация

равновесия (х, у), вычисляемая по формулам (5.11) —

(5.13):

х=(4/5,

1/5),у=(1/5,4/5),(«

.«

)

(4/5,4/5).

5.4. Рассмотрим свойства различных принципов оптимальности.

Заметим, что определения оптимальности ситуации по Парето

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

ной игры (в частности, двух лиц), поэтому они справедливы и для

смешанного расширения Г. Следовательно, для игры двух лиц

г(Г)=^Пг

(где Z(T) — множество ситуаций равновесия по Нэшу, Z

и Z

—

.множества наилучших ответов игроков 1 и 2 соответственно в игре

Г) и справедлива теорема о борьбе за лидерство (см. п. 2.5).

В более сложном отношении находятся ситуации, равновесные

по Нэшу и оптимальные по Парето. Из примеров § 2 следует, что

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

тимальна по Парето, и наоборот. Вместе с тем возможно, что одна

и та же ситуация оптимальна и в том и в другом смысле (п. 2.4).

примере

п. 3.3 было показано, что дополнительная ситуация

равновесия, возникающая в смешанном расширении игры Г, не

является оптимальной по Парето в смешанном расширении Г.

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

ричных игр.

Теорема. Пусть Г

(А,

В) —

биматричная (т

п)-игра.

Тогда

почти для всех (тхп)-игр (за

исключением

не более чем

счетного

множества

игр)

справедливо следующее

утверждение.

136

Ситуации

равновесия по Нэшу

смешанных

стратегиях,

которые

не являются

равновесными

исходной

игре,

не являются

оптималь-

ными

по

Парето

смешанном

расширении.

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

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

в множестве биматричных

(т

л)-игр.

Полное доказательство этой теоремы можно

найти в [10].

5.5.

Приведем без доказательства утверждения, касающиеся бес-

коалиционных игр

лиц, которые являются обобщением соответст-

вующих теорем из теории биматричных игр, рассмотренных в дан-

ном и предыдущем параграфах.

Теорема. Для того чтобы

ситуация

ц* в игре T = (N,

{Xi}

iBN

{Hi}

ieN

) была

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

смешанных

стратегиях,

необ-

ходимо и

достаточно,

чтобы

для

любого

i и

любой чистой

страте-

гии

XfSXt

выполнялось неравенство

K^Wx^KiQi*).

Теорема. В любой

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

игре существует

хотя бы одна

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

по Нэшу в смешанных стра-

тегиях.

Теорема.

Если равновесная стратегия

р.*

игрока

входит

в си-

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

р.*

приписывает положительную вероятность

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

х^Х

{

(р*

(х,)>0), то

(

*\\x

)=K

(p*).

5.6.

заключение параграфа рассмотрим пример решения бима-

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

телен.

Пример 12.

(Биматричные

(2х2)-игры [10].) Рассмотрим игру

(А,

В), в которой у каждого из игроков по две чистые стратегии.

Пусть

(A B)

' ^

1г)

^2 |_(

21> /*2l) (

22. hi)J

Здесь индексами 8

, т

обозначены чистые стратегии игроков

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

Предположим для простоты, что числа а

, а

(/?

, /?

02И 02г) различны.

Случай 1. В исходной игре Г, по крайней мере, один игрок,

пусть игрок 1, имеет строго доминирующую стратегию, скажем <5j

(см.

§ 8 гл. I). Тогда игра Г и ее смешанное расширение Г имеют

единственную ситуацию равновесия по Нэшу. Действительно, нера-

137

венства aii>a

приводят

тому, что

игре

чистая

стратегия д^ строго доминирует все остальные смешанные страте-

гии первого игрока. Поэтому ситуацией равновесия является пара

(<5

тД если /jjj.>Pi2i

@i.

гХ если Pu<Pi2-

Случай 2. Игра Г не имеет ситуации равновесия по Нэшу. Здесь

возможны два взаимоисключающих случая а) или б):

а)

ll9

Pu<Pi

, P

2<Piv

б)

i2>

Pi2<Pu> Ргх^гг*

причем det

АФО,

йеЬВфОя поэтому выполняются условия теоремы

п. 5.3. Поэтому в игре существует ситуация равновесия (х*, у*), где

д.1

РП-РИ

(514)

bz.

\Pii+Pii-

-Ри Р11+Р22-Р21-Р12,

J *HZ^

«AiZ^

(5.15)

\*ll

*ai

"12

11+

_а

12/

а соответствующие равновесные выигрыши v

и v

определяются по

формулам

-Я

PllPl2-012011

«21

Pll+P22-Pl2-P21

Случай

Игра

имеет две ситуации равновесия по Нэшу.

Этот случай получается, когда выполнено одно из условий:

а)

, a

<Рц, Рг\.<Ргг>

б)

«X

«22

12' Pll<Pl2> Pl2<Pll-

В случае а) равновесными будут ситуации

тД (5

, т

), а в случае

б) — ситуации (6

1г

), (8

, т

). Однако

смешанном расширении

есть еще одна вполне смешанная ситуация равновесия (х*, у*),

определенная формулами (5.14), (5.15).

Рассмотренные случаи исчерпывают изучение (2х2)-игры при

условии, что элементы в матрицах различны.

§ 6. РАВНОВЕСИЕ В СОВМЕСТНЫХ СМЕШАННЫХ СТРАТЕГИЯХ

6.1.

Продолжим рассмотрение игр двух

лиц.

Как уже отмечалось

§ 2,

даже если ситуация равновесия является недоминируемой

(оптимальной по Парето), возможны случаи, когда одна ситуация

равновесия выгодна игроку 1, а другая — игроку 2. Это затрудняет

нахождние взаимоприемлемого решения, возникающего неантаго-

нистического конфликта на уровне формализации бескоалиционной

игры. Поэтому исследуем неантагонистический конфликт

фор-

мализации, разрешающей игрокам принимать совместные решения.

138

Рис.

Проиллюстрируем этот подход на при-

мере игры «семейный спор» (см. при-

мер 1 п. 1.4).

Пример 13. Рассмотрим смешанное

расширение игры «семейный спор».

Множество точек, соответствующих

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

стратегиях в игре, можно изобразить

графически (см. рис. 9 п. 5.3). На рисун-

ке изображены две ситуации равнове-

сия по Нэшу с векторами выигрышей

(1,

4), (4, 1) в чистых стратегиях и одна

вполне смешанная равновесная ситуа-

ция с вектором выигрышей (4/5, 4/5)

(ищется с использованием теоремы п.

5.3), которая менее предпочтительна для игроков, чем каждая из

ситуаций равновесия в чистых стратегиях. Напомним, что равновес-

ными здесь являются ситуации: (a

/JJ, (a

, /?

), (

*> У*)'

гле

х*

(4/5,

1/5), У =

(1/5,

4/5), а ситуации (a

0Д (<х

, р

) также

оптимальны по Парето.

Если игра повторяется многократно, то игрокам имеет смысл

сделать совместный выбор: с вероятностью 1/2 выбирать ситуацию

) или (a

, f}

). Тогда средний ожидаемый выигрыш игроков

будет (5/2, 5/2). Однако эта точка не лежит в множестве точек,

соответствующих возможным ситуациям бескоалиционной игры

(рис . 9), т. е. не может быть реализована, если игроки выбирают

смешанные стратегии независимо.

Под

совместной смешанной стратегией

игроков будем понимать

вероятностное распределение на множестве всевозможных пар

(i,

(ситуаций в чистых стратегиях), не обязательно порожденное неза-

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

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

игры.

Обозначим М совместную смешанную стратегию в игре Г

(А,

В).

Тогда ожидаемые выигрыши К

(Л/),

(М) игроков 1 и 2 при

использовании совместной смешанной стратегии соответственно

равны

К,

(М) = £ <№

Кг

(^) = Е

Pvtb

'•J

где

A =

{a,j),

B={p,j) — матрицы выигрышей игроков,

М={/х

при

УгомиМп=\, Л/>0, « =

(1,

..., l)eR

(l,

..., l)eR". Геометричес-

ки множество точек, соответствующее множеству векторов выигры-

шей в совместных смешанных стратегиях,— это выпуклая оболочка

139