Равновесие угроз и контругроз при неопределенности тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Сашст-Патарбургский Государственный Университет

Ч, Г

> «О

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

Бирткова Лидия Владиславна

УДК 519.833

РАВНОВЕСИЕ УГРОЗ И КОНТРУГРОЗ ПРИ НЕОПРЕДЕЛЕННОСТИ

(01.01.09 - математическая кибернетика)

Автореферат

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

Санкт-Петербург - 1995

Работа выполнена в Российском заочном институте текстильной и легкой промышленности

Научный руководитель - кандидат физико-математических наук, доцент МУХИН Валерий Владимирович.

Официальные оппоненты; доктор физико-математических наук,

профессор БЛПГОДАТСШ- Виктор Иванович;

кандидат физико-математических наук, КУЗВТИН Денис Вячеславович.

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

Защита состоится "_____"______________ 199__ года

в час. мин. на заседании диссертационного совета К 063.57.16 по защите диссертаций на соискание ученой степени кандидата физико-математических наук Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Петродворец, Библиотечная площадь, д. 2. Факультет прикладной математики - процессов управления.

С диссертацией можно ознакомиться в научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан "_____"__________ 199__ года

Ученый секретарь диссертационного совета К 063.57.16, доктор физико-математических наук

0.Ф.Г срьковой

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Отметим два обстоятельства.

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

• "неулучшаемы" и множество их внутренне устойчиво;

• существуют в ряде случаев, когда отсутствует равновесие по Нэшу;

• наличие сиуации равновесия по Нэшу влечет существование активного равновесия, выигрыши всех игроков при котором не меньше чем в ситуации равновесия по Нэшу.

- А -

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

Учет подобного вида неопределенностей в задачах сшилсиъ-ного управления приводит к максиминному решению и гарантированному результату (максимину), б лногокритершлъных динамических задачах - к векторной гарантии *1 . Исследование конфликтных задач при неопределенности не проводилось, исключение составляет лишь гл.17 книги **' , где рассмотрение ограничено рамками концепции равновесия по Нашу. Итак, при выборе своего поведения в игре при неопределен- ности игроки должны одновременно учитывать

• диктуемый извне "характер" игры (в диссертации ограничились бескоалиционным вариантом игры и в нем - концепцией угроз и контругроз),

• возможность реализации любой, заранее непредсказуемой неопределенности.

Дополнительный учет динамики (изменение управляемых систем с течением времени) приводит к дифферекиршлъноО. игре со лногшш. учаатшнали и при неопределенноет - новому направлению теории неантагонистических дифференциальных игр. Эти игры позволяют одновременно учесть следующие три фактора:

1? наличие нескольких взаимосвязанных управляемых систем, качество функционирования каждой из которых оценивается "своим" критерием;

*} Zhukovskiy.V.I. and Salukvadze.li.E. The Vector-Valued Maxlrain. Boston, Hew York, London: Academic Press, Inc.¿1994. 404 p.

**^ Жуковский В.И., Чикрий A.A. Линейно-квадратичные дифференциальные игры. Киев: Наукова Думка, 1994. 328 с.

2? системы меняются в течение игры, а управление ими строится по принципу обратной связи;

3? на управляемые системы действует1 помехи, возмущения и другого вида неопределенности.

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

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

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

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

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

Основные результаты работы являются новыми.

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

- б -

дают возможность решать конкретные задачи экономики (как, например, это выполнено в диссертации для математической модели рынка с двумя товаропроизводителями).

Апробация работы. Результаты, составляющие содержание работы, обсуждались на союзных и международных конференциях, школах, семинарах. Они докладывались на III Международной конференции по глобальной оптимизации (Иркутск, 1992 г.), III Международной школе по многокритериальным задачам при неопределенности (Орехово-Зуево, 1994), III Международной конференции женщин - математиков (Воронеж, 1995), III Международном семинаре "Негладкие и разрывные задачи управления, оптимизации и их приложения" (С-Петербург, 1995), а также на научных семинарах института Кибернетики Академии Наук Украины и Санкт- Петербургского университета.

Публикации. По теме опубликовано 7 работ, приведенные в заключение автореферата. Все основные результаты, представленные в диссертации, выполнены автором самостоятельно.

Структура и объем -работы. Диссертация состоит из введения и двух глав, разбитых на 7 параграфов, списка литературы, состоящего из 56 наименований. Объем диссертации составляет 127 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дается обзор литературы по тема диссертации, обосновывается актуальность темы, излагается краткое содержание работы.

Первая глава состоит из 3-х параграфов и посвящена исследованию игры двух лиц

< {1,2), a£>t=i(2. >, (1)

nt

гдв х£сж - множество стратегий xt у t-ro игрока; /£ (г/ ,х£) -его функция выигрыша, определенная на множестве Х£хХ2.

В §1 на примерах выявляются негативные свойства ситуации равновесия по йэшу (SEN).

Пример 1. Пусть в (1) множества Х£=Хг=[-1Д]. а функции

выигрыша игроков /г [xt ,хг)=-з^-ь2х}хг, f2(xt ,x£)=-j?2+2xtx£. SEM

х6'={х° определятся равенствами xat - хаг = d, а соответствующие выигрыши будут fi {хе) = ci2 (i=I,2), d= cons.te[-I,I]. Тогда

в SEN xc"=(0.0) и хсгУ= (1,1) выигрыши fl{XCZi)

[1=1,2), т.е. множество SEN внутренне неустойчиво и SEN "улучшаем*" .

Пример 2. Пусть в (1) множества Х£=кп* и'

/£( 1/(1г) = Е ^J-^t^+^i1/5 (t=i.2>.

где постоянные матрицы D^£ = Dj.£ и вектора dj4e к J, штрих

сверху означает операцию транспонирования.

Доказано, что при Dlf>0 или (и) Ьгг>0 в такой игре не существует SEN; D>0 (<) означает, что квадратичная форма у'Иу определенно положительна (отрицательна).

В §2 формализуются неулучшаешв равновесия игры (1) и устанавливаются их свойства. Именно, пусть x'=(x*t ,хре Х=Х/»Хг. Считаем, что у первого игрока.имеется угроза на ситуация х , если у него существует такая стратегия , что ft (xf.x*) > >ft (г*,х*). в ответ на угрозу х^ первого у второго имеется "неполная" контругроза, если у него существует стратегия , при которой ft £ ft (z* ,х*г), и у второго имеется "полная"

контругроза, если существует такая стратегия .:г|еХ2, что одновременно с предыдущим неравенством выполняется и > >

Определение 1. Ситуацию хкеХ. назовем слеШеровскшt при K=S •(паретовсюи при К=Р, борвейновсюи при К=В, дхоффрионов-сшл при K=G, А - при Х=А) равновесиел угроз и контругроз для игры (1), если

1°. 0й максимальна по Слейтеру (соответственно, по Парето, Борвейну, Джоффриону, А-максимальна) в двухкритериальной задаче

< X, {/£(i))i=i >£>;

2°. в ответ на любую угрозу на а? любого игрока у оставшегося имеется "полная" контругроза.

Определение 2. Ситуацию х^еХ назовем слейтеровской при K=S (парегповской при К=Р, борвейновской при К=В, дхоффрионов-ской при K=G, А - при Х=А) ахти&но равновесной для игры (I), есж

1°. выполнено требование 1° определения 1; 2°. в ответ на любую угрозу на Xй любого игрока у оставшегося имеется "неполная" конругроза.

Введенные равновесия названы "неулучшаелнхи.". Связь между нзулуяшаемыми равновесиями устанавливает схема:

Неудучшаемые равновесия, как и SEN,

1? устоОчивы по отношению к отклонении от него отдельного игрока;

2? обладают свойством индивидуальной рациональности: 3? при fi=~f£ совпадают с седловъиси точном..

п .

Теорема 1. Пусть в игре (I) множества Х4=0? 1, /t(i/,i2)6C1(Rn) ((-1,2; n=nt +пг) и

1° существуют постоянная ofe(0,1) и ситуация такие, что

df, (iVd-cO/^x4) ^ (х)+(1-<*)/->(х). V г 2° функция fi{xi,x2) сильно выпукла по (1=1,2).

Тогда в игре (I) существует А-равновесие угроз и контругроз при А=(а.^.), где аа/<?=1_с'. элементы агг и агг -произвольные положительные числа. Теорема 2. Пусть в игре (I)

1°. Х£<= comp к"* и /£(х)е С(Х) (i=f,2); 2°. Z), П Z>2 * 0,

где

T>t=tx<dl\ ft{x) 2 min max f/(xJ,x£)}.

Va=(x<=X! fг(х) 2 min max Jг(х1,хг). xt <=Xt

Тогда существует паретовская активно равновесная ситуация.

Следствие I. Вывод теоремы 2 остается справедливым, если о п'

I . множества Х^сЖ 1 выпуклые компакты и fi (х) непрерывны на X = Х,хХ2 (i=I,2);

2°. функция выигрыша // (xt ,хг) вогнута по xJ и выпукла по х£\ 3°. функция выигрыша f2(xt ,хг) выпукла по х! и вогнута по х£.

В §3 выявлены преимущества неулучшаемых равновесия по сравнению с SEN. Именно,

a) множество неулучшаемых равновесий внутренне устойчиво, а сами равновесия "неулучиоелы";

b) для игры примера 2 при

D/r >0 , Vi2<0, Ъ21<0, Ъгг>0, \пХгг < Ь1гЛг1 (2)

отсутствует SEN, но существует джоффрионовское равновесие угроз и контругроз (X.J.- наибольший корень уравнения det[Dl^-JVE^ 1=0);

c) если в игре (1) выполнено 10 теоремы 2 и имеется SEN хе, то существует паретовская активно равновесная ситуация т такая, что fi (ze) (1=1,2);

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

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

линейно-квадратичной игре двух лиц при неопределенности:

< f1,2>. Е, iVt ,U2,Z), (JtlV.Z.tr.X,»^^ >. (3)

Здесь х, u£, 2 е к", «»const>0. (t„,xJ,)etO,'e)xRn, т, * х = k[t)x + Ut + иг + z, x(t„)=x„, См[0,<]; (4)

ui = {Ui 4 ui(t,x)lut(i.i)=Qt(i)r. Q.(.)<=CJlxnCO.im;

Z = (2 + z(t,x)!z(i,x)=P(t)x, P(. МЗ^ГО,«]};

•в

(fl)Cix('d) + fitij '[t]Dc/uJ It] + иг4гщгиг111+ t

*

+ z'[t]L£z[t] + x-(t)G£x(t)}dt [1=1,2),

где постоянные пхп-матршн С., D£j., L£, G£ симметричны, ситуации U = (Uj,иг) s x Иг = U.

В §4 приводится математическая модель игры (3) и ее экономическая интерпретация. Следующий §5 посвящен формализации решений игры (3). Особенность игры (3) в том, что при выборе своих стратегий U£<= Ui игроки должны учитывать возможность реализации мэбой неопределенности Ze Z. Тогда ситуация и*е и обеспечивает в игре (3) векторную гарантию J*=(Jj,Jg), если

J4 J(U\Z,t„,x„), VZe Z (здесь J(1)>JC2W£(1)>J£t2) [1=1,2) и J"HJ(2)-1JI1)>J(2)).

Далее K,I=S,P,B,G,A..

Определение 3. Ситуацию U^eii назовем R-L-рабкобесиел угроз и контругроз дифференциальной игры (3) с начальной позицией (t„,x„)ei:o,i3)xren, если существует неопределенность Z^Z такая, что

1°. ситуация U* является максимальной по К в двухкрите-риальной динамической задаче

< 2 (Z=ZL), и, iJt(U,Z>;

2°. в ответ на каждую угрозу на пару (U^.Z^) любого игрока у оставшегося имеется "полная" контругроза;

3°. неопределенность Z является минимальной по L в двух-

критериальной динамической задаче

>

При этом оптимум (максимум или минимум) по К означает при К=5 - оптимум по Слейтеру, при К=Р - по Парето, при К=В - по Борвейну, при К=С - по Джоффриону, при К=А - А-оптимум. Связь между введенными гарантирующими равновесиями угроз и контругроз на следующей схеме:

(Up.Zp)

Г Í Г I I

г т т т т

í Í Т I т

<ZB>

Í - I 1 т т

В §6 отнесены вспомогательные утверждения, используемые в §7 при построении явного вида А-А - равновесия угроз и контругроз игры (3).

Лемма 1. Пусть для игры (3) выполнены условия (2). Тогда 1? каковы бы ни были ситуация U=(U/ ,U2)elf, неопределенность z^z и начальная позиция

(t^rJeCO.^xR", |xj;¿0, (5)

в дифференциальной игре (3) в ответ на любую угрозу на пару (U,Z) любого игрока у оставшегося имеется "полная" контругроза;

2? существует постоянная cte(0,I) такая, что

Dl (cf)=of Ъп + {1-с1)Ъг1< 0, D2(a!)=d Di2+(i-of)D22< О. (6) Лемма 2. Если

^>0 ш (и) 1г>0, ' (7)

то существует постоянная fie (0,1) такая, что

Кр)=рЬ, + (i-p) 1г > 0. (8)

Рассмотрим квадратичные функционалы

(U.Z.t^.x^) = a^J, (U,Z,t,,;z,,) + a^J^tU.Z.i,,,^), (U.Z.i^.x,) = -a^J, (U.Z.t^.x,) - a^J^iU.Z.i^.z,), и вспомогательную дифференциальную игру двух лиц

< а.ш, Е+ (4). ш,г>, а(ш,2,1,,1,))НЛ1 >. (9)

Лемма 3. Если выполнены условия (2), то IIе из SEN (IIе, Ze) игры <9) является А-А-равновесием угроз и контругроз диффрэнци-альной игры (3) при любом выборе начальной позиции (i„), удовлетворяющей ограничениям (5);

Заключительный §7 посвящен способу построения гарантирующих равновесий угроз и контругроз для игры (3) с помощью метода динамического программирования и выявлению класса игр вида (3), в которых эти решения существуют.

Утверждение 1. Предположим, что

1°. выполнены условия (2);

2°. существуют постоянные ci, fie (0,1), для которых имеют место (6) и (8);

3°. система матричных уравнений типа Риккати -gji- + 9, A(t) + A'(1)9, - e^D/W) + l/tcOie, +

+ е,1Г' (0)9., + адГ1 tp)er + e^L 1 (р)Ъ(созГ' (Р)вг + + G (rf> = 0nxn, et (•6)=C(cf);

-а^ + е^Асг) + а- а)вг - в, го;' (соэ, (ря;1 (со +

+ (а() - ег(в;'(с{) + ((*)]&, -

- е^'ю) + (й)]8г + е^"' (р>ег -

- ССР) = 0^. 8г('в)=-С(р),

имеет продолжимоэ на интервал [0,01 решение (9*

(через 0ПхП обозначена нулевая пхп-матрица, С(7)=7С1 + (1-7)Сг,

С(7)=7а/ + (1-7)Ог).

Тогда для матрицы

в дифференциальной игре (3), при любом выборе начальной позиции из (5), А-А-равновесие угроз и контругроз и^си^.и^) существует и имеет вид

+ (сое; (О* (1=1,2), (11)

а соответствупцая (по определении 3) неопределенность

+ р)е£щх. (12)

Рассмотрим "обратную" задачу: построение векторной гарантии

с помощью найденной в (11), (12) пары (иА,гд).

Утверждение 2. Пусть выполнены требования 1°-3° утверждения 1. Тогда векторная гарантия <1(1)^,2 определится равенством

где пхп-матрица

St(tJ=r (f„)|c£ + fiï-'c-m'V'Or'Wd? Y(t„).

I

Здесь матрицы

г

D£(t) = ©*<î>2 ^ icÎ)D£yrJi (cf)B^(t) +

+ e*(i)L-i(P)L£L_î(P)8g(t) + g£ (i=i,2),

A(t) = A(t) - [Dj1 (d) + D^(rf)]9*(i) + L_i (P)8^(î),

матрица Y(î) является решением следующего однородного линейного матричного уравнения с непрерывными (по £) коэффициентами

= -ïÂ(t), YC^Ejj.

В заключение §7 рассмотрена игра вида (3) с "малыми" возмущениями, отличающаяся от (3) лишь тем, что управляемая система Е описывается уравнением

х = k(t)x + ut + иг + ez, x(tK)=x„, где е>0 - малый параметр. Остальные составляющие игры те же, что и в игре (3). Такую игру обозначим через Г£.

Утверждение 3. Пусть выполнены условия (2), (7) и матрицы C£çO (1=1,2).

•Тогда в игре Г£ при достаточно малых е>0 существует А-А-равновесие угроз и контругроз при матрице А из (10) и любом выборе начальной позиции (i„,хм) из множества (5)..

ЗАКЛЮЧЕНИЕ

Таким образом, в диссертационной работе получены следующие основные результаты:

1? установлены теоремы существования неулучшаемых равновесий при обычных ограничениях в теории игр;

2? получен способ построения гарантированных выигрышей (векторных гарантий) в линейно-квадратичных дифференциальных играх по фиксированным ситуации и неопределенности;

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

4? установлены коеффициентные критерии существования гарантирующих равновесий угроз и контругроз для дифференциальной линейно-квадратичной игры с "малыми" возмущениями.

Публикации по теме диссертации.

1. Бирюкова Л.В., Жуковский В.И. Гарантирующие равновесия угроз и контругроз в одной дифференциальной игре // Тез. докл. Воронежской весенней математической школы "Понтрягинские чтения - VI". Воронеж, 20-26 апреля 1995. С.13.

2. Бирюкова Л.В., Жуковский В.И. Об одном свойстве квадратичных функционалов // Тез. докл. Воронежской зимней математической школы "Современные метода теории функций и смежные проблемы прикладной матем. и механики". Воронеж, 25 янв.-1 февр. 1995. С.38.

3. Бирюкова Л.В. Равновесие возражений и контрвозражений в дифференциальной игре двух лиц // Тез. докл. III Международной конференции женщин - математиков. Воронеж, 29 мая - 2 июня 1995. С.116.

4. Бирюкова Л.В. Равновесие угроз и контругроз в одной игровой задаче при неопределенности // Сб. научн. тр.: "Программное обеспечение. Микропроцессорная техника сложных автоматических систем". Челябинск: ЧГТУ, 1995. С.7-12.

5. Бирюкова Л.В. Равновесия угроз и контругроз при неопределенности // Проблемы управления и информатики. 1995. Jfö. С.12-17.

6. Бирюкова Л.В. Неулучшаемое равновесие в одной дифференциальной игре // Сборник "Кибернетика и вычислительная техника (сложные системы управления)" Киев: ИК HAH Украины. 1995. Вып. 107. С. 25-33.

7. Жуковский В.И., Бирюкова Л.В. Векторные гарантии в игровых задачах // Тез. докл. 3-его Международного семинара "Негладкие и разрывные задачи управления, оптимизации и их приложения". С-Петербург, 26 июня - 2 июля 1995. С.32-36.

РосЗИТЛП Тираж 70 Заказ 34