Содержание к диссертации
Введение
Глава 1. Кооперативная стохастическая игра со случайной продолжительностью 1G
1.1 Определение стохастической игры со случайной продолжительностью 16
1,2 Основные функциональные уравнения для стохастической игры со случайной продолжительностью 19
1.3 Построение кооперативной стохастической игры со случайной продолжительностью. Определение С-ядра, вектора Щепли, JV-ядра 21
1.4 Кооперативная процедура распределения дележа 29
1.5 Позиционная состоятельность решения кооперативной стохастической игры со случайной продолжительностью 31
1,6 Регуляризация дележей 35
1.7 Регуляризация вектора Шепли и С-ядра 39
1.8 Примеры построения и регуляризации решений в кооперативных стохастических играх 44
Глава 2. Кооперативная стохастическая игра со случайной продолжительностью с конечным числом игровых элементов 61
2.1 Определение стохастической игры с конечным числом игровых элементов 61
2.2 Основные функциональные уравнения для стохастической игры с конечным числом игровых элементов G4
2.3 Кооперативная стохастическая игра с конечным числом игровых элементов G7
2,4 Процедура распределения дележа и вектора Шепли 72
2,5 Позиционная состоятельность вектора Шепли 74
2.6 Условие сохранения кооперации в кооперативной стохастической игре с конечным числом игровых элементов 77
2.7 Примеры построения решений в кооперативных стохастических играх с конечным числом игровых элементов 81
Заключение 92
Литература
- Основные функциональные уравнения для стохастической игры со случайной продолжительностью
- Позиционная состоятельность решения кооперативной стохастической игры со случайной продолжительностью
- Основные функциональные уравнения для стохастической игры с конечным числом игровых элементов
- Позиционная состоятельность вектора Шепли
Введение к работе
Актуальность темы. Стохастические игры представляют собой бурно развивающийся раздел теории игр, поскольку с их помощью удастся создать адекватные реальности модели в области страхования, охраны окружающей среды и экономики. Б частности, недавняя работа Р. Ами-ра [30] посвящена моделированию с помощью теории стохастических игр экономических задач, работа [G3] — моделированию задач страхования, а работы [39, 47, 56] — моделированию задач охраны окружающей среды с использованием математического аппарата теории стохастических игр.
Впервые стохастические игры были рассмотрены Шепли (см. [61]). В этой работе Шепли описал антагонистическую стохастическую игру двух игроков, где использовал для решения классы стратегий поведения и стационарных стратегий. В этой же работе было доказано существование оптимальных стационарных стратегий поведения и выведено основное функциональное уравнение для значения стохастической игры. Это уравнение фактически явилось прямым обобщением уравнения Беллма-на (см. [6, 32]) для игровых динамических задач.
Стохастические игры представляют собой подкласс позиционных игр (игр в развернутой форме), определенных впервые в работах Г. Купа [48, 49]. На данный момент литература по стохастическим играм достаточно обширна, и в последнее время появилось множество работ, посвя-
щепных нсантагоїшстическим стохастическим играм (см. [33, 40, 44, 55]), а также нахождению равновесий по Нэшу в стохастических играх в различных классах стратегий (см, [41, 42]). Работы (см. [38, 43]) представляют исследование стохастических игр в классе стационарных стратегий, алгоритмы нахождения равновесия в классе стационарных стратегий. В работе [42] авторы исследуют стохастические игры в классе марковских стратегии, что "сближает" теорию стохастических игр с теорией цепей Маркова (см. [14, 29]).
Подавляющее большинство работ, касающихся кооперативных игр, относится к так называемым статическим или однократным играм. В этом случае при определении кооперативной игры изначально предполагается, что игроки перед началом игры договариваются о выборе набора стратегий, максимизирующих суммарный выигрыш игроков. Такой же подход может быть применен и при построении динамических и дифференциальных игр (см, [21, 26, 59]). Однако, при рассмотрении стохастических игр нельзя говорить о максимизации суммарного выигрыша, поскольку ситуация в чистых стратегиях в стохастической игре не определяет однозначно выигрыши игроков, а определяет однозначно лишь их математическое ожидание, так как ситуация в чистых стратегиях порождает вероятностную меру па партиях, вдоль которых происходит развитие игрового процесса. Именно поэтому при построении кооперативной стохастической игры мы изначально предполагаем, что игроки выбирают такой набор (ситуацию в чистых стратегиях поведения), который максимизирует математическое ожидание суммы выигрышей игроков. Указанный набор стратегий (кооперативное решение) порождает некоторое поддерево, которое в диссертации назвается кооперативным поддеревом.
Здесь так же, как и в детерминированных динамических и дифференциальных играх, возникает проблема, вполне аналогичная проблеме динамической устойчивости (см. [13, 20, 22, 57]) или состоятельности во времени рассматриваемых кооперативных принципов оптимальности.
Содержательный смысл этой проблемы состоит с том, что, как оказалось, в подавляющем большинстве случаев оптимальное решение игры, выбранное в соответствии с некоторым кооперативным принципом оптимальности (ядро, NM-решение, вектор Шепли и др.) в начале стохастической игры, может потерять свою оптимальность в некоторой подыг-ре, развивающейся из начального состояния на кооперативном поддереве. Последнее обстоятельство может привести к желанию пересмотра первоначально выбранного кооперативного решения и, в результате, к нарушению устойчивости всего процесса игры. Это и есть позиционная несостоятельность выбранного кооперативного принципа оптимальности. Здесь следует отметить различие между термином временная несостоятельность (динамическая неустойчивость), введенного при исследовании детерминированных динамических и дифференциальных игр (ем. [21. 25, 26, 58, 59]) и нового термина позиционной несостоятельности. В детерминированных многошаговых (см. [12]) и дифференциальных (см. [18, 59, G4. С5[) играх можно всегда ограничиться одной коопе-ративной траекторией (одним путем), вдоль которой происходит развитие игрового процесса, и суммарный выигрыш игроков достигает своего максимального значения. Поэтому нарушение оптимальности выбранного решения оказывается опасным лишь в точках данного единственным образом выбранного кооперативного пути, что требует проверки условий сохранения свойства оптимальности на временном интервале игры
вдоль этого кооперативного пути, а поскольку кооперативный путь фиксирован, то на временном интервале игры. Отсюда и термин временная несостоятельность или динамическая неустойчивость.
Понятие динамической устойчивости было впервые введено и исследовано Л.А. Пстросяиом в работах [16, 17]. Важность введенного Л.А. Петросяном понятия очевидна, поскольку невыполнение условия динамической устойчивости решения делает невозможным реальное применение его в динамической кооперативной игре. К сожалению, многие решения — дележи из классической кооперативной теории — оказываются динамически неустойчивыми или позиционпо несостоятельными.
Актуальность выбранной темы подтверждает и вручение Нобелевской премии по экономике в 2004 году Эдварду Прескотту и Финну Кидланду за работу [50] о несостоятельности оптимальных планов и возможных проблем в области политической экономии, возникающих в связи с этим.
Целью диссертационной работы является построение теории кооперативных стохастических игр, исследование применимости решений классической (статической) кооперативной теории к решению кооперативных стохастических игр, проверка позиционной состоятельности классических решений, их регуляризацию с целью получения позиционпо состоятельных решений на основе предлагаемых в работе процедур распределения дележа, вывод основных функциональных уравнений для вычисления решений стохастических игр, соответствующих тому или иному принципу оптимальности, конкретизация полученных результатов для подкласса стохастических кооперативных игр с конечным числом игровых элементов.
Научная новизна работы. В работе впервые дана математическая
формализация кооперативной стохастической игры, выведены функциональные уравнения для вычисления процедуры распределения дележа. В пей получены условия позиционной состоятельности решения для класса кооперативных стохастических игр, рассмотренных как в общем случае, так и в случае наличии конечного числа игровых элементов. Предложен алгоритм построения "нового" позиционно состоятельного дележа на основе "старого", не являющегося таковым с использованием процедур распределения дележа. В диссертационной работе получены и обоснованы условия сохранения кооперации в течение игрового процесса для кооперативной стохастической игры с конечным числом игровых элементов, если игроки на каждом шаге получают выплаты ис в соответствии со своими выигрышами в одновременных играх (игровых элементах), а в соответствии с кооперативной процедурой распределения дележа. Выведены основные функциональные уравнения для определения кооперативных выигрышей и кооперативного поведения игроков.
Практическая ценность работы. Результаты, полученные в диссертационной работе, могуч1 быть положены в основу построения теории кооперативных стохастических игр. Практическая ценность работы определяется областью применения стохастических игр. Стохастические игры применяются при математическом моделировании экономических, социальных задач, задач страхования, а также задач охраны окружающей среды. Поэтому область применения полученных результатов можно оценить описанной областью применения стохастических игр, в которых имеет содержательный смысл кооперация игроков. В каждой главе диссертации приведено несколько примеров, которые демонстрируют полученные результаты.
Основные результатами, выносимые на защиту:
формализация кооперативной стохастической игры как в общем случае, так и в случае наличия конечного числа игровых элементов: в первом случае при нахождении решения используется класс стратегий поведения, а во втором случае — класс стационарных стратегий, что обусловлено структурой игры,
построение иозициошю состоятельного решения па основе процедуры распределения дележа в кооперативной стохастической игре, рассмотренной как в общем случае, так и в случае наличия конечного числа игровых элементов,
регуляризация кооперативных решений классической статической теории с целью получения на их основе "приемлемых" решений стохастической игры, а также построение "новой" неотрицательной процедуры распределения дележа в кооперативной стохастической игре со случайной продолжительностью и получение условий позиционной состоятельности решения для данного класса игр,
вывод функциональных уравнений для вычисления кооперативных выигрышей, кооперативного поведения, кооперативной процедуры распределения дележа, решения стохастической игры, соответствующего тому или иному принципу оптимальности классической кооперативной статической теории,
достаточные условия сохранения кооперации в течение игрового процесса кооперативной стохастической игры с конечным числом игровых элементов (то есть условий, которые позволяют исключить
индивидуальные отклонения игроков от кооперативного поведения с целью получения большего ожидаемого выигрыша).
Апробация работы. Основные результаты были представлены па Международном семинаре "Теория управления и теория обойденных решении уравнений Гамильтона-Якоби" (Екатеринбург, 2005), на Международном рабочем совещании "Задачи оптимальной остановки и стохастического управления" (Петрозаводск, 2005), па Международной конференции "Устойчивость и процессы управления" (Санкт-Петербург, 2005), па "Fifth International ISDG Workshop" (Segovia, Spain, 2005), па "Summer School on Game Theory in Computer Science" (Aarhus, Denmark, 2006), на семинаре российско-финской летней школы "Динамические игры и многокритериальная оптимизация" (Петрозаводск, 2006), па семинаре Воронежской весенней математической школы "Понтрягинские чтения-XV" (Воронеж, 2004), семинарах кафедры математической теории игр и статистических решений, семинарах Центра теории игр, XXXIV научной конференции "Процессы управления и устойчивость" (Санкт-Петербург, 2003).
По материалам диссертации опубликованы работы [1], [2], [3], [4], [5], [19], [31].
Структура и объем работы. Диссертация состоит из введения, двух глав, разбитых на параграфы, заключения и списка используемой литературы.
Первая глава посвящена кооперативной стохастической игре G(zq), рассмотренной із общем виде.
В 1.1 дается определение стохастической игры
G(z0) = (N, G{z0), {r(z)}zeZ, {qk}lk=o, {p(z, У\ %Z)}zeZ,yeL(z);x*eX*) ,
где Л' — {1,2, ...,тг} — множество игроков, G(zq) — конечный древовидный граф с начальной вершиной zq, [V(z)}zez — множество игровых элементов, {qkY^o — вероятности ( того, что игра закончится па шаге к, p(z,y;xz) — вероятность перехода из вершины z Є Z в следующую вершину tj при реализации в игровом элементе T(z) ситуации хг. В этом же параграфе дается описание игрового процесса.
В 1.2 выводятся основные функциональные уравнения для нахождения математического ожидания выигрыша г-го игрока E{{zq), которые фактически являются обобщением уравнения Беллмана для стохастических игр. Вводится определение стратегии поведения ipi(-) г-го игрока в стохастической игре G{zq). Для каждой подыгры G(z) стохастической игры 6'(го) стратегия определяется как усечение стратегии ^г(')- Максимум математического ожидания суммарного выигрыша игроков в классе смешанных стратегий поведения не превосходит максимум математического ожидания суммарного выигрыша игроков в классе чистых стратегий поведения, поэтому для нахождения кооперативного поведения в стохастической игре можно ограничиться классом чистых стратегий.
Кооперативный вариант игры G{zq) обозначен через G(zq) и строится на основе игры G(zq) в 1.3. Кооперативным решением 7г(-) называется ситуация в чистых стратегиях поведения в стохастической игре G(zq), которая максимизирует сумму математических ожиданий выигрышей игроков. В 1.3 выводятся функциональные уравнения для характеристической функции V(S, z) в виде уравнений Беллмана с заданными начальными условиями.
Кооперативной стохастической игрой со случайной продолжительностью G(zq), основанной на стохастической игре G(zq), называем пару
{N,V(S,zq)), где jV — множество игроков, V(S,zq) — характеристическая функция, определенная для подыгры G(zq). Даются определения дележа (^о), множества дележей I(zq), вектора Шепли Sh(zo), С-ядра Соге(гц), iV-ядра N(zq) кооперативной стохастической игры G(zq) и дележа (z), множества дележей I(z), вектора Шепли Sh(z), С-ядра Core(z), TV-ядра N(z) кооперативной подыгры G(z), где кооперативной подыгрой G(z), основанной на подыгре G(z) стохастической игры G(zq), будем называть пару (N,V{S,z)), где V(S,z) — характеристическая функция, определенная для подыгры G{z).
Определение кооперативной процедуры распределения дележа (КПРД) (3(z) — (3i(z),..., {3n(z)) в вершине z и способ сё построения приведены и 1.4, в этом параграфе доказана лемма, при доказательство которой описан способ построения КПРД для игры G(zq), если посчитаны компоненты дележа, вычисленного для каждой подыгры игры
В 1.5 дается определение и обоснование позиционной состоятельности решения.
Метод регуляризации позиционпо несостоятельного дележа предложен в 1.6. Показано, как построить регуляризованиое решение кооперативной стохастической игры G{zq) на основе уже имеющегося, не обязательно являющегося позициопно состоятельным.
В 1.7 в качестве решения рассматриваются вектор Шепли и С-ядро, для этих классических решений применен метод регуляризации из I.G. Теоремы 2, 3, 4 доказывают, что "новое", построенное на основе "старого", решение является позиционпо состоятельным.
1.8 содержит примеры, где в качестве решения рассмотрены вектор
Щепли, С-ядро и jV-ядро.
Во второй главе рассматривается кооперативная стохастическая игра со случайной продолжительностью с конечным числом игровых элементов, которая определяется множеством игроков, конечным множеством игровых элементов, вероятностью окончания на каждом шаге, вероятностями перехода из одних игровых элементов и другие, вектором начального распределения вероятностей,
В 2.1 получены основные функциональные уравнения для случая кооперативной стохастической игры с конечным числом игровых элементов, дается определение стационарной стратегии 7/((-) г-го игрока, формируется матрица вероятностей перехода. Щг}(-)) при условии реализации ситуации в стационарных стратегиях г}(-).
В 2.3 рассматривается кооперативный вариант стохастической игры со случайной продолжительностью с конечным числом игровых элементов. Находится максимальный суммарный выигрыш в явном виде. Это и будет значение характеристической функции для коалиции Лг, вычисленное для кооперативной стохастической игры с конечным числом игровых элементов. Значение характеристической функции для коалиции S С N находится как нижнее значение антагонистической игры коалиции S, играющей против коалиции N\S. Сводится понятие дележа, решения, вектора Шелл и в стохастической кооперативной игре G и любой её подыгре.
Определение кооперативной процедуры распределения дележа дается в 2,4, С реализовавшимся путем связывается некоторая последовательность случайных величин, являющихся КПРД, математическое ожидание которых, вычисленное вдоль этого пути, обозначено через В. Нахо-
дится вектор Шспли для каждой подыгры игры G. В этом же параграфе диссертации доказана лемма, которая показывает связь вектора Шепли и КПРД. Для сохранения кооперации в игре G на каждом шаге игроки должны получать выигрыш в соответствии с тем принципом оптимальности, который был выбран ими а начале игры. Если это вектор Шепли, то выплаты г-му игроку в подыгре, начинающейся с шага к, должны быть г-о и компонентой вектора Шепли, рассчитанного для игры, начинающейся с /v-ro шага. Производя выплаты игрокам на протяжении игры в соответствии с их выигрышами в игровых элементах, нельзя гарантировать выполнения данного принципа.
В 2.5 дано определение и обоснование позиционной состоятельности вектора Шспли. Определение даст условие для проверки вектора Шепли на позиционную состоятельность. Математическое ожидание выплат г-му игроку в игре G в соответствии с КПРД равно математическому ожиданию г'-ой компоненты вектора Шепли, рассчитанного для игры G, что подтверждается леммой 4.
В 2.С приведено условие сохранения кооперации в стохастической игре с конечным числом игровых элементов, дано обоснование этого условия. Доказано следствие теоремы о достаточном условии сохранения кооперации. Под условием сохранения кооперации фактически понимается условие, при котором выигрыши игроков, полученные в результате кооперации, могут быть реализованы в некоторым образом построенном равновесии по Нэшу.
Заключение содержит в себе обзор полученных результатов.
В диссертационной работе использована тройная нумерация формул. Первая цифра означает номер главы, вторая - номер параграфа в главе,
третья - помер формулы в параграфе. Для теорем, определений, следствий, замечаний используется сквозная нумерация. Параграфы пронумерованы для каждой главы отдельно. Литература приведена в алфавитном порядке.
Основные функциональные уравнения для стохастической игры со случайной продолжительностью
Предположим, что в стохастической игре со случайной продолжительностью G(ZQ) реализовалась последовательность ситуаций xz,xzK... ,xZl, где xz» Є Xz\xz Є Xz\...,xZl Є XZl, zx Є L(z0), z2 Є L(zx), ..., z\ Є L(zi i), a L{z{) — 0. Тогда выигрыш г -го игрока определяется следующим образом: ( \п \ -1 ( Х Wo / / \ / ( J2Kf(x ")). \m=0 чт=0 J П (i - ») Так как игра имеет стохастическую структуру, то в качестве выигрыша необходимо рассматривать математическое ожидание выигрыша: Ek(zo) = Е (Кі(го)).
Математическое ожидание выигрыша г -го игрока Ei(za) удовлетворяет функциональному уравнению = / ( ) + (1-90) Р( .У; ) М. (1-2.1) где (у) — математическое ожидание выигрыша г-го игрока и подыгре G(y), начинающейся в вершине у Є Z, у Є L(ZQ), графа G(ZQ). Введем определение стратегии г-го игрока в стохастической игре со СЛучаЙПОИ прОДОЛЖИТеЛЫЮСТЫО G(ZQ), КОТОруЮ Обозначим ЧерСЗ 7Г;(-). TTJ( ) — это стратегия г-го игрока в игре (7( ), то есть правило, по которому для каждого игрового элемента T(z) (z Є Z) определяется, какую стратегию в игровом элементе Г(г) выбрать, щ(г) = х\ для всех z Є 2, а х\ Є Xf. Если 7г./(-) — стратегия г-го игрока в игре G(ZQ), ТО усечение этой стратегии, рассмотренное на подграфе G(z) графа G(ZQ), которое обозначим через 7if (), будет стратегией г-го игрока в подыгрс G(z) игры G(ZQ).
Пусть z Є (L{ZQ))\ ТО есть игровой процесс на к-м шаге попадает в вершину z Є Z. тогда для математического ожидания выигрыша г-го игрока в подыгре G(z) справедлива формула Ek(z) = ЯкЩх ) + (1 - qk) Kf{xz) + J2 К . )Ш yL(z) = Щ(хг) + (1-Як) piz x Eiiy). yeL(z)
В стохастической игре со случайной продолжительностью G(ZQ) В качестве смешанных стратегий игроков рассмотрим стратегии поведения (см. [48]).
Обозначим смешанную стратегию 7-го игрока в игре G(ZQ) через (pi(-), і Є Лг. Тогда ipf(-) — усечение стратегии (pi(-) па древовидный подграф G(z) и смешанная стратегия г-го игрока в подыгре G(z) (z Є Z), Тогда /?() — (tpi(-),...: рп(-)) — ситуация в смешанных стратегиях в стохастической игре G(ZQ). Ситуацией в подыгре G(z) назовем (рг(-) — В кооперативной теории стратегии игроков используют лишь для нахождения кооперативного пути, то есть пути, который максимизирует суммарный выигрыш игроков. В случае стохастических игр — это поддерево с заданными вероятностями перехода, на которых достигается максимум математического ожидания суммарного выигрыша игроков. Однако, максимум математического ожидания суммарного выигрыша игроков в классе смешанных стратегий поведения равен максимуму математического ожидания суммарного выигрыша игроков в классе чистых стратегий поведения, поэтому для нахождения кооперативного поведения в стохастической игре можно ограничиться классом чистых стратегий.
Построение кооперативной стохастической игры со случайной продолжительностью. Определение С-ядра, вектора Шепли, JV-ядра
Обозначим через тг(-) = (тГі( ),..., 7 (-)) ситуацию в чистых стратегиях поведения в стохастической игре G(ZQ), которая максимизирует сумму математических ожиданий выигрышей игроков
Назовем такую ситуацию кооперативным решением. Можем определить кооперативное решение для любой подыгры G(z), z Є Z, начинающейся с игрового элемента V[z).
Для определения кооперативного варианта стохастической игры необходимо определить характеристическую функцию для каждого подмножества S (коалиции) множества игроков Лг. Характеристическую фупк 22 цию, вычисленную для подыгры G(z) (z Є Z), обозначим через V(S,z), где S С N. Сначала найдем максимум суммарного выигрыша коалиции N в стохастической игре G(zo). С этой целью выпишем уравнение Беллмана (см. [32]) для максимума суммы математических ожиданий выигрышей игроков:
Ситуация в чистых стратегиях в стохастической игре G(ZQ) порождает вероятностные распределения на множестве Z нершип графа G(ZQ). Определение 2. Подграф графа G(ZQ), который состоит из вершин, z Є Z графа G{ZQ), имеющих положительную вероятность реализации, порооїсденную ситуацией тТ(-) (кооперативнъш решением), позо-вем кооперативным поддеревом и обозначим через G(ZQ),
Очевидно, что подграф G(ZQ) является конечным древовидным гра-(ром. Множество вершин в графе G(ZQ) обозначим через CZ С Z.
Определим кооперативную стохастическую игру со случайной продолжительностью, построенную на основе стохастической игры со случайной продолжительностью G(ZQ), описанной выше. Для этого, для каждой вершины z Є CZ определим вспомогательную игру с нулевой суммой, которую обозначим через Gs{z). Это антагонистическая игра между коалицией S С N, выступающей в качестве максимизирующего игрока, и коалицией N \S, выступающей в качестве минимизирующего игрока, где выигрыш коалиции S определяется как сумма выигрышей игроков, входящих в коалицию 5. Тогда значение характеристической функции V(S,z) зададим как нижнее значение антагонистической игры G${z) в чистых стратегиях (аналогично нижнему значению матричной игры),
Позиционная состоятельность решения кооперативной стохастической игры со случайной продолжительностью
Замечание 1. Если C(ZQ) СОСТОИТ более чем из одной точки, то в выборе дележа () есть неоднозначность. Выбрав определенный дележ () Є C(ZQ) И решив проверить его па позиционную состоятельность, необходимо проверить условие (1.5.1) сначала для вершины ZQ, ТО есть проверить существует ли неотрицательная КПРД J3{ZQ) — (PI(ZQ), ..., Pn(zt))), удовлетворяющая условию (1.5.1) для некоторого дележа (у) Є С(у), где у Є L(ZQ), поэтому существует некоторая неоднозначность в выборе дележа ,(у) С (у), по он в свою очередь должен быть также иозиционно состоятелен в кооперативной подыгрс G(y), то есть для него также должно выполняться условие (1.5.1), что уточняется в определении, когда говорится, что условие выполняется для всех z из множества вершин кооперативного поддерева.
Определение 11. Будем говорить, что кооперативная стохастическая игра со случайной продолоісительностью G{ZQ) имеет позициоппо состоятельное решение С (ZQ) , если являются иозиционно состоятельными все дслежм () Є C(ZQ).
Отсюда получаем, что если дележ (z0) позиционно состоятелен в игре G(ZQ), ТО КПРД может быть определена для всех z Є CZ и таких, что Z$L{Z\ L(Z) = 0} по формуле VL{z) а для z Є {z : L(z) — 0} по формуле (1.5.2). Однако из (1.5.3) следует, что в общем случае невозможно гарантировать неотрицательность /3;(г) для всех вершин z Є CZ.
Найдем значения величин В\{) для всех z Є CZ, то есть математические ожидания сумм j5{{z) из (1.5.1) и (1.5.2), z Є CZ, вдоль путей, реализовавшихся її кооперативной подыгрс G(z) игры G{ZQ) (вдоль путей подграфа G(ZQ)) при использовании игроками кооперативного решения Лемма 2. Имеет место равенство Bi{z) — &(z) для всех z Є CZ и всех і Є N. Доказательство Доказательство является очевидным и следует из того, что Bi(z) и i(z) удовлетворяют одним и тем же фупкцио пальным уравнениям (1.4,3) и (1.5.1) с одними и теми же начальными условиями (1.4.4) и (1.5.2).
Замечание 2. Если в определении 10 не требовать неотрицательности функций /?;(z), где z Є CZ, то все дележи, принадлежащие решению C(z), будут являться позициоипо состоятельными, когда решение C(z) ф 0, а это ограничение было наложено сразу после того, как было введено определение решения. Если выплаты игрокам производить не в соответствии с их выигрышами в игровых элементах, по которым проходит путь, а в соответствии с кооперативной процедурой распределения дележаP(z) — (Pi(z),... ,pn(z)), определенной формулами (1.5.1), (1.5.2) для всех z Є CZ, где Pi(z) — это выплата г-му игроку в вершине z Є CZ, то математическое ожидание всех выплат г-му игроку будет совпадать с математическим ожиданием г-ой компоненты выбранного игроками дележа из решения, что следует из Леммы 2. Таким образом, игроки могут пойти и на получение в каких-то вершинах отрицательных выплат, чтобы гарантировать сохранение коалиции на протяжении всей игры и получение компонент заранее выбранного дележа (ZQ), принадлежащего решению C(ZQ) кооперативной стохастической игры G(ZQ).
Предлагаемый способ реализации дележа обладает важным свойством: в каждой вершине пути игроки ориентируются на один и тот же "принцип оптимальности" и, в этом смысле, не имеют оснований для нарушения ранее принятого кооперативного поведения, то есть реализации кооперативного решения.
В случае, когда нельзя гарантировать неотрицательность Pi(z) для всех вершин z Є CZ, можно пойти по пути построения нового позиционно состоятельного решения па основе решения из классической теории кооперативных игр. Покажем, как это делается, когда в качестве решения рассматривается множество C(ZQ) С I{ZQ). Заметим, что данная процедура может быть применена для дележей, известных в классической статической кооперативной теории (С-ядро, iV-ядро, N М- решение (см. [15, 28]) и т.д.).
Для всех вершин z Є CZ определим новую КПРД по формуле ftw = ejv V(N,Z) - (L61) где ф) = (ft(z),..., e,n(z)) Є C(z), a xz = (xf,..., xzn) - реализация кооперативного решения 7Г = (7fi(-),... ,7f„(-)) в вершине z Є CZ, максимизирующего сумму математических ожиданий выигрышей игроков в стохастической игре G (zo), V(N,z) — значение характеристической функции для коалиции N, вычисленное для кооперативной иодыгры G(z). Поскольку Ki{xz) 0 для всех вершин z Є CZ и всех і Є N, то 8i{z) 0 для любой вершины z Є CZ. Из то, что 2 &(2) — - , ), и ieN из (1,6.1) следует также, что текущая выплата (3\{z) игроку і в игровом элементе T(z) должна быть пропорциональна г-ой компоненте дележа (z) Є C(z) в кооперативной подыгрс G(z) стохастической игры G(ZQ).
Основные функциональные уравнения для стохастической игры с конечным числом игровых элементов
Пусть задано конечное множество одновременных игр п лиц в нормальной форме (игровых элементов) {Г1,..., Г }: p = (N,xl...,xijq,...,Ki), где N - множество игроков, одинаковое для всех игр Р, j — 1,..., t, X? (і = 1,... , n) — множество стратегий і - го игрока в игре Р, Щ (х{,,,., xJn) — функции выигрыша і - го игрока в игре Р. Причем К 1(%{,..., х{J 0 для всех г Є N и любого j = 1,..., . Набор стратегий х3 — (х[,. ..)Х3п) называется ситуацией в игре Р. Предполагаем также, что множество стратегий каждого из игроков конечно для всех игровых элементов из множества {Г1,..., Г;}.
Для каждого игрового элемента Р, j = 1,...,, в зависимости от ситуации х3, реализовавшейся в этом игровом элементе, определены вероятности перехода в следующие игровые элементы Г1,..., Г ; p{j,k;x3) 0, і 2p(j,k;x3) = l, где p(j, к; х3) — вероятность того, что состоится одновременная игра Г , если на предыдущем шаге (в игровом элементе Т3) реализовалась ситуация х3 = (х[,...,х3п).
Задана вероятность окончания игры на каждом шаге — q (0 q 1). Также будем считать, что задан вектор 7Г = (7Гі,..., ттп) начального распределения вероятностей на множестве игровых элементов (Г1,..., Г(}, где TTJ (j = 1,,.., t) — вероятность того, что на "нулевом" шаге (то есть перед началом игрового процесса) "случай" выбирает игровой элемент Определение 15. Стохастической игрой G со случайной продолжи-телъпостъю с конечным числом игровых элементов называется следующий набор G=(N }U MM }jJab )- (2-1-1) Стохастическая игра с конечным числом игровых элементов G происходит следующим образом:
1) на нулевом шаге "случай" выбирает игровой элемент в соответствии с вероятностями, образующими вектор начального распределения вероятностей 7г. То есті), с вероятностью 7гі стохастическая игра с конечным числом игровых элементов G начнется с игрового элемента Г1, с вероят 63 ностыо 7Г2 — с игрового элемента Г2 и так далее. Пусть реализуется вероятность 7Г/, то есть "случай" выбрал игровой элемент Р Є {Г1,..., Гг},
2) пусть на первом шаге стохастической игры G в игровом элементе п Р реализуется ситуация х? ЄР- П Хгк. Далее стохастическая игра с конечным числом игровых элементов G либо прекращается с вероятностью ?, 0 q 1, либо с вероятностью (1 — q) переходит на следующий шаг.
3) па втором шаге игры G происходит одна из одновременных игр Г1,..., Tf с вероятностями p(j, 1; ),... ,p{j,t\x ) соответственно. На вто ром шаге игра G может прекратиться с вероятностью q, 0 q 1, либо с вероятностью (1 —q) переходит на третий шаг. Таким же образом стоха стическая игра с конечным числом игровых элементов G продолжается далее.
Подыгру стохастической игры с конечным числом игровых элементов, начинающуюся с к-го шага, обозначим через G(k).
Замечание 1. Стохастическая игра, рассматриваемая в данной главе, является частным случаем игры, представленной в первой главе, поскольку в данной постановке задачи предполагается, что множество игровых элементов конечно. Стохастическая игра с конечным числом игровых элементов G представляет собой конечный марковский процесс с вектором начального распределения 7Г, конечным множеством состояний {Г1,..., Г } и матрицей вероятностей перехода, которая будет сформирована ниже из элементов
Позиционная состоятельность вектора Шепли
Игроки перед началом игры договариваются о выборе набора стратегий, гарантирующего максимальный суммарный выигрыш и рассчитывают получить компоненты вектора Sh — {Shi, Shn), Shi — irShi. Развитию игры во времени соответствует движение вдоль некоторого пути X, который получается при реализации кооперативного решения rj(-). После первого шага игра переходит в новое состояние, являющееся начальным для подыгры, начинающейся со второго шага, то есть, фактически, игроки попадают в новую стохастическую игру, которая является подыг-рой игры G. Для сохранения кооперации на этом шаге игроки должны ожидать получение выигрышей в соответствии с вектором Шепли, рассчитанным для этой подыгры (фактически, рассчитанным для одной из =i =t нодыгр {G ,...,(3}). К сожалению, осуществляя выплаты на каждом шаге игры в соответствии с выигрышами в игровых элементах, реализовавшихся на этих шагах, невозможно добиться того, чтобы оставшиеся выплаты представляли собой компоненты вектора Шепли для подыгры, начинающейся с данного шага. Это и есть проявление позиционной несостоятельности вектора Шепли. Требуется перераспределять выигрыши игроков в каждом игровом элементе, чтобы позиционная несостоятельность вектора Шепли была преодолена.
Определение 25. Вектор Шепли Sh = (Shi, ,Shn), Shi = nShi (і Є N) назовем позициоппо состоятельным в стохастической игре G, если для каоїсдого игрового элемента Р (j = 1,..., і) существует неотрицательная КПРД j3J — (/3(,... ,/) такая, что 5/г. = А + (1- ?№()№ (2-5.1) для любого і Є N. Здесь Sh, - (Sh},...,Sh\), ft - (#,...,/) и 0j — это і - ый элемент кооперативной процедуры распределения делеоіса для игрового элемента Р, а П(т/(-)) — матрица вероятностей перехода, построенная согласно (2.2.2), a rj(-) — кооперативное решение, удовлетворяюгцее условию (2.3.1).
Если вектор Шепли позиционно состоятелен, то осуществляя на каждом шаге пути выплаты игрокам в соответствии с их КПРД, можно добиться того, чтобы эти выплаты были неотрицательными и чтобы математическое ожидание вектора Шепли, вычисленного для кооперативной стохастической подыгры G , (j = 1,...,і), совпадало бы с математическим ожиданием выигрышей, которые игрокам осталось получить в подыгре G стохастической игры G. Если det( — (1 - q)U(f}(-))) ф 0, то формула (2.5.1) будет иметь вид ЗЬ = (Е-(1-дЩг](-)))-1&- (2-5.2) Уравнение (2,5.2) имеет единственное решение относительно Д, если det(is— (1 — q)H(rj(-))) ф 0. Получаем формулу для вычисления величин выплат /ЗІ і - му игроку, і Є N: Pi = (E-{l q)m(-)))Sht. (2.5.3) В общем случае невозможно гарантировать неотрицательность элементов вектора Pi — (Д-,..., Д-), таким образом невозможно гарантировать позиционную состоятельность вектора Шепли Sh в кооперативной стохастической игре G. Лемма 4. Имеют место равенства B-i — Shi, ВІ = Shi для всех і Є N.
Доказательство.О Достаточно показать, что ВІ Shi, а из того, что Вг = 7гг и Shi = к Shi будет следовать второе равенство Леммы. Величины ВІ удовлетворяют уравнению (2.4.2), a Shi уравнению (2.5.2), то есть одинаковым уравнениям, следовательно, Лемма доказана.М Лемма 4 говорит о том, что математическое ожидание сумм Pi, рассчитанных вдоль пути х для подыгры G , j — 1,... ,, равное В\, где / представляет собой вектор выплат игроку і, производимых вдоль реализовавшегося пути х подыгры G , когда игроки придерживаются кооперативного решения 7/(-), равно математическому ожиданию выигрыша г-го игрока в этой подыгре (то есть г-ой компоненте вектора Ше-пли ShJ). Таким образом, представлен конструктивный способ построения реальных выплат игрокам па каждом шаге игры, причем, исходя из Леммы 4, можно утверждать, что игроки имеют смысл в перераспределении своих выигрышей, так как, получая /?/,..., $ в игровых элементах Г1,..., Vі соответственно, игрок і в игре G получит столько же (с точки зрения математического ожидания), сколько и планировал получить в начале игры (то есть Shi), и оставшиеся выплаты будут соответствовать тому же "принципу оптимальности" (в нашем случае, вектору Шепли). Это означает, что на каждом шаге игры G оставшиеся выплаты будут рассчитаны по тем же "правилам", что и в начале игры (в нашем случае, по аксиомам Шепли).
