Введение к работе
Актуальность темы. Теория многошаговых игр занимается изучением управления изменяющихся систем в условиях конфликта или неполноты информации. По этой причине на протяжении последних восьми десятилетий наблюдается большой интерес к созданию математических моделей, теории и методов решения многошаговых игр.
Основой построения математической модели конфликтного процесса является строгое адекватное действительности определение его информационной структуры. Первоначально в работах Джона фон Неймана, Г. Куна и др. для конечных многошаговых игр с зависимой динамикой (позиционных игр) информационная структура процесса моделировалась посредством разбиения пространства игры на информационные множества игроков. Это безусловно строгий подход, но обладает одним существенным недостатком - чрезмерной общностью подхода, что затрудняет построение методов нахождения оптимальных стратегий игроков. Основополагающей работой по информационному анализу позиционных игр является работа Г. Куна "Позиционные игры и проблема информации", в которой автор для конечных игр доказал теорему о необходимых и достаточных условиях равенства выигрыша игроков в смешанных стратегиях и соответствующих им стратегиях поведения. Это условие было названо Куном полной памятью для игроков. В дальнейшем эта теорема была обобщена Л.А. Петросяном для бесконечношаговых позиционных игр с конечным множеством альтернатив и нобелевским лауреатом Р. Дж. Ауманом для бесконечношаговых позиционных игр с множеством альтернатив произвольной мощности. Однако, отметим, что требование полной памяти довольно сильное требование (игрок в каждый момент времени должен помнить всё, что совершил и знал ранее). При более слабых ограничениях на память игрока в игре теоремы об эквивалентности некоторого подкласса смешанных стратегий всему классу смешанных стратегий были доказаны Н. Н. Воробьёвым.
Настоящая диссертация посвящена многошаговым играм с разделёнными динамиками игроков. Одной из первых задач данного класса игр является интересная проблема о корабле, маневрирующим так, чтобы минимизировать вероятность его поражения бомбардировщиком, летящим над ним, сформулированная Р. Айзексом из РЭНД-Корпорейшн и представленная им на конференции Американского общества по исследованию операций 16 мая 1953 г. Он же предсказал значение этой игры. В 1957 году независимо С. Карлином и
Л. Э. Дубинсом эта игра была решена для постоянной задержки информации у корабля равной двум и полной информации у бомбардировщика при конечных альтернативных множествах. Автором настоящей диссертации в 1981 г. доказана теорема о необходимых и достаточных условиях оптимальности стратегий поведения корабля для случая произвольной конечной задержки информации у корабля. Одной из первых фундаментальных работ в области многошаговых игр с разделёнными динамиками является работа Х. Э. Скарфа, Л. С. Шепли "Игры с неполной информацией". В ней авторы рассмотрели бес- конечношаговые антагонистические игры с постоянными положительными задержками информации у игроков, с конечными альтернативными множествами. При предположении непрерывности функции выигрыша были получены функциональные уравнения, связывающие значения подыгр соседних уровней. На основании этих уравнений был получен метод решения упомянутого выше класса многошаговых игр.
В 1969 году вышла работа Д. Блэкуэлла, в которой автор исследовал вопрос существования значения в играх с конечными альтернативными множествами, с нулевыми задержками информации, с функциями выигрыша, имеющим вид характеристических функций. В 1972 году были опубликованы работы М. Ор- кина об играх, рассмотренных Х. Э. Скарфом и Л. С. Шепли, в которых изучен вопрос о приближении значения игры значениями других игр, функции выигрыша которых сходятся сверху к функции выигрыша первоначальной игры.
Говоря об играх с неполной информацией, необходимо сказать о довольно развитой области теории игр с неполной информацией - дифференциальных играх с неполной информацией, которые могут быть сведены к играм с полной информацией, что в свою очередь позволяет использовать известный аппарат дифференциальных игр. В значительной степени этот класс игр был исследован Н.Н. Красовским и его учениками. Этому же вопросу посвящены работы Ф. Л. Черноусько и А. А. Меликяна. Представляют интерес работы М. С. Никольского, в которых приводятся достаточные условия для завершения преследования за конечное время при неполном знании преследователем фазового положения или динамики убегающего. Проблема вывода функциональных интегральных уравнений в дифференциальных играх преследования с постоянной задержкой информации у преследователя, несводимых к играм с полной информацией, нашла отражение в работах Л. А. Петросяна. Значение информации о функции цели противника в играх двух лиц, основы информационной теории иерархических систем, исследованы в работах Н. Н. Моисеева,
Ю. Б. Гермейера, А. Ф. Кононенко и его учеников. Анализ равновесия в различных классах стратегий в дифференциальных играх с полной информацией приведён в работах А. Ф. Кононенко, О. А. Малафеева, С. В. Чистякова. Прикладные аспекты теории многошаговых игр исследованы в работах А. А. Васина, В. В. Мазалова и других зарубежных и отечественных учёных.
В настоящей диссертации впервые информационная структура многошаговых игр с разделёнными динамиками моделируется посредством информационных вектор-функций игроков. Производится анализ таких функций. Последнее позволяет, в частности, для антагонистических игр с переменными задержками информации у игроков, произвольной продолжительности (как конечной, так и бесконечной), с динамиками, определяемыми произвольными функциями достижимости, получить функциональные интегральные уравнения, связывающие значения подыгр соседних уровней. На базе этих уравнений в диссертации строится метод решения многошаговых антагонистических игр с неполной информацией. Таким образом, на основании вышеизложенного можно утверждать, что в диссертации исследуется актуальные проблемы конфликтных процессов.
Цель работы заключается в построении математической модели развёрнутой формы многошаговых игр с разделёнными динамиками с множеством игроков произвольной мощности, основой которой является определение информационной структуры игры, а также методов и алгоритмов решения различных подклассов рассматриваемого класса игр.
Методы исследования. Доказательство основных результатов диссертации опираются на классические методы теории игр, функционального анализа и теории вероятностей.
Научная новизна. Впервые для описания информационности игрока в многошаговых играх с разделёнными динамиками вводится информационная вектор-функция. Впервые приведена аксиоматика развёрнутой формы многошаговых игр с разделёнными динамиками, основой которой является, введённое и исследованное в диссертации, условие информационной разрешимости упорядоченного по игрокам набора информационных вектор-функций.
На множествах траектории игры и чистых стратегий игроков вводятся топологии А. Н. Тихонова. Показано, когда данные топологии можно задать метриками, аналогичными метрике Бэра. В многошаговых играх с зависимыми динамиками отображение, сопоставляющее ситуации в чистых стратегиях единственную порождённую ею траекторию, непрерывно. В играх с разделёнными динамиками это не всегда так. Впервые получена и доказана теорема о необходимых и достаточных условиях, когда упомянутое отображение непрерывно для игр с разделёнными динамиками. Это условие связывает геометрические и информационные характеристики многошаговой игры.
На базе упомянутой выше теоремы для многошаговых игр с разделёнными динамиками с не более чем счётным множеством игроков, с полной информацией, произвольной продолжительности, с произвольными непрерывными функциями выигрыша доказана теорема о необходимых и достаточных условиях существования равновесия по Нэшу в чистых стратегиях, которая развивает и обобщает теоремы Цермело-Неймана и Гейла-Стюарта. Для того же класса игр для полунепрерывных сверху функций выигрыша доказаны теоремы существования є -равновесия в игре в чистых стратегиях и построены алгоритмы нахождения є - равновесных чистых стратегий. Доказана также теорема существования седловой точки в играх преследования с полной информацией в произвольном пространстве, когда выигрыш преследователя определяется поглощением преследуемого множеством достижимости преследователя.
Для многошаговых игр с разделёнными динамиками, с множеством игроков произвольной мощности впервые вводится понятие измеримой стратегии поведения, по ситуации в измеримых стратегиях поведения строится мера на множестве траекторий игры, исследуются свойства этой меры.
Впервые для многошаговых антагонистических игр с переменными задержками информации у игроков, которые могут принимать отрицательные значения, вводится определение подыгры. Впервые для того же класса игр на основании полученных в диссертации свойств меры на множестве траекторий игры вводятся и обосновываются функциональные интегральные уравнения, связывающие значения подыгр соседних уровней. Эти уравнения развивают и обобщают уравнения Х. Э. Скарфа, Л. С. Шепли, Л. А. Петросяна.
На базе функциональных интегральных уравнений впервые определяется и обосновывается метод решения многошаговых антагонистических игр с разделёнными динамиками, с переменными задержками информации у игроков.
Практическая ценность. Полученный в диссертации метод решения многошаговых антагонистических игр с переменной задержкой информации может быть положен в основу исследования игровых задач с неполной информацией, которые служат моделями развёртывающихся во времени процессов. В частности, его модно использовать при исследовании задач управления системами при частично известных возмущающих воздействиях, при решении задач планирования с заранее неопределёнными параметрами. Введённые в диссертации информационные вектор-функции и условие информационной разрешимости упорядоченного по игрокам набора информационных вектор-функций могут быть использованы для дальнейшего исследования информационных конфликтных процессов, в частности, для информационной классификации таких процессов, начало которой приведено в диссертации.
Положения, выносимые на защиту.
-
Математический анализ информационной структуры многошаговых игр с разделёнными динамиками и на базе этого аксиоматика развёрнутой формы многошаговых игр с разделёнными динамиками, основой которой является условие информационной разрешимости упорядоченного по игрокам набора информационных вектор-функций.
-
Необходимые и достаточные условия непрерывности отображения, сопоставляющего ситуации в чистых стратегиях единственную порождённую ею стратегию для многошаговых игр с разделёнными динамиками. Получение с помощью этого условия необходимых и достаточных условий существования равновесия по Нэшу, є - равновесия в многошаговых играх с полной информацией и седловой точки в играх преследования с полной информацией.
-
Построение меры на множестве траекторий многошаговой игры с разделёнными динамиками с множеством игроков произвольной мощности по измеримым стратегиям поведения. Исследование свойств этой меры.
-
Построение о обоснование функциональных интегральных уравнений, связывающих значения подыгр соседних уровней для многошаговых антагонистических игр с переменной задержкой информации.
-
На базе функциональных интегральных уравнений построение метода решения многошаговых антагонистических игр с разделёнными динамиками, с переменными задержками информации у игроков.
Апробация работы. Основные положения и результаты работы докладывались и обсуждались на международном конгрессе по компьютерным системам и прикладной математике (Санкт-Петербург, 1993 г.); международной конференции по интегральным и алгебраическим вычислительным методам в науке и технике "Интеграл - 94"(Санкт-Петербург, 1994 г.); международных научных конференциях "Многокритериальные и игровые задачи"(Орехово- Зуево, 1994, 1996 гг.); международном симпозиуме по водородной энергетике и технологии HYPOTHESIS-III, секция "Экономика и моделирование высокотехнологичных социально-экономических процессов"(Санкт-Петербург, 1999 г.); международной конференции Control Applications of Optimization (11th IFAC) (Санкт-Петербург, 2000 г.); межвузовской конференции молодых учёных (Москва, МФТИ, 1989 г.); всероссийской конференции "Понтрягинские чтения - IV"( Воронеж 1993 г. ); III Московской международной конференции по исследованию операций (ORM2001) ( Москва, 2001 г.), а также на городских научных семинарах по теории игр под руководством профессора Н. Н. Воробьева (ИСЭП, Ленинград, 1982-1984 гг.), городских научных семинарах по теории вероятности под руководством академика И. А. Ибрагимова ( ЛОМИ, Ленинград, 1984-1985 гг.); городских научных семинарах по теории игр под руководством Л. А. Петросяна ( факультет ПМ-ПУ СПбГУ, Санкт-Петербург, 1990-е- 2000-е гг.); научном семинаре по теории игр института математики и механики УрО РАН под руководством чл. корр. РАН А. Г. Ченцова ( Екатеринбург, 2003 г.), на научном семинаре по теории игр ВЦ РАН под руководством профессора А. Ф. Кононенко ( Москва, 2003 г.); на научном семинаре по теории игр МГУ кафедры исследования операций под руководством профессора А. А. Васина ( Москва, 2003 г.), а также на научных семинарах кафедры моделирования социально-экономических систем факультета прикладной математики - процессов управления Санкт-Петербургского государственного университета под руководством профессора О. А. Малафеева ( Санкт-Петербург, 1992-2011 гг. )
Публикации. Результаты диссертации опубликованы в 43 научных работах, в том числе - в одной монографии объёмом 308 страниц.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка литературы. Общий объём диссертации - 270 страниц. Список литературы включает 124 наименования.
