Составители:
Рубрика:
12 13
Пример 2.1. Орел и решка. В этой игре каждый из двух игроков
выбирает независимо друг от друга монетку, повернутую вверх либо
«орлом», либо «решкой». Если выбор игроков различен, то игрок 2 пла-
тит игроку 1 один доллар. Если выбор совпадает, то – наоборот. Матри-
ца выигрышей такой игры:
( ) ( )
( ) ( )
÷
÷
ø
ö
ç
ç
è
æ
--
--
1,11,1
1,11,1
р
о
ро
.
Определение 2.3. Конечная антагонистическая игра
A
G
называется
матричной (МИ), поскольку выигрыши игроков полностью задаются
матрицей
A
выигрышей первого игрока.
Рассмотрим вопрос об оптимальном поведении игроков в антаго-
нистической игре
A
G
. Напомним, что естественно в этой игре считать
оптимальной такую ситуацию
(
)
2
1
2
1
, XXxx
´
Î
, отт которой ни одному
из игроков невыгодно отклоняться. Такая ситуация
(
)
2
1
, xx
называется
равновесной, а принцип оптимальности, основанный на построении
равновесной ситуации, – принципом равновесия. Ниже будет показано,
что для антагонистических игр принцип равновесия эквивалентен
принципам минимакса и максмина. Разумеется, для этого необходимо
существование равновесия, т. е. чтобы принцип оптимальности был
реализуем.
Перепишем определение равновесия по Нэшу для антагонистичес-
кой игры:
(
)
(
)
( ) ( )
.,;,
;,;,
,,
212
,
211
,,
212
,
211
jijiji
jijiji
xxKxxK
xxKxxK
a-=b=a=
a
-
=
b
=
a
=
Откуда следует, что
(
)
(
)
( ) ( )
.,
;,,
;,,
,,,
2
,
212
,
212
1
,
211
,
211
Xji
XjxxKxxK
XixxKxxK
jijiji
jiji
jiji
Î"a£a£a
Î"a-=³a-=
Î
"
a
=
³
a
=
Определение 2.4. В антагонистической игре
A
G
ситуация
(
)
ji ,
называется ситуацией равновесия или седловой точкой, если
.,
,,,
Xji
jijiji
Î
"
a
£
a
£
a
В седловой точке элемент матрицы
ji ,
a
является одновременно
минимумом в своей строке и максимумом в своем столбце.
Пример 2.2. В игре с матрицей
(
)
() ()
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
106
835
401
0
3
0
836
ситуация
(
)
2,2
является равновесной.
Определение 2.5. Стратегия
i
или
j
, входящая в ситуацию равн-
овесия, называется оптимальной стратегией 1-го или 2-го игрока.
Определение 2.6. Значение функции выигрыша в ситуации
равновесия
v
ji
=
a
,
называется значением игры.
2.2. Принцип максмина и минимакса
Установим связь между принципом равновесия и принципами ми-
нимакса и максмина в антагонистической игре. Пусть дана МИ с мат-
рицей
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
aa
a
a
=
mnm
n
A
K
KKK
K
1
111
,
которая полностью определяет выигрыши игроков.
Первый выбирает строку i, второй – столбец
j
. Выигрыш первогоо
игрока стоит на пересечении i-й строки и
j
-го столбца. Эта же величина
есть проигрыш или выигрыш с обратным знаком второго игрока.
Итак, первый игрок произвольно выбрал стратегию i. В каком
выигрыше он может быть уверен? В минимальном, естественно, т. е.
минимальное значение выигрыша
ij
j
a
min
при выбранной стратегии i
ему обеспечено. Естественно выбрать такую стратегию i, при которой
этот минимум максимален, т. е. естественно выбрать
0
i
, при которой
достигается
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
