Популярное

Мифы о звукоизоляции



Как построить дом из пеноблоков



Как построить лестницы на садовом участке



Подбираем краску для ремонта



Каркасные дома из дерева


Главная » Об иерахической повторяющейся

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

время наблюдения.11.

Е.З.Мохонько (mohon@ccas.ru ) ВЦ РАН

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

Эта статья является продолжением статьи Об иерархической повторяющейся игре с ограничением на время наблюдения. I . Работа выполнена при поддержке РФФИ, грант № 00-01-00688.

1. ОПТИМАЛЬНЫЙ РЕЖИМ ПОЛУЧЕНИЯ ИНФОРМАЦИИ В СЛУЧАЕ ОДНОТОЧЕЧНОГО ВЫБОРА В случае N = max M1(x) оптимальный выбор первого игрока

представляет собой выбор одной точки на протяжении всей игры:

x 1 (t) - x 1 .

Методами работы [1] показывается, что при M2* L2, где M2= maxM2(x°,x2), L2 = max minM2(x 1зx2), x 1 е X1, x2 е X2,

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

x такое, что maxM2(x ,x2) = L2, если

Моменты tt , i = 1,2,..., , определяются так:



t = 1 -(qУ , где q = q(x0) = M M2 , M° = M2(x°,x°) .

M 2 - L 2

Если до момента времени t второй игрок выбирал x° и первый игрок знал об этом выборе, то для того, чтобы второму игроку было не выгодно отклоняться, необходимо проконтролировать его, т.е. получить информацию о его

выборах не позже момента tk(t), который определяется из равенства M20t + M2*(tk -1) + L2(1 -tk ) = M20 .

Отсюда tk = qt +1 - q. При t = 0 из M2*t1 + L 2(1 -11) = M2 получаем, что

ti = (M20 -L2)/(ML2) = 1 -q .

Второй момент получения информации получаем так: m 2 (t 2 - ti)+l 2(1 -12) = M °(1 - ti) ,

t2 = (M 2 - l 2)/(M 2 - l 2)+[(M 2 - m 2)/(M; - l 2)][(m 2 - l 2)/(m 2 - l 2)].

Учитывая, что 1 - q = (M20 - L 2)/(M2*-L 2) , получаем t2 = 1 - (q)2 .

Выбирая моменты времени t по такому алгоритму, придем к формуле tt = 1 - (q) .

Если tn такой момент времени, что расстояние между ним и

моментом tn+1 меньше либо равно d, то начиная с этого момента нет смысла проверять игрока дискретным образом, а следует начинать непрерывную проверку. Так что минимальный расход времени при 0 < q <1-d вычисляется [1] следующим образом:

T0(q) = nd + (qn) ,

где n-число наблюдений, зависящее от q = q(x°) и удовлетворяющее такой системе Г(q) n(q 41 - q ) < d (q) n(q - q ) > d (1.2)

При 1 - d < q < 1 для всякой стратегии вида (1.1) минимальное время T0 , которое требуется затратить, равно единице, так как t1 = 1 -q , t1 -0 < d , t2 -11 = q(1 -q) < dq < d .

При q = 0 t1 = 1, так что T0(0) = d . Замечание 1.

Формулы для tt , i=1,2,... получены при предположении, что ML2 . Если M2= L2, то из M20t + M2*(tk -1) + L2(1 -tk) = M20

0 = L

следует, что M20 = L2 . Поскольку предполагается, что второй

игрок доброжелательный, то из равенства M 20 = M 2* = L 2

вытекает, что второго игрока не надо контролировать, он не

будет отклоняться от x20, то есть T0 = 0 .



Продолжим рассмотрение случая M2 Ф L2 .

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

Чтобы ответить на поставленный вопрос в случае одноточечного оптимального выбора можно было бы построить оптимальный режим получения информации и сравнить имеющийся

запас времени T с T0(q) = nd + (q)n , где n удовлетворяет (1.2).

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

что если q(x0) < qT , то первый игрок, имея запас времени T , может, делая тот же выбор, получать тот же выигрыш, который он получил бы при непрерывном контроле партнера на протяжении всей игры. Это значит, что удалось описать область каждая точка которой, будучи выбором первого игрока, обладает таким свойством. Кроме того, в процессе поиска этой величины исследуются свойства функции T0(q) .

Полученные результаты могут быть полезны при решении других задач, связанных с тематикой оптимизации информационных процессов в неантагонистических конфликтах, например, при решении задачи о максимальном гарантированном выигрыше первого игрока при T<1.

Итак, исследуем функцию T0(q) = n(q)d + (q)n(q), где функция n(q) определена при q e (0,1 - d) , принимает целые неотрицательные значения n и такова, что выполняются соотношения (1.2). При этом будут использоваться результаты из [2].

Лемма 1. Для каждого q e (0,1 - d) n(q) определяется однозначно.

Доказательство. n(q) определяется однозначно в силу

монотонного убывания функции qn(1 - q) по n. Действительно,

пусть найдется такое q , что для него существуют n1(q), n2(q),

удовлетворяющие (1.2) и такие, что n1(q) < n2(q) . Тогда имеет место неравенство

(q)n2(q- q) < (q)n1(q}(1 - q) < d . (1.3)

(Первое неравенство из (1.3) выполняется из-за убывания функции qn(1 - q) при возрастании n, второе неравенство выполняется в силу предположения, что n1 (q) удовлетворяет

(1.2)). То есть

(q)n2(q- q) < d .



По условию, n2(q) удовлетворяет (1.2). Следовательно,

должно выполняться (q) 2(q-q) > d .

Таким образом, мы пришли к противоречию. Это и доказывает, что для каждого q е (0,1 - d) n( q) единственно. Лемма доказана.

Определим конкретные значения n(q) для q е (0,1 - d) .

Функция qn(1 - q) убывает по n, равномерно стремясь к нулю. Поэтому существует такое N , что qN (1 -q) < d сразу для всех q е [0,1], и при этом найдется q0 е [0,1], для которого qN-1(1 -q0) > . N зависит только от d и не зависит от q .

Для всякого d такого, что 1/4 < d < 1, таким N является N = 1, поскольку max q(1 - q) = 1/4 при q = 1/2 , qn(1 - q) убывает

0<q <1

при росте n и для всякого q е [0,1 - d) выполняется 1 - q > d .

Заметим, что при d е (1/4,1) T0(q) = q + d , число n(q) из (1.2) равно единице: n( q) = 1 .

Далее, до замечания 2, будем предполагать, что 0<d<1/4 .

При 0 < d < 1/4 N>1 в связи с равномерным стремлением функций qn(1 - q) к нулю при росте n и тем, что max q(1 - q) = 1/4 .

0<q<1

Уравнение qn(1 -q) = d имеет один корень при n = 0 .

Лемма 2. Уравнение qn (1 - q) = d имеет не более двух различных значений корней при 0 < n <N , n - целое.

Доказательство. При 0 < n <N, n - целое уравнение qn(1 - q) = d имеет одно либо два различных значения корня так как непрерывная функция qn(1 - q) строго возрастает при 0 < q < n/n +1, строго убывает при n/n +1 < q < 1, qn(1 - q) > qN-1(1 - q) при n <N -1 и, кроме того, по определению N , qN-q) > d хотя бы при одном q е [0,1] .

Эти значения корней отличны от 0 и 1, что связано с тем,

что d > 0 . Уравнение qn(1 - q) = d при 0 < n < N имеет

единственное значение корней только в случае, когда n = N -1 и

max qN- q) = (N -1/N )nN ) = d .

qе[0,1]

В остальных случаях уравнение qn(1 - q) = d , q е [0,1], 0 < n < N , имеет два различных значения корней. Лемма доказана.

Обозначим значения корней уравнения qn(1 - q) = d через

<7n , qn . Пусть <7n < qn .

Лемма 3. Значения корней уравнений qn (1 - q) = d n = N -1, расположены в таком порядке



d < q1 < q2 < ... < qN-1 < qN-1 < ... < q2 < q1 < 1 - d . Доказательство. При n = 1 q1 = 1/2 -V1/4 - d > 1/2-V1/4 - d + d2 = 1/2 (1/2 - d )2 = 1/2 - (1/2 - d) = d ,

q1 = 1/2 W1/4 - d < 1/2 + (1/2 - d) = 1 - d . Таким образом, d < q1, q1 < 1 - d .

Докажем, что qn-1 < qn, 1 < n < N -1 . Предположим, что существует такое n, что qn-1 > qn. По свойству степенной функции qnn-1(1 - qn ) > qnn(1 - qn ) = d, qn-1(1 - q) непрерывна и принимает при q = 0 значение 0, а d>0 . Поэтому существует такое q*, q* < qn < qn-1, что qn-1(1 - q*) = d . А это противоречит тому, что уравнение qn-1(1 -q) = d имеет два значения корней, причем qn-1 -наименьшее значение корней. Таким образом, qn-1 < qn . Аналогично доказывается, что qn < qn-1 . Но равенство qn-1 = qn = q либо равенство qn = qn-1 = q возможны только тогда, когда

qn(1 -q) = qn-1(1 -q) , то есть q = 0 , либо q = 1, а все значения корней находятся, как было доказано, в промежутке (0,1 - d) . Итак,

d < q1 < q2 < ... < qn-1 < qN-1 < ... < q2 < q1 <1 -d . Лемма доказана.

Лемма 4. n( q) из (1.2) удовлетворяет таким равенствам: n(q) = N при qn -1 < q < qn-1 ;

n(q) = n -1 при qn-1 < q < qn -1, qn-1 < q < qn-2 ;

n(q) = 1 при 0 < q < q1 и q1 < q < 1 - d . Доказательство.

qn(1 - q) < d при q < qn и q > qn и при n = N для всех q e [0,1]; qn-1 (1 - q) > d в таких случаях: a) при <7n-1 < q < qn-1 для N > n , Ь)для n = N в случае qN-1 Ф qN-1 , с)при n = 1 для всех q < 1 - d . Из этого и системы неравенств (1.2) и вытекает утверждение леммы.

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

Итак, для каждого q выяснено конкретное значения n(q) . А минимальный запас времени T0(q), который требуется первому

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

T0(q) = n(q)d + (q)n(q), где n(q) удовлетворяет (1.2)



Следовательно, T0(q) выражается формулой

q + d , q2 + 2 d ,

q = 0, !

0 < q < q ,

q1 < q < q2 ,

T0(q)

qN-1 + (N - 1)d , qN-2 < q < qN-1 ,

qN + Nd , qN -1 < q < qN -1 ,

qN-1 + (N - 1)d , qN-1 < q < qN-2 ,

q + d ,

q1 < q < 1 - d 1 - d < q < 1 .

Для дальнейшего нам понадобится следующая

Лемма 5. Пусть n и q таковы, что qn(1 - q) < d , qn-1(1 - q) > d

Тогда для

0 < q < 1, d > 0 , n - целое положительное. целых положительных mqn + nd = min(qm + md) .

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

Поскольку функция qn(1 -q) убывает по n при 0 < q < 1, то V m > n qm (1 - q) < qn (1 - q) < d , т. е. qm (1 - q) < d или qm+1 - qm + d > 0 , qm + md - qn - nd = qm - qn + (m - n)d =

qm - qm-1 + d + qm-1 - qm-2 + d +... + qn+1 - qn + d = / = m-1

S (q+1 - ql + d) > 0

Из тех же соображений Vm < n , m > 0 qm (1 - q) > qn 1(1 - q) > d

т. е., q - q - d > 0 ,

m in 1 m n / \t q + md - q - nd = q - q - (n - m)d =

qm - qm+1 - d + qm+1 - qm+2 - d + ... + qn-1 - qn - d =

S-1 (ql - ql+1 - d) > 0.

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

Лемма 6. Функция T (q) непрерывна

возрастает по q при q [0,1-d].

и

строго монотонно

Доказательство. Непрерывность функции T0(q)

qn + nd 1 < n < N

следует из непрерывности функции и того факта, что для

всякого

на [0,1-d] на [0,1-d]

n 2 < n < N



+ ( - 1)d = q -1 + d

и

-1> )

+( - 1)d = + d (так как С-1(1 - = d).

Напомним, что qn, обозначают значения корней уравнения q (1 - q) , <7n < qn .

Для доказательства монотонности заметим, что если q , q (q < q ) принадлежит одному и тому же интервалу, например, (qi-1,qt ], то T0(q ) <T0(q ) из-за возрастания функции q + d по q

Пусть q , q принадлежат различным из выше интервалов, например, q g (qk-1,qk],

Поскольку q g (qk-1,qk ], то T0(q ) = q, + kd При

связаны соотношением

определенных этом k и q*

(1 - q,) < d

q, (1 - q,) > d

Это позволяет применить лемму 5. T)(q*) = q, + kd = min[q + d] < qm + md

Поскольку

q, < q , то

по q, кроме того и на этом интервале

qm + md < qZ + md

в силу возрастания функции qm +md

qZ+ md = Tu(q ) , поскольку q g , qm-1) , выполняется

ql (1 - q ) < d

q m -1(1 - q ) > d

Таким образом, мы получим, что T0(q ) <T0(q ) .В случае, если q , q принадлежат любым другим типам интервалов из набора [0, qj , (qM, q, ], [q -1) [,1 - d) , i = 2 N -1,

доказательство строгого возрастания функции T0(q) такое

Итак, T0(q) непрерывна и на [0,1-d]. Лемма доказана.

Для T<1 определим область свойствами 1-3, описанными ниже.

Свойство 1. DT g D* .

Свойство 2. Для система интервалов

строго монотонно возрастает DT g X1 xX2 , обладающую

всякой точки x = (x 1зx2) g Dt

существует j = 1m ,

d < 0 <T

обладающая

следующим

свойством: для всякого k



найдется j такое, что [tk(x)-d,tk(x)]c [rj-1,rj] и при этом

S©j <T .

max M 2( x 1, x 2) - M 2( x 1, x 2)

Здесь tk (x ) =1 - (q(x ))k , где q(x ) = --------.

max M 2( x 1, x 2) - L 2

Свойство 3. Всякая другая область Dе X1 хX2, обладающая свойствами 1 и 2, принадлежит DT .

Найдем явное выражение границы области DT через заданные T и d .

Если T < d , то T0 = 0 , DT = {x е D* M2*(x) = L2} .

Если T = 1, то DT = D*, при T = 1 можно наблюдать непрерывно. Если T = d, то DT ={x е D q(x) = 0} также, так как в этом случае информацию о ходе игры можно получить только один раз в какой-то момент времени t . Если q(x) 0, то из

формулы tk =1 - (q)k следует, что информацию о ходе игры необходимо получить не только в момент t , но и дальше.

Теорема 2. Для d < T < 1 DT = {x е D* q(x) < qT } , где

qT = max - nd при T > d . Для T = d DT = {x е D* q(x ) = qT } , где

1 1<n<[T / d] 1

qT = 0 .

Здесь [a] обозначает наибольшее целое, не превышающее a . Доказательство. Функция T0(q) непрерывна, монотонно возрастает на (0,1 -d], limT0(q) = d , T0(1 -d) = 1, поэтому для

всякого T е (d,1) существует единственное qT е [0,1 -d] такое, что T0(qT ) =T . Вследствие монотонного возрастания функции T0(q) для всех q < qT выполняется T0(q) < T . Поэтому

DT = {x е D* T0(q(x)) < T} = {x е D* q(x) < qT } .

Докажем, что qT = max - nd при T > d .

T 1<n<[T / d]

Пусть qT таково, что T = (qT )j + jd , 1 < j <N , и пусть существуют такие q, m Ф j , m < [T /d], что q = T-md > qT . Тогда T = md + (q )m . Поскольку q > qT , функция md + (q )m

возрастающая по q , то md + (qT )m < md + (q)m = T , то есть md + (qT )m < jd + (qT )j . А это противоречит лемме 5, по которой jd + (qT )j = min(nd + (qn)n) . (Условия леммы 5 для qT и j

0<n

выполнены в силу определения 0(q), которое в данном случае, по определению qT , равно T , T = (qT )j + jd = T0(qT ) . Тот факт,



что можно рассматривать только такие n , что n < [T /d], следует из требования неотрицательности подкоренного выражения T - nd и вещественности и неотрицательности q .

При T = d DT = {x g D * q(x ) = 0} . Теорема доказана. Замечание 2. При 1/4 < d < 1 T0(q) = q + d , поэтому qT = T - d ,

DT = {x g D* q(x ) < T - q} .

Пример. Mj(xj,x2) = -(xj2 + (x2 + 0.9)2) ;

M2(xj,x2) = -xj2 - x2 ; -1 < xi < 1, i = 1,2 .

T = 0.5 , d = 0.1, L2 = 0 , x°(t) = (0,-0.9) .

D*= {-1 < x,. < 1, i = 1,2 (x2 <-x2)}.

qT = qT = max - nd = a ; 0.58< a <0.59, n = 3 .

1<n<[T / d]

DT = D05 = {x g D* q(x 1,x2) < a} .

q(x 1,x2) = (-xf +1 + xj2 + x2)/(-xj2 +1) = (x2 +-xf +1) < a . Граница DT = D05 находится между кривыми: (x2 +-x2 +1) = 0.58 ; (x2 +-xj2 +1) = 0.59 и далее часть ее лежит на прямой x2 = -1 .

x 0(t) = (0,-0.9) g D0.5 . Первый игрок, обладая запасом времени наблюдения T = 0.5 , сможет получить тот же выигрыш, который он получил бы при непрерывном наблюдении за поведением второго игрока, когда T =1 .

СПИСОК ЛИТЕРАТУРЫ 1.Кононенко А.Ф. О задаче наблюдения в повторяющихся операциях Соврем. состояние теории иссл. операций: Сб. научн. тр. М.: Наука, 1979. С.179-182.

2.Мохонько Е.З. Повторяющаяся игра с ограничением на время наблюдения. М.: Деп. в ВИНИТИ, 4Г453 Деп. 1990. РЖ Мат. 1990. N4. 14 c



© 2017 РубинГудс.
Копирование запрещено.