Составители:
Рубрика:
24 25
Занятие № 3. АНТАГОНИЧЕСКИЕ ИГРЫ (АИ) С ПИ.
СТРАТЕГИИ НАКАЗАНИЯ
3.1. АНТАГОНИЧЕСКИЕ ИГРЫ С ПИ
Определение 3.1. Многошаговой АИ с ПИ называется многоша-
говая игра двух лиц с ПИ на древовидном графе
FX ,Г
^`
,,,,,2,1
2121
HHUUNG
где
xHxH
12
для всех
3
Xx
;
3
X
– множество окончательных
позиций.
Замечание 3.1. Из условия
xHxH
12
следует, чтоо
211212
,, uuKuuK
для всех
11
Uu
,
22
Uu
. Этим свойством обла-ла-
дают и все подыгры
z
G
игры G.
Определение 3.2. Пара
*
2
*
1
, uu
, для которой выполняются нера-
венства
2
*
11
*
2
*
11
*
211
,,, uuKuuKuuK dd
для всех
11
Uu
,
22
Uu
, на-
зывается ситуацией NE или седловой точкой, а стратегии, образующие
ситуацию равновесия, оптимальными.
Определение 3.3. Значение функции выигрыша v в ситуации рав-
новесия называется значением игры G.
Из теоремы 2.1 следует, что в многошаговой АИ с ПИ на конечном
древовидном графе существует ситуация абсолютного равновесия, т. е.
такая ситуация
*
2
*
1
, uu
, сужение которой на любую подыгру
z
G
игры G
образует в
z
G
ситуацию равновесия.
Определение 3.4. Число
yv
, представляющее собой значение
функции выигрыша в ситуации равновесия подыгры
y
G
, называется зна-
чением подыгры
y
G
.
Утверждение 3.1. Для любой подыгры
z
G
можно определить
ее значение
zv
.
Определение 3.5. Значением АИ
yv
называется значение функ-
ции выигрыша игрока 1 в ситуации равновесия.
Утверждение 3.2. Значение АИ
yv
определяется единственным
образом для всех
1
Xy
,
2
Xy
и является однозначной функцией.
Доказательство. Выведем функциональные уравнения для вычис-
ления функции
yv
. Из определения
yv
следует, чтоо
¸
¹
·
¨
©
§
¸
¹
·
¨
©
§
yy
y
yy
y
uuKuuKyv
*
2
*
1
2
*
2
*
1
1
,,
,
где
¸
¹
·
¨
©
§
yy
uu
*
2
*
1
,
– ситуация равновесия в подыгре
y
G
, являющаяся
сужением ситуации абсолютного равновесия
*
2
*
1
, uu
.
Пусть
1
Xy
и
y
Fz
. Тогда (рис. 3.1) имеем
zvuuKyv
yy
Fz
zz
z
Fz
¸
¹
·
¨
©
§
max,max
*
2
*
11
. (3.1)
3
y
v
3
2
z
v
2
1
z
v
¸
¸
¹
·
¨
¨
©
§
2
2
¸
¸
¹
·
¨
¨
©
§
1
1
¸
¸
¹
·
¨
¨
©
§
1
1
¸
¸
¹
·
¨
¨
©
§
3
3
Рис. 3.1
Для
2
Xy
(рис. 3.2) аналогично получаем
.minmax
,max,
*
2
*
12
*
2
*
1
2
zvzv
uuKuuKyv
y
y
y
Fz
Fz
zz
z
Fz
yy
y
¸
¹
·
¨
©
§
¸
¹
·
¨
©
§
(3.2)
Действительно, если
1
Xy
, то игрок 1 (максимизирующий) дол-
жен выбрать в точке вершину
y
Fz
, для которой значение следующей
подыгры максимально. Если же
2
Xy
, то игрок 2 (минимизирующий)
должен выбрать позицию
y
Fz
, для которой значение следующей по-
дыгры минимально.
Из (3.1), (3.2) и определения 3.5 (рис. 3.3) окончательно имеем
,,max
1
Xyzvyv
y
Fz
(3.3)
.,min
2
Xyzvyv
y
Fz
(3.4)
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
