<<
>>

6.5. Дополнение. Существование и единственность вектора Шепли

Мы докажем здесь без особых подробностей существование и единственность значения Шепли (более подробно см., например, Воробьев, 1995).

Найдем сначала вектор Шепли для характеристической функции вида CVR , где с > 0, a VR — простейшая характеристическая функция, т.е.

функция вида VR(S) = |

1, если S D R,

О, в противном случае Легко видеть, что число различных простейших характеристических функций на I равно 2п — 1, т.е. числу непустых коалиций. Следующие два предложения мы приведем без доказательств.

Предложение 6.5.1. Все 2п — 1 простейших характеристических функций на I линейно независимы.

Предложение 6.5.2. Для любой характеристической функции v имеет место единственное представление

Rcl

ScR

где

Иными словами, это предложение утверждает, что каждую характеристическую функцию на J можно представить, и притом единственным образом, в виде линейной комбинации простейших характеристических функций.

Теорема 6.5.1. Если vr — простейшая характеристическая функция, то

{ шт если г ? R, ,

= { W . ' 5.1

(0, если г f R.

Доказательство. Множество R является для cvr носителем. Поэтому по аксиоме эффективности:

^Ф,-(сг;д) = сг;д(Д) = с. (5.2)

ieR

Ясно также, что перестановка любых двух игроков из R не меняет значения характеристической функции CVR ¦ Поэтому по аксиоме симметрии слева в (5.2) все слагаемые равны ДРУГ ДРУГУ) и мы получаем верхнюю строку (5.1). Наконец, все игроки, не входящие в R, являются в CVR болванами, и это дает нам нижнюю строку (5.1).

Следствие 6.5.1. Для простейшей характеристической функции vr и с > 0 Ф(сид) = сФ(ид) .

Доказательство следует непосредственно из (5.1).

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

Ф(^сдг;д) = ^Ф(сдг;д) = сдФ(ид). (5.3)

r r r

Распространим эту формулу на случай коэффициентов сд с произвольными знаками.

Лемма 6.5.1. Если v' и v" - характеристические функции, а их разность v' - v" также является характеристической функцией, то

$(v'-v") = Ф(г/) -Ф(и"). (5.4)

Доказательство. По условию мы имеем тождественно v' = v" + (г/ — v") . Справа здесь стоит сумма двух характеристических функций, и по аксиоме линейности мы имеем

ф(и') = Ф(и") + Ф(и'-и"),

откуда и следует (5.4).

Следствие 6.5.2. Формула (5.3) остается справедливой, если знаки коэффициентов cr произвольные, а сумма ^2rCrvr является характеристической функцией.

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

v = cRvR = ^2 CRVR ~ X] (~CR)VR-

R R R

CR>° СД<°

Здесь во второй сумме все числа — cr являются положительными, так что вычитаемая сумма оказывается характеристической функцией. Поэтому по лемме 6.5.1

Ф(и) = Ф( ^2 CRVR) ~ ф( (~cR)vR) =

R R

cR>0 cR<0

= Y CR®(VR) - ("ся)фЫ = ^сдф(г;).

R R R

cR>0 cR<0

Теорема 6.5.2. Каждая характеристическая функция имеет не более одного вектора Шепли.

Доказательство. То, что каждая простейшая характеристическая функция имеет не более одного вектора Шепли, следует из теоремы 6.5.1. Но в силу предложения 6.5.2 произвольная характеристическая функция представима в виде линейной комбинации простейших единственным способом. Поэтому из доказанного выше следует, что каждая характеристическая функция имеет не более одного вектора Шепли.

Нам остается доказать существование вектора Шепли для любой характеристической функции.

Теорема 6.5.3. Для любой характеристической функции v на I = {1,..., га} компоненты вектора Шепли определяются формулой

ieR'ci

Доказательство. Проверим сначала, что вектор Ф(и) с компонентами из (5.5) удовлетворяет всем аксиомам Шепли.

Докажем эффективность вектора Ф(и) . Для этого рассмотрим

Е<ВД = Е Е (n"|g|y'"1)!Kg)-t;(g\»))-(5.6)

iei iei ieR'ci

Во всей двойной сумме выражение v(K) встречается в роли уменьшаемого \К\ раз (по числу входящих в К элементов) и тем самым приобретает коэффициент

. Ап- \К\)1(\К\ - 1)! (п-\К\)-\К\\

\к\ j = j >

га! га!

который при \К\ = га, т.е.

при К = I, очевидно, равен единице. В роли же вычитаемого оно встретится га — \К\ раз (по числу не входящих в К элементов) и тем самым приобретает коэффициент

, ST-YM- 1^1 - (га - \К\)1\К\1

— (п—\К )- !—Ц———L = - Ц1^—L, если пф\к\,

га! га! и коэффициент 0 , если п = \К\ .

Таким образом, правая часть (5.6) равна v(I) :

J2Mv) = V(I)1 (5.7)

iei

и вектор Ф(и) оказывается эффективным.

Проверка аксиомы болвана тривиальна. Пусть в игре v игрок i является болваном. Тогда для любой коалиции К С I

v(K) - v(K\i) = О,

а следовательно, каждое слагаемое в (5.5) для этого i равно 0. Поэтому

= 0.

Проверим теперь аксиому симметричности. Пусть тг — перестановка I такая, что V(TTK) = v(K) для любой коалиции К . Тогда вместе с К коалиция тг К также пробегает все подмножества I, и мы можем (5.5) переписать как

ж ^ V- (п~ КК|)!(|тгК|- 1)!. . . . . ...

ФТГ.-И= ^Т — (v(ttR) — V(TTK \ 7ГГ)).

С другой стороны, поскольку v(irK) = v(K) и \тгК\ = \К\ , то 7гг и 7ГК под знаком суммирования можно обратно переименовать соответственно в г и К. Окончательно мы имеем

Фт-(„) = ? i*-\mm-i)iiviK) _ v{K V)) = ф.(и)_

Kcl

Аксиома линейности следует из того, что компоненты вектора Ф(и) зависят от значений характеристической функции v линейно.

Таким образом, вектор Ф(и) действительно является для характеристической функции v вектором Шепли, существование которого тем самым доказано.

<< | >>
Источник: С. Л. Печерский, А. А. Беляева. Теория игр для экономистов. 2001

Еще по теме 6.5. Дополнение. Существование и единственность вектора Шепли:

  1. Свойства равновесия Курно в случае постоянных и одинаковых предельных издержек
  2. 3.C.2 Восстановление предпочтений на основе функции расходов
  3. 3.C.4 Интегрируемость (рационализуемость) спроса
  4. 5.3 Существование общего равновесия
  5. 5.5.1 Задачи
  6. 14.1.1 Свойства равновесия Курно в случае постоянных и одинаковых предельных издержек
  7. 6.1. Классические кооперативные игры
  8. Нечеткая кооперативная игра
  9. 6.5. Дополнение. Существование и единственность вектора Шепли
  10. 6.7. Задачи
  11. Счастье
  12. Глава четвертая. ХАРАКТЕРИСТИКА И ПОНЯТИЕ ГОСУДАРСТВА