Лекция 23. Вектор Шепли

Вектор Шепли. Рассмотренные до сих пор решения коалиционных игр (яд­ро, НМ-решение) обладали двумя очевидными недостатками: их могло не быть совсем, или их могло быть много. А хотелось бы иметь такое понятие решения, которое с каждой игрой связывало бы единственный дележ. Это мечта теории игр - связать с каждой игрой ее значение, или цену игры. Одно из таких решений предложил Шепли (1953); называется оно вектором (или значением, Shapley value) Шепли. Мы изложим теорию значения Шепли для игр с побочными платежами.

Пусть имеется коалиционная игра с побочными платежами v : 2N —> К, заданная своими выигрышами v(K) для всевозможных коалиций К (и(0) = 0). Напомним, что при рассмотрении супермодулярных игр мы с каждым упорядочением игроков г связали некоторый дележ хт £ Шм. Упорядочением (или нумерацией) игроков называется биекция г : {1,..., п} —> N7 а дележ хт устроен так: игрок т(г) с номером г получает полезность и(т{1,..., г}) — г>(т{1,...,г — 1}). Иначе говоря, игрок получает тот прирост, который он привносит своим присоединением к коалиции предшествующих ему игроков.

В случае выпуклых игр дележи хт принадлежали ядру игры v. и более того, образовывали крайние точки ядра. В частности, центр тяжести точек хт (т.е. точка х* = (^2Т хт)/п\) также лежит в ядре и, в некотором смысле, является наиболее справедливым ядерным дележом.

Идея Шепли заключается в том, чтобы этой же формулой определить дележ для произвольных игр. А именно, вектором, или значением Шепли игры v называется элемент Ф(у) £ M.N, заданный явной формулой:

Напомним, что г пробегает здесь все нумерации игроков.

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

Ф(у

 

 

твероятность каждого упорядочения равна 1/п!, где п - число игроков) и есть соответствующая координата вектора Шепли.

Приведенную выше формулу можно переписать, делая акцент на значении Ф(у) для конкретного игрока г. Вот игрок г вошел в зал, и вместе с ним в зале оказалась коалиция К. В этот момент он получает выплату, равную у (К) — у (К — г). Нам остается посчитать, при скольких упорядочениях г происходит это событие (т.е. что после захода г в зале собирается коалиция К). Пусть г входит к-м по очереди, где к = \К\. До него была коалиция К' = К — г тз к—1 человека. Это дает (к — 1)! возможностей для входа участников из К' до г. После входа г остаются еще (п — к)\ возможностей для входа остальных игроков, из N — К. Таким образом полное число возможностей равно [к—1)\[п—к)\. И мы получаем следующую формулу для г-ж координаты вектора Шепли

ф(и)_ = ^ {к-Щп-к)\{<К) _ <к _ (б)

где к = \К\. Здесь суммирование идет по коалициям К7 содержащим игрока г. Однако можно суммировать и по всем коалициям К7 т.к. если К не содержит г7 то К — {}} = К. и этот член ничего не меняет.

Свойства вектора Шепли. Если исходную игру у понимать как функ­цию множеств (в том смысле, что она приписывает некоторое число у (К) произвольному подмножеству К С ./V), то значение Шепли - это аддитив­ная функция множеств. Таким образом вектор Шепли математически нуж­но понимать как правило, преобразующее произвольные функции множеств в аддитивные. Какими свойствами обладает это правило?

Первое - эффективность. Это значит, что сумма всех координат вектора Ф(у) равна г'(Л^). В самом деле, Ф(у) есть среднее из дележей, поэтому сам является дележом.

Однако в общем случае вектор Ф(у) не лежит в ядре (ядро может быть пусто, и даже если непусто). В общем случае он даже не индивидуально ра­ционален (если игра не супераддитивна).

Второе - симметрия, или анонимность. Значение вектора Шепли для игро­ка зависит только от ценностей у (К), но не от имени игрока. Более формаль­но, с каждой перестановкой тт : N —> N игроков можно связать новую игру

 

7тФ(у) = Ф(жу).

Это очевидно из формулы (5) для вектора Шепли. В частности, если два игрока симметричны в игре у7 то и значения Ф(у) для них совпадают. Это свойство можно трактовать как справедливость.

Третье - линейность. Операция перехода к значению Шепли линейна в том смысле, что значение Шепли для суммы двух игр равно сумме их значений,

Сумма игр определяется очевидным образом: (у + ъи)(К) = у(К) + ъи(К).

Это тоже очевидно из формулы (5) или (6).

Четвертое свойство состоит в том, что несущественные игроки ("болваны")

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

любой коалиции К выполняется у (К и г) = у (К). Добавление такого игрока

к любой коалиции не меняет ее ценность. Из формулы (5) или (6) видно, что

болван не получает ничего в векторе Шепли.

Вместо болванов можно говорить о носителе игры. Так называется минимальная ко­алиция Б, что у (К) = у (Б П К) для любой коалиции К. Очевидно, что носитель - это дополнение к множеству болванов (докажите!).

Аксиоматика вектора Шепли. Оказывается, что приведенные выше четыре свойства вектора Шепли полностью его задают. Более точно, назовем значением любое отображение Ф из всевозможных игр (с побочными плате­жами) в К^; значение Ф на игре у обозначим Ф[у]. Мы будем предполагать, что выполнены следующие свойства:

А1. Отображение Ф - это линейный оператор из К2^ в К^.

А2. Ф симметрично, т.е. для любой перестановки тт : N —> N

АЗ. Для любого болвана і Р[у](і) = 0.

А4. Сумма координат вектора Ф[у] равна у(М).

Теорема (Шепли). Существует единственное значение, удовлетворяю­щее аксиомам А1 — .44. и оно задается формулой (5).

Ф(у\) + Ф(у2) = Ф(уі + ^2), Ф(ау) = аФ(у).

Ф[тту]

7тФ[у].

Доказательство. Нужно проверить лишь единственность. Для этого мы введем в рассмотрение специальные "базисные", или простые игры, которые образуют базис в линейном пространстве К2 ~№ всех игр. А именно, с каж­дой непустой коалицией Б свяжем свою игру уз7 которая определяется сле­дующей формулой:

.   . _     Г 1, если Б С К

МК) = | 0;   если 5 ^ к ■

Таких игр ровно 2п — 1, поэтому можно рассчитывать, что они образуют базис (2те — 1)-мерного векторного пространства К2 ~№ всех игр. Это видно, например, из того, что они линейно независимы (почему?). Однако можно и непосредственно убедиться, что любая игра у разлагается по у$. В самом деле, пусть у - игра, и Б минимальная коалиция, для которой у (Б) отлично от нуля. Тогда можно рассмотреть игру у' = у — у(Б)уз- Для нее у'(Б) = О, как и для меньших коалиций. Двигаясь таким образом, мы разложим у по уз- Можно предложить и явную формулу:

V = Х>(^Ь, где ^Б) = ^(-1)1*НГЦТ). (7)

Отметим, что для любой коалиции К

у(К)

БсК

что позволяет рассматривать ц(Б) как вклад именно коалиции 5, очищенный от вкладов меньших подкоалиций.

В силу этого единственность Ф достаточно проверять для простых игр Уз. А для них все ясно. Игроки не из Б - болваны, и они получают по 0. Игроки из Б все равноценны и поэтому получают поровну. А сколько - говорит аксиома А4. □

Кстати, мы получаем еще одну формулу для вектора Шепли:

Ф[»](<) = Х>(£0(1/«).

или

Ф(г;) = ^/х(5)15/|5|, (8)

где [I - обратное преобразование Шепли (или преобразование Мебиуса) у. Формула (8) естественно трактуется как дележ "дивидента" ^(Б) коалиции Б поровну между ее участникам.

Приведем еще одну индуктивную формулу, полученную Хартом и Маско-леем и которую нетрудно извлечь из (5):

Пример. Есть много примеров с голосованием. Мы остановимся только на игре "помещик и батраки". Пусть есть помещик (плантатор с участком земли) и п — 1 батрак. Будем считать, что помещик, наняв к батраков, получает от сбора урожая доход /(&), часть которого он отдает батракам. Батраки сами по себе доход получить не могут. Это приводит нас к игре с побочными платежами г. где

Посчитаем значение Шепли для помещика (игрока 0). Помещик с вероят­ностью 1/п заходит на к-м шагу, поэтому его значение равно Х^=о 1(Ю/п-Приблизительно это площадь под кривой /. Значения для батраков равны между собой. И в сумме с выигрышем помещика равны $(п).