Содержание к диссертации
Введение
Глава 1. Линейно-квадратичные неантагонистические дискретные игры 13
1.1 Бескоалиционные линейно-квадртичные дискретные игры 14
1.1.1 Теорема о существовании равновесия по Нэшу 15
1.1.2 Пример 18
1.2 Кооперативные линейно-квадратичные дискретные игры 21
1.2.1 Игры в форме характеристической функции 21
1.2.2 Условие устойчивости против иррационального поведения игроков 26
1.2.3 Условие устойчивости против иррационального поведения игроков в играх с неполной информацией 31
1.2.4 Пропорциональное решение 32
1.3 Решение дискретной игры с выигрышами игроков, содержащими перекрестные слагаемые 34
1.4 Пример. Планирование производства в условиях конкуренции 37
1.5 Пример. Игра с тремя участниками 41
Глава 2. Стохастические линейно-квадратичные дискретные игры со случайной продолжительностью 46
2.1 Бескоалиционные игры 49
2.2 Кооперативные игры 50
2.2.1 Игры в форме характеристической функции 50
2.2.2 ES-вектор 53
2.2.3 Динамическая устойчивость ES-вектора 54
2.2.4 Условие устойчивости ES-вектора против иррационального поведения игроков 57
2.3 Пример 58
Глава 3. Линейно-квадратичные дискретные игры с нетрансферабельными выигрышами 63
3.1 Линейно-квадратичные дискретные игры с нетрансферабельными выигрышами с предписанной продолжительностью 63
3.1.1 Теорема о существовании равновесия по Нэшу 64
3.1.2 Парето-оптимальное решение 65
3.1.3 Динамическая устойчивость Парето-оитимального решения 67
3.1.4 Условие устойчивости Парето-оитимального решения против иррационального поведения игроков 71
3.2 Линейно-квадратичные дискретные игры с нетрансферабельными выигрышами с бесконечной продолжительностью 73
3.2.1 Парето-оптимальное решение 74
3.2.2 Динамическая устойчивость Парето-оитимального решения 76
3.2.3 Условие устойчивости Парето-оитимального решения против иррационального поведения игроков 77
3.3 Пример. Игра стабилизации государственного долга 79
Глава 4. Сетевые линейно-квадратичные дискретные игры с управляющей коалицией 84
4.1 Постановка задачи 84
4.2 Некооперативная игра 86
4.3 Кооперативная игра 88
4.4 Пример 91
Заключение 96
Литература
- Теорема о существовании равновесия по Нэшу
- Игры в форме характеристической функции
- Динамическая устойчивость Парето-оитимального решения
- Некооперативная игра
Теорема о существовании равновесия по Нэшу
Систематические исследования решений линейно-квадратичных дифференциальных игр обычно связывают с выходом работы [38]. В этой работе большое внимание уделено формализму бескоалиционных линейно-квадратичных дифференциальных игр многих лиц, получены условия существования решений бескоалиционных игр в различных классах стратегий как для непрерывных, так и для дискретных моделей. Однако во многих приложениях из самой постановки задач следует необходимость объединения игроков в коалиции с целью максимизации суммарного выигрыша. Поэтому актуальным оказывается исследование кооперативных динамических игр. В данной главе рассматривается кооперативный вариант линейно-квадратичных дискретных игр с бесконечной продолжительностью.
Рассмотрим дискретную линейно-квадратичную неантагонистическую игру п лиц, состояние которой в каждый момент времени задается вектором х(к): изменяющимся согласно системе уравнений
Предполагается, что игроки выбирают только допустимые стратегии вида щ(к,х) = Mi(k)x, к ко, і = 1,...,га. Обозначим построенную выше игру Г(ко,Хо)- Это обозначение показывает, что игра началась в момент времени к = ко из состояния х(ко) = Хо 1.1 Бескоалиционные линейно-квадртичные дискретные игры
Довольно часто в реальной жизни встречаются такие конфликтные ситуации, когда кооперация или соглашение невозможны или запрещены правилами игры. Игры, описывающие подобные процессы, называют бескоалиционными. Найдем решение бескоалиционной игры Г(&о,Жо) 15
В работе Т. Башара и Г. Олсдера [39] была сформулирована теорема о нахождении равновесия по Нэшу в линейно-квадратичных дискретных играх с бесконечной продолжительностью в стационарном случае, когда матрицы А,_В , Pi Ri постоянны на протяжении всей игры. В данном параграфе приводится аналог этой теоремы для нестационарного случая. В теореме приведены необходимые и достаточные условия для существования равновесия по Нэшу в игре Г(&о,Жо). Пусть Q+(7+) С Z(7+) - множество положительных ограниченных на 7+ матриц.
Теорема 1. Для того чтобы в игре Г(&о,Жо) существовало единственное в классе допустимых равновесие по Нэшу необходимо и достаточно, чтобы си 16 стема матричных уравнений имела единственное решение {MfE(к), Qi(k)} Є Z(7+), в виде вещественных, ограниченных матриц размерности г хт итхт соответственно, где Qi(k) - симметричны для любого і Є N, для которого выполняется: 3+i с начальным условием х(ко) = Хо и функционалом Ji(ko,Xo,uNE/ui). В [27] выведены условия для существования единственного оптимального управления в задаче такого типа. Согласно [27]
Достаточность. Покажем, что доказательство достаточности следует из [27]. Действительно, при замыкании системы (1.0.1) набором допустимых управлений {uNE/щ}, она превращается в систему с одним управлением:
Рассмотрим теперь кооперативный вариант описанной игры. Будем предполагать, что условиями игры допускаются совместные действия игроков, то есть игроки могут объединяться с целью обеспечения максимального суммарного выигрыша и перераспределять его между членами коалиции. В данном параграфе рассмотрены решения, основанные на построении характеристической функции. Также исследуется вопрос динамической устойчивости полученных решений и выполнение для них устойчивости против иррационального поведения игроков.
Использование характеристической функции при построении кооперативных решений позволяет оценить возможности коалиций и вклад каждого игрока, что является основой для получения схем распределения суммарного выигрыша. Для определенной линейно-квадратичной дискретной игры Г(&о, #о) характеристическую функцию
При построении характеристической функции по указанной схеме предполагается, что игроки из коалиции S используют стратегии, которые являются наилучшим ответом на некоторое фиксированное равновесие по Нэшу в игре Г(ко,Хо)- Идея построения характеристической функции в такой форме была предложена в [58]. Заметим, что такой подход к решению кооперативных игр существенно облегчает вычислительный процесс, но построенная таким образом характеристическая функция в общем случае может не являться супераддитивной.
Игры в форме характеристической функции
В динамических играх важным свойством кооперативного решения является его динамическая устойчивость. В случае, если дележ динамически устойчив, он остается оптимальным в любой подыгре вдоль оптимальной траектории, при условии, что игроки руководствуются принципом оптимальности, выбранным в начале игры. Понятие динамической устойчивости впервые было введено Пет-росяном Л.А. в работе [14]. Но даже если дележ обладает этим свойством, игроки не застрахованы от иррационального поведения других игроков, которое может привести к распаду максимальной коалиции. Поэтому актуальным является условие устойчивости против иррационального поведения игроков, предложенное Д.В.К. Янгом в работе [66]. В данном параграфе рассматривается вопрос динамической устойчивости кооперативного решения и конкретизируется условие Янга для линейно-квадратичных дискретных игр .
Пусть набор стратегий uN = (и ,..., и ) доставляет максимум JN. Оптимальной будем называть траекторию х (к): которая реализуется при замыкании системы (1.0.1) набором стратегий uN.
Эти понятия впервые введены Петросяном Л.А. в работах [17], [16]. В определении 4 значение /?j(fto, XQ) представляет собой сумму двух слагаемых. Первое является "накопленным выигрышем" игрока і к моменту времени / + 1, если выплаты сделаны согласно ПРД /3(ft), а второе является выигрышем игрока і в подыгре Г(/+1, ж (/+1)) при условии, что при решении подыгры Г(/+1, ж (/+1)) используется тот же принцип оптимальности, что и при решении игры T(fto, XQ). Теорема 3. Пусть (рі(к,х (к) Є М(х (к)), тогда вектор-функция /3(k) =
Доказательство. Покажем сначала, что вектор /3i(k), определенный в (1.2.4), действительно является процедурой распределения дележа. Из равномерной асимптотической устойчивости системы (1.0.1) имеем: при любом I ко, где /3(к) = {(5\{к),..., (Зп(к)) состоятельная во времени ПРД, соответствующая дележу (р(ко,Хо). Интерпретировать (1.2.5) можно следующим образом: до момента / + 1 игроки образуют максимальную коалицию и используют стратегии, максимизирующие суммарный выигрыш, получают при этом "накопленные выигрыши" 2 Pi{k) согласно ПРД /3(к). В момент / + 1 происходит распад максимальной коалиции, и в подыгре Г(/ + 1, x (l + 1)) игрок і, играя индивидуально, получает выигрыш v(i,x (l + 1)). Таким образом, условие (1.2.5) гарантируют, что в случае распада максимальной коалиции в некоторый момент времени, игроки получат не меньше, чем если бы играли индивидуально изначально. выполнено для всех і = 1,..., п и при всех & &о, то дележ будет удовлетворять условию устойчивости против иррационального поведения игроков. Сформулируем полученный результат в виде утверждения.
Утверждение 1. Для того чтобы в линейно-квадратичной дискретной игре с бесконечной продолжительностью дележ: был устойчив против иррационального поведения игроков достаточно, чтобы для любого і Є N выполнялось:
Условие устойчивости против иррационального поведения игроков в играх с неполной информацией
Будем предполагать, что Г(&о,Жо) _ игра с неполной информацией, т.е. если в момент (к,х (к)) кто-то из игроков ведет себя иррационально и происходит распад максимальной коалиции, то остальные игроки узнают об этом только на шаге к + 1. Пусть Wi(k, х(к),щ(к)) = xT(k)Pi(k)x(k) + uj(к)Щ{к)щ{к).
Определение 6. Дележ, tРпікої %о)) удовлетворяет условию устойчивости против иррационального поведения игроков [66] в игре Г(ко,Хо) с неполной информацией, если неравенства і выполнены при любом I ко, где /3(к) = (/3i(k),...,/Зп(к)) состоятельная во времени ПРД, соответствующая дележу (р(ко,Хо).
Интерпретировать это условие можно следующим образом: до момента /+1 игроки образуют максимальную коалицию, используя стратегии, максимизирующие суммарный выигрыш, и получают при этом "накопленные выигрыши" 2 fii{k) согласно ПРД /3(к). В момент / + 1 происходит распад максимальной коалиции, но игроку і на шаге / +1 об этом неизвестно и он продолжает использовать управление uf, получая на этом шаге выигрыш Wi(l + 1, x (l + l),uf(l + 1)), в то время как остальные игроки могут использовать произвольный набор стратегий Uj\r\i из класса допустимых. Далее в подыгре Г(/ + 2, x(l + 2)) игрок і, играя индивидуально, гарантирует себе выигрыш min v(i,x(l + 2)), здесь
Динамическая устойчивость Парето-оитимального решения
В настоящее время одной из основных задач теории динамических и дифференциальных игр является описание процессов наиболее приближенных к реальным. Одной из проблем, возникающих при описании реальных процессов принятия решения, является вопрос возникновения неопределенности. Действительно, в жизни зачастую будущее состояние невозможно предсказать точно. Поэтому, математические модели исследуемых задач должны учитывать возможность возникновения неопределенности в различных её проявлениях. Так, актуальными является исследования конфликтно-управляемых систем с недетерминированными переходами из состояния в состояние. Игры, описывающие такие модели, называют стохастическими. Впервые стохастические игры рассмотрены Л. Шепли [62]. Т. Баш ар первым получил аналитическое решение стохастических квадратичных игр [37]. В настоящее время класс стохастических игр подробно освещен в литературе, актуальными являются работы, исследующие кооперативные стохастические игры [36, 57, 67, 68, 18].
Ещё один вид неопределенности, который может возникнуть при описании реальных процессов, это случайная продолжительность развития процесса. В играх, описывающих такие задачи предполагается, что игра заканчивается в некоторый случайный момент времени. В настоящее время ведётся активное исследование дифференциальных и многошаговых игр со случайной продолжительностью. Данной тематике посвящены, например, работы [19, 23, 34].
В данной главе предпринята попытка объединить два рассмотренных вида неопределенности применительно к линейно-квадратичным дискретным играм. Исследуются линейно-квадратичные дискретные стохастические игры со слу 47 чайной продолжительностью. Находится кооперативное решение игры в виде ES-вектора, предложенного в работе [45]. И рассматривается проблема динамической устойчивости [17, 16] кооперативного решения.
Рассмотрим дискретную линейно-квадратичную неантагонистическую игру п лиц, состояние которой в каждый момент времени задается вектором х(к): изменяющимся согласно системе уравнений вектор-столбец, Ui Є Rr - вектор-столбец управления игрока і, і = 1,...,n ; A(k), Bi{k) - матрицы размерности (тхт) и (тхг) соответственно, х(ко) = Хо - начальное состояние, w(k) - m-мерный вектор возмущений, - взаимонезависимые случайные вектора с нулевым математическими ожиданиями и матрицами дисперсий W(k). Игра начинается в момент ко из состояния хо-, однако, момент ее окончания не фиксирован заранее, а является реализацией некоторой случайной величины L. Случайная величина L принимает значения от ко до К с некоторыми вероятностями. Заданы вероятности qk того, что игра закончится на шаге /с, если она состоялась на (к — 1)-м, 0 qk l,k = 0}...}K,qK = l.
Обозначим через N = {1,..., п} множество всех игроков. Выигрыш игрока і Є N обозначим через Ji(ko,Xo,u), где и = (щ,... ,ип). Будем предполагать, что выигрыш игрока і имеет вид: где Pi (к) - симметричные матрицы размерности (mxm), Ri(k) - симметричные матрицы размерности (г хг), і = 1,..., п. Каждый игрок стремится максими 48 зировать свой выигрыш.
Заметим, что f(k) 0 для всех к = ко,..., К — 1, f(K) 0. Пусть Q_(T+) - множество отрицательных на 7+ матриц.
Теорема 6. Для того чтобы в игре Г(&о,Жо) существовало единственное в классе допустимых равновесие по Нэшу необходимо и достаточно, чтобы система матричных уравнений
Доказательство. Доказательство напрямую следует из [39] Corollary 6.4, с. 306, Remark 6.4, с. 281 и вида (2.0.4) выигрышей игроков. В данном параграфе будем искать кооперативные решения рассмотренной игры. Предполагаем, что игроки могут объединяться и перераспределять суммарный выигрыш. Исследуем различные способы построения кооперативных решений для данного класса игр. . можно построить характеристическую функцию v(S, XQ) : 2 — R в классе стохастических игр по следующему правилу: была разрешима относительно {М$(к)} Qs(k)}, в виде вещественных, ограниченных матриц размерности rs х т и т х т соответственно, где Qs(k) - симметричны. Тогда систему (2.2.2) можно рассмотреть как систему с одним управлением us(k) и функционалом Js. Согласно [27], чтобы существовало единственное управление, доставляющее максимум J5 , необходимо и достаточно, чтобы выполнялись условия теоремы, что и требовалось доказать.
Заметим, что в работе [49] предполагается, что характеристическая функция строится стандартным образом, а значит v(i,Xo) - это выигрыш, который может гарантировать себе игрок, при условии, что оставшиеся игроки играют против него. В нашем же случае v(i, XQ) - выигрыш, который может гарантировать себе игрок г, при условии, что оставшиеся игроки используют равновесные стратегии, т.е. -и(i, XQ) - выигрыш игрока і в равновесии по Нэшу. Подобным образом строится кооперативное решение в работе [2]. Согласно теоремам 6 и 7 в рассматриваемом классе игр ES-вектор может быть вычислен по формуле:
Некооперативная игра
Рассмотрим линейно-квадратичную игру на сети G = (N, U): где N - конечное множество узлов сети, N = {1, 2 ..., n}, U - множество пар (i, j), называемых дугами, і Є N: j Є N. Узлами сети считаем игроков. Предполагаем, что сеть G представляет структуру руководства или влияния некоторой организации.
Перед началом игры определятся управляющая коалиция Р. В качестве такой коалиции, например, можно взять базу, т.е. коалицию включающую наименьшее число лиц, влияющих на каждого члена организации.
Определение 17 ([И]). База В графа есть множество вершин, из которых достижима любая вершина графа и которое является минимальным, в том смысле, что не существует собственного подмножества в В, обладающего таким свойством достижимости. Если в графе существует несколько баз, то в качестве управляющей коалиции можно взять их объединение.
Для игроков, не входящих в управляющую коалицию, задается динамика, характеризующая состояние системы в каждый момент времени: х(к + 1) = Ах (к) + 2 вгиг(к), i =N\P (4.1.1) ко к К оо, &о, К Є 7+, х(ко) = хо, где х Є Rm - вектор-столбец, щ Є R - управление игрока і, і Є N\P ; А, ВІ - матрицы размерности (m х т) и (m х 1) соответственно, х(ко) = XQ - начальное состояние. Пусть N\P = {ii,... ,in-p}, Si = {j Є N\P : (i,j) Є 7} - множество игроков из N\P: для которых существует ребро (i, j). Выигрыш игрока і Є 7V\P обозначим через Ji(ko,Xo,u), где и = (щ1}... ,щп_ ). Будем предполагать, что выигрыш игрока і имеет вид: где Pb - симметричные матрицы размерности (тхт),Гі Є R, W{j Є R. Здесь Pi, г І - фиксированные параметры заданные в начале игры, W{j - вес ребра (i, j), который задаётся управляющей коалицией на первом шаге игры, W - матрица весов Wij. При этом Wij Є М, где М - конечное множество значений весов. Каждый игрок стремится максимизировать свой выигрыш. Предполагается, что игроки выбирают только стратегии вида щ(к, х) = Мі(к)х, ко к К, і є N\P. Обозначим через Gj \p игру между игроками, не вошедшими в коалицию, с динамикой (4.1.1) и выигрышами (4.1.2).
Считаем, что игроки, не вошедшие в управляющую коалицию, играют индивидуально. Игра протекает следующим образом: Управляющая коалиция выбирает стратегию 7 Гр, максимизирующую суммарный выигрыш игроков, не вошедших в коалицию в ситуации равно весия по Нэшу J2 Mko,x0,uNE{W),W).3 ecbuNE{W) = {u E{W),..., ufnE (W)) - ситуация равновесия по Нэшу в игре G/v\p. Предполагается, что управляющей коалиции известно, что оставшиеся игроки выберут равновесные по Нэшу стратегии, и 7 выбирается, учитывая это знание.
Игроки, не вошедшие в управляющую коалицию, выбирают стратегии, со ответствующие равновесию по Нэшу в игре G/v\p, И получают выигрыши Ui(ko, хо, uNE, W ). Здесь W - матрица весов, задающаяся стратегией 7 , / Є (0,1) - фиксированный параметр, характеризующий долю выигрыша, которую игроки оставляют себе, доля (1 — /) отдаётся управляющей коа лиции. Для нахождения ситуации равновесия по Нэшу в игре Gj \p переформулируем теорему о равновесии по Нэшу в линейно-квадратичной дискретной игре, приведенную в [39]. Теорема 14. Для того чтобы в игре Gjy\p существовало единственное в классе допустимых равновесие по Нэшу необходимо и достаточно, чтобы система матричных уравнений
Предположим теперь, что игроки, не вошедшие в управляющую коалицию, могут объединяться с целью максимизации суммарного выигрыша. Опишем ход игры в этом случае: 1. Управляющая коалиция выбирает стратегию 7 Є Гр, максимизирующую суммарный выигрыш игроков, не вошедших в коалицию, при условии, что они тоже максимизируют свой суммарный выигрыш J2 Ji{fo,xo,u(W),W).3flpcbu(W) = {йп {W),...,uin_p(W))- набор стра i&N\P тегий в игре GN\P: максимизирующий суммарный выигрыш. Предполагается, что управляющей коалиции известно, как будут вести себя другие игроки, и 7 выбирается, учитывая это знание. 2. Игроки, не вошедшие в управляющую коалицию, выбирают стратегии, максимизирующие суммарный выигрыш Ji(ko,Xo,u,W). Коалиция iN\P N\P получает выигрыш V(N\P) = I Yl Ji(ko, %o, u, W). Здесь W - мат iN\P рица весов, задаваемая стратегией 7, и - набор стратегий, на котором достигается максимум, / Є (0,1) - фиксированный параметр, характеризующий долю выигрыша, которую игроки оставляют себе, доля (1 — /) отдаётся управляющей коалиции.
В работе представлены результаты исследования кооперативных дискретных линейно-квадратичных игр. Рассмотрено несколько классов таких игр, для каждого из них построено кооперативное решение и исследовано такое важное свойство кооперативных решений, как динамическая устойчивость.
Кооперативные решения дискретных линейно-квадратичных игр с бесконечной продолжительностью построены при помощи специальным образом построенной характеристической функции. В динамических кооперативных играх возможны случаи, когда игроки могут посчитать для себя более выгодным отклониться от кооперативной траектории, поэтому для полученных кооперативных решений построена процедура распределения дележа, которая позволяет преодолеть проблему динамической неустойчивости. Также выведены достаточные условия устойчивости против иррационального поведения игроков. Данный вид неустойчивости может возникнуть даже если решение динамически устойчиво, в случае, если игроки действуют иррационально.
Также в работе рассмотрены кооперативные стохастические линейно-квадратичные дискретные игры со случайной продолжительностью. В качестве принципа оптимальности построен ES-вектор. Определено правило построение состоятельной во времени процедуры распределения дележа и выведены достаточные условия устойчивости против иррационального поведения.
Еще один класс линейно-квадратичных игр, который исследовался в работе, это игры с нетрансферабельными выигрышами. Для таких игр построены Парето-оптимальные решения, получены правила для вычисления состоятельной во времени процедуры распределения выигрыша, гарантирующие выполнение условие индивидуальной рациональности Парето-оптимального решения. А также показано, что при использовании этих правил, Парето-оптимальное решение удовлетворяет условию устойчивости против иррационального поведения игроков. В работе впервые рассмотрены кооперативные линейно-квадратичные сетевые игры с управляющей коалицией. Построены кооперативные решения.