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

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

Красовский Николай Андреевич

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург - 2015

Работа выполнена в ФГАОУ ВПО "Уральский федеральный университет имени первого Президента России Б.Н. Ельцина" на кафедре, анализа систем и принятия решений

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

профессор Тарас.ьев Александр Михайлович

Официальные оппоненты: Петров Николай Никандрович,

доктор физико-математических наук, профессор, ФГБОУ ВПО "Удмуртский государственный университет" заведующий кафедрой дифференциальных уравнений

Ухоботов Виктор Иванович,

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

профессор, ФГБОУ ВПО

"Челябинский государственный университет"

заведующий кафедрой

теории управления и оптимизации

Ведущая организация: ФГБУН Институт проблем механики имени

А.Ю. Ишлинского РАН, г. Москва

Защита состоится 22 апреля 2015 г. в 14.00 на заседании диссертационного совета Д 212.285.25 на базе ФГАОУ ВПО "Уральский федеральный университет имени первого Президента России Б.Н. Ельцина" по адресу: 620000, г. Екатеринбург, пр. Ленина, 51, зал заседаний диссертационных советов, комн. 248.

С диссертацией можно ознакомиться в библиотеке и на сайте ФГАОУ ВПО "Уральский федеральный университет имени первого Президента России Б.Н. Ельцина", Ы.1.р://<Шяоуе1;.science.urfu.ru/news2/

Автореферат разослан КЗр1^ ^ 2015 г.

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

В.Г. Пименов

РОССИЙСКАЯ I ГОСУДЛРС ГВЕННАЯ I БИБЛИОТЕКА

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

Актуальность темы. Задачи игровой динамики являются адекватными моделями конкурентных ситуаций, возникающих в экономических системах. В связи с этим анализ таких задач привлекал внимание многих исследователей в России и за рубежом. Особый интерес вызывает построение таких конструкций в игровых моделях, которые, с одной стороны, объясняют механизмы взаимодействий участников, а, с другой стороны, имеют строгие математические обоснования, связанные с теоремами существования решений, построением алгоритмов поиска равновесия и доказательством их сходимости. Важным элементом в части разработки алгоритмов является возможность правильной интерпретации их шагов с предметной точки зрения. Отмстим в связи с этим, что теория игр является стремительно развивающейся отраслью математики в многочисленных научных школах. Представленная диссертационная работа выполнена в рамках методов и подходов, разрабатываемых в Уральской школе оптимального управления, созданной Н.Н.Красовским. Основные результаты диссертации получены на основе конструкций позиционных стратегий игроков. Качественной особенностью работы является развитие этих конструкций в рамках идеи декомпозиции алгоритмов поиска равновесия. В работе рассмотрены модели аукционов и биматричных игр, для которых предложены строгие решения и разработаны декомпозиционные алгоритмы поиска равновесия. Все модели иллюстрируются конкретными игровыми ситуациями, возникающими в экономических приложениях. Для этих примеров проведена эконометрическая калибровка параметров игровых моделей и построены динамические равновесные траектории. Показано, что динамические равновесные траектории обладают лучшими качественными свойствами, чем решения статических игр.

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

Математический аппарат диссертационной работы основан на методах теории оптимального управления и конструкциях обобщенных решений уравнений Гамильтона-Якоби, развиваемых в школе H.H. Красовского. Основу этого аппарата составляют понятия стабильных мостов, введенных в рамках строгой формализации задач управления в условиях неопределенности в работах H.H. Красовского и А.И. Субботина1. В работе используются подхо-

1 Красовский H.H., Субботин А.И., Почиционяые дифференциальные игры. М.: Наука, 1974. 456 с.

ды к построению динамических равновесных решений в неантагонистических позиционных дифференциальных играх, развитые в монографии А.Ф. Клейменова2 на основе конструкций универсальных позиционных стратегий H.H. Красовского. Для построения аналитических решений в эволюционных играх в рамках подхода, предложенного A.B. Кряжимским и Ю.С. Осиновым3, применяются дифференциальные неравенства, определяющие обобщенные минимаксные решения уравнений Гамильтона-Якоби в монографии А.И. Субботина4. Используются конструкции принципа максимума Л.С. Понтрягина5 и его модификации для задач с бесконечным горизонтом, развитые в работах С.М. Асеева и A.B. Кряжимского6.

В аспекте развития теории оптимального управления и теории дифференциальных игр существенными являются работы С.М. Асеева, Р.В. Гам-крелидзе, М.И. Зсликина, A.B. Кряжимского, А.Б. Куржанского, П. Варайя, A.A. Меликяна, П. Бернарда, Е.Ф. Мищенко, Ю.С. Осипова, Б.Н. Пшеничного, H.H. Субботиной, В.Е. Третьякова, В.Н. Ушакова, А.Г. Чснцова, Ф.Л. Чер-ноусько, В.И. Бердышева, Р.Айзекса, Р. Беллмана, Л. Берковица, P.E. Кал-мана, М.Дж, Крэндалла, В. Лакшмикантама, Дж. Лейтмана, П.-Л. Лионса, Ж.П. Обэна, В. Флеминга, А. Фридмана, А. Брайсона и Хо Ю-Ши.

Значительный вклад в развитие методов теории оптимального управления и дифференциальных игр внесли Э.Г. Альбрехт, Б.И. Ананьев, И.М. Ананьев-ский, A.B. Арутюнов, В.Д. Батухтин, Ю.И. Бердышев, В.И. Благодатских, H.H. Болотник, В.Г. Болтянский, С.А. Брыкалов, Ф.П. Васильев, Р.Ф. Габа-сов, Н.Л. Григоренко, М.И. Гусев, A.A. Давыдов, A.B. Дмитрук, В.И. Жуковский, С.Т. Завалищин, А.Д. Иоффе, Ф.М. Кириллова, A.B. Ким, А.Ф. Клейменов, В.Б. Колмановский, А.И. Короткий, В.Б. Костоусов, Е.К. Костоусова, A.A. Красовский, А.Н. Красовский, Ю.С. Ледяев, М.И. Логинов, Н.Ю. Лу-коянов, В.В. Мазалов, В.И. Максимов, A.A. Милютин, М.С. Никольский, О.И. Никонов, А.И. Овсеевич, B.C. Пацко, А.Г. Пашков, H.H. Петров, Л.А. Пстросян, В.Г. Пименов, Е.С. Половинкин, С.А. Решмин, Д.А. Серков, А.Н. Сесекин, В.В. Стружанов, A.M. Тарасьев, Г.А. Тимофеева, В.М. Тихомиров, Е.Л. Тонкой, В.И. Ухоботов, Т.Ф. Филиппова, A.A. Чикрий, C.B. Чистяков, А.Ф. Шориков, М. Барди, E.H. Баррон, А. Бенсусан, Дж. Варга, И.К. Доль-четта, М. Ишии, Р. Йенссн, П.В. Кокотович, Е. Роксин, П.Е. Соуганидис, М. Фальконе, Л. Чезарс, Ф.Е. Удвадиа и многие другие ученые.

Важное место в диссертации занимают декомпозиционные алгоритмы поиска равновесных решений в динамических неантагонистических играх. Эти

2Клейыенои А.Ф., Неантагонистические позиционные дифференциальные игры. Екатеринбург: Наука, 1993. 184 с.

'Кряжиш.киЯ Л.В., Осипов Ю.С., О дифференциально-эволюционных играх // Тр. Мат. ин-та РАН. 1995. Т. 211. С. 257-287.

4Субботин А.И., Минимаксные неравенства и уравнения Гамильтона-Якоби. М.: Наука. 1991. 214 с.

''Понтрягин JI.C., Болтянский В.Г., ¡Ъшкралидэе Р.В., Мищенко Е.Ф, Математическая теория оптимальных процессов. М: Наука, 1969. 392 с.

6Асе<ш С.М., Крнжимский A.B., Принцип максимума Понтрягина и задачи оптимального экономического роста // Труды МИАН, 2007. Т. 257 С. 5-271.

исследования осуществляются в рамках теории эволюционных игр, в частности, на основе подходов, развитых в работах H.H. Воробьева, A.B. Кря-жимского и Ю.С. Осинова, JI.A. Петросяна и В.В. Мазалова, Р. Аксельрода, Т. Башара и Дж. Олсдера, У. Зангвилла и Ч. Гарсиа, Ю.М. Каниовского и Х.П. Янга, А. Нентьеса, С. Смэйла, Д. Фридмана, Д. Фуденберга и Д. Крейса, Дж. Хофбауэра и К. Зигмунда, X. Эхтамо и Р.П. Хамалайнена.

Большое внимание в диссертации уделяется построению обобщенных минимаксных решений уравнений Гамильгона-Якоби на основе конструкций дифференциальных неравенств для производных по направлению и сопряженных производных, разработанных в трудах А.И. Субботина.

Результаты диссертации существенным образом опираются на методы теории выживаемости, развитые в работах Ж.П. Обэна. Важную роль в направлении разработки численных методов построения множеств достижимости управляемых систем играют исследования В.Н. Ушакова и его сотрудников. Отметим здесь работы A.B. Куржапского, М.С. Никольского, Е.С. Половин-кина, Ф.Л. Черноусько и их сотрудников по оценке областей достижимости динамических систем.

Модели математической экономики и финансовой математики служат важными приложениями для теории игр. В последнее время увеличился интерес к динамическим постановкам игровых задач в науках по окружающей среде, в моделях игровых взаимодействий участников рынка и теории инвестиций. Этому направлению посвящены работы лауреатов Нобелевской премии К. Эрроу, Л.В. Канторовича, Т. Шеллинга, Р. Ауманна, Л. Шепли.

Прикладным аспектам теории игр в моделях экономики окружающей среды посвящены труды Т. Купманса, У. Нордхауса, Ф. Вирла, А. Нентьеса, М. Хойля, П. Чандера и X. Тулкенса.

Финансовые составляющие игровых моделей отражены в работах Нобелевских лауреатов Г. Марковица и У. Шарпа. Важные вопросы динамики финансовых потоков, используемые в диссертации, представлены в работах Л. Крушвица и Е.М. Четыркина.

Прикладными задачами теории динамических игр занимаются такие известные специалисты но оптимальному управлению как Дж. Лейтман, Ф. Удвадиа, Л. Ламбертини, С. Пикль и К. Дейссснберг. Отметим здесь также работы финского экономиста Т. Палокангаса по проблематике игрового равновесия в моделях экономического роста.

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

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

ности по реализации этих алгоритмов в практических приложениях. В работе демонстрируется эффективность гарантированного минимаксного подхода в построении стратегий управления H.H. Красовского и методов теории обобщенных решений уравнений Гамильтона-Якоби для конструирования функций цены в задачах с конечным и бесконечным горизонтом. Важной составляющей исследования является анализ качественных свойств равновесных траекторий, порожденных декомпозиционными стратегиями управления. Разработанные декомпозиционные стратегии управления обеспечивают сдвиг решений от классических равновесий по Нэшу к равновесным решениям с лучшими показателями качества. Алгоритмы доведены до программных комплексов, работа которых продемонстрирована на динамических моделях экономики и теории инвестиций.

Методы исследования. В работе используются методы теории дифференциальных игр, разрабатываемые в школе H.H. Красовского. Для построения динамики моделей используются подходы из теории эволюционных игр для больших групп популяций. Применяются конструкции теории исследования операций, выпуклого и негладкого анализа. Особую роль в исследованиях выполняют методы, основанные на свойствах дифференциальных неравенств в теории обобщенных решений уравнений Гамильтона-Якоби.

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

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

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

Апробация работы. Основные результаты диссертации докладывались на международных и всероссийских конференциях: XVI Уральская международная конференция молодых ученых по приоритетным направлениям развития науки и техники (Уральского государственного технического университета - УПИ, г. Екатеринбург, 24 25 мая 2009 г.); Международная конференция "Актуальные проблемы теории устойчивости и управления" (APSCT' 2009) (Институт математики и механики УрО РАН, г. Екатеринбург, 21-26 сентября 2009 г.); научный семинар "Проблемы динамического управления" кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова (г. Москва, 12-15 октября 2010 г.); Международная конференция "Динамика систем и процессы управления" (SDCP'2014) (Институт математики и механики им. H.H. Красовского УрО РАН, г. Екатеринбург, 15-20 сентября 2014 г.). Результаты обсуждались также на научных семинарах отдела динамических систем Института математики и механики им. H.H. Красовского УрО РАН; на научных семинарах кафедры анализа систем и принятия решений Уральского федерального университета им. первого Президента России Б.Н. Ельцина; на научных семинарах кафедры информационных технологий и математического моделирования Уральского государственного аграрного университета.

Публикации. Основные материалы диссертации опубликованы в семи работах. Из них три публикации из списка ВАК [1-3], одна публикация в сборнике научных трудов МГУ (6], одна публикация в трудах международной конференции молодых ученых [4] и два тезиса докладов [5,7]. В совместных работах [1,2,5 7] научному руководителю A.M. Тарасьеву принадлежат постановки задач, а основные результаты получены автором. В совместной работе [3] научному руководителю A.M. Тарасьеву и академику РАН A.B. Кряжим-скому принадлежит постановка задачи, а основные результаты получены автором.

Структура и объем работы. Диссертация состой!' из введения, двух глав и списка литературы. Главы разбиты на параграфы. Нумерация утверждений и формул производится по параграфам. Объем работы составляет 127 страниц текста. Библиография содержит 222 наименования.

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

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

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

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

Первая глава состоит из параграфов 1-8.

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

щ(х) = —С4(:п) + Вг вдагЛ. (1)

Здесь символ х = (ц,..., хп) - полный вектор снижения эмиссий; С,(з:<) — функция затрат страны г на снижение эмиссий х,\ 1 Функ-

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

перенесенных на территорию страну г. Предполагается, что ац > 0 и 5^=1 < 1- Считается, что функции затрат С< выпуклы и монотонно возрастают. Кроме того, предполагается, что функции экологического эффекта В; строго вогнуты и монотонно возрастают, а также имеют уровень насыщения од, который остается постоянным в интервале [од, см). Считается, что функции и В{ дважды дифференцируемы, и выполняются следующие условия:

С?(*0>0, С?(а:0>0 (а* > 0),

В,'(од)> 0, 5,"(од) < 0 (0 < од < од), В,'(од) = 0, (од > од).

В силу этих условий функции полезности Wi являются строго вогнутыми функциями.

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

го эффекта основаны на реальных данных7, 8, значения которых показывают, что затраты по снижению эмиссий значительно различаются для игроков: для стран Восточной Европы затраты значительно дороже.

Во втором параграфе дается определение конкурентного равновесия по Нэшу для модели торговли эмиссионными квотами.

Определение 1. Вектор снижения эмиссий xN — (х^,... является равновесием по Нэшу, если для него выполняется система равновесных условий

maxw>t(xf, = Wi(x... .. ,х%),

Xi>u (2)

t= l,...,n.

Так как функции Wi строго вогнуты, отношения (2) эквивалентны тому,

дщ(х")

что все частные производные —-—— в равновесии должны быть равны 0:

aXi

g(x»)=0 (i = l.....»)-

Для модели с двумя игроками аналитически получены выражения для точек равновесия по Нэшу.

В третьем параграфе дается определение точек кооперативного максимума по Парето.

Определение 2. Вектор arp = (if,..., называется максимумом Парето, если для любого другого векторах ф аг найдется компонента j, для которой wj(x) < Wj(xp).

По теореме Гермейера (см. ?) для строго вогнутых функций и»< множество точек Парсто совпадает с множеством всех решений параметрического семейства задач максимизации

maximize w(x,a), Х{ > 0, (3)

где символ w(x, а) обозначает функцию свертки:

п

w(x,a) = w(xi,...,xn,ati,...,an) = ^akwk(x)

k=1

при неотрициательных коэффициентах a* (fc = 1,... ,п).

Согласно строгой вогнутости Wi максимизатор в (3) описывается уравнением

¿akp(x)=0 (< = 1.....п). (4)

*=i OXi

7EUcrmuo A.D., Decuux A., Analysis of Post-Kyoto C02 Emissions Trading Using Marginal Abatement Curves // Joint Program Report Series. Cambridge: Massachusetts Institute of Technology, 1998. Report No. 40. 32 p.

"Tol ft., The Benefits of Greenhoii.se Gas Emission Reduction: an Application of FUND // Working Paper FNU-C4. Hamburg: Hamburg University, 2005. 33 p.

Для случая двух игроков дано аналитическое описание множества точек максимума по Парето.

В четвертом параграфе приводится доказательство того, что в рассматриваемой модели существуют точки максимума по Парето, доминирующие равновесие по Нэшу по всем критериям.

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

Определение 3. Назовем рыночным равновесием вектор положительного снижения эмиссий хм = (х^,..., если для каждого игрока г функция и>,(Ахм) (X > 0) достигает, максимума при А = 1,

хм = &^тах{ь>1{\хм) : Ххм, А > 0},

Л=1= 0 (» = 1,...,п). (5)

■что эквивалентно соотношению йт{{Ххм)

¿X

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

м

игрыша достигается в точке рыночного равновесиях при поиске на направлении, порожденном этим равновесием.

Соотношение (5) показывает, что точка хм является решением системы уравнений

(Уш,(х),х)=0 (< = 1,...,п). (С)

Учитывая определение функции полезности (1), систему уравнений (6) можно представить как

-х{СЦх{) + а^хЛ В[ а^х Л =0 (• = 1.....п). (7)

/ 4=1 /

Уравнения (7) описывают множество п кривых. Они показывают количество снижения эмиссий Х{, которое желает осуществить игрок г взамен на ответное снижение которое он получает благадаря снижению

эмиссий всеми другими игроками. Параметр

Г" ,

Р» = Р<(д) = 7 ' (8)

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

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

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

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

Алгоритм представлен в виде аукционного процесса, который реализует декомпозиционную конструкцию поиска равновесия при дефиците информации. Аукционер предлагает для каждой страны обменные курсы определяющие количественное снижение эмиссий Х{ на собственную территорию, которое страна i получит за счёт снижения собственных эмиссий на одну единицу. Игроки отвечают одновременно, указывая снижение эмиссий, которые они желают произвести, за предлагаемую цену р* на основе своих линий наилучших ответов. Аукционер учитывает предложенные странами-участниками снижения эмиссий и формирует по ним новые цены. Отметим, что участники отвечают снижением эмиссий, опираясь лишь на свои функции полезности и предложенные им конфиденциальные цены.

Алгоритмы реализованы в программе МАТЬАВ и сводятся к интегрированию нелинейных систем дифференциальных уравнений. Проведено сравнение результатов предложенных численных алгоритмов и аналитических решений. Сравнение показывает высокую точность численного метода, который дает практически идентичные результаты аналитическому решению.

Полученные результаты представлены на рис. 1, где показаны ситуация равновесия по Нэшу (МЕ), множество точек максимума по Парето (РМ), линии реакции конкурентов (ВЯ\ и ВЛг), точка рыночного равновесия в их пересечении (МЕ), начальная точка (1Р) и траектория алгоритма {ТА), сходящаяся к рыночному равновесию.

п 21 20 19 18 17 16 15 14

0 0.5 1 1.5 2 2.5

Рис. 1. Поиск рыночного равновесия.

В восьмом параграфе представлено доказательство локальной устойчивости рыночного равновесия для динамики алгоритма. Доказательство основано на проверке критерия Сильвестра для матрицы Якоби правой части динамической системы.

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

Вторая глава состоит из параграфов 9-14.

В девятом параграфе рассматривается эволюционная игра с ненулевой суммой с биматричными функционалами выигрыша на бесконечном интервале времени. Для построения эволюционно - игровой динамики используется дифференциально-игровой подход. Дастся описание динамики для больших групп участников в виде дифференциальных уравнений А.Н. Колмогорова. Обосновывается возможность управления динамикой для каждой из групп игроков. Управляющие параметры интерпретируются как сигналы участникам групп по изменению стратегий поведения.

Рассматривается система дифференциальных уравнений, которая описывает динамику поведения двух групп (коалиций)

* = + " (Ю)

у = -у + у. 4 1

Здесь параметр х, 0 < х < 1, есть вероятность того, что произвольно выбранный игрок из первой группы придерживается первой стратегий (соответственно, (1 — х) есть вероятность того, что он придерживается второй стратегии). Параметр у, 0 < у < 1, означает вероятность выбора первой стратегии игроком из второй коалиции (соответственно, (1—у) - вероятность того, что он придерживается второй стратегии). Управляющие параметры и и V удовлетворяют условиям 0 < и < 1, 0 < и < 1, и могут быть интерпретированы как сигналы, рекомендующие смену стратегий игроками. Например, значение и = 0 (ь = 0) соответствует сигналу: "сменить первую стратегию на вторую". Значение и = 1 (« = 1) соответствует сигналу: "сменить вторую стратегию на первую". Значение и = х {и = у) соответствует сигналу: "сохранять предыдущую стратегию".

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

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

<м(х(Т),у(Т)) = aux{T)y(T) + а12х(Т)( 1 - у{Т)) + а21(1 - х(Т))у(Т)+ +022(1 — х(Т))(1 — у(Т)) = САх(Т)у(Т) - ац(Т) - а2у(Т) + an,

(Н)

(12)

дв(х(Т),у(Т)) -Ьцх(Т)у(Т) + Ь12х(Г)(1 - у(Т)) + - *(г))у(:г)+ +Ы1 - х(Г))(1 - у(Т)) = Свх(Т)у(Т) - 01Х(Т) - р2у(Т) + Ь22.

в заданный момент Т. Здесь параметры С а, <*ь °2 и Сд, 01, /32 определены в соответствии с классической теорией биматричных игр?

С а — оц - 012 - о21 + а22, «1 = 0,22 — ац, а2 = а22 - а21,

Св = Ьц - Ь12 - 621 + Ьг2,

01 = Ью-Ь\2, 02 = Ь22 - 1>21.

"Глобальные" интересы ^ коалиций определяются как многозначные (двузначные) функции, образованные нижними и верхними пределами

"Воробьев H.H., Теория игр для экономистов-кибернетиков. М.: Наука, 1985. 271 с.

средних значений

3А = («(О. «(О) = Итт£ ^

/4 = /лМО.^О) = Итвирдл(1(*).У(<)).

г-¥оо

^ [¿в' /в]'

/в = ^вМО.иО) = (14)

7+ = ^(х(-),у(-)) = 1ипаир5в(а;^),г/(4)),

посчитанных для траекторий (х(-),у(-)) системы (10).

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

Представим определение динамического равновесия по Нэшу из класса замкнутых стратегий (обратных связей) и = и(Ь,х,у,е), V = ь(Ь,х,у,е) для игры с ненулевой суммой с динамикой (10) и многозначных функционалов выигрыша (13), (14).

Определение 4. Пусть е > 0 и (х0, уо) € [0,1] х [0,1]. Пара обрат-пых связей 17° = и°(<, х, у, е), Vго = ий(Ь,х,у,е) называются равновесием по Нэшу в начальной точке (хо,уо), если для любых других обратных связей и = и(1,х,у,с), V = 1>(р,х,у,е) выполняются следующие условия:

для всех траекторий

(*°(0.2/°(0) € Х(хо,уо,и°,У°),

ЫО.УгО) € Х(хо,уо,и°,У) выполняются неравенства

2(0)-е.

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

Динамическое равновесие по Нэшу может быть построено в рассматриваемой модели аналогично конструкциям из работ А.Ф. Клейменова, Для этого соединим "позитивные" обратные связи и°л,Уд и "наказывающие" обратные

связи иав, ь*д в равновесной стратегии. Оказывается, что пара обратных связей f/° = uü(t, х, у, е), V° = v°(t, х, у, е), соединяющая вместе "позитивные" обратные связи и°А, v°B и "наказывающие" обратные связи и°д, vA в соответствии с соотношениями

U° = u°(t,x,y,e) { "ДО- , - < -(15)

"" ' у Ug(x,y) в противном случае, х '

V0 = v°(t,x,y,s) ( , ^ - ^(0.^(0)11 < (16)

vi / ^ vA{x,y) в противном случае v '

является динамическим е-равновесием по Нэшу.

В десятом параграфе рассматриваются вспомогательные дифференциальные игры с параметрическим терминальным функционалом платы. На основе метода характеристик для уравнений Гамильтона-Якоби строятся функции цены для терминальных дифференциальных игр. Решения параметрического семейства терминальных дифференциальных игр получены аналитически в виде кусочно-гладких конструкций. Для поверхностей негладкой склейки функции цены проверяются дифференциальные неравенства для производных по направлению из работы А.И. Субботина10 и сопряженных производных из работы А.И. Субботина и A.M. Тарасьева11

Функции цены Wi(T,t,x,y),i = 1,2, терминальных игр определяются как величины соответствующих максиминов (минимаксов)

Wi(T,to,Xo,yo) = max min gA(xi(T),yx(T)) = "(«■*.») (n(-).Vl(-))

= min max. gA{x2(T),y2(T)),

v(t,x,y) (*>(•),!/>(•))

w2(T, to, x0l Уо) = max min дв(х2(Т),у2{Т)) = v(<.z.i/) (иО.Ы))

= min max дв(х\(Т),у\(Т)) »(t.*.v) (ïi(-).yi(O)

для каждого начального положения (¿о> хй\ Уо)- Здесь траектории (xi(-), у\(-)) порождаются обратной связью u(t, х, у, е) и произвольными поведениями v(t). Траектории (хгО.ЗйО) порождаются обратной связью v(t,x, у, е) и произвольными поведениями u(t) из начального положения (ioi^Oilto)-

В точках дифференцируемости функции цены удовлетворяют дифференциальным уравнениям в частных производных первого порядка типа Гамильтона - Якоби. Функции цены удовлетворяют также краевым условиям при t = T.

Согласно работам А.И. Субботина функция цены Wi(T,t,x,y), например, первой задачи совпадает с обобщенным (минимаксным, вязкостным) решением уравнения Гамильтона-Якоби, которое является единственным и опреде-

10Субботин А.И., Минимаксные нераненс-гпа и уравнения Гамильтона-Якоби. М.: Наука. 1991. 214 с.'

"Субботин А.И., Тарасьеи A.M., Сопряженные производные функции цены дифференциальной игры '// Докл. АН СССР. 1985. Т. 283, 3. С. 559-5G4.

ляется терминальным краевым условием и нарой дифференциальных неравенств для сопряженных производных 0*и>1 и Д.Ш1

1Ую1{Т,1,х,у)\(з) > Я(х, у, з), (17)

П.и>1(Т,Ъх,у)1(з) < И(х,у,а), (18)

(Ь,х,у) е х (0,1) х (0,1), 8 = (яьва) € К2.

Сопряженные производные О'гиу и и Гамильтониан Н заданы фор-

мулами

£Гп)1(Т,Ь,х,у)\{з) = вар «в, Л> - в_1«1(Т, х, у)|(1, Л)), леи3

Я.и^Т, «,*,»)!(*) = Ш4<я,Л> - д+Ул(Т,1,х,у)\(1,к)),

д-МТ^хлЖЪН)) =

.. . д У)!(Г, * + + + М2) - ^(Г, X, у)

= 11Ш 1111--;——-,

¿10 6

= lim sup s\o

a+wi(T,t,x,y) |(i, л)) = i + S,x + Shuy + Sh2) - Wj (Г, i, X, y)

#(x, у, s) = — Six — 32У + ^^ + Q^i^j S2V-

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

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

Функция цены строится для дифференциальной игры с мультитерминальным функционалом выигрыша

GA{x{-),y{-)) = Jtni+gogA(x(t),y(t))- (19)

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

sup inf inf o,i(2;i(a),yi(a)) = «(tAlw) (*,(■),Ы)) '<*0.+°c|

= inf sup inf влШ^.УгМ) =

= lim min max min дл(х2(3),У2(з)) = („(.),„(.)) «И.Л v

= lim max min min ita(zi(s),yi(a)) =

= wA{to,xo,yo) = wA(xo,yo)-

Здесь траектории (®1(-))2л(-)), {х2{-),у2{-)) генерируются из начального положения (<0)Яо,уо) обратными связями и(1,х,у,е), у(1,х,у,е) максимизирующих и минимизирующих игроков соответственно, и произвольными управлениями их ошюнетнов.

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

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

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

В четырнадцатом параграфе рассматриваются модели динамических би-матричных игр и строятся их решения на основе предложенного подхода.

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

Показано, что равновесные траектории в этой модели сходятся к точке пересечения линий переключения гарантирующих стратегий. На рис. 2 показаны ситуация равновесия по Нэшу ЫЕ, линии переключения К А и КВ, точка рыночного равновесия в их пересечении МЕ, начальные точки 1\, 12, /з и траектории алгоритма Т\, Т2, Тз, сходящиеся к рыночному равновесию. Видно, что новая точка равновесия МЕ существенно отличается от точки статического равновесия по Нэшу NEI и значение обоих функционалов выигрыша в новой точке лучше, чем в старой.

1 0.8 0.6 0.4 0.2 0

-0.3 -0.1 0.1 0.3 0.5 0.7 0.9 1.1 1.3

V

У '1 КА /

М1 Т / 1 / 1 2 ®

> / - 2

М1 . ж

кв \— т г 3 )

X

Рис. 2. Равновесные траектории в случае единственного статического равновесия по Нэшу.

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

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

На рис. 3 показан случай с тремя ситуациями равновесия по Нэшу N1, N2, N3. Показаны траектории Т\, Тз, Т4, которые стартуют в начальных точках /ь ¡2, /3, и, лежащих в качественно различных начальных областях. Их поведение можно охарактеризовать следующим образом. Они встречаются с линиями переключения К А или КБ, а затем скользят вдоль них до тех нор, пока не достигнут границ квадрата, где заканичвают движение.

У = 0.83 "з

УА »2 Р4 / Т4

7 / 'Р2 // -- / >1 КВ

тз г • Г / 2 / 1Р1

Ув = 0.38 у - > /

хв = 0 23 хд = 0.5 $ X

-0.2 0 0.2 0.4 0.6 0.8 1 1.2

Рис. 3. Равновесные траектории в случае статического мультиравновесия по Нэшу.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Для игровой задачи аукционного типа дано определение рыночного равновесия, сочетающего свойства точек максимума по Парето и декомпозиционную конструкцию равновесия по Нэшу. Доказано, что в рассматриваемой игре имеются точки максимума по Парето, в том числе точка рыночного равновесия, которые доминируют точку равновесия по Нэшу по всем критериям.

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

3. Для биматричных эволюционных игр анализируется понятие динамического равновесия но Нэшу, которое основано на конструкциях дифференциальных игр, предложенных в работах Н.Н. Красовского и А.И. Субботина и развитых А.Ф. Клейменовым для нсанашнистических дифферен-цальных игр. Максимизирующие стратегии игроков синтезируются из функций оптимального гарантированного результата, которые, в свою

очередь, конструируются в рамках методов теории обобщенных решений уравнений Гамильтона-Якоби, предложенных А.И. Субботиным. На основе максимизирующих стратегий разработаны вычислительные алгоритмы построения равновесных траекторий в биматричных эволюционных играх.

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

Работа поддержана грантом Российского фонда фундаментальных исследований 11 01 00427-а "Алгоритмы и динамические процедуры решения в дифференциальных играх и задачах управления"; грантом государственной поддержки ведущих научных школ Президента Российской Федерации Hill 5927.2012.1 "Исследование задач управления сложными динамическими системами, дифференциальных игр, обобщенных решений уравнений в частных производных. Применение разработанных методов и алгоритмов динамической оптимизации в задачах прикладного моделирования"; программой Президиума Российской Академии Наук № 29 "Динамические системы и теория управления" в рамках проекта УрО РАН 12- П 1-1002 "Управление в условиях конфликта и неопределенности. Позиционные стратегии и гамильтоновы конструкции в задачах управления"; Международным институтом прикладного системного анализа (HASА).

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи, опубликованные в рецензируемых научных журналах, определенных ВАК

1. Kpacoecxttü H.A., Тарасъев A.M., Поиск точек максимума векторного критерия с декомпозиционными свойствами, Тр. ИММ УрО РАН, Т. 15, № 4, 2009, С. 167-182.

2. Красовский H.A., Тарасъев A.M., Декомпозиционный алгоритм поиска равновесия в динамической игре // Мат. теория игр и ее црил. 2011. Т. 3, № 4. С.49-88.

3. Красовский Н.А, Кряжимский A.B., Тарасъкв A.M., Уравнения Гамильтона-Якоби в эволюционных играх, Тр. ИММ УрО РАН, Т. 20, № 3, 2014, С. 114-131.

Другие публикации

4. Красовский H.A., Разработка алгоритмов и программных средств для моделирования сбалансированного экономического развития // XVI Уральская международная конференция молодых ученых по приоритетным направлениям развития науки и техники. Екатеринбург, 2009.

5. Красовский H.A., Тарасъев A.M., Декомпозиционные методы нахождения точек максимума векторного критерия // Актуальные проблемы теории устойчивости и управления: сб. тез. докл. Междунар. конференции. Екатеринбург, 2009. С. 93-95.

6. Красовский H.A., Тарасъев A.M., Динамическая модель поиска равновесных состояний с конкурентными и кооперативными характеристиками // Проблемы динамич. упр.: сб.науч. тр. / МГУ,- МАКС Пресс, 2010.- Вып.5.- С.127-156.

7. Красовский H.A., Тарасъев A.M., Алгоритмы построения равновесных траекторий в динамических биматричных играх // Динамика систем и процессы управления: сб. тез. докл. Междунар. конференции. Екатеринбург, 2014. С. 119-121.

Подписано в печать 10.02.2015. Формат 60*90 1/16 Бумага офсетная. Усл. печ. л. 1,5. Тираж 50 экз. Заказ № 96. Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева, 4

'5--32ií

2014271132