Курсовая работа: Кооперативные игры
В барицентрической системе координат всегда выполняется равенство
x1 + x2 + x3 = 1.
В плоскости всегда имеется точка с координатами x1, x2, x3, удовлетворяющими равенству (6). По этому бароцентрическая система координат автоматически удовлетворяет одному из условий, определяющих исход игры трёх игроков. С другой стороны, поскольку игра в (0, 1)-редуцированной форме, то точка x должна находиться в заштрихованном треугольнике (см. рис. 2). Дележи x1, x2, x3 должны удовлетворять неравенствам
x1 + x2 £ u(1, 2), x1 + x3 £ u(1, 3), x2 + x3 £ u(2, 3).
Очевидно, из условия дополнительности, что
x1 + x2 = 1 - x3 £ 1 = u(1, 2), x1 + x3 £ 1, x2 + x3 £ 1.
Делёж x = (x1, x2, x3) доминирует дележ y = (y1, y2, y3)
по коалиции {1, 2}, если x1 > y1, x2 > y2;
по коалиции {1, 3}, если x1 > y1, x3 > y3;
по коалиции {2, 3}, если x2 > y2, x3 > y3,
т.е. если делёж y находится в одном из заштрихованных параллелограммов (за исключением трёх граничных прямых, проходящих через точку x) на рис. 3, то делёж x доминирует делёж y, а всякая точка находящаяся в не заштрихованных треугольниках, является предпочтительнее исхода x.
x3 = - 1 x2 = - 1
x = (x1, x2, x3)
x3 = 1 - C3
x1 = 0
x1 = 1 - C1 x2 = 1 - C2
Рис.3 Рис. 4
Таким образом, если x и y - два исхода и ни один из них не предпочтительнее другого, то соответствующие точки лежат на прямой, параллельной одной из координатных осей.
Пример. Пусть имеется (0, 1)-редуцированная игра трёх игроков с ненулевой суммой.
Рассмотрим сначала условия доминирования дележа x = (x1, x2, x3) над дележём y = (y1, y2, y3) по коалиции {1, 2}. В этом случае имеем :
Поскольку может быть, что C3 < 1 , то первое из условий (7) нельзя отбросить, как это делает- ся в играх с постоянной суммой. Это значит что, x должна быть не ниже прямой
x1 + x2 = C3.
Или, учитывая (6), последнее уравнение принимает вид
x3 = 1 + C3 .
Таким образом, если делёж x таков, что
x1 ³ 1 - C1, x2 ³ 1 - C2, x3 ³ 1 - C3,
то имеется три параллелограмма, заштрихованных на рис. 4, находясь в которых, точки x доминируют y.
Если в (8) одно из неравенств, например, третье не имеет места, то есть только 2 парал- лелограмма, заштрихованных на рис. 5, находясь в некоторых точках x доминирует y.
x1 = 1 - C1 x2 = 1 - C
2 x2 = 1 - C
2 x1 = 1 - C
1
x3 = 1 - C3
x
Рис. 5 Рис. 6
Из рассмотренного примера видно, что возможно много вариантов, которые возникают при изучении вопросов, связанных с доминированием дележей в кооперативных играх. С ростом числа игроков чрезвычайно быстро растёт количество таких вариантов. В связи с этим возникает необходимость выделения вполне устойчивых дележей, т.е. таких дележей, которые не доминируются никакими другими дележами. Множество вполне устойчивых дележей в кооперативной игре называется с-ядром этой игры.
Теорема. Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией u, необходимо и достаточно, чтобы для любой коалиции K выполнялось неравенство
Поскольку неравенства (9) линейны относительно x, то из последней теоремы следует, что с-ядро в любой кооперативной игре является выпуклым многогранником.
К особенностям кооперативных игр относительно существования с-ядра относятся :
1) в несущественной игре с-ядро существует и состоит из единственного дележа этой игры;
2) во всякой существенной игре с постоянной суммой с-ядро пусто.
Для общей игры трёх игроков в (0; 1)-редуцированной форме имеем следующее (рис. 7).
Её характеристическая функция имеет вид :
u(Æ) = u(1) = u(2) = u(3) = 0;
u(1, 2, 3) = 1,
u(1, 2) = С3; u(1, 3) = С2; u(2, 3) = С1,
где 0 £ С1, С2, С3 £ 1.
На основании последней теоремы для принадлежности дележа x с-ядру необходимо и достаточно выполнение неравенств
x1 + x2 ³ C3, x1 + x3 ³ C2, x2 + x3 ³ C1
или, используя равенство x1 + x2 + x3 = 1, получим
x3 £ 1 - C3, x2 £ 1 - C2, x3 £ 1 - C1.
3
1 2
Рис. 7
Это означает, что точка x должна лежать ближе к i-й вершине основного треугольника (см. рис. 7), чем прямая
xi = 1 - Сi (i = 1,2,3)
Из неравенства (10) путём суммирования получим
x1 + x2 + x3 £ 3 - (С1 + С2 + С3)
или, учитывая, что x1 + x2 + x3 = 1, получим
С1 + С2 + С3 £ 2.
Неравенство (12) является необходимым условием существования непустого с-ядра. С другой стороны, если (12) выполняется, то можно взять такие неотрицательные e1, e2, e3, чтобы
,
и положить
xi = 1 - Ci - ei (i = )
Такие значения xi и удовлетворяют неравенствам (10), т.е. такой делёж x = (x1, x2, x3) принад- лежит с-ядру.
Геометрически непустое с-ядро является заштрихованным треугольником (рис. 7), со сто- ронами, выраженными уравнениями (11)
3 3
1 2 1 2
Рис. 8 Рис. 9
при условии, что выполняется соотношение
x1 + x2 + x3 = 1,
и решения любой пары уравнений (11) являются неотрицательными. Так, например, рассмот- рим систему
x1 = 1 - С1, x2 = 1 - С2.
Поскольку 0 £ С1 £ 1, 0 £ С2 £ 1, то x1, x2 ³ 0. Отсюда получаем
x3 = 1 - x1 - x2 = 1 - (1 - С1) - (1 - С2) = С1 + С2 - 1.
Для того, чтобы было x3 ³ 0, необходимо чтобы
С1 + С2 - 1 ³ 0
или
С1 + С2 ³ 1.
В этом случае с-ядро представлено на рис.7 в виде заштрихованного треугольника внутри основного треугольника. Аналогично рассматриваются остальные возможные варианты сочета- ний неравенств. Например, если С1 + С2 < 1, то с-ядро имеет вид заштрихованного четырёх- угольника внутри основного треугольника (рис.8). Вообще многогранник, представляющий с‑ядро, образуется как выпуклый многогранник пересечением прямых (11) и строк основного треугольника. Если, например, выполняются неравенства
С1 + С2 < 1; С2 + С3 < 1; С1 + С3 < 1,
то с-ядро представляется в виде шестигранника, заштрихованного на рис.9.
Очевидно, в решение кооперативной игры должны входить дележи, лучшие с определён- ной точки зрения. Так, дележи, входящие в с-ядро, являются устойчивыми в несколько пассив- ном смысле, т.е. при этих обстоятельствах нет оснований отклоняться от такого дележа. Одна- ко, найти делёж, который не только не доминировался бы какими-либо другими дележами, но сам доминировал бы любой другой делёж, не удаётся. Поэтому решение отыскивают на пути расширения класса дележей . И это расширение состоит в том, что решением игры должен быть не один делёж, а некоторое их множество.
Дж. фон Нейман и О. Моргенштерн предложили потребовать от множества дележей, которое принимается в качестве решения кооперативной игры следующие два свойства: внут- реннюю устойчивость, состоящую в том, чтобы дележи из решений нельзя было противопоста- вить друг другу, и внешнюю устойчивость, состоящую в возможности каждому отклонению от решения противопоставлять некоторый делёж, принадлежащий решению. В результате мы приходим к следующему определению.
Определение. Решением по Нейману-Моргенштерну (Н-М-решением) кооперативной игры называется множество R дележей в нём, обладающее следующими свойствами :
1) внутренняя устойчивость: никакие два дележа из R не доминируют друг друга;
2) внешняя устойчивость: каков бы ни был делёж S не принадлежащий R, найдётся делёж r, принадлежащий R, который доминировал бы S.
Содержательная интерпретация Н-М-решения состоит в том, что любые две нормы пове- дения, соответствующие Н-М-решению, не могут быть противопоставлены друг другу; каково бы ни было отклонение от допустимых поведений, найдётся такая коалиция, которая будет стремиться к восстановлению нормы.
Теорема. Если в кооперативной игре существует с-ядро C и Н-М-решение R, то CÌ R.
Свойства Н-М-решений.
Н-М-решение кооперативной игры не может состоять только из одного дележа, т.к. в этом случае характеристическая функция игры несущественная.
Недостатки Н-М-решения.
1. Известны примеры кооперативных игр, которые не имеют Н-М-решений. Более того, в настоящее время не известно каких-либо критериев, позволяющих судить о наличии у кооперативных игр Н-М-решений. Тем самым заложенный в Н-М-решении принцип оптимальности не является универсально реализуемым, и область его реализуемости пока остаётся неопределён- ной.
2. Кооперативные игры, если не имеют Н-М-решения, то, как правило, более одного. Поэтому принцип оптимальности, приводящий к Н-М-решению, не является полным: он, вообще говоря, не в состоянии указать игрокам единственной системы норм распределения выигрыша.
3. Решения существенных кооперативных игр состоит более, чем из одного дележа. Таким образом, даже выбор какого-либо конкретного Н-М-решения ещё не определяет выигрыша каждого из игроков.
4. Понятие Н-М-решения отражает только в очень малой степени черты справедливости.
Перечисленные недостатки отражают положение дел в действительности: большинство экономических и социальных проблем допускает множественные решения, и эти решения не всегда поддаются непосредственному сравнению по их предпочтительности.
Перечисленные недостатки Н-М-решения коалиционных игр способствуют поискам новых подходов. Одним из таких подходов является подход Шепли, суть которого в том, что он строиться на основании аксиом, отражающих справедливость дележей.
Определение. Носителем игры с характеристической функцией u называется такая коали-ция T, что
u(S) = u(S Ç T)
для любой коалиции S.
Смысл носителя T состоит в том, что любой игрок, не принадлежащий T, является нейтральным, он не может ничего внести в коалицию и ему ничего не следует выделять из общих средств.
Определение. Пусть u – характеристическая функция
кооперативной игры n игроков, p – любая перестановка множества N игроков. Через pu обозначим
характеристическую функцию и та- кой игры, что для коалиции S = {i1, i2, ..., iS} будет
u ({p( i1), p( i2), ..., p( iS)}) = u(S).
Содержательный смысл функции pu состоит в том, что если в игре с характеристической функцией u поменять местами игроков согласно перестановке p, то получим игру с характерис- тической функцией pu.
Аксиомы Шепли.
1о. Аксиома эффективности. Если S – любой носитель игры с характеристической функцией u, то
=
u(S)
Иными словами, “справедливость требует”, что при разделении общего выигрыша носителя игры ничего не выделять на долю посторонних, не принадлежащих этому носителю, равно как и ничего не взимать с них.
2о. Аксиома симметрии. Для любой перестановки p и iÎN должно выполняться
(pu) = ji (u),
т.е. игроки, одинаково входящие в игру, должны “по справедливости” получать одинаковые выигрыши.
3о. Аксиома агрегации. Если есть две игры с характеристическими функциями u¢ и u¢¢, то
j i (u¢ + u¢¢) = j i (u¢) + j i (u¢¢),
т.е. ради “справедливости” необходимо считать, что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.
Определение. Вектором цен (вектором Шепли) игры с характеристической функцией u называется n-мерный вектор
j (u) = (j1(u), j2(u), ..., jn(u)),
удовлетворяющий аксиомам Шепли.
Существование вектора Шепли вытекает из следующей теоремы
Теорема. Существует единственная функция j, определённая для всех игр и удовлетворяющая аксиомам Шепли.
Определение. Характеристическая функция wS(T), определённая для любой коалиции S, называется простейшей, если
wS(T) =
Содержательно простейшая характеристическая функция описывает такое положение дел, при котором множество игроков S выигрывает единицу тогда и только тогда, когда оно содержит некоторую основную минимальную выигрывающую коалицию S.
Можно доказать, что компоненты вектора Шепли в явном виде запишутся следующим образом
где t – число элементов в T.
Вектор Шепли содержательно можно интерпретировать следующим образом: предельная величина, которую вносит i-й игрок в коалицию T, выражается как
u(T) - u(T \{i})
и считается выигрышем i-го игрока; gi (T) – это вероятность того, что i-й игрок вступит в коалицию T \{i}; ji (u) – средний выигрыш i-го игрока в такой схеме интерпретации. В том случае, когда u – простейшая,
Следовательно
,
где суммирование по T распространяется на все такие выигрывающие коалиции T, что коалиция T \{i}не является выигрывающей.
Пример. Рассматривается корпорация из четырёх акционеров, имеющих акции соответственно в следующих размерах
a1 = 10, a2 = 20, a3 = 30, a4 = 40.
Любое решение утверждается акционерами, имеющими в сумме большинство акций. Это решение считается выигрышем, равным 1. Поэтому данная ситуация может рассматриваться как простая игра четырёх игроков, в которой выигрывающими коалициями являются следующие:
{2; 4}, {3; 4},
{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},
{1; 2; 3; 4}.
Найдём вектор Шепли для этой игры.
При нахождении j1 необходимо учитывать, что имеется только одна коалиция T={1;2;3}, которая выигрывает, а коалиция T \{1} = {2; 3} не выигрывает. В коалиции T имеется t = 3 игрока, поэтому
.
Далее, определяем все выигрывающие коалиции, но не выигрывающие без 2-го игрока: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому
.
Аналогично получаем, что ,
.
В результате получаем, что вектор Шепли равен . При этом, если считать,
что вес голоса акционера пропорционален количеству имеющихся у него акций, то
получим следующий вектор голосования
,
который, очевидно, отличается от вектора Шепли.
Анализ игры показывает, что компоненты 2-го и 3-го игроков равны, хотя третий игрок имеет больше акций. Это получается вследствие того, что возможности образования коалиций у 2-го и 3-го игрока одинаковые. Для 1-го и 4-го игрока ситуация естественная, отвечающая силе их капитала.