Структура и поиск стационарных управлений в циклических играх с полной информацией

• Автор: Лебедев, Василий Николаевич
• Шифр специальности: 05.13.01
• Научная степень: Докторская
• Год защиты: 2005
• Место защиты: Волгоград
• Количество страниц: 195 с. : ил.

1 Стационарные равновесия в циклических играх с максимальным платежом но циклу.

1.1 Теорема существования равновесия.

1.2 Структура стационарного равновесия.

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

2.1 Теорема существования равновесия.

2.2 Сложность поиска стационарного равновесия.

Глава II. Игры с запретами.

3 Игры с запретами и средним предельным функционалом но тра ектории.

3.1 Вспомогательный алгоритм.

3.2 Корректность и конечная сходимость вспомогательного алгорит

3.3 Доказательство теоремы и алгоритм приведения сети к коноииче скому виду.

3.4 Исследование вычислительной сложности основного алгоритма.
4 Игры с запретами и максимальным предельным платежом по тра ектории.
4.1 Описание алгоритма поиска равновесных стратегий.
4.2 Корректность и вычислительная сложность алгоритма.
Глава III. Специальные классы зада.
5 полнота задачи структурной исэргодичности.
6 Сильиополииомиальиый алгоритм характеризации всех макси 5 мальных средних циклов.
7 Алгоритм нахождения стационарного равновесия в стохастиче
ских играх специальной структуры.
9 7.1 Определения и формулировка утверждения.
7.2 Алгоритм приведения игры к каноническому виду.
Глава IV. Результаты существования стационарных равновесий в играх с платежами типа средних.
8 Определения и формулировка утверждения.
9 Максимальный функционал.
Симметрический функционал.
Медианный функционал.
Глава V. Метод форсирования для вычислений в модальной логике
Модальная логика. Основные определения.
О .1 Сведение вычислений формул модальной логики
к решению циклических игр с симметрическим платежом.
Форсирование в модальной логике.
.1 Сильноэргодические игры.
Эффективное вычисление формул для почти ациклических
Крипке графов.
Заключение
Литература.
Приложение1.
Приложеиие2.
ВВЕДЕНИЕ


В этом случае метод форсирования критической позиции также даст утверждение о наличии стационарного равновесия, и удается неявно описать структуру стационарного равновесия . Из конструктивного доказательства следует лишь только экспоненциальный в худшем случае алгоритм поиска стационарного равновесия. Однако найдены широкие классы задач, где алгоритм является полиномиальным. Представлена полиномиальность для сильиоэргодическнх игр, игр с фиксированным числом приорететов, и для решения проблемы выполнимости формул исчисления на почти ациклических Крипке графах эти результаты представлены в главе 5. В формальной части работы будут даны строгие определения. Второй случай решает проблему определения выполнима ли формула исчисления с фиксированным числом альтернаций операторов наименьшей и наибольшей неподвижных точек. В главе 2 рассматриваются циклические игры с запретами . Этот случай представляется следующей схемой игры. В любой момент времени функционирования системы при попытке перевести систему из состояния V в состояние и но ребру т возможен сбой или отказ, и число этих отказов определяется целочисленной функцией ку О ку Ки 1, заданной на вершинах V. Исходя из концепции гарантированного результата, будем считать, что отказ в состоянии г Л осуществляется противоборствующим первым игроком, а в состоянии V В вторым игроком. Далее второй в вершине V Л и первый в вершине V В переводит игру по любому из оставшихся Иц ку ребер, после этого ребра восстанавливаются. В результате будет пройдена бесконечная траектория щ,. Тогда рассматриваются предельные платежи первого игрока второму а, Ь. Точно так же справедлива редукция к конечной циклической игре, равновесные стратегии в которых естественным образом продолжаются до равновесных стратегий общего вида в бесконечной игре. С помощью метода форсирования критической позиции доказаны утверждения о наличии стационарных равновесий для позиционных средних а, Ь. Из доказательства следует алгоритм поиска искомых равновесий. Для максимального платежа Ь алгоритм полиномиален. Операция форсирования позволяет описать структуру равновесных стратегий. Во второй главе также рассматривается средний платеж но траектории а. Алгоритм потенциальных праобразований обобщается на случай игр с запретами. Конструкция алгоритма заключается в следующем. Рассматриваются потенциальные преобразования стоимостной функции сиу сни н еу для произвольных рациональных еу. Длины циклов суммарная стоимость весов ребер цикла инвариантны относительно данного потенциального преобразования, поэтому потенциальное преобразование порождает игру, эквивалентную первоначальной. Оказывается, всегда существует потенциальное преобразование с б, приводящее игру к тривиальному виду. Именно, если разбить вершины по значениям экстремумов где иод экстремумом в вершине V А ц В понимается значение ку 1 максимума минимума в порядке невозрастания неубывания ребер, исходящих из вершины у, то в блоки с большим значением экстремума можно перейти только по ребрам стоимости строго большей значения экстремума в рассматриваемом блоке, а в блоки с меньшим значением экстремума по ребрам стоимости строго меньшей чем значение экстремума в рассматриваемом блоке. Поэтому, если игра началась в вершине и, то второй игрок форсирует выигрыш больший, либо равный еаг,, если он будет переводить игру но ребру максимальной стоимости, оставшегося после отсечений первого игрока в вершинах и А и отсекать первые кш ребра в порядке их неубывания в вершинах гу 6 В. Первый игрок имеет возможность платежа менее, либо равного ехгс,г, если будет отсекать первые кги ребра в порядке их невозрастания в каждой вершине и 6 А, преобразованной игры и переводить игру но ребру минимальной стоимости, оставшегося после отсечений в вершинах ю В. Таким образом, задача сводится к поиску требуемого потенциального преобразования стоимостной функции игры. Во второй главе представлен алгоритм такого преобразования. Алгоритм потенциальных преобразований также неявным образом использует идею форсирования критической позиции.