Многошаговые стохастические игровые задачи управления

4
Оглавление
Введение
1 Многошаговые стохастические игровые модели и последовательные интерактивные решения........................................ С
2 Игровые задачи цепи Маркова................................. 11
3 Повторяющиеся игры с неполной информацией................... 17
4 Стохастические игровые задачи распределения ресурсов.........21
0 Глава 1. Игровые задачи остановки цепи Маркова
1 Введение к главе 1
1.1 Постановка задачи ........................................ 26
1.2 Уравнения оптимальности................................... 29
1.3 Обзор предшествующих работ по игровой задаче остановки 32
1.4 Структура главы 1 ........................................ 34
2 Игры с ’’почти детерминированными” переходами
2.1 Модель и уравнения оптимальности.......................... 36
2.2 Решения для игр с нулевыми платежами «21(2)............... 38
2.3 Решения для игр с положительными платежами <121(2) .... 41
2.4 Примеры................................................... 43
3 Рандомизированные стратегии остановки
3.1 Супергармонические и субгармонические функции............. 47
3.2 Выходная граница Мартина.................................. 49
3.3 Рандомизированные стратегии остановки и марковские
.# моменты ...................................................... 50
3.4 Задачи оптимальной остановки цепи Маркова................. 53
4 Игры остановки с ограниченными ожиданиями максимумов платежей
4.1 Игры остановки и уравнения оптимальности ................. 56
4.2 Решения уравнении оптимальности как решения игр остановки 57
4.3 Границы для решений уравнений оптимальности .............. 60
4.4 Построение решении для игр с ограниченными платежами ... 63
2
Ф
♦
5 Игры с пулевыми платежами при остановке только одним игроком
5.1 Уравнения оптимальности и свойства их решений. Игры с нулевым знамением................................................. 68
5.2 Игры с пустым останавливающим множеством В~ .............. 71
5.3 Игры с непустым постанавливающим множеством 13+........... 75
5.4 Иллюстративные примеры ................................... 80
6 Игры с нулевым платежом при остановке только первым игроком
6.1 Уравнения оптимальности и свойства их решений............. 82
6.2 Игры с пустым постанавливающим множеством /?+ ............ 86
6.3 Иллюстративный пример..................................... в8
Глава 2. Повторяющиеся игры с неполной информацией у второго игрока
1 Введение к главе 2
1.1 Постановка задачи ........................................ 93
1.2 ”Раскрывающиеся в пределе” игры. Игра Мертенса и Замира . . 95
1.3 Игры с сепарабельными выигрышами.......................... 98
1.4 Структура главы 2 ........................................ 99
2 Рекурсивное представление повторяющихся игр с неполной информацией у второго игрока
2.1 Формалпзнровапная модель................................. 103
2.2 Рекурсивное представление для стратегий и выигрышен . . 105
2.3 Рекурсивное представление для значений и оптимальных стратегий ....................................................... 107
3 "Раскрывающиеся в пределе” игры с двумя 2x2 матрицами
3.1 Структура множества’’раскрывающихся в пределе” игр . . 110
3.2 Некоторые формулы для биномиального распределения .. 113
3.3 Решения для игр ”смешанного типа”........................ 115
3.4 Вероятностная трактовка и асимптотика решений .... 120
3.5 Решения для игр типа ”седловой точки” ................... 122
3
%
4 Решения для симметричных сепарабельных игр
4.1 Свойства симметричных сепарабельных игр.................... 125
4.2 Некоторые <]>ормулы для мультиномиального распределения 12S
4.3 Построение решений для симметричных сепарабельных игр 133
4.4 Предельное поведение решений............................... 140
5 Игры с общими сепарабельными выигрышами 143
5.1 Свойства игр с общими сепарабельными выигрышами .... 144
5.2 Мультиномиальные транспортные задачи .... 147
5.3 ”Каноническое” разложение допустимых планов .... 149
5.4 Рекуррентные решения для мультиномиальных транспортных задач ......................................................... 152
5.5 Решения для игр Г„(р) сепарабельными выигрышами 155
5.G Пример. Игра Мертенса к Замира............................. 157
6 Функции значений транспортной задачи и мультиномиальное распределение
G.1 Постановка задачи.................................... 160
G.2 Транспортная задача и задача двойственная к ней...... 1G3
6.3 Структура носителей для матриц в общем положении .......... 1GG
G.4 Функция значений для задачи Т{СЛ •>■)................ 1G9
6.5 Функция значений для задачи Т(С\*,6)................. 171
G.6 Иллюстративные примеры .................................... 175
Глава 3. Многошаговые стохастические игровые модели распределения ресурсов
I Введение к главе 3 181
1.1 Постановка задачи.......................................... 1S2
1.2 Структура главы и описание основных результатов............ 184
1.3 Стохастические игры с дисконтированным выигрышем .. 186
1.4 ’’Абсолютные” ситуации равновесия стохастических игр . . 1S9
1.5 Игровая модель распределения ресурсов как стохастическая игра 193
1.G Модели распределения ресурсов с несколькими отраслями потребления и производства .................................... 19G
•1
*
♦
2 Решения для однородных моделей распределения ресурсов с одним агентом 199
2.1 Однородные модели распределения ресурсов с одним
агентом........................................................ 200
2.2 Решения для конечного интервала планирования . . . 203
2.3 Решения для бесконечного интервала планирования . . . 200
2.4 Многоотраслевые однородные модели. Решения для одношаговых моделей............................................ 209
2.5 Решения для многоотраслевых многошаговых
однородных моделей............................................. 214
% 3 Игровые пропорционально-однородные модели
распределения ресурсов 221
3.1 Формализация пропорционально-однородных моделей .... 222
3.2 Условия согласования индивидуальных и социальных полезностей.................................................... 225
3.3 Решения для вспомогательных одношаговых игр .... 228
3.4 Абсолютные равновесия для конечного горизонта .... 230
3.5 Абсолютные равновесия для бесконечного горизонта . 233
4 Решения для игровых многоотраслевых пропорционально-однородных моделей распределения ресурсов 237
4.1 Формализация многоотраслевых пропорцмонально-
однородиых моделей ............................................ 23Б
4.2 Решения для одиошаговых игровых задач с несколькими отраслями потребления.......................................... 241
4.3 Решения одношаговой игровой задачи распределения с несколькими
отраслями производства......................................... 244
4.1 Решение для многошаговых многоотраслевых игровых
моделей распределения ресурсов................................. 247
4.5 Решение для многошаговых многоотраслевых игровых
моделей с бесконечным горизонтом планирования ................. 252
Список литературы.............................................. 257
5
Введение
1 Многошаговые стохастические игровые модели и последовательные интерактивные решения
Предметом представляемой диссертационной работы является исследование различных аспектов принятия последовательных решений в условиях долговременного взаимодействия и неопределенности на основе современных достижений теории многошаговых динамических стохастических игр с неполной информацией. Рассматриваемый в работе круг задач может быть отнесен к вероятностной теории оптимального управления.
Многошаговые стохастические игровые модели являются обобщениями управляемых марковских случайных процессов с дискретным временем, или по другой терминологии — многошаговых марковских процессов принятия решений (Multistage Markov Decison Processes — MMDP) (см., например, книги Дышат, Юшкевич [20], Мани, Осаки [30]), на случаи, когда в принятии решения участвуют несколько лиц с несовпадающими интересами.
Многошаговый стохастический игровой процесс с дискретным временем представляет собой динамическую систему с пространством состояний Ху способную изменять свое состояние в моменты времени t = 0,1,2,... под воздействием как управлений, выбираемых игроками в эти моменты, так и случайных факторов. Управления выбираются на основании предусмотренной правилами игры информации о предшествующих состояниях и о выборах игроками управлений на предшествующих этапах игры. После того как выбор всеми игроками сделан, игроки получают соответствующие этой ситуации доходы, система переходит в следующее состояние, а игроки получают предусмотренную правилами игры информацию об этом состоянии и о действиях партнеров.
Задача игрока в многошаговой стохастической игре состоит в том, чтобы максимизировать некоторые сводные показатели (целевые функции), выражающие оценку всей последовательности своих доходов, принимая во внимание, что остальные игроки поступают аналогично.
Известно, что "практически любая” динамическая игра, то есть игра, в которой процесс принятия решений игроками развернут во времени, может быть нормализована, то есть сведена к игре, и которой решения игроками принимаются однократно (см., например, Воробьев [-1]). Однако, несмотря на свою концептуальную важность, такое сведение не всегда оказывается целесообразным, ибо оно затушевывает те специфичс-
ские структурные свойства игры, которые могут облегчить ее анализ.
Более того, именно эти структурные динамические свойства решении являются предметом исследования в теории многошаговых динамических игровых моделей с неполной информацией, и превращают ее в основание для теории принятия последовательных решений в условиях долговременного взаимодействия и неопределенности.
Как указывалось выше, многошаговые стохастические игровые модели с неполной информацией являются непосредственными обобщениями управляемых марковских случайных процессов с дискретным временем, в которых имеется только один принимающий решения агент. Более того, если в игровой модели стратегии всех игроков, кроме одного, определены и обладают некоторыми "марковскими” свойствами, то нахождение оптимального ответа этого игрока оказывается задачей теории управляемых марковских случайных процессов.
Вследствие этого, характерным для теории многошаговых динамических игровых моделей с неполной информацией является их рассмотрение именно как управляемых динамических стохастических систем и использование подходов и методов, аналогичных применяемым в теории управляемых случайных процессов, интенсивно развивавшейся в последние десятилетня. Результаты этой теории широко используются при изучении стохастических динамических игровых моделей. В этой теории учитывается двоякая роль управления - на каждом шаге нужно сравнивать непосредственный выигрыш от принятого решения с его влиянием на последующую эволюцию системы. Вследствие этого, оптимальные выигрыши, соответствующие различным начальным состояниям процесса, должны удовлетворять уравнениям оптимальности Вальда — Бсллмана, выражающим принцип динамического программирования (см. Вальд [3], Веллман [!))•
Основным математическим инструментом для изучения принятия решений в условиях конкурентного взаимодействия (интерактивных решений) является теория игр.
Теория игр исследует принятие решений в условиях неопределенности, возникающей при взаимодействии нескольких агентов с несовпадающими интересами в результате того, что исход ситуации зависит от выбора всех участников (игроков). Дополнительная неопределенность может возникать в результате того, что этот исход может зависеть также от некоторых внешних случайных факторов.
Основной целью диссертации является построение и анализ решений,
то есть оптимальных стратегии игроков, и значении, то есть оптимальных выигрышен игроков, для многошаговых стохастических игровых задач с неполной информацией, в различных постановках и интерпретациях.
При изучении игровых ситуаций, в которых прямая кооперация между участниками отсутствует (бескоалиционные игры), иод решением игры понимается нахождение ситуации равновесия по Нэшу, т.е. таких наборов стратегий игроков, для которых каждому участнику невыгодно отклоняться от стратегии, предписываемой этим набором, при условии, что остальные применяют стратегии из того же набора (см., например, Воробьев [4]).
Однако, многошаговая стохастическая игра представляет собой не одну игру, а целое семейство игр, зависящих от начального состояния системы х0 = х 6 А'. Выигрыши игроков в ситуациях равновесия, соответствующих различным начальным состояниям, должны быть связаны между собой.
Антагонистическая игра имеет значение г(х), при использовании игроками 1 и 2 стратегий t и 5 из классов Т и S соответственно, если выполняются соотношения (теорема о минимаксе)
sup inf I\x{t,s) = infsup/Y'x(<,s) = г(г),
T S S т
где f\'x{t,s) — выигрыш Игрока 1, соответствующий начальному состоянию цепи х.
В теории игр получены и используются различные теоремы о мини-максе, то есть теоремы, обеспечивающие равенство supinf = inf sup при соответствующих предположениях относительно функций выигрыша II о структуре множеств стратегий игроков. Обычно, в таких теоремах предполагается, что множества стратегий игроков выпуклы и компактны п некоторой ’’естественной” топологии, а функция выигрыша непрерывна, вогнута относительно стратегий максимизирующего игрока и выпукла относительно стратегий минимизирующего игрока (см., например, Карлин [22)).
Множества чистых стратегий игроков для рассматриваемых игр, вообще говоря, не удовлетворяют этим требованиям, и, таким образом, теорема о минимаксе может не выполняться.
Хорошо известным средством преодоления этого дефекта, используемым в теории игр, является введение рандомизированных стратегий. При этом возможны два различных подхода к построению рандомизирован-
них стратегии, а именно — смешанные стратегии, то есть вероятностные смеси чистых стратегий, и рандомизированные стратегии поведения, то есть стратегии, в которых рандомизация происходит на уровне элементарных пошаговых действии игроков. Известно, что, при достаточно широких условиях, оба эти подхода эквивалентны (см. Кун [С4], Ауман [39]).
Для игр с нулевой суммой (антагонистических игр) при выполнении теоремы о миннмаксе однозначно определяется значение игры. Все оптимальные стратегии равноценны, ибо гарантируют один и тот же выигрыш, и взаимозаменяемы. Выигрыши игроков в ситуации равновесия многошаговой антагонистической игры должны удовлетворять уравнениям оптимальности, выражающим принцип динамического программирования в игровой формулировке (см. Петросян и др. [31]).
Для игр с ненулевой суммой, в случае неединственности ситуации равновесия, множество ситуации равновесия, рассматриваемое как решение игры, обладает целым рядом недостатков. Важнейшими из этих недостатков являются следующие:
а) выигрыши игроков в различных ситуациях равновесия могут не совпадать, что означает невозможность определить единое равновесное значение игры;
б) испрямоугольность множества ситуаций равновесия, то есть невозможность заменить стратегию одного из игроков в заданной ситуации равновесия на стратегию из другой ситуации равновесия, что означает невозможность определить равновесные оптимальные стратегии.
Кроме того, для игр с ненулевой суммой выигрыши игроков в ситуации равновесия, вообще говоря, не должны удовлетворять принципу динамического программирования. Однако, этому принципу должны удовлетворять устойчивые выигрыши игроков в "абсолютной”, то есть устойчивой относительно нодыгр ситуации равновесия (см. Петросян п др. [31]).
Для задачи с конечным числом шагов, ’’абсолютные” ситуации равновесия удовлетворяют принципу обратной индукции по числу шагов и могут быть построены на его основе с использованием теории управляемых марковских процессов с доходами.
Для задачи с бесконечным числом шагов уравнения оптимальности позволяют найти выигрыши игроков в ’’абсолютной” ситуации равновесия процесса как неподвижные точки оператора оптимальности. В этом случае, оптимальные действия игроков определяются только наблюдаемым состоянием системы. Таким образом, в этом случае, оптимальные дей-
ствня игроков образуют стационарные стратегии.
Первая работа по теории стохастических игр (как и сам термин) принадлежит Шепли [83]. За пять десятилетни, прошедших со времени опубликования этой статьи, вопросам теории стохастических игр было посвящено несколько сотен работ (см. обзоры Партхасаратхн и Штерн [77], Мсртенс, Сорен и Замир [77], а также обзор автора (13]).
Исследование процессов принятия решений в условиях конкурентного взаимодействия лежит в основе математического моделирования и анализа социальных процессов, и, в частности, в основе математической теории экономического поведения.
Многошаговые игры представляют собой естественную модель для исследования сложного интерактивного поведения. Продолжительность процесса взаимодействия позволяет участвующим в нем агентам генерировать некоторые представления относительно других участников, сделать свои умозаключения, статистические выводы и т.д. Изучение этого процесса предоставляет возможность охарактеризовать и формально описать различные формы кооперации и обмена информацией, возникающие из изначально некооперативиого поведения участников игры. Для самой же теории игр анализ ситуаций равновесия для многошаговых игр предоставляет возможность связать между собой стратегические к нестратсгичс-ские (кооперативные) аспекты теории.
Так, хорошо известный результат теории повторяющихся игр, ("folk theorem”, см. (67]), утверждает, что все кооперативные индивидуально рациональные, то есть обеспечивающие всем участникам игры выигрыши, не меньшие, чем их максимальный гарантированный минимум, исходы одношаговой игры могут быть реализованы как результаты некооперативного поведения — ситуации равновесия в повторяющейся игре с бесконечным временным горизонтом.
Максимальный гарантированный минимум участника игры представляет собой значение антагонистической игры, возникающей, если все остальные игроки кооперируются и действуют так, чтобы минимизировать выигрыш данного участника.
Исследование повторяющихся многошаговых игр с полной информацией показывает, что кооперация может возникать как результат угрозы наказания в будущем. Повторение, в этом случае, выступает в роли принуждающего механизма.
В антагонистических повторяющихся играх с неполной информацией проблемы стратегической передачи и сокрытия информации могут не-
следоваться сами по себе, вне зависимости от каких либо кооперативных эффектов. В этом случае повторение служит исключительно в качестве сигнального механизма.
Результаты, полученные для антагонистических многошаговых игр, непосредственно применяются к неантагонистическим играм. Так характеризация ситуаций равновесия использует условия индивидуальной рациональности, которые опираются на антагонистический вариант игры. В повторяющихся многошаговых играх с неполной информацией повторение служит одновременно и механизмом принуждения и сигнальным механизмом.
Продолжительность взаимоотношений между агентами порождает многие феномены интерактивного поведения - угрозы, наказания, поощрения, обнаружение и сбор информации, а также введение партнеров в заблуждение. Конструкция многошаговых игр направлена на изучение всех этих явлений.
Как указывалось ранее при полной информации повторение делает возможной кооперацию. При неполной информации повторение выполняет также роль сигнального механизма. Наиболее интересные аспекты социальных и экономических ситуаций проявляются при асимметричной информации у их участников.
Области приложений теории игр включают такие разделы общественных паук, как экономическая теория, социальное поведение и социальный выбор.
В последние десятилетия теория игр переживает новый подъем, которым она обязана, в некоторой степени, своей трансформацией из чисто нормативной дисциплины, каковой она была на ранних этапах своего существования, в некую разновидность науки о поведении. Эта трансформация привела к существенному расширению области приложении теории игр, включив в нее такие предметы изучения, как эволюционная теория, теория обучения и интерактивная эпистемология. Все эти области существенно используют теорию многошаговых динамических игр (см. книги Бинмора [43], Лумана и Машлера [11], Мертенса, Сореиа и Замира [07]).
Диссертация посвящена исследованию многошаговых стохастических игровых задач управления с неполной информацией, в различных постановках н интерпретациях.
2 Игровые задачи остановки цепи Маркова
В первой главе рассматривается игровая задача остановки цени Маркова в постановке, восходящей к работе Дынкина [19] и его последователей
(Фрид [34), Кифер (26), ГусеГш-Заде (6)). На Западе такие игры впервые рассмотрел Невё [73), который назвал их "играми Дынкииа”.
Два игрока наблюдают за неныо Маркова и могут остановить се в любой момент. Если оба игрока останавливают цепь одновременно, то игрок 1 выигрывает у игрока 2 сумму «ц(х), где х — состояние цени в момент остановки. Если первым остановившим является только игрок 1 или только игрок 2, то игрок 1 выигрывает «12(х) или «21(3*), соответственно.
На пространстве состояний цепи определена также функция с, задающая "выигрыш в бесконечности”. Если ни один из игроков не останавливает цепь, то игрок 1 выигрывает сумму, равную Пт^с© с(хп). Функцию с(х) можно считать гармонической функцией относительно переходного оператора Р цепи Маркова, то есть с(х) = Рс(х)^ что гарантирует существование предела.
Игровые задачи остановки являются обобщениями задач оптимальной остановки случайных процессов (см., например, книги Ширяева [30] и Роббинса, Сигмунда, Чао [33]) на случай, когда в принятии решения участвуют несколько лиц с несовпадающими интересами. Задачи оптимальной остановки представляют собой наиболее изученный раздел теории управления случайными процессами. Отличительной особенностью таких задач является наличие у игроков в каждый момент только двух возможных управлений (элементарных стратегии) — продолжить наблюдение за траекторией управляемого процесса, или прекратить его.
Значение игры остановки г(х), как функция начального состояния цепи то = х, должно удовлетворять уравнению оптимальности, выражающему принцип динамического программирования Веллмана в игровой формулировке. Уравнение оптимальности имеет вид
«(х) = (Ти)(х) = уа1[а,д(х,н)],
где уа1[л,Д — значение матричной игры с матрицей выигрышен [а,>], ау(*,и) = ау(аг) при (г?) ф (22) и а22(*,и) = (^-«)(х) = Е[и(х2)|*1 = *].
Отметим, что функция с, задающая ’'выигрыш в бесконечности”, не учитывается уравнением оптимальности. С другой стороны, неподвижная точка оператора Т, вообще говоря, не единственна, и различным "выигрышам в бесконечности” с могут соответствовать различные решения уравнения оптимальности.
Существует обширная литература по играм Дынкииа, как с дискретным, так и с непрерывным временем, дающая достаточные условия для
существования значения игры. В большинстве работ предполагалось, что выигрыши удовлетворяют соотношениям, которые гарантируют разрешимость игры с использованием только чистых стратегий остановки. Предполагалось также, что, если ни один из игроков не останавливает цепь, то игра заканчивается вннчыо (игрок 1 получает нуль). Встает вопрос о существовании значения игры и рандомизированных оптимальных моментов остановки при отказе от этих предположений. Также возникает задача выяснения зависимости значения игры от функции с, задающей ’’выигрыш в бесконечности”.
Целыо первой главы является построение решения для антагонистической игровой задачи остановки цепи Маркова при достаточно общих предположениях с помощью рандомизированных моментов остановки. Мы рассматриваем ’’выигрыш в бесконечности” с как переменный параметр и ищем решения для семейства игр остановки, параметризованных начальными СОСТОЯНИЯМИ То = х и функциями с.
Поскольку значение игры остановки должно являться неподвижной точкой оператора оптимальности 7\ исследование игровой задачи остановки сводится к изучению областей притяжения неподвижных точек оператора Т. Области притяжения неподвижных точек определяются структурой выигрышей, а также структурой переходных вероятностей цепи.
Глава 1 организована следующим образом:
В разделе 2 возможные проблемы и результаты, возникающие при решении игровых задач оптимальной остановки иллюстрируются на примере построенных в явном виде решений для класса игровых задач остановки с очень простой структурой переходных вероятностей цепи. Для этого класса задач множество состояний Л' = 1,2,... — множество натуральных чисел. Вероятность перехода из состояния х в состояние х + 1 равна р(х), а с вероятностью 1 — р(тг) цепь обрывается — переходит в поглощающее состояние 0 с нулевыми выигрышами. В частности, этот класс включает в себя игровые задачи оптимальной остановки с детерминированными переходами на счетном множестве состояний.
Простая структура переходов обуславливает столь же простую структуру чистых стратегий (нерандомиэнроваиных марковских моментов) для этой цени. Наблюдения за цепыо не дают игрокам никакой информации. Чистые стратегии игроков определяются номером шага, на котором игрок останавливает цепь, вне зависимости от сс состояния. Вследствие этого исследование таких игр не требует привлечения аппарата теории цепей Маркова и других аппаратных средств теории вероятностей.
Однако, уже рассмотрение игровых задач остановки для пространственно-временной цепи, для которой текущие выигрыши определяются дстср-минированно изменяющейся временной координатой, а пространственная координата влияет только на ’’выигрыш в бесконечности”, требует исследования гармонических функции и выходной границы Мартина для пространственной цепи.
В разделе 3 приводятся необходимые сведения о суиергармоничсских и субгармонических функциях для ценен Маркова, и о связанной с ними теории выходных границ Мартина. Приводятся также сведения о структуре и свойствах рандомизированных марковских моментов и о теории оптимальной остановки для цепей Маркова.
Чистыми стратегиями игроков для игр остановки являются обычные марковские моменты для наблюдаемой цепи, а смешанными стратегиями поведения — рандомизированные марковские моменты. Стационарная стратегия задается функцией г : А' —> [0,1], выражающей условную вероятность остановить цепь при попадании в состояние х. Показывается, что стационарная стратегия задает разбиение границы Мартина на ’’останавливающее” и ’’нсостапавливающее” множества, указываются подходы к их построению. В частности, показано, что стратегия не останавливает цепь в том и только том случае, если потенциал функции т конечен.
В разделе 4 дастся формальное описание рассматриваемых игровых задач остановки, стратегий и уравнений оптимальности.
Мы предполагаем, что функции <*12, «21 и с принадлежат классу Ь таких функций д на пространстве А”, что Ех8ирп |<7(х„)| < оо, для всех х € А'.
Э го предположение позволяет определить гармонические функции
/і,2(х) = Er lim sup я12(хп),
п-*со
hn(x) = Ех lim inf a2i(xn),
П—тОО
а также соответствующие им функции на границе Мартина
Ы&).
Основным результатом раздела 4 является следующая теорема:
Теорема 1.4.1. Пусть все платежные функции принадлежат классу L. Тогда игра Гс(х) имеет значение vc(x), определяемое соотношениями
vc{x) = lim rr\Vc\(x) ж lim T*W~(x)}
4 ' n—»OO C ' «-»W СУ'
И
где И£+(ж) — цена максимизационной задачи оптимальной остановки с текущим выигрышем «^(х) и с ”выигрышс.и па бесконечностип с+ = сЛй21, \У~_(х) — цена минимизационпой задачи с текущим выигрышем **21 (х) и с "выигрышем па бесконечности* с~ = с\//г12.
Следствие. В предположении, что все платежные функции принадлежат классу £, значение ис(:г) игры Гс(аг) зависит от значений с(6) ”выигрыша на бесконечности” только в тех точках границы Мартина, для которых выполняются неравенства
£«(*)< с(6)<Ы6).
При приближении траектории цени к элементу границы Мартина, для которого эти неравенства не выполняются, оптимальные стратегии игроков останавливают цепь.
В разделах 5 и б мы отказываемся от предположения, что функция «ц принадлежит классу Ь. Это усложняет ситуацию, так как скорость роста функции «п оказывается дополнительным фактором, определяющим степень воздействия выигрыша на бесконечности на значение игры.
Получены оценки для значении игр остановки цепи Маркова со специальной структурой выигрышен. Предполагается, что выигрыши неотрицательны, п что выигрыш = 0. Последнее условие мешает игроку 1 использовать чистые стратегии остановки и позволяет игроку 2 воздерживаться от остановки, рискуя только ”выигрышем па бесконечности” с. Чтобы проиграть меньше, игрок 2 должен останавливать цепь с положительной вероятностью. Описаны решения для таких игр с использованием рандомизированных моментов остановки.
Решение V уравнения оптимальности для таких игр удовлетворяет неравенствам 0 < V < Ри, т.е. значение игры Гс(х) является неотрицательной субгармонической функцией, удовлетворяющей условию ус(х) < с(г). Асимптотика значения такой игры определяется гармонической составляющей в разложении Рисса этой функции.
В разделе 5 мы рассматриваем игры с платежами, удовлетворяющими условиям
«21 = п12 = 0, «и,с > 0,Ух € А.
Из теоремы 1.4.1 следует, что, если функция ап 6 £, то при любой функции с значение ис игры Гс(я) равно нулю.
Для любого состояния г, для которого некоторое возвратное состояние достижимо п.н., при любой функции с значение игры ис(т) = 0.
Далее мы предполагаем, что все состояния цепи невозвратны (или являются поглощающими, с нулевыми выигрышами).
Из уравнения оптимальности следует, что ядро потенциала в разложении Рисса для субгармонической функции vc удовлетворяет уравнению 7Гс(х) = Pvc(x) - ис(х) = vc(x) • Pvc(x) • («„(х))“1.
Пусть В* С В — неостаиавливающее подмножество границы Мартина для стационарной стратегии, определяемой функцией оа(у) = («1i(j/))“ 1, а Iß + - ее индикатор. Пусть с^+ — гармоническая функция, определяемая граничными значениями с(6) • Iß+{b).
Теорема 1.5.2.
а) для любой положительной гармонической функции с(х) 6 L игра Гс(х) имеет значение нс(я), удовлетворяющее ”граничному условию на бесконечности”
lim vc(xn) = lim Cß+ (xn); (5.7)
П—* OO Л —¥CO
б) функция vc(x) — единственное решение уравнения оптимальностях (5.1), удовлетворяющее этому граничному условию на бесконечности;
в) стационарная стратегия т* игрока 1, определенная соотношениями
Т'ЛХ) = • «(а:)-1 Vx £ Л',
оптимальна; г) игрок 2, в общем случае, имеет только е-оптимальную стратегию.
Предложение 1.5.6. Функция t’c(x) удовлетворяет неравенствам
Тпхис(х) < vc(x) < Тпс(х), где функция wc(x) определена соотношением (5-4);
последовательность Тпгос(х) не убывает, последовательность Тпс[х) не возрастает, обе последовательности монотонно сходятся к t’c(x).
Следствие. Значение г>с(х) игры Гс(х) зависит от значений с(6) "выигрыша на бесконечности’’ только в точках 6 границы Мартина, принадлежащих неостанавлпвающсму подмножеству В+. При стремлении траектории цепи к точке границы 6 G В~ £-оптимальная стратегия игрока 2 останавливает цепь.
13 разделе G мы рассматриваем игры с платежами, удовлетворяющими условиям
«21 = 0, ап > «12 >0,- с> 0, Vx € X.
Для любой гармонической функции с > 0 определим стратегию ас соотношениями СТс(х) = 1, если «ц(х) < с(х), ае(х) = с(х) ■ йц(х)“1, если «21 (^) < с(х) < «ц(х), СГс(х) = 0, если «2|(*) > ^(х).
Пусть С+(х) — множество всех таких гармонических функций, что стратегия <7С останавливает цепь. Пусть с+ — наименьшая нижняя грань множества С+(х). Гармоническая функция с+(х) удовлетворяет неравенствам 0 < с+(х) < оо.
Теорема 1.6.2. Гармоническая составляющая в разложении Гисса Оля субгармонической функции гс равна с.Ас.+ . Значение гс(х) игры Гс(х) равно пределу невозрастающей последовательности Тп(с Л с+)(х).
3 Повторяющиеся игры с неполной информацией
Во второй главе рассматриваются антагонистические повторяющиеся игры с неполной информацией у второго игрока. В таких играх Гп(р) игроки разыгрывают матричную игру п раз. Матрица выигрышей А3 выбирается случайным ходом из конечного множества матриц в соответствии с распределением р. Первый игрок знает матрицу выигрышен Л\ а второй знает лишь априорное распределение. После каждого шага оба игрока узнают ход противника. В конце игры игрок 2 платит игроку 1 средний выигрыш за одни шаг.
В такой игре второй игрок на каждом шаге игры вынужден переоценивать свою априорную информацию на основании действий первого игрока, а информированный первый игрок должен учитывать возможность такой переоценки и стараться выдать как можно меньше информации противнику.
Анализируя конкретную повторяющиеся игры с неполной информацией, приходится рассматривать все семейство игр, возникающих при допущении произвольного априорного вероятностного распределения. Таким образом, естественным объектом изучения оказывается функция значений, сопоставляющая каждому распределению р 6 Д(5) значение ь’„(р) п-шаговоп игры. Последовательность оп{]>) убывает но п. Ауманн и Машлер [40] показали, что Нтц„(р) равен минимальной вогнутой мажоранте значения матричной игры с усредненной матрицей выигрышей
ЕМ*-
Поэтому значительный интерес представляет исследование игр, для которых значение усредненной игры линейно. Для таких игр ”в пределе” игрок 2 теряет столько же, сколько он мог бы потерять, зная 6, и столько же, сколько он теряет, если оба игрока 5 не знают. Это даст основание
назвать такие игры "раскрывающимися в пределе" играми.
Для конкретной игры этого класса Мертоне и Замир [68] показали, что нормальное распределение возникает в асимптотике значения игры. Однако, вероятностная природа результата оставалась непроясненной. Весьма актуальным представляется выяснение вопроса о том, насколько широко этот результат может быть распространен, и его вероятностное истолкование.
Глава 2 построена следующим образом:
В разделе 2 дается определение повторяющихся игр с неполной информацией у второго игрока, стратегий и ситуаций равновесия по Нэшу. Приводятся сведения о рекурсивных свойствах значений и оптимальных стратегий как первого, так и второго игрока, связывающих решения и —1-шаговых и п-шаговых игр.
В разделе 3 исследуются "раскрывающиеся в пределе" игры, задаваемые двумя матрицами Д1 и Л2 размера 2x2. М 1.1 описываем все множество "раскрывающихся в пределе” игр этой размерности. Это множество распадается на два подкласса, которые мы называем играми "смешанного типа” н играми "чистого типа", в соответствии с характером решений для платежных матриц.
Для класса игр "смешанного типа” с точностью до стратегической эквивалентности платежные матрицы могут быть представлены в виде:
! Ла'д; -а%] ,2 _ Ч Г *74 -«7*5
-Л[-аД; арх Л -Л[-ар'2 а/?2
(0.1)
где А > 0, 0 < а,/?ь/?2 < 1* Здесь (а, 1 — а) - общая оптимальная стратегия игрока 1 для обеих матриц Л1, Л2.
Мы получили решения в явном виде для и-шаговых игр "смешанного типа”. Оптимальная стратегия игрока 1 представляет собой зависящую от состояния последовательность лотерей, для которой на каждом шаге общая вероятность использования первого действия равна о. Таким образом, с точки зрения игрока 2, последовательные ходы игрока 1 играющего свою оптимальную стратегию, образуют последовательность независимых испытаний с вероятностью успеха а. Естественно, что полученные решения выражаются через функции вероятности биномиальных распределений с параметрами а и п.
Применяя Центральную Предельную Теорему к биномиальному распределению, мы получаем следующее утверждение:
Теорема 2.3.2. Для игры Г„(р) с матрицалш вида (0.1) с коэффпщиеп-
1В
том А = (/?і — /?2) 1 справедливо равенство
Шп ^уа1Гя(р) = у/асфИ ехр(-д*/2),
где \р — р-коантиль стандартного нормального распределения.
Мы получаем решения также и для "раскрываемых в пределе” игр "чистого типа”.
Отметим, что класс игр "смешанного типа" в размерности 2 х 2 с точностью до стратегической эквивалентности совпадает с классом игр с сепарабельными выигрышами. Для таких игр выигрыш распадается в сумму двух слагаемых, одно из которых не зависит от состояния природы и определяется только действиями игроков, а второе не зависит от действия игрока 2 и определяется только действиями игрока 1 и состоянием природы.
В разделе 4, переходя к более высоким размерностям, мы начинаем с исследования повторяющихся игр с симметричными сепарабельными выигрышами вида е-у = «у + с6*у где 6- — символ Кроцекера. Мы предполагаем, что матрицы А = [я,у] и А3 имеют одну и ту же единственную вполне смешанную оптимальную стратегию й: = (®ь... ,а:то) € Д7 игрока 1, н что уа1Л = 0. Из этого следует, что значение игры для усредненной матрицы Д(р) = Ер,Д* равно скалярному произведению < р,х > векторов р и х. Следовательно, для значения игры Уп(р) справедливо равенство 1ітГІ_+сог;п(р) =< р,х >.
Мы выражаем решения для этих игр в терминах мультиномиального распределения с параметрами х = (.ті,... ,х,„) Є Дт и п.
Полученное представление решения для этих игр с помощью мультиномиального распределения позволяет использовать Центральную Предельную Теорему и описать предельное поведение остаточного члена £п(р) = ”п0>)- < %>Р >•
Пусть Ф(у) — плотность (т — 1)-мерного центрированного нормального распределения с матрицей ковариаций £ = + .гт - (х, - .гт)(.г, -
*т)). ^ _ _
Каждой точке го Е /їт"і мы сопоставляем разбиение пространства Л™”1:
ФДїїї) = {у € К-т-1|у, -У* > Щ-и>9 і = 1,...,т- 1, у, > -гв3}, Фт(®) = {у є К-т_1|ул < -ю« л = 1,...,т - 1,}.
19
Для точки р Є /їі/А5 пусть ю(р) Є її"1"1 — единственная точка, для которой разбиение (<?«(&7(р)))«є5 порождает точку р:
Р* = ( ,гт.ф(й№)т"!і 5 = 1,...,т.
'СіЛЩР))
Теорема 2.4.2. Для игр Гп(р)
где д(}3 — граница области С)3, {(1у)т 2 — элемент гиперплоскости.
В разделе 5 исследуются игры Гп[р) с общими сепарабельными выигрышами вида а*; = а# + Ь\. Специфическим свойством этих игр является то, что для них значение усредненной игры линейно.
Получены решения для конечно повторяющихся игр Г„(р) с сепарабельными выигрышами общего вида. Элементы решений представлены посредством решений задач линейного программирования транспортного типа, которые мы называем мультиномиальными транспортными задачами.
Для мультиномиальной транспортной задачи Тп{р), соответствующей игре Г„0>), множество пунктов производства - множество 5 состояний игры, а множество пунктов потребления - множество Ът(п) целочисленных неотрицательных векторов с суммой компонент равной п. Такие вектора могут трактоваться как результаты п испытании с т исходами.
Маргинальным распределением уровней производства является априорное распределение р, а маргинальным распределением уровнен потребления является мультиномиальные распределение с параметром п. Затраты определяются скалярными произведениями векторов 6 = (6-) и векторов с, соответствующих пунктам потребления. Таким образом, будучи линейной комбинацией нескольких транспортных задач, описанная мультиномиальная задача может рассматриваться как транспортная модель с несколькими товарами.
Мы раскрываем рекурсивную структуру решений для задачи Тп(р), которая оказывается аналогичной рекурсивной структуре решений рассматриваемых игр. Это позволяет свести решения игр Г„(р) к решению задач 7\(]>).
Мы иллюстрируем наш подход, применяя его к игре, изучавшейся в работах Мертенса и Замира [68], [69] и Хойера [62]. Мы вычисляем зпа-
ченнс игры и оптимальные стратегии игроков, решал довольно простую транспортную задачу, и в результате мы легко получаем решение Хонсра для конечно повторяющейся игры.
Для того, чтобы получить результат Мертеиса и Замира об асимптотическом поведении значении, Хойср применяет центральную предельную теорему непосредственно к значенню игры. Мы применяем центральную предельную теорему к биномиальному распределению, являющемуся маргинальным распределением транспортной задачи.
Мы рассматриваем предельную транспортную задачу со стандартным нормальным распределением Лг(0,1) в качестве маргинального распределения уровнен потребления и с априорным распределением /> в качестве распределения уровнен производства. Решая эту задачу, мы получаем новое и прозрачное доказательство результата Мертеиса и Замира.
В последнем разделе второй главы мы исследуем значение транспортной задачи \'а1(«,6) как функцию уровней производства и потребления. Полагая суммарное производство и потребление равным единице, мы можем считать эти уровни а 6 Д(/) и 6 Є &{J)- вероятностными векторами на множестве пунктов производства / и пунктов потребления J соответственно. Допустимые планы транспортной задачи Л' = ||х,;|| € Д(/ х J) -вероятностные распределения на / х 3 с заданными проекциями а и 6.
Фиксируя вектор Ь Є Д(</), мы исследуем значение транспортной задачи как функцию уаІЦа) на симплексе Д(/). Вогнутая и кусочно-линейная функция уаіі(а) характеризуется своими максимальными областями линейности. Ее значения в этих областях определяются значениями в крайних точках областей, или в точках пиков. Функция \-а1Дл) имеет точек ников, которые находятся во взаимнооднозначном соответствии с векторами из множества ?.»п-мерпых целочисленных неотрицательных векторов с суммой компонент, равной 11. Точки пиков функции значении соответствуют решениям обобщенных задач о назначениях для матрицы С. Обобщенной задачей о назначениях мы называем транспортную задачу, в которой Ь = (1,...,1) € Я", а вектор а - целочисленный вектор, принадлежащий 2™.
Области линейности этой функции находятся во взаимнооднозначном соответствии с векторами из н из Первые векторы характе-
ризуют конфигурации и объемы областей, а вторые определяют их относительное расположение. Область линейности //б(<7), соответствующая вектору д € является выпуклым многогранником с П?=і(<?і + О
крайними точками. Объем |£ь(<?)| задается соответствующим коэффнци-
ентом мультиномиального распределения.
4 Стохастические игровые задачи распределения ресурсов
В третьей главе исследуются многошаговые стохастические игровые модели распределения ресурсов (капиталов) между потреблением и производством (инвестициями) несколькими конкурирующими агентами. Эти модели являются обобщениями многошаговой модели распределения ресурсов одним агентом, изученной в книге Дыикнпа и Юшкевича (21). Усложнена также динамика модели.
Агенты распределяют свои наличные ресурсы между несколькими отраслями "потребления”, то есть средствами реализации ресурсов, приводящими к получению полезности в условиях конкурентного взаимодействия, и несколькими отраслями "производства”, то есть средствами накопления ресурсов — банками, или иными средствами сбережения капиталов, определяющими наличные ресурсы на следующем этапе процесса. Полезность, получаемая каждым агентом от данной отрасли "потребления”, возрастает при увеличении количества его собственных направленных в эту отрасль ресурсов и убывает при увеличении вкладов партнеров в эту отрасль. Таким образом, в этой модели "потребление" конкурентно, что особенно естественно, если потребление трактуется как рыночная продажа ресурсов. Мы полагаем, что на рынке возникает общая для всех участников рынка цена единицы ресурса. Эта цена убывает при возрастании вклада в потребление каждого из агентов.
Конечной целью агента является максимизация дисконтированной суммы его одношаговых индивидуальных полезностей. Такие модели естественно представляются как динамические стохастические бескоалиционные игры.
В качестве решения для такой игры, мы используем концепцию "абсолютной" ситуации равновесия.
Глава 3 построена следующим образом:
В разделе 1 излагаются основные факты теории стохастических игр с суммарным дисконтированным выигрышем. Определяются "абсолютные" ситуации равновесия по Нэшу для таких игр, то есть устойчивые относительно подыгр ситуации равновесия (см. книгу Харшаиьи, Зсль-теи [61], а также учебник Петросяна, Зенкевича, Семиной [31]. Показывается, что выигрыши игроков в "абсолютной" ситуации равновесия должны удовлетворять уравнениям оптимальности, выражающим принцип динамического программирования в игровой формулировке.
Здесь же дается формализованное описание достаточно общей многошаговой стохастической модели распределения ресурсов с т участии-
нам». Такал модель с одной отраслью потребления и с одним средством накопления ресурсов задастся следующими элементами:
s(l)f t = 1,2,... — марковская цепь с конечным или счетным пространством состоянии 5 и с матрицей переходных вероятностен р(з,з'), где пространство состояний S может быть истолковано как множество возможных внешних случайных факторов, например, состояний природы, технологических нововведении и т.п.;
Fj(yi, 5), i G / — набор производственных функций всех игроков;
s), 1 € / — набор индивидуальных функций полезности всех игроков, где z — с|,...,Zjn — вектор ресурсов, направленных всеми игроками на потребление.
В разделе 2 строятся решения для однородных моделей распределения ресурсов между потреблением и производством с одним участником. В рассматриваемых моделях потребление имеет степенную функцию полезности, а производство определяется мультипликативной стохастической производственной функцией. Мы называем такие модели распределения ресурсов "однородными моделями”. Именно свойство однородности позволяет выписать в явном виде рекуррентные соотношения, определяющие решения уравнений оптимальности.
В разделе 3 разрабатываются игровые пропорционально-однородные модели распределения ресурсов между потреблением и производством с одной отраслью потребления и производства. В этих моделях производство определяется мультипликативными стохастическими производственными функциями с единым для всех агентов случайным коэффициентом выпуска b(s): F,(tji,s) = b[s) • у„ i G /.
Вектор полезностей, получаемых всеми агентами, пропорционален вектору потребляемых ресурсов с единым для всех агентов коэффициентом пропорциональности (ценой) c(c,s), являющимся однородной функцией порядка ß — 1 от z, где 0 < ß < 1: «,(2,3) = с(с,з) • г,-,1 G /.
Доходы, получаемые игроками, однородны с показателем однородности ß. В частности, если ресурсы всех игроков, кроме игрока /, равны нулю, то получаемая нм полезность равна а($) • cf.
Предлагается также дополнительная аргументация, мотивирующая рассмотрение именно "пропорционально-однородных” функций полезности. В модели может быть предусмотрен учет социальных показателей. Эти показатели оцениваются с помощью агрегирующей функции, сопоставляющей каждому вектору индивидуальных показателей всех участников некоторый неотрицательный сводный индекс. Агрегирующая функция явля-
ется однородной и выпуклой. Это может быть сумма индивидуальных показателей, или 1Р-норма, где р> 1.
Для заданной агрегирующей функции и при предположении, что общественная полезность вектора индивидуальных потреблении является экспоненциальной функцией соответствующего ему общественного потребления с показателем из интервала (0,1), мы получаем, что рыночная цепа единицы ресурса равна удельной полезности на единицу общественного ресурса вложенного в потребление.
Рассматривая динамику социальных показателей, мы получаем многошаговую стохастическую модель распределения ресурсов для одного агента, ’’встроенную” в исходную игровую модель. Мы полагаем, что общественные показатели также должны быть принимаемы во внимание при выборе ситуации равновесия, являющейся решением изначальной игровой задачи.
Теорема 3.3.1. Для конечного интервала планирования игра Г(£,5,Т) имеет единственную абсолютную ситуацию равновесия, для которой выигрыши игроков имеют вид г,(х, 5,Т) = шт($) * с(х) • аг,\
Здесь коэффициент = «(•$)> я последующие коэффициенты №г(л)
определл ют ся рс куррент ним и соотношсн иями
шТ(з) = (ШУ/1'Р+ (АЕ[(6МЯ £
У€5
Равновесные стратегии предписывают каждому игроку вкладывать в потребление иа шаге £ долю ресурсов, зависящую от числа оставшихся шагов Т — < и равную
Рассмотрение игр с бесконечным горизонтом планирования Г(Г, 5, оо) осмыслено только в случае, если последовательность векторов хот ограничена, так как в противном случае выигрыши игроков в таких играх оказываются неограниченными.
Теорема 3.3.2. Пусть возрастающая последовательность Шт ограничена. Тогда игра Г(х,5,оо) имеет единственную абсолютную ситуацию равновесия. Выигрыши игроков имеют вид о,(х, $,оо) = №«>(7,«) • .т^ где вектор коэффициентов опредслясупся соотношениями Тд^ = Нтт-юо^г* Стационарная оптимальная стратегия предписывает каждому игроку иа каждом шаге вкладывать в потребление долю ресурсов, зависящую