Методы решения. 
Основы математического моделирования социально-экономических процессов

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

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

с-Ядро (core) представляет собой множество недоминируемых дележей, т. е. коалиция всех участников не может увеличить выигрыш каждого участника собственными силами. Более строго, с-ядро — это множество эффективных распределений выигрыша, устойчивых к отклонениям любой коалиции игроков, т. е. множество векторов х = (.г,…, х_п), таких что ^ х, = о (Л^г),.

ieN

и для любой коалиции К с Довыполняется X х, — > v (K), где и — характерных стическая функция игры.

Эквивалентным является определение с-ядра кооперативной игры в терминах блокирования распределений выигрыша коалициями. Говорят, что коалиция К блокирует распределение выигрышах, если найдется другое распределение выигрыша у, такое что? У, ^ о (Д), и для любого участ;

ык

ника i € К выполнено г/_;>х_;. 'Гогда с-ядром кооперативной игры называется множество распределений выигрыша, которые не могут быть заблокированы ни одной коалицией.

Таким образом, с-ядро задается системой линейных уравнений и нестрогих линейных неравенств, поэтому геометрически оно является выпуклым многогранником, вершины которого и определяют входящие в ядро дележи. Поиск с-ядра, если оно существует, осуществляется путем нахождения координат этих вершин (например, графоаналитическим методом)^[1]. Для игр с п > 3 эта задача значительно усложняется, поэтому в учебной литературе рассматриваются примеры нахождения с-ядра лишь для трех или четырех игроков.

Рассмотрим еще один подход к поиску оптимальных решений кооперативных игр, предложенный Л. Шепли и ставший на сегодняшний день наиболее распространенным на практике. Этот подход основан на принципе справедливого дележа исходя из вклада каждого игрока в выигрыш коалиции.

Вкладом i-го игрока называется величина и (К) — и(Ki), т. е. приращение выигрыша коалиции (К) при участии г-го игрока по сравнению с выигрышем коалиции без этого игрока (Ki).

Вектор Шепли, или значение Шепли (Shapley value) Ф (о) = (Ф, …, Ф"), представляет собой распределение, в котором выигрыш каждого игрока Ф, равен его среднему вкладу в соответствующие коалиции К. В форме, практически реализуемой для расчетов, значение Шепли для каждого игрока имеет следующий вид (суммирование проводится по всем коалициям К, в которые входит г-й игрок):

где п — количество игроков; к — количество участников коалиции К.

Вектор Шепли удовлетворяет следующим свойствам (аксиомы Шепли) [17].

1. Линейность (аксиома агрегации). Ф (и) представляет собой линейный оператор, т. е. для любых двух игр с характеристическими функциями и и со.

для любой игры с характеристической функцией и и для любого а.

Это свойство показывает, что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.

• 2. Симметричность (аксиома симметрии). Получаемый игроком выигрыш не зависит от номера игрока. Это означает, что если игра со получена из игры и перестановкой игроков, то ее вектор Шепли Ф (со) есть вектор Ф (и) с соответствующим образом переставленными элементами (т.е. игроки, одинаково входящие в игру, должны получать одинаковые выигрыши).
• 3. Аксиома эффективности. При распределении общего выигрыша не должно выделяться ничего «бесполезному игроку», не вносящему вклада пи в какую коалицию. В теории кооперативных игр такой игрок называется болваном, т. е. для такого игрока i для любой коалиции К, содержащей г, выполняется о (К) — v (Ki) = 0 и, соответственно, Ф_; = 0. Благодаря этому свойству вектор Шепли позволяет полностью распределить имеющийся в распоряжении тотальной коалиции выигрыш, т. е. сумма компонент вектора Ф (и) равна и (Л'). Иными словами, при разделении общего выигрыша коалиции ничего не выделяется на долю «посторонних» игроков, не принадлежащих этой коалиции, но и ничего не взимается с них.

Приведем пример игры с болваном. В игре трех лиц характеристические функции определяются следующим образом: о (1) = 0, о (2) = и (3) = 1, о (12) = = и (13) = 1, и (23) = 3, и (123) = 3. В этой игре игрок 1 — болван.

Доказано (теорема Шепли), что для любой кооперативной игры существует единственное распределение выигрыша, удовлетворяющее аксиомам 1—3, и это распределение — вектор Шепли. Если вектор Шепли принадлежит с-ядру, то этот дележ одновременно справедлив и устойчив, но вектор Шепли может и не принадлежать непустому с-ядру.

Пример 6.2. Четыре акционера имеют следующее количество акции: 10, 20, 30 и 40 соответственно. Любое решение утверждается акционерами, имеющими в сумме большинство акций (> 50). Это решение считается выигрышем, равным единице. Поэтому данная ситуация может рассматриваться как простая игра четырех игроков, в которой выигрывающими коалициями являются следующие: {2; 4}, (3; 4}, (1; 2; 3}, {1; 2; 4}, {2; 3; 4}, (1; 3; 4}, (1; 2; 3; 4}. Необходимо найти оптимальный дележ выигрыша между акционерами.

Найдем вектор Шепли для этой игры. Вначале рассмотрим все коалиции, выигрывающие с первым игроком, но не выигрывающие без него. Имеется только одна такая коалиция: (1; 2; 3}, поэтому вектор Шепли для этого игрока содержит всего одно слагаемое. В данной коалиции три игрока, и вектор Шепли для первого игрока определяется как.

Далее определяем все выигрывающие коалиции, но не выигрывающие без второго игрока: (2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому.

1 5.

Аналогично определяем Ф₃ = - и Ф, = —.

( 1 5 Л В результате получаем вектор Шспли —•.

[ 12 4 4 12.

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

' 11 5 ^.

то получим распределение —;—;—; —, отличающееся от вектора Шепли, в котором выигрыши второго и третьего игроков равны, хотя третий игрок имеет больше акций. Это получается из-за того, что возможности образования коалиций у второго и третьего игроков одинаковы. Для первого и четвертого игроков выигрыши соответствуют их различию в количестве имеющихся акций.

• [1] См., например, работы [7, 17].