Информация и равновесие в многошаговых играх

• Автор: Слобожанин, Николай Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 2012
• Место защиты: Санкт-Петербург
• Количество страниц: 270 с.

СОДЕРЖАНИЕ
Введение

Глава 1. Информационная разрешимость

§ 1.1. Процессы с задержкой информации

§ 1.2. Процессы с неполной информацией

§ 1.3. Информационная разрешимость в общем случае

§ 1.4. Динамика принятия решений

Глава 2. Развернутая форма игры с разделенными динамиками

§2.1. Определение развернутой формы

§2.2. Траектории и чистые стратегии

§2.3. Равновесие по Нэшу в классе чистых стратегий в играх с
полной информацией
§2.4. Алгоритмы решения игр с полной информацией
Глава 3. Определение многошаговой антагонистической игры с задержкой информации
§3.1. Развернутая форма игры
§3.2. Мера на множестве траекторий, индуцируемая стратегиями
поведения
§3.3. Нормальная форма игры, подыгра. множества й'сДа:, п),
Зс(х.п)
Глава 4. Основное функциональное уравнение
§4.1. Вывод основного функционального уравнения
§4.2. Функциональное уравнение для игр с конечными альтернативными множествами
§4.3. Теорема существования ситуации г-равновесия и оптимальной стратегии у одного из игроков для дискретного случая
Глава 5. Метод решения многошаговых антагонистических

§5.1. Рекурсивная стратегия в общем случае
§5.2. Рекурсивная стратегия в играх с монотонной памятью
§5.3. Функциональные уравнения для игры с монотонной памятью
Заключение
Литература

ВВЕДЕНИЕ
Актуальность темы. Теория многошаговых игр занимается изучением управления изменяющихся систем в условиях конфликта или неполноты информации. По этой причине на протяжении последних восьми десятилетий наблюдается большой интерес к созданию математических моделей, теории и методов решения многошаговых игр.
Основой построения математической модели конфликтного процесса является строгое адекватное действительности определение его информационной структуры. Первоначально в работах Джона фон Неймана, Г. Куна и др. для конечных многошаговых игр с зависимой динамикой (позиционных игр) информационная структура процесса моделировалась посредством разбиения пространства игры на информационные множества игроков. Это безусловно строгий подход, но обладает одним существенным недостатком - чрезмерной общностью подхода, что затрудняет построение методов нахождения оптимальных стратегий игроков. Основополагающей работой по информационному анализу позиционных игр является работа Г. Куна [35], в которой автор для конечных игр доказал теорему о необходимых и достаточных условиях равенства выигрыша игроков в смешанных стратегиях и соответствующих им стратегиях поведения. Это условие было названо Куном полной памятью для игроков. В дальнейшем эта теорема была обобщена Л. А. Петросяном [54] для бесконечношаговых позиционных игр с конечным множеством альтернатив и нобелевским лауреатом Р. Дж. Ауманом [1] для бесконечношаговых позиционных игр с множеством альтернатив произвольной мощности. Однако, отметим, что требование полной памяти довольно сильное требование (трок в каждый момент времени должен помнить всё, что совершил и знал ранее). При более слабых ограничениях на память игрока в игре теоремы об эквивалентности некоторого подкласса смешанных стратегий всему классу смешанных стратегий были доказаны Н.Н. Воробьёвым [10, 12].
Настоящая диссертация посвящена многошаговым играм с разделёнными динамиками игроков. Одной из первых задач данного класса игр является интересная проблема о корабле, маневрирующим так, чтобы минимизировать вероятность его поражения бомбардировщиком, летящим над ним, сформулированная Р. Айзексом из РЭНД-Корпорейшн и представленная им на конференции Американского общества по исследованию операций 16 мая 1953 г. [120]. Он же предсказал значение этой игры. В 1957 году независимо С. Карли-
ном [20] и Л. Э. Дубинсом [16] эта игра была решена для постоянной задержки информации у корабля равной двум и полной информации у бомбардировщика при конечных альтернативных множествах. Автором настоящей диссертации в 1981 г. в [67| доказана теорема о необходимых и достаточных условиях оптимальности стратегий поведения корабля для случая произвольной конечной задержки информации у корабля. Одной из первых фундаментальных работ в области многошаговых игр с разделёнными динамиками является работа X. Э. Скарфа и Л. С. Шешш [63]. В ней авторы рассмотрели бесконечношаговые антагонистические игры с постоянными положительными задержками информации у игроков, с конечными альтернативными множествами. При предположении непрерывности функции выигрыша были получены функциональные уравнения, связывающие значения подыгр соседних уровней. На основании этих уравнений был получен метод решения упомянутого выше класса многошаговых игр.
В 1969 году вышла работа Д. Блэкуэлла [119], в которой автор исследо-ва/i вопрос существования значения в играх с конечными альтернативными множествами, с нулевыми задержками информации, с функциями выигрыша, имеющим вид характеристических функций. В 1972 году были опубликованы работы М. Оркина [121, 122] об играх, рассмотренных X. Э. Скарфом и Л. С. Шепли, в которых изучен вопрос о приближении значения игры значениями других игр, функциями выигрыша которых сходятся сверху к функции выигрыша первоначальной игры.
Говоря об играх с неполной информацией, необходимо сказать о довольно развитой области теории игр с неполной информацией дифференциальных играх с неполной информацией, которые могут быть сведены к играм с полной информацией, что в свою очередь позволяет использовать известный аппарат дифференциальных игр. В значительной степени этот класс игр был исследован H.H. Красовским и его учениками [29-34, 50, 51, 111-113]. Этому же вопросу посвящены работы Ф.Л. Черноусько [114] и A.A. Меликяна [115]. Представляют интерес работы М. С. Никольского [47, 48], в которых приводятся достаточные условия для завершения преследования за конечное время при неполном знании преследователем фазового положения или динамики убегающего. Проблема вывода функциональных интегральных уравнений в дифференциальных играх с постоянной задержкой информации у преследователя, несводимых к шрам с полной информацией, нашла отражение в работах Л. А. Петросяна [56, 58, 62]. Значение информации о функции цели

Действительно, а0 = (..., 0, ...). и с увеличением номера вектора на единицу каждая компонента увеличивается не более, чем на единицу. Однако в общем случае число к не является точной верхней границей вектора ак.
Утверждение 1.3.1. Всякий вектор из множества Т = ПаеД Та является ограниченным, тогда и только тогда, когда среди множеств Тп разве лишь конечное их число являются бесконечными, и остальные множества, по мощности ограничены единой целой константой.
Доказательство. Необходимости. Предположим противное и отметим, что Та есть множество целых чисел, лежащих в интервале [0, Та. Тогда, при условии нашего предположения для любого целого числа к из множества N найдется к+1 множеств Та, которым к принадлежит. Поэтому в Т присутствует вектор а, сужение которого равно а = (0,1,2,..., к....) (т. е. в сужении а в качестве компонент присутствуют все натуральные числа). Но такой вектор не ограничен. Противоречие. Необходимость доказана.
Достаточность. Поскольку среди множеств Та разве лишь конечное количество равно множеству У, то Т = Пг;С/) Та можно представить в виде
Т = у, х12х..Д. х Ц Тп,
«Є.4{1.2,
где N і = N. а элементы множеств Та, а Є А {1,2,... ,г}, ограничены единой константой с. Поэтому всякий вектор а = (..., а1, а2,..., аг,...) из Т ограничен константой с = тах(с, а1, а2,..., аг). Утверждение доказано.
О п р еде ление 1.3.10. Информационную функцию 1а :Та —► П7єл2Г"' будем называть тючечно-ограниченной, если для любого к < Та вектор (зпр(іа(А:)7), 7 Є А) ограничен.
Теорема 1.3.3. Если существует остовная I-последовательность, то всякая информационная функция 1а, являющаяся, компонентой набора I = (Ііз,(3 Є А), — точечно-ограничена.
Доказательство. Пусть а = а°,о},а2,... ,ак,... — остовная /-
последовательность. Тогда 1тц,_,+00 ак = Та для любого а из А. Зафиксируем некоторый элемент (3 из множества А и покажем точечную ограниченность информационной функции 1р. Для этого зафиксируем произвольное целое число к в интервале [О.Тд) и покажем ограниченность вектора (вир(//з(/с)„), а Є А).
Рассмотрим вектор ар из остовной /-последовательности а. Как отмечалось, сф ^ р для любого а из А, т. е. всякий вектор /-последовательности является