Авторефераты по всем темам >>
Авторефераты по разное
САНКТЦПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ На правах рукописи
Слобожанин Николай Михайлович
ИНФОРМАЦИЯ И РАВНОВЕСИЕ В МНОГОШАГОВЫХ ИГРАХ
01.01.09 дискретная математика и математическая кибернетика А В Т О Р Е Ф Е Р А Т диссертации на соискание ученой степени доктора физикоЦматематических наук
Санкт-Петербург 2012
Работа выполнена в СанктЦПетербургском государственном университете на факультете прикладной математики - процессов управления.
Научный консультант: доктор физикоЦматематических наук, профессор Л.А. Петросян (СПбГУ)
Официальные оппоненты: доктор физикоЦматематических наук, профессор Захаров Виктор Васильевич (СПбГУ) доктор физикоЦматематических наук, профессор Луценко Михаил Михайлович (ПГУПС, Санкт-Петербург) доктор физикоЦматематических наук, профессор Мазалов Владимир Викторович (ИПМИ Карельского Н - РАН, Петрозаводск)
Ведущая организация: Вычислительный центр им. А.А. Дородницына РАН
Защита состоится "25"апреля 2012 г. в 16 часов на заседании диссертационного совета ДЦ212.232.59 по защите диссертации на соискание учёной степени доктора физикоЦматематических наук при СанктЦПетербургском государственном университете по адресу: 199004, г. СанктЦПетербург, Средний пр. В.О., 41.
С диссертацией можно ознакомиться в библиотеке им. М. Горького Санкт - Петербургского государственного университета по адресу: 199034, г. Санкт - Петербург, Университетская наб., 7/9.
Автореферат разослан " " 2012 г.
Учёный секретарь диссертационного совета ДЦ212.232.доктор физикоЦматематических наук, профессор В.Д. Ногин
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Теория многошаговых игр занимается изучением управления изменяющихся систем в условиях конфликта или неполноты информации. По этой причине на протяжении последних восьми десятилетий наблюдается большой интерес к созданию математических моделей, теории и методов решения многошаговых игр.
Основой построения математической модели конфликтного процесса является строгое адекватное действительности определение его информационной структуры. Первоначально в работах Джона фон Неймана, Г. Куна и др. для конечных многошаговых игр с зависимой динамикой (позиционных игр) информационная структура процесса моделировалась посредством разбиения пространства игры на информационные множества игроков. Это безусловно строгий подход, но обладает одним существенным недостатком - чрезмерной общностью подхода, что затрудняет построение методов нахождения оптимальных стратегий игроков. Основополагающей работой по информационному анализу позиционных игр является работа Г. Куна "Позиционные игры и проблема информации", в которой автор для конечных игр доказал теорему о необходимых и достаточных условиях равенства выигрыша игроков в смешанных стратегиях и соответствующих им стратегиях поведения. Это условие было названо Куном полной памятью для игроков. В дальнейшем эта теорема была обобщена Л.А. Петросяном для бесконечношаговых позиционных игр с конечным множеством альтернатив и нобелевским лауреатом Р. Дж. Ауманом для бесконечношаговых позиционных игр с множеством альтернатив произвольной мощности. Однако, отметим, что требование полной памяти довольно сильное требование (игрок в каждый момент времени должен помнить всё, что совершил и знал ранее). При более слабых ограничениях на память игрока в игре теоремы об эквивалентности некоторого подкласса смешанных стратегий всему классу смешанных стратегий были доказаны Н. Н. Воробьёвым.
Настоящая диссертация посвящена многошаговым играм с разделёнными динамиками игроков. Одной из первых задач данного класса игр является интересная проблема о корабле, маневрирующим так, чтобы минимизировать вероятность его поражения бомбардировщиком, летящим над ним, сформулированная Р. Айзексом из РЭНДЦКорпорейшн и представленная им на конференции Американского общества по исследованию операций 16 мая 1953 г. Он же предсказал значение этой игры. В 1957 году независимо С. Карлином и Л. Э. Дубинсом эта игра была решена для постоянной задержки информации у корабля равной двум и полной информации у бомбардировщика при конечных альтернативных множествах. Автором настоящей диссертации в 19г. доказана теорема о необходимых и достаточных условиях оптимальности стратегий поведения корабля для случая произвольной конечной задержки информации у корабля. Одной из первых фундаментальных работ в области многошаговых игр с разделёнными динамиками является работа Х. Э. Скарфа, Л. С. Шепли "Игры с неполной информацией". В ней авторы рассмотрели бесконечношаговые антагонистические игры с постоянными положительными задержками информации у игроков, с конечными альтернативными множествами. При предположении непрерывности функции выигрыша были получены функциональные уравнения, связывающие значения подыгр соседних уровней.
На основании этих уравнений был получен метод решения упомянутого выше класса многошаговых игр.
В 1969 году вышла работа Д. Блэкуэлла, в которой автор исследовал вопрос существования значения в играх с конечными альтернативными множествами, с нулевыми задержками информации, с функциями выигрыша, имеющим вид характеристических функций. В 1972 году были опубликованы работы М. Оркина об играх, рассмотренных Х. Э. Скарфом и Л. С. Шепли, в которых изучен вопрос о приближении значения игры значениями других игр, функции выигрыша которых сходятся сверху к функции выигрыша первоначальной игры.
Говоря об играх с неполной информацией, необходимо сказать о довольно развитой области теории игр с неполной информацией - дифференциальных играх с неполной информацией, которые могут быть сведены к играм с полной информацией, что в свою очередь позволяет использовать известный аппарат дифференциальных игр. В значительной степени этот класс игр был исследован Н. Н. Красовским и его учениками. Этому же вопросу посвящены работы Ф. Л. Черноусько и А. А. Меликяна. Представляют интерес работы М. С. Никольского, в которых приводятся достаточные условия для завершения преследования за конечное время при неполном знании преследователем фазового положения или динамики убегающего. Проблема вывода функциональных интегральных уравнений в дифференциальных играх преследования с постоянной задержкой информации у преследователя, несводимых к играм с полной информацией, нашла отражение в работах Л. А. Петросяна. Значение информации о функции цели противника в играх двух лиц, основы информационной теории иерархических систем, исследованы в работах Н. Н. Моисеева, Ю. Б. Гермейера, А. Ф. Кононенко и его учеников. Анализ равновесия в различных классах стратегий в дифференциальных играх с полной информацией приведён в работах А. Ф. Кононенко, О. А. Малафеева, С. В. Чистякова. Прикладные аспекты теории многошаговых игр исследованы в работах А. А. Васина, В. В. Мазалова и других зарубежных и отечественных учёных.
В настоящей диссертации впервые информационная структура многошаговых игр с разделёнными динамиками моделируется посредством информационных векторЦфункций игроков. Производится анализ таких функций. Последнее позволяет, в частности, для антагонистических игр с переменными задержками информации у игроков, произвольной продолжительности (как конечной, так и бесконечной), с динамиками, определяемыми произвольными функциями достижимости, получить функциональные интегральные уравнения, связывающие значения подыгр соседних уровней. На базе этих уравнений в диссертации строится метод решения многошаговых антагонистических игр с неполной информацией. Таким образом, на основании вышеизложенного можно утверждать, что в диссертации исследуется актуальные проблемы конфликтных процессов.
Цель работы заключается в построении математической модели развёрнутой формы многошаговых игр с разделёнными динамиками с множеством игроков произвольной мощности, основой которой является определение информационной структуры игры, а также методов и алгоритмов решения различных подклассов рассматриваемого класса игр.
Методы исследования. Доказательство основных результатов диссертации опираются на классические методы теории игр, функционального анализа и теории вероятностей.
Научная новизна. Впервые для описания информационности игрока в многошаговых играх с разделёнными динамиками вводится информационная векторЦфункция. Впервые приведена аксиоматика развёрнутой формы многошаговых игр с разделёнными динамиками, основой которой является, введённое и исследованное в диссертации, условие информационной разрешимости упорядоченного по игрокам набора информационных векторЦфункций.
На множествах траектории игры и чистых стратегий игроков вводятся топологии А. Н. Тихонова. Показано, когда данные топологии можно задать метриками, аналогичными метрике Бэра. В многошаговых играх с зависимыми динамиками отображение, сопоставляющее ситуации в чистых стратегиях единственную порождённую ею траекторию, непрерывно. В играх с разделёнными динамиками это не всегда так. Впервые получена и доказана теорема о необходимых и достаточных условиях, когда упомянутое отображение непрерывно для игр с разделёнными динамиками. Это условие связывает геометрические и информационные характеристики многошаговой игры.
На базе упомянутой выше теоремы для многошаговых игр с разделёнными динамиками с не более чем счётным множеством игроков, с полной информацией, произвольной продолжительности, с произвольными непрерывными функциями выигрыша доказана теорема о необходимых и достаточных условиях существования равновесия по Нэшу в чистых стратегиях, которая развивает и обобщает теоремы ЦермелоЦНеймана и ГейлаЦСтюарта. Для того же класса игр для полунепрерывных сверху функций выигрыша доказаны теоремы существования Цравновесия в игре в чистых стратегиях и построены алгоритмы нахождения - равновесных чистых стратегий. Доказана также теорема существования седловой точки в играх преследования с полной информацией в произвольном пространстве, когда выигрыш преследователя определяется поглощением преследуемого множеством достижимости преследователя.
Для многошаговых игр с разделёнными динамиками, с множеством игроков произвольной мощности впервые вводится понятие измеримой стратегии поведения, по ситуации в измеримых стратегиях поведения строится мера на множестве траекторий игры, исследуются свойства этой меры.
Впервые для многошаговых антагонистических игр с переменными задержками информации у игроков, которые могут принимать отрицательные значения, вводится определение подыгры. Впервые для того же класса игр на основании полученных в диссертации свойств меры на множестве траекторий игры вводятся и обосновываются функциональные интегральные уравнения, связывающие значения подыгр соседних уровней. Эти уравнения развивают и обобщают уравнения Х. Э. Скарфа, Л. С. Шепли, Л. А. Петросяна.
На базе функциональных интегральных уравнений впервые определяется и обосновывается метод решения многошаговых антагонистических игр с разделёнными динамиками, с переменными задержками информации у игроков.
Практическая ценность. Полученный в диссертации метод решения многошаговых антагонистических игр с переменной задержкой информации может быть положен в основу исследования игровых задач с неполной информацией, которые служат моделями развёртывающихся во времени процессов. В частности, его модно использовать при исследовании задач управления системами при частично известных возмущающих воздействиях, при решении задач планирования с заранее неопределёнными параметрами. Введённые в диссертации информационные векторЦфункции и условие информационной разрешимости упорядоченного по игрокам набора информационных векторЦфункций могут быть использованы для дальнейшего исследования информационных конфликтных процессов, в частности, для информационной классификации таких процессов, начало которой приведено в диссертации.
Положения, выносимые на защиту.
1. Математический анализ информационной структуры многошаговых игр с разделёнными динамиками и на базе этого аксиоматика развёрнутой формы многошаговых игр с разделёнными динамиками, основой которой является условие информационной разрешимости упорядоченного по игрокам набора информационных векторЦфункций.
2. Необходимые и достаточные условия непрерывности отображения, сопоставляющего ситуации в чистых стратегиях единственную порождённую ею стратегию для многошаговых игр с разделёнными динамиками. Получение с помощью этого условия необходимых и достаточных условий существования равновесия по Нэшу, - равновесия в многошаговых играх с полной информацией и седловой точки в играх преследования с полной информацией.
3. Построение меры на множестве траекторий многошаговой игры с разделёнными динамиками с множеством игроков произвольной мощности по измеримым стратегиям поведения. Исследование свойств этой меры.
4. Построение о обоснование функциональных интегральных уравнений, связывающих значения подыгр соседних уровней для многошаговых антагонистических игр с переменной задержкой информации.
5. На базе функциональных интегральных уравнений построение метода решения многошаговых антагонистических игр с разделёнными динамиками, с переменными задержками информации у игроков.
Апробация работы. Основные положения и результаты работы докладывались и обсуждались на международном конгрессе по компьютерным системам и прикладной математике (СанктЦПетербург, 1993 г.); международной конференции по интегральным и алгебраическим вычислительным методам в науке и технике "Интеграл - 94"(СанктЦПетербург, 1994 г.); международных научных конференциях "Многокритериальные и игровые задачи"(Орехово - Зуево, 1994, 1996 гг.); международном симпозиуме по водородной энергетике и технологии HYPOTHESISЦIII, секция "Экономика и моделирование высокотехнологичных социальноЦэкономических процессов"(СанктЦПетербург, 19г.); международной конференции Control Applications of Optimization (11th IFAC) (СанктЦПетербург, 2000 г.); межвузовской конференции молодых учёных (Москва, МФТИ, 1989 г.); всероссийской конференции "Понтрягинские чтения - IV"( Воронеж 1993 г. ); III Московской международной конференции по исследованию операций (ORM2001) ( Москва, 2001 г. ), а также на городских научных семинарах по теории игр под руководством профессора Н. Н. Воробьева (ИСЭП, Ленинград, 1982Ц1984 гг.), городских научных семинарах по теории вероятности под руководством академика И. А. Ибрагимова ( ЛОМИ, Ленинград, 1984Ц1985 гг.); городских научных семинарах по теории игр под руководством Л. А. Петросяна ( факультет ПМЦПУ СПбГУ, СанктЦПетербург, 1990Це - 2000Це гг.); научном семинаре по теории игр института математики и механики УрО РАН под руководством чл. корр. РАН А. Г. Ченцова ( Екатеринбург, 20г.), на научном семинаре по теории игр В - РАН под руководством профессора А. Ф. Кононенко ( Москва, 2003 г.); на научном семинаре по теории игр МГУ кафедры исследования операций под руководством профессора А. А. Васина ( Москва, 2003 г.), а также на научных семинарах кафедры моделирования социальноЦэкономических систем факультета прикладной математики - процессов управления СанктЦПетербургского государственного университета под руководством профессора О. А. Малафеева ( СанктЦПетербург, 1992Ц2011 гг. ) Публикации. Результаты диссертации опубликованы в 43 научных работах, в том числе - в одной монографии объёмом 308 страниц.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Общий объём диссертации - 270 страниц. Список литературы включает 124 наименования.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснованы актуальность, научная новизна и практическая ценность результатов диссертации; сформулированы цель, методы исследования, основные результаты и положения диссертации, выносимые на защиту; дан краткий обзор известных по теме диссертации результатов и приведено краткое изложение результатов диссертации.
В первой главе приведен математический анализ информационной структуры многошаговых игр с разделенными динамиками, с множеством игроков произвольной мощности.
Обсудим терминологию. Рассмотрим произведение множеств Z = Z, B где B также некоторое множество. Элементы множества Z будем называть упорядоченными наборами, равно векторами, равно точками и обозначать:
z = (..., z,...) = (z, B).
Пусть A непустое множество произвольной мощности. В дальнейшем, при интерпретации A часто будем отождествлять с множеством игроков, а его элемент, скажем, с игроком (игроком с именем ). Сопоставим каждому элементу из A один и только один элемент из множества (N {0} {+}), где N множество натуральных чисел, и обозначим его T. При интерпретации число T можно рассматривать как количество ходов, которые должен совершить игрок . Если T = +, то мы считаем, что игрок совершит в процессе бесконечное (счетное) число ходов. Число T в философском аспекте можно рассматривать также и как личное время игры игрока . В общем случае личное время игры у разных игроков может быть различно. Предполагается также, что есть общее (внешнее) физическое время, реализуемое в виде дискретных моментов. В каждый из этих моментов, по крайней мере, один из игроков совершает ход. Другими словами, предполагается ФвложениеФ личного времени каждого игрока в общее физическое время. Последнее утверждение можно интерпретировать и так: общее физическое время процесса принятия решений ФскладываетсяФ (ФсинтезируетсяФ) из личных времен каждого участника процесса.
Обозначим через T множество всех целых чисел из отрезка [0, T], через 2T множество всех подмножеств множества T.
О п р е д е л е н и е 1. Всякое отбражение l : T 2T A будем называть информационной функцией игрока .
Тогда l(k) есть вектор, который в общем случае может быть произвольной (в том числе бесконечной) размерности. В соответствии с принятыми обозначениями можно записать: l(k) = (..., l(k),...), где принимает все значения из A и l(k) есть подмножество (которое может быть и пустым) множества T. Допускаем также и такое обозначение:
l(k) = (l(k), A).
О подмножестве l(k) будем говорить как о -й компоненте вектора l(k).
Содержательно l(k) есть подмножество номеров ходов игрока , которые необходимо и достаточно знать игроку для совершения (k + 1)-го хода. Обратим внимание на то, что среди компонент вектора l(k) = (..., l(k),...) присутствует и компонента l(k). Изначально на подмножество номеров ходов l(k) игрока , которые ему необходимо и достаточно знать для совершения (k + 1)-го хода, мы не накладываем никаких ограничений.
Далее будем рассматривать упорядоченные наборы информационных функций l = (..., l,...) = (l, A), т. е. точки из множества L = L, где A L множество всех информационных функций игрока . Нас будет интересовать их информационная разрешимость.
Рассмотрим произведение T = T. Содержательно всякий вектор A a = (..., a,...) (или в другом обозначении (a, A)) из T будем интерпретировать как информационный вектор количественного состояния процесса с игроками из множества A. При этом будем считать, что к некоторому моменту времени t игрок сделал a ходов. Будем говорить, что вектор a = (..., a,...) из T больше либо равен вектору b = (..., b,...) из T, и писать: a b, если a b для любого из A. Будем говорить, что вектор a = (..., a,...) из T не больше вектора b = (..., b,...) из T, если существует элемент из A, такой, что b > a. Это соотношение будем обозначать так: a b или b a. Таким образом множество T становится частично упорядоченным множеством. Часто векторы из T будем помечать верхним индексом и писать: ak = (..., ak,...).
О п р е д е л е н и е 2. Счетную последовательность векторов a0,..., ak,...
из T будем называть остовной, если 1) a0 = (..., 0,...);
2) для любого k из N либо ak+1 > ak, либо ak = ak+1 = ak+2;
3) ak + 1 ak+1 для любого из A и любого k из N;
4) lim ak = T.
k+ Из условия 2) определения 2. следует: если ak = ak+1 = ak+2, то ak+1 = ak+2 = ak+3 =.... Это соответствует случаю, когда в процессе принятия решений у каждого игрока число ходов конечно. Содержательно остовная последовательность соответствует реально развивающемуся процессу принятия решений с множеством игроков A. Она характеризует динамику принятия решений.
О п р е д е л е н и е 3. Будем говорить, что упорядоченный набор информационных функций (l, A) информационно разрешим на векторе a из T, если существует элемент A, такой, что sup(l(a)) a для любого из A.
В общем случае допускается, что множество l(a) может быть счетным.
Заметим также, что l(a) может равняться . Определим sup() = max() = 0.
Содержательно информационная разрешимость означает: в процессе игроками сделано столько ходов, что игроку достаточно информации, чтобы совершить свой ход с номером (a + 1).
Пусть l = (l, A) какой-либо упорядоченный набор информационных функций. Рассмотрим подмножество B множества A. Часто в дальнейшем будем говорить об информационной разрешимости упорядоченного набора информационных функций l = (l, B) на векторе a из T = T, пони B мая под значением l(a) сужение вектора l(a) (как вектора из множества 2T ) на компоненты с индексами из подмножества B.
A О п р е д е л е н и е 4. Будем говорить, что упорядоченный набор информационных функций l = (l, A) почти информационно разрешимый, если для любого подмножества B множества A упорядоченный набор информационных функций l = (l, B) информационно разрешим на всяком векторе a из T = T.
B Пусть l = (l, A) произвольный набор информационных функций.
Далее, пока не будет оговорено особо, все рассуждения будут производиться относительно данного упорядоченного набора.
О п р е д е л е н и е 5. Будем говорить, что вектор a из T l-порождает вектор b из T, если 1) a < b;
2) a + 1 b для любого из A;
3) a < b max(l(a)) a для любого из A.
О п р е д е л е н и е 6. Будем говорить, что вектор a из T максимально lпорождает вектор b из T, если 1) a < b;
2) a + 1 b для любого из A;
3) a < b max(l(a)) a для любого из A.
О п р е д е л е н и е 7. Счетную последовательность векторов a = a0, a1,..., ak,... из T назовем l-последовательностью, если 1) a0 = (..., 0,...);
2) для любого k из N выполняется условие: либо вектор ak l-порождает вектор ak+1, либо ak = ak+1 и не существует в T вектора, l-порожденного вектором ak.
О п р е д е л е н и е 8. Назовем счетную последовательность векторов a = a0, a1,..., ak,..., из T максимальной l-последовательностью, если 1) a0 = (..., 0,...);
2) для любого k из N выполняется условие: либо вектор ak максимально l-порождает вектор ak+1, либо в T нет векторов, l-порожденных вектором ak, и ak = ak+1.
Равенство ak = ak+1 в контексте с приведенными определениями равносильно равенствам ak = ak+1 = ak+2 =... = ak+m =.... Действительно, если бы вектор ak+2 был l-порожден вектором ak+1, то из-за равенства ak = ak+1 он был бы порожден вектором ak. Но ak не l-порождает ни одного вектора из T. В случае, когда множество игроков A конечно и все числа T конечны, разумно было бы определить l-последовательность как конечную. Однако при таком подходе появляется громоздкость в обозначениях. Поэтому случай конечных процессов вписан в общее определение при предположении, что при реальных рассмотрениях ФхвостФ ap+1 = ap+2 =... не будет учитываться (здесь p наименьшее число, при котором появляются равенства ap = ap+1 = ap+2 =...).
Теорема 1. Если существует остовная l- последовательность, то максимальная l-последовательность является остовной.
В диссертации показано, что в общем случае остовных последовательностей, соответствующих упорядоченному набору информационных функций, может существовать бесконечно много. Максимальная же остовная l- последовательность единственна.
Нас интересуют необходимые и достаточные условия существования остовной l-последовательности. Далее мы и займемся этими исследованиями.
Теорема 2. Если существует остовная l- последовательность, то упорядоченный набор информационных функций l = (l, A) почти информационно разрешим.
Теорема 3. Пусть множество A конечно. Тогда, для того чтобы существовала остовная l-последовательность необходимо и достаточно, чтобы упорядоченный набор информационных функций l = (l, A) был почти информационно разрешим.
Однако, в общем случае, когда |A| = +, теорема 3 не работает.
П р и м е р 1. Пусть множество имен игроков A совпадает с множеством натуральных чисел N. Пусть продолжительность процесса Ti для любого игрока i равна +. Определим информационную функцию li игрока i. Пусть li(0)i-1 = {1} при i 2, l1(1)j = {1} для любого j из N и li(k)j = {0} в остальных случаях, где k N, i N, j N. Покажем, что упорядоченный набор определенных таким образом функций (li, i N) удовлетворяет условию почти информационной разрешимости. Для этого рассмотрим произвольное подмножество B множества A и зафиксируем некоторый произвольный вектор a = (ar, r B) из множества Nr, где Nr = N для любого r из B. Нам rB надо показать информационную разрешимость упорядоченного набора информационных функций l = (lr, r B) на векторе a = (ar, r B). Рассмотрим полную группу возможностей для компонент вектора a = (ar, r B):
1) среди компонент вектора a есть компоненты, большие либо равные 2;
2) среди компонент вектора a есть компоненты, равные 0;
3) каждая компонента вектора a равна 1.
Рассмотрим случай 1. Пусть ar 2. Тогда по определению информационных функций lr(ar) = ({0r}, r B), где 0r = 0. Очевидно, что max{0r} ar для любого r из B. Полученные неравенства и означают требуемую почти информационную разрешимость.
Рассмотрим случай 2. Найдем компоненту вектора a равную нулю с наименьшим номером. Пусть это будет ar. Тогда если в множестве B есть элемент, равный r - 1, то компонента ar-1 больше либо равна 1. В этом случае получаем max(lr(ar)r-1) = 1 ar-1 и max(lr(ar)r) = 0 ar для элементов r из B, не равных r - 1. Полученные неравенства в векторной записи эквивалентны неравенству (max(lr(ar)r), r B) (ar, r B), что означает требуемую почти информационную разрешимость. Если в множестве B нет элемента r - 1, то max(lr(ar)r) = 0r = 0 ar для любого r из B. Последние неравенства, как и в случае 1, означают требуемую почти информационную разрешимость.
Рассмотрим случай 3. Здесь упорядоченный набор информационных функций (lr, r B) информационно разрешим на векторе (ar, r B), поскольку каждая функция lr ограничена единицей.
Таким образом, мы показали почти информационную разрешимость упорядоченного набора информационных функций l = {li, i N}. Но тем не менее, максимальная l-последовательность не является остовной. Чтобы это показать проанализируем каждый вектор ak максимальной l-последовательности.
Получаем:
a0 = (0,..., 0,...), a1 = (1, 0,..., 0,...), a2 = (1, 1, 0,..., 0,...),..................
ak = (1, k - 1, k - 2,..., 2, 1, 0,..., 0,...), k N.
Таким образом, ak = 1 для любого k из N, в то время как для остовной последовательности требуется, чтобы limk+ ak = +. Значит, наша максимальная l-последовательность не является остовной.
Итак мы показали, что условие почти информационной разрешимости не является достаточным для существования остовной l-последовательности для случая, когда множество игроков не менее чем счетно. Попытаемся определить необходимые и достаточные условия существования остовной l-последовательности в общем случае.
Рассмотрим множества T, A. Зафиксируем некоторый элемент из A и целое число k из множества T. Определим а л г о р и т м построения мно жеств упорядоченных пар вида (p, ), где A, p T для фиксированной упорядоченной пары (k, ).
М а к р о ш а г 0. Строим множество L0(k, ) = {(k, )}.
М а к р о ш а г 1. Строим множество L1(k, ). Если k = 0, то полагаем L1(k, ) = . Если k 1, то L1(k, ) = {k - 1, } {(p, )/ A, p l(k - 1)} М а к р о ш а г r. На r-м (r N, r 2) макрошаге строим множество Lr(k, ) = L1(i, ).
(i,)Lr-1(k,) О п р е д е л е н и е 9. Алгоритм, определенный выше, будем называть алгоритмом l-предыстории k-го хода игрока .
Обсудим это определение. Нетрудно заметить, что алгоритм l-предыстории состоит из счетного множества макрошагов. Из определения 9 следует, что если множество Lr(k, ) состоит лишь из элементов вида (0, ), то выполняются равенства = Lr+1(k, ) =... = Lr+n(k, ) =....
О п р е д е л е н и е 10. Длиной алгоритма l-предыстории k-го хода игрока назовем sup{r N/Lr(k, ) = }.
Отметим, что если первая компонента в паре (k, ) равна нулю, то по определению длина алгоритма равна нулю. Если алгоритм l-предыстории k-го хода игрока такой, что Lr(k, ) = для любого r из N, то его длина по определе нию равна +. Для каких упорядоченных наборов информационных функций l = (l, A) такое случается, будет выяснено далее.
О п р е д е л е н и е 11. Множество Lr(k, ) (r N) из определения 9 будем называть r-м слоем алгоритма l-предыстории k-го хода игрока .
Попробуем интерпретировать непустые слои Lr(k, ), которых в общем случае может быть счетное множество. О слое L1(k, ) можно говорить, как о множестве номеров ходов всех игроков, которые (ходы) необходимо и достаточно знать игроку для совершения k-го хода в некоторый момент времени tr, если он к этому моменту уже сделал (k - 1)-й ход. Тогда о всех непустых слоях Lr(k, ) алгоритма k-го хода игрока содержательно можно сказать так: для того, чтобы когда-либо состоялся k-й ход игрока , необходимо и достаточно, чтобы состоялся каждый ход p игрока для всякой пары (p, ), принадлежащей какому-нибудь слою Lr(k, ).
Ниже дадим основное определение гл. 1 определение информационной разрешимости упорядоченного набора информационных функций в общем случае:
О п р е д е л е н и е 12. Будем называть упорядоченный набор информационных функций l = (l, A) информационно разрешимым, если алгоритм l-предыстории k-го хода игрока имеет конечную длину для любого из множества A при любом k из T.
Определение 12 можно пояснить так: если упорядоченный набор информационных функций l = (l, A) информационно разрешим, то каждый ход каждого игрока произойдет за конечное время. Далее сформулируем основную теорему гл. 1.
Теорема 4. Пусть l = (l, A) упорядоченный набор информационных функций, где A непустое множество произвольной мощности. Для того чтобы существовала остовная l-последовательность векторов из T необходимо и достаточно, чтобы набор l был информационно разрешимым.
Из предыдущих рассуждений следует что, когда множество игроков A конечное, то условия почти информационной разрешимости и информационной разрешимости упорядоченного набора информационных вектор-функций l = (l, A) эквивалентны, поскольку оба они в данном случае равносильны условию существования остовной l-последовательности.
Далее в гл. 1 приводится анализ упорядоченных по игрокам наборов информационных вектор-функций с целью получения частичной информационной классификации многошаговых игр с разделенными динамиками. В частности получены и доказаны теоремы о необходимых и достаточных условиях для упорядоченным по игрокам наборов информационных вектор-функций, определяющих одновременные игры, поочередные игры, игры с полной информацией. Приведено в отличие от Г. Куна не стратегическое, а информационной определение игр с полной памятью.
В начале гл. 2 приводится аксиоматика развернутой формы многошаговых игр с разделенными динамиками, с множеством игроков произвольной мощности, основой которой является условие информационной разрешимости упорядоченного по игрокам набора информационных вектор-функций.
О п р е д е л е н и е 13. Развернутой формой многошаговой игры с разделенными динамиками относительно множества A будем называть упорядоченный набор объектов = ((X, x0, D, T, l, ), A), удовлетворяющий следующим аксиомам:
1) X множество, x0 X;
2) D : X 2X \;
3) T N {+};
4) l : T 2T, причем max(l(k)) = k и упорядоченный набор A (l, A) является информационно разрешимым;
T 5) : X R, где R множество вещественных чисел.
A Дадим названия объектам, определяющим набор , и интерпретируем развернутую форму, определяемую набором .
Для простоты понимания интерпретации введем следующие определения.
О п р е д е л е н и е 14. Очередью относительно множества A будем называть всякое отображение O : N 2A, такое, что, если O(i) = , то и O(i + 1) = .
О п р е д е л е н и е 15. Очередью, соответствующей остовной последовательности a = (ar), будем называть отображение O : N 2A, такое, что O(i) = { A|ai = ai-1 + 1}, где ai, ai-1 соответственно i-й и (i - 1)-й векторы остовной последовательности.
Для очереди, соответствующей остовной последовательности a, иногда будем использовать функциональное обозначение и писать: O(a).
Множество A будем называть множеством игроков или множеством имен игроков. При этом договоримся, что среди имен нет одинаковых. Отметим, что мы ничем не ограничиваем мощность множества A. Множество X будем называть пространством игры или множеством позиций (точек, элементов) игрока . Из определения следует, что оно не пусто и в общем случае может быть произвольной мощности. Элемент x0 пространства X является начальной позицией игрока . Отображение D определяет динамику передвижения игрока в пространстве X и называется его функцией достижимости. Множество D(x) есть множество позиций, куда может попасть игрок , находясь в позиции x. Число T количество ходов игрока в процессе принятия решений, которое в общем случае не пропорционально времени. При этом количества ходов для разных игроков могут быть разными и могут принимать бесконечные значения. Отметим, что символ T обозначает множество целых чисел в oтрезке [0, T]. Отображение l, как и в гл. 1, назовем информационной функцией игрока . Это вектор-функция (точнее, вектор-отображение), компонентами которой являются подмножества целых чисел. Отображение назовем функцией выигрыша игрока .
Интерпретация упорядоченного набора объектов будет следующей. Будем считать, что имеется счетная строго возрастающая последовательность моментов времени T = t0 < t1 < < tk < tk+1 <....
В момент t0 каждый игрок из множества A находится в своей начальной позиции x0. В некоторые моменты времени из последовательности T игроки совершают ходы (принимают решения). Ходом игрока , находящегося в позиции y X, будем называть выбор точки из множества D(y) и перемещение в нее. При этом не исключается случай, когда y D(y). Другими словами, если в данном случае игрок выберет y (останется на месте), все равно будем считать, что он совершил ход.
Правила совершения ходов игроками определяются следующим образом: в момент t1 игрок совершает ход тогда и только тогда, когда ((sup l(0)), A) (..., 0,... ).
Нетрудно заметить, что в силу определения информационных функций, в этом неравенстве sup можно заменить на max и само неравенство можно заменить равенством.
Пусть на промежутке времени [t0, tk] игрок совершил ходы x0, x1, x2,..., xak, т. е. количество его ходов равно числу ak. Иными словами, инфор мационный вектор количественного состояния (сдвига) процесса к моменту времени tk+1 есть ak = (ak, A). В момент tk+1 игрок совершает ход то гда и только тогда, когда он сделал не все ходы в процессе (ak < T) и когда выполняется векторное неравенство (max(l(ak )), A) ak.
Расшифруем последнее неравенство. Множество l(ak ) есть множество но меров тех ходов игрока , которые (ходы) необходимо и достаточно знать игроку , чтобы совершить свой (1+ak)-й ход. (Так предписано правилами игры, природы). И если max(l(ak )) ak, то такое знание реализуется. Если игрок сделал не все ходы и последнее векторное неравенство не выполняется, то в момент tk+1 он ход не делает (пропускает). Он ждет, пока остальные игроки сделают достаточные количества ходов, чтобы неравенство выполнялось. Такое обязательно случится, поскольку упорядоченный набор информационных функций l = (l, A) удовлетворяет условию информационной разрешимости. Действительно, если рассмотреть векторы ak и ak+1, о которых шла речь ранее, и предположить, что вектор ak является вектором максимальной l-последовательности, то и вектор ak+1 будет вектором максимальной l-последовательности (он образуется по правилам максимальной l-последовательности). Поскольку вектор a0 характеризует количества ходов, совершенных игроками на отрезке времени [t0, t0], то он равен (...,0,... ) нулевой вектор. Но и максимальная l-последовательность начинается вектором (...,0,... ). Следовательно, каждый вектор ak вектор максимальной l-последовательности. Поскольку в данном случае для векторов максимальной l-последовательности выполняется равенство limk ak = T для любого из A, то каждый игрок сделает все ходы.
Информированность игроков в процессе принятия решений следующая. С самого начала игроку , A, известна последовательность моментов времени T, упорядоченный набор (кроме информационных функций l, A\{} и функций выигрыша , A\{}) и правила, по которым игроки совершают ходы. Может появиться вопрос: как игрок определит количество ходов, совершенных каждым игроком на отрезке времени [t0, tk], т. е. вектор ak = (ak, A)? Ограничимся пока простым ответом: эта информация каждо му игроку сообщается неким нейтральным (а может быть заинтересованным?) игроком. Если в момент tk+1 игрок совершает ход, то кроме информации, о которой мы только что сказали, он знает ходы игрока , номера которых принадлежат множеству l(ak) для любого из A. Обратим внимание на то, что l(ak) есть лишь подмножество номеров ходов, совершенных игро ком на отрезке времени [t0, tk]. Множество номеров всех ходов игрока есть {0, 1, 2,..., ak}. В частности, подмножество l(ak) не обязано совпадать с множеством номеров всех ходов, сделанных самим игроком . Таким образом, наша модель допускает, что игрок может терять информацию и о себе. Но в силу определения max(l(ak)) = ak. Последнее означает, что игрок помнит свой последний ход, т. е. знает позицию xak, в которой находится сам.
Таким образом, если в момент tk+1 игрок совершает ход, то он помимо прочей информации, о которой было сказано, знает вектор iak = ((xr|r l(ak)), A), где xr есть реализация r-го хода игрока .
Мы уже упомянули о том, что в процессе принятия решений каждый игрок сделает все ходы. В итоге реализуется траектория игры:
s = (s, A), где s = (x1,..., xk, x(k+1),... ) = (xi)T, x(k+1) D(xk).
В Фконце игрыФ игрок получает выигрыш, равный (s). Естественно предположить, что в процессе принятия решений игрок своими решениями (ходами) стремится максимизировать значение функции (s).
Сделаем некоторые замечания к приведенной интерпретации. Мы сказали, что свой очередной ход игрок , находясь в точке xak, если совершает, то не раньше момента tk+1. К последнему надо относиться, как к идеализации. Более точно можно считать, что игроком решение о (1 + ak)-м ходе принимается, и сам ход совершается на отрезке времени (tk, tk+1].
Скажем несколько слов об очередности (очереди), в соответствии с которой игроки осуществляют ходы. Предположим, что каждому игроку известна последовательность моментов времени T, весь упорядоченный набор и информационный вектор a0 = (..., 0,... ) количественного состояния процесса в момент t0, поэтому каждый из игроков определит, кто делает ход в момент t1. Следовательно, каждому игроку еще до начала процесса может быть известен вектор a1 = (a1, A). Но тогда каждый игрок еще до начала процесса может знать, кто делает ход в момент t2 и вектор a2. Повторив наши рассуждения, если нужно, счетное число раз (скажем, по индукции) можно говорить, что каждый игрок еще до начала процесса может знать, кто из игроков делает ход в момент tk для любого k из N, если пренебречь временем, затрачиваемым на вычисление очередности. Реальнее же предположить, что все вычисления о возможности совершения хода в момент tk+1 игрок делает на отрезке времени (tk, tk+1).
Сделаем замечание о последовательности T = t1 < t2 < < tk < tk+1 <.... Мы сказали, что каждому игроку эта последовательность известна. Это упрощенная, идеализированная модель. Можно опять предположить, что всякий очередной момент принятия решений tk+1 сообщается игрокам неким ФнейтральнымФ игроком. Правда, при этом внешнее по отношению к процессу время 1, 2, 3,..., k, k + 1,... является равномерным и известным. В последнем случае внешнее время k считает ходы процесса (не ходы игрока!), где под ходом процесса в момент tk следует понимать совокупность всех ходов игроков, совершающих ход в момент tk. Если пуститься в философские рассуждения и рассмотреть принятие решений отдельным игроком в аспекте категорий свободы и необходимости, то можно считать подпоследовательность моментов времени, в которые этот игрок принимает решения, необходимостью, предопределенностью (если угодно, судьбой). Из предыдущих рассуждений следует, что эта подпоследовательность, вообще говоря, Фкому-тоФ известна (или точнее, вычислима). Свобода же игрока заключается в том, что, находясь в момент tk в точке y, он свободен на отрезке времени (tk, tk+1] выбирать любую точку z из множества достижимости D(y) и перемещаться в нее, если правилами процесса предусмотрен его ход.
Ранее мы отметили, что последовательность векторов a = (ar), характеризующих количественное состояние процесса в приведенной интерпретации, совпадает с максимальной l-последовательностью. Другими словами, можно констатировать, что очередность (очередь) совершения ходов игроками в приведенной интерпретации определяется максимальной l-последовательностью.
Зафиксируем теперь произвольную остовную l-последовательность a = (ar) и изменим приведенную ранее интерпретацию. При этом в новой интерпретации мы оставляем все неизменным за исключением очередности совершения ходов. Будем считать, что в момент tk+1 игрок совершает ход, если O(k + 1), где O очередь, соответствующая последовательности a. Напомним (см. определение 15), что O(k + 1) = {| A, ak+1 - ak = 1}.
Поскольку a = (ar) остовная последовательность, то и в данной интерпретации каждый игрок сделает все предписанные ему в процессе принятия решений ходы. При этом ни один игрок не будет ущемлен в получении информации, и в итоге реализуется та же траектория процесса, что и в случае максимальной l-последовательности, если игроки будут придерживаться тех же стратегий. Придерживаться тех же стратегий игроки смогут, поскольку состояние информации для каждого из них при очередном принятии решения то же самое, что и в случае максимальной l-последовательности. А значит, при использовании одинаковых стратегий, при разных допустимых очередях совершения ходов, игроки получат одни и те же выигрыши. Последнее более строго показано в главе 3.
Нетрудно заметить, что функции , A, из определения 2.1.1 опредеT лены с ФизбыткомФ. В общем случае не каждая точка из множества X A будет являться траекторией. Пусть, например, множество D(x0) не равно множеству X: не каждая точка множества X достижима для игрока из T точки x0. Пусть z X\D(x0). Тогда в множестве X присутствуют элементы вида (z,... ), в то время как ни одна траектория не пройдет через точку z. Для исследования всякой конкретной задачи с помощью предлагаемой модели функцию с множества действительных траекторий до множества XT всегда можно доопределить (например, нулем).
A Ранее мы отметили, что посредством своих ходов (управлений) игрок стремится максимизировать функцию (s), s = (s, A). Понятно, что случай минимизации функции (s) равносилен максимизации функции -(s). Если = = для любых элементов , из множества A, то мы находимся в условиях задачи бесконфликтного управления с множеством участников A. В этом случае игроки участвуют в оптимизации одной и той же функции (s), где s = (s, A) при довольно сложной информационной структуре процесса.
В гл. 1 мы определили динамику поступления информации игрокам для одновременных, поочередных процессов, для процессов с конечной информацией, с полной информацией, с полной памятью. Естественно, перечисленные типы динамики поступления информации не представляют собой полную классификацию, а являются лишь началом исследований в области моделирования поступления информации участникам процесса принятия решений.
О п р е д е л е н и е 16. Будем говорить, что развернутая форма игры = ((X, x, D, T, l, ), A) соответствует в информационном смысле процессу типа , если упорядоченный набор информационных функций l = (l, A) соответствует процессу типа .
Переменная из последнего определения может принимать следующие значения: одновременный, поочередный, с конечной информацией, с полной информацией, и т. д.
Далее в главе 2 определяются траектории игры и чистые стратегии игроков.
На этих структурах рассматриваются тихоновские топологии и показывается, когда эти топологии можно задать метриками, аналогичными метрике Бэра.
Доказываются теоремы о необходимых и достаточных условиях, когда в тихоновских топологиях топологические пространства траекторий и стратегий игры являются компактами. Для позиционных игр отображение, сопоставляющее ситуации в чистых стратегиях единственную порожденную ею траекторию, непрерывно. Для многошаговых игр с разделенными динамиками это не всегда так. В гл. 2 доказывается теорема о необходимых и достаточных условиях когда упомянутое выше отображение непрерывно для многошаговых игр с разделенными динамиками. Это условие связывает геометрические и информационные характеристики многошаговой игры. На базе упомянутой теоремы доказывается теорема о необходимых и достаточных условиях, когда в многошаговых играх с разделенными динамиками, с полной информацией, с не более чем счетным множеством игроков существует ситуация равновесия по Нэшу для произвольных непрерывных функций выигрыша игроков. Эта теорема развивает и обобщает известные теоремы Цермело-Неймана, ГейлаСтюарта. Для того же класса игр с полунепрерывными сверху функциями выигрыша игроков доказаны теоремы существования -равновесия в игре в чистых стратегиях и построены алгоритмы нахождения -равновесных чистых стратегий. Исследовано равновесие в бесконечношаговых антагонистических играх с разделенными динамиками, с полной информацией, с полунепрерывной функцией выигрыша. В частности для игр из данного класса доказана теорема о существовании значения игры и оптимальной стратегии у одного из игроков. На основе последней теоремы доказана теорема существования седловой точки в играх преследования с полной информацией в произвольном пространстве, когда выигрыш преследователя определяется поглощением преследуемого множеством достижимости преследователя. Для многошаговых антагонистических игр с полной информацией, с полунепрерывной функцией выигрыша получен и обоснован алгоритм построения -равновесных чистых стратегий.
В главе 3 для многошаговых игр с разделенными динамиками, с множеством игроков произвольной мощности вводится понятие измеримой стратегии поведения игрока, по ситуации в измеримых стратегиях поведения строится мера на множестве траекторий игры, исследуются свойства этой меры.
В частности для игр двух лиц определяется, когда интеграл по траекториям игры можно заменить повторным интегралом. При этом основным инструментом для построения меры является теорема И. Тулча о построении меры на произведении измеримых пространств по измеримым функциям перехода.
В главе 4 для многошаговых антагонистических игр с разделенными динамиками, произвольной продолжительности с переменными задержками информации у игроков, которые могут принимать отрицательные значения, вводится определение подыгры, стандартной подыгры. Для того же класса игр на основании полученных в главе 3 свойств меры на множестве траекторий игры определяются и обосновываются функциональные интегральные уравнения, связывающие значения подыгр соседних уровней. Эти уравнения развивают и обобщают известные уравнения Х.Э. Скарфа, Л.С. Шепли и уравнения Л.А.
Петросяна. Поскольку уравнения Х.Э. Скарфа, Л.С. Шепли определены для многошаговых антагонистических игр с конечными наперед заданными альтернативными множествами, с постоянными задержками информации у игроков при предположении непрерывности функции выигрыша. Уравнения, полученные в данной диссертации, определены и обоснованы без ограничения на функцию выигрыша. Уравнения Л.А. Петросяна получены для конечношаговых дифференциальных игр преследования с постоянной задержкой информации у преследователя с полной информацией у преследуемого.
Далее в главе 4 конкретизируется вид основных функциональных интегральных уравнений для случая, когда информационные функции l1, l2 конечны, альтернативные множества игроков конечны, функция выигрыша ограничена. Показано, что в этом случае в уравнениях операцию sup можно заменить на операцию max, операцию inf можно заменить на операцию min без какоголибо предположения о непрерывности функции выигрыша, что было сделано у Х.Э. Скарфа и Л.С. Шепли. Как уже было отмечено выше, достаточно, чтобы функция выигрыша была ограничена. Далее в этой же главе доказывается теорема о существовании -равновесия и оптимальной стратегии у максимизирующего игрока в классе смешанных стратегий в многошаговых антагонистических играх бесконечной продолжительности, с конечными альтернативными множествами, с переменными задержками информации у игроков, когда функция выигрыша ограничена снизу и полунепрерывна сверху в тихоновской топологии на множестве траекторий игры. При этом показано, что значение игры есть предел значений некоторых конечных подыгр, смешанная оптимальная стратегия максимизирующего игрока есть слабый предел расширений оптимальных стратегий некоторых конечных подыгр. Под смешанной стратегией в данном случае понимается любая вероятностная мера на множестве чистых стратегий. Далее делается замечание о том, что справедлива двойственная теорема, когда функция выигрыша полунепрерывна снизу и ограничена сверху.
В начале пятой главы на базе функциональных интегральных уравнений определяется и обосновывается метод решения многошаговых антагонистических игр с разделенными динамиками, произвольной продолжительности, с переменными задержками информации у игроков, которые могут принимать отрицательные значения. При этом сначала ищется оптимальная стратегия первого (максимизирующего) игрока. Для отыскания оптимальной стратегии второго (минимизирующего) игрока достаточно построить рассуждения двойственным образом. Далее в главе 5 рассматривается приложение построенного метода к играм с полной памятью. Приводится полная классификация функциональных интегральных уравнений для данного случая. Количество таких уравнений оказывается равным четырем.
В Заключении сформулированы основные результаты, полученные в диссертации.
1. Для описания информированности игрока в многошаговых играх с разделенными динамиками, с множеством игроков произвольной мощности, с различными (в том числе бесконечными) продолжительностями игры для разных игроков введена информационная вектор-функция игрока.
Произведен математический анализ упорядоченного по игрокам набора информационных вектор-функций с целью получения условия, когда каждый игрок получает причитающуюся ему информацию вовремя и полностью. Это условие названо информационной разрешимостью упорядоченного по игрокам набора информационных вектор-функций. Первоначально информационная разрешимость определена для игр с конечным множеством игроков.
2. Оказалось, что информационная разрешимость для игр с конечным множеством игроков в общем случае не работает для игр с не менее чем счетным множеством игроков. Для многошаговых игр с множеством игроков произвольной мощности получено другое условие информационной разрешимости. Доказано, что для игр с конечным множеством игроков эти два условия эквивалентны.
3. Дана частичная информационная классификация многошаговых игр с разделенными динамиками. В частности получены и доказаны теоремы о необходимых и достаточных условиях для упорядоченных по игрокам наборов информационных вектор-функций, определяющих одновременные игры, поочередные игры, игры с полной информацией. Приведено в отличие от Г. Куна не стратегическое, а информационной определение игр с полной памятью.
4. Приведена аксиоматика развернутой формы многошаговых игр с разделенными динамиками, с множеством игроков произвольной мощности, основой которой является условие информационной разрешимости упорядоченного по игрокам набора информационных вектор-функций.
5. Определены тихоновские топологии на множестве траекторий, чистых стратегий игры. Показано когда эти топологии можно задать метриками, аналогичными метрикам Бэра.
6. Для многошаговых игр с разделенными динамиками, с множеством игроков произвольной мощности доказана теорема о необходимых и достаточных условиях непрерывности отображения, сопоставляющего ситуации в чистых стратегиях единственную, порожденную ею траекторию. Тем самым установлена связь геометрических и информационных параметров игры.
7. Доказана теорема о необходимых и достаточных условиях существования равновесия по Нэшу в чистых стратегиях для бесконечношаговых игр с разделенными динамиками, с полной информацией, с не более чем счетным множеством игроков, для произвольных непрерывных функций выигрыша игроков.
8. Для многошаговых игр с разделенными динамиками, с полной информацией, с не более чем счетным множеством игроков, с полунепрерывными сверху функциями выигрыш доказаны теоремы существования равновесия в игре в чистых стратегиях и построены алгоритмы нахождения -равновесных чистых стратегий.
9. Доказана теорема существования седловой точки в играх преследования с полной информацией в произвольном пространстве, когда выигрыш преследователя определяется поглощением преследуемого множеством достижимости преследователя.
10. Для многошаговых игр с разделенными динамиками, с множеством игроков произвольной мощности введено понятие измеримой стратеги поведения игрока. По ситуации в измеримых стратегиях поведения построена мера на множестве траекторий игры, исследованы свойства этой меры.
11. Для многошаговых антагонистических игр, произвольной продолжительности, с разделенными динамиками, с переменными задержками информации у игроков получены и обоснованы функциональные интегральные уравнения, связывающие значения подыгр соседних уровней.
12. На базе функциональных интегральных уравнений получен и обоснован метод решения многошаговых антагонистических игр с разделенными динамиками, произвольной продолжительности, с переменными задержками информации у игроков.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Слобожанин Н. М. О мере на множестве партий в многошаговых играх // Вопросы механики и процессов управления. - Л.: ЛГУ, 1984. - Вып. 7. - С.87Ц93.
2. Слобожанин Н. М. Многошаговые игры с неполной информацией // Математические методы оптимизации и управления в сложных системах.
- Калинин: КГУ, 1984. - С.90Ц103.
3. Слобожанин Н. М. Существование ситуации равновесия при конечном времени игры // Дифференциальные игры с неполной информацией/ Л.А. Петросян, Г.В. Томский. - Иркутск: ИГУ, 1984. - Глава 3, параграф 3 - С.142Ц150.
4. Слобожанин Н. М. Одно необходимое и достаточное условие оптимальности стратегии убегающего // Дифференциальные игры с неполной информацией/ Л.А. Петросян, Г.В. Томский. - Иркутск: ИГУ, 1984.
- Глава 3, параграф 4 - С.150Ц162.
5. Слобожанин Н. М. О мере на множестве траекторий в динамических играх // Межвузовская конференция молодых ученых "Развитие фундаментальных и прикладных исследований"(II), 23.04.84-27.04.84. - Л.:
ГУ, 1984. - С.101Ц104.
6. Слобожанин Н. М. Многошаговые игры с задержкой информации // Записки науч. семинаров ЛОМИ. Проблемы теории вероятностных распределений. - Наука, 1985. - С.142Ц150.
7. Слобожанин Н. М. Об одной задаче геометрической вероятности // Межвузовская конференция молодых ученых "Развитие фундаментальных и прикладных исследований"(III), 2.04.85-5.04.85. - Л.: ЛГУ, 1985. - С.80Ц84.
8. Слобожанин Н. М. Один метод решения игр с задержкой информации // Дифференциальные, многошаговые, бескоалиционные и иерархические игры. - Калинин: КГУ, 1985. - C.140Ц154.
9. Слобожанин Н. М. Заметка к играм поиска // Дифференциальные, многошаговые, бескоалиционные и иерархические игры. - Калинин: КГУ, 1986. - C.160Ц168.
10. Слобожанин Н. М. Об одном свойстве многошаговых игр поиска // Межвузовская конференция молодых ученых "Развитие фундаментальных и прикладных исследований"(IV), 12.05.86-16.05.86. - Л.: ЛГУ, 1986.
- С.71Ц75.
11. Слобожанин Н. М. Решение одного класса многошаговых игр с полной информацией // Вестн. ЛГУ. Серия мат., мех., астрон. - Л., 1987. - Вып. 15. - 10 с. - Деп. в ВИНИТИ 27.10.1986, №7205-87 Деп.
12. Слобожанин Н. М. О рекурсивных стратегиях в играх с монотонной памятью // Межвузовская конференция молодых ученых "Развитие фундаментальных и прикладных исследований"(V), 20.04.87-24.04.87. - Л.: ЛГУ, 1987. - С.90Ц94.
13. Слобожанин Н. М. О рекурсивных стратегиях в многошаговых играх с полной памятью // Дифференциальные, многошаговые, бескоалиционные и иерархические игры. - Калинин: КГУ, 1987. - С.128Ц140.
14. Слобожанин Н. М. Формализация принципа оптимальности Беллмана // Межвузовская конференция молодых ученых МФТИ. Москва, 1989.
- С.100Ц104.
15. Слобожанин Н. М. ТеоретикоЦигровая модель диагностики экологических систем // Всесибирская конференция по математическим проблемам экологии, 23.06.92-25.06.92. - Новосибирск, Институт математики СО РАН, Тез. докладов, 1992. - С.70Ц71.
16. Слобожанин Н. М. О математической модели прогноза и управления экологическим процессом // Конференция "Теоретические и прикладные проблемы экологии 23.10.92-27.10.92. - Бухарский ГУ, 1992. - С.50Ц51.
17. Слобожанин Н. М. Об оптимизации дохода от работы сложной системы при наличии сбоев // Межвузовский сб. научных трудов "Управление экономическими системами в условиях формирования рыночных отношений. Вопросы теории и практики". - Иваново: ИГУ, 1992. - С.38 - 43.
18. Слобожанин Н. М. Об оптимальном управлении в динамических антагонистических процессах с переменной задержкой информации // Всероссийская конференция "Понтрягинские чтения-IV 3.05.93-8.05.93. - Воронеж, Тез. докладов, 1993. - С.80.
19. Слобожанин Н. М. О топологии на множестве траекторий в дискретных динамических управляемых процессах // Международный конгресс по компьютерным системам и прикладной математике, 19.07.93-23.07.93.
- СанктЦПетербург, Тез. докладов. - С.100.
20. Слобожанин Н. М. Динамические игры с дискретным временем с неполной информацией // Сб. научных трудов "Модели, алгоритмы, программы". - Тверь: ТГУ, 1993. - С. 80Ц87.
21. Слобожанин Н. М. Дискретные динамические управляемые процессы n лиц // Международная конференция по интервальным и алгебраическим вычислительным методам в науке и технике "Интервал - 94 7.03.9410.03.94. - СанктЦПетербург, Тез. докладов. - С.100Ц102.
22. Слобожанин Н. М. О свойствах меры на множестве траекторий в динамических процессах с запаздыванием информации // III Международная конференция "Многокритериальные задачи при неопределенности 5.09.949.09.94. - Орехово-Зуево, Тез. докладов. - С.70.
23. Слобожанин Н. М. The properties of control in pursuit games // Сб.
научных трудов "Game Theory and Applications-/ edited by L.A. Petrosjan and V.V. Mazalov. - New York, USA, Nova Science Publishers, 1996. - С.187 - 192.
24. Слобожанин Н. М. Управление в конфликтных дискретных процессах с запаздыванием информации // Вопросы механики и процессов управления. - СПб: СПБГУ, 1996. - Вып. 17. - С.189Ц195.
25. Слобожанин Н. М. The control in pursuit games // Международная научная конференция "Многокритериальные и игровые задачиФ, 8.09.9614.09.96. - Орехово-Зуево, Тез. докладов. - С.110.
26. Слобожанин Н. М. Управление в многошаговых играх. - СПб.:
СПбГУ, 1996.
27. Слобожанин Н. М. Управление в динамических играх с зависимыми движениями // Труды XXIX научной конференции УПроцессы управления и устойчивостьФ, ф-т ПМ-ПУ. - СПб.: СПбГУ, 1999. - С.591Ц606.
28. Слобожанин Н. М. Информационная состоятельность в динамических играх // Труды международного симпозиума по водородной энергетике и технологии HYPOTHESIS-III. Секция УЭкономика и моделирование высокотехнологичных социально-экономических процессовФ / под общ. ред.
О.А.Малафеева и А.И.Муравьева. - СПб: СПбГУЭФ, 1999. - С. 92Ц98.
29. Слобожанин Н. М. Управление в играх в развернутой форме // Труды XXXI научной конференции УПроцессы управления и устойчивостьФ, ф-т ПМ-ПУ СПбГУ. - СПб: СПбГУ, НИИ Химии, 2000. - С.472Ц481.
30. Слобожанин Н. М. On two definitions of informational consistency in games with separated dynamics // Abstracts of 11th IFAC International workshop Control Applications of Optimization. - 2000. - С.238Ц239.
31. Слобожанин Н. М. On information consistency in games with separated dynamics // A proceeding volume from the 11th IFAC Workshop/ edited by V. Zakharov. Volume 2. СПб: PERGAMON, 2000. - С.647Ц653.
32. Слобожанин Н. М. On information structure in games with separated dynamics // Тезисы докладов III Московской международной конференции по исследованию операций (ORM2001). - Москва: В - РАН, 2001. - С.108Ц109.
33. Слобожанин Н. М. О непрерывности отображения, связывающего стратегии и траектории в играх // Труды XXXIII научной конференции Процессы управления и устойчивость, ф-т ПМ-ПУ СПбГУ. - Санкт - Петербург: СПбГУ, НИИ Химии, 2002. - С.530Ц534.
34. Слобожанин Н. М. Информация и управление в динамических играх.
- СПб: СПбГУ, 2002.
35. Слобожанин Н. М. О функциональных уравнениях одной игры с переменной задержкой информации // Вестник С.-Петербургского университета. Серия 10, Прикладная математика, информатика, процессы управления. - СПб: СПбГУ, 2006. - Вып. 2. - С.75Ц90.
36. Слобожанин Н. М. Информационная разрешимость в многошаговых играх с конечным множеством игроков // Математическая теория игр и ее приложения. - Петрозаводск: редакционно-издательский отдел КарН - РАН, 2011. - Т. 3, вып. 2. - С. 81Ц101.
37. Слобожанин Н. М. Информационная разрешимость в многошаговых играх с множеством игроков произвольной мощности // Математическая теория игр и ее приложения. - Петрозаводск: редакционно-издательский отдел КарН - РАН, 2011. - Т. 3, вып. 4. - С.81Ц109.
38. Слобожанин Н. М. Теоремы существования для бесконечных позиционных игр // Некоторые вопросы вычислительной и прикладной математики. - Якутск: ЯГУ, 1977. - C.37Ц39. Слобожанин Н. М. О существовании ситуации равновесия в бесконечных позиционных играх n лиц // Вопросы механики и процессов управления. - Л.: ЛГУ, 1978. - Вып. 2. - С.213Ц240. Слобожанин Н. М. Обоснование одной гипотезы Л. А. Петросяна // Вестник Ленинградского Университета. - Л.: ЛГУ, 1981. - №13. - С.120 - 123.
41. Слобожанин Н. М. О функциональных уравнениях одного класса многошаговых игр // Вестн. ЛГУ. Серия мат., мех., астрон. - Л., 1981. - Вып. 19. - 14 с. - Деп. в ВИНИТИ 15.09.1981, №4455-81 Деп.
42. Слобожанин Н. М. О существовании ситуации равновесия в бесконечных позиционных играх с неполной информацией // Многошаговые, дифференциальные, бескоалиционные и кооперативные игры и их приложения. - Калинин: КГУ, 1982. - С.89Ц95.
43. Слобожанин Н. М. Измеримые стратегии поведения в многошаговых играх // Вестн. ЛГУ. Серия мат., мех., астрон. - Л., 1982. - Вып. 13. - 19 с. - Деп. в ВИНИТИ 24.03.1982, №1298-82 Деп.