Кооперация в дискретных линейно-квадратичных играх тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Тур, Анна Викторовна

• Тур, Анна Викторовна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Тур, Анна Викторовна

Оглавление

Введение

Глава 1. Линейно-квадратичные неантагонистические дискретные игры

1.1 Бескоалиционные линейно-квадртичные дискретные игры

1.1.1 Теорема о существовании равновесия по Нэшу

1.1.2 Пример

1.2 Кооперативные линейно-квадратичные дискретные

игры

1.2.1 Игры в форме характеристической функции

1.2.2 Условие устойчивости против иррационального поведения игроков

1.2.3 Условие устойчивости против иррационального поведения игроков в играх с неполной информацией

1.2.4 Пропорциональное решение

1.3 Решение дискретной игры с выигрышами игроков, содержащими перекрестные слагаемые

1.4 Пример. Планирование производства в условиях конкуренции

1.5 Пример. Игра с тремя участниками

Глава 2. Стохастические линейно-квадратичные дискретные игры со случайной продолжительностью

2.1 Бескоалиционные игры

2.2 Кооперативные игры

2.2.1 Игры в форме характеристической функции

2.2.2 ЕБ-вектор

2.2.3 Динамическая устойчивость Е8-вектора

2.2.4 Условие устойчивости Е8-вектора против иррационального

поведения игроков

2.3 Пример

Глава 3. Линейно-квадратичные дискретные игры с нетрансферабельными выигрышами

3.1 Линейно-квадратичные дискретные игры с нетрансферабельными выигрышами с предписанной

продолжительностью

3.1.1 Теорема о существовании равновесия по Нэшу

3.1.2 Парето-оптимальное решение

3.1.3 Динамическая устойчивость Парето-оптимального решения

3.1.4 Условие устойчивости Парето-оптимального решения против иррационального поведения игроков

3.2 Линейно-квадратичные дискретные игры

с нетрансферабельными выигрышами с бесконечной

продолжительностью

3.2.1 Парето-оптимальное решение

3.2.2 Динамическая устойчивость Парето-оптимального решения

3.2.3 Условие устойчивости Парето-оптимального решения

против иррационального поведения игроков

3.3 Пример. Игра стабилизации государственного долга

Глава 4. Сетевые линейно-квадратичные

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

4.1 Постановка задачи

4.2 Некооперативная игра

4.3 Кооперативная игра

4.4 Пример

Заключение Литература

Введение диссертации (часть автореферата) на тему «Кооперация в дискретных линейно-квадратичных играх»

Введение

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

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

I1J-

Фундаментальные результаты в исследовании антагонистических дифференциальных игр получены научными школами академиков JI.C. Понтрягина 124, 25, 26] и H.H. Красовского [10]. В развитие неантагонистических дифференциальных игр существенный вклад внесли А.Ф. Кононенко [9], А.Ф. Клейменов [8, 6, 7], JI.A. Петросян [15], В.И. Жуковский, Т.Н. Тынянский [4], С.В. Чистяков 1331 и др.

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

В своих работах исследовали задачи подобного типа Дж. Энгверда [48],

\47\, Т. Башар, Г. Олсдер [38], В.А. Жуковский, A.A. Чикрий [3], В. Чжан [70], П. Бернхард [41] и др. Решения некооперативных линейно-квадратичных игр двух или многих лиц в различных классах стратегий подробно рассмотрены авторами. При этом исследуются игры как с конечным временем окончания игры, так и с бесконечным. В некоторых работах рассмотрены также кооперативные игры, где в качестве принципа оптимальности берётся Парето-оптимальное решение.

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

Также очень важным является вопрос устойчивости кооперативного решения. Понятия динамической устойчивости впервые было введено Петросяном Л.А. в работе [14]. Динамическая устойчивость гарантирует состоятельность выбранного принципа оптимальности на всем промежутке игры. А в работе [66] Д.В.К. Янгом было предложено ещё одно важное свойство, гарантирующее устойчивость кооперации, это "устойчивость против иррационального поведения игроков". При выполнении этого свойства, даже при возникновении иррационального поведения игроков, другие игроки не проигрывают по сравнению с некооперативным решением. Марковкин М.В. [12] рассмотрел эти аспекты устойчивости кооперативных решений для линейно-квадратичных дифференциальных игр.

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

для кооперативных дискретных линейно-квадратичных игр.

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

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

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

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

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

2. Построение кооперативного решение линейно-квадратичных стохастических дискретных игр со случайной продолжительностью. Формулировка теоремы о динамической устойчивости полученного кооперативного решения. Вывод достаточных условий устойчивости против иррационального поведения.

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

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

5. Определение линейно-квадратичной дискретной игры на сети с управляющей коалицией. Построение некооперативного и кооперативного решения в таких играх.

Апробация работы. Основные результаты были представлены на I, III, VII Международных конференциях Game Theory and Management GTM'07, GTM'10. GTM'14 (Санкт-Петербург, 2007, 2009, 2014 гг.); на Всероссийской конференции «Устойчивость и процессы управления» (Санкт-Петербург, 2010); на XXXVIII, XXXIX, XL, XLI международных конференциях студентов и аспирантов «Процессы управления и устойчивость» (Санкт-Петербург, 2007, 2008, 2009. 2010 гг.); на 46-й Международной молодежной школе-конференции «Современные проблемы математики и ее приложений» (Екатеринбург, 2015 г.); на семинаре отдела динамических систем Института математики и механики им. Н.Н. Красовского УрО РАН; на семинарах кафедры математической теории

игр и статистических решений факультета прикладной математики - процессов управления СПбГУ.

По материалам диссертации опубликованы работы [13], [28], [29], [30], [31], [32], [63], [64]. Из них статьи [30], [32] опубликованы в журналах, входящих в список ведущих российских рецензируемых научных журналов ВАК РФ, статья [63] - в издании, входящем в международную реферативную базу гЬМАТН.

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

Первая глава посвящена линейно-квадратичным дискретным играм с бесконечной продолжительностью.

В § 1.1 приводится постановка задачи и находится решение бескоалиционной игры. Данный параграф делится на подпараграфы.

В §1.1.1 Формулируется теорема о существовании равновесия по Нэшу в линейно-квадратичных дискретных играх с бесконечной продолжительностью.

В § 1.1.2 приводится пример.

В §1.2 строятся кооперативные решения в рассматриваемом классе игр. Данный параграф делится на подпараграфы.

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

В §1.2.2 исследуется вопрос динамической устойчивости полученных кооперативных решений, а также выводятся достаточные условия устойчивости против иррационального поведения для этих решений.

В §1.2.3 выводятся достаточные условия, гарантирующие устойчивость против иррационального поведения для кооперативных решений, при условии,

что рассматривается игра с неполной информацией.

В § 1.2.4 строится пропорциональное решение.

В § 1.3 переформулируются теоремы, полученные в § 1.1.1 и § 1.2.1 для случая игры, в котором выигрыши игроков содержат перекрестные слагаемые, т.е. слагаемые, зависящие линейным образом и от управления, и от траектории.

В § 1.4 приводится пример игры с экономическим содержанием.

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

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

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

В §2.1 находится решение бескоалиционной игры. Формулируется теорема о нахождении ситуации равновесия по Нэшу в линейно-квадратичных дискретных играх со случайной продолжительностью.

В §2.2 строятся кооперативные решения в рассматриваемом классе игр. Данный параграф делится на подпараграфы.

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

В §2.2.2 в качестве кооперативного решения строится ЕЭ-вектор.

В §2.2.3 исследуется вопрос динамической устойчивости ЕЯ-вектора.

В § 2.2.4 выводятся достаточные условия, гарантирующие устойчивость ЕЭ-вектора против иррационального поведения игроков.

В § 2.3 приводится пример стохастической линейно-квадратичной дискретной игры со случайной продолжительностью двух лиц, в котором находятся все решения, описанные в главе 2, для ЕЯ-вектора проверяется динамическая устойчивость и устойчивость против иррационального поведения игроков.

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

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

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

В §3.1.2 находится Парето-оптимальное решение.

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

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

В §3.2 исследуются линейно-квадратичные дискретные игры с нетранс-ферабельными выигрышами с бесконечной продолжительностью. Находится Парето-оптимальное решение и исследуется вопрос его устойчивости. Данный

параграф делится на подпараграфы.

В §3.2.1 находится Парето-оптимальное решение.

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

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

В § 3.3 в качестве примера рассмотрена игра стабилизации государственного долга, исследуется устойчивость Парето-оптимального решения в этой игре.

Четвёртая глава посвящена сетевым линейно-квадратичным дискретным играм с управляющей коалицией.

В §4.1 приводится описание игры.

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

В §4.3 находится кооперативное решение игры.

В §4.4 рассмотрен пример линейно-квадратичной игры на сети с управляющей коалицией. Продемонстрирована неустойчивость решения.

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

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

Глава 1

Линейно-квадратичные неантагонистические

дискретные игры

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

Рассмотрим дискретную линейно-квадратичную неантагонистическую игру п лиц, состояние которой в каждый момент времени задается вектором х(к), изменяющимся согласно системе уравнений

п

х{к + 1) =А{к)х(к) + V Вг{к)Щ{к),

г=1 (1.0.1)

к > /с0, к0 Е Ть х(к0) = ж0,

где х Е Ят - вектор-столбец, щ Е К1' - вектор-столбец управления игрока г, г = 1,..., п ; А(к), Вг(к) Е %(Т+) -(тхт)и(тхг)- матрицы соответственно, х(кц) = хо - начальное состояние, 7+ - множество неотрицательных целых чисел, Z('T+) - множество ограниченных на 7+ матриц.

Обозначим через N — {1,..., п} множество всех игроков. Выигрыш игрока ъ £ N обозначим через ^(ко,хо,и), где и = (щ,... ,ип). Будем предполагать,

что выигрыш игрока г имеет вид:

00

Мко,хо,и) = ^2(хТ(к)рг(к)х(к) + и1(к)Н'г(к)иг(к)), Уг = 1,...,п, (1.0.2)

к=кд

где Рг(к) = Ргг(/е), Щк) = Щ(к) е Я (7^) - (т х га) и (г х г) - матрицы соответственно, i = 1,... ,п. Каждый игрок стремится максимизировать свой выигрыш.

Определение 1. Набор стратегий вида

{иг{к,х) = Мг{к)х, г = 1,..., п} (1.0.3)

будем называть допустимым, если выполняются условия:

1) Мг(к) Е г(Т+), г = 1,..., п;

2) Система (1.0.1), замкнутая набором стратегий (1.0.3), т. е. система

п

х(к + 1) = (А(к) + Вг(к)Мг(к))х(к)

г=1

равномерно асимптотически устойчива (при к оо) [27].

Предполагается, что игроки выбирают только допустимые стратегии вида и7(к,х) — Мг(к)х, к > ко, г = 1,...,п. Обозначим построенную выше игру Г(А;о,жо). Это обозначение показывает, что игра началась в момент времени

к = ко из состояния х(ко) = хо-

1.1 Бескоалиционные линейно-квадртичные дискретные игры

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

В качестве принципа оптимальности будем рассматривать равновесие по Нэшу [53].

Определение 2 ([53]). Набор стратегий

будем называть равновесием по Нэшу, если этот набор допустим в смысле определения 1 и имеет место

хо, иМЕ) > ^(ко, х0, иМЕ/щ), г = 1,..., п,

где щ - произвольная стратегия игрока г, такая что набор стратегий {иМЕ/щ} принадлежит классу допустимых.

Здесь {и^Е/щ} обозначает такой набор стратегий, что все игроки у ф г

ЫЕ

используют стратегии щ, а игрок г - стратегию щ.

1.1.1 Теорема о существовании равновесия по Нэшу

В работе Т. Башара и Г. Олсдера [39] была сформулирована теорема о нахождении равновесия по Нэшу в линейно-квадратичных дискретных играх с бесконечной продолжительностью в стационарном случае, когда матрицы А, Д-, Рг, Я^ постоянны на протяжении всей игры. В данном параграфе приводится аналог этой теоремы для нестационарного случая. В теореме приведены необходимые и достаточные условия для существования равновесия по Нэшу в игре Г(ко,Хо). Пусть С^+(Т+) С - множество положительных ограниченных

на 7+ матриц.

Теорема 1. Для того чтобы в игре Т(ко,хо) существовало единственное в классе допустимых равновесие по Нэшу необходимо и достаточно, чтобы си-

сгпема матричных уравнений

п п

(.А(к) + "£вг(к)мг»Е(к))Тег(к + 1)(л(ао +

г=1 г=1

- ег(к) - рг(к) - мг"Е(к)тя(к)мг»Е(к) = о, мгМЕ(к) = -{~кг{к) + в1\кШк + 1)вг{к))-1в^{к)ег{к + 1)х

х {А{к) + г = 1,... ,п

имела единственное решение {М^Е{к), Ог(к)} € Е(Т+), в виде вещественных, ограниченных матриц размерности г хт итхт соответственно, где Ог{к) - симметричны для любого г Е N, для которого выполняется:

1. Набор стратегий

{и?Е = М?Е(к)х(к), г — 1,... ,п} (1.1.2)

допустимым в смысле определения 1. 2 (-Яг(к) + В?{к)9г{к + 1 )Вг(к)) е <Э+(Т+), г = 1,..., п.

Тогда набор стратегий (1.1.2) будет являться равновесием по Нэшу в игре Г(ко,хо), при этом выигрыш игрока г в равновесии равен

¿{ко, х0, иМЕ) = -Хо9г{ко)хо, 1 = 1,...,п.

Доказательство. Необходимость. Пусть ситуация

является равновесием по Нэшу. Тогда для любых г = 1,..., п, и иг выполняется:

¿{ко,хо,иИЕ/иг) < Зг(ко,хо,иМЕ). Это значит, что и^Е является оптимальным управлением в задаче следующего

вида.

х{к + 1) = (А{к) + В3{к)М^Е{к))х(к) + Вг(к)иг(к)

Зфг

с начальным условием х(к0) = х0 и функционалом «Л(&о, ^о, иМЕ/иг). В [27] выведены условия для существования единственного оптимального управления в задаче такого типа. Согласно [27]

{и?Е = -(-Я,(А0 + В^(к)вг(к + I) Вг^к))^1 В^ (к)<дг(к + 1)(А(к)+

+ ^Г,В3(к)М»Е(к))х(к), г — 1,..., п},

Зфг

где 0г(/с) - симметричные ограниченные матрицы т-го порядка, для которых выполнены условия

п п

(А(к) + ^Вг(к)МгМЕ(к))тв1(к + 1 )(А(к) + ^Вг(к)Мгш(к))-

г=1 г=1

- 9г(к) - Рг(к) - МгМЕ(к)тЯ1(к)МгМЕ(к) = О,

М?Е{к) = -(-ад + В^(к)Эг(к + 1) Вг(к))~1 В^ (к)Ог{к + 1) х

х {А{к) + ^В3(к)М^Е(к)), г = 1,...,п,

(~ад + В?(к)вг(к + 1 )ад) € д+(Г+).

Откуда и следует необходимость теоремы.

Достаточность. Покажем, что доказательство достаточности следует из [27] Действительно, при замыкании системы (1.0.1) набором допустимых управлений {иМЕ/иг}, она превращается в систему с одним управлением:

х{к + 1) - (А(к) + ]ГВ]{к)М^Е{к))х{к) + Вг(к)иг(к). (1.1.3)

Зфг

Для и, существуют такие М^Е(к) и ©г(к) - симметричная, что для них выпол-

няется

(А(к) + ]Г вг(к)мгМЕ(к))Тег(к +1 )(А(к) + вг(к)мгМЕ(к))~

г=1 г=1

- &г(к) - Рг(к) - МгМЕ(к)тИ1(к)МгМЕ(к) = О,

мгМЕ(к) = -(-ад + в^(к)ег(к +1 )вг(к))-1в?{к)вг(к +1) X

х(А(к) + ^2вЛк)М?Е(к)), г — 1,... З¥=г

(-Щк) + вЦкШк + ВД(АО) е Я+{Т+).

Тогда согласно [10], и^Е(к) - единственное оптимальное управление для системы (1.1.3) с функционалом ¿, то есть

¿(к0, хо, иНЕ/щ) < ¿(к0, х0, иМЕ), 1 = 1,...,п.

Значит набор управлений (1.1.2) является равновесием по Нэшу.

При этом выигрыши игроков в ситуации равновесия по Нэшу будут равны:

¿(ко, хо, иМЕ) = -х1@1(к0)х0, 1 = 1,...,п.

□

1.1.2 Пример

Пусть

N = {1,2},

1 1

х(к + 1) = е~кх(к) + +

к—ко

, У^ ( Тпл {2(к + 2)2 8(к + 3)2\ , Тпл 1

Ъ = Е Ю " -Щк^?) ф) + и {к)(Ш?и{к)) ■

Тогда для нахождения равновесия по Нэшу необходимо проверить разре-

шимость системы

[к + 2) \~WTW2 (А; + 2)2 ;

9{к + 2)2 е2к(к + З)2

= 0

8(/с + 3)2 е2/с(& + 4)2

—

,-А;

(/с + З)1

М\{к) =

М2(А;) -

Заметим, что

©22(А; + 1)

_, е2(/с + 1)\

(/с + 4)2 (/с + З)2 У

= 0

1

1 +©1(/с + 1) к + 2

еЛк + 1) /к+ м2

к + 3

(& + 3)2 (А; + 2)2

1

1 02(/с + 1) /с + 3 +

/с + 2

(/с + 4)2 (к + З)2

©1(Л) -©2(*0 =

М2(к) =

(/с+1)2 2(/с + 2)2' 2(/с+2)2 3(/с + 3)2' 3(/с + 2)

е/г '

4(/с + 3)

являются решениями этой системы.

Проверим теперь является ли набор управлений

щ(к, х) = М\{к)х{к), и2(к,х) = М2(к)х(к)

допустимым в смысле определения 1:

где

1)|М1(А)|<6;|М2(А:)|<12.

2) Проверим равномерно асимптотическую устойчивость системы

х(к+1) = Н(к)х(к),

щк) = е~к _ тр. _ ЩЪ.

+оо

1[к0, х(к0)} = хТ{к)х{к) = х2(1 + Н2(к0) + Н2(к0)Н2(к0 + 1)+

к—ко

+ Н2(ко)Н2(ко + 1)Н2(ко + 2)...).

А так как Н2(к) - убывающая функция при А; € 7+, Я2(0) — 172 и < е-А:

при /с > 4 то

/[А?о, х(к0)} < х20( 1 + 172 + 174 + 176 + 178 +1710(1 + е~1) + е~2 + е~3 +...) = 4*

* (1 + 172 + 174 + 176 + 178 + 1710 (з^п) - *оР.

где р = 1 + 172 + 174 + 176 + 178 + 1710 ^ е_ ^ . Тогда

х\ < 1[к0,х(к0)] <рх1,

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

щ(к, х) = ^ и2(к, х) =

еК ек

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

(ко + I)2 7 2 + 2)2

Зх - ГоЛ2' 1/2 -

2(ко + 2)2' * о(ко + З)2

1.2 Кооперативные линейно-квадратичные дискретные игры

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

1.2.1 Игры в форме характеристической функции

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

Для определенной линейно-квадратичной дискретной игры ~Г (ко, хо) характеристическую функцию

v(S,xо) : 2N R будем строить по следующему правилу (см. [58]):

v(S,xо) = max JS(ko, xq, une/us).

uí,Í€S

Здесь

S С N, Js(k0,x0,u) = ^2Ji{ko,xQlu), где и = (щ,..., un),

i<=S

{uNE/us) = {u?EJtS, щ,г e S}.

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

В работе [12] подобным образом строится характеристическая функция для

линейно-квадратичных дифференциальных игр.

Пусть 5 = |5"|, ¿1,.. ., 13 ~ игроки, входящие в коалицию 5.

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

( щ\

ив{к) =

и

12

Вб = 1, • • • ,

Ян о

о

Яг

12

^О О ... 1иа)

(1.2.1)

со

Тогда = Е Чк^х^и) = £ (:хт(к)Р3(к)х(к) + ит3(к)Я3(к)и3(к)).

гб5 к=ко

Для построения характеристической функции сформулируем следующую

теорему.

Теорема 2. Для того чтобы существовал единственный набор стратегий

{и°(к,х) = М?(к)х, ieS},

доставляющий максимум Js(kQ,XQ,u) при фиксированном наборе стратегий

{й3(к,х) = М3(к)х, з £ 5} необходимо и достаточно, чтобы: 1. Система матричных уравнений

(А(к) + ^ В3{к)М3{к) + Вз{к)М°8{к))Твз{к + 1 ){А{к)+

+ ^2вз(к)М3(к) + Вз(к)М°3(к)) - е3(к) - Рз(к)-- М°3(к)тК3(к)М1(к) = О,

М$(к) = -(-^(/с) + ВЦ(к)Эз(к + 1)55(/с))-1^(/с)в5(/с + 1) х х{А(к) + ^В3{к)М3{к))

была, разрешима относительно {М^(к), 0з(к)}, в виде вещественных, ограниченных матриц размерности гв х т и т х т соответственно, где ©5(/с) - симметричны.

2 Набор стратегий

и

\к,х) = {й3(к,х) = М3(к)х, з 5, и\к,х) = М?{к)х, г е 5},

где Мг°(/с) - %-й блок матрицы М${к) =

в смысле определения 1.

(М°(к)) <(*)

[мЦк)]

(1.2.2)

; был бы допустимым

3. (-Я5(к) + ВТ(к)вз(к + 1)Вз(к)) е д+(Г+).

Тогда набор стратегий (1.2.2) доставляет максимум Js(kQ,Xo,u) и

Js(ko,xo,,u0) = -х%Оз(к0)х0.

Доказательство. Замкнем систему (1.0.1) допустимым набором управлений и (/с) = {Щ = Щ(к)х, j щ = Mi(k)x(k), г G S}:

x

(/с + 1) = (A(k) + 53 Bj{k)Mj(k))x(k) + 53 Bi(k)ui(k)

j£S ieS

или

ж

(/с + 1) = (A(fc) + 53 Bj{k)M3{k))x{k) + Bs{k)us{k), (1.2.3)

as

где

/

\

\Mis(k)J

Тогда систему (1.2.3) можно рассмотреть как систему с одним управлением us {к) и функционалом Js. Согласно [27], чтобы существовало единственное управление, доставляющее максимум необходимо и достаточно, чтобы:

1. Система матричных уравнений

(А{к) + 53 В3{к)Щк) + Bs{k)M°s{k))TQs{k + 1)(А{к)+ its

+ 53^(/с)М,-(А;) + Bs(k)M°s(k)) - es(fc) - Ps(fc)-

j£S

- M0s(k)TRs(k)M°s(k) = 0,

Mikfc) = -(-Rs(k) + B^(k)es(k + l)^))-1^)©^ + 1) X x (Ж^) + 5Z Bj(k)Mj(k))

j<£S

была разрешима относительно (М^/с), ©5(/с)}, в виде вещественных, ограниченных матриц размерности rsxm and тхт соответственно, где ©s(fc) - симметрична.

2. Управление и3(к) — М$(к)х(к) было бы допустимым в смысле определения 1.

3. {-Я3{к) + В^(к)в3(к +1 )Вз{к)) Е <Э+(Т+).

Тогда управление и°3(к) доставляет максимум функционалу Js и ^{к0,х0,и°) = -х%в3{к0)хо, где и0{к) = = Щ(к)х, з и? =

М®{к)х(к), г Е 5}, что и требовалось доказать.

□

Перейдем теперь к построению характеристической функции. Обозначим

щ,геЬ

Тогда, если набор стратегий

{и* = М*{к)х^е Б}

существует, то согласно теореме 2, М$(к) —

Щ(к)

можно наити из системы

<

(А(к) + В^к)М?Е{к) + В3(к)М*3(к))ТЩ(к + 1)И(А)+

+ в^к)м^Е(к) + в3(к)м*3(к)) - е*3{к) - р3(к)~ №

- М*3(к)тЯ3(к)М*3(к) = о,

М3{к) = -(-Я3(к) + Д5 (А;)©Ь(А: + 1) Д^/с))"1^ (/с)©*5(/с + 1) х №

При этом

^(к0,х0,иМЕ/и*3) =

То*

Согласно определению характеристической функции

о) = -х1Э*3(ко)хй.

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

Список литературы диссертационного исследования кандидат наук Тур, Анна Викторовна, 2015 год

Литература

1. Айзеке Р. Дифференциальные игры. М.: Мир, 1967. 480 с.

2. Белицкая A.B., Петросян Л.А. Сетевая игра сокращения вредных выбросов

в атмосферу // МТИП. 2012. Т. 4. Вып. 2. С. 3-13.

3. Жуковский В.А., Чикрий A.A. Линейно-квадратичные дифференциальные игры. Киев: Наукова думка, 1994. 320 С.

4. Жуковский В.И., Тынянский Т.Н. Оптимальность в бескоалиционных дифференциальных играх // Неантагонистические дифференциальные игры и их приложения: Сб. научн. тр. М. 1986. С. 3-7.

5. Зенкевич H.A., Петросян Л.А. Дифференциальные игры в менеджменте // Научные доклады Научно-исследовательского института менеджмента СПбГУ. 2006. № 38(R). С. 6-8.

6. Клейменов А.Ф. Решения по Нэшу, Парето и Штакельбергу в неантагонистических дифференциальных играх // ПММ. 1987. Т. 51. № 2. С. 209-215.

7. Клейменов А.Ф. Кооперативные решения в позиционной дифференциальной игре многих лиц с непрерывными функциями платежей. // ПММ. 1990. Т. 54. № 3. С. 389-394.

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

9. Кононенко А.Ф. О равновесных позиционных стратегиях в неантагонистических диф ференциальных играх // Докл. АН СССР. 1976. Т. 231, № 2. С. 285-288.

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

11. Кристофидес H. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.

12. Марковкин М.В. Линейно-квадратичные кооперативные дифференциальные игры: диссертация кандидата физико-математических наук, СПбГУ, Санкт-Петербург, 2006. 106 с.

13. Марковкина A.B. Линейно-квадратичные неантагонистические дискретные игры // Процессы управления и устойчивость: Труды 38-й международной научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, Г.Ш. Тамасяна- СПб.: Издат. Дом С.-Петерб. гос ун-та. 2007. С. 580-585.

14. Петросян Л.А. Устойчивость решений в дифференциальных играх со многими участниками. Вестник Ленинградского университета. 1977. № 19. Вып. 4. С. 46-52.

15. Петросян Л.А. Неантагонистические дифференциальные игры. В кн.: Вопросы механики процессов управления, управление динамическими системами. Л., 1978.

16. Петросян Л.А., H.H. Данилов. Устойчивость решений в неантагонистических дифференциальных играх с трансферабельными выигрышами // Вестн. Ленингр. ун-та. 1979. Выи. 1. С. 46-54.

17. Петросян Л.А. Построение сильно динамически устойчивых решений в кооперативных дифференциальных играх // Вестн. С.-Петерб. ун-та. 1992. Вып. 4. С. 33-38.

18. Баранова Е. М., Петросян Л. А. Кооперативные стохастические игры // Тезисы докладов международного семинара "Теория управления и теория обобщенных решений уравнений Гамильтопа-Якоби". Екатеринбург: Изд-во Уральского унив-та. 2005. С. 33-35.

19. Петросян JI. А., Баранова Е. М., Шевкопляс Е. В. Многошаговые кооперативные игры со случайной продолжительностью // Труды Ин-та математики и механики УрО РАН. 2004. Т. 10, № 2, с. 116-130.

20. Петросян Л.А., Зенкевич H.A. Принципы устойчивой кооперации // Управление большими системами. 2009. № 26-1. С. 100-120.

21. Петросян Л.А., Зенкевич H.A., Шевкопляс Е.В. Теория игр. СПб.: БХВ-Петербург, 2012. 432 с.

22. Петросян Л.А., Тур A.B. Кооперативные линейно-квадратичные дифференциальные игры на сетях // Всероссийская конференция, посвященная 80-летию со Дня Рождения В.И. Зубова "Устойчивость и процессы управления". СПб.: ВВМ. 2010. С. 174.

23. Петросян Л. А., Шевкопляс Е. В. Кооперативные дифференци- альные игры со случайной продолжительностью // Вестник СПбГУ. 2000. Сер. 1. Вып. 4. С. 18-23.

24. Понтрягин Л .С. О некоторых дифференциальных играх / / Докл. АН СССР. 1964. Т. 156. № 4. С. 738-741.

25. Понтрягин Л.С. О линейных дифференциальных играх. 1 // Докл. АН СССР. 1967. Т. 174. № 6. С. 1278-1280.

26. Понтрягин Л.С. О линейных дифференциальных играх. 2 // Докл. АН СССР. 1967. Т. 175. № 4. С. 764-766.

27. Смирнов Е.Я. Стабилизация программных движений. Издательство С.-Петербургского университета, С-Пб, 1997. 308 с.

28. Тур A.B. Теоретико-игровая модель планирования производства в условиях конкуренции // Процессы управления и устойчивость: Труды 39-й между-

народной научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, Г.Ш. Тамасяна- СПб.: Издат. Дом С.-Петерб. гос ун-та. 2008. С. 517-522.

29. Тур A.B. Условие Д.В.К. Янга в линейно-квадратичных дискретных играх // Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, Г.Ш. Тамасяна - СПб.: Издат. Дом С.-Петерб. гос ун-та. 2009. С. 678-683.

30. Тур A.B. Линейно-квадратичные неантагонистические дискретные игры // Управление большими системами. Выпуск 26.1. М.: ИПУ РАН. 2009. С. 139163.

31. Тур A.B. Условие Д.В.К. Янга в линейно-квадратичных дискретных играх с неполной информацией // Процессы управления и устойчивость: Труды 40-й международной научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, Г.Ш. Тамасяна - СПб.: Издат. Дом С.-Петерб. гос ун-та. 2010. С. 718-723.

32. Тур A.B. Линейно-квадратичные стохастические дискретные игры со случайной продолжительностью // Математическая теория игр и её приложения. Петрозаводск: КарНЦ РАН. 2014. Т. 6. В. 3. С. 76-92.

33. Чистяков C.B. О бескоалиционршх дифференциальных играх // Докл. АН СССР. 1981. Т. 259. № 5. С. 1052-1055.

34. Шевкопляс Е. В. Устойчивая кооперация в дифференциальных играх со случайной продолжительностью // МТИП. 2012. Т. 2. Вып. 3. С. 79-105.

35. Aarle В. van, Bovenberg L. and Raith, M. Monetary and fiscal policy interaction and government debt stabilization // Journal of Economics. 1995. Vol. 62. № 2, P. 111-140.

36. Baranova E. M., Petrosjan L. A. Cooperative Stochastic Games in Stationary Strategies // Game theory and Applications, Nova Science Publishers. 2006. V. 11. P. 7-17.

37. Basar T. Existence of unique equilibrium solutions in nonzero-sum stochastic differential games // Differential Games and Control Theory II, E. O. Roxin, P.T. Liu, and R. Sternberg, eds., Marcel Dekker, Inc. 1977. P. 201-228.

38. Basar T. and G.J. Olsder. Dynamic Noncooperative Game Theory. Academic Press, 1982.

39. Basar T. and Olsder G.J. Dynamic Noncooperative Game Theory, 2nd edition, Classics in Applied Mathematics, SIAM, Philadelphia, 1999. 536 p.

40. Belitskaia, A. V. The D.W.K. Yeung Condition for Cooperative Differential Games with Nontransferable Payoffs // Graduate School of Management, Contributions to game theory and management. 2012. Vol. 5. P. 45-50.

41. Bernhard P. Linear-quadratic, two-person, zero-sum differential games: necessary and sufficient conditions //J. Optim. Theory Appl. 1979. Vol.27. P. 51—69.

42. Bertsekas D.P. Dynamic Programming and Optimal Control, Vol I and II, 3rd

edition. Athena Scientific, 2007. 704 p.

43. Chistyakov, S., Petrosyan, L. Strong Strategic Support of Cooperative Solutions in Differential Games // Contributions to game theory and management. 2011. Vol. IV. P. 105-111.

44. Dockner, E. and J0rgensen, S. Cooperative and Non-cooperative Differential Games Solutions to an Investment and Pricing Problem // The Journal of the International Operational Research Society. 1984. Vol. 35. p. 731-739.

45 Di lessen T S H and Y. Funaki. Coincidence of and collinearity between game thcoietic solutions // OR Spektium 1991 N 13 P 15-30.

46 Engwcida J LQ Dynamic Optimization and Differential Games, Wiley, 2005. 510 p

47 Engwerda J C . Bas van Aarle, J E J Plasmans The (m)finite horizon open-loop Nash LQ game- An application to EMU // Annals of Operation Research. 1999 Vol 88 P 251-273.

48 Engweida JC, Bas van Aarle, JEJ Plasmans Cooperative and non-coopeiative fiscal stabilization policies in the EMU // Journal of Economic Dynamics and Control 2002 Vol 26 P 451-481.

49 Feishtman, C and Kannen I (1987) Dynamic duopolistic competition with sticky puces//Econometuca 1987 Vol 55 P 1151—1164

50 Hamalamen, R , Haurie, A. and Kaitala, V. Equilibria and Threats in a Fishery Management Game // Optimal Control Applications and Methods 1986 Vol. 6 P 315-333

51 Leitmann, G Cooperative and Non-Cooperative Many Players Differential Games, New Yoik, Springer-Verlag, 1974

52 Lillian J Ratliff, Samuel Coogan, Daniel Caldeione, and S. Shankar Sastry Pi icing in Linear-Quadratic Dynamic Games // 50th Annual Alleiton Conference on Communication, Control, and Computing. 2012. DOI 10 1109/Alleiton 2012 6483440

53 Nash J Non-cooperative Games// Ann. of Math 1951. Vol. 54 N2 P 286-295.

54 Petiosyan L A Differential Games of Pursuit, World Scientific, Singapore, 1993.

326 p

55. Pet.iosyan L.A. Agreeable Solutions in Differential Games // International Journal of Mathematics, Game Theory and Algebra. 1997. Vol. 7. P. 165-177.

56. Petrosjan L.A. The Time-Consistency Problem in Nonlinear Dynamics // RBCM - J. of Brazilian Soc. of Mechanical Sciences. 1997. Vol. XIX, No 2.

P. 291-303.

57. Petrosjan L.A. Cooperative stochastic games // Petrosjan, L. A. (ed.) et al., 10th international symposium on dynamic games and applications. St. Petersburg, Russia. In 2 vol. St. Petersburg: International Society of Dynamic Games - St. Petersburg. 2002. P. 687-690.

58. Leon Petrosian, Georges Zaccour. Time-consistent Shapley value allocation of pollution cost reduction // Journal of Economic Dynamic and Control. 2003. Vol. 27. P. 381-398.

59. Petrosjan L.A., D.W.K. Yeung. Proportional Time-Consistent Solution in Differential Games // Extended Abstracts Volume of the 2-nd International Conference "Logic, Game Theory and Social ChoiceSt Petersburg State University. 2001. P. 254-256.

60. Petrosyan, L., Chistyakov, S. Strategic support of Cooperative Solutions in 2-Person Differential Games with Dependent Motions // Contributions to Game Theory and Management. 2013. Vol. 6. P. 388-394.

61. Shapley L.S. A Value for n-Person Games // Contributions to the Theory of Games II. Princeton: Princeton University Press. 1953. P. 307-317.

62. Shapley L.S. Stochastic games // Proc. Nat. Acad. USA. 1953. V. 39. P. 10951100.

63. Tur Anna V. Dynamic Game-theoretic Model of Production Planning under Competition // Contributions to Game Theory and Management. Vol II.

Collected papers/ Editors Leon A. Petrosjan, Nikolay A. Zenkevich , SPb, Graduate School of Management, SPbU. 2009. P. 474-482.

64. Tur Anna V. The Irrational Behavior Proof Condition for Linear-Quadratic Discrete-time Dynamic Games with Nontransferable Payoffs // Contributions to Game Theory and Management. Vol VII. Collected papers/ Editors Leon A. Petrosjan, Nikolay A. Zenkevich , SPb, Graduate School of Management, SPbU. 2014. P. 384-392.

65. Yeung D.W.K. and Petrosyan L.A. Subgame Consistent Solution of A Cooperative Stochastic Differential Game With Nontransferable Payoffs // Journal of Optimization Theory and Applications. 2009. Vol. 124. No. 3. P. 701-724.

66. Yeung D.W.K. An Irrational-Behavior-Proof Condition in Cooperative Defferential Games // IGTR. 2007. Vol. 9. No. 1. P. 5-7.

67. Yeung D.W.K., Petrosyan L.A. Subgame consistent cooperative solutions in stochastic differential games // Journal of Optimization Theory and Applications. 2004. V. 120. No. 3. P. 651-666.

68. Yeung D.W.K., Petrosyan L.A. Cooperative Stochastic Differential Games. Springer Series in Operations Research and Financial Engineering, 2005.

69. Yeung D.W.K. and L.A. Petrosyan. A Time-consistent Solution Formula for Bargaining Problem in Differential Games // Int. Game Theory Rev. 2014. Vol. 16. No. 4. 1450016.

70. Zhang P. Some results on two-person zero-sum linear quadratic differential games // SIAM Journal on Control and Optimization. 2005. Vol. 43. No. 6. P. 21572165.