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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КООПЕРАТИВНЫЕ СТОХАСТИЧЕСКИЕ

Специальность 01.01.09 — .дискретная математика, и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических паук

Баранова Елена Михайловна

ИГРЫ

2006 г.

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

Научный руководитель: доктор физико-математических наук,

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

профессор Печерский Сергей Львович

кандидат физико-математических наук, доцент Зенкевич Николай Анатольевич

Ведущая организация: Институт прикладных математических

исследований КарНЦ РАН (г. Петрозаводск)

Защита состоится " 2006 г. в час. па заседании дис-

сертационного совета К-212.232.07 по защите диссертаций на соискание ученой степени кандидата фпзпко-математпческих наук при Санкт-Петербургском государственном университете по адресу: 190004, Санкт-Петербург. В.О.; Средний пр., д. 41/43, ауд. S/J.

С диссертацией можно ознакомиться в библиотеке СПбГУ им. A.M. Горького но адресу: С.Петербург, Университетская наб., 7/9.

Автореферат разослан 11 2006 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

В. Ф. Горьковой

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

В развитие теории стохастических игр свои вклад в различное время внесли В.А. Гурвич, П. Дутта, А.Н. Ляпунов. Дж.Ф. Мертенс, А. Нейман. А.Дж. Ори, Т. Партхасаратхи, Р.Дж.А.П. Питере, Т.Е.С. Рагхаван, М.Дж. Собел, Дж.А. Фи-лар, A.M. Финк.

Подавляющее большинство работ, касающихся кооперативных игр, относится к так называемым статическим или однократным играм. В этом случае при определении кооперативной игры изначально предполагается, что игроки перед началом игры договариваются о выборе набора стратегий, максимизирующих суммарный выигрыш игроков. Такой же подход был применен и при исследовании кооперативных динамических и дифференциальных игр Петросяном Л.А., Даниловым H.H., Захаровым В.В. Однако, при рассмотрении <;тохах:тичсч:ких игр нельзя творить о максимизации суммарного выигрыша, поскольку ситуация в чистых стратегиях в стохастической игре ие определяет однозначно выигрыши игроков, а определяет однозначно лишь их математическое ожидание, так как ситуация в чистых стратегиях порождает вероятностную меру на партиях, вдоль которых происходит

развитие игрового процесса. Именно поэтому при построении кооперативной стохастической игры изначально предполагается, что игроки выбирают такой набор (ситуацию н чистых стратегиях поведения), который максимизирует математическое ожидание суммы выигрышей игроков. Указанный набор стратегий (кооперативное решение) порождает некоторое поддерево, которое в диссертации называется кооперативным поддеревом. Здесь, так же, как и в детерминированных динамических и дифференциальных играх, возникает проблема, вполне аналогичная проблеме динамической устойчивости или состоятельности во времени рассматриваемых кооперативных принципов оптимальности, которая впервые была исследована Л.А. Петросяном. Важность введенного Л.А. Петросяном понятия очевидна, поскольку невыполнение условия динамической устойчивости решения делает невозможным реальное применение его в динамической кооперативной игре. К сожалению, многие1 решении — дележи из классической кооперативной теории — оказываются динамически неустойчивыми или позиционно несостоятельными.

Содержательный смысл этой проблемы состоит в том, что, как оказалось, в подавляющем большинстве случаев оптимальное решение, игры, выбранное в соответствии с некоторым кооперативным принципом оптимальности (ядро, NА1-регггение, вектор II Тепли и др.) в начале" стохастической игры, может потерять свою оптимальность в некоторой подыгре, развивающейся из начального состояния на кооперативном поддереве. Последнее обстоятельство может привести к желанию пересмотра первоначально выбранного кооперативного решения и, в результате, к нарушению устойчивости всего процесса игры. Это и есть позиционная несостоятельность выбранного кооперативного принципа оптимальности. Здссь слсдуст отметить различие между временной несостоятельностью (динамической неустойчивостью), введенной при исследовании детерминированных динамических и дифференциальных игр, н позиционной несостоятельностью. В детерминированных многошаговых и дифференциальных играх можно всегда ограничиться одной кооперативной траекторией (одним путем), вдоль которой происходит развитие игрового процесса, и суммарный выигрыш игрокез достигает своего максимального значения. Поэтому нарушение оптимальности выбранного решения оказывается опасным лишь в точках данного единственным образом выбранного кооперативного пути, что требует проверки условий сохранения свойства, оптимальности вдоль этого кооперативного пути, а поскольку кооперативный путь фиксирован, то на

временном интервале игры. Отсюда и термин временная несостоятельность или динамическая неустойчивость.

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

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

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

ции приведено несколько примеров, которые демонстрируют полученные результаты.

Основные положения, иыпосимыс па защиту:

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

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

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

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

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

Апробация работы. Основные результаты были доложены на Международном семинаре "Теория управления и теория обощеппых решений уравнений Га-мильтона-Якоби" (Екатеринбург, 2005), на Международном рабочем совещании "Задачи оптимальной остановки и стохастического управления" (Петрозаводск, 2005), на Международной конференции "Устойчивость и процессы управления"

(Санкт-Петербург, 2005), на "Fifth International ISDG Workshop" (Segovia, Spain,

2005), на "Summer School on (iaine Theory in Computer Science" (Aarhus, Denmark,

2006). на семинаре российско-финской летней школы "Динамические игры и многокритериальная оптимизация" (Петрозаводск, 2006), на семинаре Воронежской весенней математической школы "Понтрягинские чтения-XV" (Воронеж, 2004), семинарах кафедры математической теории игр и статистических решений, семинарах Центра теории игр, XXXIV научном конференции "111>оцсесы управления и устойчивость" (Санкт-Петербург, 2003).

Публикации работы. Материалы исследований опубликованы в [1—7]. Структура и объем работы. Диссертационная работа состоит из введения, двух глав, заключения, списка используемой литературы. Общий объел! диссертации 101 страница. Слисок используемой литературы включает (>Г> наименовал ия.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматривается кооперативная стохастическая игра п лиц в обл!,ем случае. Приводится постановка. задачи. Выведены функциональные уравнения для вычисления математического ожидания выигрышей игроков в стохастической игре и любой её подыгре. Описывается процесс построения характеристической функции как для стохастической игры, так и для любой её подыгры. Вводится понятие кооперативной процедуры распределения дележа, а также определение позиционной состоятельности решения. Приводится метод ¡хцуляриза.ции позицпонно несостоятельного дележа. В § 1.1 дается определение стохастической игры.

Определение 1 Стохастической игрой со случайной продолжительностью G{zq) (где Zq — начальная вершина древовидного графа G(mj)) называется система

), (1)

где N = {1,2, ...,п} — множество игроков, G(zo) = (Z, L) — конечный древовидный граф с начальной вершиной Zq, Г (г) — игровой элемент (одновременная

игра), заданный в вершине г, Г(,г) = {Ы, ..XК{,..., К*), где N — множество игроков, одинаковое для всех вершин 2 6 2; X* — множество стратегий «-го иг1юг<а,, г е N, А'?(х|,..., х*) — «функция вьrнгpыrFra. иг])ог<а г (г 6 М, х\ £ А'?). Предполагается, что К*(х\,..., ж*) ^ 0 для всех г £ Z и любого игрока г £ N.

Для каждой вершины г £ 2 в зависимости от ситуации х*, реализовавшейся в

игровом элементе Г(г), определены вероятности перехода в следующие вершины

у £ Ь{г) графа С(г0) , р(г, у;х\,..., х*п) = р(г, у, хг) ^ 0, £ р(г, у; хг) = 1, где

уеь(г)

р(г,у;хг) — вероятность того, что реализуется игровой элемент Г (у) (у €Е Ь(г)). если па предыдущем шаге (в одновременной игре Г(г)) реализовалась ситуация хг.

На каждом шаге к задана вероятность (¡к того, что игра закончится. О ^ % ^ 1. к = 0,— 1, ф = 1. где; I — длина, игры (под длиной игры понимается число шагов в максимальной партии игры); шаг к в вершине г € ¿Г в стохастической игре (7(го) определяется из условия г £ (Ь(го))к.

Стохастическая игра со случайной продолжительностью о) происходит следующим образом:

1) в вершине графа. С осуществляется одновременная игра, Г(^о), !густь в ней реализуется некоторая ситуация хг" £ Хгп, далее игра О(г0) либо прекращается с вероятностью <?1, 0 ^ <71 ^ 1, либо с вероятностью (1 — <71) продолжается и переходит в вершину у £ Ь{го) графа с вероятностью р{го, у; :г2"), зависящей от ситуации х*". реализовавшейся в игровом элементе Г(г0),

2) пусть на А>ом шаге игровой процесс находится в вершине г^ £ где задан игровой элемент Г(г^), и в Г(г^) реализуется ситуация х*к £ Х*к, далее игра либо закапчивается с вероятностью г/^, 0 ^ г/^ ^ 1, либо с вероятностью 1 — д^ продолжается н переходит в вершину графа 6 £(гд_.) с вероятностью г^-н; х*к).

Через О (г к) обозначена подыгра игры (7(г0), берущая начало в вершине х^ £ Z графа (с игрового элемента Г(г^)).

В § 1.2 получены основные функциональные уравнения для вычисления математического ожидания выигрышей игроков как для стохастической игры, так и для любой её подыгры. Пусть в стохастической игре со случайной продолжительностью С*(¿у) реализовалась последовательность ситуаций хг", х*1,..., хг', где хг" £ X20, х11 € X*1,..., хч £ X2', тогда, выигрыш г-го игрока определяется следу-

ющим ооразом:

, • У

ъы = XI ъ

3=0

Пс1-®)

)

(е^-(^)У

\т=0 /

Так как выигрыш оказывается случайной величиной, то рассматривается математическое ожидание выигрыша о). Величина Е^гг0) удовлетворяет функциональному уравнению

Е^0)=К?(х*°) + (1-д0) ]Г (р{ъ,у,х«№(у)), (2)

где Ег(у) — математическое ожидание выигрыша г-го игрока в подыгре О (у).

' Стратегия 7г4(-)

г-го игрока в игре — это правило, по которому для каждо-

го игрового элемента Г (г) (г £ 2) определяется, какую стратегию в одновременной игре Г(г) выбрать, 7Г;(г) = х\ € X* для всех гб

Пусть 2 € (¿(г0))Л, то есть игровой процесс на А>м шаге попадает в вершину г £ г?, тогда для математического ожидания выигрыша г-го игрока в подыгре С (г) справедлива формула

Е^) = Щ{х*) + {\-Як) Е (р(г,у,х*)Щу)).

В стохастической игре со случайной продолжительностью С (го) в качестве смешанных стратегий рассматриваются стратегии поведения г £ N. Тогда <£>(•) = (<р1(-),..., срп(-)) — ситуация в смешанных стратегиях поведения в стохастической игре С(га). Ситуация в подыгре О (г) обозначается через (¿>г(-) = (•),..., <^п('))-В кооперативной теории стратегии игроков используют лишь для нахождения кооперативного нути, то есть пути, который! максимизирует суммарный выигрыш игроков. В случае стохастических игр — это поддерево с заданными вероятностями перехода, на которых достигается максимум математического ожидания суммарного выигрыша игроков. Однако, максимум математического ожидания суммарною выигрыша игроков в классе смешанных стратегий поведения не превосходит максимум математического ожидания суммарного выигрыша игроков в классе чистых стратегий поведения, поэтому для нахождения кооперативного поведения в стохастической игре можно ограничиться классом чистых стратегий.

В § 1.3 строится кооперативный вариант стохастической игры, определяется характеристическая функция как для игры, так и для её любой подыгры. Даются определения дележа, -ядра, вектора Шепли, А^-ядра. ,

Через 7г(-) = (7Т1 (•),..., тгп(*)) обозначается ситуация в чистых стратегиях поведения в стохастической игре С (20)1 которая максимизирует сумму математических

Е ЪЫ

.гeN

. Такая ситуация назы-

ожядапнй выигрышей игроков г0) = тах вается кооперативным решением. .. .... .

С целью определения характеристической функции для кооперативной стохастической игры выписывается уравнение Беллмапа для максимума суммы математических ожиданий выигрышей игроков. Для определенности предполагается, что 2 е (Ь(га))к. Для подыгры С (г) (г 6 £) уравнение для вычисления максимума суммы математических ожиданий выигрышен игроков имеет вид:

*г) = ]Г А7(г») + (1 - «70 2 (р(г, у; у)) (3)

i£N уеЦг)

с начальным условием

\'(АГ, г) = « е {г : ¿(г) = 0} . (4)

¿С А' '

Ситуация 7Г(-) = (тгх(•),..., 7ТП(-)) в стохастической игре порождает вероятностное распределение на множестве 2 вершин графа С(го).

Определение 2 Подграф графа О(г^), который состоит из вершин г & 2 графа С (го), имеющих положительную вероятность реализации, порожденную кооперативным решением 7г(-), называется кооперативным поддеревом и обозначается через С(г0).

Множество вершин в подграфе С(го) обозначено через С 2 С Z.

Для определения кооперативной стохастической игры в каждой вершине 2 6 С2 определяется вспомогательная игра с нулевой суммой, которая обозначена через Оз[г). Это антагонистическая игра между коалицией Б С N (максимизирующий игрок) и коалицией N \ Б (минимизирующий игрок), где выигрыш коалиции 5 определяется как сумма выигрышей игроков, входящих в коалицию 5\ Значение характеристической функции г) задается как нижнее значение антагонистической игры Ст$(г) в чистых стратегиях (аналогично нижнему значению

матричной игры). Функция V(S,z) удовлетворяет функциональному уравнению

V(JS', z) — max min^

XS€XS XN\S^XN\S

(5)

yzL(z)

с начальным условием

V{S, z) = max , min £ z e (z : L(z) = 0> » (6)

's^s XN\S^JiN\S ieS

где игроки ?i, ?2,..., ?'fc 6 S, и ig = (xiLi ■ ■ ■' xik) — стратегия коалиции S, a Xg — J7 X*. — множество стратегий коалиции S, игроки ?fc+i,...,in образуют

j=Тл

коалицию A^S ({гьг2,..., ü} (JO'fe+ь • • •.= ^V), и xzN^s = {x*k+i,..., zfj — стратегия коалиции N\S, a = П -^ч* — множество стратегий коалиции

j=fc+l,n

N\S.

Для коалиции S = 0 значение характеристической функции V(S, z) равно 0. Характеристическая функция l/(SI, z), определяемая формулами (5), (6) суперад-дитивпа по S.

Определение 3 Кооперативной стохастической игрой со случайной продолжительностью G(zo), основанной на стохастической игре G(z0), называется пара (ЛГ, V(S, ^о)), где V(S, Zq) — характеристическая функция, определенная но формуле (3) с начальным условием (4) для коалиции N, по формуле (5) с начальным условием (6) для коалиции S ф 0 и для коалиции <S, = 0V(0,2O)=O.

В этом параграфе даются определения дележа £(zo)i множества дележей /(г0), решения С(г0), вектора Шепли Sh(z0), С-ядра Core(z0), TV-ядра N(zq) кооперативной стохастической игры G(zq).

Кооперативной подыгрой G(z), где z 6 Z, кооперативной стохастической игры G(zq), основанной на подыгре G(z) игры G(z0), называется пара (N,V(S, z)), где V(5', г) — характеристическая функция, определенная формулами (3), (4) для коалиции N, формулами (5), (6) для коалиции S ф 0 и для коалиции S" = 0

V(0,z) = 0.

Даются определения дележа £(г), множества дележей I(z), решения C(z), вектора Шепли Sh(z), С-ядра Core(z), TV-ядра N(z) кооперативной подыгры G{z).

Если C(zq) — решение кооперативной стохастической игры G(zq), то под решением C(z) кооперативной подыгры G{z) понимается решение, построенное по

тем же правилам, что и С(г0). То есть, если, например, С(гц) — это вектор Шепли для стохастической игры то С(г) — это вектор Шепли, вычисленный для

кооперативной иодыгры О(г).

В § 1.4 дается определение кооперативной процедуры распределения дележа.

Определение 4 Пскто]>-функция ¡3(г) = (/^(г),...,/3„(г)), где г € С2, называется кооперативной процедурой распределения дележа (КПРД) в вершине г, если

• ][>(*) = £ 7^(3^...,^), (7)

ieN гем

где ситуация (х^,..., ж*) — это ситуация в игровом элементе Г(г), реализовавшаяся при использовании игроками кооперативного решения ?г — (7Г1 (•),..., 7Г„ (■)).

Определение 5 Путем в многошаговой игре называется последовательность ситуаций хг",х21,..., х2', где хг* — ситуация, реализовавшаяся в игровом элементе

Г(^), * е Ць-г).

Пусть г е сг, иг€ (¿(го))'с. В любой кооперативной подыгре С (г) игрок может связать с отрезком пути Ж2, ху,... = Ш2'г/'"', реализовавшимся при кооиера-тивном решении л = (7Г!(-),...,7Гп(-)) (очевидно, что все г, у,... 6 СИ. так как СИ — множество вершин кооперативного поддерева, и ситуация тт фиксирована), случайную величину — сумму величин А (г), вычисленных вдоль этого отрезка пути хх'у'-. Предполагается, что игрок г на каждом шаге игры, то есть в каждой всртттинс пути, получает выплаты /З^у),____ Математическое ожидание

сумм таких выплат, посчитанных вдоль такого отрезка пути хх'у'— в кооперативной подыгре С?(г), обозначается через В^г). Величины Вг(г) удовлетворяют следующему функциональному уравнению

ад = &(*) + ( 1 - Чк) £ Оу; ДЫ) (8)

с начальным условием

#»(*) = &(г) для г е {г : Ь{г) = 0}. (9)

Пусть г € сг, у € Цг)псг, £(г) е С {г) С 1{г) и £(у) е С (у) С 1{у). Величина 7, (2) определяется из соотношения

Ш = + (1 - ?о у; (10)

уеЦг)

Лемма 1 Вектор 7(2) = (71 (г),..., ■уп(г)), определяемый уравнением (10), является кооперативной процедурой распределения дележа в вершине г £ CZ.

В § 1.5 дано и обосновано определение позиционной состоятельности дележа и решения. Игроки перед началом игры приходят к соглашению о кооперации, то есть договариваются максимизировать математическое ожидание суммарного выигрыша и рассчитывают получить дележ £(20) 6 С(г0). Развитию игры во времени соответствует движение вдоль вершин кооперативного поддерева С2. Так же как н в детерминированных играх в некоторый момент времени, в вершине 2, сумма, оставшихся выплат для игрока г может не совпадать с г-ой компонентой дележа из решення С (г) кооперативной подыгры С(г), являющеегося решением текущей игры, то есть подыгры С (г). Если это имеет место, то в данной вершине перед игроком г встанет вопрос о целесообразности придерживаться далее намеченного перед началом игры соглашения действовать "совместно оптимально", то есть игрок г может пожелать отклониться от кооперативного решения и получи ть больший выигрыш. Если такое отклонение будет выгодно хотя бы для одного игрока, то это и будет означать позиционную несостоятельность дележа £(го) € С {г 0) и, соответственно, самого движения вдоль путей кооперативного поддерева.

Определение б Дележ 6 С(г0) называется позпционно состоятельным в

кооперативной стохастической игре С {го), если для каждой вершины г € СЕ существует неотрицательная КПРД /3(г) — (/?х (г),..., Дг(г)) такая, что

6(*)=А(г) + (1-д*) (И)

уеЦг)

н

(12)

где £(у) — некоторый дележ, принадлежащий решению кооперативной подыгры

Щу).

Определение 7 Пудем говорить, что кооперативная стохастическая игра, со случайной продолжительностью С?(го) имеет позиционно состоятельное решение если являются позиционно состоятельными все дележи £ (гто) С С (го).

Если дележ £(гу) позиционно состоятелен в игре С(г0), то г-ая компонента КПРД (г = 1, гг.) может быть определена для всех г е С2Г, г ^ {г : Ь(г) — 0} по

формуле

Ш = Ш - (1 - qk) X р{г,у;х*)Ш, (13)

уеь(г)

а для г € {г : ¿(г) = 0} по формуле (12). Однако из (13) не следует, что в общем случае можно гарантировать неотрицательность /3¿(z) для вссх вершин z Е CZ и всех i Е N.

Лемма 2 Имеет место равенство Bi(z) = £i(z) для всех z Е CZ и всех i Е N.

Если выплаты игрокам производить не в соответствии с их выигрышами в игровых элементах, по ко торым проходит пу ть, а в соответствии с кооперативной процедурой распределения дележа /3(г), определенной формулами (11), (12) для всех г Е CZ, то математическое ожидание этих выплат будет совпадать с математическим ожиданием выбранного дележа из решения, что следует из Леммы 2. Предлагаемый способ реализации дележа обладает важным свойством: в каждой вершине пути игроки ориентируются на один и тот же "принцип оптимальности" и, в этом смысле, не имеют оснований для нарушения ранее принятого кооперативного поведения, то есть реализации кооперативного решения.

Для случаев, когда условие неотрицательности КПРД не выполняется, в § 1.6 предложен метод регуляризации дележа.

Для вссх вершин z Е CZ определяется новая КПРД но формуле

A(Z) = ^ V{N%z)-(14)

где £(z) = (£i(z),..., £n(z)) Е C(z), a.xz = (xf,..., x„) — это реализация кооперативного решения п в вершине z € CZ.

Определяется "новый" дележ в кооперативной подыгре G(z), где z Е OZ, на основе "старого" дележа как решение функционального уравнения £ Кг{х*)

Ш = А Ш + (1 - ®0 т, p(z> у; (15)

с начальным условием

£ Ki(xz)

для 2 € {z : L(z) = 0}.

Определяется новая характеристическая функция V(S,z) для каждой кооперативной подыгры G(z) для всех z € CZ, используя функциональное уравнение

Е i<i{xz)

...... pcj.(z)

с начальным условием

, ' í>(5, z) = z) для г е {г : L{z) = 0} . (18)

Функция V(S, z) суперадднтивна. Для всех познцнонно несостоятельных дележей £(z) 6 C(z), z G CZ, вычисляются регулярнзированные дележи £(z) и находится множество C(z) следующим образом:

Е A'¿(^2)

' C(z) = {{(z) : l(z) = 'у ' + (1 - %) £ p(z, у; £(г) е С {г)

с начальным условием

l(z) Ш для ze{z: L{z) = 0}}. (19)

Определение 8 Мпох<ество C{zq), определенное по формуле (19), называется регул яризованным решением кооперативной стохастической игры G(zq).

Теорема 1 Дележ £(z) = (£1(2),..., £n(z)), определенный по формуле (15) с начальным условием (16), является позиционно состоятельным дележом в кооперативной игре (N,V), где характеристическая функция V(S,z) задана функциональным уравнением (17) с начальным условием (18).

В § 1.6 рассмотрен частный случай, когда в качестве дележа игроками выбран вектор Шенли и С-ядро. § 1.7 содержит примеры построения и регуляризации решений в кооперативных стохастических играх.

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

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

Определение 9 Стохастической игрой С со случайной продолжительностью с конечным числом игровых элементов называется следующий набор

{Г'};ш1, <7,., Ы^)}^-^*) , (20)

где N — {1,... ,тг} — множество игроков, {Г1,..., Г4} — конечное множество игровых элементов (одновременных игр п лиц в нормальной форме) Г-7 = (М, Х(,..., К{,..., К^), ] — 1,..., р{г,э\х1) — вероятность того, что состоится одновременная игра Г-7, если на предыдущем шаге (в игровом элементе Г*) реализовалась *

ситуация хг [р(г,3',х1) ^ 0, хг) = 1), д (0 < д ^ 1) — вероятность оконча-

¿=1

ния игры на каждом шаге, 7Г = (7Г1,... , 7ГП) — вектор начального распределения вероятностей на множестве игровых элементов {Г1,..., Г'}, где -к^ — 1,..., £) — вероятность того, что перед началом игрового процесса " случай" выберет игровой элемент Г-1, который будет играться на первом шаге игры.

Стохастическая игра с конечным числом игровых элементов С? происходит следующим образом:

1) на нулевом шаге "случай" выбирает игровой элемент в соответствии с вероятностями, образующими вектор начального распределения вероятностей 7Г,

2) пусть на первом шаге стохастической игры (3, например, в игровом элементе

п . _

Г-7 реализуется ситуация х) € X* = П Х]к. Далее игра С? либо прекращается с

к=1

вероятностью д, 0 < д ^ 1, либо с вероятностью (1 — д) переходит па следующий шаг и так далее.

В § 2.2 получены основные функциональные уравнения для случая кооперативной игры с конечным числом'игровых элементов.

Для математического ожидания выигрыша г-го игрока, начиная с первого шага стохастической игры С. где, для определенности, будет происходить одновременная игра Г-7, будет верна формула-

• «

Е{ = Л7(.г') + (1 - д) X)рУ, (21)

/с=1

при условии, что в игровом элементе Г-7 реализовалась ситуация тР € X* = П Х3к.

Определение 10 Стратегия ?/»('), игрока г в игре называется стационарной, если выбор стратегии в каждом" игровом элементе из множества {Г1,..., Г'} на

каждом шаге зависит только от того, какой игровой элемент реализуется иа этом шаге, то есть

Г1г : Р е Х(,3 = М.

Так как описанная стохастическая игра С рассматривается в классе стационарных стратегий, определенных выше, и множество одновременных игр {Г1,..., Г'} конечно, то достаточно рассмотреть Ь подыгр игры С?, обозначенных Ст1,... , начинающихся с игровых элементов Г1, .. ., Г( соответственно.

Формируется матрица вероятностей перехода из одних игровых элементов в другие, которая зависит от ситуации в стационарных стратегиях //(■), реализовавшейся в стохастической игре С:

(р(1,1;®1) р( 2,1; ж2)

ПМО) =

р(2, Цх2)

(22)

\р(1,1;х*) ... р(1,Цх1))

где ту(-) = (гд (•),... ,г/п(.)), а тН(.) : тН{ Г1) = .т,1 е X},... = х\ е Х\, а

х* ~ (х{,..., х{ь) — ситуация, реализовавшаяся в игровом элементе

Для вычисления математического ожидания выигрыша г-го игрока в любой

подыгре стохастической игры О при реализации ситуации в чистых стационарных

стратегиях ?/(•) 6 П Е,, описанной выше, справедлива формула ieN

ЕМ')) = КМ')) + (1 - д)ПМ0) $(»;(•)), (23)

где £*(»/(•)) = • ■ •, Е*Ш))- Если <1е1(Я - (1 - <7)П(г;(-))) ф 0, то из (23)

получается

ЕМ')) = (Е - (1 - <7)П(г/(-)))-1 КМ-)). (24)

Для стохастической игры с конечным числом игровых элементов С? математическое ожидание выигрыша г-го игрока обозначается через Е^ ('/(')) 11 может быть найдено по формуле

ЕМ')) = «ЕМ')) = тг (Я - (1 - д)ПШ)ГУК*т)-

(25)

В § 2.3 построен кооперативный вариант стохастической игры с конечным числом игровых элементов. Через ?/(•) — (?71 (•),..., ?/„(•)) обозначается ситуация в

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

max ]Г^(г,(.)) = ^ВД(-)). (26)

Через V(N) обозначен вектор V(N) =

(^(iV),..., Vl(N)), где V'{N) - максимальный суммарный выигрыш коалиции N в подыгре G3. Если det(ü? — (1 — д)П(г/(-))) ф 0, то для значения V(N), уравнение Беллмана принимает вид:

V(N) = (Е-( 1 - <г)П(?/(.))Г1 £ ;(•))• (27)

i£N

Для стохастической игры G максимальный суммарный выигрыш коалиции N обозначается через V(N) и может быть найден по формуле

V(N) = irV(N) = тг (£ - (1 - д)ЩтШ'1 £ (28)

ieN

Для каждой подыгры G3 (j — l,i) стохастической игры G определяется значение характеристической функции для коалиции S таким же образом, как и в предыдущей главе.

Vj{S) = max min ]Г Е\ (Vs(•), r]NXS(•)), j = М- (2!))

чя(-) 4N\s(-) r^

Значение характеристической функпии для коалиции S для стохастической игры с конечным числом игровых элементов G обозначается через l/(Sr) и находится по формуле

V(S) = ttV{S). (30)

Определение 11 Кооперативной стохастической игрой с конечным числом игровых элементов, основанной на стохастической игре G, называется кооперативная игра G — {N, У), где N — это множество игроков, а V : S-> R — характеристическая функция, определенная формулами (28) и (30).

Определение 12 Кооперативной стохастической подыгрой с конечным число игровых элементов, основанной на стохастической подыгре G3, называется кооперативная игра if = (N, V), где N — это множество игроков, а V : S -> R —

характеристическая функция, определенная формулами (27) и (29).

Даны определения дележа а, решения С, вектора Шепли Sh — (Shi,..., Sl)n) в игре G, и дележа а?. решения С7', вектора Шепли Shj в подыгре С?.

Для п])0(:т<)тьг дальнейшего изложения считается, что С — вектор Шепли:

С = Sh = {Shi, ...,Shn} е 7.

Через Shi, г € N, обозначается вектор (Sh],..., Sh\). Д.!гя вычисления ?'-ой компоненты вектора Шепли Sh имеет место формула

Shi = тг Shi.

В § 2.4 даны определения кооперативной процедуры распределения дележа и вектора Шепли.

Определение 13 Вектор-фупкция — (¡3{,.. j = 1,..., t, называется ко-

оперативной процедурой распределения дележа (КПРД) в игровом элементе Г-7, если

ieN ieN

где выражение в правой части — суммарный выигрыш игроков в игровом элементе Г7, вычисленный при реализации кооперативного решения fj(-) в чистых стационарных стратегиях, удовлетворяющего условию (26), и такого, что Tj(rj) = х3.

Определение 14 Путем в кооперативной стохастической игре со случайной продолжительностью с конечным числом игровых элементов G называется последовательность реализовавшихся си туаций 5;( 1), ... ,x(j),..где x(j) — это ситуация, реализовавшаяся на jf-ом шаге игры.

Предполагается, что игрок г в подыгре Gt вдоль пути х-7 получает некоторые

выплаты — /3/_____Тогда в любой стохастической подыгре Сг игрок i может связать

с. путем, реализовавшимся в ситуации ?/(•) - (v/1(-),..., ??„(•))> случайную величину — сумму величин вычисленных вдоль этого пути. Математическое ожидание таких f3i, посчитанных вдоль пути в кооперативной подыгре С?, удовлетворяют следующему уравнению

А = (Е - (1 - 9)n(v(-)))_1A. (32)

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

в, = 7ТВ, = тг(Е - (1 - «^ГЩ.)))-^. (.4.4)

Вектор 7i = (7/,.. .,7') определяется из системы уравнений

Shi = Ъ + (1 - 9)П(г/(-))5/^. (:м)

Лемма 3 Вектор 7* = (7/,..., 7'), определяемый но формуле (34), состоит из

=1 =t

компонент КГТРД стохастических подыгр G ,..., G .

В § 2.5 дано определение и обоснование позиционной состоятельности вектора Шепли.

Определение 15 Вектор Шелли Sh — (Shi,..., Shn), Shi = irShi (i € N), называется позидионно состоятельным в игре G, если для каждого игрового элемента Г-7 (j — 1,..., t) существует неотрицательная КПРД /З-7 = (р{,..., pJn) такая, что

Shi = pi + (1 - <7)n(7K-))S7ii (35)

для любого i е N, где Shi = (Sh},..., Sh\), /?» = {/3},..., {%), где р( — это i - ый элемент КПРД в игровом элементе Tj(-) — кооперативное решение.

Если det(.£7 — (1 — <7)П(^(-))) ф 0, то формула, (35) принимает вид

Shi = (Е - (1 - (ЗОПФСО))-1/*. (36)

Уравнение (36) имеет единственное решение относительно Д, если det(Zv — (1 — g)n(i/(-))) ф 0. Получается формула для вычисления величин выплат /Зг:

А = (Е - (1 - <7)П(»7(.))№ (37)

В общем случае нельзя гарантировать неотрицательность элементов вектора pi = (Pi,..., pi), таким образом, невозможно гарантировать позиционную состоятельность вектора Шепли Sh в кооперативной стохастической игре G.

Лемма 4 Имеют место равенства Bi — Shi и ¿?» = Shi для всех i 6 N.

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

0 достаточном условии сохранения кооперации.

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

Теорема 2 Если для всех i £ N п для каждого игрового элемента Г7 (j — 1, t.) выполнены условия

А + (1 - д)Щг,{.)Щ ^ max {Л-») II *(•)) + (1 " 9)П(ч(0 II Vii'W ({г})} , (38)

то в стохастической игре G существует ситуация равновесия по 11эгпу с ожидаемым выигрышем г-го игрока, равным (?/(•)), i & N.

Левая часть неравенства (38) — математическое ожидание выигрыша г-го игрока при условии, что он и все остальные игроки придерживаются кооперативного поведения, и г-ый игрок получает выплаты ßi в соответствии с КIII'Д (см. (37)), правая часть неравенства — максимальный ожидаемый выигрыш г-го игрока, если в игровом элементе Г-7 огг использует стратегию х{ € Xf.

Следствие 1 Для выполнения неравенства (38) достаточно, чтобы для любого

1 Е N имело место неравенство

Ki{v{.)) - А < (1 - <7)(S/Cin - ((О)). (39)

где K'i(//(•)) — ( max /^/(х'Цх,1),..., max К\(хь||z-) ], a max К{(х'\\х{) — это максимальный выигрыш г-го игрока, получаемый при отклонении им от ситуации х\ которая является частью кооперативного поведения, то есть ситуация, соответствующая ситуации в чистых стационарных стратегиях ?/(•), удовлетворяющей

условию (26), а ситуация ?/(•) : 7/»(Г-7) = max Kjдля каждого j = 1,,.., t и

х{ех{

i е N,

Sh™in = (min Sh{,min Sh{) , Vmax ({»}) = (max Vi ({*}),..., max Vi ({¿}) ) . Vj=m j—i,t J \j=i,t j=i,t J

В § 2.7 полученные результаты продемонстрированы на численных примерах.

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ

РАБОТЫ:

1. Barancrva Е. М., Petrosjan L.A. Cooperative Stochastic Games in Stationary Strategies. Game theory and Applications. Nova Science Publishers, 2006, vol. 11, pp. 7-17, (вклад диссертанта 50%).

2. Баранова E. M., Петросяп Л. А. Кооперативные стохастические игры в классе стационарных стратегий. Сборник трудов международной конференции "Устойчивость и процессы управления", СПб: СПбГУ, НИИ ВМ и ПУ, 2005, Т.1, с. 495-503, (вклад диссертанта 50%).

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

4. Баранова Е. М. Условие Д.В.К. Янга для стохастических кооперативных игр. Тезисы докладов международного рабочего совещания "Задачи оптимальной остановки и стохастического управления", Петрозаводск: Институт прикладных математических исследований Карельского научн. центра РАН, 2005, с. 8.

5. Петросян J1. Л., Баранова. K.M., Шевкопляс Е. В. Многошаговые, кооперативные игры со случайной продолжительностью. Сборник науч. трудов "Оптимальное управление и дифференциальные игры" в Тр. Инст. мат-ки и мех-ки, Екатеринбург: Изд-во УрО РАН, 2004, Т. 10, N 2, с. 116-130, (вклад диссертанта 40%).

6. 1 Баранова Е. Л1. Многошаговые стохаспшчсскиа игры со случаи;ньш временем окончания. "Современные методы теории краевых задач." Материалы Воронежской весенней математической школы "Понтрягипские чтения - XV". Воронеж: Изд-во Воронежского госуниверситета, 2004, с. 22—23.

7. Баранова Е. М., Петросян Л. А. Стохастические игры со случайной продолжительностью. Труды XXXIV научной конференции аспирантов и студентов "Процессы управления и устойчивость", СПб: Изд-во С.-Петербургского унив-та, 2003, с. 456-462, (вклад диссертанта 50%).

Подписано в печать 18.09.20Об. Формат бумаги 60 х 84 1/16. Бумага офсетная. Печать ризографическая. Усл. печ. л. 1,0. Тираж 100 экз. Заказ 3847.

Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр.26

Введение.

Глава 1. Кооперативная стохастическая игра со случайной продолжительностью.1G

§ 1.1 Определение стохастической игры со случайной продолжительностью.

§1.2 Основные функциональные уравнения для стохастической игры со случайной продолжительностью.

§ 1.3 Построение кооперативной стохастической игры со случайной продолжительностью. Определение С-ядра, вектора

Шепли, iV-ядра.

§ 1.4 Кооперативная процедура распределения дележа.

§1.5 Позициониая состоятельность решения кооперативной стохастической игры со случайной продолжительностью.

§ 1.6 Регуляризация дележей.

§ 1.7 Регуляризация вектора Шепли и С-ядра.

§ 1.8 Примеры построения и регуляризации решений в кооперативных стохастических играх.

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

§2.1 Определение стохастической игры с конечным числом игровых элементов.

§ 2.2 Основные функциональные уравнения для стохастической игры с конечным числом игровых элементов.

§2.3 Кооперативная стохастическая игра с конечным числом игровых элементов.

§ 2.4 Процедура распределения дележа и вектора Шепли.

§ 2.5 Позиционная состоятельность вектора Шепли.

§ 2.6 Условие сохранения кооперации в кооперативной стохастической игре с конечным числом игровых элементов.

§ 2.7 Примеры построения решений в кооперативных стохастических играх с конечным числом игровых элементов

Актуальность темы. Стохастические игры представляют собой бурно развивающийся раздел теории игр, поскольку с их помощью удастся создать адекватные реальности модели в области страхования, охраны окружающей среды и экономики. В частности, недавняя работа Р. Ами-ра [30] посвящена моделированию с помощью теории стохастических игр экономических задач, работа [63] — моделированию задач страхования, а работы [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]) или состоятельности во времени рассматриваемых кооперативных принципов оптимальности.

Содержательный смысл этой проблемы состоит в том, что, как оказалось, в подавляющем большинстве случаев оптимальное решение игры, выбранное в соответствии с некоторым кооперативным принципом оптимальности (ядро, JVM-рсшение, вектор Шепли и др.) в начале стохастической игры, может потерять свою оптимальность в некоторой подыг-ре, развивающейся из начального состояния па кооперативном поддереве. Последнее обстоятельство может привести к желанию пересмотра первоначально выбранного кооперативного решения и, в результате, к нарушению устойчивости всего процесса игры. Это и есть позиционная несостоятельность выбранного кооперативного принципа оптимальности. Здесь следует отмстить различие между термином временная несостоятельность (динамическая неустойчивость), введенного при исследовании детерминированных динамических и дифференциальных игр (см. [21, 25, 26, 58, 59]) и нового термина позиционной несостоятельности. В детерминированных многошаговых (см. [12]) и дифференциальных (см. [18, 59, 64, G5]) играх можно всегда ограничиться одной кооперативной траекторией (одним путем), вдоль которой происходит развитие игрового процесса, и суммарный выигрыш игроков достигает своего максимального значения. Поэтому нарушение оптимальности выбранного решения оказывается опасным лишь в точках данного единственным образом выбранного кооперативного пути, что требует проверки условий сохранения свойства оптимальности на временном интервале игры вдоль этого кооперативного пути, а поскольку кооперативный путь фиксирован, то па временном интервале игры. Отсюда и термин временная несостоятельность или динамическая неустойчивость.

Понятие динамической устойчивости было впервые введено и исследовано JI.A. Петросяиом в работах [16, 17]. Важность введенного JI.A. Петросяном понятия очевидна, поскольку невыполнение условия динамической устойчивости решения делает невозможным реальное применение его в динамической кооперативной игре. К сожалению, многие решения — дележи из классической кооперативной теории — оказываются динамически неустойчивыми или позиционно несостоятельными.

Актуальность выбранной темы подтверждает и вручение Нобелевской премии по экономике в 2004 году Эдварду Прескотту и Финну Кидланду за работу [50] о несостоятельности оптимальных планов и возможных проблем в области политической экономии, возникающих в связи с этим.

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты были представлены на Международном семинаре "Теория управления и теория обощенных решений уравнений Гамильтопа-Якоби" (Екатеринбург, 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].

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

Заключение

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

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

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

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

1. Баранова Е. М., Петросян JI. А. Стохастические игры со случайной продолжительностью // Труды XXXIV научной конференции аспирантов и студентов "Процессы управления и устойчивость", СПб: Изд-во С.-Петербургского упив-та, 2003, с.456-462.

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

3. Баранова Е. М., Петросян JI.A. Кооперативные стохастические игры в стационарных стратегиях // Сборник трудов международной конференции "Устойчивость и процессы управления", СПб: СПбГУ, НИИ ВМ и ПУ, 2005, Т.1, с. 495-503.

4. Беллмап Р. Динамическое программирование. М.: Изд-во иностр. лит-ры, 1960, 400 с.

5. Берж К. Теория графов и её применения. М.: Изд-во иностр. лит-ры, 1962, 320 с.

6. Вилкас Э.Й. Оптимальность в играх и решениях. М.: Наука, 1990, 256 с.

7. Воробьев Н. Н. Устойчивые ситуации в коалиционных играх // Доклады АН СССР, 1960, Т. 131, с. 493-495.

8. Воробьев Н.Н. Коалиционные игры // "Теория вероятности и её применение", 1967, Т. 12, вып. 2, с. 289-306.

9. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985, 272 с.

10. Грауэр Л.В., Петросян Л. А. Многошаговые игры // Прикладная математика и механика, 2004, Т. 68, вып. 4, с. 667-677.

11. Данилов Н.Н. Связь между методом динамического программирования и принципом динамической устойчивости в кооперативных играх // Сборник научных трудов "Многошаговые иерархические, дифференциальные и кооперативные игры", Калинин, 1986, с. 7381.

12. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970, 272 с.

13. Нейман Д., Моргенштерп О. Теория игр и экономическое поведение. М.: Наука, 1970, 709 с.

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

15. Петросян Л. А. Решение неантагопистических игр // Тезисы докладов Всесоюзной конференции "Динамическое управление", Свердловск, 1979, с. 206-210.

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

17. Петросян JI. А., Данилов Н. Н. Кооперативные дифференциальные игры и их приложения. Томск: Изд. Томского ГУ, 1985, 276 с.

18. Петросян Л.А., Захаров В.В. Введение в математическую экологию. Л.: Изд. ЛГУ, 1986, 224 с.

19. Петросян Л. А., Зенкевич Н. А., Семина Е. А. Теория игр. М.: Высшая школа, 1998, 300 с.

20. Петросян Л. А., Кузютии Д. В. Игры в развернутой форме: оптимальность и устойчивость. СПб.: Изд-во С.-П. университета, 2000, 292 с.

21. Петросян Л. А., Томский Г. В. Динамические игры и их приложения. Л.: Изд-во ЛГУ, 1982, 252 с.

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

23. Печерский С. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы. СПб.: Изд-во Европ. унив-та в С.-Петербурге, 2004, 459 с.

24. Соболев А., И. Кооперативные игры // Проблемы кибернетики, М.: Наука, 1982, вып. 39, с. 201-222.

25. Чжун К. Л. Однородные цепи Маркова. М.: Мир, 1964, 426 с.

26. Amir R. Stochastic games in economics: The latter-theoretic approach // Stochastic Games and Applications in A. Neyrnan and S. Sorin (eds.)

27. NATO Science Series C, Mathematical and Physical Sciences, 2003, Vol. 570, Kluwer Academic Publishers, Dordrecht, Chapter 29, pp. 443-453.

28. Baranova E. M., Petrosjan L.A. Cooperative Stochastic Games in Stationary Strategies // Game theory and Applications, Nova Science Publishers, 200G, vol. 11, pp. 7-17.

29. Bellman R. Dynamic programming. Princeton: Princeton University Press, New Jersey, 1957.

30. Breton M. Algorithms for Stochastic Games in I.E.S. Raghavan, T.S. Ferguson, T. Parthasarathy and O.T. Vrieze (eds.) Stochastic Games and Related Topics, Series C: Game Theory, Mathematical Programming and Operation Research, 1991, pp. 45-57.

31. Driessen T., Muto S. ,Nakayama M. A cooperative Game of Information Trading: the Core, the Nucleolus and the Kernel // ZOR Methods and Models of Operations Research, Section "Theory", 1992, vol. 36, no 1, pp 55-72.

32. Dutta P. A Folk Theorem for Stochastic Games // Journal of Economic Theory, 1995, vol. 66, pp 1-32.

33. Ferguson T.S. Game Theory // http://www.math.ucla.edu/ torn / GameTheory/Contents.html.

34. Fink A.M. Equilibrium in a Stochastic n-person Game. // Journal of Science in Hiroshima University, Series AI, 1964, vol. 28, pp. 89-93.

35. Fisher R., Mirman L. The complete fish wars: biological and dynamic interactions // Journal of Environmental Economics and Management, 1996, vol. 30(1), pp. 34-42.

36. Flesch J., Thuijsman F., Vrieze 0. J. Optimality in different strategy classes of zero-sum stochastic games // Mathematical Methods of Operations Research, 2002, vol. 56, no 2, pp. 315-322.

37. Grauer L. V., Petrosjan L.A. Strong Nash Equilibrium in Multistage Games // International Game Theory Review, 2002, vol. 4(3), pp. 255264.

38. Haller H., Lagunoff R. Genericity and Markovian Behavior in Stochastic Games. // Econometrica, 2000, vol. 68, no. 5, pp. 1231-1248.

39. Herings P. J.-J., Peeters R.J. A. P. Stationary Equlibria in Stochastic Games: Structure, Selection, and Computation // Journal of Economic Theory, 2004, vol. 118, No. 1, pp. 32-60.

40. Jas'kiewicz A., Nowak A. On the optimality equation for zero-sum ergodic stochastic games // Mathematical Methods of Operations Research, 2001, vol. 54, no. 2, pp. 291-301.

41. Kohlberg E. On the Nucleolus of a Characteristic Function Game // SI AM Journal of Applied Mathematics, 1971, vol. 20 , pp. 62-66.

42. Kohlberg E. The Nucleolus as a Solution to a Minimization Problem // SIAM Journal of Applied Mathematics, 1972, vol. 23, no. 1, pp. 34-39.

43. Kronbak L. G. A coalition Game of the Baltic Sea Cod Fishery // http://www.sam.sdu.dk/ime/PDF/kronbak55.pdf.

44. Kuhn H. W. Extensive Games // Proceedings of National Academy of Sciences of the USA, 1950, vol. 36, pp. 570-576.

45. Kuhn H. W. Extensive Games and the Problem of Information // Annals of Mathematics Studies, 1953, no. 28, pp. 193-216.

46. Kydland F., Prescott E. Rules Rather than Discretion: The Inconsistency of Optimal Plans // Journal of Political Economy, 1977, vol. 85, pp. 473-491.

47. Maschler M., Peleg B., Shapley L. Geometrical Properties of the Kernel, Nucleolus and Related Solution Concepts // Mathematics of Operation Research, 1979, vol. 4, pp. 303-338.

48. Mathworks, 2005, http://www.mathworks.com.

49. Meinhardt H.I. Graphical Extensions of the Mathematica Package TU Games // http://library.wolfram.com/ infocenter/MathSource/5709/TuGames View3D.pdf.

50. Montero M. On the nucleolus as a Power Index // Homo Oeconomicus, 2005, vol. 22(4), pp. 551-567.

51. Najim K., Poznyak A. S., Gomez E. Adaptive policy for two finite Markov chains zero-sum stochastic game with unknown transition matrices and average payoffs // Automatica, 2001, vol. 37, no. 7, pp. 1007-1018.

52. Petrosjan L. A. Strongly time consistent optimality principles for the game with discount payoffs // System modelling and optimization, Lecture Notes in Control and Inform. Sci., Springer, London, 1994, no. 197, pp. 513-520.

53. Petrosjan L.A., Shevkoplyas E.V. Cooperative solutions for games with random duration // Game Theory and Applications, Nova Science Publishers, 2003, vol. 9, pp. 125-139.

54. Schmeidler D. The Nucleolus of a Characteristic Function game // SIAM Journal of Applied Mathematics, 1969, vol. 17, pp. 1163-1170.

55. Shapley L. S. Stochastic Games // Proceedings of National Academy of Sciences of the USA, 1953, vol. 39, pp. 1095-1100.

56. Shapley L.S. A Value for n-person Games // In H.W. Kuhn, A.W. Tucker, eds. Contributions to the theory of games II, Princeton: Princeton Univ. Press, pp. 307-317.

57. Suijs J., Waegenaere A., Borm P. Stochastic Cooperative Games in Insurance and Reinsurance // Insurance: Mathematics к Economics, 1998, vol. 22, no. 3, pp. 209-228.

58. Yeung D. W. K., Petrosyan L. A. Subgame consistent cooperative solutions in stochastic differential games // Journal of Optimization Theory and Applications, 2004, vol. 120, no. 3, pp. 651-666.

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