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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

6minmax),(minmax
=
=
=
ij
i
j
i
j
ajiKV .
Стратегия j = –2 второго игрока обеспечивает ему при любом выборе стратегии игроком I выигрыш не меньше V и на-
зывается максиминной стратегией. Стратегия 1 = 3 первого игрока обеспечивает, ему при любых действиях второго игрока
проигрыш не больше V и называется минимаксной стратегией.
Таким образом, если сельскохозяйственное предприятие выберет для посева культуру A
2
, то при самых неблагоприят-
ных условиях урожайность будет не меньше шести единиц.
Вернемся теперь к рассмотрению игр п лиц.
Пусть игроки из множества I находятся в таких условиях, что совокупный выигрыш, который в состоянии получить
любая из коалиций S
⊂ I, может быть произвольным образом распределен между членами коалиции S. В этом случае гово-
рят, что выигрыши трансферабельны. Обозначим через v(S) максимальный выигрыш, который может гарантировать себе
коалиция S. Функция v, ставящая в соответствие каждой коалиции S
⊂ I максимальный гарантированный ею выигрыш v(S),
называется характеристической функцией, которая является основополагающим понятием теории кооперативных игр.
Происхождение характеристической функции может иметь различную природу. Рассмотрим следующий пример.
Пример 4. Три предприятия могут осуществлять реконструкцию производства как совместно, так и каждое в отдель-
ности. При этом реконструкция, осуществляемая самостоятельно, обойдется предприятию с номером i в сумму w({i}), а для
любого объединения предприятий S – в сумму w(S). Если считать, что объединение предприятий снижает затраты на рекон-
струкцию, то предприятия получат от объединения выигрыш
∑
∈
⊂−=
Si
SSwiws }3,2,1{),(})({)(v ,
который может быть распределен между предприятиями из S в виде «премии». Поскольку u(S) представляет собой макси-
мальный гарантированный выигрыш, который получает коалиция S, то ее можно назвать характеристической функцией.
При построении характеристической функции наиболее часто пользуются следующим ее определением.
Определение. Характеристической функцией игры п лиц называется вещественная функция и, определенная на
подмножествах множества I и ставящая в соответствие любому S
⊂ I значение (для S) антагонистической игры двух лиц, ко-
торую разыграли бы S и I \ S, если бы эти две коалиции действительно возникли; при этом под функцией выигрыша коали-
ции S понимается сумма выигрышей участников коалиции
∑
∈
=
Si
i
S
xHK )( ,
а функция выигрыша коалиции I \ S полагается равной – K
S
.
Пустую коалицию, как и всякое пустое множество, будем обозначать символом
∅. Из приведенного определения сле-
дует v(
∅) = 0. Если S и R – непересекающиеся коалиции, то, очевидно, объединив свои усилия, они могут получить выигрыш
не меньший, чем если бы они действовали отдельно. Следовательно, v(S) + v(R) <= (S
∪ R), если S ∩ R ≠ ∅. Такое свойство
характеристической функции называется супераддитивностью. Докажем, что оно имеет место.
Обозначим через x
s
вектор стратегий игроков, входящих в коалицию S, который определим в качестве стратегии коали-
ции S. Представим v(S) в виде
v(S) = sup inf
∑
∈Si
i
xH ),( x
S
∈ X
S
, x
I \ S
∈ X
I \ S
,
где
∏
∈
=
Si
is
XX
– множество стратегий коалиции S; X
I \ S
=
∏
∈ SIi
i
X
\
– множество стратегий коалиции I \ S.
Имеем
()
),(
inf
sup
v
)(\
)(\)(\
RSIRSi
xxHRS
RSI
X
RSI
x
RS
X
RS
x
UU
UU
UU
U
∈
∈
= .
Если супремум в правой части взять по множеству X
s
, а затем по X
R
, то он разве лишь уменьшится, т.е.
∑
∈
∈
∈∈
≥
RSi
RSIRSi
RSIRSI
xxxHRS
Xx
R
X
R
x
S
X
S
x
U
U
UU
U ),,(infsupsup)(v
)(\
)(\)(\
,
и тем более
()
.),,(inf
),,(inf
),,(infv
)(\
)(\)(\
)(\
)(\)(\
)(\
)(\)(\
∑
∑
∑
∈
∈
∈
∈
∈
∈
+
+≥
≥≥
Ri
RSIRSi
RSIRSI
Si
RSIRSi
RSIRSI
RSi
RSIRSi
RSIRSI
xxxH
xxxH
xxxHRS
Xx
Xx
Xx
U
UU
U
UU
U
U
UU
U
Возьмем инфимум первого слагаемого по x
R
∈ X
R
, а инфимум второго по x
S
∈ X
S
. Тогда

Страницы