Динамические сетевые игры с попарным взаимодействием

Булгакова Мария Александровна

Динамические сетевые игры с попарным взаимодействием

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

Организация и управление

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 5be591497966e104e4a12523

UUID: b97ab4f0-c654-0136-3dfc-525400005860

Язык: Русский

Опубликовано: больше 5 лет назад

Просмотры: 10

Булгакова Мария Александровна

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 503,4 КБ

Поделиться работой

Санкт-Петербургский государственный университет Факультет прикладной математики - процессов управления Кафедра математической теории игр и статистических решений Булгакова Мария Александровна Выпускная квалификационная работа по основной образовательной программе «Математическая кибернетика», направление подготовки «02.06.01 Компьютерные и информационные науки» Динамические сетевые игры с попарным взаимодействием Заведующий кафедрой, доктор физ.-мат. наук, профессор Петросян Л. А. Научный руководитель, доктор физ.-мат. наук, профессор Петросян Л. А. Рецензент, доктор физ.-мат. наук, доцент Реттиева А. Н. Санкт-Петербург 2018

Содержание Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Цели и задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Апробация работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1 Динамические сетевые игры 11 1.1 Двухшаговые игры . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.1 Выбор управления . . . . . . . . . . . . . . . . . . . . 12 1.1.2 Кооперация в двухшаговых играх на втором шаге . . 14 1.1.3 Кооперация в двухшаговых играх на обоих шагах . . 16 1.1.4 Динамически устойчивые и сильно-динамически устойчивые решения . . . . . . . . . . . . . . . . . . . . . . 17 1.2 Динамические игры с шоком . . . . . . . . . . . . . . . . . . 19 1.3 Стратегическая поддержка кооперации . . . . . . . . . . . . 21 2 Описание сетевой игры с попарным взаимодействием 2.1 Общие сведения . . . . . . . . . . . . . . . . . . . . . . . 2.2 Характеристическая функция . . . . . . . . . . . . . . . . 2.2.1 Пример построения характеристической функции 2.3 Другой способ построения характеристической функции 2.3.1 Пример построения харакетристической функции 2.4 Выпуклость игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 23 24 27 28 30 31 3 Решение сетевых игр с попарным взаимодействием: Вектор Шепли 34 3.1 Вектор Шепли для сети-звезда . . . . . . . . . . . . . . . . . 34 2

3.2 Динамическая устойчивость вектора Шепли . . . . . . . . . 3.2.1 Дилемма заключенного . . . . . . . . . . . . . . . . . 3.2.2 Динамически неустойчивый вектор Шепли . . . . . . 37 39 41 4 Решение сетевых игр с попарным взаимодействием: C-ядро 44 4.1 Сильная динамическая устойчивость С-ядра . . . . . . . . . 47 4.2 Пример сильной динамической устойчивости ядра . . . . . . 49 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3

Введение На протяжении многих лет игровые и сетевые модели успешно используются для описания сложных систем и работы с ними. Результаты, полученные в теории игр, нашли большое количество приложений в самых разных сферах человеческой деятельности — в социологии, экономике, организации транспортных перевозок, линий связи, военном деле и многом другом. Согласно определению, приведенному Г. Оуэном, [5] теория игр — раздел прикладной математики, исследующий модели принятия решений в условиях несовпадения интересов сторон (которые называются игроками), когда каждая сторона стремится воздействовать на развитие ситуации в собственных интересах. Кооперативной называется игра, в которой группы игроков — коалиции — могут объединять свои усилия для достижения наилучшего результата. Теория графов с точки зрения теоретической дисциплины может рассматриваться как одна из частей дискретной математики, исследующий свойства конечных множеств с заданными отношениями между элементами [3]. Теория графов с точки зрения прикладной дисциплины, позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы. Подробно описаны методы дискретной математики, моделирующие процессы произвольной природы, в том числе используя графы, Ф.С. Робертсом в книге [14]. Начало этой науки — теории графов — было положено Эйлером, при решении известной многим задачи о кенигсбергских мостах (как пройти по всем семи мостам, не проходя ни по одному из них дважды). Позднее теория графов применялась Кирхгофом при исследовании им электрических сетей, Кели в органической химии, Гамильтоном для решения головоломок и многими другими математиками и специалистами, занимающимися картографией и раскраской карт. Решение Эйлера задачи о мостах совсем недавно было применено для оп- 4

тимизации движения подметальных машин в больших городах, что дало большую экономию топлива, в следствии чего так же улучшились экологические показатели региона. Между теорией игр и теорией графов существует тесная взаимосвязь. Инструменты и результаты теории графов широко используются в задачах по теории игр: • древовидный граф задает структуру принятия решений в игре в развернутой форме [7], • граф, где вершины — игроки, задает структуру всевозможных коалиций [4], • граф отражает постоянные или временные связи между игроками, • на графе в дискретном времени осуществляется "игра поиска"(вершины — позиции игроков, ребра — возможные пути переходов) [6]. Отдельно следует выделить теорию сетевых игр — относительно молодой (развивающийся с конца 70-х годов прошлого века) раздел теории игр, акцентирующий внимание как раз на формировании сетевых структур — устойчивых связей между игроками — в условиях несовпадения интересов. Точнее употреблять термин игра формирования сети, результатом которой является сеть, устанавливающая взаимосвязи между игроками. Далее рассматриваются так называемые "игры на сетях", где сеть уже является фиксированной, и не подлежит дальнейшим изменениям [24]. Основополагающим понятием любой игры является понятие выигрыша. В кооперативных играх важнейшей частью исследования является рассмотрение возможности создания коалиций и предложение по корректному распределению суммарного кооперативного выигрыша между игроками. Для этого наиболее удобен аппарат характеристических функций, показывающий возможности коалиции и являющийся основой для построения схем распределения суммарного выигрыша, приемлемых для игроковучастников. Достаточно полно по вопросам описания и решения кооперативные игры исследуются в книге С.Л.Печерского и Е.Б.Яновской [13]. В 5

более поздних работах Печерского решается вопрос о применении пропорционального дележа для игры многих лиц и для игр с нетрансферабельной полезностью. Не смотря на то, что теория кооперативных игр непрерывно развивается, вопрос о разделении выигрыша коалиций во многих постановках попрежнему открыт. В реальной жизни люди постоянно сталкиваются с ситуациями, в которых они взаимодействуют с кем-либо через посредников. Иными словами, даже работая с крупными компаниями, взаимодействие сводится к решению вопросов один на один с посредником, представителем компании. Это один из многих примеров попарного взаимодействия между игроками. Впервые в теории игр попарное взаимодействие упоминается в работе [21]. В некооперативной игре с попарным взаимодействием исследуется существование равновесия по Нэшу, а так же время его нахождения. Попарное взаимодействие было так же рассмотрено на примере распространения информации и дезинформации в социальных сетях в работе [15]. Однако все эти работы относеятся к некооперативным играм. Понимая актуальность данной темы, автором работы была выбрана для исследования структура сетевых игр с попарным взаимодействием игроков в применении к кооперативным многошаговым играм. После исследования кооперативного поведения, очень важно рассмотреть вопрос о том, следуют ли игроки принятым в начале игры кооперативным соглашениям на следующих шагах игры. Если найденное решение обладает свойством динамической (сильно-динамической) устойчивости, у игроков нет никаких причин отклоняться от принятых соглашений. Понятие сильной динамической устойчивости впервые было введено в [9]. Зачастую решения кооперативных игр не обладают этим свойством. Тогда возникает необходимость предупредить возможное отклонение игроков от кооперативного поведения. Процедура распределения дележа (ПРД) — это структура выплат, которая обеспечивает реализацию решения — была введена с целью предотвратить отклонения игроков в работе [11]. Работа имеет следуюшую структуру: в первой главе приводится крат6

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

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

Апробация работы Выступления с докладами на конференциях и семинарах: 1. III International Conference in memory of V.I.Zubov (2015) — Международная конференция «Устойчивость и процессы управления», посвященная 85-летию со дня рождения проф., чл.-корр. РАН В.И.Зубова. 5 9 октября 2015 года, Санкт-Петербург, факультет Прикладной математики – процессов управления Санкт-Петербургского государственного университета (СПбГУ). 2. XIII Международная конференция «Устойчивость и колебания нелинейных систем управления» (конференция Пятницкого)(2016) — Институт проблем управления им. В. А. Трапезникова Российской академии наук, Москва, июнь 2016. 3. Game Theory and Management (2016) — Санкт-Петербургский государственный университет, факультет Прикладной математики и процессов управления, Высшая школа менеджмента. Санкт-Петербург, 7-9 июля 2016 4. Международный семинар "Networking Games and Management— 5-6 июля 2016, Петрозаводск, Россия 5. Game Theory and Management (2017)— Санкт-Петербургский государственный университет, факультет Прикладной математики и процессов управления, Высшая школа менеджмента. Санкт-Петербург, 28-30 июня 2017 6. "Конструктивный негладкий анализ и смежные вопросы"(2017) — 22–27 мая 2017 г., Международный математический институт им. Леонарда Эйлера, Санкт-Петербург 9

7. XLIX международная научная конференция аспирантов и студентов «Процессы управления и устойчивость», Санкт-Петрбург, факультет Прикладной математики - процессов управления СПбГУ, 2-5 апреля 2018 г. 8. XIV Международная конференция «Устойчивость и колебания нелинейных систем управления» (конференция Пятницкого)(2018) — Институт проблем управления им. В. А. Трапезникова Российской академии наук, Москва, 30 мая - 1 июня 2018. Основные публикации: 1. Булгакова М.А., Петросян Л.А., «Сильно-динамически устойчивое ядро в многошаговой игре», Constructive Nonsmooth Analysis and Related Topics / Конструктивный негладкий анализ и смежные вопросы Тезисы докладов международной конференции, посвященной памяти профессора В.Ф. Демьянова. 2017. С. 220-224. 2. M. A. Булгакова, Л. A. Петросян , «Кооперативные сетевые игры с попарным взаимодействием», Математическая теория игр и ее приложения, т. 4, № 7, стр. 7-18, 2015. 3. M. A. Bulgakova and L. A. Petrosyan, «The Shapley value for the network game with pairwise interactions» in Stability and Control Processes in Memory of V.I. Zubov (SCP), SPb, 2015, pp. 229-232. 4. Bulgakova, M. A., Petrosyan, L. A., «About Strongly Time-Consistency of Core in the Network Game with Pairwise Interactions». Proceedings of 2016 International Conference «Stability and Oscillations of Nonlinear Control Systems». pp. 157-160. Moscow (2016) 10

Глава 1 Динамические сетевые игры 1.1 Двухшаговые игры Двухшаговая игра рассматривается как базовая модель, в которой на первом шаге игроки формуируют сеть, а на втором шаге выбирают управления. Следуя [26], стратегия игрока в сетевой игре — это правило, которое единственным образом определяет поведение игрока на обоих шагах игры (поведение игрока на втором шаге зависит от сети, сформированной на первом шаге). Предполагается, что выигрыш каждого игрока зависит от поведения игрока на втором шаге, и поведения его "соседей"по сети, котора была сформирована на первом шаге. Похожая модель с двухшаговой сетевой игрой рассматривалась в работах [23], [25]. В этих работах авторы рассматривали модель, в которой игроки формируют сеть на первом шаге, и на втором шаге игроки участвуют в координационной игре 2 × 2, которая одинакова для всех игроков. В работах, упомянутых выше, не рассматривалась проблема динамической устойчивости решений. Эта проблема впервые была обозначена в работе [9] для кооперативных дифференциальных игр, и, позднее, специальный механизм пошаговых выплат — процедура распределения дележа 11

— была введена для преодоления трудности, связанной с динамической неустойчивостью решений. Модель Данная модель была описана в работе [10]. Рассмотрим ее подробнее. Пусть N = {1, . . . , n} — конечное множество игроков, которые могут взаимодействовать друг с другом посредством создания связей. Кооперация между игроками при таком предположении ограничена стетевой структурой. Сеть задает пара (N, g), где N — это множество узлов сети, которое отождествляется с множеством игроков, а g ∈ N × N — множество связей, представленное ребрами графа. Если пара (i, j) ∈ g, это означает, что между игроками i и j есть связь. Предполагается, что связи неориентированы, то есть (i, j) = (j, i), далее будем обозначать связь просто как пару ij. На первом шаге игроки выбирают своих партнеров — тех игроков, с которыми они хотят создать связь. Такой выбор порождает сеть, как результат первого шага. Имея сформировавшуюся сеть, игроки выбирают управление, влияющее на их выигрыш на втором шаге. 1.1.1 Выбор управления Первый шаг (шаг формирования сети) подробно описывается в главе 2. Остановимся здесь подробнее на втором шаге, на котором происходит выбор управления. После формирования сети игроки выбирают свои поведения на втором шаге. Обозначим за Ni — множество соседей игрока i (подробнее см. глава 2). Игроки могут пересмотреть свои решения, сделанные на первом шаге, то есть они обладают возможностью разорвать связь, созданную на первом шаге. Определим компоненты n-мерного вектора di (g) по следующему прави- 12

лу: d1ij    1, если игрок i не разрывает связь, = сформированную на первом шаге с игрокомj ∈ Ni (g)   0, в противном случае Элементы di (g), удовлетворяющие приведенному условию, обозначим как Di (g), i ∈ N . Профиль (di (g), . . . , dn (g)), примененный к сети g, изменяет ее структуру, образуя новую сеть, котору мы обозначим чeрез g d . Сеть g d образуется из сети g путем удаления тех связей ij, для которых выполняется условие dij = 0 или dij (g) = 0. Кроме того, на втором шаге игрок i ∈ N выбирает управление ui из конечного множества Ui . Например, в работах [23], [25] Ui — это множество стратегий игрока i в симметричной координационной игре 2 × 2, в которую игрок i ∈ N играет со своими соседями по сети. Множества стратегий U1 , . . . , Un не имеют какой-то конкретной структуры, предполагается только, что они конечны. Таким образом, поведение игрока i ∈ N на втором шаге это пара (di (g), ui ). Эта пара определяет, с одной стороны, связи di (g), которые будут удалены в ходе второго шага, и, с другой стороны, управление ui . Функция выигрыша Ki игрока i ∈ N зависит от двух параметров: от новой сети g d и управления ui , i ∈ N . Иными словами, она зависит не только от поведения игрока i на втором шаге, но и от поведения его соседей по новой сети g d , т.е. Ki (ui , uNi (gd )) — это неотрицательная функция опреQ деленная на Ui × j∈Ni (gd ) Uj . Здесь uNi (gd ) обозначает профиль управлений uj выбранный всеми соседями j ∈ Ni (g d ) игрока i в сети g d . Предположим, что функции Ki , i ∈ N , удовлетворяет следующему свойству: Свойство *: Для любых двух сетей g и g 0 , таких, что g 0 ⊆ g, управQ ления (ui , uNi (g) ) ∈ Ui × j∈Ni (gd ) Uj и для любого игрока i неравенство Ki (ui , uNi (g) ) ≥ Ki (ui , uNi (g0 ) ) выполняется. 13

1.1.2 Кооперация в двухшаговых играх на втором шаге Исследование кооперации в двухшаговых играх включается в себя поиск ответа на три главных вопроса: • Что есть кооперативное решение в игре? • Может ли оно быть реализовано? • Обладает ли оно свойством (сильной) динамической устойчивости? Предположим, что профиль поведения игроков (g1 , ..., gn ), gi ∈ Gi , i ∈ N , который был выбран на первом шаге, зафиксирован, и формирует сеть g. На втором шаге игроки одновременно выбирают n пар (d∗i (g), u∗i ) ∈ Di (g) × Ui , i ∈ N, максимизирующих суммарный выигрыш игроков. [10] Обозначим через u∗ стратегию, максимизирующую суммарный выигрыш: X X Ki (u∗i , u∗Ni (g) ) = max Ki (ui , uNi (g) ) ui ∈Ui ,i∈N i∈N i∈N Следующая проблема заключается в том, каким способом разделить полученный максимальный суммарный выигрыш игроков между ними. После процедуры распределения игра заканчивается. Чтобы разделить максимальный суммарный выигрыш между игроками строится кооперативная игра с трансферабельной полезностью (N, v(g)). Характеристическая функция v(g) в данной игре определяется для всех подмножеств S ⊆ N — коалиций — по следующему правилу: v(g, N ) = X Ki (u∗i , u∗Ni (g) ) i∈N 14

X v(g, S) = max ui ∈Ui ,i∈S Ki (u∗i , u∗Ni (g)∩S ) i∈S v(g, ∅) = 0 С учетом того, что сеть g считается фиксированной. В работе [10] характеристическая функция определена согласно подходу Неймана и Моргенштерна (1944). А именно, значение v(g, S) — это максимальный выигрыш, который коалиция S может себе гарантировать (максиминное значение) в игре с нулевой суммой между двумя игроками: коалицией S, максимизирующей свой выигрыш, и дополнительной коалицией N \ S, минимизирующей выигрыш S, при условии, что сеть g фиксирована. Однако в [10] была предложена более упрощенная форма характеристической функции. Утверждение: Если функция выигрыша Ki , i ∈ N неотрицательна, и удовлетворяет свойству (*), тогда максимальный выигрыш коалиции S, который она может себе гарантировать, вычисляется по формуле: X v(g, S) = max Ki (ui , uNi (g)∩S ) ui ∈Ui ,i∈S i∈S Необходимо заметить, что такое предположение позволяет вычислять значение v(d, S), S ⊂ N как решение задачи максимизации. Найти такое решение проще, чем поиск максиминного значения в общем случае. Для единичной коалиции {i} значение характеристической функции определяется аналогичным образом: v(g, {i}) = max Ki (ui ) ui ∈Ui И это значение не зависит от структуры сети. Дележ определяется как n-мерный профиль ξ(g) = (ξ1 (g), . . . , ξn (g)), удовлетворяющий одновременно свойствам эффективности и индивидуаль- 15

ной рациональности: X ξi (g) = v(g, N ), i∈N ξi (g) ≥ v(g, {i}), i ∈ N. Обозначим множество дележей в игре (N, v(g)) через I(v(g)). Кооперативное решение в игре с трансферабельной полезностью (N, v(g)) с фиксированной сетью g — это правило, которое единственным образом ставит в соответствие подмножество CSC(v(g)) ⊆ I(v(g)) игре (N, v(g)). Например, если в качетсве кооперативного решения выбрано С-ядро C(v(g)), тогда CSC(v(g)) = C(v(g)) = {ξ(g) ∈ I(v(g)) : X ξi (g) ≥ v(g, S), S ⊂ N } i∈S 1.1.3 Кооперация в двухшаговых играх на обоих шагах Предположим теперь, что игроки совместно выбирают свои поведения на обоих шагах игры. Действуя, как один игрок, и выбирая gi ∈ Gi , ui ∈ Ui , i ∈ N максимальная коалиция N максиммизирует значение X Ki (ui , uNi (g) ) i∈N Пусть максимальное значение достигается, когда игроки выбирают поведение gi∗ , u∗i , i ∈ N , и формируют сеть g ∗ . D этом случае, чтобы максимизировать суммарный выигрыш коалиции N игрокам не стоит разрывать связи на втором шаге. Пусть X i∈N Ki (u∗i , u∗Ni (g) ) = max max gi ∈Gi ,i∈N ui ∈Ui ,i∈N X Ki (ui , uNi (g) ) i∈N Для разделения выигрыша в соответствии с некоторым дележом вводится кооперативная игра с трансферабельной полезностью (N, V ) Характерситическая функция V определяется аналогично функции v(g), расмот16

ренной выше. Утверждение: В кооперативной двухшаговой игре супераддитивная характеристическая функция V (·) в смысле Неймана и Моргенштерна определяется как: X Ki (u∗i , u∗Ni (g∗) ) v(N ) = i∈N v(S) = max max gi ∈Gi ,i∈S ui ∈Ui ,i∈S X Ki (ui , uNi (g)∩S ) i∈S V (∅) = 0. Для единичной коалиции {i} значение характеристической функции определяется следующим образом: V ({i}) = max Ki (ui ) ui ∈Ui Дележ в кооперативной двухшаговой игре — это n-мерный профиль P ξ = (ξ1 , . . . , ξn ), удовлетворяющий условиям i∈N ξi = V (N ) и ξi ≥ V ({i}) для всех i ∈ N . Множество всех дележей в игре (N, V ) обозначим через I(v). Кооперативное решение в кооперативной игре с трансферабельной полезностью (N, V ) — это правило, которое единственным образом ставит в соответствие подмножество CSC(V ) ⊆ I(V ) игре (N, V ). Например, если коопертивным решение является ядро C(V ), тогда CSC(V ) = C(V ) = {ξ ∈ I(V ) : X ξi ≥ V (S), S ⊂ N } i∈S 1.1.4 Динамически устойчивые и сильно-динамически устойчивые решения Предположим, что в начале игры игроки предварительно договорились выбирать совместно профиль поведений gi∗ , u∗i , i ∈ N , для максимизации суммарного выигрыша, и затем разделять его в соответствии с принятым 17

кооперативным решением CSC(V ), реализацией которого является дележ ξ = (ξ1 , . . . , ξn ). Это означает, что в кооперативной двухшаговой сетевой игре игрок i ∈ N ожидает получить часть выигрыша, равноую ξi . Что произойдет, если после первого шага (после выбора поведений g1∗ , . . . , gn∗ ) игрок i ∈ N пересчитает дележ, соответствующий тому же самому кооперативному решению? Профиль поведений g1∗ , . . . , gn∗ на первом шаге формирует сеть g ∗ , следовательно, после пересчета дележа (в соответствии с аналогичным кооперативным решением ξ), выигрыш игрока i будет равен ξi (g ∗ ), основанный на значении харакетристической функции v(g ∗ , S) для всех S ⊆ N . Определние динамической устойчивости дележа было адаптировано для двухшаговой сетевой игры в работе [10]. В вышеумпомянутой статье было показано, что вектор Шепли, τ -вектор и С-ядро — неустойчивые кооперативные решения в этом классе игр. Определение: Дележ ξ ∈ CSC(V ) является динамически устойчивым, если найдется такое ξ(g ∗ ) ∈ CSC(v(g ∗ )), что следующее равенство имеет место для всех игроков: ξi = ξi (g ∗ ), i∈N Кооперативное решение CSC(V ) динамически устойчиво, если любой дележ ξ ∈ CSC(V ) является динамически устойчивым. Последнее равенство означает, что если мы выбираем кооперативное решение CSC(V ) на первом шаге, и в соответствии с ним считаем дележ ξ, определяющий выигрыш игроков, и затем на втором шаге пересчитываем выигрыши игроков, в соответствии с таким же кооперативным решением CSC(v(g ∗ )), т.е. вычисляем новый дележ ξ(g ∗ ), зависящий от сети g∗, выигрыши игроков не изменятся. Утверждение: Любое кооперативное решение, основанное только лишь на значениях V (N ), V ({i}), i ∈ N является динамически устойчивым. 18

Замечание: В условиях предыдущих предположений, CIS-вектор [20], вычисляемый по формуле: P V (N ) − j∈N V ({j}) , i∈N CISi = V ({i}) + |N | является динамически устойчивым кооперативным решением. 1.2 Динамические игры с шоком Следующие работы [22], [27] посвящены повторяющимся играм с конечным числом шагов. Первый шаг — шаг формирования сети, на котором игроки выбирают своих соседей. Все последующие шаги имеют схожую структуру: наблюдая сформировавшуюся сеть, каждый игрок может пересмотреть множество своих соседей (точнее, он может только лишь уменьшить это множество) и после этого игрок выбирает управление. Решение игрока, принятое на текущем шаге, не влияет на структуру игры на последующих шагах. Оно так же имеет название «шок», некоторый внешний фактор случайной природы. Существует множество различных типов «шоков». Например в работе [19] «шок» изменял множество стратегий игрока. Предполагалось, что «шок» делал некоторого игрока неактивным в игре. Более того, предполагалось, что «шок» может возникать на любом шаге после шага формирования сети, но как только «шок» проявился, ни в каком последующем шаге он уже не произойдет. Работы [22], [27] так же охватывают проблему динамической устойчивости кооперативных решений в повторяющихся играх, а именно, устойчивость на подыграх динамического вектора Шепли. Известно, что вектор Шепли, это эффективное кооперативное решение. Вектор Шепли динамически устойчив, если для любого игрока его часть вектора Шепли равна сумме индивидуальных платежей до произвольного шага и части компоненты вектора Шепли в подыгре, начинающейся с этого шага, при условии, что все игроки следуют кооперативному соглашению. Неусточивость 19

кооперативных решений может приводить к отклонению от кооперативных соглашений. В этом случае вводится процедура распределения дележа, позволяющяя обеспечить соответствие кооперативному соглашению в течении всей игры. В качестве практического приложения описанной теории, можно привести беспроводную сеть. В которой пары беспроводных агентов (игроков) могут передавать данные друг другу. Передача данных считается успешной, если силы передатчика (игрока) достаточно для того, чтобы покрыть расстояние до приемника (другого игрока). В этом случае эти игроки считаются связанными. При такой постановке задачи первый шаг может быть интерпретирован, как шаг, на котором игроки выбирают силу передатчика. Наблюдая сформировавшуюся сеть, игроки могут уменьшить силу передатчика (если это имеет смысл) и выбрать емкость передатчика в соответствии с имеющимся спросом, в то время как шок может сделать некоторого игрока неактивным в этой сети. При кооперативной постановке задачи игроки могут сконцентрироваться на поиске таких стратегий, которые максимизируют суммарный ожидаемый выигрыш, либо сеть, в соответствии с топологией и емкостями передатчиков, выбранных игроками. Модель Рассматривается динамическая игра, включающая в себя более, чем два шага. Пусть l +1 это длительность игры. Игра состоит из одного шага формирования сети и l игровых повторяющихся шагов. Когда игра полностю определена, легко распространить теорию, относящуюся к двухшаговым играм на (l + 1)-шаговую игру. С этой целью вводится случайный элемент, называемый «шок», который влияет на сетевую структуру. «Шок», который может возникать между шагами игры с заданной вероятностью p, характеризуется дискретной случайной величиной ω, которая может принимать только l + 1 значение. Если ω = 0, шок не возникает в игре, в то время как ω = t означает номер шага, которому предшествовал «шок». 20

Предполагается, что вероятность появления шока на шаге t равна P (ω = t) = (1 − p)t−1 p, для t ∈ {1, . . . , l}. И вероятность того, что шок в игре не появится: P (ω = 0) = (1 − p)l . 1.3 Стратегическая поддержка кооперации Эта проблема была подробно рассмотрена в работе [28]. Для игроков кооперация более предпочтительна, чем некооперативное поведение, если она дает всем игрокам больший выигрыш. Однако в динамических играх кооперативное соглашение порождает две глобальные проблемы. Первая проблема заключается в том, что любые динамические кооперативные решения в общем случае неустойчивы: даже если все игроки согласны на кооперативное решение в начале игры, игроки (или группы игроков), максимизирующие собственный выигрыш, могут захотеть пересмотреть решение после некоторых шагов игры (спустя некоторое время). Чтобы сделать игроков устойчивыми к пересмотру решений в течении игры, вводится процедура распределения дележа, перераспределяющая кооперативный выигрыш, предписанный принятым кооперативным решением, по индвидуальным выплатам на каждом шаге. Вторая глобальная проблема состоит в том, что кооперативные стратегии игроков, которые приводят к кооперативному выигрышу, не являются в общем случае равновесием по Нэшу. Это означает, что существует игрок, который может выиграть больше, если отклонится от кооперативного соглашения, принятого ранее. Введение сильно-динамически устойчивой процедуры распределения дележа делает возможным найти такое равновесие по Нэшу, которое гарантирует достижение кооперативного выигрыша на некотором классе стратегий. Однако, сделать это мы можем только накладывая специфицеские условия на параметры динамической игры. 21

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

Глава 2 Описание сетевой игры с попарным взаимодействием 2.1 Общие сведения Пусть N — конечное множество игроков, которые принимают решения на двух шагах, |N | = n ≥ 2. На первом шаге z1 каждый игрок i ∈ N выбирает свое поведение b1i — n-мерный вектор предложений связи другим игрокам, компонентами которого являются 0 и 1. Результатом первого шага является сеть g(b11 , . . . , b1n ). На втором шаге z2 (g), который зависит от сети, выбранной на первом шаге, соседи по сети играют попарно в одновременные биматричные игры, после этого игроки получают выигрыши и игра заканчивается. Другими словами, мы имеем двухшаговую игру Γ, которая является особым случаем многошаговых неантагонистических игр. Адаптируя к этому случаю определение стратегий, мы имеем, что в нашем случае стратегия, это правило, которое для каждого игрока определяет множество его соседей на первом шаге, а именно, вектор b1i , и поведение в каждой биматричной игре на втором шаге, в соответствии с сетью, которая сформирована на первом шаге — b2i . Обозначим через ui = (b1i , b2i ), i ∈ N стратегию игрока i в двухшаговой игре Γ. Определим выигрыш игрока i как hi (z2 ), где (z1 , z2 ) это траектория, реализованная в ситуации 23

u = (u1 (·), . . . , un (·)) в игре Γ. Функция выигрыша в игре Γ с начальной позицией z1 определяется как Ki (z1 ; u) = Ki (z1 ; ui (·), . . . , un (·)) = hi (z2 ) Рассмотрим первый шаг игры Γ. Как было упомянуто, игроки на этом шаге выбирают поведения b1i = (b1i1 , . . . , b1in ), с компонентами: ( b1ij = 1, если j ∈ Mi 0, в противном случае (2.1) при условии: X b1ij ≤ ai . (2.2) j∈N Условие (2.2) означает, что число возможных связей ограничено для каждого игрока. Mi ⊆ N \i те игроки, которым игрок i ∈ N может предложить связь, значение ai ∈ {0, . . . , n − 1} равно максимальному числу связей игрока i. Если Mi = N \ {i} игрок i может предложить связь всем игрокам, и если ai = n − 1 игрок i может поддерживать любое число связей. Связь ij имеет место тогда и только тогда, когда b1ij = b1ji = 1. Обозначим через Ni (g) соседей игрока i в сети g, т.е. Ni (g) = {j ∈ N \ {i} : ij ∈ g}. Далее для краткости иногда будем писать Ni вместо Ni (g). После формирования сети игроки переходят на второй шаг z2 (g). 2.2 Характеристическая функция Определение: система Γ = (N, {Xi }i∈N , {Hi }i∈N ) называется бескоалиционной игрой в нормальной форме. • N = {1, 2, . . . , n} — множество игроков. 24

• xi ∈ Xi — стратегии i-го игрока. • x = (x1 , . . . , xn ) — ситуация в игре Γ. • Hi (x1 , . . . , xn ) — функция выигрыша i-го игрока. Определение: конечная бескоалиционная Γ = (N, X1 , X2 , H1 , H2 ) называется биматричной. игра двух лиц Определение: характеристической функцией игры n лиц будем называть вещественную функцию v, определенную на коалициях S ⊂ N , при этом для любых непересекающихся коалицийT , S (T ⊂ N , S ⊂ N ) выполняется неравенство (свойство супераддитивности) v(T ) + v(S) ≤ v(T ∪ S), v() = 0. Определение: под кооперативной игрой будем понимать пару (N, v), где N — множество игроков, v — характеристическая функция. На втором шаге игра представляет собой семейство попарных одновременных биматричных игр {γij } между соседями на сети. А именно, пусть i ∈ N, j ∈ Ni . Тогда i играет с j в биматричную игру γij с матрицами выигрышей Aij и Bji , игроков i и j, соответственно.  ij aij 11 a12  ij  a21 aij 22 Aij =  ..  ... .  ij aij m1 am2 apl > 0,  · · · aij 1k   · · · aij 2k  . . . ... ,  ij · · · amk bpl > 0,  ji bji 11 b12  ji  b21 bji 22 Bji =  ..  ... .  ji bji m1 bm2 p = 1, . . . , m,  · · · bji 1k   · · · bji 2k  . . . ... ,  ji · · · bmk l = 1, . . . , k. Обозначим через Γz2 подыгру игры Γ, которая происходит на шаге z2 . Рассмотрим эту игру в кооперативной форме. С этой целью определим характеристическую функцию для каждого подмножества (коалиции) S ⊂ N 25

как максиминное значение антагонистической игры двух лиц коалиции S и дополнительной коалиции N \ S, построенной на основе игры Γz2 , при этом выигрыш коалиции S определяется как сумма выигрышей игроков, входящих в S. Супераддитивность характеристической функции следует из ее определения. Обозначим через wij = max min aij p` , p = 1, . . . , m; ` = 1, . . . , k, (2.3) wji = max min bji p` , p = 1, . . . , m; ` = 1, . . . , k. (2.4) p ` p ` Теорема 1 Для каждой коалиции S ⊂ N , значение характеристической функции v(z2 ; S) определяется следующим образом: v(z2 ; {i}) = X wij , (2.5) j∈Ni v(z2 ; {i, j}) = max(aij p` p,l + bji p` ) + X X wir + r∈Ni \{j} wjq , i ∈ N, j ∈ N \ {i} q∈Nj \{i} (2.6) v(z2 ; S) = X X 1X X ji max(aij + b ) + wik , S ⊂ N, |S| > 2 p` p` p,` 2 i∈S j∈Ni ∩S i∈S k∈Ni \S (2.7) v(z2 ; N ) = 1XX ji max(aij p` + bp` ). p,` 2 (2.8) i∈N j∈Ni Рассмотрим кооперативную форму двухшаговой игры Γ. Следуя определению из главы 1, опредлим кооперативное поведение следующим образом. Предположим, что игроки выбирают стратегии ūi , i ∈ N которые максимизируют их суммарный выигрыш в игре Γ, т.e., X i∈N Ki (z1 ; ū1 , . . . , ūn ) = max u X Ki (z1 ; u1 , . . . , un ) i∈N Ситуацию ū = (ū1 , . . . , ūn ) будем называть кооперативным поведением, а соответствующую траекторию (z̄1 , z̄2 ) кооперативной траекторией. 26

Как и раньше, для коалиции S ⊆ N , мы определим характеристическую функцию v(z̄1 ; S) как максимин в антагонистической игре двух лиц коалиции S и дополнительной коалиции N \ S, где выигрыш коалиции S равен сумме выигрышей ее участников, и стратегия S это элемент декартова произведения множеств стратегий игроков, входящих в S. Имеет место следующая теорема: Теорема 2 В двухшаговой игре с попарным взаимодействием характеристическая функция имеет вид: v(z̄1 ; {i}) = 0, v(z̄1 ; ∅) = 0, ij v(z̄1 ; {i, j}) = max(aij p` + bp` ), p,` v(z̄1 ; S) = (2.9) i ∈ N, 1X X v(z̄1 ; {i, j}), 2 j ∈ N \ {i}, (2.10) S ⊂ N, (2.11) |S| > 2 i∈S j∈Ni ∩S v(z̄1 ; N ) = v(z̄2 ; N ). (2.12) Доказательство: Учитывая неотрицательность матрицы выигрышей, для игрока N \ S (минимизирующего), наилучшее поведение — это на первом шаге не создавать связей с коалицией S. Таким образом, все слагаемые wij , i ∈ S, j ∈ N \ S равны нулю, и характеристическая функция (5)-(8) принимает вид (9)-(12). 2.2.1 Пример построения характеристической функции Пусть n = 3 и сеть g имеет вид, как показано на рис. 1.

2 3 @ @ @

1 Рис.1 Сеть для 3 игроков и 3 ребер 27

Заданы матрицы: ! (4; 8) (3; 6) A12 B21 = , A13 B31 = (3; 3) (4; 4) A23 B32 = ! (4; 6) (2; 3) , (2; 2) (3; 5) ! (3; 5) (2; 3) (1; 4) (4; 6) Вычислим значения w12 = 3,5, w23 = 2,75, w13 = 3,75, w21 = 4, w31 = 4, w32 = 4,5. Таким образом, значения характеристической функции, вычисленные классическим способом, имеют вид 5 8 11 21 V (12) = max a12 + = 17 , + b pl pl + w13 + w23 = 12 + p,l 3 4 12 31 V (13) = max a13 + b pl pl + w12 + w32 = 10 + 3, 5 + 4, 5 = 18, p,l 32 V (23) = max a23 + b pl pl + w21 + w31 = 10 + 4 + 4 = 18, p,l V (1) = w12 + w13 = 3,5 + 3,75 = 7,25, V (2) = w21 + w23 = 4 + 2,75 = 6,75, V (3) = w31 + w32 = 4 + 4,5 = 8,5, 21 13 31 23 32 V (123) = max a12 pl + bpl + max apl + bpl + max apl + bpl = 32. p,l 2.3 p,l p,l Другой способ построения характеристической функции В кооперативной теории игр при построении принципов оптимальности важную роль играет понятие характеристической функции. В большинстве работ характеристическая функция вводится аксиоматически, как некото28

рая функция, определенная на множестве (подмножестве) игроков, обладающая определенными свойствами. Однако при исследовании динамических кооперативных игр необходимо анализировать изменение характеристической функции в процессе игры, что оказывается весьма затруднительно при ее неконструктивном задании, а именно, при задании аксиоматически. Как было показано ранее, значение характеристической функции для каждого подмножества игроков (коалиции) определялось как значение антагонистической игры между коалицией S (первый игрок) и коалицией N \S (втoрoй игрок), при этом под выигрышем кoалиции S понималась сумма выигрышей всех ее членов. Такой подход довольно сложен с вычислительной точки зрения, пoскoльку для вычисления всех значений характеристической функции неoбхoдимo рeшить 2N антагoнистичeских игр (N — количество игроков). В текущей главе предлагается иной подход к определению характеристической функции, который в вычислительном смысле проще, так как вместо решения антагонистической игры используется только операция максимизации. Большое внимание уделяется вопросу о сравнении характеристической функции, построенной классическим способом и новым, описанным в этой главе. В случае, когда игра Γ является сетевой игрой [24] с попарным взаимодействием, оба подхода приводят к одинаковому результату. Это оправдывает применение предложенного подхода в более общих случаях, когда число участников игры велико. Следуя [12], будем рассмотривать семейство антагонистических игр ΓN \{i},{i} , построенных на основе игры Γ между коалицией N \ {i}, действующей как первый игрок, и одиночной коалицией {i}, действующей как второй игрок. Выигрыш коалции N \ {i} полагаем равным сумме выигрышей игроков из этой коалиции. Пусть (µ̄N \{i} , µ̄i ) — ситуация равновесия в смешанных стратегиях в игре ΓN \i,i . Рассмотрим ситуацию µ̄ = (µ̄1 , . . . , µ̄n ) и определим W (S) = max µs X Ei (µS ; µ̄N \S ), (2.13) i∈S где µS = {µi , i ∈ S}, µ̄N \S = {µ̄i , i ∈ N \ S} и Ei (µS ; µ̄N \S ) — математическое ожидание выигрыша игрока i в ситуации (µs , µ̄N \S ). W (S) — это 29

максимальный выигрыш, который может обеспечить себе коалиция S, если остальные игроки используют стратегии второго, минимизирующего игрока в антагонистических играх ΓN \i,i . Рассмотрим подробнее вид функции W (S). Учитывая особенность попарного взаимодействия, можно выделить два типа ребер, по которым осуществляются игры с участием игроков из S: • рассмотрим ребро (i, j), i ∈ S, j ∈ S. Так как цель игроков в S — максимизация суммарного выигрыша, игроки i и j всегда могут это обеспечить, выбрав стратегии таким образом, чтобы получить максимальный ji суммарный выигрыш на этом ребре. Эта величина есть maxp,l (aij pl +bpl ). Коалиция N \ S никак не влияет на игру i с j; • рассмотрим ребро (i, j), i ∈ S, j ∈ N \ S. Максимальный выигрыш, который может себе гарантировать игрок i, когда игрок j использует стратегию µ̄j — это выигрыш в ситуации равновесия, т. е. значение игры wij . Таким образом, имеет место Теорема 3 В сетевой игре с попарным взаимодействием выполняется равенство: W (S) = V (S), S ⊂ N. 2.3.1 Пример построения харакетристической функции Найдем стратегии каждого игрока i = 1, 2, 3 в игре ΓN \i,i : µ1 = (µ12 ; µ13 ), µ2 = (µ21 ; µ23 ), µ3 = (µ31 ; µ32 ), где µ12 — стратегия игрока 1 в игре с игроком 2, µ13 — игрока 1 в игре с игроком 3 и т. д. Для нахождения этих стратегий решим соответствующие игры: µ1 = 1 1 0; 1; ; 2 2 , µ2 = 1 1 1 1 ; ; ; 2 2 2 2 30 , µ3 = 1 2 3 1 ; ; ; 3 3 4 4 .

Таким образом, получим следующие значения функции W (S): 21 W (12) = max(a12 pl + bpl ) + w13 + w23 = 12 + p,l 8 11 5 + = 17 , 3 4 12 31 W (13) = max(a13 pl + bpl ) + w12 + w32 = 10 + 3,5 + 4,5 = 18, p,l 32 W (23) = max(a23 pl + bpl ) + w21 + w31 = 10 + 4 + 4 = 18, p,l W (1) = w12 + w13 = 3,5 + 3,75 = 7,25, W (2) = w21 + w23 = 4 + 2,75 = 6,75, W (3) = w31 + w32 = 4 + 4,5 = 8,5, 21 13 31 23 32 W (123) = max(a12 pl + bpl ) + max(apl + bpl ) + max(apl + bpl ) = 32. p,l p,l p,l Можно заметить, что значения характеристической функции, построенной в параграфе (2.2) совпадают со значениями характеристической функции, в параграфе (2.3). Таким образом, установлено, что V (S) = W (S) для всех S N. 2.4 Выпуклость игры Игра в форме характеристической функции называется выпуклой, если для любых произвольных коалиций A ⊂ N и B ⊂ N выполняется следующее неравенство: v(A ∪ B) ≥ v(A) + v(B) − v(A ∩ B); A ⊂ N, B ⊂ N (2.14) Теорема 4 Подыгра Γz2 в форме характеристической функции (2.5)-(2.8) выпукла. Доказательство: докажем неравенство (2.14) для характеристической функции (2.5)-(2.8). Будем писать v(i) + v(j) вместо v(z2 ; {i}) + v(z2 ; {j}) для 31

ji сокращения записи. Обозначим так же через mij = maxp,l (aij p` +bp` ). Имеем: 1 X 1 X mij + (v(i) + v(j)) + 2 i,j∈A∪B 2 i,j∈A∪B v(A ∪ B) = j∈Ni i6=j j∈Ni i6=j X wik i∈A∪B k∈Ni \A∪B X 1X 1X v(A) = mij + (v(i) + v(j)) + wik 2 i,j∈A 2 i,j∈A j∈Ni i6=j v(B) = X X v(A ∩ B) = 1 X 1 X mij + (v(i) + v(j)) 2 2 (2.17) X (2.18) i,j∈B j∈Ni i6=j i∈B k∈Ni \B mij + i∈A∩B j∈A∩B i6=j j∈Ni (2.16) i∈A k∈Ni \A j∈Ni i6=j wik + (2.15) i,j∈B j∈Ni i6=j X wik + i∈A∩B k∈Ni \A∩B (v(i) + v(j)) i∈A∩B k∈Ni \A∩B Вычитая из (2.15) выражения (2.16),(2.17) и (2.18), получим: X i∈A∪B k∈Ni \A∪B wik − X i∈A\B k∈Ni \A X wik + X wik = i∈B\A k∈Ni \B wik ≥ 0 i∈A∩B k∈Ni \A∩B Последнее неравенство следует из неотрицательности выигрышей. Таким образом, неравенство (2.14) в игре Γz2 выполняется. Аналогичная теорема справедлива для случая двухшаговой игры. Теорема 5 Двухшаговая сетевая игра с попарным взаимодействием в форме характеристической функции (2.10)-(2.11) выпукла. Доказательство: для случая двухшаговой игры (2.10)-(2.11), имеем следующие выражения: v(A ∪ B) = 1 X mij 2 i,j∈A∪B j∈Ni i6=j 32 (2.19)

v(A) = 1X mij , 2 v(B) = i,j∈A j∈Ni i6=j 1 X mij 2 (2.20) i,j∈B j∈Ni i6=j v(A ∩ B) = X mij (2.21) i∈A∩B j∈A∩B i6=j j∈Ni Вычитая из (18) выражения (19) и (20), получаем: X 1 X 1X 1 X mij − mij − mij − mij = 0 2 2 2 i,j∈A∪B j∈Ni i6=j i,j∈A j∈Ni i6=j i,j∈B j∈Ni i6=j (2.22) i∈A∩B j∈A∩B i6=j j∈Ni Отсюда следует, что неравенство (13) для характеристической функции (9)-12) выполняется. Таким образом, построенная характеристическая функция удовлетворяет условию выпуклости игры. Это гарантирует непустоту С-ядра, и, принадлежность вектора Шепли С-ядру. 33

Глава 3 Решение сетевых игр с попарным взаимодействием: Вектор Шепли 3.1 Вектор Шепли для сети-звезда Определим дележ как вектор ξ[v] = (ξ1 [v], . . . , ξn [v]) который удовлетвоP ряет условиям коллективной рациональности, т.e., i∈N ξi [v] = v(·; N ) и индивидуальной рациональности, т.e., ξi [v] > v(·; {i}) для всех i ∈ N . Обозначим множество всех дележей в игре Γ через I(v). В качестве дележа возьмем вектор Шепли ϕ = (ϕ1 , . . . , ϕn ) где ϕi [v] = X S⊆N,i∈S (|S| − 1)!(n − |S|)! [v(S) − v(S \ {i})], n! i ∈ N. (3.1) Вичисление компонент вектора Шепли ϕ[v] — довольно трудная задача для большого количества игроков и случайной сети. Однако, для сетей особой структуры — сеть-звезда, — учитывая вид характеристической функции, удалось упростить формулу (3.1). Предположим следую34

щее: Mi = N \ {i} для i ∈ N и a1 = n − 1, ai = 1, i 6= 1. Кроме того, предположим, что maxj∈N wij = wi1 . Тогда, с целью максимизации суммарного выигрыша, игрокам следует выбирать следующие поведения на первом шаге — шаге формирования сети: b11 = (0, 1, . . . , 1) для игрока 1, и b1i = (1, 0, . . . , 0) для всех остальных игроков i 6= 1. Такое поведение формирует сеть-звезду на этом шаге (см. Рис. 2). В сети-звезда, |N1 | = n − 1 и |Ni | = 1, i 6= 1.

3 @ @ @

1 @ @

n ... Рис. 2 Сеть-звезда Для сети-звезда,характеристическая функция вычисляется с учетом особенностей такой структуры сети. Такая сеть имеет центральную симметрию, что позволяет предполагать, что формула (3.1) можеть быть приведена к более простому виду. Обозначим наименьшее общее кратное чисел n!/[(t − 1)!(n − t)!] для всех t = 1, . . . , n как R(n). Подставляя вышеуказанные обозначения, а так же формулы для характеристической функции, такие как (2.5), (2.10) в формулу (3.1), мы получаем следующие выражения для компонент вектора Шепли:     X  1   (m1j − v(·; {j})) , i = 1,  v(·; {1}) + 2 ϕi [v] = (3.2) j6=1   v(·; {1}) − (n − 1)w1i 1   , i 6= 1.  [m1i + v(·; {i}) − w1i ] + 2 R(n) Данное предположение является гипотезой, которую удалось проверить для сетевой игры с попарным взаимодействием общего вида (т.е. для случая, когда матрицы выигрышей различные) с количеством игроков |N | ≤ 5. Однако при большем количество игроков число слагаемых mij сильно 35

возрастает. Полное аналитическое доказательство этой гипотезы для произвольного количества игроков n является предметом будущих исследований. 36

3.2 Динамическая устойчивость вектора Шепли Перед началом игры Γ, игроки договариваются выбрать кооперативную (z̄1 , z̄2 ), то есть, такую траекторию, которая максимизирует суммарный выигрыш v(z̄1 ; N ). Мы предполагаем, что игроки будут разделять этот выигрыш в соответствии с ветором Шепли. Это означает, что в игре Γ каждый игрок i ∈ N ожидает получить прибыль, равную значению ϕi [v(z̄1 )]. Если игроки пересчитают вектор Шепли после первого шага (шага формирования сети), то есть на втором шаге, может оказаться, что пересчитанный вектор Шепли ϕ[v(z̄2 )] отличается от изначального. Это может привести к нарушению кооперативных соглашений и некотороые игроки могут отказаться от использования оптимальный стратегий. Будем говорить, что вектор Шепли в качестве дележа в двухшаговой игре Γ динамически устойчив, если ϕ[v(z̄1 )] = ϕ[v(z̄2 )] (так как игроки не получают выигрыша на шаге формирования сети), в противном случае будем называть вектор Шепли динамически неустойчивым. В общем случае игроки, следуя кооперативному соглашению, не ожидают, что кто-то может отклониться. Определение: Предположим, что ξ = {ξ1 , . . . , ξi , . . . , ξn } ∈ I(v). Всякая матрица β = {βik }, i = 1, . . . , n, k = 0, . . . , l, такая, что ξi = l X βik , βik ≥ 0, k=0 называется процедурой распределения дележа (ПРД). Чтобы предотвратить отклонение игроков от кооперативного соглашения, будем использовать процедуру распределения дележа (ПРД) β = {βi1 , βi2 }i∈N для вектора Шепли ϕ[v(z̄1 )] которая разделяет его между двумя шагами игры Γ [11]: ϕi [v(z̄1 )] = βi1 + βi2 для каждого i ∈ N . Здесь βi1 может быть интерпретирована как выплата игроку i на шаге формиро37

вания сети, и βi2 это его выплата на втором шаге игры, в соответствии с кооперативным соглашением. Будем говорить, что процедура распределения дележа β для вектора Шепли ϕ[v(z̄1 )] является динамически устойчивой процедурой распределения дележа [27] когда она задется следующим образом: βi1 = ϕi [v(z̄1 )] − ϕi [v(z̄2 )], βi2 = ϕi [v(z̄2 )], i ∈ N. (3.3) После введения динамически-устойчивой процедуры распределения дележа β для вектора Шепли ϕ[v(z̄1 )], игроки могут быть уверены, что никто из них не отклонится от кооперативного соглашения. Cледовательно, оно будет реализовано в игре Γ и каждый игрок i ∈ N получит ϕi [v(z̄1 )] как свою часть кооперативного выигрыша. Динамическая устойчивость некоторого принципа оптимальности M (z0 ) подразумевает [6], что для каждого дележа ξ ∈ M существует такая ПРД β, что если выплаты в каждой позиции z k на оптимальной траектории z будут сделаны игрокам в соответствии с ПРД β, то в каждой подыгре k Γz k игроки могут ожидать выплат ξ , которые являются оптимальными в подыгре Γz k в том же смысле, в каком они были оптимальными в исходной игре Γz0 . Сильная динамическая устойчивость означает, что если выплаты сделаны в соответствии с ПРД β, то, заработав на первых k шагах сумму β(k), игроки (если они ориентировались в подыгре Γz k на тот же принцип оптимальности, что и в Γz0 ), пересматривая оптимальный дележ в этой подыгре (заменяя один оптимальный дележ другим), все равно получат в результате в игре Γz0 выплаты в соответствии с некоторым дележом, оптимальным в предыдущем смысле, т. е. дележом, принадлежащим множеству M (z0 ). Ниже рассмотрим два примера, которые иллюстрируют что вектор Шепли, взятый в качестве дележа в двухшаговой кооперативной игре с попарным взаимодействием можеть быть как динамически устойчивым, так и неустойчивым. Первым приведем случай динамической устойчивости вектора Шепли на примере игры "Дилемма заключенного" 38

3.2.1 Дилемма заключенного "Дилемма заключённого"— фундаментальный парадокс в теории игр, согласно которому игроки, действуя рационально, не будут кооперироваться друг с другом, даже в том случае, если сотрудничество было бы в конечном итоге более выгодно. Модель предполагает, что игрок («заключённый») старается максимизировать свой собственный выигрыш, не ориентируясь на других игроков. Проблема впервые была обозначена Мерилом Фладом и Мелвином Дрешером в 1950 году. Название дилемме дал канадский математик Альберт Уильям Такер. Рассматривается игра двух лиц ("заключенных"). Их поймали одновременно и допрашивают независимо друг от друга, обвиняя в одном и том же преступлении. У кажого есть две возможных стратегии: "предать"и "молчать". В случае, если оба преступника молчат, они получают по 1 году тюрьмы. Если оба дают показания друг на друга, каждый получает 2 года тюрьмы. Если один из преступников хранит молчание, а другой дает показания на первого, то "предателя"отпускают, а "преданный"получает 3 года тюрьмы. В дилемме заключённого стратегия "предать"является строго доминирующей над стратегией "сотрудничать"("молчать"), поэтому единственное возможное в этих условиях равновесие — это предательство всех игроков. Иными словами, вне зависимости от поведения второго игрока, каждый выиграет больше, если будет использовать стратегию "предать". Поскольку в любой ситуации оказывается, что предать выгоднее, чем сотрудничать (молчать), все рациональные игроки будут выбирать предательство. Следуя по отдельности рациональному поведению, совместно игроки приходят к крайне нерациональному решению: если оба оказываются предателями, они получат суммарно меньший выигрыш, чем при кооперации (единственное равновесие в этой игре не является Парето-оптимальным решением). В этом и заключается дилемма. Рассмотрим случай, когда n игроков играют в одинаковую игру γ со 39

своими соседями по сети, т.e., Aij = A, Bij = B для всех i ∈ N , j ∈ Ni где A = BT = ! b a+b 0 , a 0 < a < b. Чтобы найти значение вектора Шепли ϕ[v(z̄2 )], для начала определим характеристическую функцию v(z̄2 ; S) для всех возможных коалиций S ⊆ N . Следуя (2.5), мы получаем следующие значения:   2b(n − 1),     2b(|S| − 1) + (n − |S|)a, v(z̄2 ; S) =  |S|a,     0, S S S S = N, ⊂ N, 1 ∈ S, ⊂ N, 1 ∈ / S, = ∅. Используя формулу компонент вектора Шепли (3.2), преобразованную для сети-звезда и, учитывая, что вектор Шепли удовлетворяет свойству симметрии, и что m1j = 2 для всех j ∈ N1 , получим: 1 [(n − 1)a + 2(n − 1) − (n − 1)a] = b(n − 1), 2 v(z̄2 ; N ) − ϕ1 [v(z̄2 )] = b, i 6= 1. ϕi [v(z̄2 )] = n−1 ϕ1 [v(z̄2 )] = Аналогично, чтобы найти компоненты вектора Шепли ϕ[v(z̄1 )], определим значения характеристической функции v(z̄1 ; S) для всех коалиций S ⊆ N . Следуя (2.10), имеем:    2b(n − 1), v(z̄1 ; S) = 2b(|S| − 1),   0, S = N, S ⊂ N, 1 ∈ S, S ⊂ N, 1 ∈ / S or S = ∅. Снова используя формулу для компонент вектора Шепли (3.2) преобразо- 40

ванную для сети-звезда, имеем следующие значения ϕ[v(z̄1 )] 1 [2(n − 1)] = b(n − 1), 2 v(z̄1 ; N ) − ϕ1 [v(z̄1 )] = b, ϕi [v(z̄1 )] = n−1 ϕ1 [v(z̄1 )] = i 6= 1. Сравнивая ϕ[v(z̄1 )] и ϕ[v(z̄2 )], оказывается, что они совпадают, что свидетельствует о динамической устойчивости вектора Шепли в данной задаче. 3.2.2 Динамически неустойчивый вектор Шепли В этом примере покажем динамическую неусточивость вектора Шепли в двухшаговой сетевой игре с попарным взаимодействием общего вида. Рассмотрим численным пример с множеством игроков N = {1, 2, 3, 4}. В данном примере сеть-звезда образуется в результате кооперативного соглашения между участниками. (см. Рис. 3). Пусть одновременные биматричные игры между игроками γ12 , γ13 и γ14 задаются следующими платежными матрицами: ! (A12 , B12 ) = (A14 , B14 ) = (2, 2) (3, 0) , (5, 1) (1, 2) ! (1, 3) (3, 2) . (6, 6) (4, 1) (A13 , B13 ) =

2 @ @ ! (3, 1) (4, 2) , (6, 2) (2, 3)

3 @

4 Рис. 3 Сеть-звезда Чтобы вычислить компоненты вектора Шепли ϕ[v(z̄1 )] и ϕ[v(z̄2 )], используем соответствующие формулы (2.5), (2.10) для характеристической 41

функции v(z̄2 ; ·) и v(z̄1 ; ·), соответственно, и преобразованную формулу компонент вектора Шепли (3.2). Таким образом, получаем w12 = 2, w21 = 1, m12 = 6, w13 = 3, w31 = 2, m13 = 8, w14 = 4, w41 = 3, m14 = 12, и значения харакетристической функции: v(z̄2 ; {1}) = 9, v(z̄1 ; {1}) = 0, v(z̄1 ; N ) = 26, v(z̄2 ; {2}) = 9, v(z̄2 ; {2}) = 0, v(z̄2 ; N ) = 26. v(z̄2 ; {3}) = 9, v(z̄1 ; {3}) = 0, v(z̄2 ; {4}) = 9, v(z̄1 ; {4}) = 0, Вектор Шепли иммеет следующий вид: ϕ[v(z̄1 )] = (13, 3, 4, 6), ϕ[v(z̄2 )] = (29/2, 33/12, 21/6, 63/12). Можно заметить, что вектор Шепли в двухшаговой игре ϕ[v(z̄1 )] отличается от вектора Шепли ϕ[v(z̄2 )] в одношаговой игре, начинающейся со второго шага. Это означает динамическую неустойчивость вектора Шепли. Например ϕ3 [v(z̄2 )] = 21/6 < ϕ3 [v(z̄1 )] = 4,игрок 3 может отклониться от кооперативного соглашения, так как его выигрыш меньше (Напомним, что игроки не получают никаких выигрышей на шаге формирования сети). Аналогичное выполняется для игрока 4: ϕ4 [v(z̄2 )] = 63/12 < ϕ4 [v(z̄1 )] = 6. Однако введение динамически устойчивой процедуры распределения дележа для вектора Шепли ϕ[v(z̄1 )] в течение двух этапов, определяемой формулой (3.3) получим β11 = −3/2, β12 = 29/2, β21 = 1/4, β22 = 33/12, β31 = 1/2, β32 = 21/6, β41 = 3/4, β42 = 63/12, и следовательно кооперативные соглашения будут сохраняться в течение всей игры. Таким образом, получение βi1 на первом шаге (шаг формирования сети) и βi2 на втором шаге (игровой шаг), игрок i ∈ N получит 42

ϕi [v(z̄1 )] на двух шагах, что соответствует кооперативному выигрышу игрока i, предписанного выбранным принципом оптимальности, т.е. вектором Шепли. 43

Глава 4 Решение сетевых игр с попарным взаимодействием: C-ядро Рассмотрим игру трех лиц и в качестве решения возьмем С-ядро. Определим множество дележей Mv в игре Γ как Mv = {x = (x1 , . . . , xn ) : n X xi = v(z1 ; N ), xi ≥ v(z1 ; {i}), i ∈ N } i=1 Определим так же ядро C(z̄) ⊂ Mv в игре Γ и предположим, что для каждого z1 , z2 , C(z̄) 6= ∅. С-ядро в игре Γ — это множество дележей x = (x1 , . . . , xn ), которые удовлетворяют следующим условиям X xi ≥ v(z̄1 ; S), S⊂N i∈S N X xi = v(z̄1 ; N ) (4.1) i=1 Для второго шага игры z2 имеем следующие значения характеристической 44

функции: v(z̄2 ; ∅) = 0, v(z̄2 ; {1}) = w13 + w12 , v(z̄2 ; {2}) = w21 + w23 , v(z̄2 ; {3}) = w31 + w32 21 v(z̄2 ; {12}) = max(a12 pl + bpl ) + w13 + w23 p,l 31 v(z̄2 ; {13}) = max(a13 pl + bpl ) + w12 + w32 p,l 32 v(z̄2 ; {23}) = max(a23 pl + bpl ) + w21 + w31 p,l 21 13 31 23 32 v(z̄2 ; N ) = max(a12 pl + bpl ) + max(apl + bpl ) + max(apl + bpl ) p,l p,l p,l Дележ x принадлежит C(z̄2 ), когда следующие неравенства выполняются:   x1 + x2 ≥ v(z̄2 ; {12})      x1 + x3 ≥ v(z̄2 ; {13})       x2 + x3 ≥ v(z̄2 ; {23}) x1 ≥ v(z̄2 ; {1})    x2 ≥ v(z̄2 ; {2})      x3 ≥ v(z̄2 ; {3})     x1 + x2 + x3 = v(z̄2 ; N ) (4.2) Подставляя значения харакетристической функции в неравенство (4.2), имеем  21  x1 + x2 ≥ max(a12  pl + bpl ) + w23 + w13  pl    x1 + x3 ≥ max(a13 + b31 ) + w12 + w32 pl pl pl (4.3) 23 32   x2 + x3 ≥ max(apl + bpl ) + w21 + w31   pl    x + x + x = v(z̄ ; N ) 1 2 3 45 2

Введем следующие обозначения для сокращения записи: 21 A12 = max(a12 pl + bpl ), pl D1 = w23 + w13 , 31 A13 = max(a13 pl + bpl ), pl D2 = w12 + w32 , 32 A23 = max(a23 pl + bpl ), pl D3 = w21 + w31 , Тогда система (4.3), определяющая вид ядра C(z̄2 ), построенного на основе характеристической функции, определенной в одношаговой игре, начинающейся со второго шага, может быть записана в следующем виде:   x1 + x2 ≥ A12 + D1     x +x ≥A +D 1 3 13 2 (4.4)  x + x ≥ A + D 2 3 23 3    x + x + x = v(z̄ ; N ) 1 2 3 2 Рассмотрим теперь ядро C(z¯1 ) двухшаговой игры Γ   x01 + x02 ≥ v(z̄1 ; {12})     x0 + x0 ≥ v(z̄ ; {13}) 1 1 3 0 0  x2 + x3 ≥ v(z̄1 ; {23})    x0 + x0 + x0 = v(z̄ ; N ) 1 1 2 3 (4.5) Подставляя значения харакетристической функции (2.10), имеем следующую систему:  21  x01 + x02 ≥ max(a12  pl + bpl )  pl    x01 + x03 ≥ max(a12 + b21 ) pl pl pl (4.6) 0 12 21 0   x + x ≥ max (a + b )  2 3 pl pl  pl    x0 + x0 + x0 = v(z̄ ; N )) 1 2 3 46 1

Переишем систему (4.6), используя вышеуказанные обозначения :       x01 + x02 ≥ A12 x01 + x03 ≥ A13  x02 + x03 ≥ A23    x0 + x0 + x0 = v(z̄ ; N ) 1 1 2 3 (4.7) В главе 1 мы доказали, что характеристическая функция в сетевых игрых с попарным взаимодействием обладает своейством выпуклости. Это справедливо как для одношаговой игры, так и для двухшаговой. Это гарантирует непустоту ядер (4.3) и (4.6). В следующем парагрефе мы исследуем вопрос о сильной динамической устойчивости С-ядра. 4.1 Сильная динамическая устойчивость С-ядра Необходимо привести следующие определения. Определение: Функция β i , i ∈ N это процедура распределения дележа (ПРД) для x ∈ Mv (см. [11]), если xi = β1i + β2i , i ∈ N. Определение: Ядро C(z1 ) является сильно-динамически устойчивым в игре Γ (см. [9]), если 1. C(z̄1 ) 6= ∅, C(z̄2 ) 6= ∅ 2. Для каждого дележа x ∈ C(z1 ) существует такая процедура распределения дележа β = (β1 , β2 ), что x = β1 + β2 и C(z̄1 ) ⊃ β1 ⊕ C(z̄2 ). Здесь символ ⊕ определяется следующим образом: для a ∈ Rn , B ⊂ Rn , 47

a ⊕ B = {a + b : b ∈ B}. В соответствии с формулой (4.3) имеем:  2 2 1 1  β1 + β2 + β1 + β2 ≥ A12 β11 + β21 + β13 + β23 ≥ A13   2 β1 + β22 + β13 + β23 ≥ A23 (4.8) Для сильной динамической устойчивости эти нераввеснвта должны удовлетворяться с учетом следующих дополнительных условий:  2 1  β2 + β2 ≥ A12 + D1 β21 + β23 ≥ A13 + D2   2 β2 + β23 ≥ A23 + D3 (4.9) Зафиксируем величину β1 , тогда для сильной динамической устойчивости мы должны иметь верные неравенства (4.9) для всех β2 . β2 должны удовлетворять неравенству (4.8). Так же из того, что v(z̄2 ; N ) = v(z̄1 ; N ) (на первом шаге формирования сети игроки не получают выигрышей), мы имеем, что β11 + β12 + β13 = 0. Если (4.8) выполняетс при минимальных значениях β21 , β22 , β23 из условий (4.9), тогда они так же выполняются и для других значений. Имеем:  3  −β1 + A12 + D1 ≥ A12 −β12 + A13 + D2 ≥ A13   1 −β1 + A23 + D3 ≥ A23 (4.10) Таким образом, мы получили условия для сильной динамичсекой устойчивости ядра C(z̄1 ) в двухшаговой кооперативной игре с попарным взаимодействием Γ. Сформулируем этот результат в виде теоремы. 48

Теорема 1. Предположим, что выполняются следующие условия:  3  β1 ≤ D1 β12 ≤ D2   1 β1 ≤ D3 (4.11) (существуеют такие β1 которые удовлетворяют (4.11)), тогда ядро C(z̄1 ) обладает свойством сильной динамической устойчивости. 4.2 Пример сильной динамической устойчивости ядра Проиллюстрируем условия сильной динамической устойчивости на примере игры трех лиц в случае, когда на первом шаге в качестве сети образовался полный граф, т.е. Ni = N \ {i} для всех i ∈ N . Для максимизации суммарного выигрыша игрокам следует составить полный граф, выбирая следующие поведения на первом шаге: b11 = (0; 1; 1), b12 = (1; 0; 1), b13 = (1; 1; 0) Имеем: 2 3 @ @ @ @ 1 Pис. 4 Сеть на втором шаге Вычислим значения харакетристической функции и найдем ядро. Следующие матрицы заданы изначально: ! ! (3; 5) (8; 7) (3; 3) (5; 4) A12 B21 = , A13 B31 = (6; 4) (5; 3) (6; 1) (2; 2) 49

A23 B32 = ! (4; 7) (5; 1) (2; 6) (3; 5) Максиминные значения: w13 =3, w23 =4, w12 =5, w32 =6, w21 =4, w31 =2 Значения параметров: D1 =6, D2 =11, D3 =6 A12 =maxp,l (a12 + b21 )=15 A13 =maxp,l (a13 + b31 )=11 A23 =maxp,l (a23 + b32 )=9 v(z̄1 ; {123}) = v(z̄2 ; {123})=35 Ядро C(z̄1 ) двухшаговой игры имеет вид:       x01 + x02 ≥ 15 x01 + x03 ≥ 11  x02 + x03 ≥ 9    x0 + x0 + x0 = 35 3 2 1 (4.12) Ядро C(z̄2 ) одношаговой игры, начинающейся со второго шага:       x1 + x2 ≥ 21 x1 + x3 ≥ 22  x2 + x3 ≥ 15    x + x + x = 35 1 2 3 (4.13) Возьмем некоторый вектор β1 который удовлетворяет условиям (4.10): β1 =(5; -10; 5). Подставляя его компоненты в систему (4.3) с учетом системы (4.6), получаем следующую систему неравенств:    5 − 10 + 21 ≥ 15 5 + 5 + 22 ≥ 11   −10 + 5 + 15 ≥ 9 50 (4.14)

И, окончательно,   16 ≥ 15 32 ≥ 11   10 ≥ 9 (4.15) Эти неравенства верны, и это означает, что ядро C(z̄1 ) обладает свойством сильной динамической устойчивости. 51

Заключение В данной работе рассмотрен особый класс динамических кооперативных игр, а именно — сетевые кооперативные игры с попарным взаимодействием. Термин «попарное» подразумевает взаимодействие игроков один на один, без посредников. Игру определяет геометрическая структура — сеть, вершинами которой являются сами игроки, а ребрами — связи между ними. По этим свзям осуществляются одновременные биматричные игры между «соседями» — участниками, расположенными на концевых вершинах одного и того же ребра. В ходе работы были получены следующие результаты: • Построена математическая модель сетевых игр с попарным взаимодействием. • Приведены два способа построения характеристической функции, каждый из которых приводит к одинаковому результату. Оба способа проиллюстрированы численными примерами. • Исследованы свойства характеристической функции в игре с попарным взаимодействием, в частности, доказана выпуклость игры в форме характеристической функции. • Исследованы методы решения кооперативных сетевых игр с попарным взаимодействием. • Для особого класса сетей (сеть-звезда) произведено преобразование формулы компонент вектора Шепли, существенно снижающее вычислительную сложность процесса поиска решения. • Рассмотрен вопрос о динамической устойчивости вектора Шепли на примере повторяющейся игры «Дилемма заключенного» и примере общего вида. В первом случае показана динамическая устойчивость вектора Шепли, во втором — неустойчивость, и способы преодоления этой трудности. 52

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

Литература [1] Булгакова M. A. , Петросян Л. A., "Кооперативные сетевые игры с попарным взаимодействием Математическая теория игр и ее приложения, т. 4, № 7, стр. 7-18, 2015. [2] Булгакова М.А., Петросян Л.А., "Сильно-динамически устойчивое ядро в многошаговой игре Constructive Nonsmooth Analysis and Related Topics / Конструктивный негладкий анализ и смежные вопросы Тезисы докладов международной конференции, посвященной памяти профессора В.Ф. Демьянова. 2017. С. 220-224. [3] Бурков В.Н. Теория графов в управлении организационными системами: учеб. пособие / В.Н. Бурков, А.Ю. Заложнев, Д.А. Новиков. — М.: Синтег, 2001. — 124 с. [4] Губко, М.В. Теория игр в управлении организационными системами: учеб. пособие / М.В. Губко, Д.А. Новиков. —2-е изд., перераб. и доп. — М.: Синтег., 2002 — 168 с. [5] Оуэн, Г. Теория игр / Пер. с англ. под ред. А.А.Корбута. — М.: Мир, 1971. — 230 с. [6] Петросян, Л.А. Игры поиска: учеб. пособие / Л.А. Петросян, А.Ю. Гарнаев. — СПб.: изд-во СПбГУ., 1992. — 216 с. [7] Петросян, Л.А. Теория игр: пособие для ун-тов / Л.А. Петросян, Н.А. Зенкевич, Е.А. Семина. — М.: Высш.шк., 1998. — 304 с. 54

[8] Петросян, Л.А. Теория игр: учебник / Л.А. Петросян, Н.А. Зенкевич, Е.В. Шевкопляс. — 2-е изд., перераб. и доп. — СПб.: БХВ-Петербург, 2012 — 432 с. [9] Петросян Л.A., Устойчивость решений в дифференциальных играх со многими участниками, Вестник Ленинградского Университета. Сер. 1. Математика, Механика, Астрономия, 19 (1977), 46–52 [10] Петросян Л.А., Седаков A.A., Бочкарев A.O., Двухшаговые сетевые игры, Математическая теория игр и ее приложения, 5:4 (2013), 84–104 [11] Петросян, Л. A., Данилов Н. Н.: Устойчивость решений неантагонистических игр с трансферабельной полезностью. Вестник Ленинградского Университета. Сер. 1. № 19. сс. 52-59 (1979) [12] Петросян Л. А., Панкратова Я. Б. Построение сильного равновесия по Нэшу в одном классе бесконечных неантагонистических игр // Труды института математики и механики УрО РАН. 2018. № 1. С. 165–174. [13] Печерский, С.Л. Кооперативные игры: решения и аксиомы / С.Л. Печерский, Е.Б. Яновская. — СПб.: Изд-во Европейского ун-та, 2004. — 459 с. [14] Робертс, Ф.С. Дискретные математические модели с приложениями к социальным, биологическим иэкономическим задачам / Пер. с англ. А.М. Раппопорта, С.И. Травкина. Под ред. А.И. Теймана. — М.: Наука. Гл.ред. физ.-мат. лит., 1986 — 496 с. [15] Acemoglua, D., Ozdaglarb, A., ParandehGheibib A. Spread of (mis)information in social networks"/ Games and Economic Behavior, Volume 70. Issue 2. pp. 194–227. (2010) [16] Boncinelli, L Stochastic Stability in Best Shot Network Games/ L. Boncinelli, P.Pin. — Pisa: Pisa Unoversity., — 2012. [17] Bulgakova, M. A., Petrosyan, L. A.: About Strongly Time-Consistency of Core in the Network Game with Pairwise Interactions. Proceedings of 2016 55

International Conference “Stability and Oscillations of Nonlinear Control Systems”. pp. 157-160. Moscow (2016) [18] Bulgakova M. A. and Petrosyan L. A., "The Shapley value for the network game with pairwise interactions"in Stability and Control Processes in Memory of V.I. Zubov (SCP), SPb, 2015, pp. 229-232. [19] Corbae D., Duffy J., “Experiments with network formation”, Games and Economic Behavior, 64 (2008), 81–120 [20] Driessen T.S.H., Funaki Y., Coincidence of and collinearity between game theoretic solutions, OR Spektrum, 13:1 (1991), 15–30 [21] Dyer, M. Mohanaraj, V. Pairwise-Interaction Games. ICALP, vol. 1, pp. 159-170. (2011) [22] Gao H., Petrosyan L., Qiao H., Sedakov A., “Cooperation in twostage games on undirected networks”, Journal of Systems Science and Complexity, 30:3 (2017), 680–693 [23] Goyal S., Vega-Redondo F., Network formation and social coordination, Games and Economic Behavior, 50 (2005), 178–207 [24] Jackson, M. Socisl and Economic Networks. / Princeton: Princeton University Press. 2008 [25] Jackson M., Watts A., On the formation of interaction networks in social coordination games, Games and Economic Behavior, 41:2 (2002), 265–291 [26] Kuhn H. W., Extensive games and the problem of information, Contributions to the Theory of Games II, eds. Kuhn H.W., Tucker A.W., Princeton, 1953, 193–216 [27] Petrosyan L., Sedakov A., “The Subgame-Consistent Shapley Value for Dynamic Network Games with Shock”, Dynamic Games and Applications, 6:4 (2016), 520–537 56

[28] Petrosyan L., Sedakov A., “Strategic support of cooperation in dynamic games on networks”, Proceedings of the International Conference on “Stability and Control Processes” in Memory of V.I. Zubov, SCP, 2015, 256–260 57

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв