Об иерахической повторяющейся игре с ограничением на время наблюдения.1.

E.3.MoxoHbKofmohon@ccas.ru ) ВЦ РАН

Рассматривается непрерывно повторяющаяся игра двух лиц с правом первого хода у первого игрока. Он может получать информацию о выборах второго игрока как дискретным, так и непрерывным образом. Время одного наблюдения фиксировано. Существует ограничение на суммарное время наблюдения за вторым игроком. Запас времени, которое первый игрок может затратить на наблюдение за партнером, в общем случае меньше длительности игры. В статье выясняется может ли первый игрок при таком ограничении получать тот же выигрыш, который он получает при отсутствии такого ограничения, т. е. при непрерывном наблюдении за партнером на протяжении всей игры. В данной статье рассматривается случай двухточечного оптимального выбора .

Работа выполнена при поддержке РФФИ, грант № 00-01-00688.

Есть много работ, посвященных динамическим играм с неполной информацией, с памятью, с запаздыванием информации, с помехами, с неточной информацией. Назовем хотя бы монографии Красовского Н.Н., Субботина А. И. [1], Куржанского А.Е. [2], Петросяна Л.А. [3], § 3 главы 1 диссертации Клейменова А.Ф. [4], работу Порталлер О. и др. [5]. О возможности получать дискретную информацию в

антагонистической динамической игре писали в своей монографии [6] Ф.Л. Черноусько и А.А.Меликян. А

неантагонистические динамические игры такого типа почти не рассматривались. Некоторое время существовала только одна работа [7] А.Ф. Кононенко. Диссертация [8] Е.З. Мохонько заполнила этот пробел, эту нишу. Был разработан

математический аппарат для решения новых задач, возникающих при исследовании допустимых и оптимальных информационных потоков разного качества в динамических неантагонистических играх. Результаты, связанные с достаточностью получения дискретной, неточной информации [9], [10], вместо точной и непрерывно поступающей, могут быть изложены с помощью терминов, привычных для исследователей, работающих в области агрегирования информации.

В [8] рассматривались игры, в которых игроки находились на одном уровне иерархии. В данной работе игроки находятся на разных уровнях иерархии. Это повлекло за собой усложнение характера оптимального режима получения информации по сравнению со случаем, когда игроки находятся на одном и том же иерархическом уровне.

1.ВВЕДЕНИЕ

Рассматривается иерархическая игра двух лиц, в которой первый игрок обладает правом первого хода и использует стратегии с памятью о выборах второго игрока во все предыдущие моменты времени. Оптимальная стратегия первого игрока представляет собой некоторый оптимальный программный выбор, если второй игрок следует предлагаемому ему поведению и наказание второго игрока в противном случае. Оптимальный программный выбор представляет собой либо выбор одной точки на протяжении всей игры, либо выбор двух точек с некоторыми весами. Для случая двухточечного оптимального выбора определяется такой режим получения информации, при котором суммарное время наблюдения за выборами второго игрока минимально. Если оно не превосходит того запаса времени, который первый игрок может потратить на наблюдение за вторым игроком, тогда первый игрок может делать тот же оптимальный выбор и получать тот же выигрыш, что и при непрерывном наблюдении на протяжении всей игры.

В следующей статье будет показано, что в случае, когда оптимальный выбор представляет собой непрерывный выбор одной точки, доказана теорема, позволяющая ответить на поставленный вопрос без поиска оптимального режима получения информации. Необходимо только знать точку оптимального выбора, величину запаса времени наблюдения и цену одного наблюдения.

Перейдем к формальному изложению результатов.

Итак, рассматривается повторяющаяся игра двух лиц с непрерывным временем, в которой первый игрок обладает

правом первого хода. В качестве множества X\ выборов

игроков можно взять множество измеримых (по Борелю)

функций Xj (t) : [0,1] - Xj, i = 1,2, где множества Xi, i = 1,2, являются

компактными подмножествами соответствующих евклидовых пространств. Критерии игроков определяются равенствами

Fj =JMt (x 1(t), x 2(t ))dt ,

где функции Mi(x) = Mi(x 1,x2), i = 1,2, непрерывны и ограничены на произведении X = X1 хX2 .

Игрок 1 использует стратегии с памятью. Он в каждый момент времени t е [0,1] будет иметь информацию о выборах игрока 2 во все предыдущие моменты времени

x 2(., t) = {x 2(7-),0 <т< t} , то есть игрок 1 выбирает и сообщает игроку 2 свою стратегию

в виде x((t) = р1(x2(.,t),t), t > 0 . Имея информацию об

x((t) = р1(x2(.,t),t), t > 0 второй игрок выбирает x2(t) еXt1 из условия максимизации своей функции выигрыша F2 . Игрок 1 выбирает x[, максимизирующий его гарантированный выигрыш при условии рационального поведения игрока два.

В дальнейшем рассматривается описанная выше игра при условии, что первый игрок может получать информацию как непрерывным, так и дискретным образом. Каждое дискретное наблюдение в момент времени tn е [0,1] и начало непрерывного наблюдения на [tn,tr], 0 < tn < tr < 1, обходится игроку в min{tn,d} временных единиц. Для того, чтобы узнать поведение партнера на [0,tn) необходимо начать наблюдение в момент tn -min{tn,d} . Само непрерывное наблюдение оценивается величиной отрезка наблюдения tr -tn .

Пусть существует ограничение на суммарное общее время, затрачиваемое на наблюдение 1-м игроком: 1-й игрок может сделать произвольные n дискретные наблюдения и произвольные m непрерывные наблюдения с длительностью 0k временных единиц (k=1,...,m) такие, что их общая сумма не превосходит T. Например, если m=2, первый отрезок непрерывного наблюдения начинается в момент t=0, его длина 01, второй отрезок непрерывного наблюдения длиной 02 находится в конце [0,1], а в промежутке между ними проводится n дискретных проверок, то общее суммарное время подсчитывается так:

nd + d + 0k = (n + 1)d + 0k .

k=1 k =1

T будем в дальнейшем называть запасом времени наблюдения, которым обладает первый игрок.

Ставится задача: пусть первый игрок обладает запасом времени наблюдения T<1. Требуется выяснить, может ли он при этом получить тот же выигрыш, делая тот же оптимальный выбор, который он делает при непрерывном наблюдении, когда запас времени наблюдения T=1?

Для решения этой задачи необходимо сначала знать, каков

же он, оптимальный выбор x10 первого игрока при T=1, то есть тогда, когда первый игрок может непрерывно получать информацию о выборах второго игрока. Этот оптимальный

выбор был определен в работе [11], стр. 65. При предположении {xеX M2(x)>L2}Ф0 была доказана теорема о верхней грани гарантированных выигрышей первого игрока и определена оптимальная стратегия первого игрока.

Верхняя грань гарантированных выигрышей игрока величине N:

N = max JM 1(x 1(t),x2(t))dt (1.1)

1 равна

ограничениях

при

у = -M2(xx,x2\ y(1) = 0, y(t) >L2(1-1), Vt е [0,1]

(1.2.)

где L2 = max minM2(x1, x2), x1 е X1, x2 е X2 .

Будем рассматривать задачу при предположении доброжелательности второго игрока к первому.

Доброжелательность понимается в следующем смысле. Второй игрок делает рекомендованный первым игроком выбор, если самостоятельные действия второго игрока не принесут ему больший выигрыш, чем выигрыш, который он получает, следуя рекомендациям партнера.

При предположении доброжелательности оптимальная стратегия первого игрока имеет вид

<z>°(x2(., t),t):

x 10(t), если x2(.,t) = x20(.,t) ,

(1.3)

xn такое, что maxM2 (xn, x2 ) = L2, при x2 (., t) Ф x2 (., t)

Если N = max M,

оптимальный точки на

то x0(t) = x0 e{x M2(x 1,x2)>L2} , то

выбор x0 (t) представляет протяжении всей игры.

максимум max M1 .

Если N Ф max M1 [11], стр.74,

собой выбор одной На x °(t) достигается

x °(t) -любая измеримая

функция вида

x0(t)

x01 е X, если t е A1 с [0,1]

(1.4)

е X, если t е A2 с [0,1]

где A1 nA2 = (0, A1 A2 = [0,1], мера множества A1 mesA1 = p .

p,x 01,x 02 находятся из решения задачи максимизации функции pM 1( x01) + (1 - pM 1( x °2)

при ограничениях pM2(x ) + (1 -p)M2(x ) = L2 , p > 0,x g X,i = 1,2 .

На A1 и A2 налагаются ограничения:

M2(x01 )mes(A1 n [t,1]) + M2 (x02 )mes(A2 n [t,1]) > L2(1 -t), Vt g [0,1] .

(1.5)

Такая задача максимизации фунции pM1(x01) + (1 - p)M1(x02) возникает при поиске оптимального скользящего режима [12] задачи (1.1),(1.2).

2. ОПТИМАЛЬНЫЙ РЕЖИМ ПОЛУЧЕНИЯ ИНФОРМАЦИИ В СЛУЧАЕ ДВУХТОЧЕЧНОГО ВЫБОРА

Пусть некоторый режим получения информации состоит из произвольных n дискретных проверок в моменты времени t,

i=1,...,n и m непрерывных проверок длительностью 0 £ , k=1,...,m.

Обозначим через Ct множество

С = [т|те ((( u tt) u ( u0 к )) п [0,t ])}

=1 к =1

Стратегия вида

x 10(t), если x2(.,т) = x2°(.,т), те Ct,т< t, °(x 2(.,t ),t) = (2.1)

такое, что maxM2(x ,x2) = L2, если ЗтеС(,т<t,x2(.,T)x°(.,t).

также может обеспечить первому игроку гарантированный выигр^1ш при правильном подборе режима проверок.

Режим получения информации, при котором стратегия (2.1) обеспечивает первому игроку тот же гарантированный выигрыш, что и стратегия (1.3), будем называть допустимым режимом получения информации. Оптимальным режимом получения информации для данного оптимального выбора первого игрока будем называть такой допустимый режим, при котором суммарное время, затрачиваемое первым игроком на наблюдение, не превосходит суммарного времени,

затрачиваемого при других допустимых режимах.

Оптимальный режим получения информации разный для разных

случаев оптимального выбора x0(t).

Пусть функция x °(t) из (1.4) имеет вид

X 0(t)

Г x01 g X, если t g [0, b)

, (2.2)

x02 g X, если t g [b,l]

bM2(x01) + (1 -bM2(x02) = L2, 0 < b < 1,x0г gX,i = 1,2, M2(x01) <L2,M2(x02) >L2.

Докажем, что при других оптимальных выборах вида (1.4), где A1, A2 удовлетворяют условию (1.5), общая сумма времени,

соответствующая оптимальному режиму получения информации, будет не меньше, чем тогда, когда первый игрок делает оптимальный выбор вида (2.2). Введем обозначения:

M*1 = max M2(x01,x2),M2*2 = maxM2(x°2,x2), M°l = M2(x01,x21),

M202 = M2(x02, x202) .

Рассмотрим x °(t) вида (1.4). Если t - момент получения информации, то следующий момент получения информации tk (t) может быть выбран исходя из неравенства

M°lmesA1 + M202mesA2 >M2mes(A1 П[0,t])+M202mes(A2 П[0,t])+M2mes(A1 П[t,tk] + Mf mes(A2 П [t, tk ]) + L 2(1 - tk ).

Учтем, что A1 П A2 = 0 , mes(A1 П [t,tk ]) + mes(A2 П [t,tk ]) = tk -1, mes(A1 П [t,0]) + mes(A2 П [t,0]) = t, M201mesA1 + M202mesA2 - L2 = 0 .

При M2*1 > M2*2 неравенство перепишем следующим образом.

0 > (M201 -M (2)mes(A1 П [0,t])+M2021 + M2*1mes(A1 П [t,tk ])+M2*2(tk -1) -M2*2mes(A1 П [0,t])- L 2tk

или

(M202 -M 201 )mes(A1 П [0, t ]) + (M2*2 -M202 )t > (M -M2*2 )mes(A1 П [t, tk ]) + (M2*2 - L 2 )t

При M2*2 >M2*1 >L2 неравенство перепишем так: (M202 -M201 )mes(A1 П [0,t]) + (M -M202 )t > (M2*2 -M)mes(A2 П[t,tk]) + (M -L2)tk

Из полученных неравенств можно сделать вывод, что при M 2*1 L 2 для данного t величина tk тем больше, чем больше величина mes(A1 П [0,t]) . При M2*1 = L2 такой вывод можно сделать при mes(A2 П [t,tk ]) (0 . В конце статьи будет продолжен разбор

случая M2*1 = L2 . А сейчас разберем случай M2*1 L2 .

Итак, мы выяснили, что если оптимальный выбор первого игрока имеет вид (2.2), то величина mes(A1 П [0,t]) будет

наибольшей, и для всякого t момент контроля tk (t) будет не

меньше, чем момент контроля t, который вычислен для любого другого оптимального выбора вида (1.4). А это значит, что режим проверки, при котором общее суммарное время T будет минимальным, следует искать при оптимальном выборе вида (2.2).

В случае двухточечного оптимального выбора (2.2)

оптимальный режим получения информации строится в два шага. Сначала строится некоторый допустимый режим получения информации, который позже используется при определении оптимального режима получения информации.

Приступим к построению такого допустимого режима.

Введем обозначения

= м 2 - м 201 = м- м 201 = м 2*2 - м 202

Сначала строим некоторую функцию tk (t): [0,1] - [0,1].

Пусть t g [0,t**], где tk(t**) = b . tk(t) находится из равенства

м 201t + м 2*1(tk -1) + L 2(1 - tk ) = м 201b + м202 (1 - b ) (2.3)

и, следовательно, t** находится из равенства м201t ** + м21 (b -1 **) + L 2 (1 - b ) = м201b + м202 (1 - b ) .

Интерпретация равенства (2.3) такая. Пусть до момента времени t игрок 2 делал выбор x 21, рекомендованный первым игроком. А после момента времени t второй игрок решил отклониться. Пусть к тому же первый игрок получал информацию о выборах партнера до момента времени t . Потом перестал получать информацию и в момент времени tk опять

начал получать информацию. Если tk выбрано согласно равенству (2.3), то второму игроку нет смысла отклоняться от выбора x201 на [t,tk ], так как в результате отклонения он не

получит больше, чем получает не отклонившись.

Замечание. Если из (2.3) следует, что первый момент получения информации t1 = 1, то будем считать, что в момент t1 = 1 производится дискретное наблюдение и общее суммарное время наблюдения T=d.

Итак, для t g [0,t ] tk(м^1 -L2) = м201Ь +м202 (1 -b) + (м^1 -м201> -L2 , то есть при

02 ,

м 201b + м 202 (1 - b ) - L

м21 -L2 * 0 tk = + - * \ -2- . Поскольку

2 2 k 1 (м2 1 - L2 )

м201b + м202 (1 - b) -L2 = 0 , то для t g [0,t**]

tk = 1t . (2.4)

Отсюда следует, что t =b/q1 .

Напомним, что мы предполагаем, что M2*1 -L2 0 . Для t [t**,b] формула tk(t) выводится аналогично.

tk (M ;2 - l 2) = Mb +Mf(i - b) + (M * - m f)t - l 2 + (M ;2 -m;>

или, поскольку M201b +M202 (1 -b)-L2 = 0 , (M2*2 -M2*>

tk = q2t + \ Л*2 . (2.5)

M ft + M 2*1 ( b -1) + M f (tk - b ) + L 2(1 - tk ) = M 201b + M 202 (1 - b ) .

Таким образом, мы нашли выражение для момента tk ,

показывающего когда следует проверять второго игрока, если до момента времени t он следовал рекомендованному первым игроком выбору. При таком выборе tk второму игроку нет

смысла отклоняться, так что при rG [t,tk] он будет выбирать

x0(r) . И отрезок [t,tk ] является максимально большим отрезком

среди всех отрезков, обладающих таким свойством не выгодности отклонения для игрока 2. Лемма 1. tk (t) непрерывна на [0,1].

Непрерывность tk(t) на [0,t**], (t**, b), [b,1] следует из вида формул для tk(t). Для доказательства леммы достаточно показать что b = tk(t**) = lim**tk(t) и tk(b) = limtk(t) .

t->t ** t ->b

t>t t<b

Покажем, что tk(t**) = lim tk(t) . Используем равенство t** = b/q1 .

Доказательство.

t>t

То есть t

- M + L 2 b

lim tk (t) = lim[q2(t + a)

t -t a-0

t >t** t >t**

(M *2

M2 2

M21 -M01 -M2!b + L2b + (M*2 -M21)b

M21b - L2b + (M22 -M21)b = (M*2 - L2)b

M2 2

M2 2

M2 2

M2 1

M2 2

Итак, мы получили tk(t**) = lim*tk(t) = b , т.е. tk(t) непрерывна

в

t ->t t >t **

точке t = t .

Докажем, что tk (b) = limtk (t) .

t --b t <b

(M*1 - m 201) (M*2 - M21)b

lim tk(t) = lim tk(b -a) = lim--(b -£) + 2 22 2 ]

t-b t <b

£-0

M*2 - L2

(M21 -M21 )b + (M*2 -M21 )b (M*2 -M°l)b

tk(b)

M22 - L2

(M 22 - M 202 )

b + 2

M*2 - L2

(1 - b ) - L 2 (M ;2 - M Г

учитывая, что M 201b + M 202 (1 - b ) Следовательно,

L2 =

lim tk (t) = tk (b)

t<b

и

tk(t)

непрерывна

исследования

при

точке

таком

t = b .

Лемма доказана.

Мы будем вести дальнейшие ограничении на величину d :

d < min(0.25;(- - -);#3(1 -q2)(1 -b)) (2.7)

Для того, чтобы был смысл проверять дискретно в момент времени tk(t), необходимо, чтобы выполнялось условие

tk (t) -1 > d , так как для получения информации в момент tk дискретным способом необходимо потратить ресурс d из запаса времени T. В самом начале отрезка [0,1] формула для t такая: tk = q1t, q1 > 1 . Пусть момент времени t такой,

tk(t) -1 = d . До момента времени t необходимо проверять второго игрока непрерывно. Длину отрезка [0, t] обозначим буквой K .

что

в

При ограничении (2.7) на величину d выполняется неравенство: K + d <t =- . Это значит, что при начальном

периоде непрерывной проверки равном K на [0, t **) есть хотя бы одна дискретная проверка и момент tg [0,t**) .

Действительно, по определению K q1 -K = d, т.е. K d

d <- (1--) = - (--), K < - K + d < t = -

q1 q1 q1 q1 q1 q1

При ограничении d < q3(1 - q3)(1 - b) при начальном периоде непрерывной проверки равном K существует хотя бы одна дискретная проверка на (b,1]. Это связано с тем, что если tj -

наименьший момент получения информации, принадлежащий [b,1], то он либо равен b , либо больше b . В первом случае tj+2 -tj+1 = q3(1 -q3)(1 -b) > d , и tj+1 -дискретный момент получения

информации, tj+1 g (b,1] . Во втором случае

tj+1 -1} = (1 - q3)(1 - tj ) > (1 - q3)(1 - q3 b -1 + = q3(1 - q3 )(1 - b) > d и t} -

дискретный момент получения информации, принадлежащий (b,1].

Выясним, в какие моменты можно получать информацию дискретно при начальном периоде непрерывной проверки равном

По определению момента t tk (t) -1 = d ,

tk (tk (t)) - tk (f) = q1tk (f) - q/ = q1 (tk (t ) -1) = > d , (2.8)

т.к. q1 > 1 . Поэтому информацию можно получать дискретно в моменты t1 = tk(tt2 = tk (tk(t)), -, tn = tk (tn-1) , где n - число дискретных моментов наблюдения, находящихся на [0,t ) . На

[t , b) есть только одно дискретное наблюдение.

Пусть при начальном периоде непрерывной проверки равном K на [b,1] расположено m -1, m > 2 , дискретное наблюдение.

В связи с тем, что q3 < 1 существует момент времени ~, ~ g [b,1] такой, что tk( t ) - t = d . По той же причине существует момент времени tn+m> 7 такой, что tn+ m- tn+m > d, tn+ m+2 - tn+m< d, tn+m < 7 .

J- n+m +1 n+ m+1 n+m ? n+ m+2 n+m +1 ? n+m

Начиная с момента времени tn+m+1 необходима непрерывная

проверка. Такой режим получения информации допустим и общее суммарное время, затрачиваемое первым игроком на

наблюдение, описывается формулой