автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Принятие решений по агрегированной информации в теоретико-игровых моделях

АКАДЕМИЯ НАУК СССР ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

АЛИЕВ ВАГИФ СУДЕИФ ОГЛЫ

ПРИНЯТИЕ РЕШЕНИИ ПО АГРЕГИРОВАННОЙ ИНФОРМАЦИИ В ТЕОРЕТИКО-ИГРОВЫХ МОДЕЛЯХ

(специальность: 05.13.18 - теоретические основы математического моделирования, численные методы и комплексы программ)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1991

с

Работа выполнена в Вычислительном Центре АН СССР

Научный руководитель - доктор физико-математических наук, профессор А.Ф.Кононенко

Официальные оппоненты: доктор физико-математических наук, профессор Ю.Н.Павловский кандидат физико-математических наук Н.С.Васильев

Ведущее предприятие - Институт проблем управления АН СССР

в /3 часов на заседании специализированного Ученого совета Д002.32.05 по присуждению ученой степени физико-математических наук при Вычислительном центре АН СССР (Москва, В-333, ул. Вавилова, 40, конференц-зал).

С диссертацией можно ознокомиться в библиотеке института.

Защита диссертации состоится

Автореферат разослан

Ученый секретарь специализированного совета кандидат физ.-мат. наук

В.А.Бушенков

Построение адекватных математических моделей социально -экономических систем и принятие решений на основе этих моделей -задача чрезвычайно сложная. Обычно эти модели содержат огромное число факторов. Это делает модель, с одной стороны, необозримой, с другой стороны, из-за большой размерности большинство задач на данной стадии развития вычислительной техники фактически невозможно или нецелесообразно решать как единые, и потому приходится разбивать их на частные задачи, затем увязывая их решения.

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

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

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

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

игрока, обладающего правом первого хода, при агрегированной и полной информации совпадают.

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

Методами исследования, используемыми в работе, являются математические методы: теория игр, теория групп Ли.

Все основные результаты, выносимые на защиту, получены лично автором.

Основные результаты диссертации были доложены в семинарах по исследованию операций в ВЦ АН СССР, на семинаре в Институте проблем управления АН СССР и на Всесоюзном совещании по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации (Алма-Ата, 1981 г.). Основные результаты диссертации опубликованы в 5-ти работах.

Основные результаты, выносимые на защиту:

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

2. Для широкого класса статических иерархических игр найдены условия точного агрегирования информации о выборах игрока (игроков) нижнего уровня.

3. Для разных классов динамических игр найдены условия точного агрегирования информации о состоянии системы.

4. Разработан новый подход к проблемам принятия решений в

х^ЧОеЗЦ : P1 (1^(7),у,Т)> вир F1 (x1 ,у,Т)-е;

х1еХ1

xf^O«^ : x^e(y)eX^(y,T), F1 (^Б(у),y,T)> sup P1 (x, ,y,T)-e;

xieX«(y,T)

Teopeual.B сформулированных условиях максимальный гарантированный выигрыш игрока 1 в игре Г^ равен 72=тах(К(Т),М(Т)]. Получение этой величины с точностью до а обеспечивает ему стратегия х^(•):

, если у=у£ ,К(Т)^М(Т), х®Е(у), если уеЕ2(Т)Д(Т)<М(Т),

х^е(у) в остальных случаях.

Теорема Z является аналогом теоремы 1 при незначительном изменении правил поведения игрока 1.

В §2 рассматриваются правильные (частично согласованные) агрегированные игры г|. Эта игровая задача редуцируется к значительно более простым оптимизационным задачам на исходных и агрегированных множествах выборов. При этом находятся максимальный гарантированный результат и соответствующая оптимальная (е-оптимальная) стратегия игрока 1.

Введем следующие обозначения:

D' (T)={(x1fy)e Х^КТ) | Р2(х1>у,Т)^Ь2(Т)};

К' (Т)= Sup Р^х^у.Т); ЩтУ-замыкание множества D(T). (z1ty)eD'(Т)

Определение 1. Агрегированная игра называется 1равильной (частично согласованной), если D(Т)?£ в и имеют лесто равенства т|=К(Т)=К'(Т).

ТеореыаЗ. Пусть выполняются условия теоремы 1 и Э(Т)И о, D(T)=D'(Т). Тогда агрегированная игра rf; правильная,

т.е. максимальный гарантированный выигрыш игрока 1 равен

т

72=К(Т)=К'(Т). Получение этой величины с точностью до Зе обеспечивает ему стратегия х^(•)еХ1:

р р

х* , если у=у ,

ЗЦ (У)=

xij^y), если у^уЕ

В §3 даются необходимые и достаточные условия точного агрегирования в частично согласованных играх Г^.

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

1^= шах min IgU.j.Xg); D={(x1 ,х2)еХ1 I i2(x1 .х^ьЛ; XgeXg X,eX^ ^ ' *

D'^.ig)^«^ j i2(x1 .Xg)^^; = ^ max^ ^ ^(x^xg);

I e о p e u к s 4, Пусть выполняются условия теоремы 1 и

следующие условия: Ъф&, D =D', L2(T)=I2- Тогда для того, чтобы

агрегирование было точным, необходимо и достаточно, чтобы выполнились следующие условия:

для любого числа е>0 , 3(x^,x|)eD': 1, К'-е,

x^Arg min f1 (xf,x2)^ х£~(х®,т(х®),Т).

В работе приводится более детальная расшифровка условий точного агрегирования теоремы 4.

В §4 на основании основных результатов теории групп Ли да-

ются достаточные условия точного агрегирования в играх, рассмотренных в §§1,2.

Пусть выполнены условия теоремы 1. Кроме того, пусть непрерывный оператор Т(•) и множество определены следующим образом: Т(-)=(г1(•),...,, Х2=|х2еХ^ | р1(х2)^Ь1, 1=17р },

где ^(О, 1=1 ,г , •), 1=ТТр, непрерывно диффернцируемые, а

1=1 ,г еще и функционально независимые функции на Х^ функции !.,(•) , 12 (■ ) непрерывно диффернцируемые; векторы

1,Л=1,2 , дц>±/дх2 , 1=1 ,р, не равны тождествственно нулю, Х^-компактное множество.

Рассмотрим непрерывную грушу в преобразований пространства Е11"1""1 в себя, каждое преобразование )=(в1 (•))

Х^ (Х^ ), Х^ =в2(Х1,Х2), (Х.,^), (х^ ,х^)бЕп+т которой

обладает свойством ,22) 3=772 ,

ф±(б2(х1,х2))=ф.(х2) , 1=ТТр, т.е. функции £.,(•), Г2(-),

Ф^(*) , 1=1 ,р, являются инвариантами группы 0.

Найдем подгруппу С группы й такую, что функции Г1(•), ') » 1=1.Р. являются ее инвариантами и любой другой инвариант группы С выражается в виде суперпозиции функций £2(■), ф1(0, 1=ТТр .

Находятся инфинитезимальные операторы группы С:

п а т а _

А.(')=Яа (х^хр)—-г-л- £ ь (х^хр)-^ , з=1 ,п+го—р , Б 1=1 1,8 1 ^ ах^ к=1 к,в 1 ^ ах£

которая является линиейно независимой и якобиевой, т.е. (А.,А.) = А.А.-А.А.=0, 1,3=1,п+т-р. Здесь р -ранг матрицы Якоби для функций 11(•), Г2(•), Ф±(•), 1=Т7р на Х1. Предполагается, что ранг этой матрицы для у(х1,х2)еХ1*Х2 равен р. Эта

система операторов в силу обратной второй основной теоремы 1 ^

Ли ' определяет (п+т-р) - параметрическую группу Ли С. Это значит, что для некоторой окрестности У(х1,х2) каждой фиксированной точки (х.| ,х2 )еХ1 'Х^ вышеизложенным способом мы можем построить соответствующую подгруппу С.

Теорема 5. При. сформулированных условиях для того, чтобы в игре Г^ рассмотренное в теоремах 1,3 агрегирование было точным, достаточно, чтобы для кавдой окрестности У(х1,х2) су ществовали не все тождественно равные нулю функции vs р(х1,х2), э=1,п+т-р, р=1 ,В, В^ш-г, удовлетворящие следующим условиям:

п+ш-р _ _

2 V (х1 ,хР )а (х.. ,х«)=0 , 1=1,11 , Р=1,В;

& п+т-р _ _ _

-7- 2 V (21,хР)Ь (х,. ,Хр)=0 , 1=1,п , к=1,т , Р=1,В; Б=1 в.р' к,з *

. т п+т-р _ _

л ^-^¡^^г"-0-3=1р=1'в:

rank

п+т-р

£ V (Х1 ,Хр)Ь (Х^Хр) s=1 S.p' ¿ k,s ¿

2

k=1 ,m

=m-r.

P=ñB

В работе также сформулированы достаточные условия точного агрегирования, если Xg не задано в явном виде (теорема 6).

В главе II рассматривается агрегированный аналог игр многих лиц, моделирующие двухуровневые веерные иерархические системы управления (ИСУ).

Рассмотрим модель двухуровневой веерной иерархической системы, состоящей из центра (игрока П0) и N элементов нижнего

уровня ( игроков П^, leí = {1,2.....Ю ), функции выигрыша и

множества выборов которых имеют соответственно вид:

1) Чеботарев Н.Г. Теория групп Ли. -М. -Л., ГИТТЛ, 1960.

Í0(X0>X), Г^.х.), UI; х0й )ex0ünxi, x^xJsE*1,

л л m.

X = (X1 .. ,XN )eX = .П X^X^E \ lei, ГД8 ФУНКЦИИ fQ(-),

•). непрерывные, а множества Xq, X^,lei, а следовательно, и Х,Х0-замкнутые и ограниченные множества в сответствующих конечномерных эвклидовых пространствах.

Рассмотрим постановку игры, где игрок П0, будет обладать только некоторой агрегированной информацией yi=Ti(x1) о выборе

х.. игрока П^, где •), lei, некоторые известные игрокам П0,П.р

m. v.

lei, непрерывные операторы, Ti(•): Е ----> Е , ri<mi, lei.

Пусть множество стратегий игрока П0 является множеством

«V (V (V •

произвольных отображений xQ(•)eXQ= П^Хд, где

X¿ = | xj(0: Е1"1--->ЕП1 I х^СГ.))^ ], У.(Т1)=Т.(Х.), lei.

Введем следующие обозначения:

Xi(y1,T1)=Xin тт1(У1); F1(x¿,y1,Ti)= max f^xj.x.);

х-Х^у-.Т.)

L^T^ шах min ^(х*^,!^), lei.

y.eY^T.)

Аналогично игре двух лиц сформулированы правила поведения и информированности игроков.

В теореме 7 §5 главы II, по аналогии с теоремой 1, найдены максимальный гарантированный результат и соответствующая оптимальная (e-оптимальная) стратегия для игрока (центра), обладающим правом первого хода.

В теореме 8 параграфа G, по аналогии с теоремой 3, рассматривается правильные агрегированные иерархические системы. Находятся максимальный гарантированный результат и соответст-

вущая оптимальная (s-оптимальная) стратегия для центра.

В теореме 9 параграфа 7, по аналогии с теоремой 4, дается необходимые и достаточные условия точного-агрегирования в частично согласованных веерных агрегировнных ИОУ.

В теореме 10 параграфа 8, по аналогии с теоремой 5, сформулированы достаточные условия точного агрегирования для правильных веерных агрегированных ИСУ.

В главе III рассматриваются многошаговые игры двух лиц с

фиксированной последовательностью ходов при агрегированной ин-информации.

Функции выигрышей игроков, fi(x,Y),1=Т72, к увеличению которых каждый из них соответственно стремится, предполагаются непрерывными, а x,v выбираются из соответствующих множеств.

Х= П Х.^, V= П Vrf, где х=(х.,... , v=(v1,... ,v)

i=1 \ i=1 in in

k- m. _

x_.eX.sE \ v_jeV.sE , 1=1 ,n, n<m, + +kn=k, m1+...+mn=m;

__lc _m mi _

X,V,Xi,Vi, 1=1 ,n - компактные множества; E^E"\E ,E , 1=1 ,n - евклидовые пространства соответствующей размерности.

Будем предполагать, что агрегированный вектор выбора игрока 2 у= (у1,.. .уп)=(Т., (vn).....Tn(vn)), при отсутствии информации о выборе у, будет известен игроку 1 последовательно в

г,- __ш. г,

п шагов, где vieVi» у^Е ri<mi, 1=1,11, а Tj_(• ):Е х—>Е ,

1=1,п -известные игрокам непрерывные на Vif 1=1 ,п, операторы. Введем следующие обозначения:

Xi=(X1,...,Xi), у±= (У1.....у±), Vi=(Y1.....7±),

Ti<V=<T1(V1 >.....(УА)), Y.)=Т±(V±),

Ч(il ))= (Х1 (vt)),... ,ХА (f ))), V;. ,Т±(У£ )nv1

V1(yi,Ti)= П Vk(yk,Tk), v.= П Vk, X,= П Xk> Т.(т.)= П Yk(Tk),

1 1 1 k=1 k k k 1 k=1 * 1 k=1 K 1 1 k=1 K K

i=T7ñ; T(.)=(T1(0.....Tn(-)), V(y,T)=JiV1(yi,T1).

Будем предполагать, что множеством стратегий игрока 1 на i-ом ходу является множество произвольных функций xi(•): i-1

Т. (К+г ) k

~ Г ~ 1 s S К. , ~ _ _ _ л _

Х.=[х1(.):Е Б-1 ----->Е 1 I х1(Х._1Д.(Т1))£Х1 ], 1=1,п.

Стратегией игрока 2 на 1-ом ходу (Kien) является v^eV^ Игрок 1, обладая точной информацией на 1-ом шаге о векторе (xi_1,yi), первым выбирает для каждого шага свои стратегии xi(') (1CUn) и сообщает х(• )=(х1 (•),••• .х^•)) в начале игры сразу на все п ходов игроку 2.

Введем следующие обозначения:

Ll(x,y,T)=Fo(х,у,Т)= max f?(x,v),

x-1 11 11 У1еГ.(Т±) 1 1 1

При известной стратегии игрока 1, в соответствии со своим правилом поведения, игрок 2 свою стратегию veV выбирает из следующего множества:

Rg(X(•),Т)=-^ YeV | f2(x(T(Y)),V)=L¿(X(T(V)),T(V),T)£

Sanaxf max Li(x.(T.(y,)),?.(y.),T);supf„(x(T(z)),z)-e(x(•))}),

где ó(-) известный игроку 1 функционал, причем <5( •)=0, если в определении R^xM.T) супремум реализуется и равен числу öQ>0 в противном случае.

Игрок 1, зная о таком правиле поведения игрока 2, выбором своих стратегий xi(-), 1=1,п стремится получить, может быть с

е'-точностью (е'>0) свой максимальный гарантированнный выигрыш.

В теореме 11 §9 главы III в этой игре находятся максимальный гарантированный результат и соответствующая оптимальная (е-оптимальная) стратегия для игрока 1.

В теореме 12 сформулирован аналог теоремы 11 при полной информации о сложившейся предыстории и о выборе второго игрока к моменту принятия решения.

В теореме 13 (§10) рассматривается многошаговые игры двух лиц с фиксированной последовательностью ходов при агрегированной информации о выборе осторожного второго игрока, где игрок 1 сообщает второму свои стратегии х^-)» 1=1,п, последовательно, т.е. только на очередной ход. Находятся максимальный гарантированный результат и соответствующая оптимальная (s-оптималь-ная) стратегия для игрока 1.

В теоремах 14,15, полученные ранее в теоремах 2 и 5 результаты для статических игр, распространены на многошаговые игры.

В главе IV исследуется вопросы агрегирования в дискретных динамических играх.

Пусть исходная динамическая управляемая система записывается в виде: х0=х°, zk+1=fk(xk,uk,vk), uk<sUk£Ep, k=Q,N-1, J1(u,v)=g1(xN), 1=172, где х^еЕ11 -вектор состояния на k-ом шаге, uk, vk -управляющие воздействия игроков 1 и 2 соответственно, u=(u0,...,uN_1), v=(vQ.....

-функции выигрыша игроков, которые описываются скалярными функциями конечного состояния системы gi(xN), 1=172. Вектор-функции fk(-). k=0,N-1 и скалярные функции (•), 1=172 непрерывны; множества Uk,Vk, k=0,N-1, замкнуты и ограничены в соответствующих конечномерных евклидовых пространствах Ер и Eq.

Пусть игроки имеют точную информацию о параметрах системы. В процессе протекания игры игрок 1 будет иметь лишь агрегированную информацию о текущим и обо всех прошлых состояниях системы, но не рассчитывает иметь полную информацию о действиях игрока 2. Эти агрегаты состояния системы определяются следующим образом: у1=Т1(х1), 1=07Н, где Т1(-):ЕП—>ЁР, г<п, 1=0^1, известные игрокам непрерывные операторы. Введем следующие обозначения:

Тк=(То.....V» Т1ГТ' Уо=то(хо>' ^=<"0....."к)'

.....V' ^Ук^^Уо0....."А»'

к

Рк (Х0' ик' 7к} к(• • ■ГО(Х0' "о' 70}.....ик'7к >'

(Пк,ук,тк) = { х^тр | (П^ ,Ук,тк)хУк,

\(Пк'Ук+1 -5к+1 > = { ?Л |

х1+1=^(х.,и.,у.), у1+1=т1+1и1+1>.

Игроки принимают решения о выборе очередных ик,7к с учетом агрегированной информации, используя в качестве стратегий

у=(у0.....^N-1 )I и(у)=(и0(у0).....%_.,(%_.,)), где

Ук=(У0,...,Ук), к=07Й, а ик(-), к=0,Ы-1, произвольные отображения соответственно из следующих множеств ик(-)е5к = | срк(•): Е(к+1)г—>ер | «рк[су0}«1п1т1(й1_1,у1_1.т1))ёик }, Введем еще следующих обозначений:

'Ум'т)=^2'Уц'т)=_ тах ):

ук+1еУк+1(uk,yk'Tk+1}

Lk(uk_1,yk,T)= Inf Ь^.у^Т), k=0,N-1. ukeUk

Рассмотрим следующую игру, и назовем ее игрой Г1у(Т). Игрок 1 выбирает и сообщает ироку 2 свою стратегию и(•), после чего игрок 2 в соответствии со своим правилом поведения выбирает произвольную стратегю v из множества

R(u(.))={veVN_., | JgWyhv^J^uiy),^,!)^., (uiyhy^.T)^

5зпах{ max f^Cü^üJ.y^.T), sup JP(и(у' ),v' )-ö(u(• ))},

v N-1

где yi+^i+^Pido.üityi),?^), yi+^Vl^VV^'V)' i=Ü7N=T, УЬ=У0=Т0(х0)}.

Функционал Q(•) известен игроку 1, причем 6(u(•))=0, есж

/

sup в определении R(-) достигается, и равен числу öQ>0 в противном случае.

Зная о таком правиле поведения игрока 2, игрок 1 выбирает свою стратегию и(•), обеспечивающую ему, может быть с s-точ-ностью (£>0), получение верхней грани своих гарантированных выигрышей.

В теореме 16 §12 главы IV в игре Г1у(Т), а в теореме 17 §13 для правильных агрегированных дискретных динамических играх находятся максимальный гарантированный результат и соответствующая оптимальная (е- оптимальная) стратегия для игрока 1.

В теоремах 18,19 сформулированы утверждения для игр с полной информацией о состояниях системы, аналогичные утверждениям соответственно теорем 16,17.

В теореме 20 §14, по аналогии с теоремой 5, сформулированы

достаточные условия точного агрегирования в динамических играх.

Основные результаты диссертации опубликованы в работах:

1. Алиев B.C., Кононенко А.Ф. О принятии коллективных решений по агрегированной информации // Всесоюзное совещание по статистическому и дискретному анализу нечисловой информации, экспертным оценкам и дискретной оптимизации ( тезисы докладов ).- Москва - Алма-Ата, 1981, с. 324-325.

2. Алиев B.C., Цветков A.B. Игра двух лиц с фиксированной последовательностью ходов при агрегированной информации // Планирование, оценка деятельности и стимулирование в активных системах: сб. трудов, М.:Институт проблем управления, 1985,

с.35-42.

3. Алиев B.C. Динамические игры двух лиц с фиксированной последовательностью ходов при агрегированной информации о текущем состоянии системы // Неантагонистические дифференциальные игры и их приложения. Межвузовский сборник научных трудов. -М.: Всесоюзный заочный машиностроительный институт, 1986, с. G3-71.

4. Алиев B.C., Кононенко А.Ф. Точное агрегирование в теоретико -игровых моделях // Сообщения по прикладной математике.-М-.: ВЦ АН СССР, 1990.

5. Алиев B.C., Кононенко А.Ф. Об условиях точного агрегирования информации в теоретико-игровых моделях // Сообщения по прикладной математике.-М.: ВЦ АН СССР, 1991.

Алиев Вагиф Судеиф оглы

Принятие решений по агрегированной информации в теоретико-игровых моделях

Подписано в печать 04.07.91. Заказ 77 Тираж 100 экз. Формат бумаги 60X84 1/16 Бесплатно

Отпечатано на ротапринтах в ВЦ АН СССР 117333, Москва, ул, Вавилова, 40