Теория игр. Часть 2. Кооперативные игры и игры в позиционной форме. Григорьева К.В. - 50 стр.

UptoLike

ВУЗ: 

СПбГАСУ | Санкт-Петербург

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

Рубрика: 

98 99
Таблица 2
The strategies
of coalition S
The strategies
of coalition N \ S



Si
i
m
S
m
S
m
xxxx
S
столбцовКоличество
,,,,
1
1
11
1
^`

^`
SNS
NS
NSi
Ni
j
j
xxK
xxK
\
11
1
:1
11
1
,,
,,
……
…… …


°
¯
°
®
NS
m
N
m
S
NS
SNi
i
xx
xx
m
,,
,,
строк
чество
-Коли
1
1
11
1
\
……
^`

^`
SNS
m
N
m
S
NSi
m
N
m
i
j
N
j
N
xxK
xxK
\
1
:1
1
,,
,,
1
1
.
Эта матрица имеет размерность
u
Si
i
S
N
i
i
mm
\
.
Требуется найти оптимальный выигрыш для каждого игрока из этих
коалиций и в некотором смысле оптимальные стратегии коалиций.
Алгоритм решения задачи
1. Решим коалиционную игру, т. е. найдем ситуацию равновесия
по Нэшу (NE) в смешанных стратегиях, используя следующую далее те-
орему 1 [9].
Теорема 1. Пусть

BAG ,
– биматричная

mm u
-игра и матрицы
А, В – невырожденные. Если игра

BAG ,
имеет вполне смешанную
ситуацию равновесия, то она единственная и вычисляется по формулам
,;
1
1
1
2
uAvyuBvx
где

.1,,1;1;1
1
2
1
1
uuuBvuuAv
Обратно, если для векторов
m
Ryx ,
, определяемых равенствами
,,
1
1
1
2
uAvyuBvx
справедливо
0,0 tt yx
, то пара

yx,
образуетует
NE в смешанных стратегиях в игре

BAG ,
с вектором равновесных вы-
игрышей

21
,vv
.
Будем рассматривать тот случай, когда матрицы из табл. 1–2






,
,,,,,,,,,,
,,,,,,,,,,
~
,
,,,,,,,,,,
,,,,,,,,,,
~
1
11
1
11
1
1
1
1
11
1
1
11
1
11
1
1
11
1
11
1
1
1
1
11
1
1
11
1
11
1
111
1
1
11
1
¸
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
¨
©
§
¸
¸
¸
¸
¸
¸
¹
·
¨
¨
¨
¨
¨
¨
©
§
¦¦
¦¦
¦¦
¦¦
N
Si
m
N
m
S
m
S
m
i
N
Si
NS
m
S
m
i
N
Si
m
N
m
S
Si
N
Si
NSSi
S
i
m
N
m
S
m
S
m
i
S
i
NS
m
S
m
i
S
i
m
N
m
S
Si
S
i
NSSi
NSSS
NS
NSSS
NS
xxxxKxxxxK
xxxxKxxxxK
B
xxxxKxxxxK
xxxxKxxxxK
A
u
S
N
i
i
Si
i
mmBA
\
,
~
dim
~
dim
можно свести к квадратным матрицам
A
и B таким, что о
,0det zA
0
d
et zB
.
Ситуаций NE в игре может быть много [10], тогда решение коали-
ционной игры определяется неоднозначно.
2. Вычислим значение игры в смешанных стратегиях в ситуации
NE:

>@
SNvSvyxE \,,
,
где

,\;
\\
¦¦¦¦

K[ K[
SSNSSN
XiXj
jiij
XiXj
jiij
bSNvaSv
^`
,
S
Xi
i
x
[
^`
.
\SN
Xj
j
y
K
Можно показать, что

,
¦
t
Si
i
vSv
где
i
v
– максималь-ль-
ный гарантированный выигрыш i-го игрока,
S
i
, при условии, что иг-
роки из коалиции
S
N
\
используют смешанную стратегию в ситуации
NE. Это следует из леммы о супераддитивности характеристической
функции, определенной как максимальный гарантированный выигрыш
коалиции S.

Страницы