Структура и поиск стационарных управлений в циклических играх с полной информацией тема диссертации и автореферата по ВАК РФ 05.13.01, доктор физико-математических наук Лебедев, Василий Николаевич

• Лебедев, Василий Николаевич
• доктор физико-математических наук
• 2005

Оглавление диссертации доктор физико-математических наук Лебедев, Василий Николаевич

Введение

Глава 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. Показана ИР- полнота задачи структурная неэргодичность. Представлен силыюполиномиальный алгоритм характеризации всех максимальных средних циклов в графе посредством потенциальных преобразований. Разработан псевдополиномиальный алгоритм решения стохастических игр с полным графом переходов.

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Лебедев, Василий Николаевич, 2005 год

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.