Многошаговые стохастические игровые задачи управления тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

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

Доманский Виктор Константинович

МНОГОШАГОВЫЕ СТОХАСТИЧЕСКИЕ ИГРОВЫЕ ЗАДАЧИ

УПРАВЛЕНИЯ

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Санкт-Петербург 2004

Работа выполнена в Санкт-Петербургском экономико-математическом институте Российской Академии Наук (СПбЭМИ РАН)

Официальные оппоненты: доктор физнко - математических наук

профессор Л. А. Петросян доктор физнко - математических наук Э. Л. Пресман доктор технических наук профессор А. А. Юшкевич

Ведущая организация: Московский государственный институт

электроники и математики (Технический университет)

Защита состоится 2004 года в /<3 часов на за-

седании диссертационного Совета Д 002.202.01 в Санкт-Петербургском отделении Математического института им. В.А. Стеклова Российской Академии Наук (191023. С.-Петербург, наб. р. Фонтанки, 27, ауд. 311.)

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского отделения Математического института им. В.А. Стеклова РАН.

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

■22 - мгкп

2004 года.

Ученый секретарь диссертационного совета доктор физ.-мат. наук

А. Ю. Зайцев

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

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

Многошаговый стохастический игровой процесс с дискретным временем представляет собой динамическую систему с пространством состояний 5, способную изменять свое состояние в моменты времени t = 0,1,2,... под воздействием как управлений, выбираемых игроками в эти моменты, так и случайных факторов. Управления выбираются на основании предусмотренной правилами игры информации о предшествующих состояниях и о выборах игроками управлений на предшествующих этапах игры. После того как выбор всеми игроками сделан, игроки получают соответствующие этой ситуации доходы, система переходит в следующее состояние, а игроки получают предусмотренную правилами игры информацию.

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

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

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

В повторяющихся многошаговых играх с неполной информацией по-

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

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

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

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

Значительный интерес представляет исследование класса игр, для которых значение усредненной игры с матрицей выигрышей линейно зависит от распределения р. В игре с линейным значением усредненной игры "в пределе" игрок 2 теряет столько же, сколько он мог бы потерять, изначально зная состояние s, и столько же, сколько он теряет, если оба игрока не знают состояние Для конкретной игры этого класса Мертенс и Замир [1976] показали, что нормальное распределение возникает в асимптотике значения игры. Однако, вероятностная природа

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

В третьей главе работы исследуются многошаговые стохастические модели распределения ресурсов (капиталов) несколькими конкурирующими агентами. Эти модели являются обобщениями многошаговой модели распределения ресурсов одним агентом, изученной в книге Дынкина и Юшкевича [1975].

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

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

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

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

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

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

Для игр с ненулевой суммой выигрыши игроков в ситуации равновесия, вообще говоря, не должны удовлетворять принципу динамического программирования. Однако, этому принципу должны удовлетворять устойчивые выигрыши игроков в "абсолютной", то есть устойчивой относительно подыгр ситуации равновесия.

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

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

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

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

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

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

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

Наиболее существенные результаты и их научная новизна.

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

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

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

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

Описано значение транспортной задачи с заданными матрицей цен и вектором потребления как функция вектора производства. Эта функция вогнута и кусочно-линейна. Показывается, что для матрицы цен общего

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

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

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

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

Теоретическая и практическая значимость. Результаты, полученные в диссертации представляют интерес для различных областей теории стохастических игр с неполной информацией и для вероятностной теории оптимального управления. Эти области включают: Статистический последовательный анализ - Игровые задачи остановки случайной последовательности; Стохастические задачи управления по неполным данным - Повторяющиеся игры с неполной информацией; Вероятностные задачи управления запасами - Стохастические игры распределения ресурсов.

Апробация работы. По материалам диссертации были сделаны доклады на семинарах Санкт-Петербургского отделения Математического Института им. В.А. Стеклова РАН, Санкт-Петербургского Экономико-Математического Института РАН, факультета Прикладной математики и процессов управления Санкт-Петербургского Государственного Университета, Центрального Экономико-Математического Института РАН (Москва), а также на семинарах Института Пуанкаре (Париж, Франция), Карлова Университета (Прага, Чехия) и Университета г. Ульм (Ульм, Гермапия). Результаты диссертации докладывались на международных конференциях в следующих городах: Стоуни-Брук (США) 1993 г., 1994 г., Берлин (Германия) 1994 г., Иерусалим (Израиль) 1995 г., Торонто

(Канада) 1995 г., Санкт-Петербург 1996 г, 2002 г., Уорвик (Великобритания) 1999 г., Петрозаводск 2000 г., Бильбао (Испания) 2000 г., Искиа (Италия) 2001 г., Бедлево (Польша) 2002 г.

Структура диссертации. Диссертация содержит введение и три главы. Общий объем работы составляет 262 страницы. Список литературы включает 90 наименований.

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

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

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

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

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

натуральных чисел. Вероятность перехода из состояния в состояние х +1 равна р(х), а с вероятной е п ь обрывается — перехо-

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

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

Чистыми стратегиями игроков для игр остановки являются обычные

марковские моменты для наблюдаемой цепи, а смешанными стратегиями поведения — рандомизированные марковские моменты. Стационарная стратегия задается функцией т : X -> [0,1], выражающей условную вероятность остановить цепь при попадании в состояние х. Показывается, что стационарная стратегия задает разбиение границы Мартина на "останавливающее" и "неостанавливающее" множества, указываются подходы к их построению. В частности, показано, что стратегия не останавливает цепь в том и только том случае, если потенциал функции г конечен.

В разделе 1.4 дается формальное описание рассматриваемых игровых задач остановки, стратегий и уравнений оптимальности. Значение vc{x) игры остановки как функция начального состояния цепи

должно удовлетворять уравнению оптимальности, выражающему принцип динамического программирования в игровой формулировке. Уравнение оптимальности имеет вид и(х) — (Ти)(х), где оператор Т определен на множестве функций и : X —> R соотношением (Ти)(х) = val[a,-j(x,ü)]. Здесь val[a,-j] - значение матричной игры с матрицей выигрышей [atJ], ay(x,u) = dij(x) при (ij) ф (22) и а<я(х,и) - Ezu = E[u(z2)|2i = г].

Пусть функция и - удовлетворяет уравнению оптимальности, д - гармоническая функция. Тогда функция и + д удовлетворяет уравнению оптимальности для игры с выигрышами а^ + д,с + д. Если д > 0, то функция удовлетворяет уравнению оптимальности для игры с выигрышами ац/д,с/д и с переходными вероятностями цепи, имеющими

вид (3(*))~VKyM2/)-

Показано, что, при некоторых ограничениях на рост выигрышей, если функция R является решением уравнения оптимальности, то R(x) равно значению vr{x) игры о с т а н о^^и с выигрышем на бесконечности, определяемом функцией R.

Поскольку значение ve{x) игры остановки должно являться неподвижной точкой оператора Г, представляется естественным использовать для нахождения значения игры последовательность итераций опе-

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

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

Мы предполагаем, что функции 012, 021 и с принадлежат классу L таких функций д на пространстве X, что Е^ир,, |<?(х„)| < оо, для всех хех.

Это предположение позволяет определить гармонические функции

42(Х) = Ег НтБир^оо 012(х„),

а2\(х) = БгИтт^ооаг^х,,),

а также соответствующие им функции на границе Мартина а^Ь) и а-7,Ш.

Пусть №+(х) — цена максимизационной задачи оптимальной остановки с текущим выигрышем п с "выигрышем на бесконечности" с+ = сЛа^, ^""(х) — цена минимизационной задачи с текущим выигрышем 021(2:) и с "выигрышем на бесконечности" с~ = с V а^. Теорема 1.4.1. Пусть функция оц £ Ь. Тогда значение ус(х) игры Гс(х) равно пределу невозрастающей последовательности Т"!^"1 (х), а также пределу неубывающей последовательности УИ^х). Следствие. В предположении, что все платежные функции принадлежат L, значение ус(х) игры Гс(х) зависит от значений с{Ь) "выигрыша на бесконечности" только в тех точках границы Мартина, для которых выполняются неравенства а^Ь) < с(Ь) < »^(Ь). При приближении траектории цепи к элементу границы Мартина, для которого эти неравенства не выполняются, оптимальные стратегии игроков останавливают цепь.

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

Получены оценки для значений игр остановки цепи Маркова со специальной структурой выигрышей. Предполагается, что выигрыши неотрицательны, п что выигрыш 012 = 0. Последнее условие мешает игроку 1 использовать чистые стратегии остановки и позволяет игроку 2 воздерживаться от остановки, рискуя только "выигрышем на бесконечности" с. Чтобы проиграть меньше, игрок 2 должен останавливать цепь с положительной вероятностью. Описаны решения для таких игр с использованием рандомизированных моментов остановки. Принимая во внимание, что если - гармоническая функция, то функция удовлетворяет

уравнению оптимальности для игры с выигрышами эти

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

Решение v уравнения оптимальности для таких игр удовлетворяет неравенствам 0 < v < Pv, т.е. значение vc игры Гс(х) является неотрицательной субгармонической функцией, удовлетворяющей условию vc{x) < с(х). Асимптотика значения такой игры определяется гармонической составляющей в разложении Рисса этой функции.

Мы начинаем с рассмотрения игр с платежами, удовлетворяющими условиям а21 = а12 = 0,ац,с > 0,Vx б X. Из Теоремы 1.4.1 следует, что, если функция ац 6 L, то при любой функции с значение игры vc = 0.

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

Из уравнения оптимальности следует, что ядро потенциала в разложении Рисса для субгармонической функции v удовлетворяет уравнению ттс(х) = Pve(x) - ve(x) = vc{x) - Pvc(x) • (au(x))_1.

Пусть В" С В — останавливающее подмножество границы Мартина для стационарной стратегии, определяемой функцией аа(у) = (ац(?/))-1Л - ее индикатор.

Теорема 1.5.1. Гармоническая составляющая в разложении Рисса для значения t'c(x) игры Гс(х) определяется граничными значениями hc(b) - с(Ь) • 1В°(Ь)-

Следствие 1. Значение vc(x) игры Гс(а:) зависит от значений с(Ь) только в точках границы Мартина, не принадлежащих подмножеству Ва. Оптимальная стратегия игрока 2 останавливает цепь при стремлении к точке границы ъева.

Конечность потенциала функции а^1 равносильна тому, что стационарная стратегия сга(у) не останавливает цепь.

Следствие 2. Пусть потенциал функции а^онечен при всех х € X. Тогда для любого "выигрыша на бесконечности" с гармоническая составляющая в разложении Риссадля значения-i'c(x) игры Гс(х) равна Последовательность не возрастает и сходится к

Пусть теперь ац > 0. Определим стратегию ае соотношениями ас(х) = 1, если ац(х) < с(х), <тс{х) = с(х) -au(x)_1, если a-¿\{x) < с(х) < «n(z), aÁx) = если a2i(x) > с(х).

Пусть — множество всех таких гармонических функций, что

стратегия останавливает цепь. Пусть — наименьшая нижняя грань множества С+(х). Гармоническая функция с+(х) удовлетворяет неравенствам 0 < с+(х) < оо.

Теорема 1.5.2. Гармоническая составляющая в разложении Рисса для субгармонической функции ьс равна сЛс1". Значение 1'с(х) игры Гс(х) равно пределу невозрастающей последовательности Т"(с Л с+)(х).

Во второй главе рассматриваются антагонистические повторяющиеся игры с неполной информацией у второго игрока. В таких играх Г„(р) игроки разыгрывают матричную игру п раз. Матрица выигрышей А4 выбирается случайным ходом из конечного множества матриц в соответствии с распределением р. Первый игрок знает матрицу выигрышей а второй знает лишь априорное распределение. После каждого шага оба игрока узнают ход противника. В конце игры игрок 2 платит игроку

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

Естественным объектом изучения оказывается функция значений, сопоставляющая каждому распределению значение шаговой игры. Последовательность 1>п(р) убывает по п. Фундаментальный результат теории таких повторяющихся игр (Луманн и Машлер [1967]) состоит в том, что 1ш1г?„(р) равен минимальной вогнутой мажоранте значения матричной игры с усредненной матрицей выигрышей Поэтому представляет интерес исследование игр, для которых значение усредненной игры линейно. Для таких игр "в пределе" игрок

2 теряет столько же, сколько он мог бы потерять, зная s, и столько же, сколько он теряет, если оба игрока s не знают. Это дает основание назвать такие игры "раскрывающимися в пределе" играми.

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

В разделе 2.3 исследуются "раскрывающиеся в пределе" игры, задаваемые двумя матрицами А} И А1 размера 2x2. Мы описываем все множество "раскрывающихся в пределе" игр этой размерности. Это множество распадается на два подкласса, которые мы называем играми "смешанного типа" и играми "чистого типа", в соответствии с характе-

ром решений для платежных матриц.

Класс игр "смешанного типа" в этой размерности с точностью до стратегической эквивалентности совпадает с классом игр с сепарабельными выигрышами. Платежные матрицы могут быть представлены в виде:

о//3[ -а'Ь -а/3| аД

А2 = А

-а%

где

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

Применяя Центральную Предельную Теорему к биномиальному распределению, мы получаем следующее утверждение.

Теорема 2.3.2. Для игры Г„(р) с коэффициенГомспра-

ведливо равенство

где р — р-квантиль стандартного нормального распределения.

Мы получаем решения также и для "раскрываемых в пределе" игр "чистого типа".

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

В разделе 4, переходя к более высоким размерностям, мы начинаем с исследования повторяющихся игр с симметричными сепарабельными выигрышами вида = ау-+С<5*, где — символ Кронекера. Мы предполагаем, что матрицы А — [ау] и А' имеют одну и ту же единственную вполне смешанную оптимальную стратегию

игрока 1, и что уа1Л = 0. Из этого следует, что значение игры для усредненной матрицы А(р) = ЛраА" равно скалярному произведению < р,х > векторов р их. Следовательно, для значения игры 1'„(р) справедливо равепство

Мы выражаем решения для этих игр в терминах мультиномиального распределения с параметрами и

Полученное представление решения для этих игр с помощью мультиномиального распределения позволяет использовать Центральную Предельную Теорему и описать предельное поведение остаточного члена ен(р) = г>п(р)~ < Х,р >.

Пусть Ф (у) — плотность (т — 1)-мерного центрированного нормального распределения с матрицейковариаций Е = +хт— (х!—xm}(xt —

х«)].

Каждой точке хг € мы сопоставляем разбиение

пространства Д™"1:

- (У ^ - Уг > Щ - Щ * = 1,- • • ,т - 1, у» > -ш,},

Фт(^) = {у е Ит-1]2/* < -Ю. 5 = 1,..., т - 1,}.

Для точки р 6 /«¿Д5 пусть мг(р) С В."1-1 — единственная точка, для которой разбиение порождает точку р:

Теорема 2.4.2. Для игр Г„(р)

то .

и™ ^/пс„(р) = £ Ф(УШ"-2 = иыр))

где дQs — граница области {йу)™'"* — элемент гиперплоскости.

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

Для мультиномиальной транспортной задачи Тп{р), соответствующей игре Г„(р), множество пунктов производства - множество Л' состояний игры, а множество пунктов потребления - мпожество целочислен-

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

Маргинальным распределением уровней производства является априорное распределение р, а маргинальным распределением уровней потребления является мультиномиальные распределение с параметром п. Затраты определяются скалярными произведениями векторов Ь* = (Ь*) и векторов z, соответствующих пунктам потребления. Таким образом, будучи линейной комбинацией нескольких транспортных задач, описанная мультиномиальная задача может рассматриваться как транспортная модель с несколькими товарами.

Мы раскрываем рекурсивную структуру решений для задачи Т„(р), которая оказывается аналогичной рекурсивной структуре решений рассматриваемых игр. Это позволяет свести решения игр Гп(р) к решению задач

Мы иллюстрируем наш подход, применяя его к игре, асимптотическое поведение решений которой исследовалось Мертенсом и Замиром [1976]. Мы вычисляем значение и оптимальные стратегии игроков для этой конечно повторяющейся игры, решая довольно простую транспортную задачу. В результате мы легко получаем решение, впервые найденное Хой-ером [1992].

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

В последнем разделе второй главы мы исследуем значение транспортной задачи та1(, Ь) как функцию уровней производства и потребления. Полагая суммарное производство и потребление равным единице, мы можем считать эти уровни - вероятностными векторами на множестве пунктов производства I и пунктов потребления 3 соответственно. Допустимые планы транспортной задачи = ||ху|| € А(/ X «/) вероятностные распределения на с заданными проекциями и

Фиксируя вектор Ь 6 А(./), мы исследуем значение транспортной задачи как функцию уаЦ(а) на симплексе Л(/). Вогнутая и кус очно-линейная функция характеризуется своими максимальными областями ли-

нейностп. Ее значения в этих областях определяются значениями в крайних точках областей, или в точках пиков. Функция уаЦ(а) имеет Ст+п_1 точек пиков, которые находятся во взаимнооднозначном соответствии с векторами из множества ш-мерных целочисленных неотрицательных векторов с суммой компонент, равной п. Точки пиков функции УаЦ(а) соответствуют решениям обобщенных задач о назначениях для матрицы . Обобщенной задачей о назначениях мы называем транспортную задачу, в которой а вектор - целочисленный вектор, принадлежащий 2™.

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

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

крайними точками. Объем задается соответствующим коэффи-

циентом мультиномиального распределения.

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

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

Глава 3 построена следующим образом:

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

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

= 1,2,... — марковская цепь с конечным или счетным прострап-

ством состояний S и с матрицей переходных вероятностей p(s, s'), где пространство состояний S может быть истолковано как множество возможных внешних случайных факторов, например, состояний природы, технологических нововведений и т.п.;

Ft(y,,s),i 6 I — набор производственных функций всех игроков; u,(z,s),i £ I — набор индивидуальных функций полезности всех игроков, где г = Zi,... ,гт — вектор ресурсов, направленных всеми игроками на потребление.

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

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

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

Доходы, получаемые игроками, однородны с показателем однородности ß. В частности, если ресурсы всех игроков, кроме игрока г, равны нулю, то получаемая им полезность равна a(s) ■

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

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

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

Рассматривая динамику социальных показателей, мы получаем многошаговую стохастическую модель распределения ресурсов для одного агента, "встроенную" в исходную игровую модель. Теорема 3.3.1. Для конечного интервала планирования игра Г(х,S,T) имеет единственную абсолютную ситуацию равновесия, для которой выигрыши игроков имеют вид vt(x,s,T) = u>r(s) • с{х) •

Здесь коэффициент it'i(s) = a(s), а последующие коэффициенты определяются рекуррентными соотношениями

Равновесные стратегии предписывают каждому игроку вкладывать в потребление на шаге t долю ресурсов, зависящую от числа оставшихся шагов Т — t и равную

Рассмотрение игр с бесконечным горизонтом планирования Г(ЗТ, s, оо) осмысленотолько в случае, если последовательность векторов w? ограничена, так как в противном случае выигрыши игроков в таких играх оказываются неограниченными.

Теорема 3.3.2. Пусть возрастающая последовательность Шт ограничена. Тогда игра Г(ЗТ, s, оо) имеет единственную абсолютную ситуацию равновесия. Выигрыши игроков имеют вид i\{x,s, сю) = tVoo(x,s) • хi, где вектор коэффициентов определяется соотношениями Щ» — limr-fooWr-

Стационарная оптимальная стратегия предписывает каждому игроку на каждом шаге вкладывать в потребление долю ресурсов, зависящую только от текущего состояния цепи s, равную

Ms))1/1-''.

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

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

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

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

Теорема 3.4.1. Для конечного интервала планирования игра Г(3 с несколькими отраслями потребления и производства имеет единственную абсолютную ситуацию равновесия. Выигрыши игроков в этой ситуации равновесия имеют вид м1{х,з,Т) ~ И'т[в)'с(?:)-Х{. Здесь коэффициент «^(в) — а последующие коэффициен-

ты определяются рекуррентными соотношениями

(*) = (ЕСМ*))1'1-" + (АЕ[Ь(з)]* Е р(*,з'^т-!^))1/1-*)1-*

Равновесные стратегии предписывают всем игрокам вкладывать в ую отрасль потребления на шаге < одну и ту же долю своих наличных ресурсов, зависящую только от текущего состояния s и числа оставшихся шагов Т — < и равную

Равновесные стратегии предписывают всем игрокам вкладывать в кую отрасль производства на шаге £ одну и ту же долю своих наличных ресурсов, зависящую только от текущего состояния s и числа оставшихся шагов и равную

]

»'ев

(ыг-жИ)1/1-"'

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

Стационарные равновесные стратегии предписывают всем игрокам вкладывать в j-ую отрасль потребления на каждом шаге одну и ту же долю своих наличных ресурсов, зависящую только от текущего состояния цепи s и равную

Эти стратегии предписывают всем игрокам вкладывать в k-ую отрасль производства на каждом шаге одну и ту же долю своих наличных ресурсов, зависящую только от текущего состояния s и равную

Работы автора по теме диссертации

1. Доманский В.К. "Существование и структура решений для одного класса антагонистических игр". Игровые вопросы принятия решений. Ротапринт ЦЭМИ АН СССР, М., с.32-46, 1973.

2. Доманский В.К. "Игры на обрывающихся процессах восстановления". Труды V зимней школы по мат. программированию и смежным вопросам. Вып.1, М., Изд. ЦЭМИ АН СССР, с.151-161, 1973.

3. Доманский В.К. "О некоторых играх, связанных с последователь- но-стью испытаний Бернулли". Техн. кибернетика, N4, с.35-39, 1974.

4. Доманский В.К. "Об одном классе игровых задач остановки последовательности сумм случайных величин". Современные направления теории игр, Вильнюс: Мокслас, с.86-93, 1976,

5. Доманский В.К. "Игровая задача остановки цепи Маркова". Резюме докладов, сделанных на заседаниях семинара по теор. вер. и мат. стат. в ЛОМИ АНСССР, 1977. Теор. вер. и ее примен. XXIII, 4, с.863-865, 1978.

6. Доманский В.К. "Игровая задача остановки цепи Маркова". Межвузовский тематический сб. Существование решений, устойчивость и информированность в теории игр. КГУ, Калинин, с.29-38, 1979.

7. Доманский В.К. "Стохастические игры". Математические вопросы кибернетики. Вып.1, М., 26-49, 1988.

8. Доманский В.К., "Рандомизированные оптимальные моменты для одного класса игр остановки". Теор. вер. и ее примен., ТВП, Москва, 2001, т.46, вып.4, с.770-778.

9. Доманский В.К., Дюбин Г.Н. "Игры на случайных процессах". Успехи теории игр, Вильнюс, 1973, с. 36-43.

10. Доманский В.К., Дюбин Г.Н., "Стратегии с неубывающим доходом в динамических моделях распределения ресурса между производством и потреблением", Оптимизация, АНСССР СО, Новосибирск, 1985, 35(52), с. 146-156.

11. Доманский В.К., Дюбин Г.Н., "Стохастическая модель распределения ресурса между производством и потреблением с несколькими участниками", Оптимизация, АНСССР СО, Новосибирск, 1985, 36(53), с. 63-68.

12. Доманский В.К., Крепс В. Л. "Функция значений транспортной задачи и мультиномиальное распределение". Экономика и математические методы, "Наука", Москва, 1998, т.34, вып.4, с. 119-133.

13. Doraansky V. "Dynamic stochastic games of resource allocation between production and consumption". International Game Theory Review, Vol.1, No 2, pp. 149-158, 1999.

14. Domansky V., "Randomized optimal stopping rules for a class of stopping games". Game Theory and Applications, vol.7. - Huntington (N.Y.), 2001, pp.33-43.

15. Domansky V., "Asymptotics of solutions for Dynkin stopping games" Proceedings of the Tenth Symposium on Dynamic Games and Applications, St.Petersburg, 2002, pp.244-251.

16. Domansky V., "Dynkin games with randomized optimal stopping rules". Annals of International Dynamic Games Society, Birkhauser, 2003, to appear.

17. Domansky V., Kreps V. ""Eventually revealing" repeated games with incomplete information". International Journal of Game Theory, v.23, pp.8999, 1994.

18. Domansky V., Kreps V. "Repeated Games and Multinomial

Distributions'". ZOR - Mathematishe Methods of Operations Research -42 pp.275-293, 1995.

19. Domansky V., Kieps V. "Repeated Games with Incomplete Information and IVansportation Problems". Mathematishe Methods of Operations Research 49, pp.263-289, 1999.

20. Domansky V., Kieps V. '"Social equilibria for competitive resource allocation models". Lecture Notes in Economics and Mathematical Systems, Springer-Wrlag. 2002. Vol. 510. pp.408-419.

Отпечатано в ООО «АкадемПринт». С-Пб. ул. Миллионная, 19 Тел.: 315-11-41. Подписано в печать 05.04.04 Тираж 100 экз.

04 - 1 53 98

Введение

1 Многошаговые стохастические игровые модели и последовательные интерактивные решения

2 Игровые задачи цепи Маркова

3 Повторяющиеся игры с неполной информацией

4 Стохастические игровые задачи распределения ресурсов.

Глава 1. Игровые задачи остановки цепи Маркова

1 Введение к главе

1.1 Постановка задачи.

1.2 Уравнения оптимальности.

1.3 Обзор предшествующих работ по игровой задаче остановки

1.4 Структура главы

2 Игры с "почти детерминированными" переходами

2.1 Модель и уравнения оптимальности

2.2 Решения для игр с нулевыми платежами «21(2:)

2.3 Решения для игр с положительными платежами ¿^(я)

2.4 Примеры.

3 Рандомизированные стратегии остановки

3.1 Супергармонические и субгармонические функции.

3.2 Выходная граница Мартина.

3.3 Рандомизированные стратегии остановки и марковские моменты

3.4 Задачи оптимальной остановки цепи Маркова.

4 Игры остановки с ограниченными ожиданиями максимумов платежей

4.1 Игры остановки и уравнения оптимальности

4.2 Решения уравнений оптимальности как решения игр остановки

4.3 Границы для решений уравнений оптимальности.

4.4 Построение решений для игр с ограниченными платежами

5 Игры с нулевыми платежами при остановке только одним игроком

5.1 Уравнения оптимальности и свойства их решений. Игры с нулевым значением.

5.2 Игры с пустым останавливающим множеством В~

5.3 Игры с непустым иеостанавливающим множеством В+

5.4 Иллюстративные примеры

6 Игры с нулевым платежом при остановке только первым игроком

6.1 Уравнения оптимальности и свойства их решений.

6.2 Игры с пустым иеостанавливающим множеством В+

6.3 Иллюстративный пример

Глава 2. Повторяющиеся игры с неполной информацией у второго игрока

1 Введение к главе

1.1 Постановка задачи.

1.2 "Раскрывающиеся в пределе" игры. Игра Мертенса и Замира

1.3 Игры с сепарабельными выигрышами.

1.4 Структура главы

2 Рекурсивное представление повторяющихся игр с неполной информацией у второго игрока

2.1 Формализированная модель.

2.2 Рекурсивное представление для стратегий и выигрышей

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

3 "Раскрывающиеся в пределе" игры с двумя 2x2 матрицами

3.1 Структура множества "раскрывающихся в пределе" игр

3.2 Некоторые формулы для биномиального распределения

3.3 Решения для игр "смешанного типа"

3.4 Вероятностная трактовка и асимптотика решений

3.5 Решения для игр типа "седловой точки"

4 Решения для симметричных сепарабельных игр

4.1 Свойства симметричных сепарабельных игр.

4.2 Некоторые формулы для мультиномиального распределения

4.3 Построение решений для симметричных сепарабельных игр

4.4 Предельное поведение решении.

5 Игры с общими сепарабельными выигрышами

5.1 Свойства игр с общими сепарабельными выигрышами

5.2 Мультиномиальные транспортные задачи

5.3 "Каноническое" разложение допустимых планов

5.4 Рекуррентные решения для мультиномиальных транспортных задач

5.5 Решения для игр Гп(р) сепарабельными выигрышами

5.6 Пример. Игра Мертенса и Замира.

6 Функции значений транспортной задачи и мультиномиальное распределение

6.1 Постановка задачи

6.2 Транспортная задача и задача двойственная к ней.

6.3 Структура носителей для матриц в общем положении

6.4 Функция значений для задачи Т(С, •,•).

6.5 Функция значений для задачи Т(С,-,Ь).

6.6 Иллюстративные примеры

Глава 3. Многошаговые стохастические игровые модели распределения ресурсов

1 Введение к главе

1.1 Постановка задачи

1.2 Структура главы и описание основных результатов.

1.3 Стохастические игры с дисконтированным выигрышем

1.4 "Абсолютные" ситуации равновесия стохастических игр

1.5 Игровая модель распределения ресурсов как стохастическая игра

1.6 Модели распределения ресурсов с несколькими отраслями потребления и производства

2 Решения для однородных моделей распределения ресурсов с одним агентом

2.1 Однородные модели распределения ресурсов с одним агентом

2.2 Решения для конечного интервала планирования

2.3 Решения для бесконечного интервала планирования

2.4 Многоотраслевые однородные модели. Решения для одношаговых моделей.

2.5 Решения для многоотраслевых многошаговых однородных моделей.

3 Игровые пропорционально-однородные модели распределения ресурсов

3.1 Формализация пропорционально-однородных моделей

3.2 Условия согласования индивидуальных и социальных полезностей.

3.3 Решения для вспомогательных одношаговых игр

3.4 Абсолютные равновесия для конечного горизонта

3.5 Абсолютные равновесия для бесконечного горизонта

4 Решения для игровых многоотраслевых пропорционально-однородных моделей распределения ресурсов

4.1 Формализация многоотраслевых пропорциональнооднородных моделей.

4.2 Решения для одношаговых игровых задач с несколькими отраслями потребления.

4.3 Решения одношаговой игровой задачи распределения с несколькими отраслями производства.

4.4 Решение для многошаговых многоотраслевых игровых моделей распределения ресурсов.

4.5 Решение для многошаговых многоотраслевых игровых моделей с бесконечным горизонтом планирования

1 Многошаговые стохастические игровые модели и последовательные интерактивные решения

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

Многошаговые стохастические игровые модели являются обобщениями управляемых марковских случайных процессов с дискретным временем, или по другой терминологии — многошаговых марковских процессов принятия решений (Multistage Markov Decison Processes — MMDP) (см., например, книги Дыикин, Юшкевич [20], Майн, О сак и [30]), на случай, когда в принятии решения участвуют несколько лиц с несовпадающими интересами.

Многошаговый стохастический игровой процесс с дискретным временем представляет собой динамическую систему с пространством состояний X, способную изменять свое состояние в моменты времени t = 0,1,2,. под воздействием как управлений, выбираемых игроками в эти моменты, так и случайных факторов. Управления выбираются на основании предусмотренной правилами игры информации о предшествующих состояниях и о выборах игроками управлений на предшествующих этапах игры. После того как выбор всеми игроками сделан, игроки получают соответствующие этой ситуации доходы, система переходит в следующее состояние, а игроки получают предусмотренную правилами игры информацию об этом состоянии и о действиях партнеров.

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

Известно, что "практически любая" динамическая игра, то есть игра, в которой процесс принятия решений игроками развернут во времени, может быть нормализована, то есть сведена к игре, и которой решения игроками принимаются однократно (см., например, Воробьев [4]). Однако, несмотря на свою концептуальную важность, такое сведение не всегда оказывается целесообразным, ибо оно затушевывает те специфические структурные свойства игры, которые могут облегчить ее анализ.

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

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

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

I])

Основным математическим инструментом для изучения принятия решений в условиях конкурентного взаимодействия (интерактивных решений) является теория игр.

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

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

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

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

Антагонистическая игра имеет значение v(x), при использовании игроками 1 и 2 стратегий tus из классов Т и S соответственно, если выполняются соотношения (теорема о минимаксе) sup inf I\x{t, s) = inf sup I\x(t, s) = v(x), y s s f где I\x(t,s) — выигрыш Игрока 1, соответствующий начальному состоянию цепи х.

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

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

Хорошо известным средством преодоления этого дефекта, используемым в теории игр, является введение рандомизированных стратегий. При этом возможны два различных подхода к построению рапдомизирован ных стратегий, а именно — смешанные стратегии, то есть вероятностные смеси чистых стратегий, и рандомизированные стратегии поведения, то есть стратегии, в которых рандомизация происходит на уровне элементарных пошаговых действий игроков. Известно, что, при достаточно широких условиях, оба эти подхода эквивалентны (см. Кун [64], Ауман М

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

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

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

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

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

Первая работа по теории стохастических игр (как и сам термин) принадлежит Шепли [83]. За пять десятилетий, прошедших со времени опубликования этой статьи, вопросам теории стохастических игр было посвящено несколько сотен работ (см. обзоры Партхасаратхи и Штерн [77], Мертенс, Сорен и Замир [77], а также обзор автора [13]).

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

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

Так, хорошо известный результат теории повторяющихся игр, ("folk theorem", см. [67]), утверждает, что все кооперативные индивидуально рациональные, то есть обеспечивающие всем участникам игры выигрыши, не меньшие, чем их максимальный гарантированный минимум, исходы одношаговой игры могут быть реализованы как результаты некооперативного поведения — ситуации равновесия в повторяющейся игре с бесконечным временным горизонтом.

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

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

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

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

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

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

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

В последние десятилетия теория игр переживает новый подъем, которым она обязана, в некоторой степени, своей трансформацией из чисто нормативной дисциплины, каковой она была на ранних этапах своего существования, в некую разновидность науки о поведении. Эта трансформация привела к существенному расширению области приложений теории игр, включив в нее такие предметы изучения, как эволюционная теория, теория обучения и интерактивная эпистемология. Все эти области существенно используют теорию многошаговых динамических игр (см. книги Бинмора [43], Аумана и Машлера [41], Мертенса, Сорена и Замира [67]).

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

2 Игровые задачи остановки цепи Маркова

В первой главе рассматривается игровая задача остановки цени Маркова в постановке, восходящей к работе Дынкина [19] и его последователей

Фрид [34], Кифер [26], Гусейн-Заде [6]). На Западе такие игры впервые рассмотрел Невё [73], который назвал их "играми Дынкина".

Два игрока наблюдают за цепыо Маркова и могут остановить ее в любой момент. Если оба игрока останавливают цепь одновременно, то игрок 1 выигрывает у игрока 2 сумму ац(ж), где х — состояние цепн в момент остановки. Если первым остановившим является только игрок 1 или только игрок 2, то игрок 1 выигрывает 012(1) или а21(х), соответственно.

На пространстве состояний цепи определена также функция с, задающая "выигрыш в бесконечности". Если ни один из игроков не останавливает цепь, то игрок 1 выигрывает сумму, равную ПгПп-юо с(хп). Функцию с(ж) можно считать гармонической функцией относительно переходного оператора Р цепи Маркова, то есть с(х) = Рс(х), что гарантирует существование предела.

Игровые задачи остановки являются обобщениями задач оптимальной остановки случайных процессов (см., например, книги Ширяева [36] и Роббипса, Сигмунда, Чао [33]) на случай, когда в принятии решения участвуют несколько лиц с несовпадающими интересами. Задачи оптимальной остановки представляют собой наиболее изученный раздел теории управления случайными процессами. Отличительной особенностью таких задач является наличие у игроков в каждый момент только двух возможных управлений (элементарных стратегий) — продолжить наблюдение за траекторией управляемого процесса, или прекратить его.

Значение игры остановки у(х), как функция начального состояния цепи хо = х, должно удовлетворять уравнению оптимальности, выражающему принцип динамического программирования Беллмана в игровой формулировке. Уравнение оптимальности имеет вид и(х) = (Ти)(х) = уа1[а,^(х,г«)], где уа1[а,у] — значение матричной игры с матрицей выигрышей [я^], ац(х,и) = а,;(ж) при (ц) ф (22) и «22(2,и) = (Р-и)(х) = Е[и(ж2)|^1 =

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

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

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

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

1. Веллман Р., Динамическое программирование. И.Л., М. 1960.

2. Блекуэл Д., Гиршик М.,.Теория игр и статистических решений. И.Л., М. 1958.

3. Вальд А., Статистические региающие функции, В сб.: Позиционные игры, М.: Наука, 1967, 300-522.

4. Воробьев H.H., Основы теории игр. Бескоалиционные игры. М.: Наука, 1984.

5. Гольштейн, Е.Г., Юдин Д.Б., Задачи линейного программирования транспортного типа. М.: Наука, 1969.

6. Гусейн-Заде С.М., Об одной игре, связанной с винеровским процессом, Теор. вер. и ее примен., 1969, XIV, 4, 732-735.

7. Доманский В. К., Существование и структура решений для одного класса антагонистических игр, Игровые вопросы принятия решений. Ротапринт ЦЭМИ АН СССР, М., 1973, 32-46.

8. Доманский В.К., Игры на обрывающихся процессах восстановления, Труды V зимней школы по мат. программированию и смежным вопросам. М., Изд. ЦЭМИ АН СССР, 1973, Вып.1, 151-161.

9. Доманский В.К., О некоторых играх, связанных с последовательностью испытаний Бернулли, Техн. кибернетика, 1974, N4, 35-39.

10. Доманский В.К., Об одном классе игровых задач остановки последовательности сумм случайных величин, Современные направления теории игр, Вильнюс: Мокслас, 1976, 86-93.

11. Доманский В.К., Игровая задача остановки цепи Маркова, Резюме докладов, сделанных на заседаниях семинара по теор. вер. и мат. стат. в ЛОМИ АНСССР, 1977. Теор. вер. и ее примен., 1978, XXIII, 4, 863-865.

12. Доманский В.К., Игровая задача остановки цепи Маркова, Межвузовский тематический сб. Существование решений, устойчивость и информированность в теории игр. К ГУ, Калинин, 1979, 29-38.

13. Доманский В.К., Стохастические игры, Математические вопросы кибернетики, М., 19S8, вып.1, 26-49.

14. Доманский В.К., Рандомизированные оптимальные моменты для одного класса игр остановки, Теор. вер. и ее примен., TBII, Москва, 2001, 46, вып.4, 770-778.

15. Доманский В.К., Дюбин Г.Н., Игры на случайных процессах, Успехи теории игр, Вильнюс: Минтис, 1973, 36-43.

16. Доманский В.К., Дюбин Г.Н., Стратегии с неубывающим доходом в динамических моделях распределения ресурса между производством и потреблением, Оптимизация, АНСССР СО, Новосибирск, 1985, 35(52), 146-156.

17. Доманский В.К., Дюбин Г.Н., Стохастическая модель распределения ресурса между производством и потреблением с несколькими участниками, Оптимизация, АНСССР СО, Новосибирск, 1985, 36(53), 63-68.

18. Доманский В.К., Крене В.Л. Функция значений транспортной задачи и мультиномиальное.распределение, Экономика и математические методы, М.: Наука, 1998, 34, вып.4, 119-133.

19. Дынкин Е.Б., Игровой вариант задачи об оптимальной остановке, ДАН СССР, 1969, 185, N1, 16-19.

20. Дынкин Е.Б.,Юшкевич A.A., Теоремы и задачи о процессах Маркова. М.: Паука, 1967.

21. Дынкин Е.Б.,Юшкевич A.A., Управляемые марковские процессы и их приложения. М.: Наука, 1975.

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

23. Карлин С., Основы теории случайных процессов. М.: Мир, 1971.

24. Кемени Дж., Снелл Дж., Конечные цепи Маркова. М.: Наука, 1970.

25. Кемени Дж., Снелл Дж., Кпепп А., Счетные цепи Маркова. М.: Наука, 19S7.

26. Кифер Ю Н., Игры с оптимальн-ой остановкой, Теория верояти. и ее примен., 1971, XVI, в.1, 183-188.

27. Лазриева Н.Л., О решениях уравнения Вальда-Беллмана, Литовский матем. сб., 1974, XIX, 2, 79-88.

28. Мазалов В.В., Игровые моменты остановки. Новосибирск. Наука, Сибирское отделение, 1987.

29. Мазалов В.В., Кочетов Э.А., Игры с оптилшльной остановкой случайных блужданий, Теория верояти. и ее примен. 1997, 42, в.4, 820-826.

30. Майн X., Осаки С., Марковские процессы принятия решений. М.: Наука, 1977

31. Петросян JI.А., Зенкевич Н.А., Семина Е.А., Теория игр. М.: Высшая школа, 1998.

32. Пресман Э.Л., Сонин И.М., Игровые задачи оптимальной остановки. Существование и единственность точек равновесия, Вероятн. проблемы управления в экономике, М.: Наука, 1977, 115-144.

33. Роббинс Г., Сигмуид Д., Чао И., Теория оптимальных правил остановки. М.: Наука, 1977.

34. Фрид Е.Б., Оптимальная остановка цепи Маркова двумя лицами с противоположными интересами, Теория вероятн. и ее примен., 1969, 14, в.4, с.746-749.

35. Хеннекен П., Тортра А., Теория вероятностей и некоторые ее приложения. М.: Наука, 1974. 472 с.

36. Ширяев А.II. Статистический последовательный анализ. М.: Наука, 1976, 272 с.

37. Элбакидзе Н.В., Построение цены и оптимальных политик в игровой задаче остановки льарковского процесса, Теория вероятн. и ее примен., 1976, 21, в.1, 164-169.

38. Alario-Lazaret, М., Lepeltier J.P., Marshal В., Dynkin Games, Stochastic Differential Systems (Bad Honnef), Lecture notes in Control and Information Sciences, Springer-Verlag, 1982, 43, 23-32.

39. Aumann, R.J., Mixed and behavioral strategies in infinite extensive games. in: Advances in Game Theory, Dresher M., Shapley L.S. and A.W.Tucker (eds), Annals of Mathematics Study 52 Princeton University Press, 1964.

40. Aumann,R.J., Maschler, M., Game Theoretic Aspects of Gradual Disarmament, Report of the US Arms Control and Disarmament Agency ST-80, Washington, D.C., 1966, V1-V55.

41. Aumann, R.J., Maschler, M.,Repeated Games with Incomplete Information The MIT Press Cambridge, Massachusetts London, England, 1995.

42. Beckmann, M.J; Resource allocation over time, in: Mathematical Models in Economics. Amsterdam-London-N.Y.-Warszawa, 1974, 171-178.

43. Binmore K., Essays on the foundation of game theory. Basil Blackwell, Southhanpton, 1990.

44. Bismuth J.M., Sur un problem de Dynkin, ZAVarsch. V. Geb. 1977, 39, 31-53.

45. Brock, W.A., L.J. Mirman, Optimal economic grouth and uncertainty: the discounted case, Journal of Economic Theory, 1972, 4, 3, 479-513.

46. Brock, W.A., L.J. Mirman, Optimal economic grouth and uncertainty: the no discounted case, International Economic Review, 1973, 14, 3, 560-573.

47. De Meyer, B., Repeated Games and Multidimensional Normal Distribution, CORE Discussion Paper 8932, 1989.

48. De Meyer, B., Repeated Games and Partial Differential Equations, Mathematics of Operations Research, 1995, 21, 209-235.

49. De Meyer, B., Repeated Games, Duality and the Central Limit Theorem, Mathematics of Operations Research, 1995, 21, 236-251.

50. Domansky V., Dynamic stochastic games of resource allocation between production and consumption, International Game Theory Review, 1999, 1, No 2, 149-158.

51. Domansky V., Randomized optimal stopping rules for a class of stopping games, Game Theory and Applications, Huntington (N.Y.), 2001, 7, 33-43.

52. Domansky V., Asymptotics of solutions for Dynkin stopping games, Proceedings of the Tenth Symposium on Dynamic Games and Applications, St.Petersburg, 2002, 244-251. .

53. Domansky V., Dynkin games with randomized optimal stopping rules, Annals of International Dynamic Games Society, Birkhauser, 2003.

54. Domansky V., Kreps V., "Eventually revealing" repeated games xvith incomplete information, International Journal of Game Theory, 1994, 23, 89-99.

55. Domansky V., Kreps V., Repeated Garnes and Multinomial Distributions, ZOR Mathematishe Methods of Operations Research, 1995, 42, 275-293.

56. Domansky V., Kreps V., Repeated Games with Incomplete Information and Transportation Problems, Mathematishe Methods of Operations Research, 1999, 49, 263-289.

57. Domansky V., Kreps V., Social equilibria for competitive resource allocation models, Lecture Notes in Economics and Mathematical Systems, SpringerVerlag, 2002, 510, 408-419.

58. Ferenstein E.Z., A variation of Dynkin's stopping game, Mathematica Japónica, 1993, 38, 2, 371-379.

59. Ferenstein E.Z., On some kind of Dynkin's stopping game, Demonstratio Mathematica, 2001, 34, 1, 191-197.

60. Gale, D., An optimal development in a multisector economy, Review of Economic Studies, 1967, 34, 1-18.

61. Harsanyi J.C., Selten R.A., General Theory of Equilibrium Selection in Games. The MIT Press, Cambridge, Massachusetts, London England, 1989.

62. Heuer, M,, Optimal Strategies for Uninformed Player, Internat. J. Game Theory, 1991,'*20, 33-51.

63. Irle A., Games of stopping with infinite horizon, ZOR Mathematical Methods of Operations Research, 1995, 42, 345-359.

64. Kuhn H.W., Extensive games and the problem of information, Contributions to the theory of games, Kuhn II.W., and A.W. Tucker (eds), Annals of Mathematics Study 28, Princeton University Press, 1953

65. Lepeltier. J.P., Maingueneau M.A., Le jeu de Dynkin en theorie generale sans l'hypothese de Mokobodski, Stochastics, 1984, 13, 25-44.

66. Lucas, R.E. Jr., N.L. Stokey, Optimal grouth with many consumers, Journal of Economic Theory, 1984, 32, 139-171.

67. Mertens, J.F., Sorin, S., Zamir, S., Repeated Games, CORE Discussion Paper, 9420, 1994.

68. Mertens, J.F., Zamir, S., The Normal Distribution and Repeated Games, Internat. J. Game Theory, 1976, 5, 1S7-197.

69. Mertens, J.F., Zamir, S., Incomplete Information Games and the Normal Distribution, CORE Discussion Paper, 9520, 1990.

70. Mirman, L.J., Uncertainty and optimal consumption decisions, Economet-rica, 1971, 39; 179-186.

71. Mirman, L.J., The steady state behavior of a class of one-sector grouth models with uncertain technology, Journal of Economic Theory, 1973, 5, 6.

72. Nash J., Non-cooperative games, Ann. Math., 1951, 54, 286-295.

73. Neveu J., Discrete-Parameter Martingales, North-Holland, Amsterdam, 1975.

74. Nowak A.S., Szajovvski K., Nonzero-zum stochastic games, Annals of International Society of Dynamic Games, 1999, 4 297-343.

75. Ohtsubo Y., On a nonzero-sum extension of Dynkin's stopping problem, Mathematics in Operation Research, 1987 12, 277-296.

76. Ohtsubo Y., On a discrete-time nonzero-sum Dynkin problem with monotonicity, J. Appl.Probab., 1991, 28, 466-472.

77. Parthasarathy T., Stern M., Markov games: A survey, A Chicago circle, Chicago: University of Illinois. 1976.

78. Phelps, E.S., The accumulation of risky capital: a sequential utility analysis, Econometrica, 1962', 30, 4, 729-743.

79. Ponssard J.-P., Sorin S., The LP Formulation of Finite Zero-Sum Games with Incomplete Information, Internat. J. Game Theory, 1980, 9, 99-105.

80. Ramsey, F., A mathematical theory of savings, Economic Journal, 1928, 38, 543-559.

81. Rosenberg D., Solan E. and Vieille V., Stopping games with randomized strategies, Preprint, Laboratoire d'Econometrie de l'ecole polytechnique, Paris, France, 2000.

82. Sakaguchi M., Sequential deception games, Math. Japonica, 1992, 37, N5, 813-826,

83. Shapley L.S., Stochastic games, Proc. Nat. Acad.Sci. USA, 1953, 39, 1095-1100.

84. Stettner L., On general zero-sum stochastic games with optimal stopping, Prob.and Math. Stat., 1982, 3, 103-112.

85. Stokey, N.L., R.E. Lucas, Jr., em Recursive methods in economic dynamics. Harvard University Press, 1989.

86. Yushkevich A.A., Optimal switching.problem for countable Markov chain: average reward criterion, Mathematishe Methods of Operations Research,2001, 53, 1-64.

87. Yushkevich A.A., Gordienko E.I., Average optimal switching of a Markov chain with a Dorel state space, Mathematishe Methods of Operations Research,2002, 55, 143-159.

88. Zamir, S., On the relation between finitely and infinitely repeated games with incomplete information, Internat. J. Game Theory, 1972, 1, 179-198.