автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Структура и поиск стационарных управлений в циклических играх с полной информацией

на правах рукописи

ЛЕБЕДЕВ ВАСИЛИЙ НИКОЛАЕВИЧ

I

СТРУКТУРА И ПОИСК СТАЦИОНАРНЫХ УПРАВЛЕНИЙ В ЦИКЛИЧЕСКИХ ИГРАХ С ПОЛНОЙ ИНФОРМАЦИЕЙ

05.13.01 системный анализ, управление и обработка информации

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

»

ВОЛГОГРАД 2005

Диссертация выполнена в Волгоградском Государственном Университете.

Официальные оппоненты: д.ф.-м.н., профессор Опойцев В.И. д.ф.-м.н., профессор Цурков В.И. д.ф.-м.н., профессор Язенин A.B.

Ведущая организация Институт Системного Анализа РАН.

Защита состоится 21.10.2005 на заседании диссертационного совета Д 212.263.03 при Тверском Государственном Университете по адресу 170000 г.Тверь, ул.Желябова, 33.

С диссертацией можно ознакомиться в библиотеке Тверского Государственного Университета.

Автореферат разослан..................

диссертационного совета В.Н.Михно

Ученый секретарь

Ни

I Общая характеристика работы.

Актуальность.

В диссертационной работе рассматриваются задачи динамических конфликтов с предельным во времени платежом по траектории. Задачи такого рода возникают в различных процессах принятия решений, имеющих место при управлении техническими и экономическими системами, при распределении запасов, при составлении графиков расписаний. В условиях полной информации имеем хорошо известную задачу оптимального управления в непрерывной или дискретной постановке. Такие проблемы нашли решение в классических работах Л.С.Понтрягина, Р.Беллмана и ряде других.

Практическая актуальность исследований данной работы обусловлена следующими факторами.

Во- первых в приложениях существенным является неопределенность параметров управляемой динамической системой, и такие задачи менее изучены. Управление в условиях стратегической неопределенности в контексте принципа гарантированного результата сводится к решению динамического, антагонистического конфликта с полной информацией. При этом считаем, что выбор неопределенных параметров осуществляет противник, цель которого противоположна основной целе управляющего объекта.

Во- вторых, как правило, управление осуществляется в реальном времени, и требуется мгновенный отклик управляющего объекта на любое отклонение от заданных параметров или от заданной траектории.

В- третьих, важным является большая размерность решаемых задач. Например, многоотраслевы модели экономического развития содержат тысячи параметров. Проблемы верификации программ требуют отслеживать каждый бит памяти компьютера. В задачах кодирования информации также проблема размерности является основной.

Теоретическая актуальность исследований заключается в следующем. Хотя вопросы вычислительной сложности в условиях определенности хорошо изучены, эти вопросы для детерминированных конфликтов даже с полной информацией являются недостаточно изученными. В основном результаты о наличии стационарного равновесия получены с помощью неконструктивной техники топологических теорем о неподвижной точке, типа теоремы Брауэра, либо проводится экспоненциальная индукция.

Подтверждением этого является следующий короткий обзор полученных ранее утверждений и неэффективные оценки сложности вытекаю-

щих из их доказательства алгоритмов.

Рассмотрим формализации стохастических игр, которые предложены Л.С.Шепли в [13].

Это игра двух лиц на конечном множестве позиций V. В позиции у € V разыгрывается матричная игра С (у) размером т(у),п(у). В позиции V первый игрок выбирает строку г, а второй столбец ] независимо друг от друга. Тогда с вероятностью р'}(у, ги) игра перейдет в очередную позицию ги и первый платит второму с^ (у) или с вероятностью в > 0 игра завершается р) {у, ш) + в — 1 для каждых V, г, ]; игроки имеют право применять и случайный выбор строк-столбцов).

Цель первого игрока состоит в минимизации суммарного ожидаемого платежа, а цель второго- максимизация. Описанная выше игра называется стохастической игрой с дисконтированием е.

Обшие стратегии в рассматриваемой игре, зависимые от предыстории. Это сложный комбинаторный объект, даже чистые стратегии не имеют конечного представления. Оказывается, игрокам достаточно ограничиться стационарными (марковскими) стратегиями, когда выбор строки, столбца в любой текущей позиции не зависит от предыстории. В [13] йоказано наличие равновесия в стационарных стратегиях в представленной игре (более точно, если одного из игроков ограничить только стационарными стратегиями, а противнику разрешить играть нестационарно, то это не ухудшит положение игрока).

Решение стохастических игр с дисконтом сводится к поиску неподвижной точки оператора, который порожден заменой матриц платежей С (у) ценой соответствующей игры. В силу наличия дисконта такой оператор оказывается сжимающим, поэтому последовательное итерирование оператора имеет геометрическую скорость сходимости к неподвижной точке. В силу полиномиалыюсти решения матричных игр из описанной схемы следует псевдополиномиальный алгоритм приближенного решения стохастических игр с дисконтом (дисконт может быть близким к нулю). Равновесная пара стационарных стратегий определяется неподвижной точкой представленного оператора. Псевдополиномиальности для гарантированной эффективности алгоритма недостаточно (для двоичной системы представления чисел в памяти машины такой алгоритм экспоненциален по времени счета).

Игры с нулевым дисконтом и средним предельным платежом по бесконечной траектории рассмотрены в работах [9], [14], [11]. Во-первых, показано наличие равновесия в стратегиях общего вида и отсутствие рав-

новесия в стационарных стратегиях [11]. Во-вторых, для эргодических игр и игр с полной информацией доказано наличие стационарного равновесия (первый случай тот, когда марковская цепь, порожденная любой парой стационарных стратегий, есть в точности один эргодичесий класс позиций; второй случай тот, когда в любой позиции V один из противников имеет одну строку, столбец, т.е. либо т(у) = 1, либо п(у) = 1) [9], [14]. Доказательство последнего результата проведено аппроксимацией рассматриваемых игр соответствующей стохастической игрой с малым дисконтом. В случае игр с полной информацией гарантируется наличие равновесия в чистых стратегиях [9], [14]. Результирующий алгоритм также имеет псевдополиномиальную оценку.

Заметим, что для эргодических игр утверждение о наличии стационарного равновесия можно получить, используя результаты Какутани о неподвижной точке точечно- множественных отображений (это следует из представления множества оптимальных стационарных стратегий игрока при фиксированной стратегии противника как решение задачи линейного программирования, коэффициенты которой непрерывно зависят от вероятностей смешанной стратегии противника).

Случай детерминированных {р'(ь,и= 0,1 для любых игр

с полной информаций является основным предметом данной работы Удобно следующее графовое представление.

Динамическая система с конечным множеством состояний V существует в дискретном времени t = 0,1,..., находясь в каждый момент времени в одном из состояний и{1) € V системы [6]. Динамика системы описывается ориентированным графом переходов С? = (V; Е), V— вершины, Е— ориентированные ребра. Ребро (кг>) 6 Е означает возможность перехода из состояния и(г) 6 V в состояние «(£ +1) € V в момент I функционирования системы. На ребрах Е задана целочисленная функция с локальных платежей переходов. Множество V состояний системы разбито на два непересекающихся подмножества А и В (АиВ = V-, АпВ = 0), так что выбор перехода у € У(и) (здесь У(и)— обозначены состояния V, достижимые за один шаг из состояния и) находится в нашем распоряжении лишь при условии принадлежности позиции и к множеству А контролируемых позиций. Исходя из принципа гарантируемого результата, считаем, что в позициях и € В выбор перехода осуществляется противоборствующей стороной, называя позиции V € В позициями первого игрока, а позиции V 6 А - позициями второго игрока.

Любая пара стратегий игроков в^.вв (очередной переход в вершине

u(t) определяется предысторией u(0),w(l), ...u(t)) однозначно порождает некоторую бесконечную траекторию: T(sa,Sb) : f(0), v(l),...

Тогда критерием качества является некоторый стоимостной функционал, определяемый по локальным платежам этой траектории. В работе рассмотрены функционалы типа средних:

(a) c{T{sA,ав) = Tjm (S с(и(т), и[т + 1))) / t,

(b) c(T(sA, Sg)) = TImс(щ, 1),

l—»OO

(c) c(T(sA, sB)) = limc(uu ut+1) + lim c(uu ut+1).

J t-KX

Таким образом, при возникшей траектории T(sA, s в) платеж первого игрока второму - есть величина с(Т($а,$в)), в минимизации которого состоит задача управления первого и в максимизации которого состоит задача управления второго игрока. Наличие равновесия в стратегиях общего вида можно показать сведением к циклической игре. Циклической игрой называют игру, которая проходит по ребрам графа до первого цикла щ,.,., иг,..., ик, и,. То есть, как только траектория игры попадает в позицию, где была ранее, игра завершается. Платеж первого игрока второму есть соответствующий платеж типа среднего:

{a)c(T{sA.sB)) = {tc(u(t),u{t + 1))) / к-г + 1,

Т=1 '

(b) c(T{sA. s в)) = maxT=v. с{и(т), и{т + 1)),

(c) c(T{sA, s в)) = maxT=l, с{и{т),и(т +1)) + rnin^,,. c((w(r), u(r + 1)). Здесь u(k +1) есть позиция и(г). Платеж (а) будем называть средним по циклу, (Ь)- максимальным, (с)- симметрическим.

По теореме Цермело следует существование равновесия в стратегиях общего вида в редуцированной циклической игре (циклическая игра -конечная). Более точно, существует пара чистых стратегий общего вида первого и второго игроков sB, sA, что для каждой начальной позиции и(0) и для любых стратегий первого и второго игроков sB, sA, выполнены условия седла:

с(и(0), 8Л, з*в) < с{и(0), а*А, а*в) = р(и(0)) < с(и(0), а'А, ав)

Здесь c(ti(0), sA, s в)- значение цикла, возникшего согласно стратегиям sA,sB игроков из начальной позиции и(0); р(и(0)), называют ценой циклической игры в позиции и(0).

Таким образом, пара стратегий sA,sB- равновесна, т.е. ни одному из игроков не выгодно уклоняться от своей стратегии при фиксированной

стратегии противника.

Последовательным удалением циклов из бесконечной траектории полученные равновесные стратегии з"л, з*в доопределяют до стратегий в первоначальной бесконечной игре, и это есть равновесная пара чистых стратегий общего вида в первоначальной бесконечной игре. Недостатком этого результата является экспоненциальное представление полученных равновесных стратегий. Хотя доказательство и конструктивно, но не может быть использовано на практике- алгоритм экспоненциален.

Как отмечалось, в бесконечной игре с полной информацией и предельным средним платежом (а) существует равновесие и в чистых, стационарных стратегиях [9]. Более точно, существует пара чистых стационарных стратегий первого и второго игроков з*А, что для каждой начальной позиции и(0) и для любых стратегий первого и второго игроков вв, ва, выполнены условия седла:

с(и(0), зА, з*в) < с(и(0), з% з*в) = р(и(0) < с(и(0), з*л, зв)

Здесь с(и(0), за, вд)- платеж (а) по бесконечной траектории; а стационарные стратегии есть отображения вида:

«в : и —> У(и) для всех и € В,

вд : и —► У(и) для всех и € А.

(последнее утверждение непосредственно переносится на конечные циклические игры).

Специальные методы решения представленных динамических, детерминированных игр в основном используют технику альтернирования, как в конструктивном доказательстве наличия равновесия в позиционных играх с полной информацией [15]. В работе [7] дано первое топологически независимое доказательство наличия стационарного равновесия, из которого следует экспоненциальный алгоритм решения игры.

В работах [4], [16] рассматривался вопрос сложности решения бесконечной игры (а). Представлена аппроксимация такой бесконечной игры конечной за 4 = 1,... шагов. Показано, что цена конечной игры за t шагов из начальной вершины р((и(0)) стремится к цене в бесконечной игре р(и(0)) при £ —> оо и получена скорость сходимости:

I й(и(0)) - р(и(0) |< 2МпЦ

Здесь М-максимальная по модулю локальная стоимость перехода, п-число вершин в графе перехода.

Игра за t шагов максминной процедурой сводится к t — 1 шаговой игре за линейное время, что дает приближенный псевдополиномиальный алгоритм решения бесконечной игры. В силу того, что две различные величины средних циклов (в графе с целочисленной платежной функцией) отличны по крайней мере на 1/п2, для точного решения бесконечной игры достаточно решать конечную игру за t — 2п3М шагов. Оценка сложности алгоритма- Mpoly(n).

Для представленного алгоритма несложно построить пример игровых сетей с двумя вершинами с достижимой псевдополиномиальной оценкой их работы.

Метод потенциальных преобразований представлен [1].

Было замечено, что циклическая игра обладает богатой группой эквивалентных, потенциальных преобразований, которые ие меняют суммарных длин циклов, поэтому не меняют игры. Показано, что всегда существует конечная последовательность элементарных потенциальных преобразований- сдвигов, которая приводит игру к тривиальному виду, когда граф распадается на две компоненты- в первой компоненте величины локальных экстремумов вершин отрицательные (оптимальный платеж игрока за один ход), во второй- неотрицательные; в первой компоненте игру оставляет первый игрок (в любой вершине первой компоненты первый игрок имеет экстремальный переход, ведущий в эту же компоненту, а у второго игрока во всех вершинах первой компоненты все переходы ведут в первую компоненту ); во второй компоненте игру оставляет второй игрок. Тогда минмаксные стационарные стратегии игроков гарантируют первому отрицательный платеж в первой компоненте и второму неотрицательный платеж во второй компоненте. Заметим, что решение циклических игр с платежом типа средних полиномиально эквивалентно определению знаков цен. Поэтому эффективный поиск приведенного выше тривиального вида игры дал бы полиномиальный алгоритм решения игры.

Но искомая последовательность преобразований- сдвигов экспоненциальна в худшем случае.

Оценка сложности алгоритма потенциальных преобразований

тгп{Мро1у(п), 2ро1у("Чод2М}. Здесь М- максимальная по модулю стоимость вершин, п- число вершин игровой сети; poly(n)- полином небольшой степени. В работе [5] представлены достижимые примеры и обобщения.

Замечательным свойством представленных игровых задач является

их принадлежность классу NPПco—NP (это непосредственно следует из наличия равновесия в стационарных стратегиях), поэтому при условии ИР ф со—ЫР, доказать ЫР-полноту проблемы определения победителя в рассматриваемых циклических играх (Ь), (с), (с!) невозможно.

Обзор по сложности решения представленных игр заканчиваем общими методами нелинейной оптимизации. Рассматриваемая проблема представима задачей нахождения максмина линейного функционала с линейными ограничениями, связующие переменные. Разработаны методы сведения такой задачи к задаче квадратичного программирования I на линейном многограннике. Сведение проводится с помощью штраф-

ных функций и соотношений двойственности. Существенным для эффективности вычислений является фиксированность коэффициента штрафа ^ при редукции к задаче квадратичного программирования. Для задачи

квадратичного программирования развиты практически быстрые алгоритмы решения, что в сочетании с полиномиальной редукцией дает эффективный практический метод решения рассматриваемых игр, но без гарантированной оценки трудоемкости этих алгоритмов. Отрицательной стороной такого подхода является тот факт, что задача поиска максмина линейного функционала с линейными ограничениями, связующие переменные, является ЖР-трудной проблемой.

Другим общим способом решения является подход, связанный с поиском неподвижной точки некоторого максминного оператора. Поиск такой точки можно проводить с помощью вычисления вращения, как некоторого многомерного интеграла. Трудности такого подхода связаны с тем, что в общем случае приближенное вычисление объема многогранника является РБРАСЕ-полной проблемой и, по всей видимости, не имеет эффективного алгоритма.

Итак, из представленного обзора современных методов решений циклических игр следует, что они неэффективны и не позволяют решать практические задачи большой размерности. Эти обстоятельства, а также перечисленные факторы являются обоснованием актуальности темы диссертации.

Цель работы.

1. Основной целью работы является построение эффективных алгоритмов отыскания и описания структуры оптимальных стационарных равновесий в дискретных, динамических, конфликтных ситуациях с предельным во времени платежом. Требования на разрабатываемые алгоритмы следующие. Оценка затрачиваемого временного ресурса прово-

дится на самый худший вариант, то есть исходим из концепции гарантированного результата. Эффективным считаем тот алгоритм, верхняя оценка числа элементарных битовых операций- есть полином небольшой степени от длины записи исходной задачи в памяти машины. Экспоненциальная верхняя оценка сложности еще не является формальным основанием неэффективности алгоритма. В этом случае требуется показать достижимость этой оценки по экспоненциальному порядку. Во многих случаях проблема аналитической оценки времени работы алгоритма довольно сложная алгебраическая задача. Достаточно вспонить, что непо-линомиальность симплекс- метода была доказана лишь через тридцать лет после разработки алгоритма. Практическим эффективным алгоритмом называем тот, для которого проведенное тестирование на модельных примерах дает приемлемое время, близкое к линейному.

2.Практические задачи всегда обладают некоторой особенностью, и поэтому в условиях, когда отсутствует полиномиальный алгоритм решения общей задачи, важно выделение полиномиально разрешимых подклассов общей задачи.

3.Другим аспектом исследований диссертации является проблема обобщения. Известен результат наличия равновесия в стационарных стратегиях для среднего предельного платежа по траектории. Теперь будем рассматривать произвольные функционалы стоимости по траектории. Спрашивается, какими свойствами должен обладать функционал, чтобы осталось в силе утверждение о наличии стационарного равновесия. При этом важно выявить грань полиномиальности задачи при такой функциональной параметризации.

4.И последний аспект целей диссертации является качественный анализ дискретных, динамических, детерминированных конфликтов с полной информацией. Здесь выделяется проблема определения структуры равновесных стратегий и выявление их свойств, таких как стационарность или эргодичность цен.

На защиту выносятся следующие концепции- положения и результаты.

Основным результатом работы является новый метод в теории дискретных динамических конфликтов- структурное представление седловых равновесий с помощью концепции форсирования критической позиции.

1. Доказано, что операцией дополнения шлейфа можно получить любую игровую сеть с заданной ценой. Это дает качественное представление о структуре равновесных стратегий, выявляет их важные свойства-

стационарность, независимость от начальной позиции и эргодичность цен.

2. С помощью форсирования критической позиции удалось получить ранее неизвестные утверждения существования стационарных равновесий в играх с позиционными средними (Ь), (с) и ряде других.

3. Конструкция форсирования критической позиции дает полиноми-альность решения игр (Ь) и существенных подклассов (с)- для графов, все сильносвязные компоненты которых сильноэргодические и в случае фиксированного приоритета стоимостной функции.

4. Получен полиномиальный алгоритм характеризации всех максимальных средних циклов в ориентированных графах. Алгоритм за полиномиальное время находит подграф, циклы которого есть в точности все максимальные средние циклы в исходном графе.

5. С помощью техники сжимающих отображений получен псевдополиномиальный алгоритм для решения стохастической игры эргодиче-ской структуры. Из этого результата непосредственно следует псевдополиномиальная оценка алгоритма потенциальных преобразований.

6. Метод потенциальных преобразований обобщен на случай игр с отказами. Проведен тщательный анализ его сложности. Показана его экспоненциальная верхняя оценка и приведен класс игр, на которых эта оценка достижима Тестирование метода показало его практическую эффективность.

7. Техника форсирования использована для вычисления формул модального исчисления. Выявлены полиномиально разрешимые классы для данной общей проблемы:

(a) определение выполнимости формул модального исчисления со свойством сильной эргодичности;

(b) определение выполнимости формул с фиксированным числом альтернаций операторов наименьшей и наибольшей неподвижных точек;

(c) вычисление значения формул на почти ациклических Крипке- графах.

Научная новизна.

1. В самой диссертационной работе проведен анализ новизны полученных результатов. Естественность вопроса о новых равновесиях возникает в контексте того, что рассмотрены критерии типа средних. Поэтому ставится вопрос, нельзя ли свести полученные утверждения о существовании равновесия к известному среднему. Оказывается в классе преобразований сохраняющих порядок циклов относительно этих критериев

такого сведения не существует. В классе более тонких преобразований сведение существует, но во многих случаях оно нетривиально, как для медианы. При этом доказательства и следующие из них алгоритмы существенно отличны. Для симметрического и максимального платежей техника потенциальных преобразований не работает- потенциальные преобразования при таких критериях меняют длины циклов. Имея только алгоритм дотенциальных преобразований, невозможно было бы получить полиномиальность решения игр с максимальным платежом по циклу и полиномиальность выделенных классов с симметрическим платежом.

2.Для игр с отказами построенный алгоритм использует известную технику потенциальных преобразований, но доказательство его конечности потребовало рассмотрения новых комбинаторных структур.

3.Существенной новизной является характеризация циклических игр с заданной ценой и выявление структуры оптимальных стационарных стратегий. В случае игр с максимальным платежом удалось описать структуру стратегий явным образом, как некоторый подграф- шлейф. В случае симметрического платежа описание проводится с помощью конечного числа операций дополнения подграфов- шлейфов. Последний результат дает качестное представление о свойствах оптимальных стратегий.

Доказанные в работе утверждения, данные без ссылок на другие источники, являются новыми. Из результатов опубликованных в соавторстве в работу вошли только те, которые получены лично диссертантом.

Практическая значимость.

Полученные результаты имеют важное практическое значение для решения следующих задач.

(а) Задача оптимального управления развивающейся экономикой в условиях параметрической неопределенности.

Состояние экономической системы определяется набором некоторых показателей. Состояния разделяются на контролируемые, где экономические показатели детерминированы субъектом принятия решения, и на неконтролируемые, где показатели недетерминированы, известна только некоторая информация о них. Динамика описывается некоторой структурой-графом, переход из одного состояния в другое означает возможность управления за единичный временной лаг, при котором система, действительно, совершит данный переход, Причем, в понятие совершит включаются общие рэндомизированные возможности поведения системы. За несколько временных лагов в результате определенных управленческих

решений система пройдет некоторую траекторию переходов. Причем, переход системы в очередное состояние находится в распоряжении лица, принимающего решение только в контролируемых состояниях. Каждый переход дает определенный выигрыш (или проигрыш) лицу принимающему решение. В максимизации (или минимизации) общего выигрыша типа средних и состоит задача управления. Мы рассматриваем асимптотическую задачу управления системой на бесконечном интервале времени, поэтому общие выигрыши берем средними в расчете на один ход. Поведение системы в неконтролируемых состояниях неоднозначно, поэтому поставленная задача управления некорректна. Исходя из прин-) ципа гарантируемого результата, будем оценивать поведение системы в

неконтролируемых состояниях.

В случае гарантированного результата считаем, что в неконтроли-* руемых состояниях переход системы осуществляется противником, цель

которого противоположна цели лица, принимающего решение, т.е. целью является минимизация (максимизация) общего выигрыша типа средних. Такая постановка корректно интерпретирует как ситуацию двусторонней монополии (т.е. при которой единственный продавец сталкивается с единственным покупателем), так и конкуренцию дуополии, когда одна из двух конкурирующих фирм играет на разорение другой.

В представленной динамической модели конкуренции показано наличие равновесия, которое является оптимальным поведением фирм. Этот результат качественно описывает положение гомеостазиса, когда ни одному из участников конфликта не выгодно уклоняться от своего поведения при фиксированном поведении противника. Найденные равновесные поведения противников структурно определяются порогом локального выигрыша, которого тот или иной противник форсированно добивается.

(Ь)Задача построения надежных динамических систем управления. При разработке компьютерных программ особое значение приобретает проверка корректности функционирования, что является основой их надежности. До недавнего времени для этих целей использовались такие методы, как тестирование прототипа, а также формальная верификация с помощью математических доказательств. Данные методы обладают рядом существенных недостатков применительно к верификации параллельных систем. В настоящее время приобрел популярность другой метод формальной верификации- проверка моделей. Анализируемая программа представляется графом переходов. Вершины графа- глобальные состояния памяти компьютера, а ребра- локальные переходы из одного

состояния в другое согласно оператором программы. Логические аспекты, такие, как конечность, отсутствие взаимной блокировки, живость, выражаются формулами модального fi—исчисления и ее фрагмента темпорального исчисления с ветвящемся временем CTL.

Синтаксически формулы модального исчисления представляют собой индуктивно построенные выражения над символами операций (->, V, А, <R>, [Я], ц, и). Семантически формуле соответствует отображение из множества вершин Крипке- графа в множество вершин этого же Крипке-графа состой'нйй Основная задача- определить значение формулы на заданном значении переменных.

В работе [8] построено полиномиальное сведение вопроса выполнимости формулы модального исчисления к решению циклических игр с симметрическим платежом по циклу. Легко показать сводимость задачи выполнимости формулы темпорального исчисления к решению циклических игр с максимальным платежом по циклу. Таким образом, можно применить полученные результаты для вычисления значений формул модального и темпорального исчислений, а это важно в контексте построения надежных систем управления реального времени.

(с) Еще одним приложением циклических игр являются задачи построения оптимального расписания с логическими условиями предшествования. Стандартные условия- исполнение всех предшествующих работ (это соответствует логике "и"); во многих практических задачах начало работы возможно после выполнения хотя бы одной из предшествующей работы (это соответствует логике "или"). Показано, что задача построения расписания, минимального по времени с "и"/"или"логикой исполнения сводится к вопросу определения знака цены циклической игры с средним платежом по циклу. Поэтому и в данном случае циклические игры являются удобным средством анализа и оптимизации.

Апробация работы По теме диссертации сделаны доклады на семинарах в Вычислительном Центре РАН 1997, 2002 годах, в Институте Проблем Управления в декабре 1990 года и в институте Imag Artemis Grenoble в 1990.

Представлены доклады по тематике диссертации на конференциях, основные из которых следующие:

1. 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.

2. Лебедев В.H. Эффективные вероятностные алгоритмы решения одной

из двух NP-полных задач. Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики. "Нижний Новгород. 1722 мая 1999.

3. 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.

4. 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.

5. Лебедев B.H., Черничкин M.C. Циклические игры и их приложения. Тезисы докладов 2-ой Московской конференции "Декомпозиционные методы в математическом моделировании и информатике". Москва. 21-24 июня 2004.

Публикации Основные результаты диссертации опубликованы в семи журнальных статьях издательства РАН, в трех иностранных журнальных статьях, в трудах Международных, Всероссийских и Региональных конференций и семинаров. Список публикаций приведен в конце автореферата.

Достоверность результатов l.Bce утверждения, корректность построенных алгоритмов строго доказаны.

2. Разработанные алгоритмы запрограммированы и тестированы. Вычислительные эксперименты показали их практическую эффективность. Алгоритмы проверены на модельной задаче преследования одного игрока другим на ограниченном отрезке с десятью позициями. Число итераций не превосходило двухсот- числа вершин в графе переходов этой игры (сама итерация квадратична от числа вершин).

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

Краткое содержание диссертации

Разработанный метод исходит из стратегии альтернирования для форсирования выигрыша в позиционных играх с полной информацией, но применительно к циклическим играм существенно усложняется, как, например, для максимального платежа по циклу (Ь). В этом случае применение этого метода позволило получить индукцию с развалом игры на две, в одной из которых решение игры очевидно, в другой конструкция применяется рекурсивно.

Метод для случая максимального платежа по циклу представлен в 1-й главе работы.

Второй, максимизирующий, игрок задается некоторым целым / и пытается определить начальные позиции, из которых он форсированно, т. е. независимо от игры противника, добьется перехода (иу) стоимости с(иь) > 3 (мы применяем нотацию позиционных игр, таких как шахматы, семантически эквивалентно форсированию применять термин гарантирование),

Ясно, что эти позиции можно получить следующим образом.

Во-первых, это позиции Хо : ех№(и) > 3 (еаЯг {и) - есть тах„6у(и) с(и, у), если и е А и тт„6у(и) с(и,и), если и 6 В).

Во-вторых, это позиции Хх : и £ А, из которых существует переход в А'о и позиции и В. в которых все переходы (гш) : с(иг>) < 3 ведут в Хо-

В-третьих, это позиции Х2 : и 6 А, из которых существует переход в Х-1 и позиции и € В, в которых все переходы (гш) : с(гш) < 3 ведут либо в Х0, либо в Хг, и так далее (см. рис. Ь).

В результате получим последовательность непересекающихся блоков позиций Х0,..., X,,..., X* таких, что в любой позиции второго игрока блока X, существует переход в блок с меньшим номером Хг_ь а в любой позиции первого игрока блока X, все лучшие для первого игрока переходы (иу) : с(иу) < 3 ведут в блоки с меньшими номерами Х0 и ... и Х,_ь В блоке Х0 у второго игрока найдется требуемый переход (иу) : с{иу) > 3, а у первого все переходы в блоке Хо больше, либо равны 3. Тогда для любой начальной позиции из перечисленных блоков второй игрок действительно форсированно добивается перехода (иу) : с(иу) > 3, играя на своем ходе в блок с меньшим номером, а в блоке Х0 по ребру (иу) : с(иу) > 3. При этом противник в текущем блоке либо совершит переход (цу) ■ с(иь) > 3, либо перейдет в блок с меньшим номером, а в блоке Х0 у первого все переходы (иу) . с (иу) > 3 (см. рис.(Ь)).

Если разбиение Хо, ...,Х/ь покрывает все позиции V игровой сети, то второй игрок, согласно указанной стратегии, форсирует более того цикл с переходом (иу) : с(иу) > 3, так как любой цикл будет содержать переход из г-го блока в блок с неменьщим номером, а это переход стоимости большей, либо равной 3. В этом случае второй игрок имеет стационарную стратегию, дающую ему выигрыш больший, либо равный 3 в любой начальной позиции игры.

Если разбиение Хо, -.., Х* не покрывает всех позиций V, то в подграфе, порожденном остатком вершин V — {Хо и ... и X*}, первый игрок

форсирует цикл с платежом менее чем 7. В этом подграфе все переходы из позиций второго игрока ведут в этот же подграф и имеют стоимости меньшие, либо равные 7 — 1, а для позиций первого игрока найдется переход со стоимостью меньшей, либо равной / — 1 в этот же подграф. Так как все собственные переходы первого игрока имеют стоимость меньшую, либо равную 7 — 1, и все переходы второго игрока имеют стоимость меньшую, либо равную 7—1, то и стоимость любого возникающего цикла в этом подграфе меньше, либо равна 7 — 1.

Таким образом, либо будет найдена стационарная стратегия второго игрока, дающая ему платеж по крайней мере 7 для любой начальной позиции, либо можно отсечь вершины подграфа, в котором у первого игрока найдется стационарная стратегия, дающая ему платеж меньший, либо равный 7 — 1.

Из приведенных выше построений следует справедливость утверждения о расщеплении:

для любого 7 найдется эргодическое разбиение VI, У2 (возможно одно из множеств У\ или У> пусто) и две стационарные стратегии в*. первого и второго игроков соответственно, что все циклы в подграфе (Уу, Е(А\,В\)и в^) имеют стоимость меньшую, либо равную 7 — 1, а все циклы в подграфе (У2; 2 и Е(В2, Л2)) имеют стоимость большую, либо равную 7.

Здесь (VI; Е{А\, В^ия}) - подграф с множеством вершин = А^В\ и множеством ребер- Е(А^, В\) - все ребра с началами в позициях Ах второго игрока и концами в позициях Вг первого игрока блока У\ и ребрами стационарной стратегии в* первого игрока; аналогично определяется подграф (У2; ^ и Е(В2, А2)).

Разбиение Ух, У2 обладает свойством эргодичности, если справедливо: из вершин I7! второго игрока отсутствуют переходы в блок У2, в вершинах У2 первого игрока отсутствуют переходы в блок Ух и подграфы, порожденные множествами вершин и У2 нетупиковые. (В дальнейшем потребуются следующие определения.

Нетупиковый граф называется структурно эргодическим. если он не допускает нетривиального эргодического разбиения: Ух, У2 и Ц, У2 не пустые.

Нетупиковый граф, любой порожденный нетупиковый подграф которого эргодический, называется сильноэргодическим.

Непосредственно из определения следует, что полный, полный двудольный графы с долями А, В- примеры эргодических и даже сильноэр-годических графов.)

Таким образом, если игра начнется в блоке Ух, то первый игрок получит платеж меньший, либо равный 7 — 1, играя согласно стационарной стратегии в*, а если игра начнется в блоке У2, то второй игрок получит платеж больший, либо равный J, играя согласно стационарной стратегии

«3-

Выше рассмотрена основная схема доказательства наличия равновесия в стационарных стратегиях игроков, из которого следует полиномиальный алгоритм поиска требуемого равновесия в циклических играх с максимальным платежом по циклу.

Удается явно указать структуру стационарных стратегий. Представим структуру для некоторого эргодического блока, т.е. подграфа с ценой во всех вершинах равной 3.

Структура стационарной равновесной стратегии первого и второго игроков представлена на рисунках (а),(Ь) соответственно.

рис. (а)

х%

рис. (Ь)

Далее в первой главе рассматривается случай симметрического платежа (с) по циклу. В этом случае метод форсирования критической позиции также дает утверждение о наличии стационарного равновесия, и удается неявно описать структуру стационарного равновесия. Из конструктивного доказательства следует лишь только экспоненциальный в худшем случае алгоритм поиска стационарного равновесия. Однако найдены широкие классы задач, где алгоритм является полиномиальным. Представлена полипомиальность для сильноэргодических игр, игр с фиксированным числом приоритетов, и для решения проблемы выполнимости формул ¿(¿-исчисления на почти ациклических Крипке графах (эти результаты представлены в главе 5). Алгоритм форсирования для графа, в котором каждая компонента сильной связности является силь-ноэргодической, имеет сложность 0(п*тах{г,п1од2п}). Здесь г- число ребер в графе игровой сети.

Отметим, что сильноэргодические графы включают как частный случай графы, в которых все циклы одной компоненты связности имеют хотя бы одну общую вершину (линейный алгоритм для этого случая анонсирован [12]). Второй случай решает проблему определения- выполнима ли формула ^—исчисления с фиксированным числом альтернаций операторов наименьшей и наибольшей неподвижных точек.

В главе 2 рассматриваются циклические игры с запретами.

Этот случай представляется следующей схемой игры. В любой момент времени £ функционирования системы при попытке перевести систему из состояния у в состояние и по ребру (гш) возможен сбой или отказ, и число этих отказов определяется целочисленной функцией к(ь) : О > к(ь) > |У(г>)| — 1, заданной на вершинах V. Исходя из концепции га-

рантированного результата, будем считать, что отказ в состоянии у € А осуществляется противоборствующим первым игроком, а в состоянии у £ В вторым игроком. Далее второй в вершине у € А и первый в вершине у £ В переводит игру по любому из оставшихся |Т^(г>)| — к{у) ребер, после этого ребра восстанавливаются. В результате будет пройдена бесконечная траектория щ,... Тогда рассматриваются предельные платежи первого игрока второму (а), (Ь). Точно так же справедлива редукция к конечной циклической игре, равновесные стратегии в которых естественным образом продолжаются до равновесных стратегий общего вида в бесконечной игре.

С помощью метода форсирования критической позиции доказаны утверждения о наличии стационарных равновесий для позиционных средних (а), (Ь). Из доказательства следует алгоритм поиска искомых равновесий. Для максимального платежа (Ь) алгоритм полиномиален. Операция форсирования позволяет описать структуру равновесных стратегий.

Во второй главе также рассматривается средний платеж по траектории (а). Алгоритм потенциальных преобразований обобщается на случай игр с запретами.

Конструкция алгоритма заключается в следующем. Рассматриваются потенциальные преобразования стоимостной функции с'(иу) = с(иу) + е(и) - е{у) для произвольных рациональных £(?.>). Длины циклов (суммарная стоимость весов ребер цикла) инвариантны относительно данного потенциального преобразования, поэтому потенциальное преобразование порождает игру, эквивалентную первоначальной. Оказывается, всегда существует потенциальное преобразование е : с—» с', приводящее игру к тривиальному виду. Именно, если разбить вершины по значениям экстремумов (где под экстремумом в вершине г/ € А (у € В) понимается значение к (у) + 1 максимума (минимума) в порядке невозрастания (неубывания) ребер, исходящих из вершины и), то в блоки с большим значением экстремума можно перейти только по ребрам стоимости строго большей значения экстремума в рассматриваемом блоке, а в блоки с меньшим значением экстремума по ребрам стоимости строго меньшей чем значение экстремума в рассматриваемом блоке. Поэтому, если игра началась в вершине у, то второй игрок форсирует выигрыш больший, либо равный еш^г(с', г/), если он будет переводить игру по ребру максимальной стоимости, оставшегося после отсечений первого игрока в вершинах ги € А и отсекать первые к(ю) ребра в порядке их неубывания в вершинах ш £ В Первый игрок имеет возможность платежа

менее, либо равного ех^(с',ь). если будет отсекать первые к(ги) ребра в порядке их невозрастания в каждой вершине т е А, преобразованной игры и переводить игру по ребру минимальной стоимости, оставшегося после отсечений в вершинах и> € В. Таким образом, задача сводится к поиску требуемого потенциального преобразования стоимостной функции игры Во второй главе представлен алгоритм такого преобразования. Алгоритм потенциальных преобразований также неявным образом использует идею форсирования критической позиции.

После описания алгоритма и доказательства его корректности дается анализ его вычислительной сложности.

Во-первых, доказывается его конечность. Приводится верхняя оценка числа операций {+, —, *, /, >} над рациональными числами- экспонента от размера входа ( числа представлены в памяти машины в двоичном счислении).

Во-вторых, показано, что верхняя оценка достижима по экспоненциальному порядку, т.е. представлена последовательность задач, на которой алгоритм затрачивает экспоненциальное число элементарных операций от длины входа [5].

В-третьх, алгоритм исследован на модельном примере преследования. Хотя гарантированное время поиска стационарного равновесия является экспоненциальным, практическое время, и это подтверждают многочисленные примеры случайных и модельных задач, оказывается полиномиальным. Ситуация по форме и по существу совпадает с симплекс-методом решения задачи линейного программирования. Конструкция этого алгоритма напоминает симплекс-метод. А именно, поиск требуемого потенциального преобразования можно представить как движение по ребрам некоторого многогранника до выполнения определенного экстремального свойства.

Поэтому, по всей видимости, представленный алгоритм практически эффективно определяет равновесные стационарные стратегии игроков в циклических играх с запретами. Алгоритм тестировался на модельной задаче преследования одного игрока другим по среднему расстоянию между ними на ограниченном отрезке с десятью позициями. Число итераций не превосходило п = 200- числа вершин в графе переходов этой игры (сама итерация квадратична от числа вершин п).

В главе 3 рассматриваются специальные классы задач. Долгое время оставался открытым вопрос вычислительной сложности определения является ли заданный граф структурно неэргодическим или нет.

Т.е. по ориентированному, без тупиков графу (V : А,В;Е) требуется определить- существует или нет нетривиальное эргодическое разбиение 14, У2 (нетривиальность означает, что множества У, У2 непустые)?

Если граф структурно эргодичен, т.е. не допускает нетривиального эргодического разбиения, то для любой стоимостной функции с : Е -+ Я цена игры одна и та же независимо от начальной вершины, т.е. структурная эргодичность влечет эргодичность цен независимо от стоимостной функции с на ребрах графа игры. Обратное утверждение, очевидно, также справедливо. Т. е. эргодичность цен для любых стоимостных функций влечет структурную эргодичность. Структурно эргодичен, например, полный двудольный граф или простой цикл. Примером структурно неэргодического графа является булев куб размерности более двух. Заметим, что структурная неэргодичность эквивалентна наличию нетривиальной неподвижной точки оператора Н : Я" —> Я"

Ь!ь — если V е А, = ттшСу(у)если V € В.

Задача определения, является ли граф структурно неэргодическим, есть ТУР-полная проблема. Это доказывается следующей цепочкой редукций. Л^Р-полная проблема выполнимость сводится к проблеме монотонная выполнимость [2], а последняя в свою очередь сводится к задаче структурная неэргодичность.

Другой известной задачей является задача поиска максимального среднего цикла в ориентированном графе (У\Е). Это есть вопрос чистой оптимизации, т.е. множество вершин первого игрока отсутствует. Алгоритмическая сложность рассматриваемой задачи достаточно хорошо изучена [3], [10]. Известна конструкция сильнополиномиального алгоритма, которая предложена [10]. Оставался неизученным вопрос эффективной характеризации всех максимальных средних циклов. Конечно, таких циклов может оказаться экспоненциально много от размера входа. Однако постановка задачи позволяет описать все максимальные средние циклы, как в точности все циклы некоторого подграфа начального графа.

Здесь представлен сильнополиномиальный алгоритм поиска такого подграфа. Поиск осуществляется с помощью потенциальных преобразований стоимостной функции с'(иу) = с(/ии) + е(и) — е(г). Через конечное, полиномиальное от числа вершин п операций {+, -, *, >}, граф будет приведен к виду, в котором подграф, образованный всеми максимальными ребрами, будет содержать цикл. Тогда любой цикл в этом подграфе- максимальный средний во всем графе, и других максималь-

ных средних циклов нет. Так как потенциальное преобразование не изменяет длин циклов, то найденный подграф искомый. Конструкция алгоритма в основном следует из алгоритма для циклических игр, но в силу отсутствия осцилляций вершин, связанных с антагонизмом противников, число итераций (потенциальных преобразований) алгоритма оказывается лишь только квадратичным п2 (число элементарных операций на каждой итерации 0(гп), более подробно см. главу III, параграф 2).

Замечание: конечно, такой подграф можно получить, используя сведение к линейному программированию, но гарантируемая верхняя оценка сложности такого поиска, конечно, будет выше, по крайней мере полиномиальная от размера входа.

В заключении третьей главы рассматриваются стохастические конфликты. Стохастическая игра задается тройкой (б; Р; с), где С- ориентированный полный двудольный граф с долями Л и В и множеством ориентированных ребер Е. Представлен псевдополиномиальный алгоритм решения таких игр с помощью потенциальных сжатий.

В главе 4 проводится обобщающий анализ доказательств наличия равновесий в стационарных стратегиях в циклических играх с платежами по циклу типа средних.

Во-первых, показывается независимость полученных максминных утверждений для некоторых платежей типа средних от известного случая среднего платежа (а) относительно сводимости одного функционала к другому.

Рассматривается игровая модель ((Л, В\ Е)\ с; /). Здесь (А, В; Е)- ориентированный, без тупиков граф с локальными платежами с : Е и платежным функционалом / : 2® <Э, дающим вес (иногда используется тождественный термин- платеж, значение) произвольного цикла по множеству его локальных платежей.

Существенным является выполнение следующего условия для функционала /: найдется рациональная константа а такая, что для любого множества рациональных чисел {с],..., с^} и любого рационального И выполнено следующее:

/({с! + А,..., * + Л}) = /({сь ..., <к}) + аН

Такие функционалы будем называть функционалами типа среднего. Все функционалы (а), (Ь), (с) данным свойством обладают.

Циклическая игра проходит по ребрам графа до первого цикла г и платеж первого игрока второму есть /(г), первый минимизирует данный вес, второй его максимизирует.

Рассмотрим два функционала типа средних Д и /2, заданных на всевозможных конечных подмножествах множества рациональных чисел.

Скажем, что функционал сводится к функционалу /2, если для произвольного конечного множества М{2],..., 2(} рациональных чисел можно представить множество рациональных чисел М...., 5(} такое, что при естественном взаимно однозначном соответствии между элементами этих множеств <р сохраняется порядок весов подмножеств этих множеств, т.е. неравенство ^(Мг) < Л (М2) влечет выполнение неравенства /г(1/'(М1)) < /2(93(^/2)). ( Множества, равные по функционалу /], могут переходить в неравные по функционалу /2).

Если функционал /1 сводится к функционалу /2, и имеет место результат о наличии равновесных стационарных стратегий в циклической игре с функционалом /2, то имеет место результат о наличии равновесия в стационарных стратегиях в циклической игре с функционалом /1.

Оказывается функционал (с) не сводим к функционалу (а). Контрпример построен в параграфе 3. Функционал (6) сводим к функционалу (а). Доказательство в параграфе 2.

Во-вторых, используя более слабое понятие сводимости одного функционала к другому, удается получать утверждения о равновесии в стационарных стратегиях.

А именно, для доказательства утверждения о стационарном равновесии достаточно справедливости утверждения расщепления для функционала типа среднего по циклу / относительно нуля.

Тогда в силу того, что функционал / - типа среднего, справедлив результат о расщеплении относительно произвольного рационального 3, и тогда в силу конечности числа циклов справедлива теорема о наличии стационарного равновесия.

Поэтому для существования стационарного равновесия достаточно слабого сведения.

Функционал типа среднего /1 слабо сводится к функционалу типа среднего /2, если для произвольного конечного множества М{г\,..., г(} рациональных чисел можно представить множество рациональных чисел М{г\,..., что при естественном взаимно однозначном соответствии между элементами этих множеств (р сохраняются знаки весов подмножеств этих множеств, т.е. если /г(М') > 0. то /2(¡р(М')) > 0, и если

/1 (М') < 0 , то /2(</>(М')) < 0 для произвольного подмножества М' С М.

Тогда, если функционал типа среднего /1 слабо сводится к функционалу типа среднего /2, и справедливо утверждение о наличии равновесия в стационарных стратегиях в циклической игре с функционалом /2, то справедливо утверждение о наличии равновесия в циклической игре с функционалом Д.

В четвертой главе показано, что функционалы (Ъ), (с) слабо сводятся к функционалу (а). Первая редукция представлена в параграфе два, вторая - в параграфе три.

С помощью техники слабого сведения доказаны новые результаты существования стационарных равновесий в циклических играх.

В главе 5 рассматриваются игровые подходы к алгоритмическому анализу параллельных динамических систем и верификации программ.

Параллельная система включает множество компонентов, работающих одновременно. Стандартные подходы к формальному анализу параллельных систем обычно представляют системы как графы переходов.

Логические аспекты взаимодействия систем формализуются модальным исчислением. Таким образом, вопрос надежного управления параллельной системой сводится к определению выполнимости формулы модального исчисления.

Синтаксически формулы модального исчисления представляют собой индуктивно построенные выражения над символами операций (->, V, А, <Н.>, [Л], ц., г/). Семантически формуле соответствует отображение из множества вершин Крипке- графа в множество вершин этого же Крипке-графа состояний. Основная задача^ определить значение формулы на заданном значении переменных.

В данной главе приведено упрощенное доказательство утверждения работы [8] и построено полиномиальное сведение вопроса выполнимости формулы модального исчисления к решению циклических игр с симметрическим платежом по циклу. Нами использована игровая интерпретация, что упрощает первоначальное доказательство [8]. Таким образом, можно применить метод форсирования критической позиции для вычисления значений формул модального исчисления. Является ли алгоритм форсирования критической позиции для вычисления формул модального исчисления полиномиальным на данный момент времени не известно.

В работах по модальным исчислениям используются игры на четность (если максимальный локальный платеж по циклу четный- выигрывает первый игрок, если нечетный- то второй). Тривиально показать

полиномиальную эквивалентность таких игр и игр с симметрическим платежом.

Решение циклических игр на четность проще, чем определение значения формулы непосредственно. Хотя практическая выполнимость многих из разработанных алгоритмов эффективна, полиномиального алгоритма для решения циклических игр на данный момент времени нет и мало примеров полиномиальных подклассов данной задачи.

Мы показываем, что метод форсирования полиномиален для графов, все сильносвязные компоненты которых сильноэргодические и в случае фиксированного приоритета стоимостной функции Перечисленные случаи достижимы на некоторых неограниченных по мощности классах формул модального исчисления, что дает полиномиальный алгоритм решения проблемы выполнимости таких формул модального исчисления. В заключении пятой главы представлен полиномиальный алгоритм решения проблемы выполнимости для почти ациклических Крипке- графов. Здесь рекурсивно применяется алгоритм форсирования критической позиции по слоям ациклического графа состояний. Это дает полиномиальный алгоритм решения динамической игры, и тем самым решается проблема выполнимости формулы модального исчисления.

Заключение

Таким образом основными результатами работы являются следующие:

1. Разработан метод форсирования критической позиции для поиска оптимальных стратегий в циклических играх с полной информацией. Показано, что операцией дополнения шлейфа можно получить любую игровую сеть с заданной ценой, тем самым дается качественное представление рассматриваемых игр.

Доказаны утверждения существования стационарных равновесий, описана их структура и показаны важные свойства- равномерность оптимальных стратегий и эргодичность цен.

Метод форсирования критической позиции дает полиномиальность решения игр с максимальным платежом по циклу и важных подклассов игр с симметрическим платежом по циклу. В последнем случае конструкция форсирования полиномиальна для сильноэргодических игр и игр с фиксированным числом приоритетов.

2. Метод форсирования использован для решения проблемы выполнимости формул модального исчисления.

Получено упрощенное сведение проблемы выполнимости формул мо-

дальнего исчисления к решению циклических игр с симметрическим платежом по циклу. При этом сведении сильноэргодические структуры достижимы, играм с фиксированным числом приоритетов соответствуют формулы с фиксированным числом альтернаций операторов наименьшей и наибольшей неподвижных точек. Форсирование критической позиции полиномиально решает проблему выполнимости формул модального исчисления на почти ациклических Крипке- графах. 3. Показана ОТ- полнота задачи структурная неэргодичность. Представлен сильнополиномиальный алгоритм характеризации всех максимальных средних циклов в графе посредством потенциальных преобразований. Разработан псевдополиномиальный алгоритм решения стохастических игр с полным графом переходов.

Возможными приложениями полученных результатов являются: верификация программ, оптимизация иерархических систем управления и построение экономных расписаний.

Форсирование критической позиции является новым методом в качественном анализе дискретных динамических конфликтов с полной информацией, имеющее важный контекст в модальном, темпоральном исчислениях и приложениях.

Работа выполнялась при поддержки гранта РФФИ 1994-2002 и госбюджетной темы Волгоградского Государственного Университета 19912005 годов. Благодарю А.Н.Катулева за внимание к работе.

Публикации:

Все результаты диссертационной работы опубликованы в рецензируемой печати:

1. Лебедев В.Н. Поиск всех максимальных средних циклов в графах. // Известия РАН. Теория и системы управления. N. 6. 2001.

2. Лебедев В.Н. Эффективно решаемые классы циклических игр// Известия РАН. Теория и системы управления. N. 4. 2005. С. 44-49.

3. Лебедев В.Н., Черничкин М.С. Игровой аспект верификации программ// Известия РАН. Теория и системы управления. N. 5. 2005. С. 40-45.

4. Гурвич В. А., Лебедев В.Н. Критерий и проверка эргодичности игровых форм // УМН В. 44. N. 1. 1989. С. 193-194.

5. Лебедев В.Н. Поиск и структура стационарных равновесий в циклических играх // Математические заметки. Т. 67. N. 6. 2000. С. 913-921.

6. Лебедев В.Н О новом равновесии в циклических играх// Дискретная математика. Т. 9. N. 4. 1997. С. 96-99.

7. Лебедев В.Н. Алгоритмы оптимизации стационарных управлений в дискретных динамических системах. Дисс. к.ф.-м.н. М: МФТИ. 1990.

8. Лебедев В.Н. Стационарные равновесия в циклических играх на графах // Вестник ВолГУ Сер Матем., Физика. В. 3. 1998. С. 83-86

9. Лебедев В.Н. О равновесиях в циклических играх на графах // Вестник ВолГУ. Сер. Матем., Физика. В. 1. 1996. С. 72-74.

10. Лебедев В.Н. Вероятностный полиномиальный алгоритм, решающий одну из двух NP-полных задач// Интеллектуальные системы. Т. 5. В. 1-4. 2000. С. 247-255.

11. Лебедев В.Н. Полиномиальный алгоритм нахождения оптимальных стратегий в одной игре двух лиц с предельным во времени платежом// Моделирование процессов управления и обработки информации. МФТИ. М- 1989.

12. Karzanov А. V., Lebedev V.N. Cyclical games with prohibitions // Mathematical Programming V. 60. 1993. P. 277-293.

13 Averbakh I.L., Lebedev V.N. Interval data minmax regret network optimization problems// Discrete Applied Mathematics. V. 138. 2004. P. 289-301.

14. Averbakh I., Lebedev V. On the complexity of minmax regret linear programming// European Journal of Operation Research. V. 160. (1). 2005. P. 227-231.

15. Лебедев В.Н. Конечный алгоритм определения цен в циклических играх с отказами/ МФТИ- М. Деп. ВИНИТИ. 13.08.90 N. 4598-В90.

Апробированы в трудах Всероссийских и Международных конференций:

1. Лебедев В.Н., Черничкин М.С. Циклические игры и их приложения. Тезисы докладов 2-ой Московской конференции "Декомпозиционные методы в математическом моделировании и информатике". Москва. 21-24 июня 2004.

2. Лебедев В.Н. Структура оптимальных стратегий в циклических играх на графах. Труды III Международной конференции "Дискретные модели в теории управляющих систем". Москва. 22-27 июня 1998.

3. 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.

4 Karzanov A.V., Lebedev V.N. Cycklical games/ Res. Rep. Imag Artemis. Grenoble. 1990.

5. 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.

6. Лебедев В.Н. Оптимизационные модели производства в условиях неполной информации. Межвузовская научно-практическая конференция "Проблемы теории и практики перехода региона к устойчивому развитию "Волгоград. 26 января 1998.

7. Лебедев В.Н. Эффективные вероятностные алгоритмы решения одной из двух NP-полных задач. Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики."Нижний Новгород. 1722 мая 1999.

8. Лебедев В.Н. Эффективная характеризация всех максимальных средних циклов в графе. Тезисы докладов международного семинара, "Универсальная алгебра и ее приложения."Волгоград. 6-11 сентября 1999.

9. Лебедев В.Н. Равновесия в стохастических играх с полной информацией VI Международная научно-техническая конференция "Математические методы и информационные технологии в экономике". Пенза. 25-26 октября 2000.

10. 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.

11. Лебедев B.H., Остякова А.В. Распределение ресурсов в условиях неполной информации. Второй всероссийский симпозиум "Стратегическое планирование и развитие предприятий". Москва. 10-12 апреля 2001

Список литературы

[1] Гурвич В. А., Карзанов А. В., Хачиян Л. Г. Циклические игры и нахождение минимаксных средних циклов в ориентированных графах // ЖВМ МФ. Т. 28. N. 9. 1988. С. 1407-1417.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

[3] Карзанов A.B. О минимальных по среднему весу разрезах и циклах ориентированного графа // Качественные и приближенные методы исследования операторных уравнений (под редакцией Климова В. С.) Ярославль.: ЯрГУ. 1985. С. 72-83.

[4] Кифер Ю.И. Оптимальное поведение в играх с неограниченной последовательностью ходов // ТВП. В. 14. N. 2. 1969. С. 279-286.

[5] Лебедев В.Н. Алгоритмы оптимизации стационарных управлений в дискретных динамических системах. Дисс. к.ф.-м.н. М: МФТИ. 1990.

[6] Цурков В.И. Динамические задачи большой размерности. М.: Наука. 1988.

[7] Ehrenfenfeucht A., Mycielski J. Positional strategies for mean payoff games // Intern. J. Game Theory. V. 8. N. 2. 1979. P. 109-113.

[8] Emerson E.A. Jutlu C.S. Sistla A.P. On model-checking for fragments of ¿i-calculus. Fifth International Conference on Computer Aided Verification, Elounda, Greece, June/July 1993.

[9] Gillette D. Stochastic games with zero stop probabilities // Ann. Math. Stud. V. 39. 1957. P. 178-187.

[10] Karp R.M. A charucterization of the minimum cycle meaning in a digraf // Discrete Mathematics V. 23. N. 3. 1978. P. 309-311.

[11] Mertens J.F., Neyman Stochastic games // Int. J. Game Theory. V. 10. 1981. P. 53-66.

[12] Poranen T., Nummenmaa J. A linear time special case for MC Games// Fundamenta Informaticae. V. 50. N. 3. 2002.

[13] Shapley L.S. Stochastic games // Proc. Nat. Acad. Sci. USA. V. 39. 1953. P. 1095-1100.

[14] Hoffman A., Karp R. On nonterminaling stochastic games. Management Science. V. 12. 1966. P. 359-370.

[15] Zermelo E. Uber eine Anwendung der Mengenlehere auf die Theorie des Schaspiels, Proc. 5-th Congress of Mathematicians, Cambridge, 1912, Cambridge Univ. Press.

[16] Zwick U., Paterson M. The complexity of mean payoff games on graphs. Theoretical Computer Sciense, V. 158. 1996. P. 343-359.

»17 148

РНБ Русский фонд

2006-4 11262

Подписано в печать 15.09.2005 г. Формат 60x84/16. Бумага офсетная. Гарнитура Тайме. Усл. печ. л. 1,3. Тираж 100 экз. Заказ 230.

Издательство Волгоградского государственного университета. 400062, Волгоград, просп. Университетский, 100.

Введение

Глава I. Метод форсирования критической позиции.

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

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

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

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

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

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

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

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

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

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

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

3.4 Исследование вычислительной сложности основного алгоритма.

§4 Игры с запретами и максимальным предельным платежом по тра- 86 ектории.

4.1 Описание алгоритма поиска равновесных стратегий.

4.2 Корректность и вычислительная сложность алгоритма.

Глава III. Специальные классы задач.

§5 NP - полнота задачи структурной неэргодичности.

§6 Сильнополиномиальный алгоритм характеризации всех макси- 105 мальных средних циклов,

§7 Алгоритм нахождения стационарного равновесия в стохастиче- 112 ских играх специальной структуры.

7.1 Определения и формулировка утверждения.

7.2 Алгоритм приведения игры к каноническому виду.

Глава IV. Результаты существования стационарных равновесий в играх с платежами типа средних.

§8 Определения и формулировка утверждения.

§9 Максимальный функционал.

§10 Симметрический функционал.

§11 Медианный функционал.

Глава V. Метод форсирования для вычислений в модальной логике

§12 Модальная логика. Основные определения. 133 ф 12.1 Сведение вычислений формул модальной логики к решению циклических игр с симметрическим платежом.

§13 Форсирование в модальной логике.

13.1 Сильноэргодические игры.

§14 Эффективное вычисление формул для почти ациклических

Крипке графов.

Главным предметом рассмотрения являются алгоритмические вопросы отыскания и описания структуры оптимальных стационарных равновесий в дискретных, динамических, конфлитных ситуациях с предельным во времени платежом.

Общие формализации динамических конфликтов являются, по всей видимости, экспоненциально сложными по времени их разрешения в контексте предполагаемых строгих включений Р С NP С PSPACE. Известно, что определение наличия равновесия по Нэшу в чистых стратегиях для нормальной формы игры с полиномиальными платежными функционалами является ЛГР-полной проблемой [83]. Установить победителя в позиционных играх, таких как кэли, шашки, го на доске п, пявляется даже PSPACE-потюй проблемой [84]. Некоторые комбинаторные игры [87], [88] существенно экспоненциально сложны по времени их решения.

Начнем рассмотрение с формализации стохастических игр, которые предложены Л.С.Шепли в [86] (см. также [42], [63]).

Это игра двух лиц на конечном множестве позиций V. В позиции v € V разыгрывается матричная игра C(v) размером m(v),n(v). В позиции v первый игрок выбирает строку г, а второй столбец j независимо друг от друга. Тогда с вероятностью plj(v, w) игра перейдет в очередную позицию w и первый платит второму с* (и) или с вероятностью s > 0 игра завершается (52wplj(v,w) + s = 1 для каждых v,i,j; игроки имеют право применять и случайный выбор строк-столбцов).

Цель первого игрока состоит в минимизации суммарного ожидаемого платежа, а цель второго-максимизация. Описанная выше игра называется стохастической игрой с дисконтированием s.

Общие стратегии в рассматриваемой игре, зависимые от предыстории. Это сложный комбинаторный объект, даже чистые стратегии не имеют конечного представления. Оказывается, игрокам достаточно ограничиться стационарными (марковским) стратегиями, когда выбор строки, столбца в любой текущей позиции не зависит от предыстории. В [86] показано наличие равновесия по Нэшу в стационарных стратегиях в представленной игре (более точно, если одного из игроков ограничить только стационарными стратегиями, а противнику разрешить играть нестационарно, то это не ухудшит положение игрока).

Решение стохастических игр с дисконтом сводится к поиску неподвижной точки оператора, который порожден заменой матриц платежей С (у) ценой соответствующей игры (см. [86]). В силу наличия дисконта такой оператор оказывается сжимающим, поэтому последовательное итерирование оператора имеет геометрическую скорость сходимости к неподвижной точке. В силу полиномиалыюсти решения матричных игр [60] из описанной схемы следует псевдополиномиальный алгоритм приближенного решения стохастических игр с дисконтом (дисконт может быть близким к нулю). Равновесная пара стационарных стратегий определяется неподвижной точкой представленного опреатора.

Игры с нулевым дисконтом и средним предельным платежом по бесконечной траектории рассмотрены в работах [71], [91], [78]. Во-первых, показано наличие равновесия в стратегиях общего вида [78] и отсутствие равновесия в стационарных стратегиях. Во-вторых, для эргодических игр и игр с полной информацией доказано наличие стационарного равновесия (первый случай тот, когда марковская цепь, порожденная любой парой стационарных стратегий, есть в точности эргодичесий класс позиций; второй случай тот, когда в любой позиции v один из противников имеет одну строку, столбец, т.е. либо тп(ь) = 1, либо п(и) = 1) [71], [91]. Доказательство последнего результата проведено аппроксимацией рассматриваемых игр соответствующей стохастической игрой с малым дисконтом. В случае игр с полной информацией гарантируется наличие равновесия в чистых стратегиях [71], [91].

Заметим, что для эргодических игр утверждение о наличии стационариого равновесия можно получить, используя технику точечно- множественных отображений [72], [45] (это следует из представления множества оптимальных стационарных стратегий игрока при фиксированной стратегии противника как решение задачи линейного программирования, коэффициенты которой непрерывно зависят от вероятностей смешанной стратегии противника). Вопросы, касающиеся общего случая стохастических и позиционных игр, рассмотрены в работах [70], [85], [89], [66], [89], [90], [21], [31], [58].

Случай детерминированных = 0,1 для любых V, ю, 1,з) игр с полной информаций является основным предметом данной работы. Удобно следующее графовое представление.

Динамическая система с конечным множеством состояний V существует в дискретном времени £ = 0,1,., находясь в каждый момент времени в одном из состояний и(Ь) € V системы [62]. Динамика системы описывается ориентированным графом переходов С? = (V; Е), V— вершины, Е— ориентированные ребра. Ребро (иь) € Е означает возможность перехода из состояния «(£) е V в состояние и(£ + 1) е V в момент t функционирования системы. На ребрах Е задана целочисленная функция с локальных платежей преходов. Множество V состояний системы разбито на два непересекающихся подмножества А н В (А и В = V; Л Г) В = 0), так что выбор перехода V £ У(и) (здесь У (и)— обозначены состояния V, достижимые за один шаг из состояния и) находится в нашем распоряжении лишь при условии принадлежности позиции и к множеству А контролируемых позиций. Исходя из принципа гарантируемого результата, считаем, что в позициях и £ В выбор перехода осуществляется противоборствующей стороной, называя позиции V € В позициями первого игрока, а позиции V € А - позициями второго игрока.

Любая пара стратегий игроков я^вд (очередной переход в вершине и(Ь) определяется предысторией и(0),и(1), однозначно порождает некоторую бесконечную траекторию: T{sA,sB) : ü(0),ü(1), .

Тогда критерием качества является некоторый стоимостной функционал, определяемый по локальным платежам этой траектории. В работе рассмотрены функционалы типа средних: a)c(T(sA,sB) =Ш(Еос(и(т),и(т+1))) / t, iЬ) c{T{sA, sB)) = Щ+1), с) с(Г(5Л, «в)) = Jimc(ut,ut+i) + Jim c(uu ut+i).

00 t-*oо

Таким образом, при возникшей траектории T(sA, sB) платеж первого игрока второму - есть величина c(T(sA,sB)), в минимизации которого состоит задача управления первого и в максимизации которого состоит задача управления второго игрока. Наличие равновесия в стратегиях общего вида можно показать сведением к циклической игре. Циклической игрой называют игру, которая проходит по ребрам графа до первого цикла щ, .,ик,щ. То есть, как только траектория игры попадает в позицию, где была ранее, игра завершается. Платеж первого игрока второму есть соответствующий платеж типа среднего: a) с{Т(зл, sB)) = (Е c(u(r), и(т + 1))) / к - i + 1,

T=i ' b) c(T(sA, sB)) = maxT=ij.)fc с(и(т),и(т + 1)), c) c(T(sA, sB)) = maxT=j.k c(u(r), и(т +1)) + гатгЦ.^ с((и(т),и{т +1)).

Здесь и(к +1) есть позиция и(г).

По теореме Цермело следует существование равновесия в стратегиях общего вида в редуцированной циклической игре (циклическая игра конечная). Более точно, существует пара чистых стратегий общего вида первого и второго игроков s*B, s*A, что для каждой начальной позиции м(0) и для любых стратегий первого и второго игроков sp, sA, выполнены условия седла: ф(0), 8Af S*B) < ф(0), S*B) = p(u(0)) < с(м(0), 8\, SB)

Здесь с(«(0), в а, вв)- значение цикла, возникшего согласно стратегиям эд^в игроков из начальной позиции м(0); р(и(0)), называют ценой циклической игры в позиции и(0).

Таким образом, пара стратегий з*в- равновесна, т.е. ни одному из игроков не выгодно уклоняться от своей стратегии при фиксированной стратегии противника.

Последовательным удалением циклов из бесконечной траектории полученные равновесные стратегии з*А,з*в доопределяют до стратегий в первоначальной бесконечной игре, и это есть равновесная пара чистых стратегий общего вида в первоначальной бесконечной игре.

Как отмечалось, в бесконечной игре с полной информацией и предельным средним платежом (а) существует равновесие и в чистых, стационарных стратегиях [71]. Более точно, существует пара чистых стационарных стратегий первого и второго игроков в*в, в*А, что для каждой начальной позиции и(0) и для любых стратегий первого и второго игроков вв, в а, выполнены условия седла: с(и(0),вл,4) - сН°)'5л>5Ь) ~Р(Ф) < с{и(0),з*А,зв)

Здесь с(и(0), $в)~ платеж (а) по бесконечной траектории; а стационарные стратегии есть отображения вида: вв : и —> У(и) для всех и £ В, : и —» У(и) для всех и £ А. (последнее утверждение непосредственно переносится на конечные циклические игры).

Обзор по сложности решения представленных игр начнем с общих методов нелинейной оптимизации. Рассматриваемая проблема предста-вима задачей нахождения максмина линейного функционала с линейными ограничениями, связующие переменные. Разработаны методы [20], [70], [12]-[16] сведения такой задачи к задаче квадратичного программирования на линейном многограннике. Сведение проводится с помощью штрафных функций и соотношений двойственности. Существенным для эффективности вычислений является фиксированность коэффициента штрафа при редукции к задаче квадратичного программирования. Для задачи квадратичного программирования развиты практически быстрые алгоритмы решения, что в сочетании с полиномиальной редукцией дает эффективный метод решения рассматриваемых игр.

Другим общим способом решения является подход, связанный с поиском неподвижной точки некоторого максмшшого оператора. Поиск такой точки можно проводить с помощью вычисления вращения [29], как некоторого многомерного интеграла. Трудности такого подхода связаны с тем, что в общем случае приближенное вычисление объема многогранника является РЭРАСЕ-полной проблемой и, по всей видимости, не имеет эффективного алгоритма.

Специальные методы в основном используют технику альтернирования, как в конструктивном доказательстве наличия равновесия в позиционных играх с полной информацией [93]. В работах [27], [67], [94] рассматривался вопрос сложности решения бесконечной игры (а). Представлена аппроксимация такой бесконечной игры конечной за £ = 1,. шагов. Показано, что цена конечной игры за £ шагов из начальной вершины рг(и(0)) стремится к цене в бесконечной игре р(и(0)) при Ь —> оо и получена скорость сходимости: р4(«(0)) - р(и(0) |< 2МпЦ

Здесь М-максимальная по модулю локальная стоимость перехода, п-число вершин в графе перехода.

Игра за Ь шагов максминной процедурой сводится к £ — 1 шаговой игре за линейное время, что дает приближенный псевдополиномиальный алгоритм решения бесконечной игры. В силу того, что две различные величины средних циклов (в графе с целочисленной платежной функцией) отличны по крайней мере на 1/п2, для точного решения бесконечной игры достаточно решать конечную игру за t = 2п3М шагов. Оценка сложности алгоритма Mpoly(n).

Для представленного алгоритма несложно построить пример игровых сетей с двумя вершинами с достижимой псевдополиномиалыюй оценкой их работы.

В работах [85], [70], [66] изучалась сходимость аналогичной процедуры для стохастических игр с полной информацией, но, как отмечено выше, сложность такого подхода псевдополиномиальная- полиномиальна от длины унарного представления численных данных задачи.

Метод потенциальных преобразований представлен [17].

Выло замечено, что циклическая игра обладает богатой группой эквивалентных, потенциальных преобразований, которые не меняют суммарных длин циклов, поэтому не меняют игры. Показано, что всегда существует конечная последовательность элементарных потенциальных преобразований-сдвигов, которая приводит игру к тривиальному виду, когда граф распадается на две компоненты- в первой компоненте величины локальных экстремумов вершин отрицательные (оптимальный платеж игрока за один ход), во второй- неотрицательные; в первой компоненте игру оставляет первый игрок (в любой вершине первой компоненты первый игрок имеет экстремальный переход, ведущий в эту же компоненту, а у второго игрока во всех вершинах первой компоненты все переходы ведут в первую компоненту ); во второй компоненте игру оставляет второй игрок. Тогда минмаксные стационарные стратегии игроков гарантируют первому отрицательный платеж в первой компоненте и второму неотрицательный платеж во второй компоненте. Заметим, что решение циклических игр с платежом типа средних полиномиально эквивалентно определению знаков цен. Поэтому эффективный поиск приведенного выше тривиального вида игры дал бы полиномиальный алгоритм решения игры.

Но искомая последовательность преобразований-сдвигов экспоненциальна в худшем случае.

Оценка сложности алгоритма потенциальных преобразований тт{Мро1у(п),2ро1^пЧод2М} [17], [81], [34]. Здесь М- максимальная по модулю стоимость вершин, п- число вершин игровой сети; ро1у(п)-полином небольшой степени. В работе [34] представлены достижимые примеры и обобщения. Богатая группа эквивалентных преобразований дает возможность анализа временной оценки этого алгоритма в среднем [77].

Замечательным свойством представленных игровых задач является их принадлежность классу ИРГ\со—ИР (это непосредственно следует из наличия равновесия в стационарных стратегиях), поэтому при условии ИР ф со—МР, доказать АГР-полноту проблемы определения победителя в рассматриваемых циклических играх (Ь), (с), (с1) невозможно.

Основным содержанием диссертационной работы является новое направление в теории дискретных динамических конфликтов- структурное представление равновесий по Нэшу посредством форсирования критической позиции [32]-[39], [74].

Показано, что операцией дополнения шлейфа можно получить любую игровую сеть с заданной ценой, тем самым дается конечно порождаемая характеризация рассматриваемых игр.

С помощью форсирования критической позиции удалось получить неизвестные ранее утверждения существования стационарных равновесий в играх с позиционными средними (Ь), (с), описать их структуру и выявить их важные, качественные характеристики- независимость от начальных вершин и эргодичность цен. Конструкция форсирования критической позиции дает полиномиалыюсть решения игр (Ь) и существенных подклассов (с). Решение игр (Ь) и (с) является важным в контексте проблемы выполнимости формул темпоральных и модальных логик и для практических приложений- верификации программ [69], оптимизации иерархических систем управления [28], [13], [4], [5] и для построения экономных расписаний [79].

Представленная техника исходит из стратегии альтернирования для форсирования выигрыша в позиционных играх с полной информацией, но применительно к циклическим играм существенно усложняется, как, например, для максимального платежа по циклу (Ь). В этом случае применение этого метода позволило получить индукцию с развалом игры на две, в одной из которых решение игры очевидно, в другой конструкция применяется рекурсивно.

Метод для случая максимального платежа по циклу представлен в 1-й главе работы и опубликован [74]. Кратко опишем его.

Второй, максимизирующий, игрок задается некоторым целым 3 и пытается определить начальные позиции, из которых он форсированно, т. е. независимо от игры противника, добьется перехода (иь) стоимости с(иь) > 3 (мы применяем нотацию позиционных игр, таких как шахматы, семантически эквивалентно форсированию применять термин гарантирование).

Ясно, что эти позиции можно получить следующим образом.

Во-первых, это позиции Хо : ехЬг(и) > 3 (ехЬг(и) - есть тах„еу(и) с(и, и), если и € А и тт„еу(и) с(и,у), если и е В).

Во-вторых, это позиции Х\ : и £ А, из которых существует переход в А'о и позиции и € В, в которых все переходы (иь) : с(иу) < 3 ведут в Хо.

В-третьих, это позиции Хч : и € А, из которых существует переход в Х\ и позиции и £ В, в которых все переходы (иу) : с(иь) < 3 ведут либо в Хо, либо в Х\, и так далее (см. рис. Ь).

В результате получим последовательность непересекающихся блоков позиций Хо,., Хг,., Хк таких, что в любой позиции второго игрока блока Хг существует переход в блок с меньшим номером Хг1, а в любой позиции первого игрока блока Х{ все лучшие для первого игрока переходы (иь) : с(иу) < 3 ведут в блоки с меньшими номерами Хо и . и Хх\. В блоке Хо у второго игрока найдется требуемый переход (иь) : с(гш) > 3, а у первого все переходы в блоке Хо больше, либо равны 3. Тогда для любой начальной позиции из перечисленных блоков второй игрок действительно форсированно добивается перехода (ми) : с(иу) > 3, играя на своем ходе в блок с меньшим номером, а в блоке Хо по ребру (иу) : с(иу) > 3. При этом противник в текущем блоке либо совершит переход (иь) : с(иу) > «7, либо перейдет в блок с меньшим номером, а в блоке Хо у первого все переходы (иг;) : с(иь) > 3 (см. рис.(Ь)).

Если разбиение Х0, .,Хк покрывает все позиции V игровой сети, то второй игрок, согласно указанной стратегии, форсирует более того цикл с переходом (иь) : с(иь) > 3, так как любой цикл будет содержать переход из г-го блока в блок с неменьшим номером, а это переход стоимости большей, либо равной 3. В этом случае второй игрок имеет стационарную стратегию, дающую ему выигрыш больший, либо равный 3 в любой начальной позиции игры.

Если разбиение Х0, .,Хк не покрывает всех позиций V, то в подграфе, порожденном остатком вершин V — {Хо и . и Х^}, первый игрок форсирует цикл с платежом менее чем 3. В этом подграфе все переходы из позиций второго игрока ведут в этот же подграф и имеют стоимости меньшие, либо равные 3 — 1, а для позиций первого игрока найдется переход со стоимостью меньшей, либо равной 3 — 1 в этот же подграф. Так как все собственные переходы первого игрока имеют стоимость меньшую, либо равную 3 — 1, и все переходы второго игрока имеют стоимость меньшую, либо равную 3—1, то и стоимость любого возникающего цикла в этом подграфе меньше, либо равна 3 — 1.

Таким образом, либо будет найдена стационарная стратегия второго игрока, дающая ему платеж по крайней мере 3 для любой начальной позиции, либо можно отсечь вершины подграфа, в котором у первого игрока найдется стационарная стратегия, дающая ему платеж меньший, либо равный 3 — 1.

Из приведенных выше построений следует справедливость утверждеиия о расщеплении: для любого 3 найдется эргодическое разбиение Ух, V2 (возможно одно из множеств У\ или У2 пусто) и две стационарные стратегии первого и второго игроков соответственно, что все циклы в подграфе (Ух] Е(Ах, 2?х)и 5^) имеют стоимость меньшую, либо равную 3 — 1, а все циклы в подграфе (14; в2 и Е(В2, А2)) имеют стоимость большую, либо равную 3.

Здесь (Кх; Е(Ах, Ях)!^) - подграф с множеством вершин Ух = АхИВх и множеством ребер: Е(Ах, Вх) - все ребра с началами в позициях Ах второго игрока и концами в позициях Вх первого игрока блока Ух и ребрами стационарной стратегии первого игрока; аналогично определяется подграф (У2]8*2иЕ(В2,А2)).

Разбиение Ух, Уг обладает свойством эргодичности, если справедливо: из вершин Ух второго игрока отсутствуют переходы в блок У2, в вершинах У2 первого игрока отсутствуют переходы в блок Ух и подграфы, порожденные множествами вершин Ух и У2 нетупиковые. Таким образом, если игра начнется в блоке Ух, то первый игрок получит платеж меньший, либо равный «7 — 1, играя согласно стационарной стратегии а если игра начнется в блоке У2, то второй игрок получит платеж больший, либо равный 3, играя согласно стационарной стратегии в2.

Выше рассмотрена основная схема доказательства наличия равновесия в стационарных стратегиях игроков, из которого следует полиномиальный алгоритм поиска требуемого равновесия в циклических играх с максимальным платежом по циклу.

Удается явно указать структуру стационарных стратегий. Представим структуру для некоторого эргодического блока, т.е. подграфа с ценой во всех вершинах равной 3.

Структура стационарной равновесной стратегии первого и второго игроков представлена на рисунках (а),(Ь) соответственно.

3 <J

• • • х„ рис. (а)

Х„

Хг

Хо рис. (Ь)

Далее в первой главе рассматривается случай симметрического платежа (с) по циклу. В этом случае метод форсирования критической позиции также дает утверждение о наличии стационарного равновесия, и удается неявно описать структуру стационарного равновесия [32]. Из конструктивного доказательства следует лишь только экспоненциальный в худшем случае алгоритм поиска стационарного равновесия. Однако найдены широкие классы задач, где алгоритм является полиномиальным. Представлена полиномиальность для силыюэргодических игр, игр с фиксированным числом приорететов, и для решения проблемы выполнимости формул /¿-исчисления на почти ациклических Крипке графах (эти результаты представлены в главе 5). В формальной части работы будут даны строгие определения. Сейчас отметим, что сильноэргодические графы включают графы, в которых все циклы одной компоненты связности имеют хотя бы одну общую вершину (линейный алгоритм для этого случая анонсирован [82]). Второй случай решает проблему определения выполнима ли формула ^—исчисления с фиксированным числом альтернаций операторов наименьшей и наибольшей неподвижных точек.

В главе 2 рассматриваются циклические игры с запретами [74].

Этот случай представляется следующей схемой игры. В любой момент времени t функционирования системы при попытке перевести систему из состояния V в состояние и по ребру (им) возможен сбой или отказ, и число этих отказов определяется целочисленной функцией к(у) : О > к(у) > |К(г;)| — 1, заданной на вершинах V. Исходя из концепции гарантированного результата, будем считать, что отказ в состоянии у € А осуществляется противоборствующим первым игроком, а в состоянии V € В вторым игроком. Далее второй в вершине V е А и первый в вершине V 6 В переводит игру по любому из оставшихся — к(у) ребер, после этого ребра восстанавливаются. В результате будет пройдена бесконечная траектория щ,. Тогда рассматриваются предельные платежи первого игрока второму (а), (Ь). Точно так же справедлива редукция к конечной циклической игре, равновесные стратегии в которых естественным образом продолжаются до равновесных стратегий общего вида в бесконечной игре.

С помощью метода форсирования критической позиции доказаны утверждения о наличии стационарных равновесий для позиционных средних (а), (Ь). Из доказательства следует алгоритм поиска искомых равновесий. Для максимального платежа (Ь) алгоритм полиномиален. Операция форсирования позволяет описать структуру равновесных стратегий.

Во второй главе также рассматривается средний платеж по траектории (а). Алгоритм потенциальных праобразований обобщается на случай игр с запретами.

Конструкция алгоритма заключается в следующем. Рассматриваются потенциальные преобразования стоимостной функции с!(иу) = с(иу) + е(и) — е{у) для произвольных рациональных е(у). Длины циклов (суммарная стоимость весов ребер цикла) инвариантны относительно данного потенциального преобразования, поэтому потенциальное преобразование порождает игру, эквивалентную первоначальной. Оказывается, всегда существует потенциальное преобразование е : с —у с/, приводящее игру к тривиальному виду. Именно, если разбить вершины по значениям экстремумов (где под экстремумом в вершине v € А (у € В) понимается значение к(у) + 1 максимума (минимума) в порядке невозрастания (неубывания) ребер, исходящих из вершины г>), то в блоки с большим значением экстремума можно перейти только по ребрам стоимости строго большей значения экстремума в рассматриваемом блоке, а в блоки с меньшим значением экстремума по ребрам стоимости строго меньшей чем значение экстремума в рассматриваемом блоке. Поэтому, если игра началась в вершине v, то второй игрок форсирует выигрыш больший, либо равный ехЬг{с!,у), если он будет переводить игру по ребру максимальной стоимости, оставшегося после отсечений первого игрока в вершинах ги € А и отсекать первые к(ъи) ребра в порядке их неубывания в вершинах ю 6 В. Первый игрок имеет возможность платежа менее, либо равного ехЬг(с!,у), если будет отсекать первые к{ш) ребра в порядке их невозрастания в каждой вершине и € Л, преобразованной игры и переводить игру по ребру минимальной стоимости, оставшегося после отсечений в вершинах ги е В. Таким образом, задача сводится к поиску требуемого потенциального преобразования стоимостной функции игры. Во второй главе представлен алгоритм такого преобразования. Алгоритм потенциальных преобразований также неявным образом использует идею форсирования критической позиции.

После описания алгоритма и доказательства его корректности дается анализ его вычислительной сложности.

Во-первых, доказывается его конечность. Приводится верхняя оценка числа операций {+,—,*,/,>} над рациональными числами- экспонента от размера входа ( числа представлены в памяти машины в двоичном счислении).

Во-вторых, показано, что верхняя оценка достижима по экспоненциальному порядку, т.е. представлена последовательность задач, на которой алгоритм затрачивает экспоненциальное число элементарных операций от длины входа [34].

В-третьх, алгоритм исследован на модельном примере преследования. Хотя гарантированное время поиска стационарного равновесия является экспоненциальным, практическое время, и это подтверждают многочисленные примеры случайных и модельных задач, оказывается полиномиальным. Ситуация по форме и по существу совпадает с симплекс-методом решения задачи линейного программирования. Конструкция этого алгоритма напоминает симплекс-метод. А именно, поиск требуемого потенциального преобразования можно представить как движение по ребрам некоторого многогранника до выполнения определенного экстремального свойства.

Поэтому, по всей видимости, представленный алгоритм практически эффективно определяет равновесные стационарные стратегии игроков в циклических играх с запретами. Алгоритм тестировался на модельной задаче преследования одного игрока другим по среднему расстоянию между ними на ограниченном отрезке с десятью позициями. Число итераций не превосходило \У\ = 200- числа вершин в графе переходов этой игры (сама итерация квадратична от числа |У|).

Возможным практическим применением рассматриваемых игр являются иерархические системы управления [28], [13], [4], [5], [И]. Представленные игры интерпретируют взаимодействие центра (максимизирующий игрок 2) и дочерней фирмы (минимизирующий игрок 1) в двухярусной динамической системе управления. В работе [28] рассмотрены многошаговые игры с непротивоположными интересами в условиях риска, когда основной игрок 2 имеет полную информацию о стратегии игрока 1 во всех состояниях, в любой момент времени. В рассматриваемом случае игрок 2 менее информирован о стратегии первого, но существенным ограничением представленной модели является антогонизм игроков.

В третьей главе рассматриваются специальные классы задач. Долгое время оставался открытым вопрос вычислительной сложности определения является ли заданный граф структурно неэргодическим или нет. Т.е. по ориентированному, без тупиков графу (V : А,В]Е) требуется определить- существует или нет нетривиальное эргодическое разбиение Уи У2 (нетривиальность означает, что множества У\, У2 непустые)?

Если граф структурно эргодичен, т.е. не допускает нетривиального эргодического разбиения, то для любой стоимостной функции с : Е —> II цена игры одна и та же независимо от начальной вершины, т.е. структурная эргодичность влечет эргодичность цен независимо от стоимостной функции с на ребрах графа игры. Обратное утверждение, очевидно, также справедливо. Т. е. эргодичность цен для любых стоимостных функций влечет структурную эргодичность. Структурно эргодичен, например, полный двудольный граф или простой цикл. Примером структурно неэргодического графа является булев куб размерности более двух. Заметим, что структурная неэргодичность эквивалентна наличию нетривиальной неподвижной точки оператора /г: Яп —> Л71

Ыу = тахги£у(у)Ь'1и, если г> € Л, к'у = тгпи,еу(и)Л.г1,, если v € В.

Задача определения, является ли граф структурно неэргодическим, есть А^Р-полная проблема. Это доказывается следующей цепочкой редукций. ИР-полная проблема выполнимость сводится к проблеме монотонная выполнимость [19], а последняя в свою очередь сводится к задаче структурная неэргодичиость [18].

Другой известной задачей является задача поиска максимального среднего цикла в ориентированном графе (У',Е). Это есть вопрос чистой оптимизации, т.е. множество вершин первого игрока отсутствует. Алгоритмическая сложность рассматриваемой задачи достаточно хорошо изучена [25], [73],[75], [76]. Известна конструкция сильнополиномиального алгоритма, которая предложена [73]. В работе [65] получено сведение этой задачи в более общей постановке стохастической оптимизации на марковских цепях к линейному программированию. В работах [25],

75], [76] также представлены силыюполиномиальные конструкции поиска максимального среднего цикла и максимального среднего разреза в ориентированных графах. Оставался неизученным вопрос эффективной характеризации всех максимальных средних циклов. Конечно, таких циклов может оказаться экспоненциально много от размера входа. Однако постановка задачи позволяет описать все максимальные средние циклы, как в точности все циклы некоторого подграфа начального графа.

Здесь представлен сильнополиномиальный алгоритм поиска такого подграфа [37]. Поиск осуществляется с помощью потенциальных преобразований стоимостной функции с!{иу) = с(гш) + е(и) — г(г>)- Через конечное, полиномиальное от число операций {+, —, *, >}, граф будет приведен к виду, в котором подграф, образованный всеми максимальными ребрами, будет содержать цикл. Тогда любой цикл в этом подграфе- максимальный средний во всем графе, и других максимальных средних циклов нет. Так как потенциальное преобразование не изменяет длин циклов, то найденный подграф искомый. Конструкция алгоритма в основном следует из алгоритма для циклических игр, но в силу отсутствия осциляций вершин, связанных с антагонизмом противников, число итераций (потенциальных преобразований) алгоритма оказывается лишь только квадратичным \У\2 (число элементарных операций на каждой итерации 0(|£||У|), более подробно см. главу III, параграф 2).

Замечание: конечно, такой подграф можно получить, используя сведение к линейному программированию, но гарантируемая верхняя оценка сложности такого поиска, конечно, будет выше, по крайней мере полиномиальная от размера входа [55], [60].

В заключении третьей главы рассматриваются стохастические конфликты. Стохастическая игра задается тройкой (С; Р; с), где С- ориентированный полный двудольный граф с долями А и В и множеством ориентированных ребер Е. Представлен псевдополиномиальный алгоритм решения таких игр с помощью потенциальных сжатий.

В четвертой главе проводится обобщающий анализ доказательств наличия равновесий в стационарных стратегиях в циклических играх с платежами по циклу типа средних [35], [36].

Во-первых, показывается независимость полученных максминных утверждений для некоторых платежей типа средних от известного случая среднего платежа (а) относительно сводимости одного функционала к другому.

Рассматривается игровая модель ((А, В; Е); с; /). Здесь (А, В; Е)- ориентированный, без тупиков граф с локальными платежами с : Е -> ф и платежным функционалом / : —> <3, дающим вес (иногда используется тождественный термин- платеж, значение) произвольного цикла по множеству его локальных платежей.

Существенным является выполнение следующего условия для функционала /: найдется рациональная константа а такая, что для любого множества рациональных чисел {сх, .,с4} и любого рационального Л выполнено следующее: с! + Н,., а + /г}) = /({сь ., с4}) + ак

Такие функционалы будем называть функционалами типа среднего. Все функционалы (а), (Ь), (с) данным свойством обладают.

Циклическая игра проходит по ребрам графа до первого цикла г и платеж первого игрока второму есть /(г), первый минимизирует данный вес, второй его максимизирует.

Рассматрим два функционала типа средних /1 и /2, заданных на всевозможных конечных подмножествах множества рациональных чисел.

Скажем, что функционал /1 сводится к функционалу /2, если для произвольного конечного множества М{гу, .¡г^ рациональных чисел можно представить множество рациональных чисел такое, что при естественном взаимно однозначном соответствии между элементами этих множеств 1р сохраняется порядок весов подмножеств этих множеств, т.е. неравенство ¡\(М\) < /1(М2) влечет выполнение неравенства /2(у(М1)) < /2(<£>(Л/2)). ( Множества, равные по функционалу Д, могут переходить в неравные по функционалу /2).

Если функционал /1 сводится к функционалу /2, и имеет место результат о наличии равновесных стационарных стратегий в циклической игре с функционалом /2, то имеет место результат о наличии равновесия в стационарных стратегиях в циклической игре с функционалом /1.

Оказывается функционал (с) не сводим к фукционалу (а). Контрпример построен в параграфе 3. Функционал (Ь) сводим к функционалу (а). Доказательство в параграфе 2.

Во-вторых, используя более слабое понятие сводимости одного функционала к другому, удается получать утверждения о равновесии в стационарных стратегиях.

А именно, для доказательства утверждения о стационарном равновесии достаточно справедливости утверждения расщепления для функционала типа среднего по циклу / относительно нуля.

Тогда в силу того, что функционал / - типа среднего, справедлив результат о расщеплении относительно произвольного рационального «/, и тогда в силу конечности числа циклов справедлива теорема о наличии стационарного равновесия.

Поэтому для существования стационарного равновесия достатоточно слабого сведения.

Функционал типа среднего Д слабо сводится к функционалу типа среднего /2, если для произвольного конечного множества ., рациональных чисел можно представить множество рациональных чисел

М{¿1,., ¿4}, что при естественном взаимно однозначном соответствии между элементами этих множеств у сохраняются знаки весов подмножеств этих множеств, т.е. если }\(М') > 0, то /2(у(М')) > 0, и если /1 (Л/') < 0 , то /2((р(М')) < 0 для произвольного подмножества Л/' С М.

Тогда, если функционал типа среднего /1 слабо сводится к функционалу типа среднего /2, и справедливо утверждение о наличии равновесия в стационарных стратегиях в циклической игре с функционалом /2, то справедливо утверждение о наличии равновесия в циклической игре с функционалом Д.

В четвертой главе показано, что функционалы (Ь), (с) слабо сводятся к функционалу (а). Первая редукция представлена в параграфе два, вторая - в параграфе три.

С помощью техники слабого сведения доказаны новые результаты существования стационарных равновесий в циклических играх.

Полученные результаты могут быть примененными в моделях [28],

13], [4], [5], [11]. Многие вопросы оптимального управления сводятся к задаче нахождения экстремальных средних циклов в соответствующем графе динамики системы. Одна из возможных интерпретаций задачи заключается в следующем. Состояние экономической системы определяется набором экономических показателей. Состояния разделяются на контролируемые, где экономические показатели детерминированы субъектом принятия решения, и на неконтролируемые, где показатели недетерминированы, известна только некоторая информация о них. Динамика описывается некоторой структурой- графом, переход из одного состояния в другое означает возможность управления за единичный временной лаг, при котором система, действительно, совершит данный переход. Причем, в понятие совершит включаются общие рэндомизированные возможности поведения системы. За несколько временных лагов в результате определенных управленческих решений система пройдет некоторую траекторию переходов. Причем, переход системы в очередное состояние находится в распоряжении лица, принимающего решение только в контролируемых состояниях. Каждый переход дает определенный выигрыш (или проигрыш) лицу принимающему решение. В максимизации (или минимизации) общего выигрыша типа средних и состоит задача управления. Мы рассматриваем асимптотическую задачу управления системой на бесконечном интервале времени, поэтому общие выигрыши берем средними в расчете на один ход. Поведение системы в неконтролируемых состояниях неоднозначно, поэтому поставленная задача управления некорректна. Исходя из принципов гарантируемого результата и принципа среднего [28], будем оценивать поведение системы в неконтролируемых состояниях. Второй принцип осреднения поведения системы в неконтролируемых состояниях приводит к задаче оптимизации дохода на соответствующей марковской цепи. Эта задача сводится к линейному программированию [65], поэтому полиномиально разрешима.

В случае гарантированного результата считаем, что в неконтролируемых состояниях переход системы осуществляется противником, цель которого противоположна цели лица, принимающего решение, т.е. целью является минимизация (максимизация) общего выигрыша типа средних.

Такая постановка корректно интерпретирует как ситуацию двусторонней монополии [24] (т.е. при которой единственный продавец сталкивается с единственным покупателем), так и конкуренцию дуополии, когда одна из двух конкурирующих фирм играет на разорение другой.

В представленной динамической модели конкуренции показано наличие равновесия, которое является оптимальным поведением фирм. Этот результат качественно описывает положение гомеостазиса, когда ни одному из участников конфликта не выгодно уклоняться от своего поведения при фиксированном поведении противника. Найденные равновесные поведения противников структурно определяются порогом локального выигрыша, которого тот или иной противник форсированно добивается.

Другим приложением является проблема управления параллельными динамическими системами. В пятой главе рассматриваются игровые подходы к алгоритмическому анализу таких параллельных динамических систем.

Параллельная система включает множество компонентов, работающих одновременно. Стандартные подходы к формальному анализу параллельных систем обычно представляют системы как графы переходов.

Логические аспекты взаимодействия систем формализуются модальной логикой. Таким образом, вопрос надежного управления параллельной системой сводится к определению выполнимости формулы модальной логики.

Синтаксически формулы модальной логики представляют собой индуктивно построенные выражения над символами операций (->, V, А, <Я>, [Я], IСемантически формуле соответствует отображение из множества вершин Крипке- графа в множество вершин этого же Крипкеграфа состояний. Основная задача- определить значение формулы на заданном значении переменных.

В данной главе приведено упрощенное доказательство утверждения работы [68] и построено полиномиальное сведение вопроса выполнимости формулы модальной логики к решению циклических игр с симметрическим платежом по циклу. Нами использована игровая интерпретация, что упрощает первоначальное доказательство [68]. Таким образом, можно применить метод форсирования критической позиции для вычисления значений формул модальной логики. Является ли алгоритм форсирования критической позиции для вычисления формул модальной логики полиномиальным на данный момент времени не известно.

В работах по модальным логикам используются игры на четность (если максимальный локальный платеж по циклу четный- выигрывает первый игрок, если нечетный- то второй). Тривиально показать полиномиальную эквивалентность таких игр и игр с симметрическим платежом.

Решение циклических игр на четность проще, чем определение значения формулы непосредственно. Известные алгоритмические подходы к решению таких циклических игр представлены в работе [92] и ряде других. Хотя практическая выполнимость многих из разработанных алгоритмов эффективна, полиномиального алгоритма для решения циклических игр на данный момент времени нет и мало примеров полиномиальных подклассов данной задачи.

Мы показываем, что метод форсирования полиномиален для графов, все силыюсвязные компоненты которых сильноэргодические и в случае фиксированного приоретета стоимостной функции. Перечисленные случаи достижимы на некоторых неограниченных по мощности классах формул модальной логики, что дает полиномиальный алгоритм решения проблемы выполнимости таких формул модальной логики. В заключении пятой главы представлен полиномиальный алгоритм решения проблемы выполнимости для почти ациклических Крипке- графов. Здесь рекурсивно применяется алгоритм форсирования критической позиции [32] по слоям ациклического графа состояний. Это дает полиномиальный алгоритм решения динамической игры, и тем самым решается проблема выполнимости формулы модальной логики.

Результаты пятой главы представляются существенными в контексте построения надежных систем управления реального времени.

Еще одним приложением циклических игр являются задачи построения оптимального расписания [79]. В этой работе рассматриваются ограничения "и, или"предшествования для выполняемых работ. Показано, что задача построения расписания, минимального по времени выполнения всех работ, сводится к вопросу определения цены циклической игры с средним платежом по циклу (а).

Форсирование критической позиции, как конечно порождаемая ха-рактеризация циклических игр, является новым направлением в исследовании дискретных динамических конфликтов с полной информацией, имеющее важный контекст в модальной, темпоральной логиках и приложениях.

Далее мы используем нотацию теории графов, теории игр и сложности алгоритмов [48], [49], [1].

Параграфы относительно независимы, поэтому нумерация утверждений своя для каждого параграфа, ссылки даются на утверждения в одном и том же параграфе. Основные утверждения не нумеруются.

ЗАКЛЮЧЕНИЕ

Итогом дайной работы являются следующие основные результаты:

1. Разработана техника форсирования критической позиции для поиска оптимальных стратегий в циклических играх с полной информацией. Показано, что операцией дополнения шлейфа можно получить любую игровую сеть с заданной ценой, тем самым дается конечно порождаемая характеризация рассматриваемых игр.

Доказаны утверждения существования стационарных равновесий, описана их структура и показаны важные свойства- равномерность оптимальных стратегий и эргодичность цен.

Конструкция форсирования критической позиции дает полиномиаль-ность решения игр с максимальным платежом по циклу и важных подклассов игр с симметрическим платежом по циклу. В последнем случае конструкция форсирования полиномиальна для сильноэргодических игр и игр с фиксированным числом приорететов.

2. Техника форсирования использована для решения проблемы выполнимости формул модальной логики.

Получено упрощенное сведение проблемы выполнимости формул модальной логики к решению циклических игр с симметрическим платежом по циклу. При этом сведении сильноэргодические структуры достижимы, играм с фиксированным числом приорететов соответствуют формулы с фиксированным числом альтернаций операторов наименьшей и наибольшей неподвижных точек. Форсирование критической позиции полиномиально решает проблему выполнимости формул модальной логики на почти ациклических Крипке- графах.

3. Показана ИР- полнота задачи структурная неэргодичность. Представлен силыюполиномиальный алгоритм характеризации всех максимальных средних циклов в графе посредством потенциальных преобразований. Разработан псевдополиномиальный алгоритм решения стохастических игр с полным графом переходов.

Возможными приложениями полученных результатов являются: верификация программ, оптимизация иерархических систем управления и построение экономных расписаний.

Форсирование критической позиции, как конечно порождаемая ха-рактеризация циклических игр, является новым направлением в исследовании дискретных динамических конфликтов с полной информацией, имеющее важный контекст в модальной, темпоральной логиках и приложениях.

Благодарю Ю.И.Журавлева, Г.С. Поспелова за основы научной работы, полученные мной в Московском Физико-Техническом Институте. Выражаю признательность В.И. Цуркову, А.Н.Катулеву, М.А.Тайцлину за ценные советы при подготовке диссертационной работы.

1. А.Ахо, Дж. Ульман. Анализ и построение вычислительных алгоритмов. М.: Мир. 1979.

2. Ашманов С. А. Линейное программирование. М.: Наука. 1981.

3. Берж К. Теория графов и ее применения. М.: ИЛ. 1962.

4. Бурков В.Н., Опойцев В.И. Метаигровой подход к управлению иерархическими системами // Автоматика и телемеханика. N. 1. С. 103-114.

5. Бурков В.Н., Опойцев В.И. Распределение ресурсов в активной системе. В кн.: Активные системы. М.: ИПУ. 1973.

6. Воеводин В. В. Вычислительные основы линейной алгебры. М.: Наука. 1977.

7. Воробьев H.H. Современное состояние теории игр // УМН. В. 25. N. 2. 1970. С 81-140.

8. Воробьев H.H. Конечные бескоалиционные игры // УМН. В. 14. N. 4. 1959. С. 56-84.

9. Воробьев H.H. Бескоалиционные игры // Проблемы кибернетики. Вып. 33. М.: Наука. 1978. С. 69-90.

10. Врублевская И.Н. Эквивалентность смешанных стратегий и стратегий поведения в счетной позиционной структуре. // Матричныеигры (под ред. Воробьева H.H.) М.: Физматгиз. 1961. С. 246-250.

11. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука. 1976. 256. С.

12. Горелик В.А., Кононенко А.Ф. Теоретико-игровые модели принятия решений в эколого-экономических системах. М.: Радио и связь. 1991. 287 С.

13. Горелик В.А., Горелов М.А., Кононенко А.Ф. Анализ конфликтных ситуаций в системах управления. М.: Радио и связь. 1991. 287 С.

14. Горелик В.А. Максминные задачи на связных множествах в банаховых пространствах // Кибернетика. N. 1. 1983. С. 64-67.

15. Горелик В.А. Приближенное нахождение максмина с ограничениями, связующими переменные // ЖВМиМФ. N. 3.1975. С. 599-607.

16. Горелик В.А., Федоров В.В. Метод внешней точки в задаче определения кратного максмина с ограничениями // ЖВМиМФ. N. 3. 1975. С. 599-607.

17. Гурвич В. А., Карзанов А. В., Хачиян JI. Г. Циклические игры и нахождение минимаксных средних циклов в ориентированныхграфах // ЖВМ МФ. Т. 28. N. 9. 1988. С. 1407-1417.

18. Гурвич В. А., Лебедев В. Н. Критерий и проверка эргодичности игровых форм // УМН В. 44. N. 1. 1989. С. 193-194.

19. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

20. Демьянов В.Ф. О задаче минмакса при связных ограничениях // ЖВМиМФ. N. 3. 1972. С. 799-804.

21. Доманский В.К. Стохастические игры (обзор) // Математические вопросы кибернетики. В. 1. М.: Наука. 1988. С. 26-49.

22. Дрешер М. Стратегические игры. М.: Советское радио. 1964.

23. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов // Кибернетика. N. 4. 1977.

24. Загорулько М.М., Иншаков О.В. Основы экономической теории и практика рыночных реформ в России. М.: Логос. 1997.

25. Карзанов A.B. О минимальных по среднему весу разрезах и циклах ориентированного графа // Качественные и приближенные методы исследования операторных уравнений (под редакцией Климова В. С.) Ярославль.: ЯрГУ. 1985. С. 72-83.

26. Карлин С. Математические методы в теории игр, программировании и экономике. М.: Мир. 1964

27. Кифер Ю.И. Оптимальное поведение в играх с неограниченной последовательностью ходов // ТВП. В. 14. N. 2. 1969. С. 279-286.

28. Кононенко А.Ф., Халезов А.Д., Чумаков В.В. Принятие решений в условиях неопределенности. М.: ВЦ АН СССР. 1991.

29. Красносельский М.А., Забрейко П.П. Геометрические методы нелинейного анализа. М.: Наука. 1975.

30. Кук С. А. Сложность процедур вывода теорем // Кибернетический сборник. Новая серия. М.: Мир. 1975. С. 5-15.

31. Кун Г.У. Позиционные игры и проблема информации // Матричные игры ( под редакцией Воробьева H.H. ) М.: Физматгиз. 1961. С. 13-40.

32. Лебедев В.Н. Поиск и структура стационарных равновесий в циклических играх // Математические заметки. Т. 67. N. 6. 2000. С. 913-921.

33. Лебедев В.Н. О новом равновесии в циклических играх// Дискретная математика. Т. 9. N. 4. 1997. С. 96-99.

34. Лебедев В.Н. Алгоритмы оптимизации стационарных управлений в дискретных динамических системах. Дисс. к.ф.-м.н. М: МФТИ. 1990.

35. Лебедев В.Н. Стационарные равновесия в циклических играх на графах // Вестник ВолГУ. Сер. Матем., Физика. В. 3. 1998. С. 83-86.

36. Лебедев В.Н. О равновесиях в циклических играх на графах // Вестник ВолГУ. Сер. Матем., Физика. В. 1. 1996. С. 72-74.

37. Лебедев В.Н. Поиск всех максимальных средних циклов в графах. // Известия РАН. Теория и системы управления. N 6. 2001.

38. Лебедев В.Н. Эффективно решаемые классы циклических игр// Известия РАН. Теория и системы управления. N. 4. 2005. С. 44-49.39. 16. Лебедев В.Н. Игровой аспект верификации программ// Известия РАН. Теория и системы управления. N. 5. 2005. С. 40-45.

39. Лебедев В.Н. Вероятностный полиномиальный алгоритм, решающий одну из двух NP-полных задач// Интеллектуальные системы. Т. 5. В. 1-4. 2000. С. 247-255.

40. Лыос Р., Райфа X. Игры и решения. М.: 1961.

41. Матричные игры (под редакцией Воробьева H.H.) М.: Физматгиз. 1961.

42. Миронов A.A., Цурков В.И. Транспортные и сетевые задачи с минимаксным критерием // ЖВМ МФ. Т. 35. 1995. С. 24-45.

43. Моисеев H.H. Математические задачи системного анализа. М.: Наука. 1981. 487 С.

44. Опойцев В.И. Нелинейная системостатика. М.: Наука. 1986.

45. Опойцев В.И. Равновесие и устойчивсть в моделях коллективного поведения. М.: Наука. 1977.

46. Опойцев В.И. Топологические методы в теории сложных систем // Автоматика и телемеханика. N. 3. 1976. С. 142-160.

47. Ope О. Теория графов. М.: Наука. 1968.

48. Оуэн Г. Теория игр. М.: Мир. 1971.

49. Партхасаратхи Т., Рагхаван Т. Некоторые вопросы теории игр двух лиц. М.: Мир. 1974.

50. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М: Мир. 1985.

51. Позиционные игры (под редакцией Воробьева H.H. и Врублевской И.Н.). М.: Физматгиз. 1963.

52. Проблема программно-целевого планирования и управления. Поспелов Г.С., Вен B.JL, Солодов В.М., Шафранский В.В., Эрлих А.И. М.: Наука. 1980.

53. Робинсон Дж. Итеративный метод решения игр // Матричные игры (под редакцией Воробьева H.H.). М.: Физматгиз. 1961.

54. Схрейвер А. Теория линейного и целочисленного программирования. Т. 1. М.: Мир. 1991.

55. Федоров В.В. Численные методы максмина. М.: Наука. 1979. 280 С.

56. Фон-Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука. 1970

57. Фрид Е.Б. О стохастических играх // ТВП. Т. 18. N. 2. 1973. С. 389-393.

58. Харари Ф. Теория графов. М: Наука. 1973.

59. Хачиян JI. Г. Полиномиальные алгоритмы в линейном программировании //ЖВМ МФ. Т. 20. N 1. 1980. С 51-68.

60. Ховард Р. Динамическое программирование и марковские процессы. М.: Сов. радио. 1964.

61. Цурков В.И. Динамические задачи большой размерности. М.: Наука. 1988.

62. Яновская Е.Б. Антагонистические игры //Проблемы кибернетики. В. 34. 1978. С. 34-56.

63. Bellmann R. Dynamic Programming. Princeton University Press. Princeton. 1957.

64. Denardo E.V. On Linear Programming in a Markov Decision Chain // Manaeg. Sci. V. 16. 1970. P. 281-288.

65. Denardo E.V. Contraction mappings in the theory underlying dynamic programming // SIAM Review. N. 2. V. 9. 1967. P 165-177.

66. Ehrenfenfeucht A., Mycielski J. Positional strategies for mean payoff games // Intern. J. Game Theory. V. 8 N. 2. 1979. P. 109-113.

67. Emerson E.A. Jutlu C.S. Sistla A.P. On model-checking for fragments of /¿-calculus. Fifth International Conference on Computer Aided Verification, Elounda, Greece, June/July 1993.

68. Emerson E.A. Jutla C.S. Tree automata, mu-callculus and determinacy. In Proceedings of 32nd Annual Symposium on Foundations of

69. Computer Science. P. 368-377. IEEE Computer Society Press. 1977.

70. Federgruen A., Schweitzer R. Contraction mappings underling undiscounted Marcov decision problems //J. Math. Anal. Appl. V. 65. 1978. P. 711-730.

71. Gillette D. Stochastic games with zero stop probabilities // Ann. Math. Stud. V. 39. 1957. P. 178-187.

72. Kakutani S. A generelization on Brouwer's fixed point // Duke Math. J. V. 8. 1941. P. 457-458.

73. Karp R.M. A charucterization of the minimum cycle meaning in a digraf // Discrete Mathematics V. 23. N. 3. 1978. P. 309-311.

74. Karzanov A. V., Lebedev V. N. Cyclical games with prohibitions // Mathematical Programming V. 60. 1993. P. 277-293.

75. Karzanov A.V., Mccormick S.T. Polynomial methods for separable convex optimization in unimodular linear spaces with applications // SIAM J. Comput. V. 26. N. 4. 1997. P. 1245-1275.

76. Karzanov A.V. Minimal mean weight cuts and cycles in directed graphs // Amer. Math. Soc. TYansl. V. 158. N. 2. 1994. P. 47-55.

77. Kuzjurin N.N. An algorithm for integer programming polynomial in the average case// Soviet Mathematics Doklady. 1995, V 343, N 1.

78. Mertens J.F., Neyman Stochastic games // Int. J. Game Theory. V. 10. 1981. P. 53-66.

79. Mohring R.H., Skutella M., Stork F. Scheduling with "and, or"precedence constraints. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'OO)

80. Moulin H. Extention of two-person zero sum games //J. Math. Anal. Appl.

81. Pisaruk Mean cost cyclical games // Mathematics of Operations Research. 1999, V 24, N 4.

82. Poranen T., Nummenmaa J. A linear time special case for MC Games// Fundamenta Informaticae. 2002, V 50, N 3.

83. Sahni S. Coputationally related problems// SIAM J.Comput. 1974. Vol. 3.

84. Schaefer T.J. Complexity of some two-person perfect- information games// J.Comput. System Sci. 1978 Vol. 16.

85. Schweitzer P., Federgruen A. Geometric convergence of value-iteration in multichain markov decision problems. // Adv. Appl. Prob. V. 11. 1979. P.188-217.

86. Shapley L.S. Stochastic games // Proc. Nat. Acad. Sci. USA. V. 39. 1953. P. 1095-1100.

87. Stockmeyer L.J., Meyer A.R. Word problems requiring exponetial time. 5th Annual ACM Symposium on Theory of Computing, P.l-9.

88. Stockmeyer L.J., Chandra A.K., Provably difficult combinatorial games. Report N RC-6957, IBM, Thomas J. Watson Research Center, York-town Heights, NJ.

89. Vrize O.J. Zero-sum sthochastic games // CWI Quarterly V. 2. N. 2.1989. P. 147-170. V 55. N. 2. 1976. P. 165-178.

90. White D. Dynamic programming, Marcov chains and the method of successive approximations //J. Math. Anal. Appl. V. 6. N. 3. 1963. P. 373-376.

91. Hoffman A., Karp R. On nonterminaling stochastic games. Management Science. 12:359-370, 1966

92. Jens Voge, Marein Jurdzinski. A Descrete Stratege Improvement Algorithm for Solving Parity Games. // Basic Research in Computer Science, Centre of Danish Science Foundation. 2000

93. Zermelo E. Uber eine Anwendung der Mengenlehere auf die Theorie des Schaspiels, Proc. 5-th Congress of Mathematicians, Cambridge, 1912, Cambridge Univ. Press.

94. Zwick U., Paterson M. The complexity of mean payoff games on graphs. Theoretical Computer Sciense, 158:343-359, 1996.