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

• Автор: Грауэр, Лидия Вальтеровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Санкт-Петербург
• Количество страниц: 118 с. : ил.

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

числом шагов

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

числом шагов

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

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

равновесие

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

шагов

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

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

Глава 3. Стохастические игры п лиц с постоянными
вероятностями перехода
§ 3.1. Стохастические игры с постоянными вероятностями перехода с бесконечным числом шагов
3.1.1. Построение равновесий по Нэшу
3.1.2. Сильное трансферабельное равновесие
§ 3.2. Стохастические игры с постоянными вероятностями
перехода с конечным числом шагов
§ 3.3. Дилемма заключенного п лиц
3.3.1. Случай одношаговой игры
3.3.2. Стохастическая игра дилемма заключенного
Заключение
Список литературы
Приложение
Приложение

Актуальность темы. Теория стохастических игр и, как частный случай, теория многошаговых и повторяющихся игр представляют собой бурно развивающийся в настоящее время раздел теории игр. Стохастические и многошаговые игры более адекватно моделируют общественные, экономические, экологические и другие процессы, характеризующиеся случайным или последовательным переходом из одного состояния в другое.
Стохастические игры были введены Л.С. Шепли [48]. Шепли рассматривал останавливающиеся стохастические игры двух лиц с нулевой суммой, т.е. игры, для которых в каждом состоянии для каждой пары альтернатив игроков, игра останавливается с положительной вероятностью. Предполагалось, множество состояний конечно и множества альтернатив конечны. Шепли доказал, что такие игры имеют значение и оба игрока обладают оптимальными стационарными стратегиями.
Работы [21, 23, 24, 25, 37, 38, 47, 50, 51, 56] посвящены исследованию стационарных и марковских стратегий, стратегий поведения в стохастических играх. Особое место занимают алгоритмы построения стационарного равновесия в стохастических играх [22, 42, 36].
Основным принципом оптимальности в бескоалиционных играх является равновесие по Нэшу [39]. Вопросу построения равновесия в многошаговых и стохастических играх посвящены многочисленные исследования отечественных и зарубежных авторов [10, И, 15, 18, 20, 21, 23, 24, 25, 35, 37, 38, 50, 51, 52, 56].
В литературе по теории многошаговых и повторяющихся игр особое

место занимают так называемые народные теоремы, из которых следует возможность построения Парето оптимальных равновесий по Нэшу с использованием стратегий наказания. Поскольку авторство этих теорем не определено, они получили название народных теорем. Идеология народных теорем встречается в работах [19, 27, 28, 40, 46, 53, 54, 57].
В теории игр важным вопросом является построение сильных равновесий, то есть равновесий, устойчивых относительно отклонений коалиций игроков [13, 18, 27, 32, 40]. Для классического статического случая оно не имеет особого смысла, так как такие равновесия, как правило, не существуют. Однако, рассмотрение игр в динамике открывает новые возможности. Л.А. Петросян [14] предложил механизм регуляризации динамических и дифференциальных игр, в рамках которой сильное равновесие существует.
В работах [31, 33, 34, 49] предлагаются решения задач типа дилемма заключенного.
В данной работе рассматриваются стохастические игры п лиц с конечным и бесконечным числом шагов. В дискретные моменты времени игроку приходится выбирать одну из конечного множества альтернатив. Этот выбор определяет немедленный выигрыш, а также вероятностный вектор, согласно которому указывается новое состояние, в котором надо будет выбирать альтернативу на следующем шаге. В каждый момент времени для каждого набора альтернатив вероятность окончания игры положительна. Предполагается, что множества состояний и множества альтернатив конечны. Игрок стоит перед проблемой выбора стратегии, которая принесет ему наибольший выигрыш. В данной работе, используя идеологию народных теорем удалось конструктивно построить Па-

2. Предположим теперь, что стратегия д^(-) совпадает со стратегией (Д(-) на историях /г(г) С Т, г € Д А, но существуют вершина г' € А и история й(г') : [ад]щл С Т, такие, что
<й(Л(/)) ф ч]{Кг'))-
Не умоляя общности, будем считать, что г' — первая из вершин г € А, таких, что существует история Н(г) : [Ь{г)^А С Т и qj(h(z)) ф д*{к{г)).
Обозначим через Z* С % объединение вершин из пути го, г гт_1 (гт = г') и вершин из множества ^г', Zz' — множество вершин подграфа О {г 0 = {2^, Т), начинающегося с г1.
Рассмотрим ожидаемый выигрыш игрока ^ в ситуации (?*(•) 11^(0)
^ М(г,д*(-)1Ы'))'
гб{г0,г1 2т_1}
+РВД) Е д*(-)1М-))
геД*'
+ е щ*.«*(-)н»(-))-
Ем'Щ)к;щ)
, Ж*

X2 , Ж*
+ (2.10)
+ (2.11)
(2.12)
Здесь
к=ш Ч1г*
гт = г', г* = г, М*'{г',д-)||дД-))
Сумма (2.10) равна ожидаемому выигрышу, который игрок $ получит в ситуации (?*(-)||?у(0) ВД°ЛЬ пути го, г гт~: ггп = г'. Так как стратегия д^(-) совпадает со стратегией д*(-) на пути го, г гт-,