Санкт-Петербургский государственный университет
Факультет прикладной математики – процессов управления
Кафедра математического моделирования энергитических
систем
Петросян Ованес Леонович
Выпускная квалификационная работа
Решение с информационной дискриминацией в
кооперативных дифференциальных играх
Специальность 01.01.09
Дискретная математика и математическая кибернетика
Заведующий кафедрой,
доктор физ.-мат. наук,
профессор
Захаров В. В.
Научный руководитель,
доктор физ.-мат. наук,
профессор
Захаров В. В.
Рецензент,
кандидат физ.-мат. наук,
Уткин Ю. Г.
Санкт-Петербург
2017
2
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
ГЛАВА 1. КООПЕРАТИВНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ С ДИНАМИЧЕСКИМ ОБНОВЛЕНИЕМ ИНФОРМАЦИИ
12
§ 1. Определение усеченной подыгры . . . . . . . . . . . . . . . . . . . .
12
§ 2. Решение кооперативной усеченной подыгры . . . . . . . . . . . . .
15
§ 3. Концепция решения в исходной игре с динамическим обновлением
информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
§ 4. Построение характеристической функции в игре с динамическим
обновлением информации . . . . . . . . . . . . . . . . . . . . . . . .
25
§ 5. Связь решения в усеченных подыграх и результирующего решения 28
§ 6. Кооперативная игра добычи ограниченного ресурса с динамическим обновлением информации . . . . . . . . . . . . . . . . . . . .
38
ГЛАВА 2. КООПЕРАТИВНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ С ПРЕДПИСАННОЙ ПРОДОЛЖИТЕЛЬНОСТЬЮ И СО СЛУЧАЙНЫМ
ОБНОВЛЕНИЕМ ИНФОРМАЦИИ
49
§ 1. Определение случайной усеченной подыгры . . . . . . . . . . . . .
49
§ 2. Решение кооперативной случайной усеченной подыгры . . . . . . .
51
§ 3. Концепция решения в исходной игре со случайным обновлением
информации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
§ 4. Кооперативная игра добычи ограниченного ресурса со случайным
обновлением информации . . . . . . . . . . . . . . . . . . . . . . . .
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
56
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
3
ВВЕДЕНИЕ
Актуальность темы. Теория дифференциальных игр в настоящее время
является одним из наиболее бурно развивающихся разделов математической
теории игр. Главным образом это связано с тем, что математический аппарат дифференциальных игр позволяет реалистично моделировать конфликтноуправляемые процессы, непрерывно развивающиеся во времени. Так динамика фазовой переменной, описывающей состояние процесса, задается системой
дифференциальных уравнений на некотором временном промежутке заданной
продолжительности.
Теория дифференциальных игр сформировалась как отдельный раздел математической теории игр в пятидесятых годах двадцатого века. Одними из первых интересные результаты в этой области получили Р. Айзекс, Л. Берковитц
[33], В. Флеминг [36]. Долгое время исследования были посвящены в основном
антагонистическим дифференциальным играм. Значительные успехи в данной
области связаны с представителями отечественной научной школы Н. Н. Красовским [11, 12], Л. С. Понтрягиным [25], Е. Ф. Мищенко, Б. Н. Пшеничным,
Л. А. Петросяном [20].
Толчком для развития теории неантагонистических дифференциальных игр
послужили задачи конфликтного управления со многими участниками из различных практических областей. В качестве принципа оптимальности в неантагонистических дифференциальных играх чаще всего рассматривается равновесие по Нэшу в программных или позиционных стратегиях. Основные результаты, посвященные исследованию вопроса существования и проблемы построения
равновесия по Нэшу, получены в работах А. Ф. Клейменова [7, 8], А. Ф. Кононенко [9], С. В. Чистякова [29].
Особый интерес представляют также кооперативные дифференциальные игры [5, 6, 18, 21]. Естественным подходом к изучению кооперативных дифференциальных игр, как игр дележей, является попытка переноса результатов классической кооперативной теории "однократных"игр Неймана-Моргенштерна [13].
Однако при использовании результатов классической теории необходимо допол-
4
нительно исследовать вопрос о динамической и сильно динамической устойчивости полученного решения. Попытки применения динамически неустойчивых
принципов оптимальности при решении прикладных задач в области экономики, экологии, менеджмента приводят к не реализуемости таких принципов,
поскольку в некоторый момент времени возникают условия, когда соглашение о кооперации могут быть пересмотрено. Это обстоятельство впервые было замечено Л. A. Петросяном в 1977 году. В [14] он сформулировал строгое
математическое определение динамической устойчивости принципа оптимальности (кооперативного решения), а в работе [17] предложен способ решения
проблемы динамической неустойчивости кооперативного решения при помощи
схемы выплат, получившей название процедуры распределения дележа (ПРД).
Определение сильной динамической устойчивости впервые было дано в работе
[15]. Исследованиям проблемы динамической устойчивости посвящены работы
[4, 18, 19, 21] и др.
В литературе по кооперативной теории игр и ее приложениям в качестве
кооперативного решения часто применяется C-ядро. В частности, в работе [27]
приводятся условия существования сильно динамически устойчивого C-ядра в
кооперативных динамических (дискретных) играх. В работе [2] впервые были
сформулированы достаточные условия для выполнения сильной динамической
устойчивости кооперативного решения в неантагонистической дифференциальной игре двух лиц, а в работе [37] данная проблема изучалась для игры трех
лиц.
Теория кооперативных дифференциальных игр изучает вопросы построения
оптимальных (кооперативных) решений в конфликтно-управляемых процессах
со многими участниками на определенном временном интервале. Но множество подобных процессов развивается во времени непрерывно, а их участники
непрерывно получают обновленную информацию и адаптируются. Именно для
таких процессов был предложен подход позволяющий моделировать кооперативные игры с динамическим обновлением информации. Но возникает много
вопросов, например, как для таких игр построить кооперативную траекторию,
стратегии, ее порождающие, суммарный выигрыш вдоль кооперативной траек-
5
тории, определить распределение суммарного выигрыша между игроками.
В выпускной квалификационной работе описывается новый подход к определению решения кооперативной дифференциальной игры в условиях, когда
игроки не имеют полную информацию об игре (уравнения движения, функция
выигрыша) на всем временном интервале, на котором задана игра. В любой момент времени игроки принимают решение, используя информацию на временном интервале с продолжительностью меньшей, чем продолжительность исходной игры. Информация об игре обновляется в определенные моменты времени
и неизвестна заранее. Согласно описанному подходу решение в игре определяется как комбинация решений в усеченных подыграх. В выпускной квалификационной работе предложен метод для построения кооперативной траектории и
соответствующего решения. Ключевым для построения решения является понятие усеченной подыгры, в рамках которой удается описать поведение игроков между моментами обновления информации. Оказывается, что в подобных
играх любое построенное решение обладает свойством сильной динамической
устойчивости.
В выпускной квалификационной работе были исследованы несколько моделей и подходов для определения решений в кооперативных дифференциальных
играх с динамическим обновлением информации. Для кооперативных дифференциальных игр с предписанной продолжительностью и динамическим обновлением информации было определено понятие усеченной подыгры, предложены
способы построения условно кооперативной траектории и решений обладающих
свойством ∆t-сильной динамической устойчивости. Аналогичный результат получен для кооперативных дифференциальных игр с бесконечной продолжительностью. Была также рассмотрена модель, когда игроки, получая обновленную информацию о структуре игры, не имели точной информации, в течение
какого срока эта информация будет является актуальной. Единственное, что
им было известно, это то, что информационный горизонт является случайной
величиной. Подобный класс игр назван в выпускной квалификационной работе
кооперативными дифференциальными играми с предписанной продолжительностью и со случайным обновлением информации. Для них введено понятие
6
случайной подыгры. В описанных постановках в качестве исходного кооперативного решения использовались вектор Шепли, пропорциональное решение,
С-ядро и сильно динамически устойчивое ПРД-ядро.
Дифференциальные игры со случайной продолжительностью в общей постановке были введены в работе Л. А. Петросяна и Е. В. Шевкопляс [16]. В работе
рассматривались дифференциальные игры со многими участниками, при этом
момент окончания игры не был определен заранее, а представлял собой реализацию некоторой случайной величины с известной функцией распределения.
В работах Е. В. Шевкопляс [30, 31] были продолжены исследования кооперативных дифференциальных игр со случайной продолжительностью, получены
важные результаты, относящиеся к проблеме динамической устойчивости кооперативных принципов оптимальности.
Цели и задачи исследования. Целью выпускной квалификационной работы является формализация и построение оптимальных решений о распределении выигрышей в конфликтно-управляемых процессах со многими участниками, когда информация о процессе обновляется динамически с течением
времени. Для достижения поставленной цели в работе ставятся и решаются
следующие задачи:
1. Формализация поведения игроков на периодах между моментами времени, когда информация об игре обновляется, т.е. построение усеченных
подыгр.
2. Исследование каждой усеченной подыгры, нахождение кооперативной
траектории, построение характеристической функции вдоль кооперативных траекторий, получение оптимального решения.
3. Нахождение результирующего решения для игры, определенной на совокупности всех временных интервалов.
4. Формализация общей кооперативной игры, определенной на совокупности всех временных интервалов, определение характеристической функции для игры с динамическим обновлением информации.
5. Исследование свойства сильной динамической устойчивости (сильной временной состоятельности) результирующего решения дифференциальной
7
кооперативной игры.
6. Построение результирующего решения, соответствующего набору классических решений в каждой усеченной подыгре, а именно пропорционального решения, вектора Шепли, C-ядра, сильно динамически устойчивого
ПРД-ядра.
7. Исследование связи результирующего решения и решения в каждой усеченной подыгре, а именно пропорционального решения, вектора Шепли,
C-ядра, сильно динамически устойчивого ПРД-ядра.
8. Изучение различных вариантов или моделей игр с динамическим обновлением информации, а именно: кооперативные дифференциальные игры
с динамическим обновлением информации, с предписанной или бесконечной продолжительностью, кооперативные дифференциальные игры со
случайным обновлением информации.
9. Апробация полученных теоретических результатов на теоретико-игровой
модели добычи ограниченного ресурса, демонстрация свойства сильной
динамической устойчивости полученного решения.
Научная новизна полученных результатов. Научная новизна работы
заключается в том, что в ней:
1. Построены и исследованы новые математические модели дифференциальной игры с динамическим обновлением информации с предписанной
и бесконечной продолжительностью, дифференциальной игры со случайным обновлением информации.
2. Предложены конструктивные методы нахождения результирующего кооперативного решения в дифференциальных играх с динамическим обновлением информации с предписанной и бесконечной продолжительностью, дифференциальных играх со случайным обновлением информации.
3. Предложена процедура построения характеристической функции в играх
с динамическим обновлением информации на основе значений характеристических функций в усеченных подыграх.
8
4. Доказаны теоремы о сильной ∆t-динамической устойчивости в дифференциальных играх с динамическим обновлением информации с предписанной и бесконечной продолжительностью, дифференциальных играх со
случайным обновлением информации.
5. Определена связь кооперативного решения в игре с динамическим обновлением информации и кооперативных решений (пропорциональное решение, вектор Шепли, C-ядро, сильно динамически устойчивое ПРД-ядро),
в каждой усеченной подыгре.
Практическая значимость. Полученные в выпускной квалификационной
работе результаты представляют практический интерес. Кооперативные дифференциальные игры с динамическим обновлением информации, а также их
различные варианты являются удобными математическими моделями для описания процессов, происходящих в экономике, экологии, менеджменте и прочих
сферах человеческой деятельности.
Методология и методы исследования. В процессе проведения исследования автор опирался на научную методологию проведения исследования,
общепризнанные принципы и подходы к исследовательской деятельности в области прикладной математики, методы теории оптимизации и теории игр.
Структура и основное содержание работы. Выпускная квалификационная работа состоит из введения, двух глав, разбитых на параграфы, заключения, списка используемой литературы, включающего 48 наименований. Объем
составляет 73 страниц машинописного текста. Работа содержит 18 рисунков.
Первая глава посвящена описанию и изучению кооперативных дифференциальных игр с динамическим обновлением информации, как с предписанной
продолжительностью так и с бесконечной продолжительностью. Для кооперативных дифференциальных игр с динамическим обновлением информации
определено понятие усеченной подыгры, построена условно кооперативная траектория, построено решение. Было показано, что решение обладает свойством
∆t-сильной динамической устойчивости. Также была показана связь между решениями, выбранными игроками в усеченных подыграх и в общей игре. Было
введено понятие характеристической функции для общей игры, с помощью нее
9
и решения для общей игры удалось показать, что решения, выбранные игроками в усеченных подыграх, соответствуют результирующему решению, построенному на основе новой характеристической функции. В § 1 приводится определение усеченной подыгры, объясняется каким образом на основе этого понятия
можно смоделировать поведение игроков. В § 2 описывается решение усеченной
подыгры, строится условно-кооперативная траектория. В § 3 на основе результатов в параграфе 2 строиться решение в игре с динамическим обновлением
информации, доказывается свойство сильной ∆t-динамической устойчивости. §
4 посвящен построению характеристической функции в игре с динамическим
обновлением информации. В § 5 описывается и формализуется математически
связь решений выбранных игроками в усеченных подыграх с результирующим
решением в исходной игре с динамическим обновлением информации. В § 6
демонстрируется использование теоретических результатов для кооперативной
игры добычи ограниченного ресурса трех лиц с предписанной продолжительностью и динамическим обновлением информации, в качестве принципа оптимальности используется C-ядро. Приводятся результаты численного моделирования в среде Matlab.
Вторая глава посвящена описанию и изучению кооперативных дифференциальных игр с предписанной продолжительностью и случайным обновлением информации. В этом случае игроки, получая обновленную информацию о
структуре игры, не имеют точной информации, в течение какого срока эта информация будет верна. Единственное, что им известно, это то, что величина
информационного горизонта является случайной величиной. Понятие усеченной подыгры здесь основано на понятии дифференциальной игры со случайной
продолжительностью и она названа случайной подыгрой. В качестве кооперативного решения этой подыгры использовалось сильно динамически устойчивое
ПРД-ядро. Для построения С-ядра и сильно динамически устойчивого ПРДядро была доработана классическая кооперативная игра добычи ограниченного
ресурса для случая трех игроков. В § 1 приводится определение случайной усеченной подыгры, объясняется, каким образом на основе этого понятия можно
смоделировать поведения игроков, которые получают точную информацию об
10
игре, но уверены только в вероятностных характеристиках длительности этой
информации. В § 2 описывается сильно динамически устойчивое ПРД-ядро, как
решение случайной усеченной подыгры, строится условно-кооперативная траектория. В § 3 описывается решение в игре с динамическим обновлением информации, доказывается свойство сильной динамической устойчивости полученного решения. В § 4 теоретические результаты применяются для кооперативной
игры добычи ограниченного ресурса трех лиц, демонстрируется свойство сильной динамической устойчивости выбранного решения, приведены результаты
численного моделирования в среде Matlab.
Степень достоверности и апробация результатов исследования. Достоверность полученных результатов основана на строгом доказательстве всех
сформулированных математических утверждений. По теме выпускной квалификационной работы опубликовано 5 работ, две из которых ([22], [23]) - в изданиях, рекомендуемых Высшей аттестационной комиссией (ВАК) для публикации основных научных результатов. Публикации [38], [40], [41] индексируются в
базе данных Scopus. В работе [23] аспирант построил новое решение для кооперативных дифференциальных игр с предписанной продолжительностью, обладающее свойствами сильной динамической устойчивостью - ПРД-ядро. В работе [41] аспирантом была построена модель кооперативных дифференциальных
игр с динамическим обновлением информации и стохастическим прогнозом,
для этого класса игр было получено решение и доказано свойство сильной ∆tдинамической устойчивости. В работе [38] аспирантом была сформулирована и
решена задача определения в некотором смысле оптимального информационного горизонта.
Основные результаты были представлены на семинарах кафедры математического моделирования энергетических систем, на семинарах Центра теории
игр, на международной конференции "Game Theory and Management"(СанктПетербург, 2015 и 2016 гг.), "Workshop on the Game Theory and Social
Choice"(Будапешт, 2015 г.), на XIII международной конференции "Устойчивость и колебания нелинейных систем управления"(Москва, 2016 год).
Положения и результаты, выносимые на защиту. На защиту выно-
11
сятся следующие результаты, полученные в ходе исследования:
1. Построены и исследованы новые математические модели дифференциальной игры с динамическим обновлением информации с предписанной
и бесконечной продолжительностью, дифференциальной игры со случайным обновлением информации.
2. Предложены конструктивные методы нахождения результирующего кооперативного решения в дифференциальных играх с динамическим обновлением информации с предписанной и бесконечной продолжительностью, дифференциальных играх со случайным обновлением информации.
3. Предложена процедура построения характеристической функции в играх
с динамическим обновлением информации на основе значений характеристических функций в усеченных подыграх.
4. Доказаны теоремы о сильной ∆t-динамической устойчивости в дифференциальных играх с динамическим обновлением информации с предписанной и бесконечной продолжительностью, дифференциальных играх со
случайным обновлением информации.
5. Определена связь кооперативного решения в игре с динамическим обновлением информации и кооперативных решений (пропорциональное решение, вектор Шепли, C-ядро, сильно динамически устойчивое ПРД-ядро),
в каждой усеченной подыгре.
12
ГЛАВА 1
КООПЕРАТИВНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ С
ДИНАМИЧЕСКИМ ОБНОВЛЕНИЕМ ИНФОРМАЦИИ
§ 1.
Определение усеченной подыгры
В этой главе будем рассматривать два типа игр, дифференциальные игры с
предписанной продолжительностью Γ(x0 , T − t0 ) и бесконечной продолжительностью Γ(x0 , t0 ). Рассуждения и доказательства для этих двух классов игр в
данном случае схожи. Исходная игра Γ(x0 , T − t0 ) уже определена в главе 1.
Определим игру Γ(x0 , t0 ) с бесконечной продолжительностью.
Рассмотрим дифференциальную игру n лиц Γ(x0 , t0 ) с бесконечной продолжительностью и начальным состоянием x0 . Динамика игры задается системой
обыкновенных дифференциальных уравнений:
x ∈ Rn ,
ẋ = f (x, u1 , . . . , un ),
ui ∈ Ui ⊂ compRk ,
t ∈ [t0 , +∞],
(1.1)
x(t0 ) = x0 ,
для которой предполагаются выполненными условия существования, единственности и продолжимости решений для любого набора измеримых управлений u1 (·), . . . , un (·) [17]. Выигрыш i-го игрока определяется следующим образом:
∫+∞
Ki (x0 , t0 ; u1 , . . . , un ) =
hi (x(τ ), u1 (τ ), . . . , un (τ ))e−r(τ −t0 ) dτ,
i = 1, . . . , n,
t0
где hi (x, u1 , . . . , un ) представляет собой непрерывную функцию, x(t) - решение
задачи Коши для системы (1.1) при управлениях u(t) = (u1 (t), . . . , un (t)) и
r ≥ 0 - это дискаунт фактор.
Предположим, что в игре Γ(x0 , T − t0 ) (Γ(x0 , t0 )) информация обновляется
в моменты времени t = t0 + j∆t, j = 0, . . . , l, здесь l =
T
∆t
− 1, 0 < ∆t <
T задает время между моментами обновления информации. В игре Γ(x0 , t0 )
13
с бесконечной продолжительностью в качестве T = +∞, поэтому l = +∞.
В моменты времени t = t0 + j∆t игроки получают точную информацию об
уравнениях движений и функциях выигрыша на временном интервале [t0 +
j∆t, t0 +j∆t+T ], здесь ∆t < T < T (∆t < T < +∞) задает временной горизонт,
на котором игрокам известна информация об игре. На интервалах [t0 +j∆t, t0 +
j∆t + T ], j = 0, . . . , l (j = 0, . . . , +∞) строится игра. С помощью уравнений
Гамильтона–Якоби–Беллмана [32] можно определить кооперативное поведение
(кооперативные стратегии, траекторию) в каждой подобной усеченной игре.
Рисунок 1.1. Каждый овал показывает усеченную информацию, которая
известна игрокам в течение временного интервала [t0 + j∆t, t0 + (j + 1)∆t],
j = 0, . . . , l.
В течение первого временного интервала [t0 , t0 + ∆t] игроки имеют точную информацию о структуре игры на интервале [t0 , t0 + T ]. В момент времени t = t0 + ∆t информация об игре обновляется, и на втором интервале
(t0 + ∆t,t0 + 2∆t] игроки имеют точную информацию о структуре игры на интервале (t0 + ∆t, t0 + ∆t + T ] и т.д. Чтобы смоделировать подобный процесс введем следующее определение (Рис.2.1.). Обозначим xj,0 = x(t0 + j∆t), x0,0 = x0 .
Определение 2.1.1. Пусть j = 0, . . . , l. Усеченная подыгра Γ̂j (xj,0 , t0 +
j∆t, t0 + j∆t + T ) определена на временном интервале [t0 + j∆t, t0 + j∆t + T ]
14
следующим образом. На временном интервале [t0 +j∆t, t0 +j∆t+T ] уравнения
движения, функция выигрыша в усеченной игре и исходной игре совпадают:
ẋ = f (x, u1 , . . . , un ),
x(t0 + j∆t) = xj,0 ,
t0 +j∆t+T
∫
Kij (xj,0 , t0 + j∆t, t0 + j∆t + T ; u) =
hi (τ, x(τ ), u(τ ))e−r(τ −t0 ) dτ.
(1.2)
(1.3)
t0 +j∆t
Под исходной игрой в определении 2.1.1. будем понимать игру Γ(x0 , T − t0 ) с
предписанной продолжительностью, тогда дискаунт фактор может принимать
нулевое значение r ≥ 0 и l =
T
∆t
− 1, где T < +∞. Либо игру Γ(x0 , t0 ) с
бесконечной продолжительностью, тогда l = +∞ и дискаунт фактор r > 0. Для
игры с бесконечной продолжительностью предполагается также, что выигрыш
в игре (в любой усеченной подыгре) рассчитывается от момента времени t0 ; в
формуле (1.3) дисконтирование выигрыша начинается с момента времени t0 .
Рисунок 1.2. Поведение игроков в условиях усеченной информации может
быть смоделировано с помощью набора усеченных подыгр
Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ), j = 0, . . . , l.
15
§ 2.
Решение кооперативной усеченной подыгры
Рассмотрим усеченную кооперативную подыгру Γ̂j (xj,0 , t0 +j∆t, t0 +j∆t+T )
на временном интервале [t0 + j∆t, t0 + j∆t + T ] с начальным условием x(t0 +
j∆t) = xj,0 . В кооперативной постановке игрокам необходимо максимизировать
суммарный выигрыш
∑
Kij (xj,0 , t0 + j∆t, t0 + j∆t + T ; uj ) =
i∈N
=
∑
t0 +j∆t+T
∫
hi (x(τ ), u(τ ))e−r(τ −t0 ) dτ (2.1)
i∈N t +j∆t
0
при условии
ẋ = f (x, u1 , . . . , un ),
(2.2)
x(t0 + j∆t) = xj,0 .
Это задача оптимального управления. Необходимые условия для ее решения
и соответствующие управления могут быть определены с помощью уравнения
Гамильтона-Якоби-Беллмана [32]. Обозначим максимальное значение суммарного выигрыша игроков (2.1) через W (j∆t) (t, x):
}
{
∑ j
j
W (j∆t) (t, x) = max
K
(x,
t;
u
) ,
i
j
u
(2.3)
i∈N
где x, t - начальные позиция и время подыгры усеченной игры Γ̂j (x, t, t0 + j∆t +
T ).
Теорема 2.2.1. Предположим, что существует непрерывно дифференцируемая функция W (j∆t) (t, x) : [t0 + j∆t, t0 + j∆t + T ] × Rm → R, удовлетворяющая следующей системе уравнений в частных производных:
(j∆t)
− Wt
(t, x) =
= max
u
{
n
∑
}
hi (t, x, u)e−r(τ −t0 ) + Wx(j∆t) (t, x)f (x, u1 , . . . , un )
(2.4)
W (j∆t) (t0 + j∆t + T , x) = 0.
(2.5)
i=1
при условии
16
Предположим, что максимум в (2.4) достигается при u = u∗j (t). Тогда u =
u∗j (t) является оптимальным в задаче управления, определяемой (2.1), (2.2).
Траекторию, соответствующую u = u∗j (t), будем называть кооперативной
и обозначать через x∗j (t). В соответствии с рассматриваемым подходом в каждый момент времени игрокам доступна ограниченная информация о структуре
игры Γ(x0 , T − t0 ) (Γ(x0 , t0 )). Этой информации недостаточно, чтобы определить кооперативное поведение для игроков во всей игре Γ(x0 , T − t0 ) (Γ(x0 , t0 )).
Вместо кооперативной траектории в игре Γ(x0 , T − t0 ) (Γ(x0 , t0 )) будем строить
условно кооперативную траекторию:
Определение 2.2.1. Условно кооперативная траектория {x̂∗ (t)}Tt=t0
∗
({x̂∗ (t)}+∞
t=t0 ) - это комбинация кооперативных траекторий xj (t) в усеченных
подыграх Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ):
x∗0 (t) t ∈ [t0 , t0 + ∆t],
···
{x̂∗ (t)}lt=t0 = x∗j (t) t ∈ (t0 + j∆t, t0 + (j + 1)∆t],
···
x∗ (t) t ∈ (t + l∆t, t + (l + 1)∆t],
0
0
l
(2.6)
где для игры Γ(x0 , T −t0 ) с предписанной продолжительностью t0 +(l +1)∆t =
T и T < ∞, а для игры Γ(x0 , t0 ) с бесконечной продолжительностью l = +∞
и соответственно t0 + (l + 1)∆t = +∞.
На временном интервале [t0 , t0 + ∆t] траектория x∗0 (t) является кооперативной в усеченной подыгре Γ̂0 (x0 , t0 , t0 + T ). В момент времени t = t0 + ∆t в
позиции x∗0 (t0 + ∆t) информация об игре обновляется. На временном интервале (t0 + ∆t, t0 + 2∆t] игроки двигаются вдоль кооперативной траектории x∗1 (t)
в усеченной подыгре Γ̂1 (x∗0 (t0 + ∆t), t0 + ∆t, t0 + ∆t + T ). В момент времени
t = t0 + j∆t в позиции x∗j−1 (t0 + j∆t) информация об игре обновляется. Условно
кооперативная траектория x̂∗ (t) на временном интервале (t0 +j∆t, t0 +(j +1)∆t]
определена, как комбинация частей кооперативных траекторий x∗j (t) в усеченных подыграх Γ̂j (x∗j−1 (t0 + j∆t), t0 + j∆t, t0 + j∆t + T ) (Рис. 2.3.). Введем сле-
17
дующие обозначения: x∗j,0 = x∗j−1 (t0 + j∆t) = x∗j (t0 + j∆t). Тогда усеченная
подыгра может быть записана в следующем виде: Γ̂j (x∗j,0 , t0 + j∆t, t0 + j∆t + T ).
Рисунок 1.3. Условно кооперативная траектория {x̂∗ (t)}Tt=t0 определена, как
комбинация кооперативных траекторий x∗j (t) в усеченных подыграх
Γ̂j (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) на интервалах (t0 + j∆t, t0 + (j + 1)∆t].
Пунктирные линии отображают части кооперативных траекторий, которые не
используются игроками, т.е. которые не являются оптимальными в текущей
усеченной подыгре
Кооперативная усеченная подыгра.
Перейдем к рассмотрению ко-
оперативной дифференциальной игры Γ̂jv (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) и семейства подыгр Γ̂jv (x∗j (t), t, t0 + j∆t + T ) вдоль кооперативной траектории x∗j (t),
∀t ∈ [t0 , T ] в форме характеристической функции. Допустим, что в каждой
усеченной подыгре Γ̂jv (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) существует ситуация равноE
E
NE
весия по Нэшу uN
= (uN
j
1,j , . . . , un,j ). Тогда для каждой коалиции S ⊂ N и
усеченной подыгры с номером j = 0, . . . , l (l = +∞ для исходной игры Γ(x0 , t0 ))
определим значения характеристической функции так, как это сделано в [39]:
18
Vj (S; x∗j,0 , t, t0 + j∆t + T ) =
0,
S = {∅},
∑ j ∗
E
max
Ki (xj (t), t, t0 + j∆t + T ; u∗j,S , uN
j,N
\S ), S ⊂ N,
u
,i∈S
i
=
i∈S
N
E
uj =u
,j∈N \S
j
n
∑ j
S = N.
max Ki (x∗j (t), t, t0 + j∆t + T ; u∗j ),
u
(2.7)
i=1
В этом подходе предполагается, что фиксируется некоторая ситуация равновеE
E
NE
сия по Нэшу uN
= (uN
/ S,
j
1,j , . . . , un,j ), игроки k, не входящие в коалицию k ∈
E
используют равновесные по Нэшу стратегии {uN
k,j }, тогда как игроки из коа-
лиции S максимизирует свой суммарный выигрыш.
Любой дележ ξj (x∗j (t), t, t0 + j∆t + T ) в кооперативной усеченной подыгре
Γ̂jv (x∗j , t, t0 + j∆t + T ) должен удовлетворять следующей системе неравенств
∀i ∈ N :
ξij (x∗j (t), t, t0 + j∆t + T ) ≥ Vj ({i}; x∗j (t), t, t0 + j∆t + T ),
∑ j
ξi (x∗j (t), t, t0 + j∆t + T ) = Vj (N ; x∗j (t), t, t0 + j∆t + T ).
i∈N
Обозначим множество всевозможных дележей для усеченной подыгры
Γ̂jv (x∗j (t), t, t0 + j∆t + T ) через Ej (x∗j (t), t, t0 + j∆t + T ). Предположим, что для
каждой усеченной подыгры определено непустое решение:
Wj (x∗j , t, t0 + j∆t + T ) ⊂ Ej (x∗j (t), t, t0 + j∆t + T ).
Это может быть C-ядро, НМ-решение, N-ядро или вектор Шепли.
§ 3.
Концепция решения в исходной игре с динамическим обновлением информации
Логично предположить, что распределение суммарного выигрыша между
игроками в игре Γ(x0 , T − t0 ) (Γ(x0 , t0 )) вдоль условно кооперативной траектории {x̂∗ (t)}Tt=t0 ({x̂∗ (t)}+∞
t=t0 ) определено, как комбинация дележей на временных
интервалах [t0 + j∆t, t0 + (j + 1)∆t], j = 0, . . . , l (j = 0, . . . , +∞). Эту конструкцию будем называть новой концепцией решения.
19
Комбинация семейства множеств Wj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) не позволяет получить решение в игре Γ(x0 , T − t0 ) (Γ(x0 , t0 )) непосредственно.
Для каждого j = 0, . . . , l (j = 0, . . . , +∞) решение в усеченной подыгре
Γ̂jv (x∗j,0 , t0 +j∆t, t0 +j∆t+T ) определено для временного интервала [t0 +j∆t, t0 +
j∆t + T ]. Но информация об игре обновляется с шагом ∆t, а использование
такого решения на временном интервале [t0 + j∆t, t0 + (j + 1)∆t] не представляется возможным. Необходимая часть решения может быть получена с
помощью процедуры распределения дележа для каждой усеченной подыгры.
ПРД также обеспечивает свойство динамической устойчивости новой концепции решения и возможность определять решения внутри временного интервала
[t0 + j∆t, t0 + j∆t + T ].
Для
того,
(Γ(x0 , t0 ))
чтобы
необходимо
построить
определить
решение
ПРД
для
в
Γ(x0 , T
− t0 )
усеченных
подыгр
игре
всех
Γ̂jv (x∗j,0 , t0 + j∆t, t0 + j∆t + T ), j = 0, . . . , l (j = 0, . . . , +∞). Обозначим
семейство подыгр для Γ̂jv (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) вдоль кооперативной траектории x∗j (t) через Γ̂jv (x∗j,0 , t0 + j∆t, t0 + j∆t + T ), где t ∈ (t0 + j∆t, t0 + j∆t + T ]
- начальный момент времени подыгры. Характеристическая функция вдоль
x∗j (t) в семействе подыгр Γ̂jv (x∗j (t), t, t0 + j∆t + T ) определена также, как и в
(2.7). Обозначим через Ej (x∗j (t), t, t0 + j∆t + T ) множество дележей в подыгре
Γ̂jv (x∗j (t), t, t0 + j∆t + T ).
Предположим, что в каждой усеченной подыгре Γ̂jv (x∗j,0 , t0 +j∆t, t0 +j∆t+T )
решение Wj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) ̸= ∅ вдоль кооперативной траектории x∗j (t) выбрано. Также предположим, что для любой усеченной подыгры
Γ̂jv (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) в начальной позиции x∗j,0 выбран дележ
ξj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) ∈ Wj (x∗j,0 , t0 + j∆t, t0 + j∆t + T )
и соответствующее ПРД
βj (t, x∗j ) = [β1j (t, x∗j ), . . . , βnj (t, x∗j )],
t ∈ (t0 + j∆t, t0 + j∆t + T ],
20
что гарантирует динамическую устойчивость выбранного дележа [17]:
ξj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) =
t0 +j∆t+T
∫
βj (t, x∗j )e−r(τ −t0 ) dt.
t0 +j∆t
ПРД βj (t, x∗j ) может быть получена путем дифференцирования дележа
ξtj (x∗j , t, t0 + j∆t + T ), соответствующая теорема представлена в [47]:
Теорема 2.3.1. Если функция ξj (x∗j , t, t0 + j∆t + T ) является непрерывно
дифференцируемой по t и x∗j , тогда
βj (t, x∗j )
]
[
j ∗
= − ξt (xj , t, t0 + j∆t + T ) −
[
] [
]
j
∗
∗ ∗j
∗j
− ξx∗j (xj , t, t0 + j∆t + T ) f xj , u1 (τ ), . . . , un (τ ) . (3.1)
Новая концепция решения в игре Γ(x0 , T −t0 ) (Γ(x0 , t0 )) состоит из комбинации решений Wj (x∗j,0 , t0 +j∆t, t0 +j∆t+T ) (соответствующих ПРД) в усеченных
подыграх Γ̂jv (x∗j,0 , t0 + j∆t, t0 + j∆t + T ), j = 0, . . . , l (j = 0, . . . , +∞). Пусть для
каждого дележа ξj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) ∈ Wj (x∗j,0 , t0 + j∆t, t0 + j∆t + T )
существует ПРД βj (t, x∗j ). Определим результирующее ПРД для всей игры
Γ(x0 , T − t0 ) (Γ(x0 , t0 )) следующим образом:
Определение 2.3.1. Результирующее ПРД β̂(t, x̂∗ ) определяется для
каждого набора ξj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) ∈ Wj (x∗j,0 , t0 + j∆t, t0 + j∆t + T )
с соответствующими ПРД βj (t, x∗j ) следующим образом:
β0 (t, x∗0 ), t ∈ [t0 , t0 ∆t],
···
β̂(t, x̂∗ ) = βj (t, x∗j ), t ∈ [t0 + j∆t, t0 + (j + 1)∆t],
···
β (t, x∗ ), t ∈ [t + l∆t, t + (l + 1)∆t],
l
0
0
l
(3.2)
где для игры Γ(x0 , T −t0 ) с предписанной продолжительностью t0 +(l +1)∆t =
T и T < ∞, а для игры Γ(x0 , t0 ) с бесконечной продолжительностью l = +∞
и соответственно t0 + (l + 1)∆t = +∞.
21
Рисунок 1.4. Комбинация ПРД βj (t, x∗j ) определенных для каждого
ξj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) ∈ Wj (x∗j,0 , t0 + j∆t, t0 + j∆t + T ), j = 0, . . . , l
определяет распределение суммарного выигрыша между игроками с помощью
β̂(t, x̂∗ ).
С помощью результирующего ПРД β̂(t, x̂∗ ) определим следующий вектор:
ˆ ∗ (t), T − t) - это вектор
Определение 2.3.2. Результирующий вектор ξ(x̂
определенный с помощью результирующего ПРД β̂(t, x̂∗ ) следующим образом,
пусть t ∈ [t0 + j∆t, t0 + (j + 1)∆t]:
ˆ ∗ (t), T − t) =
ξ(x̂
=
l
∑
m=j+1
∫T
β̂(τ, x̂∗ (τ ))e−r(τ −t0 ) dτ =
t
t0 +(m+1)∆t
∫
t
βm (τ, x∗m (τ ))e−r(τ −t0 ) dτ +
∫
0 +j∆t
βj (τ, x∗j (τ ))e−r(τ −t0 ) dτ ,
t
t0 +m∆t
(3.3)
в частности:
∫T
ˆ 0 , T − t0 ) =
ξ(x
β̂(τ, x̂∗ (τ ))e−r(τ −t0 ) dτ,
t0
где для игры Γ(x0 , T − t0 ) с предписанной продолжительностью l =
T
∆t
−1 и
T < ∞, а для игры Γ(x0 , t0 ) с бесконечной продолжительностью T = +∞ и
22
соответственно l = +∞. Для игры Γ(x0 , t0 ) вектор определенный с помощью
ˆ ∗ (t), t).
формулы (3.3) будем обозначать через ξ(x̂
Введем понятие результирующего решения в игре Γ(x0 , T − t0 ) (Γ(x0 , t0 )) с
динамическим обновлением информации:
Определение 2.3.3. Результирующее решение Ŵ (x̂∗ (t), T −t) (Ŵ (x̂∗ (t), t))
ˆ ∗ (t), T −t) (ξ(x̂
ˆ ∗ (t), t)), построенных с помощью
- это множество векторов ξ(x̂
(3.2), (3.3) для всевозможных результирующих ПРД β̂(t, x̂∗ ).
ˆ ∗ (t), T − t)
Покажем, что с помощью результирующего вектора ξ(x̂
ˆ ∗ (t), t)) и соответственно результирующего решения Ŵ (x̂∗ (t), T − t)
(ξ(x̂
(Ŵ (x̂∗ (t), t)) можно разделить фактический суммарный выигрыш между игроками:
ˆ 0 , T − t0 ) ∈
Утверждение 2.3.1.Любой результирующий вектор ξ(x
ˆ 0 , t0 ) ∈ Ŵ (x0 , t0 )) и соответствующее результирующее ПРД
Ŵ (x0 , T −t0 ) (ξ(x
β̂(t, x̂∗ (t)) распределяет текущий суммарный выигрыш игроков (2.1) вдоль
условно кооперативной траектории x̂∗ (t) в игре с предписанной продолжительностью Γ(x0 , T − t0 ) (с бесконечной продолжительностью Γ(x0 , T − t0 )),
т.е. ∀t ∈ [t0 , T ] (∀t ∈ [t0 , +∞]) выполняется:
n ∫
∑
t
β̂i (τ, x̂∗ (τ ))e−r(τ −t0 ) dτ =
i=1 t
0
n ∫
∑
t
hi (x̂∗ (τ ), û∗ (τ ))e−r(τ −t0 ) dτ.
(3.4)
i=1 t
0
Доказательство. Пусть ∀t ∈ [t0 + j∆t, t0 + (j + 1)∆t], тогда правая часть
(3.4) может быть записана:
n ∫t
∑
t
∫
n
∑
∗
∗
−r(τ −t0 )
∗
∗
−r(τ −t0 )
hi (x̂ (τ ), û (τ ))e
dτ =
dτ +
hi (xj (τ ), uj (τ ))e
i=1 t
0
i=1
j−1
n ∑
∑
+
i=1 m=0
j∆t
(m+1)∆t
∫
hi (x∗m (τ ), u∗m (τ ))e−r(τ −t0 ) dτ . (3.5)
m∆t
Из определения β̂(t, x̂∗ (t)) в (3.2) и (3.5) следует, что для доказательства (3.4)
необходимо показать, что ∀t ∈ [t0 + j∆t, t0 + (j + 1)∆t] выполняется следующее
23
равенство
∫t
n
∑
β̂i (τ, x̂∗ (τ ))e−r(τ −t0 ) dτ =
i=1 t +j∆t
0
∫t
n
∑
hi (x∗j (τ ), u∗j (τ ))e−r(τ −t0 ) dτ.
(3.6)
i=1 t +j∆t
0
В самом деле, максимальный суммарный выигрыш игроков в усеченной подыгре Γ̂j (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) равен W (j∆t) (t0 + j∆t, x∗j,0 ) (2.3), это значит, что
в соответствии с определением этой функции, для ∀t ∈ [t0 + j∆t, t0 + j∆t + T ]:
{
}
∑ j
∗
j
W (j∆t) (t, x̂∗ (t)) = max
K
(x
(t),
t;
u
) =
j
i
j
u
=
n
∑
i=1
t0 +j∆t+T
∫
i∈N
hi (x∗j (τ ), u∗j (τ ))e−r(τ −t0 ) dτ =
n
∑
t0 +j∆t+T
∫
i=1
t
βij (τ, x∗j (τ ))e−r(τ −t0 ) dτ.
t
(3.7)
Тем не менее для ∀t ∈ [t0 + j∆t, t0 + j∆t + T ] верно
W (j∆t) (t0 + j∆t, x∗j,0 ) − W (j∆t) (t, x̂∗ (t)) =
∫t
n
∑
hi (x∗j (τ ), u∗j (τ ))e−r(τ −t0 ) dτ.
i=1 t +j∆t
0
(3.8)
Из (3.7) и (3.8) следует, что для ∀t ∈ [t0 + j∆t, t0 + (j + 1)∆t]
∫t
n
∑
i=1 t +j∆t
0
hi (x∗j (τ ), u∗j (τ ))e−r(τ −t0 ) dτ =
∫t
n
∑
βij (τ, x∗j (τ ))e−r(τ −t0 ) dτ.
i=1 t +j∆t
0
По определению β̂(τ, x∗j (τ )) на интервале [t0 +j∆t, t0 +(j+1)∆t] результирующее
ПРД β̂(τ, x̂∗ (τ )) = βj (τ, x∗j (τ )). Утверждение доказано.
В соответствии с новой концепцией, результирующее решение в игре
Γ(x0 , T − t0 ) (Γ(x0 , t0 )) с динамическим обновлением информации определено
как Ŵ (x0 , T −t0 ) (Ŵ (x0 , t0 )). Результирующее решение Ŵ (x0 , T −t0 ) (Ŵ (x0 , t0 ))
является динамически устойчивым по построению. Также оказывается, что оно
обладает и свойством сильной динамической устойчивости:
Определение 2.3.4. Решение Ŵ (x0 , T − t0 ) (Ŵ (x0 , t0 )) называется сильно
∆t-динамически устойчивым, если для каждого j = 0, . . . , l (j = 0, . . . , +∞) и
24
каждого ξ(x0 , T − t0 ) ∈ W (x0 , T − t0 ) (ξ(x0 , t0 ) ∈ W (x0 , t0 )) соответствующее
ПРД β(t, x∗ ) удовлетворяет условию
t0∫
+j∆t
β(τ, x∗ (τ ))e−r(τ −t0 ) dτ ⊕ W (x∗j,0 , T − t0 + j∆t) ⊂ W (x0 , T − t0 )
t0
t
∫
(3.9)
0 +j∆t
β(τ, x∗ (τ ))e−r(τ −t0 ) dτ ⊕ W (x∗j,0 , t0 + j∆t) ⊂ W (x0 , t0 ) ,
(3.10)
t0
в котором a ⊕ A = {a + a′ : a′ ∈ A}.
Теорема 2.3.2. Результирующее решение Ŵ (x0 , T − t0 ) (Ŵ (x0 , t0 )) является сильно ∆t-динамически устойчивым в игре Γ(x0 , T − t0 ) с предписанной
продолжительностью (Γ(x0 , t0 ) с бесконечной продолжительностью).
ˆ 0 , T − t0 ) ∈
Доказательство. Пусть 0 ≤ j ≤ l (0 ≤ j ≤ +∞) и дележ ξ(x
ˆ 0 , t0 ) ∈ Ŵ (x0 , t0 )) порождает результирующее ПРД β̂(t, x̂∗ ).
Ŵ (x0 , T − t0 ) (ξ(x
Тогда для любого 0 ≤ k < j существует ξ(x∗k,0 , T − t0 + k∆t) ∈ W (x∗k,0 , T − t0 +
k∆t) (ξ(x∗k,0 , t0 + k∆t) ∈ W (x∗k,0 , t0 + k∆t)) с ПРД βk (t, x∗k ) таким, что
β̂(t, x̂∗ ) = βk (t, x∗k ),
t ∈ [t0 + k∆t, t0 + (k + 1)∆t),
0 ≤ k ≤ j − 1.
Следовательно,
t0∫
+j∆t
∗
−r(τ −t0 )
β̂(τ, x̂ (τ ))e
dτ =
j−1 ∫
∑
k=0
t0
t0 +(k+1)∆t
βk (t, x∗k (t))e−r(τ −t0 ) dt.
t0 +k∆t
Предположим, что ξ ′′ ∈ W (x∗j,0 , T − t0 + j∆t) (ξ ′′ ∈ W (x∗j,0 , t0 + j∆t)). Тогда
для любого j ≤ k ≤ l (j ≤ k ≤ +∞) существует ξk (x∗k,0 , T − t0 + k∆t) ∈
W (x∗k,0 , T − t0 + k∆t) (ξk (x∗k,0 , t0 + k∆t) ∈ W (x∗k,0 , t0 + k∆t)) с ПРД βk (t, x∗k )
такое, что β̂(t, x̂∗ ) = βk (t, x∗k ) для t ∈ [t0 + k∆t, t0 + (k + 1)∆t) и
t0 +(m+1)∆t
∫
l
∑
′′
ξ =
βm (τ, x∗m (τ ))e−r(τ −t0 ) dτ ,
m=j
t0 +m∆t
где для игры Γ(x0 , T − t0 ) с предписанной продолжительностью l =
T
∆t
−1 и
T < ∞, а для игры Γ(x0 , t0 ) с бесконечной продолжительностью T = +∞ и
соответственно l = +∞.
25
Таким образом,
t0∫
+j∆t
∗
−r(τ −t0 )
β̂(τ, x̂ (τ ))e
l
∑
dτ + ξ =
′′
m=0
t0
t0 +(m+1)∆t
∫
βm (τ, x∗m (τ ))e−r(τ −t0 ) dτ ∈
t0 +m∆t
∈ Ŵ (x0 , T − t0 ),
где для игры Γ(x0 , T − t0 ) с предписанной продолжительностью l =
T
∆t
−1 и
T < ∞, а для игры Γ(x0 , t0 ) с бесконечной продолжительностью T = +∞ и
соответственно l = +∞.
Теорема доказана.
§ 4.
Построение характеристической функции в игре с
динамическим обновлением информации
В этой и следующей главе все результаты будут описаны для игры Γ(x0 , T −
t0 ) с предписанной продолжительностью, для игр с бесконечной продолжительностью рассуждения аналогичны. Также для простоты будем считать, дискаунт
фактор в выражении для функции выигрыша и во всех связанных с ней местах
r = 0, поэтому множитель e−r(τ −t0 ) = 1.
В качестве характеристической функции в дифференциальной игре
Γ(x0 , T − t0 ) с динамическим обновлением информации будем использовать понятие результирующей характеристической функции:
Определение 2.4.1. Результирующей характеристической функцией
V (S; x̂∗ (t), T − t) в игре Γ(x̂∗ (t), T − t) с динамическим обновлением информации будем называть функцию, которая вычисляется с помощью значений характеристических функций Vj (S; x∗j (t), t, t0 + j∆t + T ) в каждой текущей усеченной подыгре Γ̂jv (x∗j (t), t, t0 + j∆t + T ) вдоль условно кооперативной траектории x̂∗ (t) для j = 0, . . . , l, ∀t ∈ [t0 + j∆t, t0 + j∆t + T ]. Пусть
26
t ∈ [t0 + j∆t, t0 + (j + 1)∆t], тогда:
∗
V (S; x̂ (t), T − t) =
l
[
∑
Vm (S; x∗m,0 , t0 + m∆t, t0 + m∆t + T )−
m=j+1
[
+
−
Vj (S; x∗j (t), t, t0
Vm (S; x∗m,1 , t0
]
+ (m + 1)∆t, t0 + m∆t + T ) +
+ j∆t + T ) −
Vj (S; x∗j,1 , t0
]
+ (j + 1)∆t, t0 + j∆t + T ) , (4.1)
где x∗j,0 = x̂∗ (t0 + j∆t) и x∗j,1 = x̂∗ (t0 + (j + 1)∆t).
ˆ 0 , T − t0 ), который
Покажем, что в этом случае результирующий вектор ξ(x
мы используем, чтобы распределить выигрыш между игроками, можно считать
дележом в игре Γ(x0 , T − t0 ) с определенной результирующей характеристической функцией V (S; x0 , T − t0 ):
ˆ 0 , T − t0 ) является дележом
Теорема 3.4.1 Результирующий вектор ξ(x
в игре Γ(x0 , T − t0 ) с динамическим обновлением информации, если для ∀t ∈
[t0 + j∆t, t0 + (j + 1)∆t], j = 0, . . . , l выполняется следующее условие:
ξij (x∗j (t), t, t0 + j∆t + T ) − Vj ({i}; x∗j (t), t, t0 + j∆t + T ) ≥
≥ ξij (x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) − Vj ({i}; x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ).
(4.2)
Доказательство. Необходимо показать, что для ∀t ∈ [t0 , T ] выполняются
следующие условия:
n
∑
ξˆi (x̂∗ (t), T − t) = V (N ; x̂∗ (t), T − t),
(4.3)
ξˆi (x̂∗ (t), t) ≥ V ({i}; x̂∗ (t), T − t).
(4.4)
i=1
ˆ ∗ (t), T − t) и V (S; x̂∗ (t), T − t) левую часть
В соответствии с определением ξ(x̂
27
(4.3) можно переписать следующим образом:
n
∑
n ∫
∑
T
ξˆi (x̂∗ (t), T − t) =
i=1
n
l
∑
∑
=
i=1
m=j+1
=
n
∑
[
i=1
i=1 t
β̂(τ, x̂∗ (τ ))dτ =
j∆t
∫
∗
βm (τ, xm (τ ))dτ +
βj (τ, x∗m (τ ))dτ =
(m+1)∆t
∫
t
m∆t
l
∑
[ m ∗
ξi (xm,0 , t0 + m∆t, t0 + m∆t + T )−
m=j+1
]
− ξim (x∗m,1 , t0 + (m + 1)∆t, t0 + m∆t + T ) +
]
[
]
+ ξij (x∗j (t), t, t0 + j∆t + T ) − ξij (x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) , (4.5)
V (N ; x0 , T −t0 ) в правой части определяется в (4.1). Так как в (4.5) выполняется
n
∑
ξij (x∗j (t), t, t0 + j∆t + T ) = Vj (N ; x∗j (t), t, t0 + j∆t + T ),
j = 0, . . . , l,
i=1
то (4.3) верно.
Перейдем к доказательству (4.4). Подставим выражение для ξˆi (x̂∗ (t), T − t)
и V ({i}; x̂∗ (t), T − t) в левую часть (4.4). В правую часть (4.4) подставим (4.1)
V ({i}; x0 , T − t0 ):
[
l
∑
ξim (x∗m,0 , t0 + m∆t, t0 + m∆t + T )−
m=j+1
]
− ξim (x∗m,1 , t0 + (m + 1)∆t, t0 + m∆t + T ) +
[
]
j ∗
j ∗
+ ξi (xj (t), t, t0 + j∆t + T ) − ξi (xj,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) ≥
[
l
∑
≥
Vm ({i}; x∗m,0 , t0 + m∆t, t0 + m∆t + T )−
m=j+1
]
− Vm ({i}; x∗m,1 , t0 + (m + 1)∆t, t0 + m∆t + T ) +
[
+
Vj ({i}; x∗j (t), t, t0
+ j∆t + T ) −
Vj ({i}; x∗j,1 , t0
]
+ (j + 1)∆t, t0 + j∆t + T )
(4.6)
28
(4.6) выполняется для ∀t ∈ [t0 , T ], если для ∀m = 0, . . . , l выполняется
ξim (x∗m,0 , t0 + m∆t, t0 + m∆t + T ) − ξim (x∗m,1 , t0 + (m + 1)∆t, t0 + m∆t + T ) ≥
Vm ({i}; x∗m,0 , t0 +m∆t, t0 +m∆t+T )−Vm ({i}; x∗m,1 , t0 +(m+1)∆t, t0 +m∆t+T )
(4.7)
и для ∀t ∈ [t0 + j∆t, t0 + (j + 1)∆t], m = 0, . . . , l выполняется
ξij (x∗j (t), t, t0 + j∆t + T ) − ξij (x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) ≥
Vj ({i}; x∗j (t), t, t0 + j∆t + T ) − Vj ({i}; x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ). (4.8)
Видно, что выполнение условия (4.8) для ∀t ∈ [t0 + j∆t, t0 + (j + 1)∆t],
m = 0, . . . , l влечет выполнение условия (4.7). Перепишем условие (4.8):
ξij (x∗j (t), t, t0 + j∆t + T ) − Vj ({i}; x∗j (t), t, t0 + j∆t + T ) ≥
≥ ξij (x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) − Vj ({i}; x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ).
(4.9)
Условие (4.9) означает, что в каждой усеченной подыгре изменение значений
характеристической функции и дележа в зависимости от времени происходит
равномерно относительно друг друга.
Теорема доказана.
В этом разделе было введено понятие характеристической функции
V (S; x0 , T − t0 ) в игре Γ(x0 , T − t0 ) с динамическим обновлением информаˆ 0 , T − t0 ) действительно
ции. Было показано, что результирующий вектор ξ(x
является дележом в классическом понимании при выполнении дополнительных
условий. Стоит заметить, что условие (4.2) выполняется не всегда.
§ 5.
Связь решения в усеченных подыграх и результирующего решения
На основе введенного понятия характеристической функции V (S; x̂∗ (t), T −
t) определим такие принципы оптимальности, как пропорциональное решение,
29
вектор Шепли, C-ядро и сильно динамически устойчивое ПРД-ядро в игре
Γ(x0 , T − t0 ) с динамическим обновлением информации:
Определение 2.5.1.Пропорциональным решением в Γ(x0 , T − t0 ) с
динамическим обновлением информации, с характеристической функцией
∗
ˆ
V (S; x̂∗ (t), T − t) будем называть дележ P rop(x̂
(t), T − t), ПРД которого рассчитывается следующим образом:
β̂iP rop (t)
=
d
(
∗
dt V ({i}; x̂ (t), T − t)
−
∑ d
∗ (t), T − t)
V
({i};
x̂
dt
i∈N
)
d
∗
V (N ; x̂ (t), T − t) ,
dt
t ∈ [t0 , T ]. (5.1)
Определение 2.5.2.Вектором Шепли в Γ(x0 , T − t0 ) с динамическим обновлением информации, с характеристической функцией V (S; x̂∗ (t), T − t) будем называть следующий дележ:
ˆ i (x∗ (t), t, t0 + j∆t + T ) =
Sh
j
∑ (|N | − |S|)!(|S| − 1)!
|N |!
S⊂N
i∈S
(
·
)
· V (S; x̂ (t), T − t) − V (S\{i}; x̂ (t), T − t) . (5.2)
∗
∗
Определение 2.5.3.C-ядром в Γ(x0 , T − t0 ) с динамическим обновлением
информации, с характеристической функцией V (S; x̂∗ (t), T − t) будем назыˆ ∗ (t), T − t), каждый из которого
вать множество Ĉ(x̂∗ (t), T − t) дележей ξ(x̂
удовлетворяет следующем условию:
∑
ˆ ∗ (t), T − t) ≥ V (S; x̂∗ (t), T − t),
ξ(x̂
∀S ⊆ N,
t ∈ [t0 , T ].
(5.3)
i∈S
Определение 2.5.4.Сильно динамически устойчивым ПРД-ядром в игре
Γ(x0 , T − t0 ) с динамическим обновлением информации, с характеристической
ˆ ∗ (t), T −t) дележей
функцией V (S; x̂∗ (t), T −t) будем называть множество C(x̂
ˆ ∗ (t), T − t), ПРД β̂(t, x̂∗ ) каждого из которых удовлетворяет следующем
ξ(x̂
30
условию:
−
∑
d
d
V (S; x̂∗ (t), T −t)−V (N \S; x̂∗ (t), T −t) ≥
β̂i (t, x̂∗ ) ≥ − V (S; x̂∗ (t), T −t),
dt
dt
i∈S
∑
d
∀S ⊂ N,
β̂i (t, x̂∗ ) = − V (N ; x̂∗ (t), T − t). (5.4)
dt
i∈N
Покажем, что если игроки в каждой усеченной подыгре будут выбирать дележ ξj (x∗j (t), t, t0 +j∆t+T ) ∈ Ej (x∗j (t), t, t0 +j∆t+T ) на основе Vj (S; x∗j (t), t, t0 +
j∆t + T ), j = 0, . . . , l по одинаковому правилу, то предложенный результируюˆ ∗ (t), T − t) соответствует дележу, выбранному по такому же пращий дележ ξ(x̂
вилу на основе предложенной характеристической функции V (S; x̂∗ (t), T − t).
Докажем это для приведенных принципов оптимальности.
Сначала покажем, что если в каждой усеченной подыгре Γ̂j (x∗j , t, t0 +j∆t+T )
игроки будут выбирать вектор Шепли Shj (x∗j (t), t, t0 + j∆t + T ) в качестве
ˆ ∗ (t), T − t) (3.3) будет
дележа, то соответствующий результирующий вектор ξ(x̂
ˆ ∗ (t), t, t0 + j∆t + T ) (5.2), рассчитанным на
совпадать с вектором Шепли Sh(x
j
основе результирующей характеристической функции V (S; x̂∗ (t), T − t) (4.1).
Теорема 2.5.1. Пусть в каждой усеченной подыгре Γ̂j (x∗j , t, t0 + j∆t + T ):
ξj (x∗j (t), t, t0 + j∆t + T ) = Shj (x∗j (t), t, t0 + j∆t + T ),
где t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l. Тогда результирующий вектор
ˆ ∗ (t), T − t) будет совпадать с Sh(x̂
ˆ ∗ (t), T − t) (5.2):
ξ(x̂
ˆ ∗ (t), T − t) = Sh(x̂
ˆ ∗ (t), T − t),
ξ(x̂
∀t ∈ [t, T ],
ˆ ∗ (t), T − t) - это вектор Шепли, рассчитанный на основе результигде Sh(x̂
рующей характеристической функции V (S; x̂∗ (t), T − t) (4.1).
Доказательство.
ˆ ∗ (t), T − t) рассчитывается с
В данном случае результирующий дележ ξ(x̂
помощью формул (3.2), (3.3) на основе значений Shj (x∗j (t), t, t0 + j∆t + T ) в
каждой усеченной подыгре Γ̂j (x∗j (t), t, t0 + j∆t + T ):
31
[
l
∑
ˆ ∗ (t), T − t) =
ξ(x̂
Shm (x∗m,0 , t0 + m∆t, t0 + m∆t + T )−
m=j+1
]
− Shm (x∗m,1 , t0 + (m + 1)∆t, t0 + m∆t + T ) +
[
]
+ Shj (x∗j (t), t, t0 + j∆t + T ) − Shj (x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) , (5.5)
где Shj (x∗j (t), t, t0 + j∆t + T ), t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l рассчитывается по формуле
Shji (x∗j (t), t, t0 + j∆t + T ) =
·
(
∑ (|N | − |S|)!(|S| − 1)!
S⊂N
i∈S
Vj (S; x∗j (t), t, t0
+ j∆t + T ) −
|N |!
·
Vj (S\{i}; x∗j (t), t, t0
)
+ j∆t + T ) . (5.6)
ˆ ∗ (t), T − t) рассчитывается по формуле (5.2). Подставим в определение
Sh(x̂
ˆ ∗ (t), T − t) (5.2) выражение для V (S; x̂∗ (t), T − t) (4.1), пусть t ∈ [t0 +
Sh(x̂
j∆t, t0 + (j + 1)∆t]:
ˆ ∗ (t), T − t) =
Sh(x̂
(
·
∑ (|N | − |S|)!(|S| − 1)!
|N |!
S⊂N
i∈S
[
l
∑
[
Vm (S; x∗m,0 , t0 + m∆t, t0 + m∆t + T )−
m=j+1
−
·
Vm (S; x∗m,1 , t0
]
+ (m + 1)∆t, t0 + m∆t + T ) −
[
− Vm (S\{i}; x∗m,0 , t0 + m∆t, t0 + m∆t + T )−
]
]
− Vm (S\{i}; x∗m,1 , t0 + (m + 1)∆t, t0 + m∆t + T ) +
[
+
−
Vj (S; x∗j,1 , t0
[
Vj (S; x∗j (t), t, t0 + j∆t + T )−
]
[
+ (j + 1)∆t, t0 + j∆t + T ) − Vj (S\{i}; x∗j (t), t, t0 + j∆t + T )−
])
]
− Vj (S\{i}; x∗j,1 , t0 + (j + 1)∆t, t0 + j∆t + T )
. (5.7)
32
При подстановке (5.6) в (5.5) и после выноса знака суммы мы получим правую
часть (5.7).
Теорема доказана.
Покажем, что если в каждой усеченной подыгре Γ̂j (x∗j (t), t, t0 + j∆t + T )
игроки будут выбирать пропорциональное решение P ropj (x∗j (t), t, t0 + j∆t +
ˆ ∗ (t), T − t)
T ) (??), то результирующий вектор, определенный по формуле ξ(x̂
∗
ˆ
(3.3) будет совпадать с пропорциональным решением P rop(x̂
(t), T − t) (5.1),
рассчитанным на основе характеристической функции V (S; x̂∗ (t), T − t) (4.1).
Теорема 2.5.2. Пусть в каждой усеченной подыгре Γ̂j (x∗j , t, t0 + j∆t + T )
ξj (x∗j (t), t, t0 + j∆t + T ) = P ropj (x∗j (t), t, t0 + j∆t + T ),
где t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l. Тогда результирующий вектор
∗
ˆ ∗ (t), T − t) будет совпадать с P rop(x̂
ˆ
ξ(x̂
(t), T − t) (5.1):
∗
ˆ ∗ (t), T − t) = P rop(x̂
ˆ
ξ(x̂
(t), T − t),
∀t ∈ [t, T ],
∗
ˆ
где P rop(x̂
(t), T −t) - это пропорциональное решение, рассчитанное на основе
характеристической функции V (S; x̂∗ (t), T − t) (4.1).
ˆ ∗ (t), T − t)
Доказательство. В данном случае результирующий вектор ξ(x̂
рассчитывается с помощью формулы (3.2) для ПРД на основе комбинации значений ПРД для пропорционального решения (??) в каждой усеченной подыгре
на временном интервале [t0 + j∆t, t0 + (j + 1)∆t]. Пусть i ∈ N :
βiP rop,j (t)
=
d
∗
(
dt Vj ({i}; xj , t, t0 + j∆t + T )
∑ d
∗
dt Vj ({i}; xj , t, t0 + j∆t + T )
i∈N
)
d
∗
− Vj (N ; xj , t, t0 + j∆t + T ) (5.8)
.
dt
∗
ˆ
Покажем, что формула для P rop(x̂
(t), T − t), а именно для его ПРД
β̂ P rop (t) (5.1) сводится к правой части (5.8). Подставим в (5.1) выражение
для V (S; x̂∗ (t), T − t) (4.1). Рассмотрим отдельно одно из слагаемых. Пусть
33
t ∈ [t0 + j∆t, t0 + (j + 1)∆t]:
)
d
d (
−
V ({i}; x̂∗ (t), T − t) = −
dt
dt
−
Vk ({i}; x∗k,0 , t0
(
l
[
∑
Vk ({i}; x∗k,0 , t0 + k∆t, t0 + k∆t + T )−
k=j+1
]
+ (k + 1)∆t, t0 + k∆t + T ) +
)
]
+ Vj ({i}; x∗j (t), t, t0 + j∆t + T ) − Vj ({i}; x∗j,0 , t0 + (j + 1)∆t, t0 + j∆t + T ) .
[
(5.9)
Из (5.9) видно, что для t ∈ [t0 + j∆t, t0 + (j + 1)∆t], j = 0, . . . , l под знаком
производной находится только одно слагаемое, зависящее от t, поэтому
)
)
d(
d(
∗
∗
−
Vj ({i}; xj (t), t, t0 + j∆t + T ) .
V ({i}; x̂ (t), T − t) = −
(5.10)
dt
dt
Подставим (5.10) и аналогичную формулу для V (N ; x̂∗ (t), T −t) в (5.1). Нетрудно убедиться, что в этом случае правые части (5.8) и (5.1) совпадают.
Теорема доказана.
Покажем теперь, что если в каждой усеченной подыгре Γ̂j (x∗j , t, t0 +
j∆t + T ) игроки будут выбирать в качестве принципа оптимальности C-ядро
Cj (x∗j (t), t, t0 +j∆t+T ), то результирующее решение, каждый элемент которого
ˆ ∗ (t), T − t) рассчитан по формуле (3.3), будет являться C-ядром, рассчитанξ(x̂
ным на основе результирующей характеристической функции V (S; x̂∗ (t), T − t)
(4.1).
Теорема 2.5.3. Пусть в каждой усеченной подыгре Γ̂j (x∗j , t, t0 + j∆t + T ):
Wj (x∗j (t), t, t0 + j∆t + T ) = Cj (x∗j (t), t, t0 + j∆t + T ),
где ∀t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l, тогда для всех ξj (x∗j (t), t, t0 + j∆t +
T ) ∈ Cj (x∗j (t), t, t0 + j∆t + T ), для которых выполняется условие
∑
ξij (x∗j (t), t, t0 + j∆t + T ) − Vj (S; x∗j (t), t, t0 + j∆t + T ) ≥
i∈S
≥
∑
ξij (x∗j,1 , t0 +(j +1)∆t, t0 +j∆t+T )−Vj (S; x∗j,1 , t0 +(j +1)∆t, t0 +j∆t+T ),
i∈S
(5.11)
34
верно, что
ˆ ∗ (t), T − t) ∈ Ĉ(x̂∗ (t), T − t),
ξ(x̂
∀t ∈ [t, T ],
где Ĉ(x̂∗ (t), T − t) - это C-ядро, рассчитанное на основе результирующей характеристической функции V (S; x̂∗ (t), T − t) (4.1).
Доказательство. Стоит отметить, что для доказательства этой теоремы
необходимо будет доказать два утверждения:
1. Если игроки в каждой усеченной подыгре будут выбирать дележ
ξj (x∗j (t), t, t0 + j∆t + T )
∈
Cj (x∗j (t), t, t0 + j∆t + T ) на основе
Vj (S; x∗j (t), t, t0 + j∆t + T ), j = 0, . . . , l, то предложенный результируюˆ ∗ (t), T − t) будет принадлежать C-ядру Ĉ(x̂∗ (t), T − t),
щий вектор ξ(x̂
рассчитанному на основе предложенной характеристической функции
V (S; x̂∗ (t), T − t).
2. C-ядро Ĉ(x̂∗ (t), T − t) (5.3) не должно содержать дележей
ˆ ∗ (t), T − t), для которых нельзя найти набора дележей в усеченξ(x̂
ных подыграх ξj (x∗j (t), t, t0 + j∆t + T ) ∈ Cj (x∗j (t), t, t0 + j∆t + T ).
Докажем
первое
условие,
а
именно,
что
если
набор
дележей
ξij (x∗j (t), t, t0 + j∆t + T ), удовлетворяет системе неравенств:
∑
ξij (x∗j (t), t, t0 + j∆t + T ) ≥ Vj (S; x∗j (t), t, t0 + j∆t + T ),
S ⊂ N,
i∈S
для любых t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l, i = 1, . . . , n, то результируˆ ∗ (t), T − t) удовлетворяет системе неравенств:
ющий вектор ξ(x̂
∑
ξˆi (x̂∗ (t), T − t) ≥ V (S; x̂∗ (t), T − t),
∀t ∈ [t0 , T ],
S ⊂ N.
(5.12)
i∈S
ˆ ∗ (t), T − t) в левую часть (5.12). В правую часть
Подставим выражение для ξ(x̂
(5.12) подставим (4.1). Поступим также, как и в теореме 3.4.1. Покажем, для
любого S ⊂ N , t ∈ [t0 + j∆t, t0 + j∆t + T ] выполнение (5.12) сводится к выполнению условия (5.11). Первое условие доказано.
Перейдем к доказательству второго условия, а именно, что в множестве
наборов дележей ξij (x∗j (t), t, t0 + j∆t + T ), i = 1, . . . , n, j = 0, . . . , l, удовлетво-
35
ряющих системе неравенств ∀j = 0, . . . , l, S ⊂ N :
l
[
∑
ξim (x∗m (t), t, t0 + m∆t + T )−
m=j+1
−
ξim (x∗m,1 , t0
]
+ (m + 1)∆t, t0 + m∆t + T ) +
[
]
j ∗
j ∗
+ ξi (xj (t), t, t0 + j∆t + T ) − ξi (xj,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) ≥
≥
l
[
∑
Vm (S; x∗m,0 , t0 + m∆t, t0 + m∆t + T )−
m=j+1
Vm (S; x∗m,1 , t0
]
+ (m + 1)∆t, t0 + m∆t + T ) +
−
]
[
∗
∗
+ Vj (S; xj (t), t, t0 + j∆t + T ) − Vj (S; xj,1 , t0 + (j + 1)∆t, t0 + j∆t + T ) ,
(5.13)
существует хотя бы один набор ξij (x∗j (t), t, t0 + j∆t + T ), i = 1, . . . , n, j = 0, . . . , l
удовлетворяющий:
∑ j
ξi (x∗j (t), t, t0 + j∆t + T ) ≥
i∈S
≥ Vj (S; x∗j , t, t0 + j∆t + T ),
∀j = 0, . . . , l,
S ⊂ N. (5.14)
Докажем это от противного. Допустим, что для дележей удовлетворяющих
(5.11) и (5.14) не выполняется (5.13). Покажем, что для ∀j = 0, . . . , l выполняется:
∑
ξij (x∗j (t), t, t0 + j∆t + T ) − Vj (S; x∗j (t), t, t0 + j∆t + T ) ≥
i∈S
≥
∑
ξij (x∗j,1 , t0 +(j +1)∆t, t0 +j∆t+T )−Vj (S; x∗j,1 , t0 +(j +1)∆t, t0 +j∆t+T ),
i∈S
(5.15)
тогда на из (5.14) получается, что знак правой и левой части всегда положительный, а из (5.11) следует, что в этом случае (5.15) выполняется.
Теорема доказана.
Покажем
теперь,
что
если
в
каждой
усеченной
подыгре
Γ̂j (x∗j , t, t0 + j∆t + T ) игроки будут выбирать в качестве принципа оптимальности сильно динамически устойчивое ПРД-ядро C j (x∗j (t), t, t0 + j∆t + T )
36
(глава 1, (??)), то результирующее решение, каждый элемент которого определен по формуле (3.3), будет являться сильно динамически устойчивым
ПРД-ядром, рассчитанным на основе результирующей характеристической
функции V (S; x̂∗ (t), T − t) (4.1).
Теорема 2.5.4. Пусть в каждой усеченной подыгре Γ̂j (x∗j , t, t0 + j∆t + T )
Wj (x∗j (t), t, t0 + j∆t + T ) = C j (x∗j (t), t, t0 + j∆t + T ) ̸= ∅,
где ∀t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l, тогда
ˆ ∗ (t), T − t),
Ŵ (x̂∗ (t), T − t) = C(x̂
∀t ∈ [t, T ],
ˆ ∗ (t), T − t) - это сильно динамически устойчивое ПРД-ядро, рассчигде C(x̂
танное на основе характеристической функции V (S; x̂∗ (t), T − t) (4.1).
Доказательство.
Результирующее
решение
Ŵ (x̂∗ (t), T
− t)
состоит
из
векторов
ˆ ∗ (t), T − t), каждый из которых определяется с помощью ПРД набора
ξ(x̂
дележей ξj (x∗j (t), t, t0 + j∆t + T ) ∈ C j (x∗j (t), t, t0 + j∆t + T ), j = 0, . . . , l по формуле (3.2). По построению ПРД для каждого дележа из сильно динамически
устойчивого ПРД-ядра удовлетворяет следующей системе неравенств (глава 1,
(??)):
)
d(
∗
∗
−
Vj (N ; xj (t), t, t0 + j∆t + T ) − Vj (N \ S; xj (t), t, t0 + j∆t + T ) ≥
dt
)
∑ j
d(
≥
βi (t, x̂∗ (t)) ≥ −
Vj (S; x∗j (t), t, t0 + j∆t + T ,
dt
i∈S
)
∑ j
d(
∗
∗
Vj (N ; xj (t), t, t0 + j∆t + T ) , ∀S ⊂ N. (5.16)
βi (t, x̂ (t)) = −
dt
i∈N
Таким образом, результирующее решение Ŵ (x̂∗ (t), T − t) определяется с помощью (5.16) для t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l.
ˆ ∗ (t), T − t) (5.4). Покажем, что эта система
Выпишем выражение для C(x̂
сводится к (5.16). Рассмотрим отдельно одно из ограничений в (5.4) при t ∈
[t0 + j∆t, t0 + (j + 1)∆t] и подставим туда выражение для V (S; x̂∗ (t), T − t) (4.1):
37
l
)
d(
d( ∑ [
∗
Vk (S; x∗k,0 , t0 + k∆t, t0 + k∆t + T )−
−
V (S; x̂ (t), T − t) = −
dt
dt
k=j+1
]
∗
− Vk (S; xk,0 , t0 + (k + 1)∆t, t0 + k∆t + T ) +
[
])
∗
∗
+ Vj (S; xj (t), t, t0 + j∆t + T ) − Vj (S; xj,0 , t0 + (j + 1)∆t, t0 + j∆t + T ) .
(5.17)
Из (5.17) видно, что для t ∈ [t0 + j∆t, t0 + (j + 1)∆t], j = 0, . . . , l под знаком
производной находится только одно слагаемое зависящее от t, поэтому
)
)
d(
d(
∗
∗
−
V (S; x̂ (t), T − t) = −
Vj (S; xj (t), t, t0 + j∆t + T ) .
dt
dt
(5.18)
Подставим (5.18) и аналогичные формулы для V (N ; x̂∗ (t), T − t) и V (N \
S; x̂∗ (t), T − t) в (5.4):
)
d(
−
Vj (N ; x̂∗ (t), t, t0 + j∆t + T ) − Vj (N \ S; x̂∗ (t), t, t0 + j∆t + T ) ≥
dt
)
∑
d(
∗
∗
β̂i (t, x̂ (t)) ≥ −
≥
Vj (S; xj (t), t, t0 + j∆t + T ) ,
dt
i∈S
)
∑
d(
∗
∗
β̂i (t, x̂ (t)) = −
Vj (N ; x̂ (t), t, t0 + j∆t + T ) , ∀S ⊂ N.
dt
i∈N
Таким
образом,
сильно
динамически
устойчивое
ПРД-ядро
ˆ ∗ (t), T − t), рассчитанное на основе результирующей характеристиC(x̂
ческой функции V (S; x̂∗ (t), T − t), совпадает с результирующим решением Ŵ (x̂∗ (t), T − t), рассчитанным с помощью комбинации решений
C j (x∗j (t), t, t0 + j∆t + T ) в усеченных подыграх.
Теорема доказана.
Таким образом, в этом разделе было показано, что если игроки в каждой усеченной подыгре Γ̂j (xj,0 , t0 +j∆t, t0 +j∆t+T ) в качестве принципа оптимальности
будут выбирать пропорциональное решение, вектор Шепли, дележ из С-ядра
или дележ из сильно динамически устойчивого ПРД-ядра, то результирующий
дележ также будет являться пропорциональным решением, вектором Шепли,
дележом из С-ядра или дележом из сильно динамически устойчивого ПРД-ядра
в игре Γ(x0 , T − t0 ) с динамическим обновлением информации.
38
Доказанные теоремы в этом параграфе для пропорционального решения,
вектора Шепли, C-ядра и сильно динамически устойчивого ПРД-ядра в частности означает, что для того, чтобы вычислить их в игре Γ(x̂∗ (t), T −t) с динамическим обновлением информации не необходимо рассчитывать P ropj (x∗j (t), t, t0 +
j∆t + T ), Shj (x∗j (t), t, t0 + j∆t + T ), Cj (x∗j (t), t, t0 + j∆t + T ), C j (x∗j (t), t, t0 +
j∆t + T ) для каждой усеченной подыгры Γ̂j (x∗j , t, t0 + j∆t + T ). Достаточно лишь вычислить значения результирующей характеристической функции
∗
ˆ
V (S; x̂∗ (t), T − t), S ⊂ N и использовать их при расчете P rop(x̂
(t), T − t),
ˆ ∗ (t), T − t) в качестве характеристической
ˆ ∗ (t), T − t), Ĉ(x̂∗ (t), T − t), C(x̂
Sh(x̂
функции. Без этого результата нельзя было бы построить Ĉ(x̂∗ (t), T − t), т.к.
построение C-ядра с помощью формул 3.2 и 3.3 не представляется конструктивным.
§ 6.
Кооперативная игра добычи ограниченного ресурса с динамическим обновлением информации
Рассмотрим игру добычи ограниченного ресурса на ограниченном временном интервале. Решение игры двух лиц в классическом виде представлено в
[48]. Проблема динамической устойчивости была изучена Дэвидом Янгом [47].
В этом примере представлена игра добычи ограниченного ресурса с динамическим обновлением информации для трех лиц. В качестве принципа оптимальности используется C-ядро. Характеристическая функция рассчитывается также,
как это сделано в [39]. В последней части примера показано свойство сильной
динамической устойчивости. Модель игры с бесконечной продолжительностью
может быть построена аналогично и была рассмотрена в деталях в работе [22].
Исходная игра. Уравнения движения, описывающие изменение запаса ресурса x(t) ∈ X ⊂ R, имеют следующий вид:
3
∑
√
ẋ = a x(t) − bx(t) −
ui ,
i=1
где ui - уровень добычи игрока i = 1, 3.
x(t0 ) = x0 ,
39
Запишем функцию выигрыша игрока i:
∫T
Ki (x0 , t0 ; u) =
hi (x(τ ), u(τ ))dτ,
t0
здесь
hi (x(τ ), u(τ )) =
√
ui (τ ) − √
ci
x(τ )
ui (τ ),
i = 1, 3,
где ci - константа, ci ̸= ck , ∀i ̸= k = 1, 3.
Усеченная подыгра. Исходная игра Γ(x0 , T −t0 ) определена на временном
интервале [t0 , T ]. Предположим, что для любого t ∈ [t0 + j∆t, t0 + (j + 1)∆t],
j = 0, . . . , l, игроки имеют усеченную информацию об игре. Она включает в себя информацию об уравнениях движения и функциях выигрыша на временном
интервале [t0 +j∆t, t0 +j∆t+T ]. Смоделируем это с помощью усеченной подыгры Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ). Уравнения движения и начальные данные
имеют следующий вид:
3
∑
√
ẋ = a x(t) − bx(t) −
ui ,
x(t0 + j∆t) = xj,0 .
(6.1)
i=1
функция выигрыша игрока i:
t0 +j∆t+T
∫
Kij (xj,0 , t0 + j∆t, t0 + j∆t + T ; u) =
hi (x(τ ), u(τ ))dτ.
t0 +j∆t
Рассмотрим случай, когда игроки соглашаются на кооперацию в усеченной
подыгре Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ). Тогда игроки будут действовать исходя
из максимизации их суммарного выигрыша.
Кооперативная траектория. Максимальный суммарный выигрыш в
каждой усеченной подыгре Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ) имеет следующий
вид [48]:
√
W j (t, x) = Aj (t) x + C j (t),
(6.2)
где функции Aj (t), C j (t) удовлетворяют системе дифференциальных уравне-
40
ний:
Ȧj (t) =
b j
A (t) −
2
3
∑
i=1
[ 1
] ,
Aj (t)
4 ci + 2
a
Ċ j (t) = − Aj (t),
2
j
A (t0 + j∆t + T ) = 0, C j (t0 + j∆t + T ) = 0.
Кооперативная траектория x∗j (t) в каждой усеченной подыгре может быть
вычислена на временном интервале следующим образом [48]:
2
t
∫
√
1
∗
2
∗
ϖj (t0 + j∆t, τ )−1 dτ ,
xj (t) = ϖj (t0 + j∆t, t) xj,0 + a ·
2
t0 +j∆t
где t ∈ [t0 + j∆t, t0 + j∆t + T ] и
∫t
ϖj (t0 + j∆t, t) = exp
t0 +j∆t
1
− b +
2
3
∑
i=1
1
dτ.
[
]
2
Aj (τ )
4 ci + 2
Начальное положение для кооперативной траектории в каждой усеченной
подыгре устанавливается из предыдущей усеченной подыгры: x∗0,0 = x0 и
x∗j,0 = x∗j−1 (t0 + j∆t) для 1 ≤ j ≤ l. Определим условно кооперативную траекторию x̂∗ (t) в игре Γ(x0 , T − t0 ):
x̂∗j (t) = x∗j (t),
t ∈ [t0 + j∆t, t0 + (j + 1)∆t],
j = 0, . . . , l.
Характеристическая функция. Для того, чтобы распределить максимальный суммарный выигрыш между игроками в каждой усеченной подыгре
необходимо определить значения характеристической функции Vj (S; xj,0 , t0 +
j∆t, t0 + j∆t + T ) (Vj (S; x∗j (t), t, t0 + j∆t + T )) для каждой коалиции S ⊂ N .
В соответствии с формулой (2.7) максимальный суммарный выигрыш игроков Wj (t0 + j∆t, xj,0 ) (6.2) соответствует значению характеристической функции Vj (N ; xj,0 , t0 + j∆t, t0 + j∆t + T )) коалиции S = N в усеченной подыгре
Γ̂jv (xj,0 , t0 + j∆t, t0 + j∆t + T ):
Vj (N ; x∗j (t), t, t0 + j∆t + T ) = Wj (t, x∗j (t)),
(6.3)
41
где t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l. Далее, нам необходимо определить
значения характеристической функции для следующих коалиций:
{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}.
Для каждой коалиции вида {i}, i = 1, 3 нам необходимо определить равновесие
по Нэшу в усеченной подыгре Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ) и как результат
Vj ({i}; x∗j (t), t, t0 + j∆t + T ).
Коалиции, состоящие из одного игрока. Равновесие по Нэшу в усеченной подыгре Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ) определяется следующими стратегиями игроков:
uji (t, x) =
x
4[ci + Aji (t)/2]2
,
i = 1, 3,
где функции Aji (t) для i = 1, 3 находятся из системы дифференциальных уравнений:
Ȧji (t)
=
b
Aji (t)
2
+
∑
1
k̸=i
8(ck + Ajk (t)/2)2
−
1
4(ci + Aji (t)/2)
,
a
Ċij (t) = − Aji (t),
2
j
Ai (t0 + j∆t + T ) = 0, Cij (t0 + j∆t + T ) = 0.
Выигрыш игрока i = 1, 3 в ситуации равновесия по Нэшу определяется
функцией:
√
Vij (t, x) = Aji (t) x + Cij (t),
i = 1, 3.
Таким образом, значение характеристической функции для коалиций состоящих из одного игрока S = {i}, i ∈ N вычисляется следующим образом:
Vj ({i}; x∗j (t), t, t0 + j∆t + T ) = Vij (t, x∗j (t)),
(6.4)
где t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l.
Коалиции, состоящие из двух игроков. В соответствии с формулой
(2.7) значение характеристической функции Vj (S; xj,0 , t0 + j∆t, t0 + j∆t + T )
(Vj (S; x∗j (t), t, t0 + j∆t + T )) для коалиций состоящих из двух игроков S =
42
{1, 2}, {1, 3}, {2, 3} определяется, как наилучший ответ коалиции против страE,j
E,j
E,j
E
тегий, входящих в ситуацию равновесия по Нэшу uN
= (uN
, uN
, uN
)в
j
1
2
3
усеченной подыгре Γ̂j (xj,0 , t0 + j∆t, t0 + j∆t + T ), используемых игроками не
входящими в коалицию. В нашем случае это означает, что игроки из коалиции S действуют как один игрок и максимизируют свой суммарный выигрыш.
Используя этот подход, мы определим равновесие между двумя игроками: комбинированный игрок (коалиция S), игрок не входящий в коалицию S (коалиция
N/S).
Рассмотрим
формулы
для
Vj (S; xj,0 , t0 + j∆t, t0 + j∆t + T )
(Vj (S; x∗j (t), t, t0 + j∆t + T )) в случае, когда S = {1, 2}, формулы для
вычисления остальных коалиций можно получить по такому же принципу. Значения выигрышей игроков в ситуации равновесия по Нэшу имеют
следующий вид:
√
j
j
V{1,2}
(t, x) = Aj{1,2} (t) x + C{1,2}
(t),
√
V3j (t, x) = Aj3 (t) x + C3j (t),
j
где функции Aj{1,2} (t), Aj3 (t), C{1,2}
(t), C3j (t) удовлетворяют системе дифферен-
циальных уравнений:
[
]
∑
b
1
1
+
−
,
j
j
2 8(c3 + A3 (t)/2)2
4(c
+
A
(t)/2)
k
{1,2}
[
]k∈S
b ∑
1
1
Ȧj3 (t) = Aj3 (t)
+
,
−
j
j
2
2
8(c
+
A
4(c
+
A
(t)/2)
(t)/2)
k
3
3
{1,2}
k∈S
a
a
j
Ċ{1,2}
(t) = − Aj{1,2} (t), Ċ3j (t) = − Aj3 (t)
2
2
Ȧj{1,2} (t) = Aj{1,2} (t)
со следующими ограничениями Aj{1,2} (t0 + j∆t + T ) = 0, Aj3 (t0 + j∆t + T ) = 0,
j
C{1,2}
(t0 + j∆t + T ) = 0, C3j (t0 + j∆t + T ) = 0.
Таким образом, значение характеристической функции коалиции S = {1, 2}
вычисляется следующим образом:
j
Vj ({1, 2}; x∗j (t), t, t0 + j∆t + T ) = V{1,2}
(t, x∗j (t)),
где t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l.
(6.5)
43
Концепция решения. Пусть игроки в каждой кооперативной усеченной
подыгре Γ̂jv (xj,0 , t0 +j∆t, t0 +j∆t+T ) используют в качестве принципа оптимальности C-ядро Cj (x∗j (t), T −t) (Cj (x0 , T −t0 )). Это означает, что игроки в каждой
усеченной подыгре выбирают дележ ξj (x∗j , t, t0 + j∆t + T ) ∈ Cj (x∗j (t), T − t) по
следующему правилу:
∑ j
ξi (x∗j , t, t0 + j∆t + T ) ≥ Vj (S; x∗j (t), t, t0 + j∆t + T ),
S ⊂ N,
i∈S
для любого t ∈ [t0 +j∆t, t0 +j∆t+T ], j = 0, . . . , l. Тогда результирующий вектор
ˆ ∗ (t), T − t) для любого набора дележей в усеченных подыграх ξj (x∗ , t, t0 +
ξ(x̂
j
j∆t + T ) ∈
Cj (x∗j (t), T
− t), t ∈ [t0 + j∆t, t0 + j∆t + T ], j = 0, . . . , l может быть
вычислен по формуле (3.3). Через Ĉ(x̂∗ (t), T − t) (Ĉ(x0 , T − t0 )) обозначим
ˆ ∗ (t), T − t) (ξ(x
ˆ 0 , T − t0 )), построенных с помощью (3.2),
множество векторов ξ(x̂
(3.3).
На основе результатов, полученных в § 4 и § 5, решение Ĉ(x̂∗ (t), T −t) можно
построить по следующему правилу:
∑
ˆ ∗ (t), T − t) ≥ V (S; x̂∗ (t), T − t),
ξ(x̂
S ⊂ N,
(6.6)
i∈S
где V (S; x̂∗ (t), T − t) вычисляется по формуле (4.1)
Далее на примере конкретных дележей из Ĉ(x̂∗ (t), T − t) покажем, что
построенное решение является сильно ∆t-динамически устойчивым в игре
Γ(x0 , T − t0 ).
Численный пример. Рассмотрим численный пример игры добычи ограниченного ресурса заданного на временном интервале длинной T − t0 = 4, в
котором информация об игре известна на временном интервале с продолжительностью T = 2 и обновляется каждый ∆t = 1 временной интервал. Зафиксируем следующие параметры для уравнения движения a = 5, b = 0.3, для
функции выигрыша c1 = 0.15, c2 = 0.65, c3 = 0.45 и для начальных условий
t0 = 0, x0 = 250.
На графике 2.5. показаны оптимальные стратегии для первого игрока в игре
с динамическим обновлением информации (сплошная линия) и оптимальные
стратегии в исходной игре [48] (пунктирная линия).
44
Рисунок 1.5. Оптимальные стратегии игрока 1 в игре с динамическим
обновлением информации (сплошная линия) и оптимальные стратегии в
исходной игре [48] (пунктирная линия).
Условно кооперативная траектория x̂∗ (t) составлена из кооперативных траекторий в усеченных подыграх Γ̂j (x∗j,0 , t0 + j∆t, t0 + j∆t + T ) с уравнениями
движения (6.1). На рисунке 2.6. представлено сравнение условно кооперативной траектории x̂∗ (t) (сплошная линия) в игре с динамическим обновлением
информации и кооперативной траектории x∗ (t) (пунктирная линия) в исходной
игре Γ(x0 , T − t0 ) [48]. Видно, что в случае ограниченной информации выработка ресурсов происходит быстрее, т.к. игроки ориентируются на урезанный
временной интервал. Ось абсцисс на рисунке 2.6. определяет время t, ось ординат определяет запас ресурса x.
На основе значений характеристических функций
Vj (S; x∗j (t), t, t0 + j∆t + T ),
t ∈ [t0 + j∆t, t0 + (j + 1)∆t],
S ⊂ N,
i = 0, . . . , l,
вычисленных в (6.3), (6.4), (6.5) получим выражение для результирующей характеристической функции V (S; x̂∗ (t), T − t) (4.1), t ∈ [t0 , T ]. Далее с помощью
(6.6) построим Ĉ(x̂∗ (t), T − t) в игре с динамическим обновлением информации
Γ(x0 , T − t0 ) (см. Рис.2.9., Рис.2.10.).
Продемонстрируем свойство сильной ∆t динамической устойчивости решения Ĉ(x̂∗ (t), T −t). Предположим, что в начале игры Γ(x0 , T −t0 ) игроки догово∗
ˆ
рились использовать пропорциональное решение P rop(x̂
(t), T − t) (5.1) (далее
45
Рисунок 1.6. Условно кооперативная траектория x̂∗ (t) (сплошная линия) в
игре с динамическим обновлением информации и кооперативная траектория
x∗ (t) (пунктирная линия) в исходной игре [48].
∗
ˆ
покажем, что при заданных параметрах P rop(x̂
(t), T −t) ∈ Ĉ(x̂∗ (t), T −t)). Те-
перь предположим, что в некоторый момент времени tbr = t0 + m∆t ∈ [t0 , T ] игроки решили, что пропорциональное решение больше их не устраивает и выбраˆ ∗ (t), T −t),
ли другой дележ из Ĉ(x̂∗ (tbr ), T −tbr ), например, вектор Шепли Sh(x̂
t ∈ [tbr , T ] (5.2). Рассчитаем ПРД для пропорционального решения и вектора
Шепли по формулам (3.1).
Пусть m = 2, тогда ПРД для комбинированного решения (3.2) имеет следующий вид:
β̂(t, x̂∗ ) =
β̂ P rop (t, x̂∗ ), t ∈ [t0 , tbr ],
β̂ Sh (t, x̂∗ ),
t ∈ (tbr , T ].
(6.7)
На графике 2.8. изображены ПРД пропорционального решения, который выбрали игроки в начале игры β̂ P rop (t, x̂∗ ) (глава 1, (??)) (сплошная линия) и
ПРД β̂(t, x̂∗ ) для комбинированного решения (6.7) (пунктирная линия).
Проинтегрируем комбинированное решение β̂(t, x̂∗ ) (6.7) по t и получим соˆ ∗ (t), T −t). В соответствии с
ответствующий дележ (3.3), обозначим его через ξ(x̂
ˆ ∗ (t), T −t) игроки разделят суммарный выигрыш в игре Γ(x0 , T −t0 )
дележом ξ(x̂
с динамическим обновлением информации следующим образом:
ˆ ∗ (t), T − t) = (12.3, 30.2, 16.8).
ξ(x̂
46
Рисунок 1.7. Условно кооперативная траектория x̂∗ (t) (сплошная линия) в
игре с динамическим обновлением информации и соответствующие
кооперативные траектории в усеченных подыграх (пунктирные линии).
На рисунках 2.9., 2.10. можно наблюдать, что дележ соответствующий комˆ ∗ (t), T − t) (пунктирная линия) принадлежит
бинированному решению ξ(x̂
Ĉ(x̂∗ (t), T − t) (выделенная область) для всех t ∈ [t0 , T ]. Это показывает
свойство сильной δt-динамической устойчивости Ĉ(x̂∗ (t), T − t), т.к. дележ
ˆ ∗ (t), T − t) был построен путем отклонения игроков от пропорционального
ξ(x̂
∗
ˆ
решения P rop(x̂
(t), T − t) (сплошная линия) в момент времени tbr = t0 + j∆t
ˆ ∗ (tbr ), T − tbr ).
в пользу вектора Шепли Sh(x̂
47
Рисунок 1.8. ПРД β̂ P rop (t, x̂∗ ) для пропорционального решения (сплошная
линия), ПРД β̂(t, x̂∗ ) для комбинированного решения (6.7) (пунктирная
линия).
Рисунок 1.9. Оси: ξ1 , ξ3 , t. ξ2 можно вычислить используя нормировочное
условие.
48
Рисунок 1.10. Оси: ξ1 , ξ2 , ξ3 . Добавлена виртуальная ось t для отображения
изменения множества Ĉ(x∗ (t), T − t) во времени.
49
ГЛАВА 2
КООПЕРАТИВНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ ИГРЫ С
ПРЕДПИСАННОЙ ПРОДОЛЖИТЕЛЬНОСТЬЮ И СО
СЛУЧАЙНЫМ ОБНОВЛЕНИЕМ ИНФОРМАЦИИ
§ 1.
Определение случайной усеченной подыгры
Рассмотрим кооперативную дифференциальную игру Γ(x0 , T − t0 ) определенную в первой главе. Предположим, что информация об игре обновляется в
моменты времени t = t0 + j∆t, j = 0, . . . , l, здесь l =
T
∆t
− 1, t0 < ∆t < T
задает время между моментами обновления информации. В эти моменты игроки получают точную информацию об уравнениях движений и функции выигрыша на временном интервале [t0 + j∆t, T j ]. Однако, игроки точно не знают
длительность этого интервала, т.к. T j является случайной величиной, но ее
распределение известно. В течение первого временного интервала [t0 , t0 + ∆t]
игроки имеют точную информацию о структуре игры на интервале [t0 , T 0 ], где
T 0 - случайная величина, которая принимает значения из [t0 + ∆t, T ]. В момент
времени t = t0 + ∆t информация об игре обновляется и на втором интервале
(t0 + ∆t,t0 + 2∆t], игроки имеют точную информацию о структуре игры на интервале (t0 + ∆t, T 1 ], где T 1 - случайная величина, которая принимает значения
из [max(t0 +2∆t, T 0 ), T ]. Чтобы смоделировать такой процесс введем следующее
определение. Обозначим xj,0 = x(t0 + j∆t).
Определение 4.1.1. Пусть j = 0, . . . , l. Случайная усеченная подыгра
Γ̂j (xj,0 , t0 + j∆t) определена на интервале [t0 + j∆t, T j ], где T j - случайная
величина, которая принимает значения из [max(t0 + (j + 1)∆t, T j−1 ), T ], T j−1
- реализация случайного информационного горизонта в случайной усеченной
подыгре Γ̂j−1 (xj−1,0 , t0 + (j − 1)∆t). Уравнения движения и функция выигрыша в случайной усеченной подыгре и исходной игре Γ(x0 , T − t0 ) на временном
50
интервале [t0 + j∆t, T j ] совпадают:
ẋ = f (x, u1 , . . . , un ),
x(t0 + j∆t) = xj,0 .
Функция выигрыша игрока i ∈ N имеет следующий вид:
t
T
∫
∫
j
Ki (xj,0 , t0 + j∆t; u) =
hi (x(τ ), u(τ ))dτ dFj (t),
t0 +j∆t
(1.1)
t0 +j∆t
где Fj (t) - это функция распределения случайной величины T j :
∫T
∫T
t0 +j∆t
Предположим,
что
(1.2)
dFj (t) = 1.
dFj (t) =
max(t0 +(j+1)∆t,T j−1 )
реализация
случайной
величины
T j−1
в
игре
Γ̂j−1 (xj−1,0 , t0 + (j − 1)∆t) превышает время t = t0 + (j + 1)∆t:
T j−1 > t0 + (j + 1)∆t,
тогда значение случайного информационного горизонта T j должно превышать
реализацию T j−1 , т.к. информация об игре уже известна на временном интервале [t0 +(j−1)∆t, T j−1 ]. Поэтому в формуле (1.2) вероятность того, что случайная
величина T j примет значение из интервала [t0 + j∆t, T j−1 ], равна нулю:
max(t0 +(j+1)∆t,T
j−1 )
∫
dFj (t) = 0.
t0 +j∆t
В большинстве статей, посвященных изучению кооперативных дифференциальных игр со случайной продолжительностью [44], [45], [16], функция распределения случайной величины T j определяется на бесконечном временном
интервале. В данной постановке T j принимает значения на конечном временном интервале, т.к. исходная игра определена на конечном интервале [t0 , T ].
В соответствии с [10] формула для выигрыша игрока i ∈ N (1.1) для каждой
случайной усеченной подыгры Γ̂j (xj,0 , t0 + j∆t) может быть записана в следу-
51
ющем виде:
∫T
Kij (xj,0 , t0 + j∆t; u) =
t0 +j∆t
∫t
hi (x(τ ), u(τ ))dτ dFj (t) =
t0 +j∆t
∫T
(1 − Fj (τ ))hi (x(τ ), u(τ ))dτ,
=
(1.3)
t0 +j∆t
где Fj (t) = 0 для t ∈ [t0 + j∆t, max(t0 + (j + 1)∆t, T j−1 )).
§ 2.
Решение
кооперативной
случайной
усеченной
подыгры
Рассмотрим усеченную случайную кооперативную подыгру Γ̂j (xj,0 , t0 + j∆t)
на временном интервале [t0 + j∆t, T j ] с начальным условием x(t0 + j∆t) = xj,0 .
В кооперативной постановке игрокам необходимо максимизировать суммарный
выигрыш
n
∑
Kij (xj,0 , t0
i=1
+ j∆t; uj ) =
∫T
n
∑
(1 − Fj (τ ))hi (x(τ ), u(τ ))dτ
(2.1)
x(t0 + j∆t) = xj,0 .
(2.2)
i=1 t +j∆t
0
при условии
ẋ = f (x, u1 , . . . , un ),
Это задача оптимального управления. Необходимые условия для ее решения
и соответствующие управления могут быть определены с помощью уравнения
Гамильтона-Якоби-Беллмана [45]. Обозначим максимальное значение суммарного выигрыша игроков (2.1) через W (j∆t) (t, x):
{
}
∑ j
j
W (j∆t) (t, x) = max
K
(x,
t;
u
) ,
i
j
u
i∈N
где x, t - начальная позиция и время начала подыгры усеченной игры Γ̂j (x, t).
Теорема 4.2.1. Предположим, что существует непрерывно дифференцируемая функция W (j∆t) (t, x) : [t0 + j∆t, T j ] × Rm → R, удовлетворяющая сле-
52
дующей системе уравнений в частных производных
fj (t)
(j∆t)
W (j∆t) (t, x) = Wt
(t, x)+
1 − Fj (t)
}
{ n
∑
+ max
hi (x, u) + Wx(j∆t) (t, x)f (x, u1 , . . . , un ) (2.3)
u
i=1
при условии
lim W (j∆t) (t, x) = 0,
t→T
где fj (t) - функция плотности для случайной величины T j (1.2). Предположим, что максимум в (2.3) достигается при u = u∗j (t). Тогда u = u∗j (t)
является оптимальным в задаче управления, определяемой (2.1), (2.2).
Траекторию, соответствующую u = u∗j (t), будем называть кооперативной и
обозначать через x∗j (t). Условно кооперативную траекторию {x̂∗ (t)}Tt=t0 во всей
игре Γ(x0 , T − t0 ) определим так же, как и в главе 2:
{x̂∗ (t)}lt=t0 = x∗j (t),
t ∈ (t0 + j∆t, t0 + (j + 1)∆t],
где j = 0, . . . , l и t0 + (l + 1)∆t = T . Введем следующие обозначения: x∗j,0 =
x∗j−1 (t0 + j∆t) = x∗j (t0 + j∆t).
Кооперативная случайная усеченная подыгра. Перейдем к рассмотрению кооперативной дифференциальной игры Γ̂jv (x∗j,0 , t0 + j∆t) и семейства
подыгр Γ̂jv (x∗j (t), t) вдоль кооперативной траектории x∗j (t), ∀t ∈ [t0 , T ] в форме характеристической функции. Для каждой коалиции S ⊂ N и усеченной подыгры с номером j = 0, . . . , l определим значения характеристической
функции Vj (S; x∗j (t), t) так, как это сделано в главе 2 и [39]. В этом подходе предполагается, что фиксируется некоторая ситуация равновесия по Нэшу
E
E
NE
uN
= (uN
/ S, используj
1,j , . . . , un,j ), игроки k, не входящие в коалицию k ∈
E
ют равновесные по Нэшу стратегии {uN
k,j }, тогда как игроки из коалиции S
максимизирует свой суммарный выигрыш.
Определим дележ ξj (x∗j (t), t) для каждой кооперативной случайной усеченной подыгры Γ̂jv (x∗j (t), t). Обозначим множество всевозможных дележей для усеченной подыгры Γ̂jv (x∗j (t), t) через Ej (x∗j (t), t).
53
§ 3.
Концепция решения в исходной игре со случайным обновлением информации
В качестве принципа оптимальности
Wj (x∗j (t), t) ⊂ Ej (x∗j (t), t).
В каждой случайной усеченной подыгре Γ̂jv (x∗j (t), t) будем использовать аналог
сильно динамически устойчивое ПРД-ядро C j (x∗j (t), t) определенного в главе 1
для случая игры с предписанной продолжительностью [23]. Переформулируем
это решение для случая игр со случайной продолжительностью, но сначала
введем понятие ПРД для игр со случайной продолжительностью.
Определение 4.3.1. Функция βj (t, x∗j ), t ∈ [t0 + j∆t, T j ] называется процедурой распределения дележа ξj (x∗j,0 , t0 + j∆t) ∈ Ej (x∗j,0 , t0 + j∆t), если выполняется
ξj (x∗j,0 , t0
∫
T
+ j∆t) =
(1 − Fj (τ ))βj (t, x∗j (t))dτ.
t0 +j∆t
Предположим, что функция Vj (S; x∗j (t), t) является непрерывно дифференцируемой по t, t ∈ [t0 +j∆t, T ]. Далее определим следующее множество векторов
Bj (t, x∗j ):
Bj (t, x∗j )
{
= βj (t) = (β1j (t), . . . , βnj (t)) :
]
d [
−
Vj (S; x∗j (t), t) − Vj (N \ S; x∗j (t), t) ≥
dt
∑
]
d [
≥
(1 − Fj (t))βij (t, x∗j (t)) ≥ −
Vj (S; x∗j (t), t) ,
dt
i∈S
}
∑
]
d [
j
∗
∗
Vj (N ; xj (t), t) , ∀S ⊂ N (. 3.1)
(1 − Fj (t))βi (t, xj (t)) = −
dt
i∈N
Предположим, что Bj (t, x∗j ) ̸= ∅, j = 0, . . . , l. Тогда с помощью множества Bj (t, x∗j ) можно определить следующее множество векторов C j (x∗j (t), t)
(??), ПРД βj (t, x∗j (t)) каждого из которых принадлежит множеству Bj (t, x∗j ).
В условиях постановки игры в главы 1 и в [23] было показано, что это множество является подмножеством C-ядра, это означает, что каждый элемент
54
ξj (x∗j (t), t) ∈ C j (x∗j (t), t) этого множества является дележом. Также было доказано свойство сильной динамической устойчивости этого принципа оптимальности.
Перейдем к определению решения в игре Γ(x0 , T − t0 ) со случайным обновлением информации. Для того, чтобы построить такое решение будем использовать семейство множеств Bj (t, x∗j ), j = 0, . . . , l. Сначала мы построим
результирующее множество ПРД для всей игры Γ(x0 , T − t0 ) следующим образом: для каждого набора βj (t, x∗j ) ∈ Bj (t, x∗j ), j = 0, . . . , l мы определяем
функцию β̂(t, x̂∗ ), которая будет использоваться в результирующем ПРД для
всей игры (также, как это было сделано в главе 2):
β̂(t, x̂∗ ) = (1 − Fj (t))βj (t, x∗j ),
t ∈ [t0 + j∆t, (j + 1)∆t],
(3.2)
где βj (t, x∗j ) ∈ Bj (t, x∗j ), j = 0, . . . , l. Множество всевозможных функций β̂(t, x̂∗ )
(3.2) для разных βj (t, x∗j ) ∈ Bj (t, x∗j ), j = 0, . . . , l мы обозначим через B̂(t, x̂∗ ).
Функция β̂(t, x̂∗ ) ∈ B̂(t) определяет следующий результирующий вектор
ˆ ∗ (t), T − t). Пусть t ∈ [t0 + j∆t, t0 + (j + 1)∆t], тогда положим:
ξ(x̂
t0 +(m+1)∆t
∫T
∫
l
∑
∗
∗
ˆ
ξ(x̂ (t), T −t) = β̂(τ, x̂ (τ ))dτ =
(1 − Fm (t))βm (τ, x∗m (τ ))dτ +
t
m=j+1
+
t0 +m∆t
t0 +(j+1)∆t
∫
(1 − Fj (t))βj (τ, x∗j (τ ))dτ (3.3)
t
для j = 0, . . . , l. Обозначим через Ŵ (x0 , T − t0 ) множество всех векторов
ˆ 0 , T − t0 ), построенных на основе (3.2), (3.3). В игре Γ(x0 , T − t0 ) со слуξ(x
чайным обновлением информации будем использовать Ŵ (x0 , T − t0 ) в качестве
решения и будем называет его результирующим решением.
Результирующее решение Ŵ (x0 , T − t0 ) является динамически устойчивым
по построению. Оказывается, что Ŵ (x0 , T − t0 ) обладает также свойством сильной динамической устойчивости.
Теорема 4.3.1. Пусть Ŵ (x̂∗ (t), T − t) ̸= ∅, тогда результирующее решение Ŵ (x0 , T −t0 ) является сильно динамически устойчивым в игре Γ(x0 , T −t0 )
55
со случайным обновлением информации.
Доказательство. Предположим, что в игре Γ(x0 , T − t0 ) со случайным
обновлением информации игроки согласились выбрать результирующий векˆ 0 , T − t0 ) ∈ Ŵ (x0 , T − t0 ). Это означает, что в течение игры, в кажтор ξ(x
дой кооперативной случайной усеченной подыгре Γ̂jv (x∗j,0 , t0 + j∆t) они будут
выбирать дележ ξj (x∗j,0 , t0 + j∆t) ∈ C j (x∗j,0 , t0 + j∆t) с соответствующим ПРД
βj (t, x∗j ) ∈ Bj (t, x∗j ), t ∈ [t0 +j∆t, T ]. Таким образом, в каждой усеченной подыгре игроки будут использовать ПРД β̂(t, x̂∗ ) = βj (t, x∗j ) и распределять выигрыш
между собой следующим образом:
∫T
∗
β̂(τ, x̂ (τ ))dτ =
l ∫
∑
j=0
t0
t0 +(j+1)∆t
(1 − Fj (t))βj (t, x∗j )dt,
t0 +j∆t
где t ∈ [t0 + j∆t, t0 + (j + 1)∆t], β̂(t, x̂∗ ) ∈ B̂(t, x̂∗ ).
Предположим, что в момент времени t = tbr , где tbr ∈ [t0 + k∆t, T ],
k = 0, . . . , l в случайной усеченной подыгре Γ̂kv (x∗k,0 , t0 + k∆t) игроки решили
′
выбрать другой дележ ξk (x∗k (tbr ), tbr ) из сильно динамически устойчивого ПРДядра C k (x∗k (tbr ), tbr ). Тогда существует ПРД βk′ (t, x∗k ) ∈ Bk (t, x∗k ), t ∈ [tbr , T ],
которое соответствует этому дележу, т.е.:
′
ξk (x∗k (tbr ), tbr ) =
∫T
(1 − Fk (t))βk′ (t, x∗k )dt.
tbr
В этом случае, суммарный выигрыш во всей игре будет распределен в соответствии с результирующим вектором ξˆ′ (x0 , T −t0 ), результирующее ПРД которого
будет иметь вид:
∗
(1 − Fk (t))βk (t, xk ), t ∈ [t0 + k∆t, tbr ),
β̂ ′ (t, x̂∗ ) =
(1 − Fk (t))βk′ (t, x∗k ), t ∈ [tbr , t0 + (k + 1)∆t],
(1 − F (t))β (t, x∗ ), t ∈ [t + j∆t, t + (j + 1)∆t],
j
j
0
0
j
(3.4)
где (1 − Fj (t))βj (t, x∗j ), j ̸= k, j = 0, . . . , l определяет распределение суммарного выигрыша между игроками во всех кооперативных случайных подыграх,
кроме Γ̂kv (x∗k,0 , t0 + k∆t), т.е. там где произошел пересмотр решения. Вектор
56
ξˆ′ (x0 , T − t0 ) соответствующий результирующему ПРД β̂ ′ (t, x̂∗ ) будет рассчитываться следующим образом:
ξˆ′ (x0 , T − t0 ) =
[∫
∫T
t0
tbr
+
t0 +k∆t
β̂ ′ (t, x̂∗ )dt =
[∫
l
∑
j=0
j̸=k
(1 − Fk (t))βk (t, x∗k )dt +
t0 +(j+1)∆t
]
(1 − Fj (t))βj (t, x∗j )dt +
t0 +j∆t
∫
t0 +(k+1)∆t
]
(1 − Fk (t))βk′ (t, x∗k )dt . (3.5)
tbr
Так как βk′ (t, x∗k ) ∈ Bk (t, x∗k ), t ∈ [tbr , T ], то результирующее ПРД β̂ ′ (t, x̂∗ ) (3.4)
также принадлежит множеству B̂(t, x̂∗ ). Множество всех результирующих векˆ 0 , T − t0 ), соответствующих элементам β̂(t, x̂∗ ) множества B̂(t, x̂∗ )
торов ξ(x
∫T
ˆ 0 , T − t0 ) =
ξ(x
β̂(t, x̂∗ )dt
t0
является результирующим решением Ŵ (x0 , T − t0 ) по определению. В (3.5)
был построен результирующий вектор ξˆ′ (x0 , T − t0 ) с результирующим ПРД
β̂ ′ (t, x̂∗ ) из множества B̂(t, x̂∗ ) и было показано, что результирующий вектор
ξˆ′ (xt , T − t0 ) принадлежит результирующему решению Ŵ (x0 , T − t0 ), которое
0
было выбрано с самого начала. Теорема доказана.
§ 4.
Кооперативная игра добычи ограниченного ресурса со случайным обновлением информации
Рассмотрим игру добычи ограниченного ресурса трех лиц аналогичную рассмотренной в главе 2, но со случайным обновлением информации. В качестве
принципа оптимальности будем использовать сильно динамически устойчивое
ПРД-ядро. Характеристическая функция рассчитывается также, как это сделано в [39]. В последней части примера показано свойство сильной динамической
устойчивости результирующего решения. Вид уравнений движения и функции
выигрыша для исходной игры аналогичен описанному в главе 2. Перейдем к
описанию случайной усеченной подыгры.
57
Случайная усеченная подыгра. Исходная игра Γ(x0 , T − t0 ) определена на временном интервале [t0 , T ]. Предположим, что в любой момент времени
t ∈ [t0 +j∆t, t0 +(j+1)∆t], j = 0, . . . , l, игроки имеют усеченную информацию об
игре. Она включает в себя информацию об уравнениях движения и функциях
выигрыша на временном интервале [t0 + j∆t, T j ], где T j - это экспоненциальная случайная величина распределенная на усеченном временном интервале
[max(t0 + (j + 1)∆t, T j−1 ), T ] с функцией распределения Fj (t) и функцией плотности fj (t):
)
(
1 − exp − λ(t − max(t0 + (j + 1)∆t, T j−1 ))
(
),
Fj (t) =
1 − exp − λ(T − max(t0 + (j + 1)∆t, T j−1 ))
)
λ exp − λ(t − max(t0 + (j + 1)∆t, T j−1 ))
(
).
fj (t) =
1 − exp − λ(T − max(t0 + (j + 1)∆t, T j−1 ))
(4.1)
(
(4.2)
Обозначим через Λj (t):
fj (t) , t ∈ [max(t + (j + 1)∆t, T ), T ],
0
j−1
1−Fj (t)
Λj (t) =
0,
t ∈ [t0 + j∆t, max(t0 + (j + 1)∆t, T j−1 )].
Очевидно, что
∫T
∫T
dFj (t) =
t0 +j∆t
dFj (t) = 1.
max(t0 +(j+1)∆t,T j−1 )
Построим соответствующую случайную усеченную подыгру Γ̂j (xj,0 , t0 +j∆t).
Уравнения движения и начальные условия для этой игры имеют следующий
вид:
3
∑
√
ui ,
ẋ = a x(t) − bx(t) −
x(t0 + j∆t) = xj,0 .
i=1
В соответствии с (1.3) функция выигрыша игрока i ∈ N может представлена в
виде:
∫T
Kij (xj,0 , t0 + j∆t; u) =
(1 − Fj (τ ))hi (x(τ ), u(τ ))dτ.
t0 +j∆t
58
Рассмотрим случай, когда игроки соглашаются на кооперацию в случайной
усеченной подыгре Γ̂j (xj,0 , t0 + j∆t). Тогда игроки будут действовать исходя из
максимизации их суммарного выигрыша.
Кооперативная траектория. Максимальный суммарный выигрыш в
каждой случайной усеченной подыгре Γ̂j (xj,0 , t0 + j∆t) имеет следующий вид
[48]:
√
W j (t, x) = Aj (t) x + C j (t),
(4.3)
где функции Aj (t), C j (t) удовлетворяют системе дифференциальных уравнений:
[
]
3
∑
b
[ 1
] ,
Ȧj (t) = Λj (t) +
Aj (t) −
Aj (t)
2
4 ci + 2
i=1
a
Ċ j (t) = Λj (t)C j (t) − Aj (t),
2
j
j
lim A (t) = 0, lim C (t) = 0,
t→T
t→T
где Λj (t) определено в (4.3).
Кооперативная траектория x∗j (t) в случайной усеченной подыгре Γ̂j (xj,0 , t0 +
j∆t) может быть вычислена на временном интервале следующим образом [48]:
2
t
∫
√
1
∗
2
xj (t) = ϖj (t0 + j∆t, t) x∗j,0 + a ·
ϖj (t0 + j∆t, τ )−1 dτ ,
2
t0 +j∆t
где t ∈ [t0 + j∆t, T j ], T j - это случайная величина распределенная по закону
Fj (t) (4.1):
∫t
ϖj (t0 + j∆t, t) = exp
t0 +j∆t
∑
1
1
− b +
[
]
2 dτ.
2
Aj (τ )
i=1
4 ci + 2
3
Начальное положение для кооперативной траектории в каждой усеченной
подыгре устанавливается из предыдущей усеченной подыгры: x∗0,0 = x0 и
x∗j,0 = x∗j−1 (t0 + j∆t) для 1 ≤ j ≤ l. Определим условно кооперативную траекторию x̂∗ (t) в игре Γ(x0 , T − t0 ) со случайным обновлением информации:
x̂∗j (t) = x∗j (t),
t ∈ [t0 + j∆t, t0 + (j + 1)∆t],
j = 0, . . . , l.
59
Характеристическая функция. Характеристическую функцию будем
рассчитывать также, как это было сделано в главе 2. Отличие заключается в
том, что все расчеты происходят для игры со случайной продолжительностью.
Рассчитаем Vj (S; xj,0 , t0 + j∆t) (Vj (S; x∗j (t), t)) для каждой коалиции S ⊂ N .
В соответствии с формулой в главе 2 (2.7) максимальный суммарный выигрыш игроков Wj (t0 +j∆t, xj,0 ) (4.3) соответствует значению характеристической
функции Vj (N ; xj,0 , t0 + j∆t) коалиции S = N в случайной усеченной подыгре
Γ̂jv (xj,0 , t0 + j∆t):
Vj (N ; x∗j (t), t) = Wj (t, x∗j (t)),
t ∈ [t0 + j∆t, T j ],
j = 0, . . . , l.
Далее нам необходимо определить значения характеристической функции для
следующих коалиций:
{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}.
Для каждой коалиции вида {i}, i = 1, 3 нам необходимо определить равновесие
по Нэшу в усеченной подыгре Γ̂j (xj,0 , t0 + j∆t) и как результат Vj ({i}; x∗j (t), t).
Коалиции, состоящие из одного игрока. Равновесие по Нэшу в случайной усеченной подыгре Γ̂j (xj,0 , t0 +j∆t) определяется следующими стратегиями
игроков:
uji (t, x) =
x
4[ci + Aji (t)/2]2
,
i = 1, 3,
где функции Aji (t) находятся из системы дифференциальных уравнений:
1
b ∑
1
−
,
Ȧji (t) = Aji (t) Λj (t) + +
j
2
8(ck + Ak (t)/2)2
4(ci + Aji (t)/2)
k̸=i
a
Ċij (t) = Λj (t)Cij (t) − Aji (t),
2
j
j
lim Ai (T ) = 0, lim Ci (T ) = 0, i = 1, 3,
t→T
t→T
где Λj (t) определено в (4.3).
Выигрыш игрока i = 1, 3 в ситуации равновесия по Нэшу определяется
функцией:
√
Vij (t, x) = Aji (t) x + Cij (t),
i = 1, 3.
60
Таким образом, значение характеристической функции для коалиций, состоящих из одного игрока S = {i}, i ∈ N , вычисляется следующим образом:
Vj ({i}; x∗j (t), t) = Vij (t, x∗j (t)),
t ∈ [t0 + j∆t, T ],
j = 0, . . . , l.
Коалиции, состоящие из двух игроков. Значение характеристической
функции для коалиций, состоящих из двух игроков, рассчитывается аналогично
тому, как это делается в главе 2. Рассмотрим формулы для Vj (S; xj,0 , t0 + j∆t)
(Vj (S; x∗j (t), t)) в случае, когда S = {1, 2}, формулы для вычисления остальных коалиций можно получить по такому же принципу. Значения выигрышей
игроков в ситуации равновесия по Нэшу имеют следующий вид:
√
j
j
(t, x) = Aj{1,2} (t) x + C{1,2}
(t),
V{1,2}
√
V3j (t, x) = Aj3 (t) x + C3j (t),
j
где функции Aj{1,2} (t), Aj3 (t), C{1,2}
(t), C3j (t) удовлетворяют системе дифферен-
циальных уравнений:
[
]
Ȧj{1,2} (t) = Aj{1,2} (t) Λj (t) +
−
∑
b
1
+
−
2 8(c3 + Aj3 (t)/2)2
1
,
j
4(c
+
A
(t)/2)
k
{1,2}
k∈S
[
]
∑
b
1
Ȧj3 (t) = Aj3 (t) Λj (t) + +
−
2
8(ck + Aj{1,2} (t)/2)2
k∈S
−
1
4(c3 + Aj3 (t)/2)
,
a
a
j
j
Ċ{1,2}
(t) = Λj (t)C{1,2}
(t) − Aj{1,2} (t), Ċ3j (t) = Λj (t)C3j (t) − Aj3 (t),
2
2
j
j
j
j
lim A{1,2} (t) = lim A3 (t) = lim C{1,2} (t) = lim C3 (t) = 0,
t→T
t→T
t→T
t→T
где слагаемое Λj (t) определено в (4.3). Таким образом, значение характеристической функции коалиции S = {1, 2} вычисляется следующим образом:
j
Vj ({1, 2}; x∗j (t), t) = V{1,2}
(t, x∗j (t)),
t ∈ [t0 + j∆t, T ],
j = 0, . . . , l.
Концепция решения. Пусть игроки в каждой кооперативной случайной
усеченной подыгре Γ̂jv (xj,0 , t0 + j∆t) используют в качестве принципа оптимальности сильно динамически устойчивое ПРД-ядро C j (x∗j (t), t) (C j (x0 , t0 )).
61
Это означает, что игроки в каждой случайной усеченной подыгре выбирают
ПРД βj (t, x∗j ) из множества Bj (t, x∗j ) (3.1), j = 0, . . . , l. Далее строится соответствующее результирующее ПРД β̂(t, x̂∗ ) (3.2) и множество B̂(t, x̂∗ ). С поˆ ∗ (t), T − t),
мощью формулы (3.3) рассчитывается результирующий вектор ξ(x̂
множество всевозможных таких векторов образует результирующее решение
Ŵ (x̂∗ (t), T − t).
Далее на примере конкретных результирующих векторов из Ŵ (x̂∗ (t), T − t)
покажем, что построенное решение является сильно динамически устойчивым
в игре Γ(x0 , T − t0 ) со случайным обновлением информации. Отличием этого
раздела от подобного в главе 2 является то, что в главе 2 в качестве принципа
оптимальности использовалось C-ядро, а значит исследовалось свойство сильной ∆t-динамической устойчивости. Это означает, что исследовалось отклонение от выбранного решения (дележа) только в моменты времени t = t0 + j∆t,
j = 0, . . . , l. В этом разделе в качестве принципа оптимальности используется
сильно динамически устойчивое ПРД-ядро, поэтому интерес представляет исследование свойства сильной динамической устойчивости. Т.е. будет исследовано отклонение от выбранного решения для любого момента времени t ∈ [t0 , T ].
Численный пример. Рассмотрим численный пример игры заданной на
временном интервале длинной T − t0 = 4, в котором на интервалах времени
[t0 + j∆t, t0 + (j + 1)∆t] информация об игре известна на интервале длинной
T j , где T j - это случайная величина (4.1) с λ = 0.5. Информация об игре обновляется с периодом ∆t = 1. Зафиксируем следующие параметры для уравнений
движений a = 10, b = 0.5, для функции выигрыша c1 = 0.15, c2 = 0.65, c3 = 0.45
и для начальных условий t0 = 0, x0 = 200.
Во время обновления информации об игре происходит реализация случайного временного горизонта для текущей усеченной подыгры:
T 0 = 2.423,
T 1 = 3.538,
T 2 = 3.871,
T 3 = 4.
Сгенерированное значение информационного горизонта в текущей усеченной
подыгре влияет на распределение продолжительности следующей усеченной
подыгры.
62
На графике 4.1. отображены плотности распределения. Видно, каким образом происходила генерация T j , и как менялась плотность распределения fj (t)
(4.2) информационного горизонта.
Рисунок 2.1. Плотность распределения fj (t) информационного горизонта,
j = 0, 1, 2 (4.2) для каждой случайной усеченной подыгры.
На графике 4.2. изображены оптимальные стратегии (стратегии соответствующие кооперативной траектории) для первого игрока, рассчитанные в игре
со случайным обновлением информации (сплошная линия) и в исходной игре
трех лиц [48] (пунктирная линия).
На графике 4.3. представлено следующее сравнение: условно кооперативная
траектория x̂∗ (t) (толстая сплошная линия) в игре со случайным обновлением
информации, условно кооперативная траектория x̄∗ (t) (тонкая пунктирная линия) в игре с динамическим обновлением информации, описанной в главе 2 и
в [40] (где значение временного горизонта T = 2), и кооперативная траектория
x∗ (t) (пунктирная линия) в исходной игре трех лиц. На следующем графике 4.4.
отображена условно кооперативная траектория x̂∗ (t) (сплошная линия) в игре
со случайным обновлением информации и траектории, которые были частью
кооперативных траекторий в каждой из случайных усеченных подыграх, но не
являются оптимальными во всей игре (пунктирные линии).
Далее для того, чтобы распределить суммарный выигрыш между игроками
63
Рисунок 2.2. Оптимальные стратегии игрока 1 в игре со случайным
обновлением информации (сплошная линия) и в исходной игре трех лиц [48]
(пунктирная линия).
необходимо рассчитать значения характеристической функции Vj (S; x∗j (t), t),
S ⊂ N для каждой случайной усеченной подыгры Γ̂jv (x∗j,0 , t0 + j∆t). Используя
Vj (S; x∗j (t), t), построим множество ПРД Bj (t, x∗j ), j = 0, . . . , l (3.1) для каждой
случайной усеченной подыгры и результирующее множество ПРД B̂(t, x̂∗ ).
Продемонстрируем свойство сильной динамической устойчивости результирующего решения Ŵ (x0 , T − t0 ). Предположим, что в начале игры Γ(x0 , T − t0 )
∗
ˆ
игроки договорились использовать пропорциональное решение P rop(x̂
(t), T −
∗
ˆ
t) (5.1) (далее покажем, что при заданных параметрах P rop(x̂
(t), T − t) ∈
Ŵ (x̂∗ (t), T − t)). Теперь предположим, что в некоторый момент времени tbr ∈
[t0 , T ] (пусть tbr ̸= t0 + j∆t, j = 0, . . . , l) игроки решили, что пропорциональное
решение больше их не устраивает, и выбрали другой вектор из результируюˆ ∗ (tbr ), T − tbr ),
щего решения Ŵ (x̂∗ (tbr ), T − tbr ), например, вектор Шепли Sh(x̂
t ∈ [tbr , T ] (5.2). Рассчитаем результирующее ПРД для пропорционального решения и вектора Шепли. Пусть tbr = 1.2, тогда ПРД для результирующего комбинированного решения (3.2) имеет следующий вид:
β̂ P rop (t, x̂∗ ), t ∈ [t0 , tbr ],
∗
β̂(t, x̂ ) =
β̂ Sh (t, x̂∗ ), t ∈ (t , T ].
br
(4.4)
64
Рисунок 2.3. Траектория запасов ресурсов x̂∗ (t) (толстая сплошная линия) в
игре со случайным обновлением информации, траектория x̄∗ (t) (тонкая
сплошная линия) в игре с динамическим обновлением информации, и
кооперативная траектория x∗ (t) в исходной игре трех лиц (тонкая пунктирная
линия).
На графике 4.5. изображены результирующее ПРД пропорционального решения, который выбрали игроки в начале игры β̂ P rop (t, x̂∗ ) (глава 1, (??)) (сплошная линия) и результирующее ПРД β̂(t, x̂∗ ) для комбинированного решения (4.4)
(пунктирная линия).
Проинтегрируем комбинированное решение β̂(t, x̂∗ ) (4.4) по t (3.3) и получим
ˆ ∗ (t), T − t).
соответствующий результирующий вектор, обозначим его через ξ(x̂
ˆ ∗ (t), T − t) игроки разделят суммарный выигрыш в
В соответствии с ним ξ(x̂
игре Γ(x0 , T − t0 ) со случайным обновлением информации следующим образом:
ˆ ∗ (t), T − t) = (12.3, 30.2, 16.8).
ξ(x̂
На рисунках 4.6., 4.7. можно наблюдать, что результирующее ПРД β̂(t, x̂∗ )
(4.4) (пунктирная линия) принадлежит B̂(t, x̂∗ ) (выделенная область) для всех
t ∈ [t0 , T ]. Это показывает свойство сильной динамической устойчивости
Ŵ (x̂∗ (t), T − t).
На графике 4.8. видна разница между результирующим вектором
∗
ˆ
P rop(x̂
(t), T − t) для пропорционального решения (сплошная линия) и резуль-
65
Рисунок 2.4. Траектория запасов ресурсов x̂∗ (t) (толстая сплошная линия) в
игре со случайным обновлением информации и соответствующие части
кооперативных траекторий, которые были частью оптимальных траекторий в
каждой из усеченных подыграх (пунктирные линии).
ˆ ∗ (t), T −t) для комбинированного решения (пунктирная
тирующим вектором ξ(x̂
линия).
66
Рисунок 2.5. ПРД β̂ P rop (t, x̂∗ ) для пропорционального решения (сплошная
линия), ПРД β̂(t, x̂∗ ) для комбинированного решения (4.4) (прерывистая
линия).
Рисунок 2.6. Оси: β1 , β3 , t. β2 можно вычислить используя нормировочное
условие.
67
Рисунок 2.7. Оси: β1 , β3 , t. β2 можно вычислить используя нормировочное
условие.
∗
ˆ
Рисунок 2.8. Результирующий вектор P rop(x̂
(t), T − t) для
пропорционального решения (сплошная линия), результирующий вектор
ˆ ∗ (t), T − t) для комбинированного решения (пунктирная линия).
ξ(x̂
68
ЗАКЛЮЧЕНИЕ
Основными результатами, полученными в ходе исследования и выносимыми
на защиту, являются следующие:
1. Построены и исследованы новые математические модели дифференциальной игры с динамическим обновлением информации с предписанной
и бесконечной продолжительностью, дифференциальной игры со случайным обновлением информации.
2. Предложены конструктивные методы нахождения результирующего кооперативного решения в дифференциальных играх с динамическим обновлением информации с предписанной и бесконечной продолжительностью, дифференциальных играх со случайным обновлением информации.
3. Предложена процедура построения характеристической функции в играх
с динамическим обновлением информации на основе значений характеристических функций в усеченных подыграх.
4. Доказаны теоремы о сильной ∆t-динамической устойчивости в дифференциальных играх с динамическим обновлением информации с предписанной и бесконечной продолжительностью, дифференциальных играх со
случайным обновлением информации.
5. Определена связь кооперативного решения в игре с динамическим обновлением информации и кооперативных решений (пропорциональное решение, вектор Шепли, C-ядро, сильно динамически устойчивое ПРД-ядро),
в каждой усеченной подыгре.
69
ЛИТЕРАТУРА
1. Воробьев Н. Н. Теория игр для экономистов-кибернетиков. ЕМ: Наука. 1985.
272 с.
2. Громова Е. В., Петросян Л. А. Сильно динамически устойчивое кооперативное решение в одной дифференциальной игре управления вредными выбросами // Управление большими системами. 2015. N 55. С. 140-159.
3. Громова Е. В., Петросян Л. А. Об одном способе построения характеристической функции в кооперативных дифференциальных играх // Математическая теория игр и ее приложения. 2015. N 7. С. 19-39.
4. Данилов Н. Н. Кооперативные многошаговые игры с побочными платежами
// Изв. Вузов. Мат. 1991. N 2. С. 33-42.
5. Клейменов А. Ф. К кооперативной теории бескоалиционных позиционных
игр // Докл. АН СССР. 1990. Т. 312. N 1. С. 32-35.
6. Клейменов А. Ф. Кооперативные решения в позиционной дифференциальной игре многих лиц с непрерывными функциями платежей // Прикл. математика и механика. 1990. Т. 54. Вып. 3. С. 389-394.
7. Клейменов А. Ф. Неантагонистические позиционные дифференциальные игры. Екатеринбург: Наука. УРО. 1993. 185 с.
8. Клейменов А. Ф. О решениях в неантагонистической позиционной дифференциальной игре // Прикл. математика и механика. 1997. Т. 61. Вып. 5. С.
739-746.
9. Кононенко А. Ф. О равновесных позиционных стратегиях в неантагонистических дифференциальных играх // Доклады АН СССР. 1976. Т. 231. N 2.
С. 285-288.
10. Костюнин С. Ю., Шевкопляс Е. В. Об упрощении интегрального выигрыша
в дифференциальных играх со случайной продолжительностью // Вестн.
С.-Петерб. ун-та Сер.10: Прикладная математика, информатика, процессы
управления. 2011. N 4. С. 47-56.
11. Красовский Н. Н. Управление динамической системой. Задача о минимуме
гарантированного результата. М.: Наука, 1985. 469 с.
70
12. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры.
М.: Наука, 1974. 456 с.
13. Нейман Д. фон, Моргенштерн О. Теория игр и экономическое поведение.
М.: Наука, 1970. 983 с.
14. Петросян Л. А. Устойчивость решений в дифференциальных играх со многими участниками // Вестн. ЛГУ. 1977. N 19. С. 46-52.
15. Петросян Л. А. Сильно динамически устойчивые дифференциальные принципы оптимальности // Вестн. ЛГУ. 1993. N 4. С. 35-40.
16. Петросян Л. А., Шевкопляс Е. В. Кооперативные дифференциальные игры
со случайной продолжительностью // Вестн. СПбГУ. 2000. Сер. 1. Вып. 4.
С. 18-23.
17. Петросян Л. А., Данилов Н. Н. Устойчивость решений неантагонистических
дифференциальных игр с трансферабельными выигрышами // Вестник Ленинградского университета. Серия 1: Математика, механика, астрономия.
1979. N 1. С. 52-59.
18. Петросян Л. А., Данилов Н. Н. Кооперативные дифференциальные игры и
их приложения. Изд-во Томского университета, 1985. 273 с.
19. Петросян Л. А., Кузютин Д. В. Игры в развернутой форме: оптимальность
и устойчивость. СПб.: Изд. СПбГУ, 2000. 292 с.
20. Петросян Л. А., Мурзов Н. В. Теоретико-игровые проблемы в механике //
Литовский математический сборник. 1966. N 3. С. 423-433.
21. Петросян Л. А., Томский Г. В. Динамические игры и их приложения. Л.:
Изд. ЛГУ, 1982. 251 с.
22. Петросян О. Л. Решение с информационной дискриминацией в кооперативных дифференциальных играх с бесконечной продолжительностью //
Вестник Санкт-Петербургского Государственного Университета. 2016. N 4.
С. 18-30.
23. Петросян О. Л., Громова Е. В., Погожев С. В. О сильно динамически устойчивом подмножестве C–ядра в кооперативных дифференциальных играх
с предписанной продолжительностью // Математическая Теория Игр и ее
Приложения. 2016. Т. 8. N 4. С. 79-106.
71
24. Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы.
Изд-во Европейского ун-та в С.-Петербурге, 2004. 460 с.
25. Понтрягин Л. С. К теории дифференциальных игр // Успехи математических наук. 1966. N 26, 4 (130). С. 219-274.
26. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф.
Математическая теория оптимальных процессов. Москва: Государственное
издательство физико-математической литературы, 1961. 392 с.
27. Седаков А. А. О сильной динамической устойчивости C-ядра // Математическая теория игр и ее приложения. 2015. N 2, С. 69-84.
28. Смирнова Е. В. Устойчивая кооперация в одной линейно-квадратичной
дифференциальной игре // Труды XLIV Международной научной конференции аспирантов и студентов «Процессы управления и устойчивость»(CPSЎ13). 2013. С. 666-672.
29. Чистяков С. В. О бескоалиционных дифференциальных играх // Доклады
АН СССР. 1981. Т. 259. N 5. С. 1052-1055.
30. Шевкопляс Е. В. Уравнение Гамильтона-Якоби-Беллмана в дифференциальных играх со случайной продолжительностью // Математическая теория игр и ее приложения. 2009. Т. 1. N 2. С. 98-118.
31. Шевкопляс Е. В. Устойчивая кооперация в дифференциальных играх со
случайной продолжительностью // Управление большими системами: сборник трудов. 2010. N 31-1. С. 162-190.
32. Bellman R. E. Dynamic Programming. Princeton: Princeton University Press.
1957. 550 p.
33. Bercovitz L. D. A variational approach to differential games // Adv. in game
theory, Ann. of Math. Studies. 1964. P. 127-175.
34. Breton M., Zaccour G., Zahaf M. A differential game of joint implementation of
environmental projects // Automatica. 2005. Vol. 41. N 10. P. 1737-1749.
35. Dockner E., Jorgensen S., van Long N., Sorger G. Differential Games in
Economics and Management Science. Cambridge: Cambridge University Press.
2001. 396 p.
72
36. Fleming W. H. The convergence problem for differential games // Adv. in game
theory, Ann. of Math. Studies. 1964. P. 175-195.
37. Gromova E. V. The Shapley value as a sustainable cooperative solution in
differential games of 3 players // In book: Recent Advances in Game Theory
and Applications, Static & Dynamic Game Theory: Foundations & Applications,
Chapter: IV, Publisher: Springer International Publishing. 2016. P. 67-89.
38. Gromova E. V., Petrosian O. L. Control of information horizon for cooperative
differential game of pollution control // 2016 International Conference Stability
and Oscillations of Nonlinear Control Systems (Pyatnitskiy’s Conference). 2016.
(DOI:10.1109/STAB.2016.7541187)
39. Petrosyan L., Zaccour G. Time-consistent Shapley value allocation of pollution
cost reduction // Journal of Economic Dynamics and Control. 2003. Vol. 27. N
3. P. 381-398.
40. Petrosian O. L. Looking Forward Approach in Cooperative Differential Games
// International Game Theory Review. 2016. Vol. 18. N 2. P. 1-14.
41. Petrosian O. L., Barabanov A.E. Looking Forward Approach in Cooperative
Differential Games with Uncertain Stochastic Dynamics // Journal of
Optimization Theory and Applications. 2017. Vol. 172. N 1. P. 328-347.
42. Shapley L. S. A Value for n-person Games // In Contributions to the Theory
of Games, volume II, by H.W. Kuhn and A.W. Tucker, editors. Annals of
Mathematical Studies. Princeton University Press. 1953. Vol. 28. P. 307-317.
43. Shapley L. S. Cores of convex games // International Journal of Game Theory.
1971. Vol. 1. N 1. P. 11-26.
44. Shevkoplyas E. V. The Shapley value in cooperative differential games with
random duration // Annals of the International Society of Dynamic Games.
2010. Vol. 11. P. 359-373.
45. Shevkoplyas E. V. The Hamilton-Jacobi-Bellman Equation for a Class of
Differential Games with Random Duration // Automation and Remote Control.
2014. Vol. 75. N 5. P. 959-970.
73
46. Yeung D.W.K. An irrational-behavior-proofness condition in cooperative
differential games // Int. J. of Game Theory Rew. 2007. Vol. 9. N 1. P. 256273.
47. Yeung D. W. K., Petrosyan L. A. Subgame-consistent Economic Optimization.
New York: Springer. 2012. 395 p.
48. Jorgensen S., Yeung D. W. K. Inter- and intergenerational renewable resource
extraction // Annals of Operations Research. 1999. Vol. 88. N 0. P. 275-289.
Отзывы:
Авторизуйтесь, чтобы оставить отзыв