Системный анализ в информационных технологиях. Громов Ю.Ю - 73 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

(
)
.),,(infinf
),,(infinfv
)(\
)(\)(\
)(\
)(\)(\
∑
∑
∈
∈
∈∈
∈∈
+
+≥
Ri
RSIRSi
RSIRSISS
Si
RSIRSi
RSIRSIRR
xxxH
xxxHRS
XxXx
XxXx
U
UU
U
UU
U
Переход в первом слагаемом от инфимума по множествам Х
R
и X
I\(R∪S)
инфимуму по множеству Х
I\S
всевозможных пар
(X
R
, X
I\(R∪S
) и во втором слагаемом от инфимума по множествам Х
S
и X
I\(R∪S)
к инфимуму по множеству Х
R\S
всевозможных
пар (
X
S
, X
I\(S∪R
) может лишь уменьшить правую часть. Поэтому
∑
∑
∈∈
∈∈
+≥
Ri
RIRi
RIRI
Si
SISi
SISI
xxHxxHRS
XxXx
),(inf),(inf)(v
\
\\
\
\\
U
для всех x
S
∈ X
S
и x
R
∈ X
R
. Отсюда
∑
∑
∈∈
∈
∈
∈
∈
+≥
Ri
RIRi
RIRI
RR
Si
SISi
SISI
xxHxxHRS
Xx
Xx
Xx
S
X
S
x
),(infsup),(infsup)(v
\
\\
\
\\
U
,
что и требовалось доказать.
Из свойства супераддитивности характеристической функции следует, что игроки, объединяясь в коалицию I, получают
наибольший выигрыш v(I). Поскольку коалиции I никто не противостоит, то ее гарантированный выигрыш v(I) совпадает с
максимальным
∑
∈
∈
=
Ii
i
Xx
xHI )(sup)(v .
В такой ситуации проблема конфликтного выбора стратегии отсутствует. Основной задачей игроков становится дости-
жение справедливого дележа общего выигрыша v(I). Эти вопросы являются предметом исследования теории кооперативных
игр. Для того чтобы определить кооперативную игру, необходимо задать множество игроков I и характеристическую функ-
цию.
Игра T
v
= <I, v>, называется кооперативной игрой в форме характеристической функции.
Определим понятие дележа в кооперативной игре.
Определение. Дележом для игры п лиц с характеристической функцией v называется вектор
α = (α
1
, α
2
, ..., α
n
),
удовлетворяющий условиям:
1)
)(v
1
I
n
i
i
=α
∑
=
;
2)
α
i
>= v({i}) для всех i ∈ I.
Первое условие означает, что весь полученный выигрыш распределяется между игроками. Это условие называется ус-
ловием коллективной рациональности. Второе условие означает, что игрок в результате объединения должен получить вы-
игрыш не меньший, чем он может себе уверенно обеспечить самостоятельно, и называется условием индивидуальной рацио-
нальности.
Пусть
α' и α" – дележи и S – некоторая коалиция.
Определение. Дележ
α' доминирует дележ α'' по коалиции S (α' > α"), если:
а)
ii
α
′′
>α
′
для всех i ∈ S;
б)
∑
∈
≤α
′
Si
i
S)(v
.
Дележ
α' доминирует α'' (α' ⊂ α"), если существует такая коалиция S ⊂ I, что α' ⊂ α".
Условие а) в определении доминирования означает, что все члены коалиции S предпочитают
α'; условие б) – что они в
состоянии реализовать дележ
α'. Отметим, что доминирование по коалиции, состоящей из единственного игрока, а также по
множеству всех игроков I невозможно. Как легко видеть, в этих случаях нарушаются первое и второе свойства дележа.
Дележ, который не доминируется никаким другим дележом, можно считать в известном смысле «вполне устойчивым».
Определение. Множество всех недоминируемых дележей в кооперативной игре с характеристической функцией v
называется
С-ядром.
Любой дележ из С-ядра устойчив в том смысле, что ни одна из коалиций не имеет ни желания, ни возможности изме-
нить исход игры. Но С-ядро часто оказывается пустым.
Приведем важное необходимое и достаточное условие принадлежности дележа С-ядру.
Утверждение. Для того чтобы дележ
α принадлежал С-ядру кооперативной игры, необходимо и достаточно, чтобы
выполнялось неравенство
∑
∈
≥α
SI
i
S)(v
для любой коалиции S ⊂ I.
Доказательство. Необходимость. Пусть дележ
α принадлежит С-ядру. Предположим, что найдется некоторая коалиция
S
⊂ I, для которой

Страницы