Введение
Глава I. Метод форсирования критической позиции. 27
1 Стационарные равновесия в циклических играх с максимальным платежом по циклу .
1.1 Теорема существования равновесия. 30
1.2 Структура стационарного равновесия. 40
2 Стационарные равновесия в циклических играх с симметрическим платежом по циклу.
2.1 Теорема существования равновесия. 42
2.2 Сложность поиска стационарного равновесия. 52
Глава II. Игры с запретами. 56
3 Игры с запретами и средним предельным функционалом по тра- 56
ектории.
3.1 Вспомогательный алгоритм. 60
3.2 Корректность и конечная сходимость вспомогательного алгоритма . - 65
3.3 Доказательство теоремы и алгоритм приведения сети к кононическому виду. - 71
3.4 Исследование вычислительной сложности основного алгоритма. 75
4 Игры с запретами и максимальным предельным платежом по траектории.
4.1 Описание алгоритма поиска равновесных стратегий. 88
4.2 Корректность и вычислительная сложность алгоритма. 93
Глава III. Специальные классы задач . 99
5 NP - полнота задачи структурной неэргодичности. 99
6 Силыюполиномиальный алгоритм характеризации всех максимальных средних циклов, - 105
7 Алгоритм нахождения стационарного равновесия в стохастических играх специальной структуры .
7.1 Определения и формулировка утверждения. 112
7.2 Алгоритм приведения игры к каноническому виду. 116
Глава IV. Результаты существования стационарных равновесий в играх с платежами типа средних. 120
8 Определения и формулировка утверждения. 120
9 Максимальный функционал. 124
10 Симметрический функционал. 125
11 Медианный функционал. 126
Глава V. Метод форсирования для вычислений в модальной логике 133
12 Модальная логика. Основные определения. 133
12.1 Сведение вычислений формул модальной логики к решению циклических игр с симметрическим платежом. 138
13 Форсирование в модальной логике. 148
13.1 Сильноэргодические игры. 156
14 Эффективное вычисление формул для почти ациклических Крипке графов. 159
Заключение 171
Литература. 173
