Составители:
Рубрика:
16 17
Занятие № 2. АБСОЛЮТНОЕ РАВНОВЕСИЕ ПО НЭШУ
2.1. АБСОЛЮТНОЕ РАВН ОВЕСИЕ ПО НЭШУ
Определение 2.1. Ситуация
xuxuxuxu
ni
,...,,...,
1
называ-
ется равновесной по Нэшу (NE – Nash Equilibrium), если
,,,
iiiii
UxuNixuxuKxuK t
где
.,...,,...,
1
xuxuxuxuxu
nii
Определение 2.2. В игре с нулевой суммой ситуация NE называет-
ся ситуацией равновесия.
Замечание 2.1. В дальнейшем в тексте будет использоваться обо-
значение NE в качестве равновесной ситуации во всех рассматриваемых
играх.
Для многошаговых игр можно усилить понятие равновесия.
Определение 2.3. Ситуация равновесия называется абсолютно
равновесной, если ее усечение в любой подыгре
x
G
является ситуацией
равновесия в этой подыгре.
Определение 2.4. Ситуация равновесия по Нэшу
**
1
*
...,,
n
uuu
называется ситуацией абсолютного NE в игре G, если для любого
X
z
ситуация
¸
¹
·
¨
©
§
z
n
zz
uuu
**
1
*
...,,
, где
z
i
u
*
– сужение стратегии
*
i
u
на по-
дыгру
z
G
, является ситуацией NE в подыгре
z
G
.
Не все ситуации равновесия обладают этим свойством. Однако имеет
место основная теорема.
Теорема 2.1. В любой многошаговой игре с ПИ на конечном древо-
видном графе существует ситуация абсолютного NE.
Доказательство. Докажем по индукции по длине игры l.
Пусть
1
l
(рис. 2.1). Предположим, что
i
Xx
– множеству оче-
редностей i-го игрока. Игрок
i выбирает альтернативу в вершине x
из условия максимизации своего выигрыша
yHyH
i
Fy
i
x
max
. Игроки
получают
yHyHyH
ni
,,,,
1
соответственно. Если i -й игрок от-т-
клонится, он получит меньше, следовательно, он будет действовать со-
гласно стратегии, образующей абсолютное NE.
Предположим теперь, что теорема справедлива для всех игр, таких,
что длина каждой из них не превосходит
1
l
.
Докажем, что ситуация равновесия существует для игры G длины l.
x
Рис. 2.1
Так как подыгры
skG
k
z
,1,
,
0
xk
Fz
(рис. 2.2), имеют длину
не более
1
l
, то по индукционному предположению теорема спра-
ведлива, следовательно, существует ситуация абсолютного NE
»
¼
º
«
¬
ª
kkk
z
n
zz
uuu
**
1
*
,...,
.
0
0 i
Xx
< l
s
z
G
2
z
G
1
z
G
< l
< l
Рис. 2.2
Пусть
*
0
*
1
zxu
i
, где
*
z
:
»
¼
º
«
¬
ª
»
¼
º
«
¬
ª
k
k
xk
z
z
i
Fz
z
z
i
uKuK
*
*
**
1
0
1
max
.
И пусть в точке
*
z
ходит игрок
1
: iii z . Тогда игра G переходит
в подыгру
*
z
G
. Но в подыгре
*
z
G
каждый i-й игрок получает выигрыш
*z
i
K
, соответствующий ситуации NE
*
*
z
u
. Поскольку у
*
*
z
i
u
– сужение
стратегии
*
i
u
на множество
zi
XX
, то выигрыш i-го игрока в ситуации
*
u
игры G равен выигрышу в ситуации
*
*
z
u
:
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
