Содержание к диссертации
Введение
Глава 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
- Стационарные равновесия в циклических играх с максимальным платежом по циклу
- Стационарные равновесия в циклических играх с симметрическим платежом по циклу.
- Корректность и конечная сходимость вспомогательного алгоритма
- Алгоритм нахождения стационарного равновесия в стохастических играх специальной структуры
Введение к работе
I . Актуальность.
В диссертационной работе рассматриваются задачи динамических конфликтов с предельным во времени платежом по траектории. Задачи такого рода возникают в различных процессах принятия решений, имеющих место при управлении техническими и экономическими системами, при распределении запасов, при составлении графиков расписаний. В условиях полной информации имеем хорошо известную задачу оптимального управления в непрерывной или дискретной постановке. Такие проблемы нашли решение в классических работах Л.С.Понтрягина, Р.Беллмана и ряде других.
Практическая актуальность исследований данной работы обусловлена следующими факторами.
Во- первых в приложениях существенным является неопределенность параметров управляемой динамической системой, и такие задачи менее изучены. Управление в условиях стратегической неопределенности в контексте принципа гарантированного результата сводится к решению динамического, антагонистического конфликта с полной информацией. При этом считаем, что выбор неопределенных параметров осуществляет противник, цель которого противоположна основной целе управляющего объекта.
Во- вторых, как правило, управление осуществляется в реальном времени, и требуется мгновенный отклик управляющего объекта на любое отклонение от заданных параметров или от заданной траектории.
В- третьих, важным является большая размерность решаемых задач. Например, многоотраслевы модели экономического развития содержат тысячи параметров. Проблемы верификации программ требуют отслеживать каждый бит памяти компьютера. В задачах кодирования информации также проблема размерности является основной.
Теоретическая актуальность исследований заключается в следующем. Хотя вопросы вычислительной сложности в условиях определенности хорошо изучены, эти вопросы для детерминированных конфликтов даже с полной информацией являются недостаточно изученными. В основном результаты о наличии стационарного равновесия получены с помощью неконструктивной техники топологических теорем о неподвижной точке, типа теоремы Брауэра, либо проводится экспоненциальная индукция.
Подтверждением этого является следующий короткий обзор полученных ранее утверждений и неэффективные оценки сложности вытекаю-
щих из их доказательства алгоритмов.
Рассмотрим формализации стохастических игр, которые предложены Л.С.Шепли в [13].
Это игра двух лиц на конечном множестве позиций V. В позиции v &V разыгрывается матричная игра C(v) размером m(v),n(v). В позиции v первый игрок выбирает строку г, а второй столбец j независимо друг от друга. Тогда с вероятностью p'(v, w) игра перейдет в очередную позицию w и первый платит второму с* (v) или с вероятностью s > О игра завершается (ю р) {v, w) + s — 1 для каждых v, і, j; игроки имеют право применять и случайный выбор строк-столбцов).
Цель первого игрока состоит в минимизации суммарного ожидаемого платежа, а цель второго- максимизация. Описанная выше игра называется стохастической игрой с дисконтированием s.
Обшиє стратегии в рассматриваемой игре, зависимые от предыстории. Это сложный комбинаторный объект, даже чистые стратегии не имеют конечного представления. Оказывается, игрокам достаточно ограничиться стационарными (марковскими) стратегиями, когда выбор строки, столбца в любой текущей позиции не зависит от предыстории. В [13] показано наличие равновесия в стационарных стратегиях в представленной игре (более точно, если одного из игроков ограничить только стационарными стратегиями, а противнику разрешить играть нестационарно, то это не ухудшит положение игрока).
Решение стохастических игр с дисконтом сводится к поиску неподвижной точки оператора, который порожден заменой матриц платежей C(v) ценой соответствующей игры. В силу наличия дисконта такой оператор оказывается сжимающим, поэтому последовательное итерирование оператора имеет геометрическую скорость сходимости к неподвижной точке. В силу полиномиальное решения матричных игр из описанной схемы следует псевдополиномиальный алгоритм приближенного решения стохастических игр с дисконтом (дисконт может быть близким к нулю). Равновесная пара стационарных стратегий определяется неподвижной точкой представленного оператора. Псевдополиномиальности для гарантированной эффективности алгоритма недостаточно (для двоичной системы представления чисел в памяти машины такой алгоритм экспоненциален по времени счета).
Игры с нулевым дисконтом и средним предельным платежом по бесконечной траектории рассмотрены в работах [9], [14], [11]. Во-первых, показано наличие равновесия в стратегиях общего вида и отсутствие рав-
новесия в стационарных стратегиях [11]. Во-вторых, для эргодических игр и игр с полной информацией доказано наличие стационарного равновесия (первый случай тот, когда марковская цепь, порожденная любой парой стационарных стратегий, есть в точности один эргодичесий класс позиций; второй случай тот, когда в любой позиции v один из противников имеет одну строку, столбец, т.е. либо m{v) = 1, либо n(v) = 1) [9], [14]. Доказательство последнего результата проведено аппроксимацией рассматриваемых игр соответствующей стохастической игрой с малым дисконтом. В случае игр с полной информацией гарантируется наличие равновесия в чистых стратегиях [9], [14]. Результирующий алгоритм также имеет псевдополиномиальную оценку.
Заметим, что для эргодических игр утверждение о наличии стационарного равновесия можно получить, используя результаты Какутани о неподвижной точке точечно- множественных отображений (это следует из представления множества оптимальных стационарных стратегий игрока при фиксированной стратегии противника как решение задачи линейного программирования, коэффициенты которой непрерывно зависят от вероятностей смешанной стратегии противника).
Случай детерминированных (pj(«,w) = 0,1 для любых v,w,i,j) игр с полной информации является основным предметом данной работы Удобно следующее графовое представление.
Динамическая система с конечным множеством состояний V существует в дискретном времени t = 0,1,..., находясь в каждый момент времени в одном из состояний u(t) Є V системы [6]. Динамика системы описывается ориентированным графом переходов G — (V; Е), V— вершины, Е— ориентированные ребра. Ребро (uv) є Е означает возможность перехода из состояния u(t) Є К в состояние v(t+1) Є V в момент t функционирования системы. На ребрах Е задана целочисленная функция с локальных платежей переходов. Множество V состояний системы разбито на два непересекающихся подмножества А и В (AUB = V; АПВ — 0), так что выбор перехода v Є V{u) (здесь V(u)— обозначены состояния v, достижимые за один шаг из состояния и) находится в нашем распоряжении лишь при условии принадлежности позиции и к множеству А контролируемых позиций. Исходя из принципа гарантируемого результата, считаем, что в позициях и В выбор перехода осуществляется противоборствующей стороной, называя позиции v є В позициями первого игрока, а позиции v є А - позициями второго игрока.
Любая пара стратегий игроков вд. вв (очередной переход в вершине
u(t) определяется предысторией w(0),w(l), ...u(t)) однозначно порождает некоторую бесконечную траекторию: T(sA,sB) ' ^(0),^(1),...
Тогда критерием качества является некоторый стоимостной функционал, определяемый по локальным платежам этой траектории.
В работе рассмотрены функционалы типа средних:
c{T{sA, 8В) = ТшГ( с(и(т), и[т + 1))) / t,
c(T(sA, sB)) = ~Шс{щ, «t+i),
I—»OQ
(c) с(Г(«л,зв)) = \imc(uuut+1) + Jim c(«t,ut+1).
Таким образом, при возникшей траектории T(sA, sB) платеж первого игрока второму - есть величина c(T($a,sb)), в минимизации которого состоит задача управления первого и в максимизации которого состоит задача управления второго игрока. Наличие равновесия в стратегиях общего вида можно показать сведением к циклической игре. Циклической игрой называют игру, которая проходит по ребрам графа до первого цикла щ,..., щ,..., щ, и,. То есть, как только траектория игры попадает в позицию, где была ранее, игра завершается. Платеж первого игрока второму есть соответствующий платеж типа среднего:
(ft) c(T{sA. sB)) = ( с(и(т), «(т + 1))) /к-1 + 1,
c(T{sA. sB)) = maxT=1,.. ,fc с(ы(т), и(т +1)),
c(T(sA, sB)) = maxT=l> ., с{и{т),и(т +1)) + minT^,,. ,* с({и(т), и{т + 1)). Здесь и(к + 1) есть позиция и(г). Платеж (а) будем называть средним по циклу, (Ь)- максимальным, (с)- симметрическим.
По теореме Цермело следует существование равновесия в стратегиях общего вида в редуцированной циклической игре (циклическая игра -конечная). Более точно, существует пара чистых стратегий общего вида первого и второго игроков s*B, s*A, что для каждой начальной позиции и(0) и для любых стратегий первого и второго игроков sB, sA, выполнены условия седла:
с(и(0), 8 А, s*B) < й(и(0), 8А, ав) = р(и(0)) < с(и(0), sA, а в)
Здесь c(u(0),sa,sb)- значение цикла, возникшего согласно стратегиям sa,sb игроков из начальной позиции u(0); р(и(0)), называют ценой циклической игры в позиции и(0).
Таким образом, пара стратегий sA,sB- равновесна, т.е. ни одному из игроков не выгодно уклоняться от своей стратегии при фиксированной
стратегии противника.
Последовательным удалением циклов из бесконечной траектории полученные равновесные стратегии sA, s*B доопределяют до стратегий в первоначальной бесконечной игре, и это есть равновесная пара чистых стратегий общего вида в первоначальной бесконечной игре. Недостатком этого результата является экспоненциальное представление полученных равновесных стратегий. Хотя доказательство и конструктивно, но не может быть использовано на практике- алгоритм экспоненциален.
Как отмечалось, в бесконечной игре с полной информацией и пре-
' дельным средним платежом (а) существует равновесие и в чистых, ста-
ционарных стратегиях [9]. Более точно, существует пара чистых стаци
онарных стратегий первого и второго игроков sB, з*А, что для каждой
г начальной позиции и(0) и для любых стратегий первого и второго игро-
ков ss, sA, выполнены условия седла:
с(и(0), зА, зв) < с(и(0), зА, зв) = р(и(0) < c(u(0), sA, sB)
Здесь c(u(0),sa,Sb)- платеж (а) по бесконечной траектории; а стационарные стратегии есть отображения вида:
sb ' и —> V(u) для всех и Є В,
Sa'-u-> V(u) для всех и А.
(последнее утверждение непосредственно переносится на конечные циклические игры).
Специальные методы решения представленных динамических, детер
минированных игр в основном используют технику альтернирования,
как в конструктивном доказательстве наличия равновесия в позицион
ных играх с полной информацией [15]. В работе [7] дано первое тополо-
l гически независимое доказательство наличия стационарного равновесия,
из которого следует экспоненциальный алгоритм решения игры.
В работах [4], [16] рассматривался вопрос сложности решения бесконечной игры (а). Представлена аппроксимация такой бесконечной игры конечной за t, t = 1,... шагов. Показано, что цена конечной игры за t шагов из начальной вершины pt(u(0)) стремится к цене в бесконечной игре р(и(0)) при t —» со и получена скорость сходимости:
|р*(и(О))-р(щ(0) \<2Mn/t
Здесь М-максимальная по модулю локальная стоимость перехода, п-число вершин в графе перехода.
Игра за t шагов максминной процедурой сводится к t — 1 шаговой игре за линейное время, что дает приближенный псевдополиномиальный алгоритм решения бесконечной игры. В силу того, что две различные величины средних циклов (в графе с целочисленной платежной функцией) отличны по крайней мере на 1/п2, для точного решения бесконечной игры достаточно решать конечную игру за t — 2п3М шагов. Оценка сложности алгоритма- Mpoly(n).
Для представленного алгоритма несложно построить пример игровых сетей с двумя вершинами с достижимой псевдополиномиальной оценкой их работы.
Метод потенциальных преобразований представлен [1].
Было замечено, что циклическая игра обладает богатой группой эквивалентных, потенциальных преобразований, которые не меняют суммарных длин циклов, поэтому не меняют игры. Показано, что всегда существует конечная последовательность элементарных потенциальных преобразований- сдвигов, которая приводит игру к тривиальному виду, когда граф распадается на две компоненты- в первой компоненте величины локальных экстремумов вершин отрицательные (оптимальный платеж игрока за один ход), во второй- неотрицательные; в первой компоненте игру оставляет первый игрок (в любой вершине первой компоненты первый игрок имеет экстремальный переход, ведущий в эту же компоненту, а у второго игрока во всех вершинах первой компоненты все переходы ведут в первую компоненту ); во второй компоненте игру оставляет второй игрок. Тогда минмаксные стационарные стратегии игроков гарантируют первому отрицательный платеж в первой компоненте и второму неотрицательный платеж во второй компоненте. Заметим, что решение циклических игр с платежом типа средних полиномиально эквивалентно определению знаков цен. Поэтому эффективный поиск приведенного выше тривиального вида игры дал бы полиномиальный алгоритм решения игры.
Но искомая последовательность преобразований- сдвигов экспоненциальна в худшем случае.
Оценка сложности алгоритма потенциальных преобразований
min{Mpoly(n), W^^log^M}. Здесь М- максимальная по модулю стоимость вершин, п- число вершин игровой сети; poly(n)- полином небольшой степени. В работе [5] представлены достижимые примеры и обобщения.
Замечательным свойством представленных игровых задач является
их принадлежность классу NPClco—NP (это непосредственно следует из наличия равновесия в стационарных стратегиях), поэтому при условии NP ф co—NP, доказать NP-полноту проблемы определения победителя в рассматриваемых циклических играх (Ь), (с), (d) невозможно.
Обзор по сложности решения представленных игр заканчиваем об
щими методами нелинейной оптимизации. Рассматриваемая проблема
представима задачей нахождения максмина линейного функционала с
линейными ограничениями, связующие переменные. Разработаны мето
ды сведения такой задачи к задаче квадратичного программирования
і на линейном многограннике. Сведение проводится с помощью штраф-
ных функций и соотношений двойственности. Существенным для эффек
тивности вычислений является фиксированность коэффициента штрафа
\ при редукции к задаче квадратичного программирования. Для задачи
квадратичного программирования развиты практически быстрые алгоритмы решения, что в сочетании с полиномиальной редукцией дает эффективный практический метод решения рассматриваемых игр, но без гарантированной оценки трудоемкости этих алгоритмов. Отрицательной стороной такого подхода является тот факт, что задача поиска максмина линейного функционала с линейными ограничениями, связующие переменные, является іУР-трудной проблемой.
Другим общим способом решения является подход, связанный с поиском неподвижной точки некоторого максминного оператора. Поиск такой точки можно проводить с помощью вычисления вращения, как некоторого многомерного интеграла. Трудности такого подхода связаны с тем, что в общем случае приближенное вычисление объема многогранника является PSPACE-полной проблемой и, по всей видимости, не имеет эффективного алгоритма.
Итак, из представленного обзора современных методов решений циклических игр следует, что они неэффективны и не позволяют решать практические задачи большой размерности. Эти обстоятельства, а также перечисленные факторы являются обоснованием актуальности темы диссертации.
Цель работы.
1. Основной целью работы является построение эффективных алгоритмов отыскания и описания структуры оптимальных стационарных равновесий в дискретных, динамических, конфликтных ситуациях с предельным во времени платежом. Требования на разрабатываемые алгоритмы следующие. Оценка затрачиваемого временного ресурса прово-
дится на самый худший вариант, то есть исходим из концепции гарантированного результата. Эффективным считаем тот алгоритм, верхняя оценка числа элементарных битовых операций- есть полином небольшой степени от длины записи исходной задачи в памяти машины. Экспоненциальная верхняя оценка сложности еще не является формальным основанием неэффективности алгоритма. В этом случае требуется показать достижимость этой оценки по экспоненциальному порядку. Во многих случаях проблема аналитической оценки времени работы алгоритма довольно сложная алгебраическая задача. Достаточно вспонить, что непо-линомиальность симплекс- метода была доказана лишь через тридцать лет после разработки алгоритма. Практическим эффективным алгоритмом называем тот, для которого проведенное тестирование на модельных примерах дает приемлемое время, близкое к линейному.
2.Практические задачи всегда обладают некоторой особенностью, и поэтому в условиях, когда отсутствует полиномиальный алгоритм решения общей задачи, важно выделение полиномиально разрешимых подклассов общей задачи.
3.Другим аспектом исследований диссертации является проблема обобщения. Известен результат наличия равновесия в стационарных стратегиях для среднего предельного платежа по траектории. Теперь будем рассматривать произвольные функционалы стоимости по траектории. Спрашивается, какими свойствами должен обладать функционал, чтобы осталось в силе утверждение о наличии стационарного равновесия. При этом важно выявить грань полиномиальности задачи при такой функциональной параметризации.
4.И последний аспект целей диссертации является качественный анализ дискретных, динамических, детерминированных конфликтов с полной информацией. Здесь выделяется проблема определения структуры равновесных стратегий и выявление их свойств, таких как стационарность или эргодичность цен.
На защиту выносятся следующие концепции- положения и результаты.
Основным результатом работы является новый метод в теории дискретных динамических конфликтов- структурное представление седловых равновесий с помощью концепции форсирования критической позиции.
1. Доказано, что операцией дополнения шлейфа можно получить любую игровую сеть с заданной ценой. Это дает качественное представление о структуре равновесных стратегий, выявляет их важные свойства-
стационарность, независимость от начальной позиции и эргодичность цен.
С помощью форсирования критической позиции удалось получить ранее неизвестные утверждения существования стационарных равновесий в играх с позиционными средними (Ь), (с) и ряде других.
Конструкция форсирования критической позиции дает полиноми-альность решения игр (Ь) и существенных подклассов (с)- для графов, все сильносвязные компоненты которых сильноэргодические и в случае фиксированного приоритета стоимостной функции.
Получен полиномиальный алгоритм характеризации всех максимальных средних циклов в ориентированных графах. Алгоритм за полиномиальное время находит подграф, циклы которого есть в точности все максимальные средние циклы в исходном графе.
С помощью техники сжимающих отображений получен псевдополиномиальный алгоритм для решения стохастической игры эргодиче-ской структуры. Из этого результата непосредственно следует псевдополиномиальная оценка алгоритма потенциальных преобразований.
Метод потенциальных преобразований обобщен на случай игр с отказами. Проведен тщательный анализ его сложности. Показана его экспоненциальная верхняя оценка и приведен класс игр, на которых эта оценка достижима Тестирование метода показало его практическую эффективность.
Техника форсирования использована для вычисления формул модального исчисления. Выявлены полиномиально разрешимые классы для данной общей проблемы:
определение выполнимости формул модального исчисления со свойством сильной эргодичности;
определение выполнимости формул с фиксированным числом альтернаций операторов наименьшей и наибольшей неподвижных точек;
вычисление значения формул на почти ациклических Крипке- графах.
Научная новизна.
1. В самой диссертационной работе проведен анализ новизны полученных результатов. Естественность вопроса о новых равновесиях возникает в контексте того, что рассмотрены критерии типа средних. Поэтому ставится вопрос, нельзя ли свести полученные утверждения о существовании равновесия к известному среднему. Оказывается в классе преобразований сохраняющих порядок циклов относительно этих критериев
такого сведения не существует. В классе более тонких преобразований сведение существует, но во многих случаях оно нетривиально, как для медианы. При этом доказательства и следующие из них алгоритмы существенно отличны. Для симметрического и максимального платежей техника потенциальных преобразований не работает- потенциальные преобразования при таких критериях меняют длины циклов. Имея только алгоритм потенциальных преобразований, невозможно было бы получить полиномиальность решения игр с максимальным платежом по циклу и полиномиальность выделенных классов с симметрическим платежом.
2.Для игр с отказами построенный алгоритм использует известную технику потенциальных преобразований, но доказательство его конечности потребовало рассмотрения новых комбинаторных структур.
3.Существенной новизной является характеризация циклических игр с заданной ценой и выявление структуры оптимальных стационарных стратегий. В случае игр с максимальным платежом удалось описать структуру стратегий явным образом, как некоторый подграф- шлейф. В случае симметрического платежа описание проводится с помощью конечного числа операций дополнения подграфов- шлейфов. Последний результат дает качестное представление о свойствах оптимальных стратегий.
Доказанные в работе утверждения, данные без ссылок на другие источники, являются новыми. Из результатов опубликованных в соавторстве в работу вошли только те, которые получены лично диссертантом.
Практическая значимость.
Полученные результаты имеют важное практическое значение для решения следующих задач.
(а) Задача оптимального управления развивающейся экономикой в условиях параметрической неопределенности.
Состояние экономической системы определяется набором некоторых показателей. Состояния разделяются на контролируемые, где экономические показатели детерминированы субъектом принятия решения, и на неконтролируемые, где показатели недетерминированы, известна только некоторая информация о них. Динамика описывается некоторой структурой-графом, переход из одного состояния в другое означает возможность управления за единичный временной лаг, при котором система, действительно, совершит данный переход, Причем, в понятие совершит включаются общие рандомизированные возможности поведения системы. За несколько временных лагов в результате определенных управленческих
решений система пройдет некоторую траекторию переходов. Причем, пе
реход системы в очередное состояние находится в распоряжении лица,
принимающего решение только в контролируемых состояниях. Каждый
переход дает определенный выигрыш (или проигрыш) лицу принимаю
щему решение. В максимизации (или минимизации) общего выигрыша
типа средних и состоит задача управления. Мы рассматриваем асимп
тотическую задачу управления системой на бесконечном интервале вре
мени, поэтому общие выигрыши берем средними в расчете на один ход.
Поведение системы в неконтролируемых состояниях неоднозначно, по
этому поставленная задача управления некорректна. Исходя из прин-
) ципа гарантируемого результата, будем оценивать поведение системы в
неконтролируемых состояниях.
В случае гарантированного результата считаем, что в неконтролируемых состояниях переход системы осуществляется противником, цель которого противоположна цели лица, принимающего решение, т.е. целью является минимизация (максимизация) общего выигрыша типа средних. Такая постановка корректно интерпретирует как ситуацию двусторонней монополии (т.е. при которой единственный продавец сталкивается с единственным покупателем), так и конкуренцию дуополии, когда одна из двух конкурирующих фирм играет на разорение другой.
В представленной динамической модели конкуренции показано наличие равновесия, которое является оптимальным поведением фирм. Этот результат качественно описывает положение гомеостазиса, когда ни одному из участников конфликта не выгодно уклоняться от своего поведения при фиксированном поведении противника. Найденные равновесные поведения противников структурно определяются порогом локального выигрыша, которого тот или иной противник форсированно добивается.
(Ь)Задача построения надежных динамических систем управления. При разработке компьютерных программ особое значение приобретает проверка корректности функционирования, что является основой их надежности. До недавнего времени для этих целей использовались такие методы, как тестирование прототипа, а также формальная верификация с помощью математических доказательств. Данные методы обладают рядом существенных недостатков применительно к верификации параллельных систем. В настоящее время приобрел популярность другой метод формальной верификации- проверка моделей. Анализируемая программа представляется графом переходов. Вершины графа- глобальные состояния памяти компьютера, а ребра- локальные переходы из одного
состояния в другое согласно оператором программы. Логические аспекты, такие, как конечность, отсутствие взаимной блокировки, живость, выражаются формулами модального fi—исчисления и ее фрагмента темпорального исчисления с ветвящемся временем CTL.
Синтаксически формулы модального исчисления представляют собой индуктивно построенные выражения над символами операций (-, V, Л,
В работе [8] построено полиномиальное сведение вопроса выполнимости формулы модального исчисления к решению циклических игр с симметрическим платежом по циклу. Легко показать сводимость задачи выполнимости формулы темпорального исчисления к решению циклических игр с максимальным платежом по циклу. Таким образом, можно применить полученные результаты для вычисления значений формул модального и темпорального исчислений, а это важно в контексте построения надежных систем управления реального времени.
(с) Еще одним приложением циклических игр являются задачи построения оптимального расписания с логическими условиями предшествования. Стандартные условия- исполнение всех предшествующих работ (это соответствует логике "и"); во многих практических задачах начало работы возможно после выполнения хотя бы одной из предшествующей работы (это соответствует логике "или"). Показано, что задача построения расписания, минимального по времени с "и"/"или"логикой исполнения сводится к вопросу определения знака цены циклической игры с средним платежом по циклу. Поэтому и в данном случае циклические игры являются удобным средством анализа и оптимизации.
Апробация работы По теме диссертации сделаны доклады на семинарах в Вычислительном Центре РАН 1997, 2002 годах, в Институте Проблем Управления в декабре 1990 года и в институте Imag Artemis Grenoble в 1990.
Представлены доклады по тематике диссертации на конференциях, основные из которых следующие:
Lebedev V.N. Effective algorithm for solving one of two NP- complite tasks. The 2nd Moscow International Conference On Operations Research. Moscow. November 17-20 1998.
Лебедев B.H. Эффективные вероятностные алгоритмы решения одной
из двух NP-полных задач. Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики. "Нижний Новгород. 17-22 мая 1999.
Lebedev V.N. The complexity of the computation of maximin for square function. The 3rd Moscow International Conference On Operation Research. Moscow. April 4-6 2001.
Averbakh I.L., Lebedev V.N. On the comparison between discrete-scenario and interval data minmax regret optimization. ECCO XV. Conference of the European Chapter on Combinatorial Optimization, Lugano, Switzerland, May- June 2002.
Лебедев B.H., Черничкин M.C. Циклические игры и их приложения. Тезисы докладов 2-ой Московской конференции "Декомпозиционные методы в математическом моделировании и информатике". Москва. 21-24 июня 2004.
Публикации Основные результаты диссертации опубликованы в семи журнальных статьях издательства РАН, в трех иностранных журнальных статьях, в трудах Международных, Всероссийских и Региональных конференций и семинаров. Список публикаций приведен в конце автореферата.
Достоверность результатов l.Bce утверждения, корректность построенных алгоритмов строго доказаны.
Разработанные алгоритмы запрограммированы и тестированы. Вычислительные эксперименты показали их практическую эффективность. Алгоритмы проверены на модельной задаче преследования одного игрока другим на ограниченном отрезке с десятью позициями. Число итераций не превосходило двухсот- числа вершин в графе переходов этой игры (сама итерация квадратична от числа вершин).
Получены теоретические оценки сложности построенных алгоритмов.
Стационарные равновесия в циклических играх с максимальным платежом по циклу
Далее необходимы определения.
Стратегия общего вида - есть отображение, при котором очередной переход в вершине u(t) определяется всей предысторией w(0), u(l), ...u(t). Это не конструктивный объект, в контексте алгоритмической сложности нас будут интересовать стационарные стратегии.
Мы скажем, что первый применяет стационарную стратегию (3 в графе (В, А; Е), /3 : В -» Е(В), где /3(v) 6 E(v) для v Є В, если всякий раз, когда фишка попадает в вершину v Є В, первый передвигает ее по тому же самому ребру (3(v). j3:={ElCE(B,A):\E1\ = \B\ V и Є В 3 {v,w) Є Ег.} Для второго игрока стационарная стратегия а определяется аналогично.
Пусть Si, 5г будет множество всех стратегий первого и второго игроков в приведенной игре. Пусть T(si,S2,Vo) будет маршрут из начальной вершины VQ, который соответствует стратегиям Si Є S\ и S2 Є . игроков, и c(si,S2,vo) платеж этого маршрута. ТЕОРЕМА.
Для каждой игры (В,А;Е;с) с целочисленной платежной стоимостью с: Е — Z существуют стационарные стратегии /3 иа первого и второго игроков, что для любой начальной вершины и0 выполнено следующее условие равновесия: supc(0,s2,vo) =Mc(si,a,v0) := c(v0) c(v0) называют ценой игры в позиции VQ. Инфинум ( супремум ) берется по всем, не обязательно по стационарным стратегиям игроков. ОПРЕДЕЛЕНИЕ 2.
Мы скажем, что упорядоченное разбиение на непересекающиеся множества Vi,...,Vm вершин V называется эргодическим, если: a) для каждого г = 1,...,т граф G(Vi) беступиковый (G(Vi) обозначает подграф порожденный множеством Vi) b) для любых 1 і j т нет ребер (v, w), таких что v Є BOVj и w Є УІ; или v Є А П Vi uweVj.
Далее удобно ввести понятие веса цикла (некоторой функции, которая однозначно определяет величину, вес цикла по локальным платежам цикла). В данном параграфе используется максимальный вес. Вес простого цикла С : УО-.ЛІЬУО определяется как максимальный платеж по ребрам цикла: с(С) := тахс(е). 4 ееЕ v ОПРЕДЕЛЕНИЕ 3. Граф (В, А; Е(В, А), Е(А, В)) с целочисленной стоимостной функцией с : Е - Z называется равновесным с ценой J, если существуют две стационарные стратегии (3 и а первого и второго игроков, что справедливо следующее: 1. Веса всех простых циклов графа (В, А; 0, Е(А, В)) не больше J. 2. Веса всех простых циклов графа (В,А;Е(В,А),а) не меньше J. (В,А;Р,Е(А,В)) есть граф с множеством вершин В U А и множеством ребер /3 U Е(А, В), мы кратко обозначаем этот граф как (V; J3), для второго графа обозначение - (V;a). Легко видеть, что цена игры для любой начальной вершины г;0 равновесного графа есть J, и /?, а две равновесные стационарные стратегии первого и второго игроков из теоремы. Теорема будет непосредственно следовать из леммы 1 и 2. ЛЕММА 1. Для каждого графа (V; Е) с целочисленной стоимостной функцией с : Е —Ь Z существует эргодическое разбиение У\...\% и возрастающая последовательность целых чисел J\ ... Jk, что граф G(Vi) равновесный с ценой Ji, і = 1,..., А;. Легко видеть, что цена игры для любой вершины і-ого графа v Є Vi есть J{, г = 1,..., А;. Лемма о расщеплении: ЛЕММА 2.
Пусть (В, А; Е) граф игры с целочисленной стоимостной функцией с: Е —ї Z, и пусть J произвольное целое число. Тогда существуют эргодическое разбиение: (1) Vi,V2 (возмооїсно V\ = 0 или V2 = ) и две стационарные стратегии (3\, а2 для G(V\) и G(V2) соответственно, такие что следующее справедливо: (2) веса всех простых циклов графа (Vj;/?i) не больше J — 1; (3) веса всех простых циклов графа {у2; а2) не меньше J. Обозначим А\ := Vi П Л; В\ := V\ Г] В. Аналогично А2; В2. Первый игрок гарантирует свои потери не более J — 1, если он применит стационарную стратегию /?і в графе G(Vi). Точно также второй игрок обеспечит себе выигрыш не менее «7, если применит стационарную стратегию а в графе G(V2).
Стационарные равновесия в циклических играх с симметрическим платежом по циклу.
Из доказательства основного утверждения следует, что строение стационарных равновесных поведений игроков достаточно описать в одном равновесном блоке следующим образом: 1. Для первого игрока:
Множество вершин v произвольного блока из леммы с ценой J можно разбить на эргодическис классы Ci...Ci...Cs, где строение каждого класса одинаково, и поэтому опишем строение произвольного класса, который будем обозначать С. Класс С можно разбить на подклассы F0Fi...Fj...Ft (см.рис. 5)так, что:
a) G(F0)— нетупиковый, и для любой вершины v Є F0 : opt(v) J(opt(v) берется по ребрам с концами в Fo);
b) для каждой вершины і»д Є Fj, j = 1,..., t все переходы ведут в подклассы с меньшим номером %)C{FHU...UF0}; для каждой вершины VA Є Fo все переходы ведут в Fo V(vA) С F0; для каждой вершины VB Є Fj j = 1,...,t найдется переход в подкласс Fj-\. Первый обеспечит себе платеж не больший J играя в подкласс с меньшим номером, а в подклассе Fo играя по любому оптимальному ребру ведущему в Fo.
2. Для второго игрока: Множество вершин блока с ценой J можно разбить на подклассы D\...Di... (рис. 6) так, что: a) для любой вершины v Є Д. : (opt(v) J (opt(v) берется по ребрам с концами в V); b) для каждой вершины ид Є А, г = 1, ...,г — 1 найдется переход в подкласс Д+1 : V(VA) П Di+i ф 0; РОССИЙСКАЯ ГОСУДАРСТВЕННАЯ! БИБЛИОТЕКА для каждой вершины VB Є Д, і = 1,..., г — 1 все переходы стоимости меньшей J ведут в подклассы с большими номерами. V"(«B) с{д+1и...ид}. Здесь V (vB): vA Є V(vD) и c(uB,iu) J. Второй обеспечит себе платеж не меньший J играя в подкласс с большим номером, а в подклассе Д играя по любому оптимальному ребру ведущему в V.
В данном параграфе представляется результат о наличии равновесия в игре с симметрическим по отношению к обоим игрокам платежом по траектории: с(Т) = "Hrnc(vt, vt+i) + Шпф(, vt+i). t-юо t- oo (Если стратегии игроков стационарны, то это-просто сумма максимального с(е) и минимального с(е) ребер цикла, на который выйдет игра. Для позиционного среднего в определении выше мы должны сумму разделить на два, тем не менее для сокращения записи коэффициент перед суммой будем опускать. )
Применяя метод форсирования критической позиции, мы получаем требуемые равновесия. В общем случае рекурсия алгоритма имеет только экспоненциальную верхнюю оценку трудоемкости, в случае эргоди ческих расширений матричных игр мы показываем полиномиалыюсть алгоритма.
Схема доказательства теоремы о наличии стационарного равновесия аналогична предыдущему параграфу, но проведение индуктивного перехода существенно усложняется в лемме о расщеплении следующего параграфа, кроме того для сокращения доказательства отдельно выносится утверждение 2.
Определения стационарной стратегии, эргодического разбиения, цены игры, равновесия в игре, равновесного графа далее аналогичны предыдущему парграфу. Пусть 5i, 5 будет множество всех стратегий первого и второго игроков в заданной игре. Пусть T(si,S2,Vo) будет маршрут из начальной вершины VQ, который соответствует стратегиям si Є 5i и s2 Є 5г игроков, и c(si,S2, г/о)-значение платежного функционала на этом маршруте.
Для каждой игры на графе (В, А; Е) с целочисленной стоимостной функцией с : Е — Z существуют стационарные стратегии (3 и а первого и второго игроков такие, что для любой начальной вершины vQ выполнено следующее условие равновесия: sup c(p,s2,v0) = inf c(si,a,v0) := c(v0) ( c(v0)-ufiim игры в позиции VQ.) Инфинум ( супремум ) берется по всем, не обязательно стационарным, стратегиям игроков.
Далее подграф, порожденный подмножеством вершин W С V, будет обозначаться как G(W).
Из определения эргодического разбиения следует: УТВЕРЖДЕНИЕ 1.
Пусть V\ и УЇ эргодическое разбиение V в графе G(V) и Уз, У\-эргодическое разбиение Уч в подграфе (3(). Тогда разбиение Vi U Уз,У\-эргодическое разбиение У в графе G(V). ОПРЕДЕЛЕНИЕ 1.
Граф (В, А; Е(В, A) U Е(А, В)) с целочисленной стоимостной функцией с: Е — Z называется равновесным с ценой J, если существуют две стационарные стратегии (3 и а первого и второго игроков, что справедливо следующее: 1. Веса всех простых циклов графа {В, А; (3 U Е(А, В)) не больше J. 2. Веса всех простых циклов графа {В, А; Е(В, A) U а) не меньше J. Граф (В, A; @UE(A, В)) кратко будем обозначать как (V; /?), для второго графа соответствующее обозначение - (V; а).
Корректность и конечная сходимость вспомогательного алгоритма
Ясно, что если при работе вспомогательного алгоритма осуществляется случай (рЗ), то есть было найдено правильное разбиение (V V") игровой сети, то для справедливости теоремы 1 достаточно доказать ее отдельно для каждого из блоков V, V". Неоднократным применением алгоритма можно найти потенциальное преобразование, для которого разность М — тп в каждом блоке преобразованной сети станет сколь угодно малой. Тогда ограничимся величиной М — тп = ЩЇТЇ И приведем сеть к такой разности разброса экстремумов вершин в каждом блоке сети. После этого, используя вспомогательный алгоритм, покажем, как привести сеть к виду, где выполнено условие: М — тп = 0 в каждом блоке нашей сети. Опять не ограничивая общности, будем считать, что мы имеем один блок с величиной разброса экстремумов 0 М — тп 1/2V2 = 1/2п2. МОДИФИЦИРОВАННЫЙ АЛГОРИТМ. ШАГ 1. Выбор числа р:
В данном алгоритме р— есть значение среднего цикла, на который мы выйдем, двигаясь из произвольной вершины сети по экстремальным ребрам. (В силу того, что J с —с" 1/п2 для двух различных по значению средних циклов с7 и с" в графе с целочисленными значениями ребер, имеем, что значение р однозначно). ШАГ 2. Применяя обычный вспомогательный алгоритм с данным значением р приведем сеть к виду, где или V = 0 или V+ = 0 . Ограничимся первым случаем и покажем, как перевести вершины из V+ в множество V0 , второй случай аналогичен первому и рассматриваться здесь не будет. ШАГЗ. Как и в ранее описанном вспомогательном алгоритме строится помеченное множество L со свойствами: (Ql) V+CLCV (Q2) veLnV0 = \V+(v)\ + \V(v) П L\ k{v). ШАГ 4.
Аналогично вспомогательному алгоритму определяется число 8, как максимальное, не нарушающее свойства монотонности и проводится сдвиг L, д. После чего в случае V+ ф 0 процедура алгоритма проводится с шага 3. Следует отметить, что всегда на шаге 3 будет найдено помеченное множество L такое что V — L ф 0. В противном случае не трудно показать наличие среднего цикла d : р+1/2п2 d р, что противоречит примечанию на предыдущей странице. Поэтому алгоритм корректен. Конечная сходимость алгоритма следует из утверждения аналогичного лемме 1.
ЛЕММА 2. Пусть па шаге 3 j—ой итерации были помеченные множества: Х0 = V+Xi...Xr и мнооїсества ребер: YQ Y\...Yr, где Yi = {uv :v Є X{,u eV - L( c(uv) p} і — 0,...,r. Будем ассоциировать с этой итерацией последовательность целых чисел q(i) = aoPo-ctrPr "І = A = - 5 і = 1» -,r, тогда q(j + 1) лексикографически меньше q(j), где q(j + 1) аналогичная последовательность для j + 1—ой итерации. Доказательство леммы 2 повторяет доказательство леммы 1 и приводиться здесь не будет. Из леммы 2 следует, что не более чем через п4п итераций V+ = 0, то есть ext(v) = р для любой вершины и Є V, что завершает доказательство теоремы 1.
Общее число обращений к вспомогательному алгоритму 0(nlog2(Mn)) и трудоемкость итерации вспомогательного алгоритма 0(п3), поэтому общая гарантируемая трудоемкость алгоритма п(пНод2М, М- максимальная по модулю локальная стоимость.
Частным случаем представленного результата является утверждение о равновесии в стационарных стратегиях в работе [17] для обычных циклических игр, а также хорошо известная из комбинаторной оптимизации задача поиска максимального среднего цикла в графе.
Именно, рассмотрим случай, когда множество вершин графа можно разбить на два непересекающихся класса А и В такие, что, если v Є А, то k(v) = 1, и если v Є В, то k(v) = \Е(у)\. Таким образом, в вершинах А право перевода фишки находится в распоряжении первого игрока, а в вершинах В в распоряжении второго игрока. Критерий игры остается тем же, что и в более общей постановке. Это циклическая игра с средним платежом по циклу, и теорема 1 переформулируется в этом случае следующим образом.
ТЕОРЕМА 2. Пусть имеется сеть (G = (V : А,В;Е;с). Тогда существует функция d эквивалентная с такая, что для чисел p(v) = ext(d, v) и любых v Є V будут выполнены следующие условия: (г) p(u)=p(v) uGV(d,v) (И) р(и) p(v) и Є V {d,v) (iiv) р(и) p(v) и Є V+(c ,v)
Из теоремы 2 видно, первый (второй) обеспечит себе выигрыш (проигрыш) не менее (не более) p(vo), если на своем ходе он перемещает фишку по ребру экстремальному, максимальному (минимальному) относительно d . Если такого правила придерживаются оба игрока, то для всех ребер возникающего маршрута будет выполнено: cf(viVi+i) = p(vi) = p(vi+i) = P(VQ) и, следовательно, выигрыш первого (проигрыш второго) равен p(v0). Из теоремы вытекает существование стационарных и равномерных стратегий для обоих игроков которые определяются как: a(v) = vu : и Є V(c , v) Vv Є A, /?(«) = vu : и Є V(cf, v) Vu Є В. Укажем еще одно следствие теоремы 2. ОПРЕДЕЛЕНИЕ 1.
Беступиковый граф G = (V, Е); V = В U В называется структурно эргодическим, если при любой стоимостной функции с все его вершины имеют одинаковую цепу в циклической игре с сетью (G = (V, Е), А, В, с). Примером структурно эргодического графа является симметричный полный двудольный граф с долями An В.
Алгоритм нахождения стационарного равновесия в стохастических играх специальной структуры
Здесь используются общепринятые обозначения работ по теории сложности вычислений, теории линейного программирования и теории гра-фов [1], [3], [19], [48].
Формулировка задачи структурная неэргодичность: ЗАДАЧА Задан ориентированный граф G = (V; Е), V = A U В без тупиков. Вопрос: существует ли эргодическое разбиение Vi, Уг вершин графа, то есть такое разбиение, что справедливо: VlUV2 = V, VlnV2 = Q, Уі#0, V2#0, для любой v Є Vi Г) В существует и Є V(v) П V\, для любой v Є Vi П А верно V(v) С Уь для любой v ЄУ2ПА существует и Є У (v) П V2, для любой v ЄУ2П В верно V{v) С У2.
Содержательно это означает: существует ли разбиение V\,V2 вершин, при котором в подграфе, порожденном множнством Vi, черные запирают белых, а в подграфе, порожденном множеством V2, белые запирают черных? Для доказательства NP— полноты этой задачи покажем NP— полноту следующей задачи 1. ЗАДАЧА 1 Задан ориентированный граф без тупиков G = (VE), V = A U В и две выделенные вершины х Є В и у Є А. Вопрос: существует ли эргодическое разбиение вершин V\, V2, при котором х eV2, ye V\. Сведем NP— полную задачу 2 монотонная 3-выполнимость (смотри [19] стр. 332) к задаче 1. Пусть имеется некоторая индивидуальная задача монотонная 3- выполнимость: ЗАДАЧА 2
Задано множество булевых переменных U : yi г = 1,..., \U\ и набор дизъюнкций С, С над U, такой что дизъюнкции множества С содержат только переменные без отрицаний, а дизъюнкции множества С содержат переменные только с отрицанием и као/сдая дизъюнкция содержит не более трех переменных. (Например, U : УІ,У2,УЗ,УІ , С : yi V т/г V у3; С : ух V у3 V у4.
Вопрос: существует ли для набора дизъюнкций выполняющий набор истинностных значений?) Будем обозначать г—ую дизъюнкцию множества С как с,-, і = 1,..., С , а г—ую дизъюнкцию множества Скак с;, г=1,...,С.
ЗАДАЧА 1: (1) Описание множества вершин V графа G = (V, Е) : Для каждой переменной у І Є U, і = 1,..., \U\ введем вершину произвольного цвета, например, белого и обозначим ее уі Є А, г = 1,..., \U\. Для каждой дизъюнкции С{ Є С введем белую вершину и обозначим ее: І Є А, г = 1,..., \С\. Для каждой дизъюнкции с; Є С введем черную вершину и обозначим ее: с Є В, г — 1,..., \С\. Введем две выделенные вершины у Є А и х Є В. (2) Описание ребер Е графа G. Для каждой вершины уг- Є А, і = 1,..., \U\ введем петлю (УІУІ) Є Е. Для каждой вершины с Є А, г = 1,..., \С\ и у Є y(cj) (у(с ) : {у, Є А : переменная у,- входит в дизъюнкцию Cj}) введем ребро (сіу1). Для каждой вершины СІ Є В, і = 1,..., \С\ и у Є у(й) (у(с ) : {у, Є Л : переменная yj входит в дизъюнкцию с }) введем ребро (СІУ ). Для отмеченной вершины х Є В и каждой вершины ct-, г = 1,..., \С\ введем ребро (ХСІ).
Для отмеченной вершины у Є А и каждой вершины с , г = 1,..., \С\ введем ребро {уСі). Например, для С : уі V уг V уз С : Уі V у3 V у4 граф имеет вид: ЛЕММА 1. Набор дизъюнкций индивидуальной задачи 2 выполним тогда и только тогда, когда для соответствующего графа G существует эргодиче-ское разбиение Vi, V2, при котором х Є V2, у Є V\.
ДОКАЗАТЕЛЬСТВО. Пусть набор дизъюнкций выполним. По выполняющему набору истинностных значений построим следующее разбиение Vi, V2: Если переменная yi = О, отнесем уі в V\. Если переменная г/, = 1, отнесем у І В V . Все вершины Cj, г = 1,..., \С\ и вершину х отнесем в V . Вершины СІ, і = 1,..., \С\ и вершину у отнесем в Vi. Докажем, что Vi, V2 - эргодическое разбиение.
Очевидно, что Vi и V2 = V, Vi П V2 = 0, Vi 0, V2 0. (a) для вершины х Є В(у Є А) имеем V{x) С V2 (V(y) С Vi), (b) для вершины СІ, і = 1,..., \С\ существует у Є у(сі) и у Є Vi так как найдется переменная дизъюнкции Cj такая, что в выполняющем наборе эта переменная имеет значение 0, а поэтому соответствующая вершина лежит в V\. Аналогично для вершины с , г = 1,..., \С\ существует у1 Є y(ci) : У Є V2. (c) для вершины УІ, і = 1,..., \U\ условия эргодичности выполнены. Поэтому первая часть леммы доказана. (2) Пусть в графе G = (V; Е) существует эргодическое разбиение Vi, V2, при котором iG i У Є V\. Тогда построим набор истиностных значений следующим образом: Уі = 0, если уі Є V\ и уі = 1, если уі Є V2. Докажем, что построенный набор выполнит все дизъюнкции С, С.
