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

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

Автор: Лебедев, Василий Николаевич

Шифр специальности: 05.13.01

Научная степень: Докторская

Год защиты: 2005

Место защиты: Волгоград

Количество страниц: 195 с. ил.

Артикул: 2901374

Автор: Лебедев, Василий Николаевич

Стоимость: 250 руб.

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

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 А, преобразованной игры и переводить игру но ребру минимальной стоимости, оставшегося после отсечений в вершинах ю В. Таким образом, задача сводится к поиску требуемого потенциального преобразования стоимостной функции игры. Во второй главе представлен алгоритм такого преобразования. Алгоритм потенциальных преобразований также неявным образом использует идею форсирования критической позиции.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.238, запросов: 244