Бескоалиционные игры в нормальной форме. Часть 1. Григорьева К.В. - 8 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

14 15
v
ji
j
ij
j
i
=a=
ú
û
ù
ê
ë
é
a
0
minminmax
,
где
v
– нижнее значение игры (нижняя цена игры).
Определение 2.7. Стратегия
0
i
называется максминной страте-
гией первого игрока.
Пусть теперь второй игрок выбрал
j
-й столбец и уверен, что он
проиграет не больше, чем
ij
i
a
max
. Естественно выбрать такую стратегию
j
, при которой этот максимальный проигрыш минимален, т. е. выбрать
такой столбец
0
j
, который минимизирует его проигрыш:
0
maxmaxmin
ij
i
ij
i
j
v a=
ú
û
ù
ê
ë
é
a=
,
где
v
– верхнее значение игры (верхняя цена игры).
Определение 2.8. Стратегия
0
j
называется минимаксной страте-
гией второго игрока.
Таким образом, минимакс и максмин для игры
A
G
могут быть
найдены по схеме, представленной на рис. 2.1.
Пример 2.3. Так, в игре с матрицей из примера 2.2 нижнее значение
(максмин)
v
и максминная стратегия
0
i
первого игрока а
3
=
v
,
2
0
=
i
,
а верхнее значение (минимакс)
v
и минимаксная стратегия j
0
второгоо
игрока –
3
=
v
,
2
0
j
. А в игре с матрицей
(
)
()
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
--
-
/
-
/
-
/
/
/
0642
1107
5510
0
1
1
5647
максминная стратегия первого игрока –
3
0
=
i
, нижнее значение игры –
0
v
; минимаксная стратегия второго игрока –
2
0
=
j
, верхнее значение
игры
4
v
.
v
v
ij
j
i
mj
j
j
j
j
j
mnmm
n
n
ij
i
j
in
i
i
i
i
i
=a
ï
ï
þ
ï
ï
ý
ü
a
a
a
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ë
é
aaa
aaa
aaa
a
aaa
minmax
min
min
min
maxmin
maxmaxmax
2
1
21
22221
11211
21
K
K
KKKK
K
K
444444 8444444 76
K
Рис. 2.1. Схема нахождения максмина и минимакса для игры G
A
Лемма 2.1. В антагонистической игре
A
G
vv
.
Теорема 2.1. Для того чтобы в
(
)
nm
´
-МИ
A
G
существовалала
ситуация равновесия, необходимо и достаточно, чтобы
vv
=
, при этомм
максминная и минимаксная стратегия
(
)
00
, ji
образует ситуацию
равновесия.
Определение 2.9. Игры, в которых существуют ситуации равнове-
сия, называются вполне определенными.
Поэтому данная теорема устанавливает критерий вполне опреде-
ленной игры и может быть переформулирована следующим образом.
Теорема 2.2. Для того чтобы игра была вполне определена,
необходимо и достаточно, чтобы существовали минимакс и максмин
и выполнялось равенство
vv
=
.
Замечание 2.1. Заметим, что в
(
)
nm
´
-МИ
A
G
экстремумы, т. е.
минимакс и максмин достигаются всегда, а вот ситуация, в которой
максимальный элемент по столбцу и минимальный элемент по строке
равны, очень редка. См. пример 2.3, где есть максминная и минимаксная
стратегии, а ситуации равновесия нет и, соответственно, значения игры
тоже нет.
Пример 2.4. Так, в игре с матрицей
(
)
()()
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-- 720
432
141
2
2
1
742

Страницы