Теория полезности фон Неймана-Моргенштерна и расчет оптимальных портфелей для различных моделей финансовых рынков

++=1000, . 200, 300, 0,

+800, +500, +650.

Рис. 2.2.1. Графическая иллюстрация С-ядра (пример 2.2.3).

Размерность соответствующего многогранника равна 2, поэтому его вершины можно определить графическим методом. Так как =1000--, то получаем систему 200350, 300500, 800 +1000. Множество всех дележей соответствует треугольнику ABC рисунка 2.2.1, а С-ядро - маленькому заштрихованному треугольнику внутри него. Вершинами С-ядра являются дележи (350,450,200), (350,500,150), (300,500,200), то есть выигрыш каждого игрока определяется с точностью до 50 долларов. Справедливым компромиссом внутри С-ядра является его центр =(333, 483, 183) (среднее арифметическое вершин). Запишем (0,1)-нормальную форму данной игры:

=0, i=1,2,3; (1,2)=3/5, (1,3)=3/5, (2,3)=7/10, (1,2,3)=1.

После такого преобразования становится ясно, что коалиции {1,2}={певец, пианист} и {1,3}={певец, ударник} имеют одинаковую силу, которая меньше силы коалиции {2,3}={пианист, ударник}.

Пример 2.2.4 ("Распределение прибыли" [15, с.135]). Объект коллективного пользования может обслуживать четырех потребителей (районы, фирмы и т.п.). Каждый потребитель может быть либо обслужен, либо нет, например, подключен к локальной системе водоснабжения или нет. Минимальные затраты на обслуживание пользователей наиболее эффективным способом таковы: один потребитель - 40, два потребителя - 60, три потребителя - 70, четыре потребителя - 80, т.е. функция затрат симметрична и имеет вид Подключение к рассматриваемому объекту приносит пользователям следующие доходы: =41, =24, =22, =12. Ясно, что потребителю i не выгодно обслуживаться, если он должен заплатить больше, чем . Вычислим характеристическую функцию. Максимально возможная прибыль любой коалиции пользователей есть наибольшая прибыль по всем ее подкоалициям, включая нулевую прибыль, когда никто не обслуживается

(S)=,

(3,4)=max{0, 22 - 40, 12 - 40, (22 + 12) - 60}=0,

(1,2)=max{0, 41 - 40, 24 - 40, (41 + 24) - 60}=5,

(1,4)=max{0, 41 - 40, 12 - 40, (41 + 12) - 60}=1 и т.д.

Таким образом, игроки 3 и 4 не могут получить никакой прибыли ни по отдельности, ни вместе, поскольку их доходы слишком малы. Если коалиция состоит из игроков 1 и 2, то они получают прибыль в 5 единиц. Если игрок 4 присоединяется к игроку 1, то ему это в действительности не помогает, т.к. обслуживаться будет только игрок 1. Окончательно получаем:

(1)=1, (2)=(3)=(4)=0, (1,2)=5, (1,3)=3, (1,4)=1, (2,3)=(2,4)=(3,4)=0, (1,2,3)=17, (1,2,4)=7, (1,3,4)=5, (2,3,4)=0, (1,2,3,4)=19.

Максимальная прибыль достигается при совместном обслуживании всех пользователей. Задача заключается в ее распределении ее между игроками. С-ядро определяется системой

1, , ,0, +5, +3,

++17, ++7, ++5, +++=19,

из которой исключены зависимые неравенства. С-ядро не совпадает с множеством дележей, но устанавливает достаточно широкие границы распределения прибыли. С-ядру принадлежит дележ =(19,0,0,0), при котором вся прибыль отдается игроку 1, а также дележ =(1,8,8,2), где игрок 1 остается на своем собственном гарантированном уровне прибыли, а вся выгода от кооперации идет остальным игрокам.

Пример 2.2.5 ("Чистые торги" [16, с.318]). Администрация города может выделить n фирмам сумму в d долларов для ремонта дорог. Если фирмы не смогут договориться между собой о распределении денег, то деньги не выделяются. Итак, (N)=d >0 и (S)=0, если S< n. Нужно выяснить, смогут ли фирмы договориться. В данной игре С-ядро совпадает с множеством всех дележей D().

Пример 2.2.6 ("Взвешенная мажоритарная игра" [16, с.319]). Игрок i имеет голосов. Коалиция выигрывает (побеждает), если сумма ее голосов не меньше некоторой доли Q от их общего количества (Q ). Эта игра задается (n+1)-м числом (Q; ,…,). Характеристическая функция игры имеет вид

Взвешенные мажоритарные игры возникают во многих случаях. Например, игроки могут быть акционерами компании, а число голосов игрока соответствовать его доле акций. В качестве игроков можно рассматривать также избирательные округи. Число голосов, которыми обладает округ в законодательном органе, соответствует численности населения. Число голосов игрока не всегда соответствует его реальной силе. Например, в игре (51; 49, 48, 3) для победы необходимо простое большинство в 51 голос. Выигрывающие коалиции: {1,2}, {1,3}, {2,3} и {1,2,3}. Такие же выигрывающие коалиции имеет игра (2; 1,1,1), у которой все игроки равной силы, т.к. обладают одинаковым числом голосов. Следовательно, и в игре (51; 49, 48, 3) игроки также имеют одинаковую силу относительно их влияния на выбор исхода игры. С-ядро игры (2; 1,1,1) определяется системой

, , 0, +1, +1, +1, ++=1.

Складывая последние три неравенства, получаем ++3/2, что противоречит соотношению ++=1. Следовательно, C()=.

Упражнения

Используя графический метод определить все вершины С-ядра следующей игры трех лиц:

(1,2,3)=1000, (1)=200, (2)=300, (3)=0,

(1,2)=800, (1,3)=500, (2,3)=650.

Выбрать два дележа. Один из этих дележей не должен принадлежать С-ядру. Связаны ли дележи отношением доминирования? Проверить, принадлежат ли С-ядру вектор равномерного распределения прибыли и вектор равномерного распределения дополнительного дохода

.

Записать характеристическую функцию взвешенной мажоритарной игры (52;19,25,15,20). Из системы, определяющей С-ядро, исключить зависимые неравенства. Существует ли С-ядро у данной игры? Если существует, то определить один из дележей С-ядра.

2.2.2 Условия существования ядра

Анализ каждой экономической ситуации, моделируемой кооперативной игрой, обычно начинается с проверки ее сбалансированности. Проверить сбалансированности игры G=(N,) можно с помощью задачи линейного программирования

f(x) = min, (2.2.2)

, S=\N \ ; (2.2.3)

Пусть - оптимальное решение. С-ядро не пусто тогда и только тогда, когда

f() (N). (2.2.4)

Если условие (2.2.4) выполняется, но не принадлежит С-ядру, то точку С() можно получить по формуле

(2.2.5)

т.е. есть проекция на гиперплоскость .

Пример 2.2.7. Рассмотрим (0,1)-нормальную игру пяти лиц: (N)=1; (1,2)=(4,5)=(2,3,4)=1/2;(S)=1/2 для всех собственных коалиций, включающих {1,2} или {4,5} или {2,3,4}; (S)=0 в остальных случаях. Решив задачу f(x) =++++ min,

+1/2, +1/2, ++1/2, ,

из ограничений которой исключены зависимые неравенства, получаем оптимальное решение =(0,1/2,0,0,1/2) и оптимальное значение f()=1. Условие (2.2.4) выполняется, следовательно, С() . Так как , то С().

Пример 2.2.8. Пусть N={1,…,5}, (N)=1; (1,2)=(4,5)=1/3; (2,3,4)=1/2; (S)=1/3 для собственных коалиций, включающих {1,2} или {4,5}; (S)=1/2 для собственных коалиций, включающих {2,3,4}; (S)=0 в остальных случаях. Решив задачу линейного программирования

f(x) =++++ min,

+1/3, +1/3, ++1/2, ,

получаем =(0,1/3,0,1/6,1/6), f()=2/3.

Условие (2.2.4) выполняется, т.е. С(), но С(). Используя (2.2.5), вычисляем =(0,1/2,0,1/4,1/4)С().

Необходимое и достаточное условие (2.2.4) существования С-ядра включает оптимальное значение задачи линейного программирования (2.2.2)-(2.2.3), что затрудняет его использование для аналитического описания множества сбалансированных игр. Запишем задачу, двойственную к (2.2.2)-(2.2.3)

g() = max, =, 0,

где (S) - двойственная переменная, соответствующая коалиции S; =(,…, - характеристический вектор коалиции S

Допустимая область двойственной задачи полностью определяется количеством игроков, т.е. уже не зависит от характеристической функции и является выпуклым многогранником. Обозначим его через , а множество вершин - через . Задача (2.2.2)-(2.2.3) разрешима, поэтому

f()=g(*)=,

следовательно, C-ядро существует тогда и только тогда, когда

(N),

что равносильно

(N), . (2.2.6)

Рассмотрим игру трех лиц. Задача (2.2.2)-(2.2.3) имеет вид

f(x) =++ min,

(1)
(2)
(1),
+ (1,2)
+ (1,3)
+ (2,3)

Запишем двойственную задачу

g()=(1)(1)+(2)(2)+(3)(3)+(1,2)(1,2)+(1,3)(1,3)+(2,3)(2,3) max;

(1) + (1,2) + (1,3) = 1,

(2) + (1,2) + (2,3) = 1,

(3) + (1,3) + (2,3) = 1,

0,

Многогранника имеет пять вершин

=(1,1,1,0,0,0), =(1,0,0,0,0,1), =(0,1,0,0,1,0), =(0,0,1,1,0,0), =(0,0,0,1/2,1/2,1/2),

где , .

Из (2.2.6) получаем необходимое и достаточное условие сбалансированности игры трех лиц

(1) + (2) + (3) (1,2,3),

(1) + (2,3) (1,2,3),

(2) + (1,3) (1,2,3),

(3) + (1,2) (1,2,3),

(1,2) + (1,3) + (2,3) 2(1,2,3).

Для супераддитивной характеристической функции первые четыре неравенства всегда выполняются, следовательно, супераддититвная игра трех лиц сбалансирована тогда и только тогда, когда

(1,2) + (1,3) + (2,3) 2(1,2,3).

Пример 2.2.9. Игра трех лиц (i)=0, iN; (1,2)=(1,3)=2, (2,3)=(1,2,3)=3 супераддитивна, но не сбалансирована.

Пример 2.2.10. Игра трех лиц: (1)=(2)=2, (3)=3, (1,2)=3, (1,3)=(2,3)=4, (1,2,3)=5 не супераддитивна, но сбалансирована.

Пример 2.2.11. Игра трех лиц: (1)=(2)=2, (3)=3, (1,2)=3, (1,3)=(2,3)=4, (1,2,3)=5 не супераддитивна и не сбалансирована.

Пример 2.2.12 ("Озеро" [16, с.320]). Вокруг озера расположено n предприятий. Обработка стоков перед их сбросом в озеро стоит каждому предприятию В (денежных единиц), а очистка воды для собственных нужд стоит А, где - число предприятий, не обрабатывающих свои отходы. Считая, что А <В < nА, s =S, получаем

В этой игре нужно узнать, смогут ли предприятии договориться об обработке отходов. Положим n=3, А=10, В=25. Тогда (1)=(2)=(3)=30, (1,2)=(1,3)+(2,3)=60, (1,2,3)= 75. С-ядро задается системой

30, 30, 30, + 60,

+ 60, + 60, ++= 75,

множеством решений которой является треугольник (рис. 2.2.1) с вершинами =(30, 30, 15), =(30, 15, 30), =(15, 30, 30). Центром С-ядра является точка (25,25,25) равномерного распределения величины (1,2,3)=75.

Рис. 2.2.1. Графическая иллюстрация С-ядра (пример 2.2.12).

Для некоторых частных классов игр получены более простые, чем (2.2.6) условия существования С-ядра.

Игра называется игрой с постоянной суммой, если

(S) + (N \S)=(N), S N.

Все несущественные игры являются играми с постоянной суммой, т.к.

(S)+(N\S)= +==(N) , но не наоборот.

Теорема 2.2.2. Если - существенная игра с постоянной суммой, то C()=.

Доказательство. Если

xC(), то (S), SN, =(N).

Пусть существует такая коалиция S, что >(S), тогда <(N)-(S)=(N\S), что противоречит предположению xC(). Если =(S) для всех коалиций SN, то игра не существенна, что тоже противоречит предположениям.

Игра называется простой, если (S){0,1}, SN, и (N)=1. Коалиция S называется выигрывающей, если (S)=1, в противном случае S называется проигрывающей коалицией. Простую игру можно задать в виде пары (N,W), где W - множество выигрывающих коалиций. Выигрывающая коалиция S называется минимальной выигрывающей коалицией, если любая ее собственная подкоалиция проигрывает, т.е. (T)=0 для T S. Супераддитивную простую игру можно задать в форме (N, ), где - множество минимальных выигрывающих коалиций.

Игрок i простой игры, в которой (S)=0, если iS, называется вето игроком.

Теорема 2.2.3. Простая игра сбалансирована тогда и только тогда, когда у нее есть хотя бы один вето игрок, то есть .

Доказать эту теорему предлагается читателю (упражнение 2.2.2.1)

Пример 2.2.9. Простая игра четырех лиц с множеством выигрывающих коалиций W={{12345},{124},{12},{13},{14}} сбалансирована, так как ={1}.

Игра называется симметричной, если значение (S) зависит только от мощности s=S коалиции S, т.е. коалиции с одинаковым числом игроков имеют одинаковый выигрыш. Характеристическая функция симметричной игры имеет вид (S)= f(s), S N.

Теорема 2.2.4. Симметричная игра сбалансирована тогда и только тогда

(S)/s=(N)/n, S N. (2.2.7)

Доказательство. Пусть выполняется (2.2.7). Для вектора

получаем (S), S N, и =(N),

следовательно, , т.е. C().

Обратно, пусть C(), тогда выполняются условия

(N), . (2.2.8)

Рассмотрим квадратную булеву матрицу порядка n, каждая строка и каждый столбец которой содержит s (1? s? n -1) единиц. Столбцы матрицы являются характеристическими векторами некоторых коалиций ,…,. Вектор =((),…,(), 0,…,0)=(1/ s,…,1/ s, 0,…,0) принадлежит , тогда из (2.2.8) получаем (N), то есть (N). Все коалиции имеют одинаковую мощность, поэтому ()=…=()=(S). Получили, что при непустом С-ядре всегда выполняется (2.2.7).

Пример 2.2.10. Для симметричной игры четырех лиц

условие (2.2.7) не выполняется, т.е. C()=, а для следующей игры

условие (2.2.7) справедливее, т.е. C().

Упражнения.

2.2.2.1. Доказать теорему 2.2.3.

2.2.2.2. Существует ли С-ядро у взвешенной мажоритарной игры

(10; 5, 3, 3, 1, 1)?

2.2.2.3. Дана игра трех лиц

(1)=1(2)=2(3)=3(1,2)=3(1,3)=5(2,3)=7(1,2,3)=9.

Используя необходимое и достаточное условие существования С-ядра, определить максимальное число д, при котором игра

, =, S?N,

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

2.2.2.4. Записать характеристическую функцию игры "Озеро" (три предприятия, А =14, В=25). Перейти к стратегически эквивалентной игре с неотрицательной характеристической функцией. Существует ли С-ядро у данной игры?

2.3 Равновесие по Нейману-Моргенштерну

Если С-ядро игры существует, то в качестве исхода игры обычно выбирают дележ, принадлежащий С-ядру. Возможная пустота С-ядра является главным недостатком этого понятия. Указанного недостатка практически не имеет понятие решения, предложенное фон Нейманом и Моргенштерном [1].

Множество B()D() называется решением Неймана-Моргенштерна (NM-решением, решением), если

B()=D()\dom B(),

т. е. B() удовлетворяет следующим двум условиям:

1) для любых , B() выполняется () и (),. (ни один из дележей множества B() не является предпочтительней другого - внутренняя устойчивость);

2) для любого дележа B() найдется такой дележ B(), что (внешняя устойчивость).

NM-решение может не существовать, но в крайне редких случаях. Первая игра, не имеющая NM-решения, была получена для n=10. NM-решение не является единственным. В отличие от С-ядра, являющимся выпуклым многогранником, NM-решением может быть невыпуклым и даже не связным.

Из определения вытекают следующие свойства NM-решения:

- любое NM-решение не может быть подмножеством другого NM-решения;

- в сбалансированной игре NM-решение есть замкнутое множество пространства , содержащее С-ядро;

- если С-ядро является NM-решением, то NM-решение единственно.

Пример 2.3.1.. Рассмотрим игру трех лиц, в которой каждый из игроков обязан заплатить двум другим игрокам по единице, если они образуют коалицию. Если интерпретировать как максимальное количество денег, которое может получить коалиция S, характеристическая функция будет иметь вид

После (0-1)-нормализации получаем, Эта симметричная простая игра эквивалентна взвешенной мажоритарной игре (2; 1, 1, 1), где выигрывают все коалиции, мощность которых больше 1. Игра не сбалансирована, так как . Покажем, что множество

={=(1/2,1/2, 0), =(1/2,0,1/2), =(0,1/2,1/2)}

является NM-решением.

Внутренняя устойчивость U() очевидна. Рассмотрим дележ x=(,,), тогда , , 30, ++=1. Следовательно, не более двух компонент вектора x могут не меньше 1/2. Если две компоненты x равны 1/2, то третья равна 0, то есть x. В противном случае x имеет не более одной компоненты, не меньшей чем 1/2. Тогда две остальные компоненты меньше 1/2 и x доминируется одним из дележей из . Возвращаясь к исходной игре, из формулы

, i=1,2,3;

получаем ее NM-решение ={(1, 1, -2), (1, -2, 1), (-2, 1, 1)}. Аналогично можно доказать, что для любого [0,1] множества

: 0 1- },

: 0 1- } и т.д.

тоже являются NM-решениями (0-1)-нормальной формы рассматриваемой игры.

Для частных классов игр получен явный вид NM-решений.

Теорема 2.3.1. Пусть - простая игра, - множество таких дележей x, что =0 для всех iS. Тогда есть NM-решение.

Доказательство теоремы аналогично доказательству, проведенному в примере 2.3.1.

Теорема 2.3.2. Множество

где ,

,,

является NM-решением игры трех лиц.

Доказательство можно найти в [32, с.31-32].

Пример 2.3.2. Дана не сбалансированная игра трех лиц:

(i)=0, i=1,2,3; (1,2)=(2,3)=2, (1,3)=3, (N)=3.

Множество определяется системой:

=1; + = 2; , 0 > =1; 0 2

(отрезок АВ, рис. 2.3.1.(a)). Множество определяется системой:

=1; 2; + = 3; 0 > =0; =1 (точка С, рис.2.3.1.(a)).

NM-решение есть объединение отрезка АВ и точки С (рис.2.3.1.(a)).

Рис 2.3.1. Графическая иллюстрация NM-решения (пример 2.3.2)

Пример 2.3.3. Дана сбалансированная игра трех лиц: (i)=0, i=1,2,3; (1,2)=(2,3)=2, (1,3)=3, (N)=4. Ее С-ядро определяется системой

+ 2, + 3, + 2, + + = 4 , , 0,

0 2, 2 + 4, 0 1,

(треугольник DEF, рис.2,3.1.(b)).

Множество определяется системой:

=2; + = 2; , 0 > =2; 0 2

(отрезок GE, рис.2,3.1.(c)).

Множество определяется системой:

=1; 2; + = 4; 0 > 01; =1

(отрезок LF, рис. 2.3.1.(c)).

Упражнения

2.3.1. Дана игра трех лиц

(1)=(2)=(3)=0, (1,2)=4, (1,3)=6, (2,3)=5, (1,2,3)=12.

Определить целое число д, при котором игра , имеет С-ядро, а игра , не имеет С-ядра.

Вычислить NM-решение игры . Выполнить графическую иллюстрацию.

Вычислить NM-решение игры . Выполнить графическую иллюстрацию.

2.3.2. Является ли дележ x=(5, 3, 1) NM-решением следующей игры трех лиц: =5, =3, =1, =8, =6, =4, =9?

2.4 Операторы значения

2.4.1 Утилитарный подход

В идеальном случае анализ кооперативной игры должен был бы приводить к выбору единственного дележа, который и следовало бы принять за решение. Правило, ставящее в соответствие каждой кооперативной игре единственное распределение =(,…,) величины (N), называется оператором значения, а само распределение - значением игры. Одним из популярных значений, показавших свою применимость к широкому классу экономических моделей, является: цена Шепли (значение Шепли, вектор Шепли). Цена Шепли приписывает каждому игроку выигрыш, равный его среднему вкладу во все коалиции и вычисляется по формуле

, , где .

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

Для игры трех лиц цена Шепли имеет вид

,

,

.

Для простой игры лиц формула для цены Шепли упрощается

=, ,

где - множество таких проигрывающих коалиций S, не содержащих игрока , что коалиция S {} является выигрывающей.

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

={{2},{3},{2,3},{2,4},{3,4}}, ={{1},{1,4},{3,4}}, ={{1},{1,4},{2,4}}., ={2,3}.

Вычислив = ,

получаем .

Цена Шепли не совпадает с "вектором голосования" , в котором выигрыш игрока пропорционален его доле акций. В отношении цены Шепли, игроки 2 и 3 обладают одинаковой силой (несмотря на разное количество акций, они имеют одинаковые возможности для образования коалиций).

Сила игрока 1 больше доли его акций, а сила игрока 4, наоборот, меньше доли акций.

Предположим теперь, что игрок 3 приобрел еще 10 акций, т.е. рассмотрим игру (55; 40, 30, 30, 10). В этом случае

W={{1,2}, {1,3}, {2,3}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}, =, ={{2},{3},{2,4},{3,4}}, ={{1},{3},{1,4},{2,4}}, ={{1},{2},{1,4},{2,4}}., =, .

Цена Шепли также не совпадает с "вектором голосования" и показывает, что дополнительные акции игрока 3 не дают ему преимуществ, а акции игрока 4 обесцениваются (он не может войти ни в одну коалицию, т.е. становится "болваном").

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

Аксиома 1 (независимость). Для любого игрока , где ((1),…,(n)) - перестановка N , то есть выигрыш игрока не зависит от его номера.

Аксиома 2 (аксиома болвана). Если (S(i})=(S) для любого SN, то .

Аксиома 3 (эффективность). =(N).

Аксиома 4 (линейность).

Пусть ,, - векторы Шепли для игр ,, и =+, тогда =+.

Теорема 2.4.1. Существует единственный вектор распределения величины (N), удовлетворяющий аксиомам 1-4. Это вектор Шепли.

Доказательство теоремы можно найти в [15].

Цена Шепли является коалиционно монотонной, т.е. если прибыль (S) некоторой коалиции S увеличить, а прибыли всех остальных коалиций оставить без изменения, то цена каждого игрока коалиции S не уменьшиться. В симметричной игре цена Шепли делит (N) на равных частей =((N)/n,…,(N)/n). Цена Шепли может не принадлежать непустому С-ядру.

Пример 2.4.2. ("Рынок перчаток" [17]). Два игрока (1 и 2) имеют по одной правой перчатке, а два остальных игрока (3 и 4) имеют по одной левой перчатке. Рыночная цена одной перчатки равна нулю, а цена одной пары (с одной правой и одной левой) равна единице. Эта ситуация описывается игрой четырех лиц:

(1,3)= (1,4)=(2,3)= (2,4)=(1,2,3)= (1,2,4)=(1,3,4)=(2,3,4)=1,

(1,2,3,4)=2, (S) =0 для остальных S.

С-ядро, определенное системой:

+1, +1, +1, +1, +++=2, ,

является отрезком с концами =(1,1,0,0), =(0,0,1,1). Цена Шепли =(1/2,1/2,1/2,1/2) совпадает с равномерным распределением прибыли.

Предположим теперь, что игрок 1 имеет две правые перчатки, в то время как остальные игроки располагают прежними запасами. Тогда

(1,3)=(1,4)=(2,3)=(2,4)=(1,2,3)=(1,2,4)=(2,3,4)=1, (1,3,4)=(1,2,3,4)=2, (S) =0 для остальных S. С

собственная прибыль коалиции {1,3,4} увеличилась на единицу.

С-ядро игры задается системой

+1, +1, +1, +1,, ++2, +++=2, .

Оно состоит из единственного дележа = (0,0,1,1), при котором всю прибыль делят владельцы левых перчаток. Цена Шепли =(7/12, 3/12, 7/12, 7/12) увеличивает долю первого, третьего и четвертого игроков, чьи коалиционные возможности возросли, уменьшая долю второго игрока. В данном случае цена Шепли не принадлежит С-ядру.

Упражнения

2.3.1.1. Вычислить цену Шепли взвешенной мажоритарной игры

(10; 6, 5, 3, 3).

Сравнить цену Шепли с "вектором голосования". Какие игроки имеют силу (относительно цены Шепли) превышающую их долю голосов? Принадлежит ли цена Шепли С-ядру

2.3.1.2. Записать характеристическую функцию игры "Озеро" (три предприятия, А =12, В=27). Вычислить цену Шепли. Дать содержательную интерпретацию полученного дележа.

2.4.2 Эгалитарный подход

Эгалитарный принцип справедливости, приводит к понятию N-ядра (nucleolus) . Эгалитарный принцип отражает стремление людей к равенству и приводит выравниванию выигрышей всех коалиций. В отличие от цены Шепли, N-ядро всегда принадлежит непустому С-ядру. Оно занимает центральное место внутри С-ядра. Для определения N -ядра вводится понятие эксцесса

,

который является "мерой неудовлетворенности" коалиции S дележом . Положительный (отрицательный) эксцесс есть дополнительная прибыль (убыток) коалиции S по сравнению с ее собственной возможностью . Для каждой коалиции S желательно, чтобы значение эксцесса было как можно больше.

Каждому дележу ставиться в соответствие вектор эксцессов

=,

компонентами которого являются упорядоченные по неубыванию эксцессы собственных коалиций

,

; , .

Дележ принадлежит С-ядру тогда и только тогда, когда его вектор эксцессов неотрицателен.

Пример 2.4.3. Вычислим, например, вектор эксцессов для цены Шепли =(7/12, 3/12, 7/12, 7/12) игры "Рынок перчаток" (пример 2.4.2.)

(1,3)=(1,4)=(2,3)=(2,4)=(1,2,3)=(1,2,4)=(2,3,4)=1, (1,3,4)=(1,2,3,4)=2.

Определяем вначале эксцессы собственных коалиций

===7/12, =3/12, =10/12, ==2/12, == 2/12,

=14/12, ==5/12,

= 3/12, =5/12.

Упорядочивая эти величины по неубыванию получаем

=(,,,,,,,,,,,,,)=(3/12, 2/12, 2/12, 2/12, 2/12, 3/12, 5 /12, 5/12, 5/12, 7/12, 7/12, 7/12, 10/12, 14/12).

Вектор эксцессов единственной точки =(0, 0, 1, 1) С-ядра этой же игры имеет вид

(

)=(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2).

На множестве векторов эксцессов дележей игры G вводится лексикографическое упорядочение . Говорят, что вектор предшествует (или предпочтительнее в смысле лексикографического порядка)

,

если существует такая коалиция , что

=, , < .

Так, например, для вычисленных выше векторов эксцессов и имеем .

Существует единственный дележ , вектор эксцессов которого предпочтительнее всех остальных векторов из

=. (2.4.1)

Это и есть N-ядро.

Как и цена Шепли, N-ядро удовлетворяет аксиомам анонимности и болвана, но не является коалиционно монотонным. Поэтому возможен случай, когда увеличение величины (N) при сохранении прибылей (S) всех остальных коалиций S N, приводит к уменьшению доли прибыли некоторых игроков. Это очень непривлекательное свойство, т.к. если какие-либо игроки страдают в результате улучшений, то они могут отказаться от участия и тем самым сделать невозможным улучшение ситуации. Для 5 не существует такого значения кооперативной игры, которое одновременно принадлежит С-ядру и является коалиционно монотонным (теорема Янга [15]).

При определении N-ядра рассматриваются эксцессы коалиций, но не учитываются размеры коалиций. Поэтому единица прибыли для одного игрока расценивается так же, как и единица прибыли для его дополнения - коалиции из (n 1) игрока. Это может быть воспринято участниками игры как несправедливость.

В некоторых играх, возможно, более предпочтительным окажется понятие пропорционального N-ядра, которое определяется через средние (в расчете на одного члена коалиции) эксцессы

,

и обладает теми же свойствами, что и N-ядро. Если желательно увеличить прибыль больших коалиций, то можно рассматривать взвешенное N-ядро, определенное через взвешенные эксцессы

, .

Вообще эксцесс коалиции S можно представить в виде

,

где >0 - нормирующий множитель. Соответствующее N-ядро называется обобщенным N-ядром. Обобщенное N-ядро также не является коалиционно монотонным.

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

Из соотношения (2.4.1) следует, что для нахождения N-ядра нужно в первую очередь максимизировать минимальную коалиционную прибыль

. (2.4.2)

После введения дополнительной переменной задача (2.4.2) сводится к задаче линейного программирования с (n+1) переменной и () ограничениями

, =; , . (2.4.3)

Оптимальное значение этой задачи равно величине первой компоненты вектора эксцессов N-ядра

. (2.4.4)

Если задача (2.4.3) имеет единственное оптимальное решение (,), то оно является N-ядром. В противном случае, из оптимального множества нужно выбрать те дележи, которые максимизируют вторую по минимальности коалиционную прибыль. Для этого необходимо определить, на каких коалициях достигается минимум в соотношении (2.4.4)

Рассмотрим двойственную к (2.4.3) задачу

 (2.4.5)

; (2.4.6)

; , ; (2.4.7)

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

(2..4.8)

Если она имеет единственное решение (, ), то это N-ядро. В противном случае находим оптимальное решение двойственной к (2.4.8) задачи, имеющей аналогичную (2.4.5)-(2.4.7) структуру и решаем новую задачу

,

=; , ;

, ; , ;

где

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

, , .

Пример 2.4.4. Дана игра трех лиц:

(1)=1, (2)=(3)=0, (1,2)=5, (1,3)=1, (2,3)=0, (1,2,3)=8.

Решаем соответствующую (2.4.3) задачу ЛП, исключив из ее ограничений зависимые неравенства (таблица 2.4.1, столбец 1). Затем решаем двойственную задачу (таблица 1, столбец 2) и находим ={{3},{1,2}}. Результаты решения этой пары двойственных задач ЛП определяют значения первых двух компонент вектора эксцессов N-ядра

e()=(e(,{3}, e(,{1,2}),…)=(1.5, 1.5,…),

то есть дополнительная прибыль коалиций {3} и {1,2} равна оптимальному значению =1.5 прямой задачи, а прибыли остальных коалиций будет больше, чем .

Таблица 2.4.1.

Задача 1	Двойственная задача
- + - 1	0
- + 0	0
- + 0	0
- - + -5	0
+ + = 8	-
0	- -+ 0
0	- -+ 0
0	- + 0
-	+++ =1
Оптимальное решение: =(2.5, 4, 1.5), =1.5	Оптимальное решение: ==0, ===0.5.

Для вычисления значения второй по минимальности компоненты вектора эксцессов N-ядра решаем новую пары двойственных задач (таблица 2.4.2). Получаем: =2.75 - оптимальное значение прямой задачи: ={{1},{2}} - множество коалиций, дополнительная прибыль которых равна ;

e()=(e(,{3}, e(,{1,2}, e(,{1}, e(,{2}),…)=(1.5, 1.5, 2.75, 2.75,…) -

значения первых четырех компонент вектора эксцессов N-ядра.

Система ограничений новой задачи ЛП

=3.75, =2.75, =1.5, +=6.5, ++=8,

содержит три линейно независимые уравнения, то есть имеет единственное решение =(3.75,2.75,1.5). Полученный способ распределения общей полезности (I) между игроками гарантирует каждой коалиции SI положительный дополнительный доход:

e(,{3})=e(,{1,2})=1.5, e(,{1})=e(,{2})=2.75, e(,{1,3})= e(,{2,3})=4.25.

Таблица 2.4.2.

Задача 2	Двойственная задача
- + - 1	0
- + 0	0
=1.5	-
+ = 6.5	-
+ + = 8	-
0	- ++ 0
0	- ++ 0
0	+ 0
-	+ =1
Оптимальное решение: =(3.75,2.75,1.5), =2.75	Оптимальное решение: ==0.5, ==0, =0.5.

Рис. 2.4.1. Графическая иллюстрация к примеру 2.4.4.

Упражнения

2.4.2.1. Вычислить N-ядро выпуклой игры

===2, ===5, =9.

2.4.2.2. Вычислить N-ядро игры, приведенной в таблице 15, используя задачи линейного программирования. Вычислить вектор эксцессов N-ядра. Существует ли С-ядро у данной игры? Вычислить пропорциональное N-ядро. Вычислить взвешенное N-ядро.

Литература

1. Фон Нейман Дж. Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

2. Таха Х. Введение в исследование операций. Том 2. М.: Мир. 1985.

3. Исследование операций. Методологические основы и математические методы (под редакцией Дж. Моулера и С. Элмаграби). Том 1. М.: Мир. 1988.

4. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. М.: Мир. 1977.

5. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир. 1984.

6. Шрейдер ЮА. Равенство, сходство, порядок. М.: Наука. 1971.

7. Фишберн П. Теория полезности для принятия решений. М.: Наука. 1978.

8. Волошин Г.Я. Методы оптимизации в экономике. М.: Дело и сервис. 2004.

9. Сапир Ж. Новые подходы теории индивидуальных предпочтений и ее следствия // Экономический журнал ВШЭ. № 3. 2005. С. 325-360.

10. Expected Utility Hypotheses and the Allais Paradox / M. Allais, O. Hagen (ads.). Dordrecht: Reidel, 1979.

11. Шапкин А.С. Экономические и финансовые риски: оценка, управление, портфель инвестиций. М.: Дашков и Ко, 2003.

12. Ларичев О.И. Теория и методы принятия решений. М.: Логос. 2000.

13. Kaneko M., Wooders M.H. Utility Theory in Cooperative Games. Handbook of Utility Theory. P. Hammond and C. Seidel eds., Klauwer Academic Press. 1997

14. Мулен Э. Теория игр с примерами из математической экономики. М.: Мир. 1985.

15. Мулен Э. Кооперативное принятие решений: аксиомы и модели. М.: Мир. 1991.

16. Робертс Ф.С. Дискретные математические модели с приложениями к социологическим, биологическим и экологическим задачам. М., 1986.

17. Розенмюллер И. Кооперативные игры и рынки. М.: Мир. 1974

18. Губко М.В. Кооперативная модель формирования торговой сети // Труды МНПК Современные сложные системы управления (СССУ/НТСS 2004). Тверь: ТГТУ. 2004.

19. Жак С.В., Зинченко А.Б. Согласование внутренних цен предприятий как кооперативная игра с побочными платежами // Изв. вузов. Сев.-Кавк. регион. Естеств. науки, №4, 2001.

20. Ball M.A. Outline of the superplayer theory of coalitions. In Proceedings ICM2002GTA. 2002. Р. 35-40.

21. Branzei R., Dimitrov D., Tijs S. Egalitarianism in convex fuzzy games // Working Papers 337, University of Bielefeld, Institute of Mathematical Economics, 2002.

22. Bom P.E.M., Megen F.G.C., Tijs S.H. A perfectness concept fjr multicreteria games // Mathematical Methods of Operations Research. 49(3). 1999. P.401-412.

23. Fernandez F., Hinojosa M, Puerto J. Multi - criteria minimum cost spanning tree games // Eur. J. Oper. Res, 2004, v.158, n.2. P.399-408.

24. Hwang Y.A., Sudholter P. An Axiomatization of the Core on the Universal Domain and other Natural Domains // International Journal of Game Theory. 2001. P.597-623.

25. Sun H. Contributions to set game theory. Twente University Press, China. 2003.

26. Tijs S.H., Meca A., Lopez M.A. Benefit shaning in holding situations // European Journal of Operational Research. 162(1). 2005. P. 251-269.

27. Tijs S.H., Gelekom J.R.G., Potters J.A.M., Reijnierse J.H., Engel M.C/ Characterization of the Owen set of linear production processes // Games and Economic Behavior. 32(1). 2000. P.139-156.

28. Петросян Л.П., Зенкевич Н.А., Семина Е.А.Теория игр (учебное пособие для университетов). СПб . 1998.

29. Печерский С.Л., Беляева А.А. Теория игр для экономистов. Вводный курс. Учебное пособие. СПб.: Европейский университет в СПб. 2001.

30. Данилов В.И. Лекции по теории игр. М.: Российская экономическая школа. 2002.

31. Васин А.А., Морозов В.В. Теория игр и модели математической экономики. М.: Макс-Пресс. 2005.

32. Кукушкин Н.С., Морозов В.В. Теория неантагонистических игр. М.: Наука. 1984

33. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. 1985.

34. Дюбин Г.Н., Суздаль В.С. Введение в прикладную теорию игр.1981

35. Оуэн Г. Теория игр. М.: Мир. 1971.

36. Owen G. Game Theory. New York. Academic Press. 1982.

37. Петросян Л.П., Зенкевич Н.А., Семина Е.А.Теория игр (учебное пособие для университетов). 1998.

38. Bhattacharya A. On the equal division core // Social Choice and Welfare. 2. 2004. Р.391-399.

Размещено на Allbest.ru