Составители:
Рубрика:
40 41
9
11.
, тоо
21.1
5
~
,,3
1
~
,,1
1.1
1
211
211
1
d
¯
®
v
uuK
uuK
u
.
Таким образом, ситуация
21
~
,
~
uu
NE.
Теорема 3.3. Пусть
lk
xxx ,...,,...,
0
– некоторый путь в игре
0
x
G
, игра
i
x
k
G
ni ,1
,
lk ,0
– АИ, где игрок i играет против всех, х,
k
i
xv
– ее
значение.
Пусть
li
xH
– выигрыш i-го игрока в окончательной позиции
l
x
.
Тогда, если имеет место
k
i
li
xvxH t
,
1,0 lk
, то существуетет
ситуация NE, в которой реализуется путь
lk
xxx ,...,,...,
0
с выигрышем
li
xH
.
Доказательство. Построим NE. Обозначим путь
l
xxZ ,...,
0
.
Мы должны построить стратегии во всех позициях игры
0
x
G
. Сначала
построим стратегию пути Z . Игрок i движется вдоль пути Z , следова-а-
тельно,
Zyu
i
,
i
XZy
,
ni ,1
.
Пусть теперь
Zy
,
i
Xy
(рис. 3.15). Тогда для любой точки y на
дереве существует наиболее близкий прообраз этой точки, который
принадлежит пути
Z
, т. е.
m
:
Z
m
y
*
1
, где де
m
– min.
i
Xy
k
Xy
ˆ
Рис. 3.15
Следовательно, существует точка
ZyXy
k
m
y
*
ˆ
,
ˆ
1
, в
y
ˆ
ходит k-й игрок. Следовательно, игрок k нарушил соглашение, и его
стратегия
yuyu
kk
ˆˆ
z
.
Если
k
i z
, то i -й игрок играет в игру у
k
y
G
ˆ
в составе группы игроков
^`
kN \
и его стратегия
yu
i
. Если
k
i
, то, как он играет, не имеет зна-
чения.
Докажем, что
n
uuu ,..,
1
– ситуация NE, т. е. выигрыш
lii
xHuK i
.
Рассмотрим ситуацию
ii
uuK ||
. Если i-й игрок отклонился
в той позиции, куда он никогда не попадет, то его отклонение не играет
никакой роли.
Если он отклонился от пути Z и первая позиции, где имеет место
отклонение,
Zy
ˆ
:
yuyu
ii
ˆˆ
z
, то рассмотрим подыгру у
y
G
ˆ
1
, где
происходит отклонение (если игрок отклонился, то он рассчитывает
на больший выигрыш), но максимальная величина, которую i игрок может
гарантировать себе в этой позиции,
yv
i
ˆ . Следовательно,
yvuuK
iii
ˆ
|| d
, но, если
lii
xHyv d
ˆ
, а
uKxH
ili
(выигрыш в конце пути, реализуемого в стратегиях
u
),
то
d uKuuK
iii
||
, ч. т. д.
Если существует траектория Z:
1
d
k
i
k
i
xvxv
1,0 lk
,
N
i
,
то в этой игре выполняются условия теоремы 3.3. Эти неравенства
означают, что выигрыши не убывают, следовательно,
lik
i
xHxv d
1
.
Если такой путь существует, то это NE.
Теорема 3.4. В любой конечной игре с ПИ всегда существует путь,
вдоль которого гарантированные выигрыши не убывают, т. е.
ixvxv
k
i
k
i
d
1
, а значит, существует ситуация NE.
Доказательство. Рассмотрим игру
0
x
G
и АИ
i
x
G
0
, где все игроки,
кроме i, играют против
i
-го игрока.
Обозначим через
$
0
~
x
i
u
оптимальную стратегию
i
-го игрока в АИ
i
x
G
0
. Строим ситуацию
}{
0
0
2
0
1
~
,,
~
,
~
~
x
n
xx
uuuu
, т. е. каждый играет
так, как если бы все играли против него.
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
