Петросян Л.А. и др. Теория игр
Подождите немного. Документ загружается.
рышей
A
x
=
{v[T
x
(a, Д)]}. Пусть ft (х) =
{Ь{
(х,
а)}, #,(*) =
=
{Ь'
ц
(х,
/?)} — оптимальные смешанные стратегии в игре с мат-
рицей А
х
. Тогда имеет место следующая теорема о структуре оп-
тимальных стратегий в игре Г
х
.
Теорема. В игре Г
оптимальная
стратегия
поведения
игрока
1 в точке х
(каждое информационное множество
игрока 1 в игре
Г
состоит
из
одной позиции
хеХ
г
)
предписывает каждой
альтер-
нативе а
вероятность
в
соответствии
со
смешанной оптимальной
стратегией игрока
1 в
матричной игре
А
х
, т. е.
b
t
(x, a)
=
bf(x, a).
Оптимальная стратегия поведения
{Ь
2
(Х{,
/?} игрока 2 в игре
Г
предписывает каждой альтернативе
ft
вероятность
в
соответст-
вии
с
оптимальной смешанной стратегией игрока
2 в
игре с матрицей
А
х
,
т. е.
где x=F~\
если
уеХ{.
Значение игры удовлетворяет следующему функциональному
ура-
внению:
v(x)=Vtd{v[T
x
(a,P)]}*xeXi, (9-1)
с
граничным условием
•
(*W,=#(x).
(9-2)
(Здесь Val A — значение игры с матрицей А).
Доказательство проводится по индукции и вполне аналогично
доказательству теоремы п. 2.1.
9.2.
Пример 11. (Игра
инспектирования).
Игрок Е (нарушитель)
хочет совершить некоторое запрещенное действие. Имеется N пери-
одов времени, в которые это действие может быть осуществлено.
Игрок Р (инспектор), желающий предотвратить это действие, мо-
жет провести только одну инспекцию в любой из этих периодов
времени. Выигрыш игрока Е равен 1, если запрещенное действие
произошло и осталось необнаруженным, и равен
(—
1),
если наруши-
тель пойман (это будет в том случае, когда для совершения дейст-
вия он выбирает тот же самый период времени, что и инспектор для
проверки); выигрыш равен нулю, если нарушитель не действует
вовсе. Обозначим такую iV-шаговую игру через Гц.
В первом периоде (на 1-м шаге) каждый игрок имеет две альтер-
нативы. Игрок Е может предпринимать действие или не предприни-
мать его; игрок Р может инспектировать или не инспектировать.
Если игрок Е действует и игрок Р инспектирует, то игра заканчива-
220
ется и выигрыш равен
—
1.
Если игрок Е действует, а игрок Р не
инспектирует, то игра заканчивается и выигрыш равен 1. Если игрок
Е не действует, а игрок Р инспектирует, то игрок Е может пред-
принять действие в следующий период времени (в предположении,
что N>
1)
и выигрыш также равен 1. Если игрок Е не действует
и игрок Р не инспектирует, то переходят к следующему шагу игры,
который отличается от предыдущего только тем, что до конца игры
остается меньшее число периодов времени, т. е. попадают в подыг-
ру T
N
_
l
. Следовательно, матрица для 1-го шага игры выглядит
следующим образом:
_1
" ' (9.3)
1_
1
%-J'
1
Уравнение (9.1) в этом случае принимает вид
%=Va
'["i
«!-,}
(9А)
Здесь
v (х)
одинаково для всех позиций игры одного уровня и поэто-
му зависит только от числа периодов до конца игры. Поэтому
вместо v(x) записано v
N
. Далее будет показано, что v
N
_
t
<
1,
следо-
вательно, матрица в (9.4) не имеет седловой точки, т. е. игра
с матрицей (9.4) является вполне смешанной. Отсюда получаем (см.
п. 9.1 гл. I) рекуррентное уравнение
V
N
=
—> (
9
-
5
)
которое вместе с начальным условием
-^
ш
(~1 S)-°
(9
-
6)
определяет v
N
. Преобразуем уравнение (9.5) с помощью подстанов-
1 „ 1
ки t
N
= . Получим новое рекуррентное уравнение
t
N
=t
N
_
1
—,
»„-1 2
t
l
—
—
l. Это уравнение имеет очевидное решение t
N
= — (N+l)/2,
откуда имеем
Теперь можно вычислить оптимальные стратегии поведения на
каждом шаге игры. Действительно, матрица игры (9.4) принимает
вид
Г-1 1 1
„, ,.,„ , оптимальные стратегии поведения таковы:
|_ 1 (N-2)/N J
221
\JV+1 ЛГ+1/ \JV+1 JV+1/
Пример 12.
(Теоретико-игровые особенности оптимального
рас-
хода
ресурса).
Пусть первоначально игроки 1 и 2 имеют соответст-
венно г ъ R—r единиц некоторого ресурса, а также по две чистые
стратегии. Допустим, что если игроки выберут одинаковые по
номеру чистые стратегии, то ресурс игрока 2 уменьшится на еди-
ницу. Если же игроки выберут разные по номеру чистые стратегии,
то на единицу уменьшится ресурс игрока 1. Игра заканчивается
после того, как ресурс одного из игроков станет равным нулю. При
этом игрок 1 получает выигрыш, равный 1, если ресурс игрока
2 станет равным нулю, и выигрыш
—
1,
если станет равным нулю
его собственные ресурс.
Обозначим через T
kl
многошаговую игру, в которой игрок
1 имеет k(k=\, 2, ..., г) единиц, а игрок 2 —
1(1=1,
..., R—r) единиц
ресурса. Тогда
rvairv,.,, VallV.n
Vair
t/
=Val
L
Valr
*-u
v
air*.,_iJ'
гдеУа1Г
к
.
0
=1,Уа1Г
м
=-1.
Рассмотрим 1-й от конца шаг, т. е. когда у обоих игроков
осталось по одной единице ресурсов. Очевидно, что на этом шаге
г Г
1
"
Г
разыгрывается следующая матричная игра: r^i =
I
Игра Г
и
является симметричной, ее значение, которое мы обозна-
чим через «]
>ь
равно нулю, а оптимальные стратегии игроков со-
впадают и равны (1/2, 1/2).
На 2-м от конца шаге, т. е. когда у игроков осталось три
единицы ресурсов, разыгрывается одна из двух матричных игр
Г^ или
Г
2>
1.
При этом
e,
2
=Vair,,=Val
-1 щ
Л
\~^~~~2'
1
Vl,1
l_
,
'
I
.i+
1
_
1
_«U
1_Г~~2'
«2,,=Уа1Г2,,
= Уа1
На 3-м от конца шаге (т. е. когда у игроков имеется в общей
сложности четыре единицы ресурса) разыгрывается одна из следу-
222
юших трех
игр:
Г
13
, T
w
,
Г
3
,1.
При
этом
х/
IT-
л! t[
Vl
* ~П "U-1 3
»
w
=Vair
u
=Val =^-—=--,
L-l «,J
2 4
[
«2,1 «1,2*1
«U «2,lJ
.«2,1
U
„
w
=Vair
wS
=Val|
1-^-0.
«
3
,i=Vair
3
,,=Val
«2,1 +
1
_3
2
4'
Продолжая аналогичные вычисления далее
до
iV-ro шага
от
конца, получим следующее выражение для значения исходной игры:
«г.Д-r-l «Г-1.Я-Л
•,.*_,=Vair
r
.,_,=Val
J>r-l,R-r «г.Л-г-lj
В силу симметричности матрицы выигрышей игры
T
rR
_
r
имеем
1
,
ч
V
r
.R-r~-
K
v
r.R-r-l+
v
r-l,R-r),
оптимальные стратегии поведения игроков
на
каждом шаге
со-
впадают
и
равны (1
/2, 1/2).
Пример
13. В
шуточной игре играют
две
команды: игрок
1 (m
t
женщин
и т
2
кошек); игрок
2
(п
1
мышей
и и
2
мужчин).
На
каждом
шаге каждый
из
игроков выбирает своего представителя. Один
из
двух выбранных представителей «устраняется» согласно следу-
ющим правилам: женщина «устраняет» мужчину; мужчина «устра-
няет» кошку; кошка «устраняет» мышь; мышь «устраняет» жен-
щину. Игра продолжается
до тех пор,
пока
в
одной
из
групп
не
останутся игроки только одного типа. Когда группа
не
имеет
больше выбора, другая группа, очевидно, выигрывает.
Обозначим значение исходной игры
v{m
v
m
2
, п
1
, п
2
).
Будем
полагать
v(m
lt
m
2
, n
v
0)=v(m
v
m
2
, 0,
л
2
)=1,
если
m
lt
m
2
>0, ,д
„..
v(m
lt
0, л
1(
n
2
)=v(Q,
m
2
, n
v
п
2
)=
—
1,
если
n
v
и
2
>0.
Введем следующие обозначения: «(/«i
—
!)=«(»»!
—
1,
т
2
, n
v
n
2
),
v(m
2
—\)=v(m
i
, т
2
—
\, и
1(
п
2
), v(n
l
—
l)=v(m
1
,
m
2
,
п^
—
Х,
п
2
),
»=(и
2
— \)=v(m
l
,
m
2
, n
lt
л
2
—
1).
Согласно теореме
п. 9.1
справед-
ливо соотношение
223
v(m
v
m
2
, n
v
n
2
)=Val
LflOij-l) e(m
2
-
-1)"
1).
Можно показать, что рассматриваемая игра является вполне сме-
шанной. Согласно теореме п. 9.1 гл. I имеем
v(m,-l) «(/w^-lJ-tKnj-l) «(л
2
-1)
ю(т
1(
m
2
, n^ n
2
)=-
»(/«!—1)+«(да
2
—!)—«(«!
—l)—«(n
2
—
l)
Учитывая граничные условия (9.8), отсюда получаем
»(»»!-
1)+1
e(m
lf
1, 1, 1) =
-«(л^-Ц+З
и v(l, 1, 1, 1)=0. Но эти уравнения совпадают с уравнениями (9.5),
(9.6),
следовательно, v(m, 1, 1, l)=(m
—
1)/(/и+1) и оптимальные
стратегии в этом случае также совпадают с приведенными в приме-
ре 11.
Упражнения
и
задачи
1.
Найти все ситуации абсолютного равновесия по Нэшу в примере 4 п. 2.2.
2.
Доказать, что в неантагонистической конечно-шаговой
игре
двух
лиц с
полной
информацией выигрыши во всех «благожелательных» (неблагожелательных) ситу-
ациях равновесия по Нэшу равны между собой.
3.
Пусть v
1
(x), v
2
(x), ...,
v„(x)
— значения функций выигрыша игроков 1, 2, ...,
л в подыгре Г
х
в ситуации абсолютного равновесия в игре Г.
а) Показать, что функции
i>,-(дс),
i=\,
2,...,
н, удовлетворяют следующей системе
функциональных уравнений:
«i(x)=
max »,(JO. xeXu i=l,
2,...,
л, (ЮЛ)
х!еГ
х
при граничном условии
«.•(*W„
+1
=#<(*)•
(Ю-2)
б) Привести пример игры, в которой выигрыши игроков в ситуации равновесия
в стратегиях наказания не удовлетворяют системе функциональных уравнений (10.1)
при граничном условии (10.2).
4.
Построить пример неантагонистической многошаговой игры
двух
лиц,
в кото-
рой в ситуации равновесия в «стратегиях наказания» наказывающий игрок при
наказании противника за отклонение от выбранного пути еще сильнее наказывает
самого себя.
5.
Построить Парето-оптимальные множества в игре из примера 4 п. 2.2.
6. Построить пример многошаговой неантагонистической игры, в которой ни
одна из ситуаций равновесия по Нэшу не приводит к Парето-оптимальному реше-
нию.
7.
Построить отображение
Т,
которое каждой подыгре Г, игры Г ставит в соот-
ветствие некоторое подмножество ситуаций U
z
в эгой подыгре. Пусть
Г(Г)=1/
Х1)
.
224
Будем говорить, что отображение Т динамически устойчиво, если из
и (
)
б
U
Xo
~к
-к zb 2
следует, что и
()eU
:k
,
где и ()={и
1
(•), ..., и„
к
()) —сужение ситуации и{) на
подагру Г
:к
,
со
0
=
{х
0
, z
lt
.... z^} — партия, реализовавшаяся в ситуации
u()eU
Xo
.
Показать, что если отображения Т каждой подыгре Г
1к
ставит в соответствие
множество Парето-оптимальных ситуаций I/', то оно динамически устойчиво.
8. Отображение Т, определенное в упр. 7, называется сильнодинамически устой-
чивым, если для любой ситуации
и
(•)
е
U
Xo
,
любого z* e
{z,}
= ш, где
{z,}
=
<о
— партия
в ситуации
и (•),
ситуации й
(•)
е U
Zk
существует ситуация
й
(•)
б
U
Xa
, для которой
z
k
ситуация и (•) является ее сужением на позициях подыгры Г-
к
и позиция
z*
возможна
в ситуации й(-).
Показать, что если отображение Т каждой подыгре Г,
к
ставит в соответствие
множество ситуаций равновесия по Нашу, то оно сильнодинамически устойчиво.
9. Построить пример, когда отображение Т, ставящее в соответствие каждой
подыгре
Г%
множество Парето-оптимальных ситуаций равновесия, сильнодинамичес-
ки устойчивым не является.
10.
Для каждой подыгры Г, введем в рассмотрение величины v
({/},
z),
i = 1,..., п,
представляющие собой гарантированный выигрыш 1-го игрока в подыгре Г%, т. е.
v
({/},
z) — значение антагонистической игры, построенной на графе подыгры
Г\ между игроком i и игроками N\i, действующими как один игрок. При этом
множество стратегий коалиции игроков N\ i есть декартово произведение множества
стратегий каждого из игроков ke{N\i}, и^е [\
и
и функция выигрыша игрока
/ в ситуации
(UJ,
и^,) определяется как Н](щ, и^), а функция выигрыша коалиции
N\i
полагается равной — Н](щ,
«AT\I)-
Построить функции
i»({i'},
z) для всех подыгр Г
г
из примера 4 п. 2.2.
11.
Показать, что если в некоторой многошаговой неантагонистической игре
Г с неотрицательными выигрышами (Я,->0, i=l, ..., и)
»({/},
z)
=
0
для всех /=1, ...
л
..., л и ze [J X
h
то любая партия может быть реализована в некоторой ситуации
i=i
равновесия в стратегиях наказания.
12.
Формализовать fc-уровневую древовидную систему управления в виде иерар-
хической игры, в которой управляющий центр, находящийся на /-м уровне (i=
1
к~\),
распределяет ресурсы между подчиненными ему управляющими центрами
следующего уровня при /<fc—1 и между подчиненными ему производственными
подразделениями при i=k—l. Выигрыш каждого производственного подразделения
зависит только от своего производства, а выигрыш управляющих центров — от
подчиненных им производственных подразделений.
13.
Найти ситуацию равновесия по Нэшу в построенной в упр. 12 fc-уровневой
иерархической древовидной игре.
14.
Показать, что вектор выигрышей a =
{JJ(JV),
0, ..., 0} принадлежит С-ядру
двухуровневой иерархической древовидной игры с характеристической функцией
«(5).
Показать, что ситуация равновесия, построенная в двухуровневой древовидной
иерархической игре, является также ситуацией сильного равновесия.
15.
В ромбовидной иерархической игре построить характеристическую функцию,
используя ситуацию равновесия по Нэшу.
16.
Описать множество всех ситуаций равновесия по Нэшу в двухуровневой
225
древовидной иерархической игре. Учесть возможность «наказания» центра А
0
игро-
ками
5,, ...,
В„ (например, прекращение выпуска продукции при распределении
ресурсов, не отвечающих интересам игрока i).
17.
Построить матрицу выигрышей игроков
в
игре примера
б п.
7.1. Найти
оптимальные чистые стратегии и значение получившейся матричной игры.
18.
Привести к матричной форме и решить игру из примера 8 п. 7.1.
19.
Рассмотрим следующую антагонистическую многошаговую игру
с
задерж-
кой информации о местоположении одного из игроков. Имеются два
игрока:
мишень
Е
и
стрелок Р. Мишень может двигаться только по точкам оси Ох с координатами
О,
1,2,...,
причем если игрок Е находится в точке i, то в следующий момент времени он
может переместиться только
в
точки i+1, i—1 или остаться
на
месте. Стрелок
Р имеет
j
патронов, У=0,
1, ..., и
может производить не более одного выстрела
в каждый момент времени. Считается, что стрелок попадает в ту точку,
в
которую
целится.
В каждый момент времени игрок Р знает только точное местоположение игрока
Е на предыдущем шаге,
т. е.
если Е находился на предыдущем шаге в точке
i, то
игроку
Р
необходимо целиться
в
точки i+1,
i и
i—
1.
Игрок
Е
знает количество
патронов, которые имеет игрок
Р в
каждый момент времени,
но не
знает, куда
целится игрок
Р.
Выигрыш стрелка
Р
равен числу попаданий
в
мишень. Таким
образом, цель стрелка
Р
— максимизировать количество попаданий в мишень Е до
того,
как она достигнет «бункера». Цель мишени противоположна. Здесь под «бун-
кером» понимается точка О, в которой мишень недостижима для стрелка Р.
Обозначим символом Г(,/> описанную выше игру при условии, что мишень
Е
в
начальный момент времени находилась в точке с координатой i, а стрелок Р имел
j патронов. Символом
«
(i,
J) обозначим значение игры Гу (если оно существует).
Нетрудно заметить, 4TO«(i, 0)=0, i=l, 2
v=(l,j)=0,j=l,
2 На каждом шаге
игры Г
|>7
, i=2,
3
у=1,
2
стрелок имеет четыре стратегии (на самом деле
больше, но они неразумны), а игрок Е — три стратегии. Стратегии стрелка Р таковы:
выстрелить в точку
i—
1,
выстрелить в точку
i,
выстрелить в точку i+1, не стрелять
на данном шаге. Стратегии мишени: передвинуться в точку
i—
1,
оставаться
в
точке i,
передвинуться
в
точку i+1. Следовательно, на каждом шаге игры разыгрывается
матричная игра с матрицей выигрышей
"
1
+«
(i-1,
j-1)
«
(i,
j-1)
•
(i+1,
j-1) "
»(i-l, 7-1) l+t>(i,7'-l) «(i+1,7-1)
«(i-1,
7-1) «(i.7'-l)
1
+«(i+1, 7-1)
«0-1,7) «(i,7) «(i+1, J)
.
Символами *! (i, j), x
2
(i, j), x
3
(i,
J),
x^
(i,
j)
обозначим вероятности,
с
которыми
стрелок
Р
использует свои
1, 2, 3 и
4-ю стратегии,
а
символами
y^i, j),
y
2
(i,
j),
Уз&Л — вероятности, с которыми мишень Е использует свою 1, 2, и 3-ю стратегии
(стратегии поведения игроков
Р
и Е соответственно есть функции информационных
множеств {i,7'})-
а) Показать, что значение игры «(i,
j) и
оптимальные стратегии поведения
стрелка Р (x
t
(i,
f),
x
2
(i,
J),
x
3
(i,
J),
x
A
(i,
7))
и мишени Е (у,
(i,
j),
y
2
(i,
7),
^3
('. Л) связаны
между собой следующими соотношениями:
(l+»(i-l,7-l))x
1
+»(i-l,7'-l)x
2
+»(i-l,7-l)*s+»(»-l,;')**>«0'.A
«(i,7'-l) *j + (l+«(i,7"-l)) *2+«(i.7'-l) x
a
+v(i,j)
x^v{i,J),
«(i+l,7'-l)x
1
+«(i+l,7-l)x
2
+(l+«(i+l
>
7'-l))x3-t-«(' + l.
J
/)^>«('.7).
x
l
+x
2
+x
3
+x
4
.
= l,
X!>0, x
2
>0,
x
3
>0,
x
A
^0;
(l+v(i-l,j-l))
yi
+v(i,j-l) y
2
+v(i+l,j-l)
y
3
^v(i,j),
226
v(i-l,j-l)y
1
+
(l+v(i,j-l))y
2
+v(i+l,j-l)y
3
^v(i.J),
v(i-l,j-l) y^vQ.j-l) y
2
+
(l+v(i+l,j-l))
y^vfrj),
»0'-l.y) yi+v(i.J) y
2
+vQ+\,J)
y
3
<v(i,J),
У\
+Уг +Уз =
1.
34
>0,
У
2
>0,
Уз>0-
Указание. Трудность решения этой игры состоит в том, что для определения
v(i, J) необходимо знать v(i+\, J), для определения »(i+l, 7) необходимо знать
v(i+2,J) и т. д. В приводимых ниже упражнениях дано решение игры rpj) и приво-
дятся некоторые его свойства.
б) Пусть
4>(i,j),
i=l, 2,
...,7—0,
1
—
двойная последовательность, определя-
емая соотношениями
(j»(i, 0)=0,
/
=
1,
2, ...; <р(1,т)=0,7=1,
2
, -
>
fl)(/,7)-min{(l+4»(/-l,7-l)+9(i,7-l)+9(i+l,7-l))/3,
Q+
9
Q-l,j-l)+
9
(t,J-l))l2}.
1) Доказать, что v(i, J)=(p(i, J), и если v(i,
J) =
(l+v(i-l,
7-1)+»
ft
j—l)+
+t,(i +
l,7-l))/3,TO
*i ft Л=»
0".
j)-«
(«'-1,
У-1),
*
2
ft
Л =» 0'.
J)-« ft J-1).
*з ft
j) =»
ft /)-»
0
+
1,
j-1).
*4
С
J)=°>
2) Доказать, что»
{i,j)*=<p{i,
j), и если«0',7)=(1+»(«-1,7'-1)+»0",7"-1))2, то
*i('.7)=»0'.y)-»0-1,7-1), *
2
ft
•/)-»(».
/)-*('. У-1), *s ft Л-**('../)-О,
Ух(/.Л-л(4Л-1/2: ^ftJ)=o.
в) Доказать, что
при
любом7=0, 1, 2,... справедливы следующие соотношения:
i)«ft/)=y/3,1-7+1J+2,...;
2)«ft7)<«0'+l,A« = l,2,...;
3)»ft7)<»ft7'+l),«'=2, 3, ...;
4) • ft7) +•(!+2,7)<2»(i+l,7),
/-1,
2, ... .
г) Доказать, что:
1) ton »(«',т)
=
У/3 при любом фиксированном7°—0, 1,
2,...;
2) ton v(i,f)=i—\ при любом фиксированном
/
=
1,
2, ....
_/-• —оо
20.
Рассмотрим обобщение игры о стрелке и мишени, когда мишень Е, занимая
положение /, может из него передвинуться максимум на к единиц вправо или влево,
т.е.
перейти в каждую из следующих точек /'— к, i—к+\ »,
i
+ l, ..., i+k.
Остальные цели и возможности стрелка Р и мишени Е остаются прежними с учетом
нового определения стратегии игрока Е.
Символом G(i,j) обозначим игру при условии, что мишень в начальный момент
времени занимает i-ю точку, а стрелок имеет
7°
патронов.
Символом v(i,J) обозначим
значение игры G{i,j). Из определения G(i,j) имеем
.(/.
0)=0
/=1,
2, ... , v(i,j)=0,
»
=
1,
2, ..., t,J=\, 2
На каждом шаге игры G(i,J), i=Jfc+l,
...,7=1,
—
стрелок Р имеет 2fc+2 чистые
стратегии, а мишень Е(2к+\) — чистую стратегию. Чистыми стратегиями игрока
Р
являются:
стрельба
в
точку
i—k,
стрельба
в
точку
i—k+
1,..., стрельба
в
точку i+k,
227
отказ от выстрелов на данном шаге. Стратегиями Е
являются:
перемещение в точку
i—k, перемещение в точку
i—k+l,
..., перемещение в точку i+k.
Таким образом, на каждом шаге игры разыгрывается игра с матрицей
{<х
тп
(г,
_/)}
размера (2fc+2)
х
(2к+1),
где
!
1+«(1+и—к—
1,
j—
1),
если
ти=л
=
1,
..., 2к+1,
v(i+n-k-l,
j-\),
если тфп; т. л=1, ..., 2к+1,
v(i+n-k-l, j), если m=2A+2, я=1, ..., 2к+1.
а) Показать, что игра
G
(z,
j)
имеет значение, равное
v
(i,
_/),
в том и только в том
случае, если существуют (х,, х
2
,.... х
2
^+г). (Ук
>а» ••» У2к+г)
такие, что:
2*+2
£ Omnd.f) Xm>v(i,j),
И
=
1,
..., 2АтЧ-1,
т+1
2*+2
£
x
m
= l, дс
т
>0, т=1, ..., 2*+2,
т=1
2*+1
Е
"тяО.
7) >в<«0'-Л »» = 1> •••>
2fc+l,
л-1
2*+1
I Л-1,Л>0,я-1,
...,2*+1.
л-1
Указание. Обозначим символами x
1
(i,
J),
x
2
(i, f) хгк+гИ j) оптимальные
стратегии поведения (если они существуют), с которыми стрелок Р
использует
свои
1-ю, 2-ю, ..., (2fc+2)-K> стратегии в информационном состоянии (i, j),
а
символами
УЛ'<
А
Уг(}>
JX
—>
Угк+ii'' J) — оптимальные стратегии поведения,
с
которыми
мишень
Е
использует свою 1-ю, 2-ю,
...,
(2£+1)-ю стратегии
в
информационном
состоянии (j, j). В приводимых ниже упражнениях приведено решение игры
G{i,
j)
и его свойства.
б) Символом
<p(i,
J), j=0,
1,
...; i=l,
2, ...,
обозначим следующую двойную
последовательность:
<Z>(/,0)=0, «=1,2,...;
?(«,;)=0, /=1,
2,...,
k;j=\,
2,...;
(p(i,j)=
min ((l+^
v
(i+t~k-l,j-l))l(k+2)\
(10.3)
!•-/. ,*+l
\ ,., /
i=k+l, k+2,
...,j=\,
2
Доказать, что
1)
v(i,j)=<l>(i,j)l
2) при i=fc+l, ...; j=l, 2, .., имеем x
m
(i, j)=v(i, j)—v(i+m—k—
1,
j—
1)
при
m=l,..., fc+r*, иначе x
m
(j',/)=0,>'„(i,7')=l/(fc-)-r*) при
л
=
1,...,
fc+r*,
иначе
j>„=0.
Здесь r=r* — точка, в которой достигается минимум в (10.3).
в) Доказать, что при./=0, 1, ...:
1) v(i,J)>Q,
J
=
1,
2,...;
2) v(i,j)=jl(2k+l), ''==fc/'+l, */+2, ...;
228
з)»(|,Л<«0"+1.Л»=1Д».;
4) v(i,J)^v(i,j+l), i=k+l
k+2,
...;
5) »(|'.У+1)<«(/./)+1/(2*+1),
/-1,
2
г) Игра
G(i, oo).
Доказать,
что
fimv(i, j)=u>(i)
при
каждом
i
= l,
2, ..., где
j-»ao
u>
(i)
— решение линейного разностного уравнения
к
ЬЧО-
I
W(!-P)-1,
t-k+l,
k+2,...
Р
-\
с начальными условиями:
*(!)*= и-(2)=...=и>(А:)=0.