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

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

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

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

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

04.07.2017

Лето - пора делать собственную диссертацию!

Здравствуйте! Дорогие коллеги, предлагаем Вам объединить отдых и научные исследования. К примеру Вы можете приобрести на нашем сайте 15 ...

28.06.2016

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

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


Все новости

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