Санкт-Петербургский государственный университет
Кафедра математической теории игр и статистических решений
Башлаева Дарья Владимировна
Выпускная квалификационная работа бакалавра
Устойчивые объединения, основанные на
коллективной рациональности
Направление 010400
Прикладная математика и информатика
Научный руководитель,
кандидат физ.-мат. наук,
доцент
Седаков А.А.
Санкт-Петербург
2016
Содержание
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 1. Игра с главным игроком и координатором . . . . . . . . . .
1.1. Коалиционная игра . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Значение вектора Майерсона . . . . . . . . . . . . . . . . . . .
1.3. Значение ES - вектора . . . . . . . . . . . . . . . . . . . . . .
Глава 2. C - устойчивость коалиционных структур . . . . . . . . . .
2.1. C - yстойчивость коалиционных структур относительно вектора Майерсона . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. C - устойчивость коалиционных структур относительно ES вектора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Численный пример . . . . . . . . . . . . . . . . . . . . . . . .
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
3
5
5
7
9
11
11
21
29
31
32
Введение
Во многих экономических, политических и социальных ситуациях
люди осуществляют деятельность в группах (т. е. в коалициях), а не в одиночку. Примерами могут послужить семьи, политические партии, профсоюзы, компании, представленные на рынке. Многие практические ситуации служат причиной возникновения кооперативных игр в форме характеристической функции, когда функция является супераддитивной, монотонной, т. е. игрокам выгодно образовывать максимальную коалицию для
увеличения собственного выигрыша. Но это не всегда так, при некоторых
ограничениях на характеристическую функцию, максимальная коалиция
может быть не создана. Этот факт мотивирует изучить модель игры с ограниченной кооперацией: игры с коалиционным разбиением и игры с коммуникационными ограничениями. В литературе вопрос игр с коалиционной
структурой был изучен в работах [4] и [12], где были описаны кооперативные решения (значение Аумана-Дрезе и значение Оуэна соответственно),
опирающиеся на вектор Шепли [14]. Игры с коммуникационной структурой
были исследованы в работе [11], где было представлено решение – вектор
Майерсона, также основанный на решении, предложенным Шепли.
В качестве базовой модели за основу взята модель, разработанная
в [1]. В данной работе рассматривается игра с двумя типами ограничений на кооперацию: игра с коалиционной структурой и игра, заданная при
помощи ненаправленного коммуникационного графа. В данной игре существует три типа игроков, распределенных по уровням — это главный игрок
(единственный игрок первого уровня), координатор (единственный игрок
второго уровня), ведомые игроки (игроки третьего уровня).
В математической теории кооперативных игр существует несколько
принципов оптимального (справедливого) распределения выигрыша. При
построении данных принципов оптимальности предполагается, что коалиции сформированы, следовательно, для каждой возможной коалиционной
структуры существует свое распределение выигрыша. Центральным вопросом в формировании коалиций является устойчивость коалиционной
структуры: если у игроков есть возможность увеличения выигрыша путем перехода в другую коалицию или путем слияния коалиций, или каким
либо другим способом изменения коалиционной структуры, игроки ею воспользуются, и такая структура будет не устойчивой. Возникает вопрос,
какую структуру считать устойчивой? В литературе используется широ3
кий спектр понятий, например, c - ядро, строгое ядро, равновесие Нэша.
В работах [6], [7], [8] изучается вопрос получения достаточных условий,
гарантирующих существование устойчивых решений, относительно индивидуальной рациональности (Нэш устойчивые структуры, т. е. рассматривается вопрос устойчивости каждого игрока в отдельности) или коллективной рациональности (c - устойчивые структуры, т. e. рассматривается
вопрос устойчивости коалиции). В работах [2], [10], [13] для определенных
моделей исследуется вопрос устойчивости коалиционной структуры относительно выбранного принципа оптимальности. В работе [5] доказано, что
поиск c - устойчивых решений является N P полной задачей.
Целью настоящей работы является исследование устойчивости коалиционных структур для выбранной модели, где в качестве распределения
выигрыша используются вектор Майерсона и ES - вектор [9], а для того,
чтобы определить, какая коалиционная структура является устойчивой,
используется принцип, основанный на коллективной рациональности.
Рассматриваемая тема является актуальной, т. к. охватывает широкий спектр практических ситуаций, а также является предметом исследований многих научных деятелей.
Работа имеет следующую структуру. В первой главе приводится игра с тремя типами участников, как кооперативная игра c двумя типами
ограничений: игра с коалиционной структурой и игра коммуникационными ограничениями, приводятся все возможные коалиционные структуры,
а также решения относительно вектора Майерсона и ES - вектора для
каждого возможного типа структуры. Во второй главе изучаются вопрос
коллективной устойчивости коалиционных структур для игры с главным
игроком и координатором, приводится численный пример. В конце работы
располагается заключение и список литературы, которая была использована при написании данной работы.
4
Глава 1. Игра с главным игроком и координатором
1.1. Коалиционная игра
Пусть N — конечное множество игроков. |N | = n > 2 — количество
игроков.
Определение 1.1. Кооперативной игрой в форме характеристической функции называется игра, заданная (N, v), где v — характеристическая функция, сопоставляющая каждому подмножеству S ⊆ N , называемому коалицией, некоторое значение v(S) ∈ R, выражающее заслугу (цену)
коалиции S. При этом v(∅) = 0.
Рассмотрим модель кооперативной игры с трансферабельной полезностью
(т. е. коалиция S может произвольно разделить выигрыш v(S) между ее
членами) с ограниченной кооперацией.
Коммуникация между игроками ограничена графом g (т. е. если отсутствует ребро между игроками, они не могут взаимодействовать напрямую)
(см. рис. 1).
Рис. 1: Граф g
Будем говорить, что первый игрок это главный игрок (или игрок первого уровня), второй игрок это координатор (или игрок второго уровня).
Других игроков из множества N \ {1, 2} будем называть ведомыми (или
игроками третьего уровня). Главный игрок может взаимодействовать напрямую только с координатором, координатор с главным игроком и игроками третьего уровня, а игроки третьего уровня только с координатором.
Игроки друг от друга отличаются параметром, определяющим результативность их работы. Будем считать, что коэффициент эффективности главного игрока равен — β, координатора — σ, игроков третьего уровня — α.
5
В рассматриваемой модели предполагается, что коэффициент эффективности главного игрока не меньше коэффициента эффективности координатора, а коэффициент эффективности координатора не меньше коэффициента
эффективности чем у ведомых игроков, также допускается равенство всех
или двух коэффициентов, т. е. α ≤ σ ≤ β.
Характеристическая функция, для рассматриваемой модели выглядит следующим образом [1]:
если 1 ∈ S и 2 ∈
/ S,
β
v(S) =
(1.1)
0
если 1 ∈
/ S,
α(s − 2) + σ + β если 1 ∈ S и 2 ∈ S.
s−1
2
Определение 1.2. Характеристическая функция называется суперааддитивной если для любых непересекающихся коалиций S1 , S2 верно неравенство v(S1 ∪ S2 ) ≥ v(S1 ) + v(S2 ).
Характеристическая функция v(S) определенная в (1.1) считается супераддитивной, когда выполняются условия [1]:
max{α; β − 2α} ≤ σ ≤ min{2α; β}
(1.2)
Характеристическая функция, определенная в (1.1), при допустимых параметрах модели (0 ≤ α ≤ σ ≤ β) не всегда является супераддитивной,
следовательно, игроки для собственной выгоды могут разбиваться на коалиции, не всегда совпадающие с максимальной. Поэтому введем определение коалиционной структуры.
Определение 1.3. Коалиционная структура π - это разбиение
{B1 , . . . ,Bm } множества игроков N т. е.
• B1 ∪ . . . ∪ Bm = N
• Bi ∩ Bj = ∅ для всех i, j = 1, . . . ,m , где i 6= j.
Обозначим через (N, v, g, π) кооперативную игру с множеством игроков
N , коалиционной структурой π, характеристической функцией v, которая
определена в (1.1), ненаправленным коммуникационным графом g, заданным на рис. 1.
Рассмотрим все возможные варианты формирования коалиционных
структур в игре с главным игроком и координатором. Первый вариант:
в коалицию объединяются главный игрок и координатор, игроки третьего уровня объединяются произвольным образом. Второй вариант: главный
игрок играет самостоятельно, координатор и ведомые игроки объединяются произвольным образом. Третий вариант: в коалицию объединяются
главный игрок, координатор и произвольное количество ведомых игроков,
6
остальные игроки объединяются произвольным образом. Четвертый вариант отличается от второго тем, что игрок первого уровня играет не один,
а с некоторым количеством ведомых игроков. Пятый вариант: игроки образуют максимальную коалицию. (см. рис. 2).
Рис. 2: Варианты формирования коалиций игроков
Определение 1.4. Вектор xπ = (xπ1 , ... , xπn )∈ Rn называется распределением выигрыша в игре (N, v, g, π) с коалиционной структурой π =
{B1 , . . . , Bm }, если выполняется условие коллективной рациональности
P
π
i∈Bj xi = v(Bj ) для всех Bj ∈ π.
В рассматриваемой игре от вектора распределения выигрыша не требуется выполнение условия индивидуальной рациональности, т. е. xπi ≥ v({i})
для всех i = 1...n.
В игре (N, v, g, π) c коалиционной структурой π = {B1 , . . . ,Bm } в качестве принципов оптимальности (т. е. способов распределения выигрыша)
рассмотрим вектор Майерсона и ES - вектор.
1.2. Значение вектора Майерсона
Компоненты вектора Майерсона φ = (φ1 , ..., φn ) для игры (N, v, g, π)
c характеристической функцией (1.1) можно вычислить по следующему
правилу:
P
(B(i)|−|S|)!(|S|−1)!
φπi =
[v(S) − v(S \ {i})] , i ∈ N
(1.3)
|B(i)|!
S⊆B(i),i∈S
где B(i) ∈ π — коалиция, содержащая игрока i ∈ N .
Ведомые игроки N \ {1, 2} симметричны между собой, поэтому согласно
свойствам вектора Майерсона их выигрыш одинаков.
Запишем распределение выигрыша относительно вектора Майерсона для
всех возможных типов коалиционных структур.
7
Первый тип
Пусть в первой коалиции находятся только главный игрок и координатор.
В остальных коалициях произвольным образом расположены игроки третьего уровня: π = {{1, 2}, B2 , ..., Bm }.
3β
σ
φ1 = 2 + 4 ,
φ2 = σ2 − β4 ,
φ = 0.
i
Второй тип
Пусть главный игрок играет один. Остальные игроки распределены по другим коалициям произвольным образом: π = {{1}, B2 , ..., Bm }.
(
φ1 = β,
φi = 0, если i 6= 1.
Третий тип
Пусть в первой коалиции находятся обязательно главный игрок и координатор, количество ведомых игроков может меняться произвольным образом, но первая коалиция не должна совпадать с максимальной:
π = {B1 , ..., Bm }, 1 ∈ B1 , 2 ∈ B1 , |B1 | > 2, |B1 | =
6 n.
φ1 = α(b13−2) + bσ1 + 3β
4 ,
φ = α(b1 −2) + σ − β ,
2
3
b1
4
α
σ
φi = 3 − b1 (b1 −1)
i ∈ B1 ,
φ =0
j∈
/ B1 .
j
Четвертый тип
В первой коалиции находятся главный игрок и некоторое количество ведомых игроков, остальные игроки объединяются произвольным образом:
π = {B1 , B2 , ..., Bm }, 1 ∈ B1 , |B1 | > 1.
(
φ1 = β,
φi = 0, если i 6= 1.
Пятый тип
Игроки образуют максимальную коалицию: π = {N }.
α(n−2)
3β
σ
φ1 = 3 + n + 4 ,
φ2 = α(n−2)
+ σn − β4 ,
3
φ =α− σ .
i
3
n(n−1)
8
1.3. Значение ES - вектора
Распределение выигрыша относительно ES - вектора ψ = (ψ1 , ..., ψn )
для игры (N, v, g, π) c характеристической функцией (1.1) можно вычислить по следующей формуле:
P
v(B(i))−
ψiπ
= v({v}) +
v({j})
j∈B(i)
|B(i)|
,i∈N
(1.4)
По аналогии с вектором Майерсона приведем распределение выигрышей
относительно ES - вектора для всех возможных вариантов коалиционных
структур.
Первый тип
В первой коалиции находятся только главный игрок и координатор:
π = {{1, 2}, B2 , ..., Bm }.
3β
σ
ψ1 = 2 + 4 ,
ψ2 = σ2 − β4 ,
ψ = 0.
i
Второй тип
Пусть главный игрок играет отдельно. Остальные игроки распределены
произвольным образом: π = {{1}, B2 , ..., Bm }.
(
ψ1 = β,
ψi = 0, если i 6= 1.
Третий тип
Пусть в первой коалиции находятся обязательно главный игрок и координатор, количество ведомых игроков может меняться произвольно, но первая коалиция не совпадает с максимальной: π = {B1 , ..., Bm }, 1 ∈ B1 ,
2 ∈ B1 , |B1 | > 2, |B1 | =
6 n.
ψ1 = α(bb11−2) + b1 (bσ1 −1) + β(2b2b11−1) ,
ψ = α(b1 −2) + σ − β ,
2
b1
b1 (b1 −1)
2b1
α(b
−2)
σ
1
ψi = b1 + b1 (b1 −1) − 2bβ1 ,
i ∈ B1 ,
ψj = 0,
j∈
/ B1 .
Четвертый тип
В первой коалиции находится главный игрок и некоторое количество игроков третьего уровня, другие игроки объединяются произвольным образом:
π = {B1 , B2 , ..., Bm }, 1 ∈ B1 , |B1 | > 1.
9
(
ψ1 = β,
ψi = 0, если i 6= 1.
Пятый тип
Игроки образуют максимальную коалицию π = {N }.
α(n−2)
β(2n−1)
σ
ψ
=
+
+
1
n
n(n−1)
2n ,
β
σ
+ n(n−1)
− 2n
,
ψ2 = α(n−2)
n
α(n−2)
β
ψi =
+ σ − .
n
n(n−1)
10
2n
Глава 2. C - устойчивость коалиционных структур
Во многих практических ситуациях, один человек не может решать за
всех, поэтому является важным рассмотреть устойчивость коалиционных
структур, относительно коллективной рациональности, т. e. решение может
принимать не только один игрок.
Определение 2.1. Будем говорить, что игрок предпочитает одну коалицию B1 другой B2 и обозначать B1 i B2 , если выполняется xπi > xπi 0 ,
B1 ∈ π, B2 ∈ π 0 .
Определение 2.2. Коалиция B ∈ π 0 блокирует коалиционную структуру π, если каждый игрок i ∈ B предпочитает коалицию B в коалиционной структуре π 0 , т. e. B i Sj (i), для всех i ∈ B, Sj (i) ∈ π.
Определение 2.3. Коалиционную структуру π={B1 ,...,Bm } будем
называть c - устойчивой относительно выбранного принципа оптимальности, если не существует блокирующих коалиций для данной структуры.
Рассмотрим все возможные типы коалиционных структур, выведем
условия при которых данные структуры будут c - устойчивыми относительно выбранного принципа оптимальности, а именно вектора Майерсона
или ES - вектора. Для того, чтобы найти все возможные блокирующие
коалиции для коалиционной структуры π, используем следующий подход:
рассматриваем все коалиции, которые отличаются составом игроков от коалиций, входящих в коалиционную структуру π. Если выигрыш всех игроков в возможной блокирующей коалиции совпадает с выигрышем этих
игроков в коалиционной структуре π, то такую коалицию исключаем из
рассмотрения.
2.1. C - yстойчивость коалиционных структур
относительно вектора Майерсона
Первый тип структуры: π = {{1, 2}, B2 , ..., Bm }.
Чтобы данная коалиционная структура была c - устойчива, каждому игроку должно быть выгодно оставаться в своей коалиции и не объединяться с
игроками третьего уровня. Проанализируем, какие коалиции могут блокировать данное коалиционное разбиение и при каких условиях они не будут
являться блокирующими.
11
Во-первых, игрокам, состоящим в коалиции {1, 2}, должно быть не выгодно играть по отдельности, следовательно, выигрыш первого игрока в
коалиции должен быть больше:
(a)
σ
2
3β
4
+
≥ β.
Аналогичное условие должно выполняться и для второго игрока:
(b)
σ
2
β
4
−
≥ 0.
Во-вторых, либо игрокам третьего уровня должно быть невыгодно присоединяться к коалиции {1, 2}, либо выигрыш главного игрока или координатора должен становиться меньше в случае объединения с игроками
третьего уровня. Таким образом, должно выполняться хотя бы одно из
ниже представленных условий, где условие c1 гарантирует, что выигрыш
каждого игрока третьего уровня будет меньше, если он присоединиться к
коалиции {1, 2}. Если выполняется c2 (c3 ), то первому (второму) игроку не
выгодно объединяться с некоторым количеством игроков третьего уровня.
Условия c1 − c3 принимают вид:
σ
α
.
(c1 )
3 − b1 (b1 −1) ≤ 0,
.
(c2 )
.
(c3 )
σ
2
σ
2
+
−
α(b1 −2)
3β
+ bσ1 + 3β
4 ≥
3
4 ,
α(b1 −2)
β
+ bσ1 − β4 .
4 ≥
3
В-третьих, хотя бы одному из игроков должно быть не выгодно объединяться в максимальную коалицию:
α
σ
.
(d1 )
3 − n(n−1) ≤ 0,
.
.
(d2 )
(d3 )
σ
2
σ
2
α(n−2)
+ 3β
+ σn + 3β
4 ≥
3
4 ,
− β4 ≥ α(n−2)
+ σn − β4 .
3
В-четвертых, главному игроку должно быть не выгодно играть с игроками
третьего уровня без координатора:
(e)
σ
2
+
3β
4
≥ β.
Аналогично предыдущему случаю, координатору должно быть не выгодно
играть с игроками третьего уровня без главного игрока:
(f )
σ
2
−
β
4
≥ 0.
Соединим полученные условия вместе. Заметим, что условия (a), (b), (e), (f )
и (c2 ), (c3 ), и (d2 ), (d3 ) повторяются, исключим повторы.
12
σ
2
α
3
+ 3β
4 ≥ β,
− b1 (bσ1 −1) ≤ 0 или (и)
α
3
−
σ
n(n−1)
≤0
или (и)
σ
2
−
β
4
≥
α(b1 −2)
3
σ
2
−
β
4
≥
α(n−2)
3
+
+
σ
b1
σ
n
− β4 ,
− β4 .
Далее, каждое из условий выразим относительно σ:
β
σ ≥ 2,
1
σ ≥ 31 (α(b1 − 1)b1 ) или (и) σ ≥ 2αb
3 ,
σ ≥ 13 (α(n − 1)n) или (и) σ ≥ 2αn
3 .
.
1
1
Заметим, что при допустимых параметрах (b1 ≥ 3, n > b1 ) 2αb
3 ≤ 3 (α(b1 −
2αb1
1
2αn
1)b1 ) и 2αn
3 ≤ 3 (α(n − 1)n), а так же 3 > 3 .
Следовательно, три неравенства являются избыточными, оставим четвертое неравенство σ ≥ 2αn
3 . Запишем получившуюся систему:
σ ≥ β,
2
(2.1)
σ ≥ 2αn .
3
Графическое решение этой системы (2.1) приведено на рис. 3, т. е. это область значений допустимых параметров при которых коалиционная структура π является c - устойчивой.
Рис. 3: Область значений параметров, удовлетворяющих (2.1) при n = 10
13
Второй тип структуры: π = {{1}, B2 , ..., Bm }.
Для того, чтобы данная коалиционная структура была c-устойчивой необходимо, чтобы первому игроку было невыгодно объединяться с кем-либо,
т. е. его выигрыш в одноэлементной коалиции должен быть больше или
остальные игроки при объединении с главным игроком будут терпеть убытки, т. е. их выигрыш будет отрицательным.
Рассмотрим все возможные блокирующие коалиции.
1) Для того, чтобы коалиция {1, 2} не являлась блокирующей необходимо
выполнение хотя бы одного из условий
3β
σ
.
(a1 )
2 + 4 ≤ β,
β
σ
.
(a2 )
2 − 4 ≤ 0.
2) Коалиция Bl , где 1, 2 ∈ Bl , |Bl | > 2, |Bl | =
6 n, не будет блокировать коалиционную структуру π, если будет выполняться хотя бы одно из условий
α(b1 −2)
.
(b1 )
+ bσ1 + 3β
3
4 ≤ β,
.
.
(b2 )
(b3 )
α(b1 −2)
+ bσ1
3
α
σ
3 − b1 (b1 −1)
− β4 ≤ 0,
≤ 0.
3) Максимальная коалиция {N } не будет блокировать коалиционную структуру, если выполняется одно из условий
α(n−2)
+ σn + 3β
.
(c1 )
3
4 ≤ β,
α(n−2)
β
σ
.
(c2 )
+ n − 4 ≤ 0,
3
α
σ
.
(c3 )
3 − n(n−1) ≤ 0.
Коалицию содержащую в себе главного игрока и игроков третьего уровня
не считаем блокирующей, так как выигрыш у игроков в обеих коалиционных структурах одинаков.
Соберем все условия вместе, исключим повторы:
β
σ
−
2
4 ≤0
α(b1 −2)
α
σ
+ bσ1 − β4 ≤ 0,
3 − b1 (b1 −1) ≤ 0 или (и)
3
α(n−2)
α − σ ≤ 0 или (и)
+ σ − β ≤ 0.
3
n(n−1)
3
14
n
4
.
Выразим каждое условие относительно σ:
β
σ≤ 2
1
1 −2))
или (и)
σ ≥ α(b1 −1)b
,
σ ≤ b1 (3β−4α(b
12
3
σ ≤ n(3β−4α(n−2))
или (и)
σ ≥ α(n−1)n
.
12
3
(2.2)
Графическое решение этой системы (2.2) приведено на рис. 4, т. е. область
значений параметров, при которых коалиционная структура π будет Сустойчивой.
Рис. 4: Область значений параметров, удовлетворяющих (2.2) при n = 4, b1 = 3
Третий тип структуры: π = {B1 , . . . , Bm }, 1, 2 ∈ B1 ,
|B1 | > 2, |B1 | =
6 n.
Для того, чтобы данная коалиционная структура была c - устойчивой необходимо, чтобы все игроки, состоящие в коалиции B1 получали больше, чем
по отдельности, хотя бы одному игроку должно быть невыгодно объединяться в максимальную коалицию, также выигрыш главного игрока или
(и) координатора должен быть больше, чем при объединении в двухэлементную коалицию. Соответственно, возможные блокирующие коалиции:
{1}, {2}, {Bk }, {1, 2}, {N }, где {Bk }, |Bk | ≥ 1 — коалиция содержащая в
себе игроков третьего уровня.
1) Главному игроку будет невыгодно играть одному, если его выигрыш в
коалиции B1 больше:
(a)
α(b1 −2)
3
+
15
σ
b1
+
3β
4
≥ β.
2) Координатор в коалиции B1 получит больше, чем в коалиции {2}, если
будет выполняться условие:
(b)
α(b1 −2)
3
+
σ
b1
−
β
4
≥ 0.
3) Ведомым игрокам будет невыгодно объединяться в коалицию {Bk }, если
будет выполняться условие:
α
3
(c)
−
σ
b1 (b1 −1)
≥ 0.
4) Коалиция {1, 2} не будет являться блокирующей, если хотя бы одно
условие будет выполняться:
α(b1 −2)
3β
σ
+ bσ1 + 3β
.
(d1 )
3
4 ≥ 2 + 4 ,
α(b1 −2)
.
(d2 )
+ bσ1 − β4 ≥ σ2 − β4 .
3
5) Максимальная коалиция N не будет блокировать коалиционную структуру π, если будет выполняться хотя бы одно из условий:
α(b1 −2)
α(n−2)
.
(e1 )
+ bσ1 + 3β
+ σn + 3β
3
4 ≥
3
4 ,
α(b1 −2)
.
(e2 )
+ bσ1 − β4 ≥ α(n−2)
+ σn − β4 ,
3
3
α
σ
α
σ
.
(e3 )
3 − b1 (b1 −1) ≥ 3 − n(n−1) .
Заметим, что условие (e3 ) при допустимых значениях (n > b1 , a ≥ 0)
никогда не выполняется, т. е. выигрыш игрока третьего уровня возрастает
с увеличением количества игроков в коалиции.
Соберем все условия вместе, удалив повторы.
α(b1 −2)
β
σ
+
−
3
b
4 ≥0
1
α− σ
3
b1 (b1 −1) ≥ 0
α(b1 −2)
+ bσ1 − σ2 ≥ 0
3
α(b1 −2) + σ − σ ≥ 0
3
b1
n
Разрешим каждое условие относительно σ:
1 −2)
σ ≥ b1 (3β−4α(b
12
1
σ ≤ α(b1 −1)b
3
σ ≤ 2b31 α
σ ≥ nb31 α
(2.3)
Система (2.3) не имеет решения, т. к. третье и четвертое неравенства
противоречат друг другу, следовательно, данная коалиционная структура
не является c - устойчивой.
16
Четвертый тип структуры: π = {B1 , B2 , ..., Bm }, 1 ∈ B1 ,
|B1 | > 1, 2 ∈
/ B1 .
Для того, чтобы данная структура была c - устойчивой необходимо, чтобы
первому игроку или игрокам третьего уровня было невыгодно объединяться ни с координатором, ни в максимальную коалицию. Также выигрыш
главного игрока должен быть больше в коалиции B1 , чем при кооперации
только с координатором или координатору должно быть выгодно играть
одному. Выпишем все возможные блокирующие коалиции:{1, 2}, {N }, {Bl },
где 1, 2 ∈ Bl , |Bl | > 2.
В силу ограничения на коммуникацию внутри коалиции B1 , игроки третьего уровня получают нулевой выигрыш. Распределение выигрыша в коалиционной структуре π совпадает с распределение выигрыша в коалиционной
структуре второго типа, при этом совпадают так же и возможные блокирующие коалиции.Cледовательно, условия c - устойчивости коалиционной
структуры π аналогичны условиям, полученным для коалиционной структуры второго типа:
β
σ≤ 2
1 −2))
1
(2.4)
σ ≤ b1 (3β−4α(b
или (и)
σ ≥ α(b1 −1)b
,
12
3
σ ≤ n(3β−4α(n−2))
или (и)
σ ≥ α(n−1)n
.
12
3
Пятый тип структуры: π = {N }.
Объединяться в максимальную коалицию всем игрокам будет выгодно, когда им будет невыгодно играть по отдельности, разбиваться на меньшие коалиции. Выпишем все возможные блокирующие коалиции: {1}, {2}, {Bk },
{Bl }, {Bm }, {1, 2}, где {Bk }, |Bk | ≥ 1 — коалиция содержащая в себе игроков третьего уровня, 1, 2 ∈ Bl , |Bl | > 2, |Bl | =
6 n, 1 ∈ Bm , 2 ∈
/ Bm , |Bm | > 2.
1) Первый игрок не будет блокировать коалиционную структуру π, если
будет выполняться условие:
(a)
α(n−2)
3
+
σ
n
+
3β
4
≥ β.
2) Координатор не будет блокировать коалиционную структуру π, если будет выполняться условие:
(b)
α(n−2)
3
+
σ
n
−
β
4
≥ 0.
3) Игроки третьего уровня не будут блокировать коалиционную структуру
π, если будет выполняться условие:
17
α
3
(c)
−
σ
n(n−1)
≥ 0.
4) Коалиция Bl не является блокирующей, если выполняется хотя бы одно
из неравенств:
α(n−2)
α(b1 −2)
.
(c1 )
+ σn + 3β
+ bσ1 + 3β
3
4 ≥
3
4 ,
σ
n
−
β
4
≥
α(b1 −2)
3
σ
n(n−1)
≥
α
3
−
σ
b1 (b1 −1) .
.
(c2 )
α(n−2)
3
.
(c3 )
α
3
−
+
+
σ
b1
− β4 ,
5) Коалиция {1, 2} не является блокирующей, если выполняется хотя бы
одно из неравенств:
α(n−2)
3β
σ
.
(d1 )
+ σn + 3β
3
4 ≥ 2 + 4 ,
.
(d2 )
α(n−2)
3
+
σ
n
−
β
4
≥
σ
2
− β4 .
6) Коалиция {Bm } не будет блокирующей, если будет выполнено хотя бы
одно условие:
α(n−2)
.
(e1 )
+ σn + 3β
3
4 ≥ β,
α
σ
.
(e2 )
3 − n(n−1) ≥ 0.
Соберем все неравенства в систему, исключив повторы. Так как неравенство (c3 ) при допустимых значениях (n > b1 , a ≥ 0) выполняется всегда,
то исключим из рассмотрения возможность блокирования коалиционной
структуры π коалицией {Bl }.Тогда система ограничений принимает вид:
α(n−2)
+ σn − β4 ≥ 0,
3
σ
α3 − n(n−1)
≥ 0,
α(n−2)
3
+
σ
n
−
σ
2
≥ 0.
Каждое из неравенств выше разрешим относительно σ:
σ ≥ n(3β−4α(n−2))
,
12
α(n−1)n
σ≤
,
3
σ≤
2αn
3 .
18
Заметим, что граница третьего ограничения меньше второго, следовательно, второе ограничение избыточно:
(
σ≥
σ≤
n(3β−4α(n−2))
,
12
2αn
3
(2.5)
Графическое решение системы (2.5) приведено на рис. 5, т. е. область значений параметров, при которых коалиционная структура π устойчива.
Рис. 5: Область значений параметров, удовлетворяющих (2.5) при n = 10
Покажем, что при допустимых параметрах (когда коалиционная структура, состоящая из максимальной коалиции, c - устойчива) характеристическая функция не всегда удовлетворяет свойству супераддитивности.
Пусть n = 4, α = 8, σ = 13, β = 30
Подставим коэффиценты в систему (2.5):
(
(
(
26
13
≥
,
39 ≥ 26,
σ ≥ n(3β−4α(n−2))
,
3
12
13 ≤ 64
39 ≤ 64.
σ ≤ 2αn
3,
3 ,
Также подставим коэффициенты в условие супераддитивности (1.2) характеристической функции определенной в (1.1)
max{8; 14} ≤ 13 ≤ min{16; 30}
или
14 13 ≤ 16
Можно увидеть, что при данных параметрах коалиционная структура
π = {N } c - устойчива, но условие супераддитивности характеристической
19
функции нарушено.
На рис. 6 приведена область значений параметров, удовлетворяющих условию супераддитивности и c - устойчивости коалиционной структуры π.
Рис. 6: Область значений параметров, удовлетворяющих (2.5) и (1.2) при n = 10
Были разобраны все возможные типы коалиционных структур, и для
каждого случая приведены условия коллективной рациональности относительно вектора Майерсона. Сводные данные представлены в таблице ниже:
Коалиционная структура Условие
c - устойчивости
β
σ ≥ 2,
π = {{1, 2}, B2 , ..., Bm }
σ ≥ 2αn .
3
β
σ ≤ 2,
n
1 −2))
1
σ ≤ b1 (3β−4α(b
или (и) σ ≥ α(b1 −1)b
,
12
3
π = {{1}, B2 , ..., Bm }
n
n(3β−4α(n−2))
или (и) σ ≥ α(n−1)n
.
σ≤
12
3
π = {B1 , ..., Bm }
1 ∈ B1 , 2 ∈ B1 , |B1 | > 2
π = {B1 , B2 , ..., Bm },
1 ∈ B1 , |B1 | > 1, 2 ∈
/ B1
π = {N }
Не является c - устойчивой
σ
≤ β2
n
1 −2))
1
σ ≤ b1 (3β−4α(b
или (и) σ ≥ α(b1 −1)b
,
12
3
n
n(3β−4α(n−2))
или (и) σ ≥ α(n−1)n
.
σ≤
12
3
(
σ ≥ n(3β−4α(n−2))
,
12
2αn
σ≤ 3 .
20
2.2. C - устойчивость коалиционных структур
относительно ES - вектора
В данном разделе найдем условия c - устойчивости всех возможных
коалиционных структур, относительно ES - вектора.
Первый тип структуры: π = {{1, 2}, B2 , ..., Bm }.
Выпишем все возможные блокирующие коалиции: {1}, {2}, {Bl },
{Bm }, {N }, где Bm — коалиция, состоящая из главного игрока и произвольного количества игроков третьего уровня, Bl — коалиция, включающая в
себя главного игрока, координатора и произвольное число игроков третьего уровня.
1) Главному игроку будет невыгодно играть в коалиции {1}, если:
(a)
σ
2
+
3β
4
≥ β.
2) Аналогичное условие должно выполняться для второго игрока:
(b)
σ
2
−
β
4
≥ 0.
3) Коалиция Bl не будет блокирующей, если хотя бы одному игроку будет
невыгодно в нее вступать:
α(b1 −2)
3β
σ
.
(c1 )
+ b1 (bσ1 −1) + β(2b2b11−1) ,
2 + 4 ≥
b1
.
(c2 )
σ
2
−
α(b1 −2)
β
+ b1 (bσ1 −1) − 2bβ1 ,
4 ≥
b1
α(b1 −2)
+ b1 (bσ1 −1) − 2bβ1 .
b1
.
(c3 )
0≥
4) Коалиция Bm не будет блокирующей, если первому игроку будет невыгодно в нее вступать:
(d)
σ
2
+
3β
4
≥ β.
5) Коалиция N не будет блокирующей, хотя бы у одного из игроков выигрыш при объединении в максимальную коалицию будет меньше: В-третьих,
хотя бы одному из игроков должно быть не выгодно объединяться в максимальную коалицию.
α(n−2)
3β
σ
σ
.
(e1 )
+ n(n−1)
+ β(2n−1)
2 + 4 ≥
n
2n ,
.
(e2 )
σ
2
.
(e3 )
0≥
−
α(n−2)
β
β
σ
+ n(n−1)
− 2n
,
4 ≥
n
α(n−2)
β
σ
+ n(n−1)
− 2n
.
n
Соединим полученные условия вместе, исключим повторы:
21
σ
− β4 ≥ 0,
2
b(b1 +1)(b1 −2)
2(b1 −1)b1
−
a(b1 −2)
2
+
(2−b1 )β
4b1
или (и)
0 ≥ α(bb11−2) +
σ
b1 (b1 −1)
−
β
2b1 ,
b(n+1)(n−2)
2(n−1)n
−
или (и)
+
0 ≥ α(n−2)
n
a(n−2)
2
+
σ
b1 (n−1)
(2−n)β
4n
−
≥0
≥0
β
2n .
Далее, каждое из условий выразим относительно σ:
σ ≥ β2 ,
σ ≥ (b1 −1)(4α+β)
2(b1 +1)
σ≥
(n−1)(4α+β)
2(n+1)
1 −2)−β)
или (и) σ ≤ − (b1 −1)(2a(b
,
2
или (и) σ ≤
(2.6)
− (n−1)(2a(n−2)−β)
.
2
.
Графическое решение этой системы (2.6) приведено на рис. 7, т. е. это область значений допустимых параметров при которых коалиционная структура π является c - устойчивой.
Рис. 7: Область значений параметров, удовлетворяющих (2.6) при n = 10
Второй тип структуры: π = {{1}, B2 , . . . , Bm }.
Рассмотрим все возможные блокирующие коалиции: {1, 2}, {Bl }, {N }, где
1, 2 ∈ Bl , |Bl | > 2, |Bl | =
6 n.
1) Для того, чтобы коалиция {1, 2} не являлась блокирующей необходимо
22
чтобы выигрыш в коалиционной структуре π был больше:
3β
σ
.
(a1 )
2 + 4 ≤ β,
β
σ
.
(a2 )
2 − 4 ≤ 0.
2) Коалиция Bl , не будет блокировать коалиционную структуру π, если
будет выполняться хотя бы одно из ограничений:
α(b1 −2)
.
(b1 )
+ b1 (bσ1 −1) + β(2b2b11−1) ≤ β,
b1
.
(b2 )
α(b1 −2)
b1
+
σ
b1 (b1 −1)
−
β
2b1
≤ 0.
3) Максимальная коалиция {N } не будет блокировать коалиционную структуру, если выполняется одно из ограничений:
.
(c1 )
.
(c2 )
α(n−2)
n
α(n−2)
n
+
+
σ
n(n−1)
σ
n(n−1)
+
−
β(2n−1)
≤
2n
β
2n ≤ 0.
β,
Коалицию содержащую в себе главного игрока и игроков третьего уровня
не считаем блокирующей, так как выигрыш у игроков в обеих коалиционных структурах одинаков.
Соберем все условия вместе, исключив повторы:
β
σ
2 − 4 ≤ 0,
α(b1 −2)
+ b1 (bσ1 −1) − 2bβ1 ≤ 0,
b1
α(n−2)
β
σ
+ n(n−1)
− 2n
≤ 0.
n
Выразим каждое условие относительно σ:
β
σ ≤ 2,
1 −2)−β)
σ ≤ − (b1 −1)(2α(b
,
2
σ ≤ − (n−1)(2α(n−2)−β)
.
2
Однако, мы можем переписать данную систему, исключив второе условие:
(
σ ≤ β2 ,
σ ≤ − (n−1)(2α(n−2)−β)
.
2
(2.7)
В справедливости данного решения можно легко убедиться:
1 −2)−β)
− (b1 −1)(2α(b
≥ − (n−1)(2α(n−2)−β)
2
2
т. к. n > b1 , α ≥ 0, β ≥ 0.
23
Графическое решение этой системы (2.7) приведено на рис. 8, т. е. область значений параметров, при которых коалиционная структура π будет
С-устойчивой.
Рис. 8: Область значений параметров, удовлетворяющих (2.7) при n = 4, b1 = 3
Третий тип структуры: π = {B1 , ..., Bm }, 1 ∈ B1 , 2 ∈ B1 ,
|B1 | > 2, |B1 | =
6 n.
Все возможные блокирующие коалиции: {1}, {2}, {Bk }, {1, 2}, {N }, где {Bk },
|Bk | ≥ 1 — коалиция содержащая в себе игроков третьего уровня.
1) Главному игроку будет невыгодно будет играть одному, если будет выполняться ограничение:
(a)
α(b1 −2)
b1
+
σ
b1 (b1 −1)
+
β(2b1 −1)
2b1
≥ β.
2) Координатор и игроки третьего уровня в коалиции B1 должны получать
больше, чем в коалициях {2}, {Bk }:
(b)
α(b1 −2)
b1
+
σ
b1 (b1 −1)
−
β
2b1
≥ 0.
3) Коалиция {1, 2} не будет являться блокирующей, если хотя бы одно
ограничение будет выполняться:
α(b1 −2)
.
(c1 )
+ b1 (bσ1 −1) + β(2b2b11−1) ≥ σ2 + 3β
b1
4 ,
α(b1 −2)
.
(c2 )
+ b1 (bσ1 −1) − 2bβ1 ≥ σ2 − β4 .
b1
4) Максимальная коалиция N не будет блокировать коалиционную структуру π, если будет выполняться хотя бы одно из условий:
α(b1 −2)
σ
.
(d1 )
+ b1 (bσ1 −1) + β(2b2b11−1) ≥ α(n−2)
+ n(n−1)
+ β(2n−1)
b1
n
2n ,
24
α(b1 −2)
β
σ
.
(d2 )
+ b1 (bσ1 −1) − 2bβ1 ≥ α(n−2)
+ n(n−1)
− 2n
.
b1
n
Соберем все условия вместе, удалим повторы:
α(b1 −2)
β
σ
b1 + b1 (b1 −1) − 2b1 ≥ 0,
α(b1 −2)
+ b1 (bσ1 −1) + β(2b2b11−1) ≥ σ2 + 3β
b
4 ,
1
α(b1 −2) + σ − β ≥ α(n−2) + σ − β .
b1
b1 (b1 −1)
2b1
n
n(n−1)
2n
Разрешим каждое условие относительно σ:
(b1 −1)(2α(b1 −2)−β)
,
σ≥−
2
(b1 −1)(4α+β)
σ ≤ 2(b1 +1) ,
σ ≥ (b1 −1)(4α+β)(n−1)
.
2b1 +2n−1
(2.8)
Система (2.8) несовместна т. к. второе и третье неравенства не имеют общего решения. В этом можно убедиться, показав, что нижеприведенное
неравенство верно:
(b1 −1)(4α+β)(n−1)
2b1 +2n−1
≥
(b1 −1)(4α+β)
2(b1 +1)
Приведем его к общему знаменателю, разделим на (4α + β),
(b1 − 1), перенесем все в левую часть:
2b1 (n−2)−1
(2(b1 +n)−1)(2b1 +2)
≥0
Легко увидеть, что числитель и знаменатель при допустимых параметрах
(n > b1 ) буду положительными, неравенство верно. Следовательно, коалиционная структура π = {B1 , ..., Bm }, 1 ∈ B1 , 2 ∈ B1 , |B1 | > 2 не является
c - устойчивой.
Четвертый тип структуры: π = {B1 , B2 , ..., Bm }, 1 ∈ B1 , |B1 | > 1,
2∈
/ B1 .
Распределение выигрыша в коалиционной структуре π совпадает с
распределением выигрыша в коалиционной структуре второго типа, также
совпадают все возможные блокирующие коалиции, следовательно, условия c - устойчивости коалиционной структуры π аналогичны условиям,
полученным для коалиционной структуры второго типа:
(
σ ≤ β2 ,
(2.9)
σ ≤ − (n−1)(2α(n−2)−β)
.
2
Пятый тип структуры: π = {N }.
Выпишем все возможные блокирующие коалиции: {1}, {2}, {Bk }, {Bl },
25
{Bm }, {1, 2}, где {Bk }, |Bk | ≥ 1 — коалиция содержащая в себе игроков
третьего уровня, 1, 2 ∈ Bl , |Bl | > 2, |Bl | =
6 n, 1 ∈ Bm , 2 ∈
/ Bm , |Bm | > 2.
1) Главному игроку будет невыгодно играть одному, если будет выполняться условие:
(a)
α(n−2)
n
+
σ
n(n−1)
+
β(2n−1)
2n
≥ β.
2) Координатору или ведомым игрокам будет невыгодно играть в коалициях {2}, {Bk }, если:
(b)
α(n−2)
n
+
σ
n(n−1)
−
β
2n
≥ 0.
3) Коалиция {1, 2} не будет являться блокирующей, если хотя бы одно
ограничение будет выполняться:
α(n−2)
σ
.
(c1 )
+ n(n−1)
+ β(2n−1)
≥ σ2 + 3β
n
2n
4 ,
α(n−2)
β
σ
+ n(n−1)
− 2n
≥ σ2 − β4 .
.
(c2 )
n
4) Коалиция Bl не является блокирующей, если выполняется хотя бы одно
из условий:
α(n−2)
σ
.
(d1 )
+ n(n−1)
+ β(2n−1)
≥ α(bb11−2) + b1 (bσ1 −1) + β(2b2b11−1) ,
n
2n
α(n−2)
β
σ
+ n(n−1)
− 2n
≥ α(bb11−2) + b1 (bσ1 −1) − 2bβ1 .
.
(d2 )
n
5) Коалиция Bm не блокирует коалиционную структуру π, если выполняется хотя бы одно из неравенств:
α(n−2)
σ
.
(e1 )
+ n(n−1)
+ β(2n−1)
≥ β,
n
2n
α(n−2)
β
σ
.
(e2 )
+ n(n−1)
− 2n
≥ 0.
n
Соберем все условия вместе, удалим повторы:
α(n−2)
β
σ
+ n(n−1)
− 2n
≥ 0,
n
α(n−2)
β
σ
+ n(n−1)
− 2n
,
n
α(n−2) + σ − β ≥ α(b1 −2) +
n
n(n−1)
2n
b1
σ
b1 (b1 −1)
−
β
2b1 .
Каждое из неравенств разрешим относительно σ:
σ ≥ − (n−1)(2α(n−2)−β)
,
2
σ ≤ (n−1)(4α+β)
,
2(n+1)
1 −1)
σ ≤ (n−1)(4α+β)(b
.
2b1 +2n−1
Заметим, что третье условие избыточно, исключив его, получим следующую систему:
26
(
σ ≥ − (n−1)(2α(n−2)−β)
,
2
.
σ ≤ (n−1)(4α+β)
2(n+1)
(2.10)
Графическое решение системы (2.10) приведено на рис. 9, т. е. область
значений параметров, при которых коалиционная структура π устойчива.
Рис. 9: Область значений параметров, удовлетворяющих (2.10) при n = 10
Покажем, что при допустимых параметрах c - устойчивости максимальной коалиции, характеристическая функция не всегда супераддитивна. Пусть n = 10, α = 4, σ = 10, β = 20. Подставим коэффиценты в систему
(2.10)
(
(
(
(n−1)(2α(n−2)−β)
σ≥−
,
10 ≥ −198,
10 ≥ −198,
2
(n−1)(4α+β)
144
σ ≤ 2(n+1) ,
110 ≤ 11 ,
110 ≤ 144.
Также подставим коэффициенты в условие супераддитивности (1.2) характеристической функции определенной в (1.1)
max{4; 12} ≤ 10 ≤ min{8; 20}
или
12 10 8
Можно увидеть, что при данных параметрах коалиционная структура
π = {N } c - устойчива, но условие супераддитивности характеристической
функции нарушено.
На рис. 10 приведена область значений параметров, удовлетворяющих условию супераддитивности и c - устойчивости коалиционной структуры π.
27
Рис. 10: Область значений параметров, удовлетворяющих (2.10) и (1.2) при n = 10
Были разобраны все возможные типы коалиционных структур, и для
каждого случая приведены условия коллективной рациональности относительно ES - вектора. Сводные данные представлены в таблице ниже:
Коалиционная структура Условие c - устойчивости
σ ≥ β2 ,
σ ≥ (b1 −1)(4α+β)
,
2(b1 +1)
или (и)
1 −2)−β)
σ ≤ − (b1 −1)(2a(b
.
π = {{1, 2}, B2 , ..., Bm }
2
σ ≥ (n−1)(4α+β)
,
2(n+1)
или (и)
(n−1)(2a(n−2)−β)
σ
≤
−
.
2
(
σ ≤ β2 ,
π = {{1}, B2 , ..., Bm },
σ ≤ − (n−1)(2α(n−2)−β)
.
2
π = {B1 , ..., Bm }
Не является c - устойчивой
1 ∈ B1 , 2 ∈ B1 , |B1 | > 2
(
σ ≤ β2 ,
π = {B1 , B2 , ..., Bm },
1 ∈ B1 , |B1 | > 1, 2 ∈
/ B1
,
σ ≤ − (n−1)(2α(n−2)−β)
2
(
σ ≥ − (n−1)(2α(n−2)−β)
,
2
π = {N }
σ ≤ (n−1)(4α+β)
.
2(n+1)
28
2.3. Численный пример
Приведем численный пример, иллюстрирующий полученные результаты c - устойчивости коалиционных структур относительно вектора Майерсона и ES - вектора.
Пример Пусть известно количество игроков n = 4, также заданы параметры эффективности для каждого типа игроков: β = 6, σ = 4, α = 2.
Проверим каждый из возможных типов коалиционных структур на c устойчивость относительно выбранного принципа оптимальности:
Первый тип: π = {{1, 2}, B2 , ..., Bm }
Для первого случая возможны следующие коалиционные структуры:
{{1, 2}, {3}, {4}}, {{1, 2}, {3, 4}} В первую очередь проверим c - устойчивость коалиционной структуры, относительно вектора Майерсона, подставив значения в систему (2.1)
(
(
4≥3
σ ≥ β2
4 16
σ ≥ 2αn
3
3
А также подставим значения параметров в систему (2.6), чтобы проверить
c - устойчива ли коалиционная структура, относительно ES - вектора. Заметим, что b1 = 3.
4≥ 3
σ ≥ β2
4 ≥ 27
(b1 −1)(4α+β)
σ ≥ 2(b1 +1)
или (и)
или
(и)
42
(b1 −1)(2a(b1 −2)−β)
σ≤−
2
(n−1)(4α+β)
σ
≥
21
2(n+1)
4 5
или (и)
или (и)
(n−1)(2a(n−2)−β)
σ≤−
2
4 −3
Коалиционные структуры {{1, 2}, {3}, {4}}, {{1, 2}, {3, 4}} не являются c устойчивыми.
Второй тип: π = {{1}, B2 , ..., Bm }
Выпишем все возможные коалиционные структуры, которые принадлежат
данному типу: {{1}, {2}, {3}, {4}}, {{1}, {2, 3}, {4}}
{{1}, {2}, {3, 4}}, {{1}, {2, 4}, {3}}, {{1}, {2, 3, 4}} Подставим значения параметров в условия c - устойчивости коалиционной структуры π.
1) Относительно вектора Майерсона
29
β
σ
≤ 2 b (3β−4α(b −2))
1
1
σ≤
12
или (и)
1
σ ≥ α(b1 −1)b
3
n(3β−4α(n−2))
σ≤
12
или (и)
σ ≥ α(n−1)n
3
4 3
5
42
или (и)
4≥4
2
43
или (и)
48
2) Относительно ES - вектора
(
σ≤
(
β
2
σ ≤ − (n−1)(2α(n−2)−β)
2
43
4 −3
Коалиционные структуры: {{1}, {2}, {3}, {4}}, {{1}, {2, 3}, {4}}
{{1}, {2}, {3, 4}}, {{1}, {2, 4}, {3}}, {{1}, {2, 3, 4}} не являются c - устойчивыми.
Четвертый тип: π = {B1 , B2 , ..., Bm },
1 ∈ B1 , |B1 | > 1, 2 ∈
/ B1 .
Выше было показано, коалиционные структуры второго типа не являются
c - устойчивыми, следовательно, следующие структуры также не устойчивы: {{1, 3, 4}, {2}}, {{1, 3}, {2}, {4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2}, {3}},
{{1, 4}, {2, 3}}
Пятый тип: π = {N }
Подставим значения параметров эффективности в условия c - устойчивости коалиционной структуры π.
1) Относительно вектора Майерсона.
(
(
4 ≥ 23
σ ≥ n(3β−4α(n−2))
12
σ ≤ 2αn
4 ≤ 16
3
3
2) Относительно ES - вектора
(
σ ≥ − (n−1)(2α(n−2)−β)
2
(n−1)(4α+β)
σ ≤ 2(n+1)
(
4 ≥ −3
4 ≤ 21
5
Коалиционная структура π = {N } c - устойчива относительно вектора
Майерсона и ES - вектора.
30
Заключение
В данной работе был изучен вопрос коллективной устойчивости коалиционных структур, относительно двух принципов оптимальности — вектора Майерсона и ES - вектора, для игры с двумя типами ограничений на
кооперацию и коммуникацию игроков, где коммуникация между игроками
была ограничена при помощи ненаправленного коммуникационного графа,
а кооперация коалиционной структурой.
Были получены аналитические условия c - устойчивости для всех
возможных типов коалиционных структур. Было выяснено, что коалиционная структура, содержащая в себе коалицию из трех типов игроков, но
не являющаяся максимальной, не является c - устойчивой. Результаты иллюстрируются численным примером и графической интерпретацией аналитических условий.
31
Список литературы
[1] Григорьева И. Р. Кооперативные решения в игре с тремя типами участников. маг.дис., СПбГУ, 2015, 61 с.
[2] Парилина Е. М., Седаков А. А. Устойчивость коалиционных структур в
одной модели банковской кооперации. Математическая теория игр и ее
приложения, 2012, т. 4, № 4, сс. 45 - 62.
[3] Петросян Л. А., Зенкевич Н. А.,
игр. СПБ.: БХВ-Петербург, 2012, 432 c.
Шевкопляс
Е. В.
Теория
[4] Aumann R. J. and Dreze J H. Cooperative Games with Coalition Structures.
International Journal of Game Theory, 1974, pp. 217 – 237.
[5] Ballester С. NP-completeness in hedonic games. Games and Economic
Behavior. 2004, pp. 1 – 30.
[6] Banerjee S., Konishi H.,Sonmez T. Core in a simple coalition formation
game. Social Choice and Welfare. 2001, pp. 135 – 153.
[7] Bogomolnaia A. and Jackson M. O. The Stability of Hedonic Coalition
Structures. Games and Economic Behavior, 2002, pp. 201 – 230.
[8] Dimitrov D., Borm P., Hendrickx R. Simple priorities and core stability in
hedonic games. Social Choice and Welfare. 2006, pp. 421 – 433.
[9] Driessen T.S.H. Funaki Y. Coincidence of and collinearity between game
theoretic solutions. OR Spectrum, 1991,
pp. 15 - 30.
[10] Haeringer G. Stable Coalition Structures with Fixed Decision Scheme
Economics with Heterogeneous Interacting Agents. Lecture Notes in
Economics and Mathematical Systems. 2001, V. 503, Part IV, pp. 217 – 230.
[11] Myerson R. Graphs and cooperation in games. Mathematics of Operations
Research, 1977, pp. 225 - 229 .
[12] Owen, G. Values of games with a priori unions. In: Henn R., Moeschlin O.
(eds.) Essays in mathematical economics and game theory, Springer-Verlag,
Berlin, 1977, pp. 76 - 88.
[13] Sedakov A., Parilina E., Volobuev Yu., Klimuk D. Existence of Stable
Coalition Structures in Three-person Games. Contributions to Game Theory
and Management, 2013, Vol. 6, pp. 407 - 422.
32
[14] Shapley L. S. (1953). A value for n-person games. In: Kuhn, H. W., Tucker,
A. W. (Eds.), Contributions to the Theory of Games, vol. II, Princeton
University Press, pp. 307 - 317 .
33
Отзывы:
Авторизуйтесь, чтобы оставить отзыв