автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Равновесные стратегии поведения в бесконечных повторяющихся биматричных играх

/ /

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

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

С^)_

005042536

Райгородская Анастасия Викторовна

РАВНОВЕСНЫЕ СТРАТЕГИИ ПОВЕДЕНИЯ В БЕСКОНЕЧНЫХ ПОВТОРЯЮЩИХСЯ БИМАТРИЧНЫХ ИГРАХ Специальность 05.13.18 -- математическое моделирование, численные методы и комплексы программ

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

1 С Літ?

Москва - 2012 ' ' 1

005042536

Работа выполнена на кафедре оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: академик РАН,

доктор физико-математических наук, профессор Кряжимский Аркадий Викторович.

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

профессор Васин Александр Алексеевич;

доктор физико-математических наук, профессор Мазалов Владимир Викторович.

Ведущая организация: Институ т математики и механики УрО РАН.

Защита диссертации состоится маА* 2012 г. в ч. мин.

на заседании диссертационного совета Д 501.001.43 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, МГУ, второй учебный корпус, факультет вычислительной математики и кибернетики, ауд. 685.

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан алрглЛ. 2012 г.

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

"7 Е. В. Захаров

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

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

Для управляемых повторяющихся биматричных игр произвольной раз-ерности с бесконечным числом раундов исследован вопрос о существовали равновесной по Нэшу пары поведенческих стратегий игроков. Приведен игоритм программы, разработанной автором для численного нахождения авновесной пары поведенческих стратегий. Подробно изучены управляемые овторяющиеся биматричные игры размерности 2x2- игра е-наилучших гветов и игры е-рандомизированного выбора «консерваторов» и «инновато-ов», в которых каждому игроку в каждом последующем раунде допускается азначать смешанную стратегию, предписывающую с большой, но, вообще эворя, отличной от 1, вероятностью выбор чистой стратегии, соответствую-;ей его типу поведения. Для этих классов управляемых повторяющихся игр ана классификация равновесных по Нэшу пар стратегий поведения и по-азана целесообразность рандомизации исходных детерминированных типов оведения для обоих игроков.

Актуальность темы

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

решений в моделях многошаговых и стохастических игр. Активно изуча мый ныне подкласс многошаговых игр составляют повторяющиеся биматри1 ные игры, выступающие в качестве моделей рациональных поведений вза] модействующих игроков с учетом их краткосрочных интересов. Общеприн; той моделью такого рода является повторяющаяся «Дилемма заключенной: (R.D.Luce и Н. Raiffa, R. Axelrod, М. Doebeli, B.N. Grofman, Т. Killingbac M. Nowak, J. Pool, A. Rapoport, К. Sigmund, S. Smale, Jl.A. Петросян, B.B. 3i харов и др.). Модель допускает многочисленные интерпретации с точки зр< ния биологии, экономики, политологии, социологии, психологии. Повторяв щаяся «Дилемма заключенного» организована таким образом, что при кая дом однократном взаимодействии рациональный выбор каждого из игроко: делаемый им в изоляции от партнера, ведет к тому, что каждый из них п< лучает меньший выигрыш, чем в случае, когда игроки совместно выбирак обоюдно оптимальное действие - кооперирование. Многократное повторен? взаимодействий, с учетом опыта, создает предпосылки для положительно1 разрешения дилеммы в долгосрочной перспективе - ДЛЯ «обучения» КООП1 рированию. Многие исследования посвящены анализу поведенческих схе? способствующих такому «обучению». В исследованиях этого рода доминир; ющая роль принадлежит численным экспериментам. К истокам численно1 экспериментирования относятся широко известные компьютерные турнир Аксельрода 1980-х годов1, осуществившие столкновение различных поведе! ческих схем с выявлением «чемпионов».

Теория повторяющихся (эволюционных) игр представляет собой ветвь о Г щей теории игр, восходящей к основополагающей работе Д. фон Неймана О.Моргенштерна (1944 г.)2 и концентрирующейся вокруг понятия игровог равновесия. Это центральное теоретико-игровое понятие, введенное в 1950 годы Дж. Нэшем 3 4, впоследствии обогатилось многочисленными вариа] тами. В развитии основ современной теории игр признан пионерский вкле отечественных ученых Ю.В. Гермейера и H.H. Воробьева.

Возникновение к началу 1970-х годов теории повторяющихся взаимоде] ствий связано с именем Р. Ауманна. Это направление исследований бьи сформировано в США под влиянием диалога специалистов по теории ш

'Axelrod R. The evolution of cooperation. New York: Basic Books, 1984.

'Нейман Дж., фон, Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

sNash J.F. Equilibrium points in n-person games // Proc. Nat. Acad. Sei. USA. 1950. V. 36. P. 48-49.

4Nash J.F. Noncooperative games // Annals of mathematics. 1951. V.54. P.286-295.

политиками по вопросам стратегии ядерного вооружения. Один из основах результатов, полученных в рамках этого направления (так называемая [ародная теорема»), говорит о том, что при повторяющихся взаимодействи-: игроки могут воздерживаться от действий, направленных на извлечение >аткосрочной выгоды. «Народная теорема» лежит в основе методов приня-[я решений для различных моделей повторяющихся взаимодействий. Теория повторяющихся (эволюционных) игр получила бурное развитие конца 1980-х годов благодаря новым моделям популяционной биологии С. Sigmund, J.Hofbauer, B.B. Захаров, JI.А. Петросян и др.) и экономики ). Friedman, S. Smale, М. Smith и др.). Модели этого рода предполагают, 1к правило, наличие фиксированных, содержательно обоснованных правил ¡аимодействия. Соответствующие теоретико-игровые исследования посвя-,ены, в основном, анализу долгосрочной динамики действий участников и их ¡имптотических свойств. Содержательная цель этих исследований состоит выявлении, на модельном уровне, долгосрочных качественных феноменов «отношений видов в биологических сообществах, распределений техноло-1й в сообществах фирм и т. д.), которые могут возникнуть в результате голкновения тех или иных локально рациональных правил повторяющегося заимодействия. В последние десятилетия в формирование теории повторяющихся (эволюционных) игр существенный вклад внесли работы таких уче-ых, как D. Friedman, D. Fudenberg, J. Hofbauer, Yu.M.Kaniovski, D.M. Kreps, I. Nowak, K. Sigmund, M. Smith, X. Tieman, G. Van der Laan, J. Weibull, '.P. Young, A.A. Васин, B.B. Захаров, А.Ф. Клейменов, A.B. Кряжимский, Э.С. Осипов, JI.A. Петросян и другие авторы.

Настоящая диссертация примыкает к работе A.B. Кряжимского и Ю.С. Основа5, где вводится в рассмотрение динамическая игра на классах эволюцион-ых игр, определяемых ограниченно рациональными поведенческими стра-егиями игроков, и описываются равновесные по Нэшу пары поведенческих гратегий. Диссертация направлена на разработку инструментария для под-ержки моделирования равновесных поведений в процессах многократно по-торяющихся взаимодействий недетерминированного характера. Численное юделирование таких процессов связано с существенными сложностями. Ода из них вызвана тем, что устойчивость результата моделирования прояв-

5А.В.Кряжимский, Ю.С.Осипов Об эволюционно-дифференциалъных играх jf Труды Математического нститута им. В.А.Стеклова. 1995. Т. 211. С. 257-287.

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

Сказанным выше определяется актуальность темы диссертации.

Цель работы

В проводимом в диссертации исследовании ставятся следующие цели:

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

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

• Для моделей бесконечных управляемых повторяющихся биматричны игр размерности 2x2, определяемых стохастически возмущенными ве риантами некоторых типовых стратегий поведения, исследовать вопрос существовании и структуре равновесных пар стратегий поведения. Сра! нить равновесные значения со средними выигрышами в детерминирс ванных повторяющихся играх, определяемых невозмущенными поведет ческими стратегиями.

Научная новизна работы

Основные результаты диссертации являются новыми и заключаются в слс дующем:

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

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

3. Создана программа СатеСакиЫог для исследования и симуляций обобщенной модели стохастической повторяющейся игры поведений. Программа реализована в среде МаЛаЬ и предназначена для исследовательских экспериментов и использования в учебном процессе.

4. Для общей бесконечной управляемой повторяющейся биматричной игры размерности 2 х 2, в предположении отсутствия в исходной статической игре равновесий в чистых стратегиях, построены и изучены модели игр поведений в классах стохастических расширений (а) детерминированных стратегий наилучшего ответа, (б) детерминированных стратегий поведения «консерваторов», (в) детерминированных стратегий поведения «ин-новаторов», (г) комбинаций последних двух типов стратегий поведения. Во всех случаях вычислены равновесные стратегии поведения. Показано, что равновесные выигрыши игроков превосходят их выигрыши в соответствующих детерминированных повторяющихся играх. В плане сравнения с конечношаговыми моделями изучена двухшаговая игра поведений в классах стохастических расширений детерминированных стратегий наилучшего ответа: дана классификация равновесий по Нэшу и проведено сопоставление равновесных значений выигрышей со средними выигрышами в детерминированной двухшаговой игре наилучших ответов.

Основные методы исследования

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

Теоретическая и практическая ценность работы

Результаты диссертации имеют теоретическое значение. В работе устано лены конструктивные условия, гарантирующие существование равновесий і Нэшу для моделей бесконечных управляемых повторяющихся биматричнь игр произвольной размерности. На основе исследования расширений нек торых стандартных типов поведений игроков для бесконечных управляемь повторяющихся биматричных игр размерности 2x2 выявлены условия, пр которых обеим взаимодействующим сторонам выгодно отклоняться от баз вых правил поведения. Теоретические результаты диссертации могут бьг использованы при анализе конкретных моделей игр поведений, а также д] отладки численных методов моделирования повторяющихся взаимодействи в частности, для идентификации временного шага, на котором начинает пр являться устойчивость значений ожидаемых средних выигрышей. Практич скую ценность представляют результаты диссертации, связанные с числе ным построением функций выигрышей и равновесий по Нэшу в бесконечн* управляемой повторяющейся биматричной игре произвольной размерност Соответствующий программный продукт, представленный в диссертации, м жет быть использован для численного исследования конкретных моделі многократных повторяющихся взаимодействий.

Апробация работы

Результаты диссертации докладывались на следующих научных семинар, и конференциях:

• Международной конференции по математической теории управления механике, 1-5 июля 2011 г., Суздаль, название доклада «К выбору равн весного поведения в бесконечной повторяющейся игре размерности 2x2

• Конференции «Дифференциальные уравнения и оптимальное управі ниє», посвященной 90-летию со дня рождения академика Евгения Фр ловича Мищенко, 16-17 апреля 2012 г., Москва, название доклада «Равк весные поведенческие стратегии в бесконечных повторяющихся играх)

б

• Международной конференции «Ломоносов-2011», секция «Вычислительная математика и кибернетика», 12-14 апреля 2011 г., Москва, название доклада «Бесконечная повторяющаяся игра е-наилучших ответов размерности 2 х 2»,

• Конференции «Тихоновские Чтения 2010», 26 октября 2010 г., Москва, название доклада «Повторяющаяся игра £-наилучших ответов размерности 2 х 2»,

• Научном семинаре отдела управляемых систем Института математики и механики УрО РАН, 22 марта 2012 г., Екатеринбург,

• Семинарах «Игровые задачи управления», «Управляемые процессы в условиях неопределенности» и «Методы оптимизации в функциональных пространствах» кафедры Оптимального управления факультета ВМК МГУ им. М.В. Ломоносова,

• Научном семинаре «Экономический рост: модели и прогнозирование», 11-17 октября 2010 г., Валуево, название доклада «Стохастическая двух-шаговая игра эпсилон-наилучших ответов размерности 2 х 2».

Публикации

Основные результаты диссертации опубликованы в статьях автора [1, 2, 3] и материалах конференций, все статьи опубликованы в изданиях, удовлетворяющих требованиям ВАК. Совместная работа [4] с научным руководителем A.B. Кряжимским принята в печать; в данной работе научному руководителю принадлежат постановка задачи, план исследования и редактирование рукописи.

Структура и объем диссертации

Диссертация состоит из введения, трех глав, заключения и списка литературы. Главы разбиты на разделы. Объем работы составляет 126 страницы текста, библиография включает 67 наименований.

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

Глава 1

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

шей А = (аг^)г=1,...,п;;'=1.....т И В = (Ьу)г=1,...,щ]=1,...,т СООТВеТСТВвННО ПврвОГ

и второго игроков6. Управляющими факторами выступают поведенчески стратегии игроков - смешанные стратегии, доставляющие игрокам некотс рые правила вероятностного выбора их чистых стратегий на каждом след} ющем раунде игры в зависимости от пары чистых стратегий, реализованно на текущем раунде.

Глава состоит из шести разделов.

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

Определение. Под стратегией поведения первого игрока понимаете

семейство Р = (Ру)»,»'=1.....П, j=l.....т Неотрицательных чисел такое, ЧТО Рц 1

... + Ру = 1 для любых г = 1,..., п, ] = 1,..., т.

Смысл величины ру - вероятность выбора первым игроком на следующе] раунде чистой стратегии г' в ответ на выбор игроками пары [г,]) чисты: стратегий на текущем раунде. Аналогично определяется стратегия поведени Я = (4).=1,...,«, л)'=1,..,т второго игрока.

Бесконечная повторяющаяся игра, соответствующая стратегиям поведени

Р = (ру )»,»'=1.....^=1.....т первого ид = (^)г=1,...,п, ¿¿'=1.....т ВТОрОГО ИГрОКО!

есть случайный процесс пересчета чистых стратегий игроков, реализуемый

раундах 0,1,____Процесс начинается в раунде 0 из положения (го,За)- Даль

нейшее течение процесса определяется следующим правилом: если в раунд] к первый и второй игроки реализуют свои стратегии и }к соответствен но, то в раунде к + 1 они реализуют свои чистые стратегии и jk+\ вероятностями и <7^ соответственно. В диссертации приведено такж

еВ соответствии со стандартом теории игр ац и Ъу есть значения выигрышей соответственно первого и второго игрок« при выборе первым игроком своей чистой стратегия» и вторым игроком своей чистой стратегии/.

ормальное определение обозначенного выше случайного (марковского) провеса. В соответствии с данной формализацией, множество всех траекторий = ((¿ь ji), {12,32), • ■ •) данного случайного процесса имеет структуру вероят-эстного пространства с некоторой вероятностью Р. Для каждой траектории = ((¿ъ ji), (¿2, ji), ■ ■ •) и каждого I — 1,2,... введем значения средних вы-грышей игроков, реализуемых на первых I раундах повторяющейся игры з,оль данной траектории:

1 1 1 1

ai{t) = aikdk, bt(t) = у Y^ (!)

k=1 fc=1

»ункции t H> ai(t) и t н> b;(i) (Z = 1,2,...) есть случайные величины на ве-оятностном пространстве всех траекторий. Математические ожидания слу-айных величин (1), т.е. значения

J[ = jai(t)P(dt), 4 = Jbi(t)P{dt), (2)

х1 X'

азовем ожидаемыми средними выигрышами первого и второго игроков в I аундах бесконечной повторяющейся игры, соответствующей парe(p,q) стра-егий поведения.

?еорема 1. Существуют пределы ожидаемых средних выигрышей (2):

= lim J[, J2°° = lim Jl2.

1 i-*oo 1 1 ¡-+00

Доказательство теоремы 1 опирается на известный результат из теории лучайных процессов, утверждающий, что для любого марковского процесса конченым числом состояний существует предел по Чезаро степеней его пе->еходной матрицы. Заметим, что значения, указанные в теореме 1, зависят от ¡ыбранной пары (p,q) стратегий поведения: Jf° = Ji°(p,q), J™ =

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

Зафиксируем непустое множество Si стратегий поведения первого игрока и непустое множество ¿>2 стратегий поведения второго игрока. Данная пара множеств и определенная на их произведении пара функций (р, q) И-

(р, я) ¿2°(р, <7) задают игру, которую называем игрой поведени (с множествами 5х, 5г стратегий поведения).

Определение. Пару (р°, д°) £ 51 х 5г называем равновесной (по Нэшу парой стратегий поведения, если для любых р € 51 и д 6 5г выполняютс неравенства д°) > я0) и д°) > 72°°(р0, <?).

Легко видеть, ЧТО ДЛЯ любых стратегий поведения;/1) = (р\Уг )«,,'=1 ,..„п, ¿=1 р(2) — (Ру^* )«,»'=1,...,п, j=l,■■■,m первого игрока и любых Ау € [0,1] (г = 1,..., тг, . 1, . . . , т) семейство Р = (ру)м'=1,...,п, .7=1.....т> ГДе

4 = + (1 - (»,»' = 1,...,п, ] = 1,...,т), (3

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

Определение. Будем говорить, ЧТО множество 51 усиленно выпукло, ее ли для любых его элементов р^ и любых Ау 6 [0,1} (г = 1,... ,п, j = 1,... ,т) стратегия поведения р первого игрока, определенная по (3), содер жится в 51.

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

Определение. Стратегию поведения р — (ру)м'=1,-,п, .7=1,....т первого иг рока будем называть строго рандомизированной, если рг^ > 0 для все: г, г' = 1,... ,тг, з = 1,... ,т.

Определение. Множество 51 стратегий поведения первого игрока назь ваем строго рандомизированным, если все его элементы строго рандомиз^ рованы.

Аналогично вводятся определения усиленной выпуклости и строгой ра! домизированности множества 5г стратегий поведения второго игрока.

Теорема 2. Пусть множества 51 стратегий поведения первого игрока и 5 стратегий поведения второго игрока строго рандомизированы, замкнуть и усиленно выпуклы. Тогда в игре поведений с множествами 51 и 5г дощ стимых стратегий поведения игроков существует равновесная пара стр( тегий поведения.

^Замкнутость множеств 51 и понимается в смысле евклидовых пространств (Япт)п и (ЛТ1т)Тп, в которые эти мн жества естественным образом вкладываются.

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

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

Ставится вопрос о расширении множеств 51 и 52, при котором в игре пове-эний обеспечивается существование равновесной пары стратегий поведения, ассматривается два типа расширений. Первый тип, введенный в разделе 1.3, зязан с понятием усиленных выпуклых оболочек множеств 51 и ¿2, анало-лчным известному в выпуклом анализе понятию выпуклых оболочек.

Определение. Пару (5Ь 52), где 51 и 52 - множества стратегий поведения эответственно первого и второго игроков, назовем корректным расширени-м пары (51,52), если 5х С 5Ь 52 С 52 и в игре поведений с множествами 1 и 52 стратегий поведения соответственно первого и второго игроков суще-гвует равновесная пара стратегий поведения.

Определение. Усиленно выпуклой оболочкой множества 5Х (соответствен-о множества 52) назовем множество со(5х) (соответственно со(52)), опреде-яемое, как пересечение всех усиленно выпуклых множеств стратегий пове-ения первого игрока, содержащих 51 (соответственно множества 52).

На вопрос о построении корректного расширения пары (51,52) отвечает ледующая теорема.

?еорема 3. Пусть множества 5х и 52 замкнуты и строго рандомизиро-аны. Тогда пара (со(51),со(52)) стратегий поведения есть корректное расширение пары (51,52).

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

Определение. Смешанной стратегией поведения первого игрока (с носителем 5х) назовем всякую борелевскую вероятностную меру на £1; аналогично, смешанной стратегией поведения второго игрока (с носителем 52)

назовем всякую борелевскую вероятностную меру на

Множества всех смешанных стратегий поведения первого и второго игроков обозначим, соответственно, гшх^) и гшх^г).

Содержательная интерпретация применения первым игроком выбранной им смешанной стратегии поведения /л € ггих^) такова. До начала повторяющейся игры первый игрок, руководствуясь вероятностной мерой /х, делает случайное испытание по выбору своей стратегии поведения р € 5ь Затем, руководствуясь стратегией поведения р, первый игрок на каждом раунде повторяющейся игры выбирает свою чистую стратегию. Содержательная интерпретация применения вторым игроком выбранной им смешанной стратегии поведения аналогична.

Ожидаемые выигрыши первого и второго игроков в бесконечной повторяющейся игре при смешанных стратегиях поведения^ £ пих^х) и и € пнх^г) определим, соответственно, как

Теорема 4. Пусть множества 5х и 5г замкнуты и строго рандомизирова-ны. Тогда существует равновесная пара смешанных стратегий поведения.

В разделе 1.5 предполагаем, что множества ¿1, ¿>2 стратегий поведения соответственно первого и второго игроков есть произвольные борелевские подмножества пространств (Дпт)", (Я"т)т соответственно, т.е. они не обязательно являются замкнутыми и строго рандомизироваными.

При сделанных предположениях функции (р,я) и (р,д) >->■

°{р, <?) ожидаемых выигрышей игроков, вообще говоря, разрывны (соответствующий пример приведен в главе 3, см. ниже комментарий к таблице 1), поэтому в классах гшх^х) и т1х(5г) максимумы, соответственно, функций ¡1 ь* и) и V ь-> ^(ц, и), могут, вообще говоря, не достигаться. Это ста-

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

лжений классов гшх^х), пих^г). Соответствующие суженные классы сме-:анных стратегий поведения назовем допустимыми.

Определение. Допустимой шешанной стратегией поведения первого грока будем называть всякую вероятностную меру /х е гшх(51) такую, что пя каждого борелевского множества Е С выполняется

Г к

(4)

;есь ... - попарно различные элементы из а\,..., а^ - неотри-мельные числа, д - неотрицательная интегрируемая по Борелю функция

Г 11

КЗ1) = / д{р)<1р+ ^2ак = 1

Х^(Щр^) равно 1 при € В и равно 0 в противном случае. Аналогично вводится определение допустимой смешанной стратегии пове-зния второго игрока:

и(Е) = [ %)ф + £ ЬкХ{2)(Е\дЮ). (5)

•*Е к=1

Определение. Ожидаемый выигрыш первого игрока, соответствующий эпустимым смешанным стратегиям поведения /х (4) первого игрока и V (5) горого игрока определим, как математическое ожидание функции на эрелевском вероятностном пространстве с мерой [1:

* ¿>1 о $2

¡1 ь

.нелогично определим ожидаемый выигрыш и) второго игрока.

Зададим непустое множество М допустимых смешанных стратегий пове-ения (1 первого игрока вида (4) со следующими свойствами:

(1) М выпукло в том смысле, что если /XI = (дх, а(-п\..., а^) 6 М, ¿¿2 = (52, а<21\..., а<21>>) € М, то ц = (Ай + (1 - А)д2, Аа<и> + (1 - А)а(21>,...,

Аа(1(г) + (1 _ \)аШ) е М;

(И) множество М ограничено в том смысле, что при некотором К > О для всех д е М вида (4) /Лнорма функции д не превосходит К,

(111) множество М замкнуто в х Я}1, где £2 - банахово пространство всех суммируемых с квадратом евклидовой нормы скалярных функций на 5Ь снабженное слабой нормой; точнее, если // = {дк,а(к1\... ,0^) е М (к = 1,2,...), 9к 9 слабо в Ь1, (аС*1),..., а^>) (а«,..., в В}\ то д = .. € М.

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

Теорема 5. В классах М и IV смешанных стратегий поведения существует равновесие по Нзшу.

Раздел 1.6 посвящен описанию алгоритма разработанной в среде Ма1;Ьа1 программы ОатеСа1иЫог. Программа разработана для исследования обоб щенной модели стохастической повторяющейся игры поведений и представ ляет собой алгоритм численного построения функций выигрышей и прибли женного нахождения равновесия по Нэшу.

Перед началом работы программы подаются следующие входные данные:

• Матрицы выигрышей А = и В = (Ьу);=1,...,пу=1,...,т соответственно первого и второго игроков.

• Множество стратегий поведения первого игрока и множество 5г стратегий поведения второго игрока задаются границами интервалов, в коте рых могут изменяться значения стратегий поведенияр = (р^)м'=з=\ и <7 = (д|7-)г=1,...,п, з,}'=!,.,.,т первого и второго игроков. Для выполнены: условия усиленной выпуклости, для каждой пары (г,]), г = 1,... ,п, ] = 1,...,т задаются независимые интервалы, которые никак не связан! между собой.

• Число Т > О, которое задает количество узлов сетки разбиений интерве лов.

• Значение 6 > 0, задающее точность вычислений.

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

Георема 6. При Т оо и 3 —О численная пара (рщД^) оптимальных тратегий поведения сходится к паре стратегий поведения (р°, где (р°, - одна из равновесных (по Нэшу) пар стратегий поведения в бесконечной ювторяющейся игре с матрицами выигрышей А = (ау ^ т и В =

Ьу)«'=1,...,п,7=1,...,т и множествами 51 стратегий поведения первого игрока и % стратегий поведения второго игрока.

Глава 2

Главы 2 и 3 посвящены рассмотрению повторяющихся биматричных игр 1азмерности 2 х 2 с матрицами выигрышей А = (аг;))^=1,2 и В = 1,2 со-

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

&12 > ¿>11, £>21 > £>22, Он > а21, а22 > а12. (6)

Далее предполагаем, что неравенства (6) имеют место. Эти неравенства ;ля каждого игрока определяют его чистую стратегию наилучшего ответа :а всякую чистую стратегию партнера. В данной модели смешанная стра-егия игрока отождествляется с числом из отрезка [0,1], задающим вероят-юсть выбора этим игроком своей чистой стратегии 1, вероятность выбора им [истой стратегии 2 при этом определяется автоматически.

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

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

Определение. Функцией е-наилучшего ответа первого игрока назовем любую пару (а1,а2) смешанных стратегий первого игрока такую, что

1 > с*1 > 1 - е, 0 < а2 < е.

Данное определение подразумевает, что первый игрок, в ответ на реализа цию вторым игроком, на текущем раунде, чистой стратегии], выбирает - для реализации на следующем раунде - смешанную стратегию о^-, при этом, ввиду (6), он придает большую вероятность своей чистой стратегии наилучшеп ответа на реализованную чистую стратегию ] второго игрока. Аналогичное определение принимается в отношении второго игрока.

Определение. Функцией е-наилучшего ответа второго игрока назовем любую пару /32) смешанных стратегий второго игрока такую, что

О < А < е, 1 > & > 1 - е.

Определение. Каждую пару

5=((аьа2),(/31,/32)), (7)

где (аь а2) - функция е-наилучшего ответа первого игрока и (А, 02) - функ ция е-наилучшего ответа второго игрока, будем называть парой функций е наилучших ответов игроков.

Для произвольной пары 5 (7) функций е-наилучших ответов игроков рас смотрим случайный процесс,представляющий бесконечную повторяющуюс игру е-наилучших ответов, соответствующую 5". Процесс состоит из рауг дов 0,1,2,..., в каждом из которых игроки разыгрывают описанную в начат: данной главы биматричную игру. Процесс развивается по следующей схем-В раунде 0 реализуется начальная пара (¿о, ¿о) чистых стратегий игроков. Ее ли в раунде к реализуется пара {ък,3к) чистых стратегий игроков, то первы игрок для выбора своей чистой стратегии в раунде к + 1 производит стг тистический эксперимент на множестве своих чистых стратегий, примен?

вешанную стратегию аналогично, второй игрок для выбора своей читай стратегии в раунде к+1 производит статистический эксперимент на ножестве своих чистых стратегий, применяя смешанную стратегию ¡3^. По шнчании каждого раунда игроки получают очки согласно своим матрицам аигрышей. При е — 0 повторяющаяся игра £-наилучших ответов переходит (детерминированную) повторяющуюся игру наилучших ответов. Следуя рассмотренному в главе 1 общему случаю, математические ожида-ия средних выигрышей (1), задаваемые выражениями

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

Раздел 2.3 посвящен вычислению предела ожидаемых средних выигрышей 5) при I —> оо. Основную часть анализа составляет вывод следующего пред-гавления:

[ри помощи данного представления получен явный вид пределов ожидаемых редних выигрышей (8) при I оо.

'еорема 7. Предел ожидаемого среднего выигрыша а^З] (8) первого игрока I раундах бесконечной повторяющейся игры е-наилучших ответов, соот-етствующей паре 5 (7), при I —> оо существует и равен

а^то)[5] = + (1 - ш^аци^ + а>,а12(1 - а;*,) + (1 — 2(1 -и,*),

ак[Б] =

(/Зта)2Л(/Зат)2, если к четно

(РТа)^/3ТАТаТ(РаТ)к*к, если к нечетно

де

I, = у, [-З] =

Рг{<*\ - а2) + а2

ш». = ш,*^] =

1-001-&)(«!-<*2)'

1 + (А-А)(а1-аз)'

В отношении второго игрока справедлив аналогичный результат.

Раздел 2.4 посвящен поиску равновесных функций е-наилучшего ответа.

Определение. Пару 5* = ((а*, с^), (/?*, функций е-наилучших от ветов игроков назовем равновесной (по Нэшу) в бесконечной повторяющей ся игре е-наилучших ответов, если для любого е-наилучшего ответа (а^аг) первого игрока верно а'00^] < а(оо) [<?*], где — ((ах, а2), /?£)), и дл: любого е-наилучшего ответа (/3^, /Зг) второго игрока верно М00'^] < Ь^ [5*]

где £2* = ((<*!, а$), (А, &))■

Полученный результат состоит в следующем. При достаточно малом е \ бесконечной повторяющейся игре е-наилучших ответов каждый игрок име ет оптимальную функцию е-наилучшего ответа, которая максимизирует ег ожидаемый выигрыш вне зависимости от выбора партнером своей функци е-наилучшего ответа. Структура оптимальной функции е-наилучшего ответ; игрока зависит от соотношений между элементами матрицы выигрышей этс го игрока и не зависит от матрицы выигрышей его партнера. Оптимальна функция (с^, й'з) е-наилучшего ответа первого игрока имеет вид (1 — е, О либо (1, е), т.е. одна из ее компонент остается чистой стратегией наилучшег ответа, другая же максимально рандомизируется. Аналогичные наблюдени справедливы в отношении оптимальной функции (¡З^, е-наилучшего отве та второго игрока. Пара оптимальных функций е-наилучшего ответа явля ется равновесной. Из данного результата следует, что для каждого из игре ков малая рандомизация ответного выбора является целесообразной: перехо обоих игроков от исходных детерминированных стратегий наилучшего отве та к оптимальным (частично рандомизированным) стратегиям е-наилучшег ответа ведет к увеличению значения среднего ожидаемого выигрыша дл каждого из них.

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

Глава 3

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

0 названных «консерватизм» и «инноваторство». Игрок-консерватор не ме-яет номера своей чистой стратегии на следующем раунде. Игрок-инноватор раунде к + 1 применяет чистую стратегию, отличную от чистой стратегии, римененной им в раунде к.

Под бесконечной повторяющейся игрой с двумя типами поведения по-имается процесс повторения исходной биматричной игры в бесконечной по-ледовательности раундов 0,1,2,... при условии, что каждый игрок является ибо консерватором, либо инноватором: в раунде 0 реализуется априорно за-анная пара (¿о,^о) чистых стратегий, и в каждом раунде к + 1 каждый игрок рименяет свою чистую стратегию в соответствии со своим типом поведения зависимости от его чистой стратегии, реализованной в раунде к. Далее вводится в рассмотрение процесс, аналогичный бесконечной повто-яющейся игре с двумя типами поведения, в котором, однако, игроки в каж-ом последующем раунде отдают лишь вероятностные предпочтения своим истым стратегиям, соответствующим их типам поведения. В этом процессе ля каждого игрока в качестве инструмента генерирования решений выступа-г та или иная функция е-релаксированного выбора. Фиксируем е € (0,1/2).

Определение. Функцией е-релаксированного выбора первого игрока на-овем любую пару (а, 1 — а) смешанных стратегий первого игрока такую, то

(а) 1 > а > 1 — е, если первый игрок - консерватор;

(б) 0 < а < е, если первый игрок - инноватор.

Данное определение подразумевает, что первый игрок в раунде к +1 выби-ает свою смешанную стратегию а при реализации в раунде к своей чистой тратегии 1 и выбирает смешанную стратегию 1 — а при реализации в раунде : своей смешанной стратегии 2. Из определения следует, что, будучи кон-ерватором, первый игрок в раунде к + 1 задает большую вероятность своей истой стратегии, реализованной в раунде к, и, будучи инноватором, задает ольшую вероятность своей чистой стратегии, отличной от реализованной им раунде к. При а = 1 называем первого игрока чистым консерватором, при 1 > а > 1 — е - е-консерватизмом, при а = 0 - чистым инноватором, при

1 < а < е - е-инноватором. Аналогичные определения даются в отношении второго игрока.

Определение. Каждую пару

5 - ((а, 1-а), (/3,1-/3)), (9)

где (а, 1 - а) - функция е-релаксированного выбора первого игрока и (/3,1 -/3) - функция е-релаксированного выбора второго игрока, называем паро функций е-релаксированного выбора игроков.

Для произвольной пары 5 (9) функций е-релаксированного выбора ш роков рассмотрим случайный процесс, который назовем е-релаксированно бесконечной повторяющейся игрой, соответствующей Процесс состоит и раундов 0,1,2,..., в каждом из которых игроки разыгрывают биматричну] игру. Процесс развивается по следующей схеме. В раунде 0 реализуется н! чальная пара (г0,;'о) чистых стратегий игроков. Если в раунде к реализуете пара {1к,3к) чистых стратегий игроков, то первый игрок для выбора своей ч] стой стратегии гк+\ в раунде к+1 производит статистический эксперимент и множестве своих чистых стратегий, применяя смешанную стратегию а, есл гк = 1, и стратегию (1 - а), если гк = 2. Аналогично, второй игрок для вь бора своей чистой стратегии в раунде к+ 1 производит статистически эксперимент на множестве своих чистых стратегий, применяя смешанну стратегию ¡3, если зк = 1 и стратегию (1-,/3), если ]к = 2. По окончании кал дого раунда игроки получают очки согласно своим матрицам выигрыше Данный процесс представляет собой модель поведения взаимодействуют;! игроков, которая, в случае е > 0, допускает большую гибкость в выбо1 действий по сравнению с детерминированной игрой: в каждом последующе раунде каждый игрок выбирает свою будущую чистую стратегию из услов! вероятностного предпочтения своей чистой стратегии, соответствующей е типу поведения.

Аналогично предыдущим главам, выигрышами игроков выступают мат матические ожидания их средних выигрышей, получаемых на протяжен! всех раундов.

Теорема 8. Для е-релаксированной бесконечной повторяющейся игры, с ответствующей паре 5 функций е-релаксированного выбора игроков (9), с ществует предел

а(о°)[5] = Нш аг[5], (1

¡—►оо

значения которого приведены в таблице 1.

Предел о^00^] (10) будем называть ожидаемым выигрышем первого игро-1 в г-релаксированной бесконечной повторяющейся игре, соответствующей *ре 5 (9).

Таблица 1.

Условия Поведение первого игрока Поведение второго игрока

а,0е (0,1) е-консерватор либо г-инноватор г-консерватор либо 5-инно»атор ои+а^+вгт+в^а 4

а = 1,0е(О,1) чистый консерватор «-консерватор либо г-ии новатор

а = 0,0 е(0,1) чистый инноватор г-консерватор либо е-инноватор 4

а £ (0,1), 0 = 1 ¿•консерватор либо Б-инноватор чистый консерватор

се (0,1), 0 = 0 е-консерватор либо е-инноватор чистый инноватор ИП+ШТ+И!^

а= 1,0 = 1 чистый консерватор чистый консерватор

а = 0, 0 = 1 чистый инноватор чистый консерватор

а = 1, 0 = 0 чистый консерватор чистый инноватор 22Ф"№о,;о)е{(2т1),(2,2)})

а = 0, 0 = 0 чистый инноватор чистый инноватор ^Щ^-т.М 6 {(1,2), (2,1)))

Отметим, что, как видно из таблицы 1, при стремлении первого игрока г е-консерватизма к чистому консерватизму, т. е. при стремлении а к 1 газу (без вариаций вторым игроков значения /3), его ожидаемый средний ыигрыш а[5*], вообще говоря, не стремится к значению, соответствующему тучаю а = 1, т. е. чистому консерватизму. Такого же рода разрывы имеют есто при стремлении о; к 0 сверху.

Утверждение, аналогичное теореме 8, справедливо в отношении второго грока.

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

Автор выражает глубокую признательность своему научному руководите-ю, академику РАН, доктору физико-математических наук, профессору Ар-адию Викторовичу Кряжимскому за постановку задач, постоянное внима-ие к работе и многолетнюю поддержку.

Публикации автора по теме диссертации

[1] Райгородская A.B. К выбору равновесного поведения в бесконечной повторяющейся игре размерности 2 х 2: случай игроков-консерваторов и игроков-инноваторов /'/ Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2012. № 1. С. 15-22.

[2] A.B. Райгородская. Равновесные поведения игроков в бесконечной повторяющейся игре £-наилучших ответов размерности 2x2// Труды ИММ УрО РАН. 2011. Т. 17. № 1. С. 201-216.

[3] A.B. Райгородская. Стохастическая двухшаговая игра е-наилучших ответов размерности 2x2// Математическая теория игр и ее приложения. 2010. Т. 2. № 4. С. 84-105.

[4] A.B. Кряжимский, A.B. Райгородская. О равновесных стратегиях поведения в бесконечных повторяющихся играх // Проблемы динамического управления. М.: МАКС Пресс. 2012. Вып. 6. С. 133-159.

Напечатано с готового оригинал-макета

Подписано в печать 19.04.2012 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 191.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 939-3890. Тел./факс 939-3891.