Новые ситуации равновесия в стохастических играх

Грауэр, Лидия Вальтеровна

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

Грауэр, Лидия Вальтеровна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Санкт-Петербург МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Новые ситуации равновесия в стохастических играх»

Автореферат диссертации на тему "Новые ситуации равновесия в стохастических играх"

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

На правах рукописи

ГРАУЭР Лидия Вальтеровна

НОВЫЕ СИТУАЦИИ РАВНОВЕСИЯ В СТОХАСТИЧЕСКИХ ИГРАХ

Специальность 01.01 09 - дискретная математика и математическая кибернетика

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

Санкт-Петербург 2004 г.

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

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

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

профессор Жуковский Владислав Иосифович

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

Ведущая организация:

Саратовский государственный университет имени Н.Г. Чернышевского (г. Саратов)

"Л1" 2004 г. в

Защита состоится "/уу " уъг tyt-vn^ 2004 г. в /У час. на заседании диссертационного совета К-212.232.07 по защите диссертаций на соискание ученой степени кандидата физико-математических наук при Санкт- Петербургском государственном университете по адресу: 190004, Санкт-Петербург, 10-я линия В.О., д.ЗЗ, ауд._.

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

Автореферат разослан

«>М" eut7A$jL% 2004 г.

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

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

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

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

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

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

Основным принципом оптимальности в бескоалиционных играх является равновесие по Нэшу. Вопросу построения равновесий в динамических и дифференциальных играх посвящены многочисленные исследования отечественных и зарубежных авторов: Ауманна Р.Дж., Вайсмана К.С, Ван Дамме Е.Е.С., Воробьева Н.Н., Данилова Н.Н., Жуковского В.И., Захарова В.В., Зенкевича НА., Ка-ноненко А.Ф., Клейменова А.Ф., Кряжимского А.Б., Кузютина Д.В., Куна Г.В., Лагунова В.Н., Малафеева ОА, Мертенса Дж.Ф., Неймана А., Петросяна Л.А., Фуиджсмена Ф., Чистякова С.В.

В литературе по теории многошаговых и повторяющихся игр особое место занимают так называемые народные теоремы, из которых следует возможность построения Парето оптимальных равновесий по Нэшу с использованием стратегий наказания. Поскольку авторство этих теорем не определено, они получили название народных теорем. Идеология народных теорем встречается в работах Ауман-на Р.Дж., А. Вазина, К. Вена., О. Госснера, Е. Маскина, Л. Смита, Д. Фунденберга,

и ос. члционАльаяв

* -:'.jHJOTEi<A

Д. Эбрю.

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

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

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

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

существования регуляризации, в которой существует сильное трансферабельное равновесие.

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

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

1. построение и исследование новых классов равновесий по Нэшу в стохастических играх п лиц;

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

3. нахождение явных выражений для построенных равновесий для стохастических игр с постоянными вероятностями перехода;

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

Апробация работы. Результаты работы докладывались на 10-м международном симпозиуме по динамическим играм и приложениям ISDG 2002 (Санкт-Петербург), на XV конференции по теории игр и приложениям IMGTA (Урби-но, Италия), на XXXII научной конференции "Процессы управления и устойчивость" (Санкт-Петербург), на семинарах Центра теории игр при факультете ПМ-ПУ СПбГУ, на семинаре на Механико-математическом факультете Саратовского государственного университета имени Н.Г. Чернышевского (г. Саратов).

Публикации работы. Материалы исследований опубликованы в [1-6].

Структура и объем работы. Диссертационная работа состоит из введения, трех глав (8 параграфов), заключения, списка используемой литературы и 2 приложений. Общий объем диссертации 118 страниц. Список используемой литературы включает 57 наименований. Работа содержит 9 рисунков.

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

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

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

В § 1.1 приводятся постановка и основные определения. Рассматривается стохастическая игра я лиц с бесконечным числом шагов, представляющая собой набор 1 "игровых элементов" Г1, Г2,..., Г*. Каждый игровой элемент есть одновременная играп лиц в нормальной форме Г* = (Л/'; X*,... ,Х*; К*,...,К„) , А: = 1,2,...,£, где N = {1,... ,п} — множество игроков, одинаковое во всех игровых элементах; X* — множество чистых стратегий игрока « е /V, множества X*, к = 1,2,..., конечны; ..., г*) — функция выигрыша игрока г (г 6 Лг, г* е X*).

Наряду с чистыми стратегиями х* будем рассматривать смешанные ц*. Стратегии в одношаговых играх будем называть альтернативами.

Кроме того, для каждого игрового элемента Г*, к = 1,2.....определены

(

вероятности перехода ... = ртк{хк) > 0, г = Т7<, 0 < У.Р^Д*) < 1,

__Г=1

к — Вероятность перехода р£(х1) — условная вероятность появления игры Гг на следующем шаге при условии, что на данном шаге имеет место игра Г* и в игре Г* реализовался набор альтернатив I* € X*.

Рассмотрим бесконечный древовидный граф С = (2, V), где 2 — множество

вершин и Ь : 2 —> 22, Ь(г) = Ьг С 2, 2 е 2. Ьг — множество вершин, следующих за г. Пусть (начальная вершина го 6 2) — множество вершин, каждой из

которых соответствует одна из игр Г1, Г2,..Г':

Г{2) = (^; Х{.....Х'п;К1.....К*) = Г*.

Кроме того, предположим, что для каждой вершины ге2ие существует таких вершин ух 6 и т/2 € уI ф 1/2. что им соответствует одна и та же игра Г'. = 4 + 1 для всех г е 2. Множество 2 \ 2 С 2 — множество вершин окончания игры, т.е. Ьг = 0 для любой вершины 2 6 2\2. В вершинах г е 2\ 2 стохастическая игра заканчивается.

Пусть Г (г) = Г*, х" = хк, тогда вероятность перехода р(г, у; х*) из вершины гб^в вершину у £ Ьг определяется следующим образом

!р'к{хк), если вершине у сопоставлена Гг;

1-Х>1(х*), если у £ 2\2.

На дереве <2 = (2\ Ь) с помощью одновременных игр Г(г) и вероятностей перехода р(г, у, х') определим стохастическую игру С следующим образом. На первом шаге в начальной вершине гц € 2 происходит одновременная игра Г(го). Если в этой игре реализовался набор альтернатив х*°, тогда на следующем шаге с вероятностью р{го, у, х*°) произойдет игра Г(у), если у € Ьго П 2, или стохастическая игра закончится, если у £ ЬгаГ\(2\2). Если на шаге к происходила одновременная игра Г(гк_1) и в Г(г*_1) реализовался набор альтернатив х**-', то на следующем шаге с вероятностью р(г*_!, у; х"—1) произойдет игра Г (у), если у £ П2, или стохастическая игра закончится, если у е С\{2\ 2).

Определим понятие "истории" в игре С?. Рассмотрим вершину г* 6 2. Обозначим путь, соединяющий начальную вершину го с вершиной г*, через гд, 21,..., 2* и предположим, что до вершины г* реализовалась последовательность п-наборов чистых альтернатив х2", х'1,..., Iх*-'. Последовательность пар (20,1го), (21,г11),..., (2ц_1,х*'-') будем называть историей вершины г* и обозначать Л(г*).

В игре О игроки обладают полной информацией, в том смысле, что в каждой вершине 2 е 2 они знают одновременную игру Г(г), в которую играют, и каждый игрок помнит всю историю игры Н(г) = ((го,2*°), (21.x").....(гт_1,1*",-1)))

2 = 2т- Но ни один игрок не знает вероятностей выбора альтернатив (опреде-

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

Будем рассматривать три класса стратегий: стационарные стратегии (чистые ?/,(•) или смешанные £,(•)); марковские стратегии (чистые 7,(-) или смешанные А(0); стратегии поведения (чистые 7г,(-) или смешанные ?,(•)).

Так как переход от одной вершины к другой носит стохастический характер, то выигрыш игрока оказывается случайной величиной, поэтому будем рассматривать математическое ожидание выигрыша. Ожидаемый выигрыш игрока » в ситуации в смешанных стратегиях поведения q(■) = (91(-)| • • •) Чп{')) в стохастической игре С? равен

гег I *'

где К*{х') — выигрыш игрока г в ситуации т* в одношаговой игре Г(г), — вероятность появления ситуации х' в одношаговой игре Г (г), — вероятность

ожидание выигрыша (?(•)) игрока 1 конечно. Каждый игрок заинтересован в максимизации своего индивидуального выигрыша.

Для каждой вершины у е 2 рассмотрим подыгру С(у) игры С? (б = С(л0)), начинающуюся из вершины у и разыгрываемую на подграфе С (у) = Ь). Здесь — множество вершин подграфа С7(у). Вероятности перехода р(г/, г"; х' ) в игре <7(у) те же, что и в игре £?. Достаточно рассмотреть 4 подыгр, начинающихся с одной из одношаговых игр Г1,..., Г'. Обозначим эти подыгры соответственно б*,

Рассмотрим ситуацию в чистых стационарных стратегиях г}(-) = (т;1(-).....»&»('))>

такую, что 77,(г) = г* е X* для всех вершин г: Г(г) = Г*, I € N (г € 2, к = !,...,<). Составим для ситуации »?(•) матрицу перехода:

(1)

того, что стохастическая игра пройдет через вершину г € Ъ. Математическое

к = 1,4.

П(ч(0) =

(?}(*') Р?(х1) ... Р\(х1) \ р](*2) Р&2) ... Р^2)

выступающей в роли максимизирующего игрока, и коалицией N\S, выступающей

—1с

в роли минимизирующего игрока, построенная по структуре игры G . Выигрыш игрока 1 (коалиции S) определен как сумма выигрышей ее членов. Введем функции Vk(S) : 2N R, к = l,...,t. Определим значение функции Vk(S), S С N, как верхнее значение антагонистической игры Gs,n\s

V*(S)= min max^Ej(tjs[-),t]n\s{-)), * = M, Чг(-) = ЫОЪег-

Обозначим через rjs = (rjf,... ситуацию в чистых стационарных стратегиях: ijts(z) = zf* для Vz : Г(г) = Г*, доставляющую минимакс Vk{S).

В §1.2 строятся равновесия по Нзшу в стохастической игре с бесконечным числом шагов. В каждой одношаговой игре Г*, к = 1,..., i, фиксируем некоторую ситуацию хк G PJ X*, такую, что хотя бы для одного номера тк вероятность пере-

»€ЛГ

хода р];к(хк) > 0. Определим чистые стационарные стратегии ??,(•) игроков ia N в игре G следующим образом: тЦг) = xf ддяУг: Г(г) = Г*. Пусть множество Т = {(z, х2), z 6 Z).

Пусть вектор функций ^({j}) = {ЩШ}), • • •, такой, что

Л*({7»= max (äJ + ¿*4 - , fc=W. (2)

z* e x) L (=i J

Теорема 1 Предположим, что для всех j £ N выполнены следующие условия

ПЙ) • ад» S КМ. где КМ ± (К^х1),..., КЦх1))*. (3)

Тогда в стохастической игре G существует ситуация равновесия по Нэшу с ожидаемыми выигрышами игроков, равными j € N.

Пусть — ситуация равновесия в стационарных стратегиях в

антагонистической стохастической игре ^ = Причем совместная сме-

шанная стратегия коалиции N\j представима в виде fj^.(-) =

Тогда в качестве Vfc({j}) можно взять значение антагонистической игры G^) .

В § 1.3 строится регуляризация G стохастической игры G (используется механизм, предложенный JI.A. Петросяном). Выбирается дерево "кооперативных траекторий", вдоль которого происходит перераспредление суммарного выигрыша игроков, и на этой основе проводится регуляризация.

Фиксируем ситуацию в чистых стационарных стратегиях rj(-): 17(2) = хк для всех вершин г : Г(г) = Г*, к = 1,2,..., i, такую, что

V'(tf) = max £ = Е # й(0), к = 1.2,..., t.

Предположим, что для всех i 6 N Кк(хк) > 0, к = 1,..., t. Обозначим через Т — {(z,x*) : z € 2} дерево кооперативных траекторий. Рассмотрим векторы а* = (а*,а*)т 6 iZn, к = 1,2,...,t, такие, что

«¡=>0, i е N, fc = l,2,...,t. (4)

t eN i €W

Построим стохастическую игру (?„, которая отличается от игры G лишь значениями функций выигрыша в одношаговых играх вдоль дерева кооперативных траекторий. А именно заменим выигрыши в играх Гк следующим образом

ь t , ,, если х' — х*

КНх") = < ' k „

К*{х), если х ^ х .

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

Определим функции Я* : 2" —> R, k = 1,2.....t:

Rk(S) = 4 max (е^ (ífcH4) + ¿Pí (xk\\xks) V(S)1. (5) ^fcllies^; (.Jgs r=l J

Определение 1 Ситуация в стратегиях поведения q = (ft.....q„) называется

сильным трансферабельным равновесием в игре <5„, если для всех коалиций

s С N, s * 0, ££(«(■)) > EÉ> Ш1Ы-)) дая vte(.) = 6 njesOí-

1 €S «6S

Теорема 2 Пусть существуют векторы а* = (а*, а*, - - -. G Д", fc = 1,2,..., i,

удовлетворяющие (4), такие, что для всех к = 1.....t и всех S С ÍV, 5 ф 0,

выполнены следующие условия

ñ(fl).^(S)<i4(S), (6)

где = Л(5)= (е^Е^ — Е^ •

ves «es «es J

Тогда в регуляризации Ga существует сильное трансферабельное равновесие.

Пусть ситуация в стратегиях поведения ?(■) = (?!(•)>•••> ?»(•)) в игре 6а такая, что ' е* (2?) , ди V * 6 ^ : Г(г) = Г» и Л(») С Г; е.5* (я?*). если Э у € 2 до г € 1? и 5 С ЛГ, Я ? »:

*.(А(«)) =

Цу) С.Т,7?цф 5?3, {у, (х»||х|)) 6 Г; (?)

. произвольна в остальных случаях, где (х?) — смешанная стратегия игрока I в игре Г*, предписывающая выбор чистой альтернативы х* € с вероятностью 1; Г(у) — первая одношаговая игра из последовательности одношаговых игр Г(г0),..., Г(гт),..., Г(г), в которых существует коалиция 5 С такая, что г 5, а игроки $ отклоняются от х|; ef' (х^*) — смешанная стратегия игрока г в игре Г (г), предписывающая выбор чистой альтернативы х^ 6 X' с вероятностью 1.

Ситуация <?(•) = (91(01 • • • 19п(')) ~' сильное трансферабельное равновесие в Ол. Пусть (СКО'^яС')) — пара оптимальных стационарных стратегий в игре к = 1,...,4. Причем совместная смешанная стратегия коалиции

N \ в представима в виде = Тогда в качестве мож-

—^

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

из предыдущих вершин первой отклонилась коалиция Я, равновесные стратегии игроков г е N \ 5 предписывают следовать стратегиям

Следствие 1 Пусть выполняются условия теоремы 2, тогда в регуляризации (?„ существует сильное равновесие.

Достаточно заметить, что если ?(•) — ситуация сильного трансферабельного равновесия в игре <За, д(-) является сильным равновесием в ил.

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

Определение 2 Набор (Аг^слг чисел из [0,1] называется сбалансированным набором весов, если для каждого игрока г сумма по всем коалициям, содержащим », равна 1, т.е. ^ = 1, » € N.

Теорема 3 Пусть <? — стохастическая игра п лиц, на каждом шаге которой разыгрывается одна из двух игр, Гь Г5. Для того, чтобы существовала регуляризация С, в которой существует сильное трансферабельное равновесие, необходимо, чтобы выполнялись следующие условия

т>Ел^ к ^ (Е*;№)+Х>;^(5)1, * = 1,2,

вся хв^ЧгеаЛ1 г=1 )

для любого сбалансированного набора весов

Также в данной главе приводятся примеры, иллюстрирующие теоремы.

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

В § 2.1 рассматривается стохастическая игра п лиц, построенная на конечном древовидном графе б = (2, Ь). Каждой вершине г € 2 соответствует одновременная игра л лиц Г (г) = Х{,..., X*] К',..., К*), где N — {1,..., п} — множество игроков, одинаковое для всех вершин г 6 2, X* — множество чистых стратегий (альтернатив) игрока » £ К"(х[,х£) — функция выигрышаигро-ка i (х 6 ЛГ, х' 6 X"). Предположим, что игры Г (г), г € 2, конечны. Для каждой вершины ге2 определены вероятности перехода

Р(г, У, х\.....х'я)= р(г, у;х')>0, у £ Ь„ ]П р(2> У' х') =

УСЬш

Вероятность р(г, у; х') — вероятность перехода из вершины г 6 2 ъ вершину у&Ь, при условии, что в игре Г(г) реализовался набор альтернатив х' = {х\,..., х*). Полагаем р(г, у; х') = 0, если Ь, — 0.

На дереве б = (2, Ь) с помощью одношаговых игр Г{г) и вероятностей перехода р(г, у; х'), как и в случае стохастической игры с бесконечным числом шагов, строится стохастическая игра (7.

В игре <3 игроки обладают полной информацией, в том смысле, что в каждой вершине г £ 2 они знают одновременную игру Г(г), в которую играют, и каждый игрок помнит всю историю игры Л(г).

Ожидаемые выигрыши игроков 1 € N определяются аналогично случаю стохастических игр с бесконечным числом шагов.

Для каждой вершины у £ 2 рассмотрим подагры (?(у) стохастической игры С, начинающиеся в вершине у (£? = о)) и играемые на подграфе С (у) = (2У, Ь).

В § 2.2 для каждой подыгры С(г), г € ¿, строятся вспомогательные антагонистические стохастические игры з £ между игроком з и коалицией Рассмотрим функции У : N Я, г € 2. Определим значение функции как верхнее значение антагонистической игры (^^{^(г).

Т«\,()7,()

Обозначим через у3 = (Тп• • • >7«) ситуацию в чистых марковских стратегиях: ■у3, (г) = х3,', г 6 ¿Г, доставляющую минимакс

Через /З'(-) = (/3£(-),..., /3*(*)) обозначим ситуацию абсолютного равновесия в игре 5. Пусть Л С 2 — некоторое подмножество множества вершин, такое, что А Э {г € 2 : Ь, — 0}. Рассмотрим ситуацию в смешанных марковских стратегиях Р(') = (Д(-). • • •. Д»(0) следующего вида:

[ Д(г) = е'(хг), если г€2\А,

< удовлетворяющую условиям

|Д(г) =/?;(*), если г 6 Л,

> (/ПО) Для всех » € N и существует ю : Е«(р(-)) > ££(/Г(-)).

е'(х') — смешанная стратегия игрока»в игре Г(г), предписывающая выбор чистой альтернативы х^ 6 Л"' с вероятностью 1.

Множество {(г,!1) : г £ 2 \ А} = Т назовем деревом коопертивных траекторий. Обозначим через [Л(2)]г\л множество пар (г,х*) из Л(г), таких, что г 6 2\А.

Теорема 4 Предположим, что существует такое подмножество вершин А Э {г € 2 : Ь, — 0}, что для каждой вершины г 6 2 \ А, такой, что либо существует вершина у £ 2\ А, для которой р(у, г; ху) ф 0, либо г — 2о, выполняются следующие условия

шах + £ ?(*. У. (2*11*,*))• ПШ)} < £/(№(')). V ; 6 (8)

уел.

Тогда в стохастической игре С? существует равновесие по Нэшу с ожидаемыми выигрышами = Е? (/](■)), * е

Рассмотрим ситуацию в стратегиях поведения д'(-) = <?*(•)) в игре 5,

такую, что

' е*(х*), если г € 2 \ А и Л(г) С Т,

/?,*(*), если г 6 Л и Ь(г): [Л(*)]г\л С Т,

9,•(*»(*))= еслигб2иЭг/б2\Адоги;^г:Л(у)сТ, (9)

(у,х»)*Г, но (у, (х"||х]|)) 6 Т, . произвольна в остальных случаях.

Ситуация д'(-) — (?!(•).....?*(•)) образует равновесие по Нэшу в игре С?.

Пусть (Р](-),Р'н^^)) — ситуация абсолютного равновесия в антагонистической стохастической игре Причем совместная смешанная стратегия /З^(-)

коалиции представима в виде = {^»(О},^^ • Тогда в качестве

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

одной из предыдущих вершин отклонился игрок ], равновесные стратегии игроков I 6 М\] предписывают следовать стратегиям Результат теоремы иллюстрируется на примере.

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

В §3.1 рассматривается стохастическая игра п лиц С с постоянными вероятностями перехода (р£(х*) = р*, Ух' 6 П»елг-^'> Л, г = 1,4) с бесконечным числом шагов Процесс построения стохастические игры с бесконечным числом шагов подробно описан в первой главе.

В данном случае следует рассмотреть антагонистические игры между коалицией 5 и коалицией Выигрыш игрока 1 (коалиции 5) определен как сумма выигрышей членов коалиции. Пусть — пара оптимальных стратегий в

игре Г|. Рассмотрим функции ч*(5) : 2" -* Я, к ~ 1,...,4. Определим значение функции и'(5) одним из следующих способов:

1. если совместная равновесная стратегия коалиции N\S представима в виде = тогда определим как значение игры Г|:

»»(5) = «1 {£,«*?}:

2. или как верхнее значение антагонистической игры Г*

min max x*,vs).

xn\s€ll<en\sx> 's^lhes^j jg5

Как и ранее, фиксируем в каждой одношаговой игре Г', 2 = 1,..., t, некоторую

ситуацию х1 е П|eff

Теорема 5 Если для всех j е N выполняются следующие условия

max

«J е х;

xj ф s*

pax

xj е х}

,k = l,t, (Ю)

тогда в стохастической игре С? существует равновесие по Нэшу с ожидаемыми выигрышами игроков, равными Е, =

Здесь ([П]"1)( - 1-я строка матрицы [П]"1, Кх = (К](ху)>... ,Я?(х'))г.

Далее формулируется теорема о существовании сильного трансферабельного и сильного равновесий в регуляризованной игре йл. Обозначим через х* = {£I, ■ • I набор чистых альтернатив, доставляющий максимум сумме ^ К*.

16ЛГ

Регуляризованная игра строится аналогично как и в § 1.3.

Теорема 6 Пусть существуют векторы а* = (а*, ..., о*)Т 6 Л", к = 1,2,..., {, удовлетворяющие (4), такие, что для всех к = 1,...,$ и всех 5 С выполнены следующие условия

^s ellj€sA> ,cs jes ы

XS = Hies A J J€s

. x's Ф ¿s

(11)

Тогда в регуляризации существуют сильное трансферабельное равновесие и сильное равновесие.

Теорема 7 Для того, чтобы существовала регуляризация <5, в которой существует сильное трансферабельное равновесие, необходимо и достаточно, чтобы для любого сбалансированного набора весов и всех к = выполнялись условия

/ \

scn

XS fc 11,65 X3 jeS (=l

V «s * *s /J

В § 3 2 рассматривается стохастическая игра с постоянными вероятностями перехода (р(г, у\х') = р(г, у)) с конечным числом шагов. Процесс построения стохастической игры в данном параграфе немного отличается от предложенного в главе 2. В данном параграфе предполагается, что все пути графа С? = (2, Ь), соединяющие начальную вершину га и конечные вершины г : Ьг = 0, имеют длину М. Каждой вершине г € 2 соответствует одна из игр Г1, Г2,..., Г':

Г(г) = Г* = <ЛГ; х;.....Хк;Кк,...,Кк).

Рассмотрим антагонистические игры Г^ между игроком j и коалицией N\J, порожденные играми Г*, к = 1,..., ¿. Пусть паРа оптимальных стра-

тегий в игре Как и ранее определим функции ъ,к({]}) одним из следующих способов:

1. если совместная равновесная стратегия коалиции N \ ] представима в виде = , тогда определим как значение игры Г^.

2. как верхнее значение антагонистической игры Г*^.

Зафиксируем некоторый набор альтернатив хк = (г*,...,!*) в каждой игре Г', к — 1,..., Ь. Обозначим через К, = (К} (ж1),..., К[ (г'))т вектор соответствующих выигрышей в играх Г1,..., Г'. Пусть ц'к = (ц\к,..., — ситуация равновесия по Нэшу в одношаговой игре Г*, к = 1,..., Ь и Я, = (Я,1,..., Я')г — вектор соответствующих выигрышей в играх Г1,..., Г'.

Теорема 8 Пусть Г(г0) = IV Предположим, что существует такое з (1 < я < М), что для всех i € N выполняются следующие условия:

тах/С.ЧхЧ^-ЛГЛ^^П,.

тах Кк(хкЦхк)-Кк(хк) < Пк-

(ЕпА (Я,- „({,})) + (еп») (к - я,)

Дт=0 / \т=0 /

"/М-»"-! \ \

Е пт №-"№»)+ Е п» (*,-я.)

Л т=0 / \ т=0 /

к = 1,..., 1 < з' < з. Тогда в игре (? существует равновесие по Нэшу с выигрышами

(Епт)^,+( Е пт)я-

. \т=0 / \т=л-1 /

, »елг.

Множество А — множество вершин г £ 2, таких, что путь, соединяющий начальную вершину го и г, имеет длину не менее з +1.

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

Так как для каждого игрока г выигрыш Я* в ситуации равновесия по Нэшу в каждом игровом элементе Г' равен значению «*({»}) антагонистической игры Г*,}, в данной игре метод построения нового класса равновесий, предложенный в § 2 2 и § 3.2, не может быть применен.

По этой причине предлагается построить регуляризацию игры. Пусть хк = [х^,...,хк) — ситуация в Г*, такая, что Кк(хк) > #*, для г е N, к = 1 ,...,£ (такая ситуация существует). С этой целью граф С надстраивается до графа <-?т = (2"т, ¿т) так, чтобы все пути имели длину М+т. Пусть Г (г) = Г*, Г(у) = Гг, у € Ь,. Вероятности перехода р(г,у;х') задаются следующим образом: если г € 2: Ьж ф 0, или г € 2Г \ ¿, тогда р(г, у\ х") = ргк для V I1; если г € ¿Г: Ьг = 0, тогда р(г,у,х') = р[, для хг- х' ф х', но (гг||г,г) = хг, г € ТУ;

р(г,у\х') = 0 в остальных случаях. Таким образом, вЗ, в некоторых случаях стохастическая игра продолжается (М 4- т) шагов.

Обозначим через Ki = ( max ^(i'lfi?),..., max ie|lx{) . Теорема 9 Предположим, что Нк < 0, к = 1,..., t, t е N. Пусть т такое, что

тогда в игре GT существует ситуация равновесия по Нэшу с ожидаемыми выигры-

Теоремы проиллюстрированы на примерах. В заключении подытоживаются полученные результаты. В приложении 1 приводятся необходимые расчетные выкладки к примеру из § 1.3. В приложении 2 приводятся необходимые расчетные выкладки к примеру из

§2.2.

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

РАБОТЫ:

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

2. Grauer L. (2003). Strong Nash equilibrium in stochastic games. Conference Book of the XV Italian Meeting on Game Theory and Applications. P. 38.

3. Grauer L.V. (2002). Folk TheoremsforStochastic Games. Proc. 10th International Symposium on Dynamic Games and Applications. V. 1 P. 345-348.

4. Grauer L.V., Petrosjan L.A. (2002). Strong Nash Equilibrium in Multistage Games. International Game Theory Review. V. 4(3). P. 255-264.

5. Grauer L.V., Petrosjan L.A. (2002). New Class of Solutions in Multistage Games with Applications to "Prisoner's Dilemma". Game Theory and Applications. V. 8. P. 125-134.

6. Грауэр Л.В. (2001). Повторяющаяся игра "Дилемма заключенного" п лиц. Труды XXXII научной конференции "Процессы управления и устойчивость". С. 357-361.

Подписано к печати 03.09.2004 г. Формат бумаги 60X84 1/16. Бумага офсетная. Печать ризографическая. Объем 1 п.л. Тираж 100 экз. Заказ 3335. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198504. Санкт-Петербург, Старый Петергоф, Университетский пр., 26.

»16647

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Грауэр, Лидия Вальтеровна

Введение

Глава 1. Стохастические игры п лиц с бесконечным числом шагов.

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

§ 1.2. Равновесие по Нэшу в стратегиях наказания

§ 1.3. Регуляризация игры G. Сильное трансферабельное равновесие.

Глава 2. Стохастические игры п лиц с конечным числом шагов

§ 2.1. Постановка задачи.

§ 2.2. Построение равновесий по Нэшу

Глава 3. Стохастические игры п лиц с постоянными вероятностями перехода

§ 3.1. Стохастические игры с постоянными вероятностями перехода с бесконечным числом шагов

3.1.1. Построение равновесий по Нэшу.

3.1.2. Сильное трансферабельное равновесие

§ 3.2. Стохастические игры с постоянными вероятностями перехода с конечным числом шагов

§ 3.3. Дилемма заключенного п лиц.

3.3.1. Случай одношаговой игры

3.3.2. Стохастическая игра дилемма заключенного.

Введение диссертация по математике, на тему "Новые ситуации равновесия в стохастических играх"

Стохастические игры были введены JI.C. Шепли [48]. Шепли рассматривал останавливающиеся стохастические игры двух лиц с нулевой суммой, т.е. игры, для которых в каждом состоянии для каждой пары альтернатив игроков, игра останавливается с положительной вероятностью. Предполагалось, множество состояний конечно и множества альтернатив конечны. Шепли доказал, что такие игры имеют значение и оба игрока обладают оптимальными стационарными стратегиями.

Работы [21, 23, 24, 25, 37, 38, 47, 50, 51, 56] посвящены исследованию стационарных и марковских стратегий, стратегий поведения в стохастических играх. Особое место занимают алгоритмы построения стационарного равновесия в стохастических играх [22, 42, 36].

Основным принципом оптимальности в бескоалиционных играх является равновесие по Нэшу [39]. Вопросу построения равновесия в многошаговых и стохастических играх посвящены многочисленные исследования отечественных и зарубежных авторов [10, 11, 15, 18, 20, 21, 23, 24, 25, 35, 37, 38, 50, 51, 52, 56].

В теории игр важным вопросом является построение сильных равновесий, то есть равновесий, устойчивых относительно отклонений коалиций игроков [13, 18, 27, 32, 40]. Для классического статического случая оно не имеет особого смысла, так как такие равновесия, как правило, не существуют. Однако, рассмотрение игр в динамике открывает новые возможности. JI.A. Петросян [14] предложил механизм регуляризации динамических и дифференциальных игр, в рамках которой сильное равновесие существует.

В работах [31, 33, 34, 49] предлагаются решения задач типа дилемма заключенного.

В данной работе рассматриваются стохастические игры п лиц с конечным и бесконечным числом шагов. В дискретные моменты времени игроку приходится выбирать одну из конечного множества альтернатив. Этот выбор определяет немедленный выигрыш, а также вероятностный вектор, согласно которому указывается новое состояние, в котором надо будет выбирать альтернативу на следующем шаге. В каждый момент времени для каждого набора альтернатив вероятность окончания игры положительна. Предполагается, что множества состояний и множества альтернатив конечны. Игрок стоит перед проблемой выбора стратегии, которая принесет ему наибольший выигрыш. В данной работе, используя идеологию народных теорем удалось конструктивно построить Парето оптимальные равновесия по Нэшу, а также, используя механизм регуляризации, предложенной JI.A. Петросяном [14], построены сильные равновесия в стохастических играх.

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

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

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

1. предлагается новый класс равновесий по Нэшу в стохастических играх п лиц;

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

3. предлагается новый класс равновесий по Нэшу в стохастических играх с постоянными вероятностями перехода;

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

Результаты работы докладывались на семинаре по теории игр (Санкт-Петербург), на 10-м международном симпозиуме по динамическим играм и приложениям (Санкт-Петербург), на XV конференции по теории игр и приложениям IMGTA (Урбино, Италия), на XXXII научной конференции "Процессы управления и устойчивость" (Санкт-Петербург).

Основные результаты диссертации опубликованы в работах [3, 4, 29, 30, 44, 45].

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

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

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

В § 1.3 вводится понятие сильного трансферабельного равновесия. Строится регуляризация исходной стохастической игры п лиц с бесконечным числом шагов, в которой возможно перераспределение выигрышей игроков. Используется механизм регуляризации, который был впервые предложен в [14]. Предлагается способ построения сильного трансферабельного и сильного равновесий в регуляризованной стохастической игре, основанных на возможности наказания игроков, отклонившихся от соглашения. Даются достаточные условия существования сильного трансферабельного и сильного равновесий в регуляризованной игре. Для случая двух игровых элементов даются необходимые условия существования регуляризации, в которой существует сильное трансферабельное равновесие. Результаты иллюстрируются на примере.

Во второй главе рассматриваются стохастические игры п лиц с конечным числом шагов. В § 2.1 приводится постановка задачи. Описывается стохастическая игра на конечном древовидном графе. Описывается структура графа.

В § 2.2 предлагается способ построения равновесия по Нэшу в стохастической игре с конечным числом шагов п лиц, основанного на комбинировании наказания игрока, отклонившегося от соглашения, и использования абсолютного равновесия по Нэшу. Впервые данный подход построения такого равновесия был предложен в работе [43] для случая биматричных повторяющихся игр. Результаты иллюстрируются на примере.

В третьей главе рассматриваются стохастические игры п лиц с постоянными вероятностями перехода.

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

В §3.2 рассматриваются стохастические игры п лиц с постоянными вероятностями перехода с конечным числом шагов. Строится новое комбинированное равновесие по Нэшу

В § 3.3 рассматривается случай стохастической игры с конечным числом шагов на каждом шаге, которой разыгрывается игра вида дилемма заключенного п лиц. Для такого вида игр проводится регуляризация. Формулируются достаточные условия существования нового равновесия по Нэшу в регуляризованной игре. Результаты иллюстрируются на примере.

В заключении подытоживаются полученные результаты.

В приложении 1 приводятся необходимые расчетные выкладки к примеру из § 1.3.

В приложении 2 приводятся необходимые расчетные выкладки к примеру из §2.2.

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

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Заключение

Подведем основные итоги диссертационной работы. В работе

1) предложен новый класс равновесий по Нэшу в стохастических играх п лиц с бесконечным числом шагов;

2) предложен новый класс равновесий по Нэшу в стохастических играх п лиц с конечным числом шагов;

3) построены сильное трансферабельное и сильное равновесия в стохастических играх п лиц с бесконечным числом шагов; получены необходимые условия существования регуляризации стохастической игры п лиц, в которой существует сильное трансферабельное равновесие;

4) предложен новый класс равновесий по Нэшу в стохастических играх п лиц с постоянными вероятностями перехода;

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Грауэр, Лидия Вальтеровна, Санкт-Петербург

1. Беллман Р. Динамическое программирование. М., 1960.

2. Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. М: Наука, 1984.

3. Грауэр Л. В. Повторяющаяся игра "Дилемма заключенного"п лиц // Труды XXXII научной конференции "Процессы управления и устойчивость". 2001. С. 357-361.

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

5. Данилов Н.Н. Кооперативные многошаговые игры с побочными платежами // Изв. Вузов. Мат. 1991. №2. С. 33-42.

6. Данилов В.И. Лекции по теории игр. М: РЭШ, 2002.

7. Кемени Дж., Снелл Дж., Кнепп А. Счетные цепи Маркова. М: Наука, 1987.

8. Кузютин В., Зенкевич Н., Еремеев В. Геометрия. СПб, 2003.

9. Куммер Бернд Игры на графах. М: Мир, 1982.

10. Лагунов В.Н., Сушкин В.В. Многошаговые позиционные игры N лиц. Тверь, 1993.

11. Многошаговые, иерархические, дифференциальные и бескоалиционные игры: межвузовский тематический сб. науч. тр. Калинин КГУ, 1987.

12. Мулен Э. Теория игр с примерами из математической экономики. М: Мир, 1985.

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

14. Петросян Л.А. Полукооперативные игры // Вестник СПбГУ. 1998. Сер. I. Вып. 2(8). С. 62-69.

15. Петросян Л.А., Данилов Н.Н. Устойчивость решений в неантагонистических дифференциальных играх с трансферабельными выигрышами // Вестник Ленинградского университета. 1979. №1

16. Петросян Л.А., Захаров В.В. Математические модели в экологии. СПб: Изд. СПбГУ, 1996.

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

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

19. Abreu D., Dutta Р.К., Smith L. The folk theorem for repeated games: a NEU condition // Econometrica. 1985. V. 62. P. 939-948.

20. Aumann R.J. Mixed and behavior strategies in infinite extensive games // Ann. Math. Studies. 1964. V. 52. P. 627-650.

21. Duffie D., Geanakoplos J., Mas-Colell A., McLennan A. Stationary Markov Equilibria // Econometrica. 1994. V. 62. P. 745-781

22. Filar J.A., Schultz Т.A., Thuijsman F., Vrieze O.J. Nonlinear programming and stationary equilibria in stochastic games // Mathematical Programming. 1991. V. 50. P. 227-237.

23. Flesch J., Thuijsman F., Vrieze O.J. Markov strategies are better than stationary strategies // International Game Theory Review. 1997. V. 1. P. 9-31

24. Flesch J., Thuijsman F., Vrieze O.J. Optimality in different strategy classes in zero-sum stochastic games // Math. Meth. Oper. Res. 2002. V. 56. P. 315-322.

25. Flesch J., Thuijsman F., Vrieze O.J. N-person switching control stochastic games // Proc. 10th International Symposium on Dynamic Games and Applications. 2002. V. 1 P. 315-321.

26. Fudenberg D., Maskin E. The folk theorem for repeated games with discounting or with incomplete information // Econometrica. 1986. V. 54. P. 533-554.

27. Fudenberg D., Tirole J. Game theory. Cambridge: MIT press, 1991.

28. Gossner O. The folk theorem for finitely repeated games with mixed strategies // Int. J. Game Theory. 1995. V. 24. P. 95-107."

29. Grauer L.V. Folk Theorems for Stochastic Games // Proc. 10th International Symposium on Dynamic Games and Applications. 2002. V. 1 P. 345-348.

30. Grauer L. Strong Nash equilibrium in stochastic games // Conference Book of the XV Italian Meeting on Game Theory and Applications, 2003. P. 38.

31. Hamburger H. N-person prisoner's dilemma // J. Mathematical Sociology. 1973. V. 3. P. 27-48.

32. Holzman R., Law-Yone N. Strong Equilibrium in Congestion Games // Games and Economic Behavior. 1997. V. 21. P. 85-101.

33. Jones M. The effect of punishment duration of trigger strategies and quasifinite continuation probabilities for prisoner's dilemma // Int. J. Game Theory. 1999. V. 28. P. 533-546.

34. Kreps D., Milgrom P., Roberts J., Wilsson R. Rational cooperation in the finitely repeated prisoner's dilemma // J. Economic Theory. 1982. V. 27. P. 245-252.

35. Kuhn, H. W. Extensive games and the problem of information // Anals of Mathematics Studies. 1953. V. 28 P. 193-216.

36. Liapounov A.N. Asymptotic optimality in Markov processes and stochastic games // In: Int. Conf. "Logic, Game theory and Social Choice", Ext Abstracts. 2001. P.155-157.

37. Mertens J.F., Parthasarathy T. Non Zero Sum Stochastic Games //In Stochastic Games and Related Topics, Raghavan T.E.S. et al. (eds.), Kluwer Academic Publishers, 1991. P. 145-148.

38. Mertens J.F., Neyman A. Stochastic games j j Int. J. Game Theory. 1981. V. 10. P. 53-66.

39. Nash J. Equilibrium points in n-person games // Proc. Nat. Acad. Sci. U.S.A. 1950. Vol. 36. P. 48-49

40. Osborne M. J., Rubinstein A. A course in game theory. Oxford: Univ. Press, 1996.

41. Owen G. Game Theory. W. B. Saunders Company. Philade-lphia-London-Toronto. 1986.

42. Peeters R.J.A.P., Herings P.J.-J. Stationary equilibria in Stochastic games: structure, selection and computation // Proc. 10 ISDG. 2002. V. 2. P.669-685

43. Petrosjan L.A., Egorova A. A. New class of solutions for repeated bimatrix games. // Proc. 11th IFAC Workshop Game "Control Applications of Optimization". 2000. V. 2. P. 617-622.

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

45. Petrosjan L.A., Grauer L.V. New Class of Solutions in Multistage Games with Applications to "Prisoner's Dilemma" // Game Theory and Applications. 2002. V. 8. P. 125-134.

46. Smith L. Necessary and sufficient conditions for the perfect finite horizon folk theorem // Econometrica. 1995. V. 63. P.425-430.

47. Sobel M.J. Non-cooperative stochastic games // Ann. Math. Studies. 1971. V. 42. P. 1930-1935.

48. Shapley L.S. Stochastic games // Proc. Nat. Acad. Sci. U.S.A. 1953. V. 39. P. 1095-1100.

49. Straffin P. D. Game Theory and Strategy. Washington. Washington: The Math. Associat. America, 1993.

50. Thuijsman F. Optimality and equilibria in stochastic games. CWI tract. Amsterdam: Centrum voor wiskunde en informatica, 1992.

51. Thuijsman F., Raghavan T.E.S. Perfect information stochastic games and related classes // Int. J. Game Theory. 1997. V.26. P. 403-408.

52. Van Damme E.E.C. Stability and perfection of Nash Equilibria. Berlin: Springer-Verlag, 1991.

53. Vasin A.A. The folk theorem for dominance solutions // Int. J. Game Theory. 1999. V. 28. P. 15-24.

54. Vasin A. The folk theorems in the framework of evolution and cooperation // Proc. 10th International Symposium on Dynamic Games and Applications. 2002. V. 2 P. 852-857.

55. Villiger R., Petrosjan L.A. Construction of time-consistent imputations in differential games // Proc. 2nd International Conference "Logic, Game Theory and Social Choice". 2001.

56. Vrieze O. Stochastic games with finite state and action spaces. CWI tract. Amsterdam: Centrum voor wiskunde en informatica, 1987.

57. Wen Q. The folk theorem for repeated games with complete information // Econometrica. 1994. V. 62. P. 949-954.