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

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

Рис.

15 Рис. 16

всех дележей. Хотя элементы С-ядра и не доминируются никакими

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

любого наперед заданного дележа а найдется доминирующий его

дележ. Поэтому оказывается целесообразной формулировка при-

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

ятельство.

Определение. Подмножество дележей L кооперативной игры

(N, v) называется Н — М-решением, если:

1) из

<х>Р

следует, что либо

<хфЬ,

либо рфЬ (внутренняя устой-

чивость);

2) для любого

<хфЬ

существует такой дележ f}$L, что /?^=а

(внешняя устойчивость).

К сожалению, применение понятия Н — М-решения на практике

невозможно. Оно несет скорее философский, нежели практический

смысл.

Между С-ядром кооперативной игры и ее Н — Л/-решением

имеется известная связь. Например, если С-ядро не пусто и Я — М-

решение существует, то оно содержит С-ядро. Действительно, пусть

дележ а принадлежит С-ядру; тогда если бы он не принадлежал

Н — М-решению L, то согласно свойству 2) нашелся бы такой

дележ а', что а'^=а. Однако это противоречит принадлежности а С-

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

Теорема. Если для характеристической функции игры (N, v)

в (0 — \)-редуцированной форме

(\Щ

— п)

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

»(S)<—i—,

л-ISI + l

где \S\ — число игроков в коалиции S, то

С-ядро

этой игры не пусто

и является ее Н — М-решением.

160

Доказательство. Возьмем произвольный дележ

а,

лежащий

вне С-ядра. Тогда существует непустое множество коалиций

{S}, по

которым можно доминировать

а, т. е. это те и

только

те

коалиции

для

которых <x(S)<v

(S).

Множество

{S}

частично упорядочено

по включению,

т. е.

, если З^з,^. Возьмем

в нем

какой-

нибудь минимальный элемент

который, очевидно, существует.

Пусть

к—

число игроков

коалиции

Очевидно, 2^к^п— 1.

Построим дележ /? следующим образом:

«(S

)-a(S

)

а,Н

, 16Л

.-* •

°-

Так как f}(S

)=v(S

), /?,>а,-,

ieS

то В доминирует а по коалиции

. Докажем, что В содержится в С-ядре. Для этого достаточно

показать, что fJ(S)^v(S) при произвольном S. Пусть сначала

\S\^k.

Заметим, что

не доминируется по S

, так как f}(S

)=v(S

)

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

5<=

, поскольку

/?,>а,

(ieS

a 5"

— минимальная коалиция, по которой можно

доминировать а. Если же хоть один игрок из S не содержится

в So, то

п-к п-к n-fc+1

n-|S|

Таким образом, /J не доминируется ни по какой коалиции, содер-

жащей не более к игроков.

Пусть теперь

\S\>k.

Если S^S

, то

я/с» (1Д1-*)д-"(До)> . ,owW-t

p(S)= +v(S

п—к

|Д|-*+*-|Д1+1

1 ^ ,_

и-*+*-|5|

+ 1 я-151 + 1

Если

же S не

содержит

, то

число игроков множества

S, не

содержащихся

в S

, не

меньше

\S\

—

k+1,

поэтому

B(S)> >——->———>v(S).

п-к п-к+\

л-ISj + l

Таким образом,

В не

доминируется

ни по

какой коалиции

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

содержится

С-ядре. Кроме того,

доминирует

а. Итак, доказано,

что

С-ядро непусто

удовлетворяет свойству

характеризующему множество

— М-решений. Свойству

С-ядро

161

удовлетворяет автоматически в силу определения. Теорема до-

казана.

9.6. Определение. Игра {N, v) в

(О

—

\)-редуцированной

форме

называется

простой,

если для любых S^N v(S) принимает лишь

одно из двух значений О или 1.

Кооперативная

игра называется

простой,

если проста

ее

(О

—

\)-редуцированная

форма.

Пример 19 [2]. Рассмотрим простую игру трех лиц в (0 — 1)-

редуцированной форме, в которой коалиция, состоящая из двух

и трех игроков, выигрывает

(«(5)

1),

а коалиция, включающая

только одного игрока, проигрывает («({z}) =

0).

Для этой игры

рассмотрим три дележа:

(1/2,

1/2, 0), а

(1/2,

0, 1/2), а

(0,

1/2, 1/2). (9.7)

Ни один из этих трех дележей не доминирует никакого другого.

Множество дележей (9.7) имеет и следующее свойство, любой дележ

(кроме трех дележей

)

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

. Чтобы

это проверить, рассмотрим какой-нибудь дележ а=(а

1а

, а

). Так

как мы рассматриваем игру в (0 — 1)-редуцированной форме, то

а,^0 и а

+ а

Следовательно, не более двух компонент

вектора а могут быть не меньше 1/2. Если их действительно две, то

каждая из них равна 1/2, в то время как третья равна 0. Но это

означает, что а совпадает с одним из а

. Если же а — какой-нибудь

иной дележ, то он имеет не более одной компоненты, не меньшей

чем 1/2. Значит, по крайней мере две компоненты, например,

а,-

и а,,

где i<j, меньше 1/2. Но в этом случае

>a.

Таким образом, три

дележа (9.7) образуют Н

—

М-решение. Но это не единственное

—

М-решение.

Пусть с — любое число из отрезка [0, 1/2]; легко проверить, что

множество

={(a,

\-c-a, c)|0s£a<l-c}

также является Н

—

Af-решением. Действительно, в это множество

входят дележи, при которых игрок 3 получит постоянную с, а игро-

ки 1 и 2 делят остаток во всевозможных пропорциях. Внутренняя

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

из

этого множества имеем: если

то а

. Однако доминиро-

вание по коалиции, состоящей из единственного участника, невоз-

можно. Чтобы доказать внешнюю устойчивость L

, „ возьмем ка-

кой-либо дележ рфЬ

3с

. Это означает, что либо /?

>с, либо

<с.

Пусть Р

>с, например

= с + е. Определим дележ а следующим

образом:

<*i=0i +

/2,

=Д

е/2,

=с

162

Тогда, <xeL

и а^Р по коалиции {1,

2}.

Пусть теперь Р

<с. Ясно,

что либо

^1/2,

либо /?

^1/2 (ибо в противном случае их сумма

была бы больше 1). Пусть

^ 1/2. Положим а =

(1 —

с,

О,

с). Так как

1 —

ol/l^Pi, то а^р по коалиции {1, 3}. Очевидно, что ае!^,

с-

Если же /?

< 1/2» то можно показать аналогично, что y^/J, где у =

(0,

1-е,

с).

Итак, кроме симметричного Я — М-решения, рассматрива-

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

3 получает фиксированное количество с из отрезка 0<с<1/2. Эти

—

Л/-решения называются дискриминирующими; говорят, что

игрок 3 при этом дискриминирован. В случае множества

Z^_

гово-

рят, что игрок 3 полностью дискриминирован или исключен.

Из соображений симметрии очевидно, что существуют также два

семейства Н

—

Л/-решений L

h c

Z^,

„ в которых дискриминируют-

ся игроки 1 и 2 соответственно.

Предшествующий пример показывает, что у игры может быть

чрезвычайно много Н

—

Л/-решений. Совершенно неясно, какое из

них следует выбрать. Когда же Я — Л/-решение выбрано, остается

непонятным, какой из него выбрать дележ.

Существование Н

—

Л/-решений в общем случае до сих пор не

доказано, однако получены некоторые частные результаты. Одни из

них касаются существования Н — М-решений для конкретных клас-

сов игр, другие — существования решений определенного типа [5].

§ 10. ВЕКТОР ШЕПЛИ

10.1.

Множественность рассмотренных ранее принципов оптима-

льности С-ядра и Я

—

Af-решения в кооперативных играх, а также

жесткие условия существования этих принципов стимулируют по-

пытки поиска принципов оптимальности, существование и единст-

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

игре.

К таким принципам оптимальности относится вектор Шепли.

Вектор Шепли определяется аксиоматически.

Определение. Носителем игры (N, v) называется такая ко-

алиция Т,

что

v(S)=v(S(~)T) для

любой коалиции

S<=N.

Содержательно определение утверждает, что любой игрок, не

принадлежащий носителю, является «болваном», т. е. не может

ничего внести ни в какую коалицию.

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

жества игроков iV={l, 2, ..., л}. С этой перестановкой связана

подстановка я, т. е. такая взаимно однозначная функция я: N-*N,

что для ieN значение n(i)eN представляет собой элемент из N,

в который переходит ieN в перестановке Р.

Определение. Пусть (N, «) —

игра

п лиц. Р —

перестановка

множества

N, an —

соответствующая ей

подстановка.

Тогда через

163

(N, nv) обозначим такую игру (N, и), что для любой коалиции ScN,

S={i

, i

i,}

иЦп^п^),

...,n(Q})=v(S).

По существу игра (N, nv) отличается от игры (N, v) лишь тем, что

в последней игроки поменялись ролями в соответствии с переста-

новкой Р.

С помощью этих определений можно изложить аксиоматику

Шепли. Сначала заметим, что так как кооперативные игры к лиц,

в сущности, отождествляются с вещественными (характеристичес-

кими) функциями, то можно говорить о сумме двух или большего

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

10.2.

Поставим в соответствие каждой кооперативной игре (N, v)

вектор <pH=(<j0iM, ..., 9>n[v]), компоненты которого будем интер-

претировать как выигрыши, полученные игроками в результате

соглашения или решения арбитра. При этом будем считать, что

указанное соответствие удовлетворяет следующим аксиомам.

Аксиомы Шепли.

Если S — любой носитель игры (N, ю), то

5>,Н=«(5).

ieS

Для любой подстановки п и ieN

Если (N, и) и (N, v) — две любые кооперативные игры, то

<Pi[u+v]

q>,[u]

<f>i[v].

Определение. Пусть

— функция, ставящая в соответствие

согласно аксиомам 1 — 3 каждой игре (N, v) вектор

q>[v].

Тогда

<p[v]

называется вектором значений или вектором Шепли игры (N, v).

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

ственным образом значения для всех игр п лиц.

Теорема. Существует единственная функция

q>,

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

для всех игр (N, v) и удовлетворяющая аксиомам 1 — 3.

10.3.

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

таты.

Лемма. Пусть для любой коалиции SczN игра (N, w

) определя-

ется следующим образом:

164

Тогда

для

игры

(N, w,)

аксиомы

1, 2

однозначно определяют вектор

9,Ы = № .'!*

(10-2)

где

-s=

|iS|

— число игроков в S.

Доказательство. Ясно, что S — носитель w„ как и любое

множество Т, содержащее множество S. Тогда по аксиоме 1, если

ScT, то

Но это означает, что <p,[wj]=0 для i4S. Далее, если

— любая

подстановка, которая переводит S в себя, то nw

. Следователь-

но,

в силу аксиомы 2 для любых г, jeS имеет место равенство

<Pi[

s]=<Pj[ws]-

Так как этих величин всего s=

\S\,

а сумма их равна 1,

то <Pi[w

]=l/,s, если ieS.

Игра с характеристической функцией w

, определяемой (10.1),

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

ет, что для простой игры

{N,

) вектор Шепли определяется форму-

лой (10.2). Вектор Шепли для игры (N, w

) определяется единствен-

ным образом.

Следствие. Если с^О, то

<p,[cw

]-.

|ф,

ieS,

1 0, /#5.

Доказательство очевидно. Таким образом,

(p[cw

]=cq>[w

]

для

с>0.

Теперь покажем, что если ^c

является характеристической

функцией, то

<Pi

s)=E^(

s)=S

(

''(

s)- (Ю.З)

\s / s s

В случае

первое равенство в (10.3) постулируется аксиомой

второе следует из следствия. Далее, если и, v и и—v — харак-

теристические функции, то согласно аксиоме 3 имеем

(p[u—v]=q> [и] —

q>[v].

Отсюда следует справедливость (10.3) для лю-

бых c

. Действительно, если £

— характеристическая функция,

165

то

поэтому

= Yc

£ (-c

)

{S\c

»0}

\{S|c

<0}

)w S

<PM

-<P E

L{S|Cj»0} J L{S|Cs<0} J

E адЫ- E

s]=E<v)»K].

{S|<:

»0} {S

«>}

10.4.

Лемма. Пусть (N, v) —

любая

игра,

тогда найдутся

—1

вещественных чисел

таких, что

»=

(Ю.4)

ScJV

где w

определены

(10.1),

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

по

всем

подмноже-

ствам

множества

исключая пустое

множество.

При

этом

представление (10.4) единственно.

Доказательство. Положим

<*=

(-l)

~'v(T)

(10.5)

{Г|Гс=5)

(здесь

— число элементов

7). Покажем, что эти числа c

удовлет-

воряют условиям леммы. Действительно, если

— произвольная

коалиция,

то

Е **.(0)-

Е *«« Е ( Е

(-1Г'«(*))-

Е Г Е

<-ir'l«<D.

Рассмотрим теперь величину

квадратных скобках

последнем

выражении. Для каждого значения

между

и и имеется CJJIf таких

множеств

5 с s

элементами, что Гс=5с=

Следовательно, выраже-

ние

скобках можно заменить следующим выражением:

Е^=К-1Г'=Е^-'<(-1Г'.

v»-f

S-t

но это биномиальное разложение

—

1)"

Следовательно, для всех

t<u оно равно 0,

для

t=u

равно 1. Поэтому для всех

UcN

Е c

(U)=v(U).

{S|.S<=JV}

166

Докажем единственность представления (10.4). Любой харак-

теристической функции v соответствует элемент пространства

Действительно, упорядочим коалиции TaN. Тогда каждой

непустой коалиции

Гс=ЛГ

соответствует компонента вектора, равная

(Г).

Эти векторы будем обозначать, как и функции, через v. Очеви-

дно,

что простейшим характеристическим функциям w

соответ-

ствуют векторы, у которых компоненты равны либо нулю, либо

единице. Докажем, что простейшие характеристические функции

(точнее, соответствующие им векторы) линейно независимы. Дейст-

вительно, пусть

£ X

(T)=0 для всех TcN.

ScN

Тогда для Т={г] имеем w

({f}) =

если S=t{i}, и w

({i})=\, если

5'={i}.

Поэтому А{(} = 0 для всех

iczN.

Продолжим доказательство

методом индукции. Пусть A

=0 для всех ScT, 5#

Т.

Покажем, что

=0.

Действительно,

£ A

(7) = £ l

(T)=X

=0.

ScJV ScT

Таким образом, мы имеем 2

—1 линейно независимых вектора

в R

z -1

, поэтому любой вектор, а значит и любая характеристичес-

кая функция v единственным образом выражается в виде линейной

комбинации (10.4) простейших характеристических функций w

Лемма доказана.

10.5.

Перейдем к доказательству теоремы п. 10.2. Лемма п. 10.4

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

ной комбинации игр w

, причем представление (10.4) единственно.

Согласно п. 10.3 функция

q> [v]

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

соотношениями (10.3), (10.2).

Пусть (N, v) — произвольная игра. Получим теперь выражение

для вектора

q>[v].

Согласно п. 10.3, 10.4

Ф*И=

£ c

(p,[w

]= £ c

(lls),

но c

определены формулой (10.5). Подставляя (10.5) в это выраже-

ние,

получаем

<Pilv]= Е (1/*)Г I (-1Г'«(7)

= I Г I (-ir'(mv(T)

Положим

167

ViV)= £ (-iy-'(Hs). (10.6)

{S\7\JieS<=N}

Если i$T и T=T'\J{i}, то y,(7")=-у,(Г). Действительно, все

члены в правой части (10.6) в обоих случаях одни и те же,

и только t=t'+l, следовательно, они отличаются лишь знаком.

Таким образом, имеем

{Г|1бГ<=ЛГ}

Далее, если ieT, то ровно

Z.'

таких коалиций S

s элементами, что

Гс5.

В результате получаем хорошо известный определенный ин-

теграл:

y,(T)=i(-l)'-'C

(lls) =

1 1 •.

£(-1Г'(7

\x'-

dx=

f £(-ir'Qi<*'-'<&=

S-t J J J-»

0 0

1 1

= f*

i(-l)"'ОТ-',x

-'dx= ix^il-xf-'dx.

о о

Таким образом, имеем (бета-функция)

,~* (1-1)!(л-0!

у,(Г)=

л!

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

9iM= I

1)!

<)!

[t>(7)-t,(7\{/})]. (10.7)

Формула (10.7) определяет компоненты вектора Шепли в явном

виде. Это выражение удовлетворяет аксиомам

— 3 п. 10.2.

Заметим, кроме того, что вектор

<р [«]

всегда является дележом.

Действительно, в силу супераддитивности функции v

Ф. [«]>«({*}) X ; =»({»}) LCJJi ; =

«({*})•

{T\ieT^ff}

- t-l

10.6.

Если отвлечься от аксиоматического определения, то век-

тору Шепли, выраженному формулой (10.7), можно дать следующее

содержательное истолкование. Предположим, что игроки (элемен-

ты множества N) решили встретиться в определенном месте в опре-

деленное время. Естественно, что из-за случайных отклонений все

168

они будут прибывать в различные моменты времени; однако пред-

полагается, что все порядки прибытия игроков (т. е. их перестанов-

ки) имеют одну и ту же вероятность, а именно

1/(и!).

Предположим,

что если игрок /, прибывая, застает на месте членов коалиции Т\ {/"}

(и только

их),

то он получает выигрыш «(7)—v (7\{i}); иначе говоря,

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

в коалицию. Тогда компонента вектора Шепли <р,[«] представляет

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

в условиях этой

рандомизационной схемы.

10.7.

Для простой игры (п. 9.6) формула для вектора Шепли

особенно наглядна. Действительно, v(T)—v(T\{i}) всегда равно ли-

бо 0, либо 1, причем это выражение равно 1, если Т

—

выиг-

рывающая коалиция, а коалиция 7\

{г}

не является выигрывающей.

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

<р,м=Е('-1Ж«-0!М

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

коалиции 7Ъ

для которых коалиция 7\

{/}

не является выигрыва-

ющей.

Пример 20 [2]. (Игра с главным игроком.) В игре участвуют

п игроков, один из которых называется «главным». Коалиция S вы-

игрывает 1, если она либо содержит главного игрока и хотя бы

одного кроме него, либо всех

и— 1

«неглавных». Бели главный игрок

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

ется в следующем виде:

{

5Ь{/, и}, 1фп,

*э{1, .... 1.-1},

0, в остальных случаях.

Ясно,

что для всякой коалиции Г=э{и} условия v(T)=l

и »(7\{п}) = 0 выполняются тогда и только тогда, когда

2<|71<и-1.

Поэтому

(рпЫ=

X Ci-i ; =—•

1.2

л!

Поскольку игра имеет (0 — 1)-редуцированную форму,

л-1

1=1

Все неглавные игроки равноправны, поэтому в силу симметрии

9t[v] = ~—-, /=1, -, л-1.

л(л-1)

169