Динамические сетевые игры тема диссертации и автореферата по ВАК РФ 01.01.09, доктор наук Седаков Артем Александрович

• Седаков Артем Александрович
• доктор наук
• 2020

Оглавление диссертации доктор наук Седаков Артем Александрович

1.1 Динамическая сетевая игра

1.2 Кооперация в динамической игре

1.2.1 Базовая некооперативная динамическая игра

1.2.2 Кооперативная динамическая игра

1.2.3 Динамическая устойчивость и сильная динамическая устойчивость

1.3 Сильная динамическая устойчивость с-ядра

1.3.1 Достаточные условия сильной динамической устойчивости с-ядра

1.3.2 Достаточные условия сильной динамической устойчивости процедуры распределения дележа из с-ядра

1.3.3 Связь сильной динамической устойчивости с-ядра c условием защиты от иррационального поведения и кооперативным регулирующим условием

1.4 Трансформация характеристической функции в кооперативных динамических играх

1.4.1 Модифицированная характеристическая функция

1.4.2 Сильная динамическая устойчивость процедур распределения дележа из модифицированных с-ядра и вектора Шепли

1.4.3 Сходимость итерационного процесса трансформации характеристической функции

1.4.4 Предельная характеристическая функция

1.4.5 Сильная динамическая устойчивость процедур распределения дележа из предельных с-ядра и вектора Шепли

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

с дисконтированием

1.6 Сильная динамическая устойчивость с-ядра в одном классе динамических

игр с дисконтированием

1.6.1 Модель динамической игры

1.6.2 Построение характеристической функции игры

1.6.3 Свойства характеристической функции

1.6.4 Сильная динамическая устойчивость с-ядра

1.6.5 Числовой пример

Заключение к главе

2 Кооперация в динамических сетевых играх

2.1 Двухшаговые сетевые игры

2.1.1 Формализация двухшаговой сетевой игры

2.1.2 Некооперативная двухшаговая сетевая игра

2.1.3 Двухшаговая сетевая игра с возможностью кооперации на втором шаге

2.1.4 Кооперативный вариант двухшаговой сетевой игры

2.1.5 Две прикладные модели кооперативных двухшаговых сетевых игр

2.1.6 Двухшаговые сетевые игры с попарным взаимодействием

2.1.7 Дележи в двухуровневых иерархических структурах

2.2 Формирование ориентированной сети в двухшаговой игре

2.2.1 Ключевые отличия от случая неориентированной сети

2.2.2 Кооперативный вариант двухшаговой сетевой игры для случая ориентированной сети

2.2.3 Двухшаговая сетевая игра с возможностью кооперации на втором шаге в случае ориентированной сети

2.3 Многошаговые сетевые игры

2.3.1 Формализация многошаговой сетевой игры

2.3.2 Кооперация в многошаговой сетевой игре

2.3.3 Стратегическая поддержка кооперации в многошаговой сетевой игре

2.3.4 Повторяющаяся сетевая игра и стратегическая поддержка кооперации

2.4 Многошаговые сетевые игры с шоком

2.4.1 Модель многошаговой сетевой игры с шоком

2.4.2 История и стратегии в многошаговой сетевой игре с шоком

2.4.3 Кооперация в многошаговой сетевой игре с шоком

2.4.4 Проблема позиционной состоятельности кооперативного решения

2.4.5 Числовой пример

2.4.6 Формулы явного представления значений характеристической функции и вектора Шепли

2.4.7 Альтернативный вариант многошаговой сетевой игры с шоком . . . 176 Заключение к главе

3 Консенсус и влияние в моделях социальных сетей

3.1 Динамика мнений и достижимость консенсуса в сети с двумя центрами влияния

3.1.1 Основная модель динамики мнений

3.1.2 Консенсус в сети с двумя центрами, не влияющими друг на друга напрямую

3.1.3 Консенсус в сети с двумя центрами, влияющими друг на друга напрямую

3.1.4 Консенсус в сети с двумя центрами, не влияющими друг на друга напрямую, и неоднородными агентами

3.2 Кооперация и равновесие в игре динамики мнений

3.2.1 Основная модель игры динамики мнений

3.2.2 Кооперативная ситуация в игре динамики мнений

3.2.3 Распределение кооперативного выигрыша

3.2.4 Построение характеристической функции для распределения кооперативного выигрыша

3.2.5 Равновесие по Нэшу

3.2.6 Цена анархии

3.2.7 Модификация модели: другой критерий

3.2.8 Оценка уровней доверия

3.2.9 Численное моделирование

Заключение к главе

4 Динамические игры с полной информацией на древовидных графах

4.1 Многошаговые сетевые игры с полной информацией

4.1.1 Формализация многошаговой сетевой игры с полной информацией

4.1.2 Построение ситуации абсолютного равновесия по Нэшу в многошаговой сетевой игре

4.1.3 Числовой пример

4.2 Решения многошаговых игр с ограниченной коммуникацией и полной информацией

4.2.1 Основные обозначения

4.2.2 Динамическое формирование коммуникационного графа: модель

4.2.3 Динамическое формирование коммуникационного графа: модель

4.2.4 Игра с главным игроком

4.2.5 Динамическое формирование коммуникационного графа в игре

с главным игроком: модель

4.2.6 Динамическое формирование коммуникационного графа в игре

с главным игроком: модель

4.3 Кооперация в многошаговых играх с интервальными выигрышами

4.3.1 Операции с замкнутыми интервалами

4.3.2 Интервальные динамические игры с полной информацией

4.3.3 Кооперативные интервальные динамические игры с полной информацией

4.3.4 Динамическая устойчивость аналога интервального вектора Шепли

4.3.5 Числовой пример

Заключение к главе

5 Кооперация и равновесие в динамических играх на деревьях событий

5.1 Линейная по переменной состояния динамическая игра на дереве событий

5.1.1 Основные обозначения и определения

5.1.2 Бинарное дерево событий с симметричными игроками

5.2 Решения

5.2.1 ^-адаптированное равновесие по Нэшу

5.2.2 Кооперация

5.3 Цена анархии

5.4 Модель управления вредными выбросами

5.4.1 Описание модели

5.4.2 Основные результаты

Заключение к главе

Заключение

Литература

Введение

Введение диссертации (часть автореферата) на тему «Динамические сетевые игры»

Актуальность темы исследования

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

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

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

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

Степень разработанности проблемы в литературе

Задачи, решаемые методами теории сетевых игр, можно условно разделить на три группы. К первой группе относятся стратегические некооперативные и кооперативные игровые модели, в которых игроками являются узлы сети, а ее ребра описываются структуру взаимодействия между игроками. В таких задачах основным предположением является стратегических характер игры, т. е. наличие у игроков возможности выбора своих стратегий, которые в совокупности определяют их выигрыши в игре. Подобные игры изучались в [30, 31, 74, 111, 125, 127, 162, 164, 168, 180, 257] для статических сетевых игр и в работах [56, 74, 120, 122, 140, 163, 240, 241, 260] при моделировании динамических игровых задач, в том числе при изучении в них вопросов кооперации [6, 38, 92, 242]. Существует ряд обзоров использования теории стратегических сетевых игр [16, 17, 18, 126]. Надо отметить, что сюда могут относиться как задачи с фиксированной конфигурацией сети, так и задачи ее выбора. Такие модели нашли свое применение в прикладных задачах, в частности, в задачах предоставления общественных благ [86, 87, 88], конкуренции и кооперации в олигополии [139], задачах экологического регулирования [2] и экономического роста [24, 25].

Ко второй группе задач, в которых используются методы теории сетевых игр, можно отнести стратегические некооперативные и кооперативные игровые модели, в которых игроки не являются узлами сети, а лишь принимают решение, будучи вовлеченными в управление некоторым объектом, описываемым сетью. В подавляющем большинстве случаев это игровые задачи, связанные с маршрутизацией или передачей данных в сети с заданной конфигурацией [20, 21, 22, 29, 53, 66, 67, 97, 100, 101], включая беспроводные сети [64, 65, 146, 193]. Сюда также можно отнести задачи управления, влияния, противоборства, распространения информации, достижимости консенсуса в социальных сетях [1, 5, 8, 14, 15, 39, 59, 77, 83, 91, 116, 137, 141].

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

возможна лишь при наличии между ними связи. Главная задача такой теории заключается в выработке методов распределения кооперативного выигрыша между игроками, принимая во внимание структуру связей между ними, задаваемых графом. Первым исследованием в этой области считается нахождение вектора Майерсона [197] путем распространение вектора Шепли [248] на игру с ограниченной кооперацией. Другие кооперативные решения игры были предложены в работах [28, 84, 85, 111, 155, 156, 161, 171], в которых аксиоматизированы решение усредненного дерева, правила равноправия и положения в сети и др., в том числе решения, основанные на двухуровневом распределении совместного выигрыша [79, 167, 169]. Надо отметить, что существуют также результаты применения решений игр с ограниченной кооперацией к динамическому поиску структуры графа связей [71].

Поскольку теория кооперативных динамических сетевых игр считается достаточно молодой, то по этой причине в литературе существует крайне мало результатов: для дифференциальных игр [2, 38] и динамических игр с попарным взаимодействием [6, 92]. При разработке теории динамических сетевых игр мы будем опираться на эти результаты. В то же время мы будем также опираться на уже полученные результаты теории кооперативных динамических игр. Поскольку известно, что кооперативное поведение может приносить игрокам больший выигрыш в сравнении с их выигрышем при некооперативном поведении, то основной акцент здесь будет сделан на выработку механизмов, стимулирующих кооперацию в динамических сетевых играх. Эти механизмы необходимы, поскольку кооперативное поведение в общем случае не является равновесным по Нэшу, и индивидуальное отклонение игрока, т. е. его отклонение от кооперативного соглашения, может привести к распаду кооперации. Для кооперативных динамических сетевых игры мы будем строить динамически устойчивые, сильно динамических устойчивые и позиционно состоятельные кооперативные решения, рассматриваемые в работах [12, 19, 34, 35, 36, 37, 40, 44, 181, 209, 214, 215, 233, 254, 255] для других классов кооперативных динамических игр. В зависимости от контекста динамическая устойчивость, сильная динамическая устойчивость или позиционная состоятельность кооперативного решения означает нецелесообразность игрокам пересматривать это решение с течением игры. Результаты, основанные на выполнение этих свойств, нашли свое применение в приложениях кооперативных динамических игр [174, 224, 265, 266, 267, 268]. В литературе рассматриваются механизмы сохранения кооперации на основе стратегической поддержки [33,41], которая делает кооперативную ситуацию некоторым равновесием по Нэшу с применением специальной процедуры распределения дележа вдоль кооперативной траектории. Другими механизмами сохранения кооперации являются методы защиты от иррационального поведения [264] в дополнении с кооперативным регулирующим условием [49], основанные на

отказе игроков от кооперации из-за непредвиденных обстоятельств.

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

Цели и задачи

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

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

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

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

решений приведен механизм стратегической поддержки кооперации в сетевых играх.

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

Научная новизна

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

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

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

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

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

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

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

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

Научные исследования, которые легли в основу материала диссертации были выполнены

при поддержке грантов Российского научного фонда (грант 17-11-01079 «Оптимальное поведение в конфликтно-управляемых системах»), Российского фонда фундаментальных исследований (гранты 17-51-53030 «Рациональность и устойчивость в играх на сетях», 16-0100713 «Игровые модели кооперации при структурных и информационных ограничениях», 14-01-31141 «Устойчивость коалиционных соглашений», 13-01-91160 «Кооперация в сетевых играх»), Санкт-Петербургского государственного университета (гранты Мероприятия 2: 9.38.245.2014 «Принципы оптимальности в динамических и дифференциальных играх с фиксированной и изменяющейся коалиционной структурой», 9.38.77.2011 «Кооперация в конфликтных управляемых системах со многими участниками»; гранты Мероприятия 5: 28013887, 9.41.731.2012, 9.41.1312.2016; грант Мероприятия 6: 9.42.1456.2015), проекта Shandong Province Double-Hundred Talent Plan (No. WST2017009) и финансовой поддержке исследовательского центра GERAD (2015 г.) и Китайской Академии наук (Visiting Fellowship Program of the Chinese Academy of Sciences for Outstanding Young Scientists в 2016 и 2017 гг.).

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

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

Личный вклад автора

Построена теория кооперативных двухшаговых сетевых игр, в которых на первом шаге игроки формируют сеть при ограничениях на допустимые связи, а на втором — могут ее «скорректировать» и выбрать некоторые действия. Автором установлено и показано, что при ряде предположений характеристическая функция согласно классическому ее определению является решением некоторой задачи максимизации, и предложены динамически устойчивые процедуры распределения вектора Шепли и т-вектора [46, 130, 218]. В [128] автором приведены достаточные условия сильной динамической устойчивости c-ядра для этого класса игр, а также определен класс кооперативных решений, обладающих свойством сильной динамической устойчивости. Эти результаты были адаптированы для двухшаго-вых сетевых игр с попарным взаимодействием, являющихся частным случаем двухшаго-

вых сетевых игр. Автором получено выражение вектора Шепли для сети типа «звезда» и исследована его динамическая устойчивость, а также (сильная) динамическая устойчивость с-ядра для игры «Дилемма заключенного» и координационной игры [216, 217]. Исследованы кооперативные модели предоставления общественных благ и рыночной конкуренции [242, 243, 244]. При заданной структуре связей в [221] автором построена схема двухуровневого распределения кооперативного выигрыша (в том числе и для случая попарного взаимодействия) и продемонстрировано ее отличие от классической одноуровневой схемы на основе вектора Шепли.

В [131, 220] при исследовании позиционной состоятельности вектора Шепли в кооперативной динамической сетевой игре с шоком автором проведена формализации игры, построена характеристическая функция игры и определен вид позиционно состоятельной процедуры распределения вектора Шепли. Стратегическая поддержка кооперативного соглашения в динамических сетевых играх предложена автором в [219].

Для кооперативных динамических игр с дискретным временем получены достаточные условия сильной динамической устойчивости с-ядра [52]. Эти условия далее сформулированы для одной динамической игры [245], имеющее важное прикладное значение, где автором найдены кооперативные стратегии игроков, построена характеристическая функция игры, исследованы ее свойства и приведены условия сильной динамической устойчивости с-ядра. Сильная динамическая устойчивость с-ядра в кооперативной динамической игре исследовалась и на основе некоторого преобразования характеристической функции [129, 223]. Так, автором доказана сходимость итерационного процесса преобразования характеристической функции, обеспечивающего сильную динамическую устойчивость с-ядра, найдена предельная характеристическая функция и исследованы ее свойства, на основе которых предложена сильная динамически устойчивая процедура распределения дележа из с-ядра.

Изучены модели влияния в социальных сетях. В предположении существования двух центров влияния в [7, 93] в рамках неуправляемой модели влияния автором найдены условия достижимости консенсуса или консенсуса большинства, и при их достижимости найдены предельные влияния участников социальной сети. При рассмотрении игровой модели с двумя центрами влияния найдено равновесие по Нэшу в классе позиционных стратегий [246]. Далее в [50] сделано обобщение модели влияния в социальной сети на случай нескольких игроков. Так, автором найдены кооперативные стратегии игроков, построена характеристическая функция игры как в классе программных, так и позиционных стратегий, которая позволяет определять кооперативные решения. Кроме того, построенная характеристическая функция позволяет найти и равновесие по Нэшу в игре.

В [45] автором формализована игра формирования сети как динамическая игра с полной информацией, разыгрываемая на древовидном графе. Для нее построена ситуация абсолютного равновесия по Нэшу. Этот подход использовался в работе [170] для двух динамических моделей формирования сети, где автором был проведен сравнительный анализ кооперативных правил распределения, основанных на векторе Шепли: вектора Майерсона, решения усредненного дерева и поощряющих центральность векторов Шепли и Майерсо-на, в том числе применительно к игре с главным игроком. Отдельно игра с главным игроком была исследована в [205, 206], где автором исследованы свойства этой игры, найдено явное представление вектора Майерсона и изучены его свойства. В работе [222], автором формализована кооперативная динамическая игра с полной информацией и интервальными выигрышами, разыгрываемая на древовидном графе, построена кооперативная (медианная) траектория, определена характеристическая функция игры и предложена динамически устойчивая процедура распределения медианного элемента интервального аналога вектора Шепли.

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

Положения, выносимые на защиту

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

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

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

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

цедуры распределения дележа из с-ядра, так и процедуры распределения дележа из с-ядра, построенного по предельной характеристической функции.

5. Нахождение равновесия по Нэшу, характеристической функции и кооперативного решения (вектора Шепли) в сетевой игре динамики мнений с дискретным временем. Определение условий достижимости консенсуса в модели динамики мнений в сети с двумя центрами влияния.

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

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

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

Все выносимые на защиту основные результаты получены автором диссертации самостоятельно.

Степень достоверности и апробация результатов

Основные результаты диссертации докладывались на семинарах кафедры математической теории игр и статистических решений Санкт-Петербургского государственного университета, семинарах Центра теории игр Санкт-Петербургского государственного университета, 30-й Европейской конференции по исследованию операций (Дублин, Ирландия, 2019 г.), Международных симпозиумах и семинарах по динамическим играм и приложениям (Падуя, Италия, 2011 г.; Бышице, Чехия, 2012 г.; Амстердам, Нидерланды, 2014 г.; Глазго, Великобритания, 2015 г.; Урбино, Италия, 2016 г.; Гренобль, Франция, 2018 г.), Международных конференциях «Теория игр и менеджмент» (Санкт-Петербург, Россия, 2009, 2010, 2012, 2013, 2016, 2018, 2019 гг.), Международных конференциях по теории сетевых игр (Сеул, Южная Корея, 2018 г.; Париж, Франция, 2019 г.), XIV Международной конференции «Устойчивость и колебания нелинейных систем управления» (Москва, Россия,

Список литературы диссертационного исследования доктор наук Седаков Артем Александрович, 2020 год

Литература

1. Барабанов И. Н., Коргин Н. А., Новиков Д. А., Чхартишвили А. Г. Динамические модели информационного управления в социальных сетях // Автоматика и телемеханика. 2010. № 11. С. 172-182.

2. Белицкая А. В., Петросян Л. А. Сетевая игра сокращения вредных выбросов в атмосферу // Математическая теория игр и ее приложения. 2012. T. 4. № 2. С. 3-13.

3. Берж К. Теория графов и ее применения. М: Изд-во иностранной литературы, 1962.

4. Болтянский В. Г. Оптимальное управление дискретными системами. М: Наука, 1973.

5. Бреер В. В., Новиков Д. А., Рогаткин А. Д. Управление толпой: математические модели порогового коллективного поведения. М: ЛЕНАНД, 2016.

6. Булгакова М. А., Петросян Л. А. Кооперативные сетевые игры с попарными взаимодействиями // Математическая теория игр и ее приложения. 2015. T. 7. № 4. С. 7-18.

7. Буре В. М., Парилина Е. М., Седаков А. А. Консенсус в социальной сети с двумя центрами влияния // Проблемы управления. 2016. № 1. С. 21-28; Bure V., Parilina E., Sedakov A. Consensus in a social network with two principals // Automation and Remote Control. 2017. Vol. 78. N. 8. P. 1489-1499.

8. Бурков В. Н., Кузнецов Н. А., Новиков Д. А. Механизмы управления в сетевых структурах // Автоматика и телемеханика. 2002. № 12. С. 96-115.

9. Васин А. А., Морозов В. В. Теория игр и модели математической экономики. М: Макс-пресс, 2005.

10. Вольф Д. А., Захаров В. В., Петросян О. Л. О существовании ПРД-ядра в дифференциальных кооперативных играх // Математическая теория игр и ее приложения. 2017. T. 9. № 4. С. 18-38.

11. Воробьев В. В., Врублевская И. Н. Позиционные игры (сб. статей под ред.). М: Наука, 1967.

12. Громова Е. В., Петросян Л. А. Сильно динамически устойчивое кооперативное решение в одной дифференциальной игре управления вредными выбросами // Управление большими системами. 2015. № 55. С. 140-159.

13. Громова Е. В., Петросян Л. А. Об одном способе построения характеристической функции в кооперативных дифференциальных играх // Математическая теория игр и ее приложения. 2015. Т. 7. № 4. С. 19-39.

14. Губанов Д. А., Новиков Д. А., Чхартишвили А. Г. Модели информационного влияния и информационного управления в социальных сетях // Проблемы управления. 2009. № 5. С. 28-35.

15. Губанов Д. А., Новиков Д. А., Чхартишвили А. Г. Социальные сети: модели информационного влияния, управления и противоборства. М: Физматлит, 2010.

16. Губко М. В. Управление организационными системами с сетевым взаимодействием агентов. I. Обзор теории сетевых игр // Автоматика и телемеханика. 2004. № 8. С. 115132.

17. Губко М. В. Управление организационными системами с сетевым взаимодействием агентов. II. Задачи стимулирования // Автоматика и телемеханика. 2004. № 9. С. 131148.

18. Губко М. В. Оптимальные иерархии управления для функций затрат, представимых в виде суммы однородных функций // Проблемы управления. 2009. № 3. С. 44-53.

19. Захаров В. В. О регуляризации и динамической устойчивости решений иерархических дифференциальных игр // Вестник Ленинградского университета. Серия 1: математика, механика, астрономия. 1988. № 2. С. 27-31.

20. Захаров В. В., Крылатов А. Ю. Системное равновесие транспортных потоков в мегаполисе и стратегии навигаторов: теоретико-игровой подход // Математическая теория игр и ее приложения. 2012. Т. 4. № 4. С. 23-44.

21. Захаров В. В., Крылатов А. Ю. Конкурентная маршрутизация транспортных потоков поставщиками услуг навигации // Управление большими системами. 2014. № 49. С. 129-147.

22. Карпов М. И., Петросян Л. А. Кооперативные решения в коммуникационных сетях // Вестник Санкт-Петербургского университета. Серия 10: прикладная математика, информатика, процессы управления. 2012. № 4. С. 37-45.

23. Кузютин Д. В., Петросян Л. А. Устойчивые решения позиционных игр. СПб: Издательский дом Санкт-Петербургского университета, 2008.

24. Матвеенко В. Д., Королев А. В. Равновесия в сетевой игре с производством и с экс-терналиями знаний // Математическая теория игр и ее приложения. 2016. Т. 8. № 1. С.106-137.

25. Матвеенко В. Д., Королев А. В. Типология сетей и равновесия в сетевой игре с производством и экстерналиями знаний // Математическая теория игр и ее приложения. 2017. Т. 9. № 3. С. 64-92.

26. Мазалов В. В., Дорофеева Ю. А., Коновальчикова Е. Н. Моделирование влияния среди участников образовательного коллектива // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2019. Т. 15. № 2. С. 259-273.

27. Мазалов В. В., Реттиева А. Н. Условия, стимулирующие рациональное поведение, в дискретных задачах управления биоресурсами // Доклады академии наук. 2010. Т. 432. № 3. С. 308-311.

28. Мазалов В. В., Трухина Л. И. Производящие функции и вектор Майерсона в коммуникационных сетях // Дискретная математика. 2014. Т. 26. № 3. С. 65-75.

29. Мазалов В. В., Чиркова Ю. В. Сетевые игры. СПб: Лань, 2018.

30. Новиков Д. А. Игры и сети // Математическая теория игр и ее приложения. 2010. Т. 2. № 1. С. 107-124.

31. Новиков Д. А. Теория управления организационными системами, 3-е изд. М: Физмат-лит, 2012.

32. Панкратова Я. Б. Решение кооперативной дифференциальной игры группового преследования // Дискретный анализ и исследование операций. 2010. Т. 17. № 2. С. 57-78.

33. Парилина Е. М. Устойчивая кооперация в стохастических играх // Математическая теория игр и ее приложения. 2010. Т. 2. № 3. С. 21-40.

34. Парилина Е. М., Петросян Л. А. Сильно позиционно состоятельное с-ядро в стохастических играх // Математическая теория игр и ее приложения. 2017. Т. 9. № 2. С. 39-61.

35. Петросян Л. А. Устойчивость решений дифференциальных игр со многими участниками // Вестник Ленинградского университета. Серия 1: математика, механика, астрономия. 1977. № 19. С. 46-52.

36. Петросян Л. А. Построение сильно-динамически устойчивых решений в кооперативных дифференциальных играх // Вестник Ленинградского университета. Серия 1: математика, механика, астрономия. 1992. № 2. С. 33-38.

37. Петросян Л. А. Сильно динамически устойчивые дифференциальные принципы оптимальности // Вестник Ленинградского университета. Серия 1: математика, механика, астрономия. 1993. № 4. С. 35-40.

38. Петросян Л. А. Кооперативные дифференциальные игры на сетях // Труды Института математики и механики УрО РАН. 2010. Т. 16. № 5. С. 143-150.

39. Петросян Л. А. Одна транспортная теоретико-игровая модель на сети // Математическая теория игр и ее приложения. 2011. T. 3. № 4. С. 89-98.

40. Петросян Л. А., Данилов Н. Н. Устойчивость решений неантагонистических дифференциальных игр с трансферабельными выигрышами // Вестник Ленинградского университета. Серия 1: математика, механика, астрономия. 1979. № 1. С. 52-59.

41. Петросян Л. А., Зенкевич Н. А. Принципы устойчивой кооперации // Математическая теория игр и ее приложения. 2009. T. 1. № 1. С. 106-123.

42. Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр: учебник, 2-е изд. СПб: БХВ-Петербург, 2012.

43. Петросян Л. А., Мамкина С. И. Игры с переменным коалиционным разбиением // Вестник Санкт-Петербургского университета. Серия 1: Математика, механика, астрономия. 2004. № 3. С. 60-69.

44. Петросян Л. А. Панкратова Я. Б. Построение сильно-динамически устойчивых подъ-ядер в дифференциальных играх с предписанной продолжительностью // Труды Института математики и механики УрО РАН. 2017. T. 23. № 1. С. 219-227.

45. Петросян Л. А., Седаков А. А. Многошаговые сетевые игры с полной информацией // Математическая теория игр и ее приложения. 2009. T. 1. № 2. С. 66-81; Petrosyan L. A., Sedakov A. A. Multistage network games with perfect information // Automation and Remote Control. 2014. Vol. 75. N. 8. P. 1532-1540.

46. Петросян Л. А., Седаков А. А., Бочкарев А. О. Двухступенчатые сетевые игры // Математическая теория игр и ее приложения. 2013. T. 5. № 4. С. 84-104; Petrosyan L. A., Sedakov A. A., Bochkarev A. O. Two-stage network games // Automation and Remote Control. 2016. Vol. 77. N. 10. P. 1855-1866.

47. Петросян О. Л., Громова Е. В., Погожев С. В. О сильно динамически устойчивом подмножестве c-ядра в кооперативных дифференциальных играх с предписанной продолжительностью // Математическая теория игр и ее приложения. 2016. T. 8. № 4. С. 79-106.

48. Печерский C. Л., Яновская Е. Б. Кооперативные игры: решения и аксиомы. СПб: Изд-во Европейского университета в Санкт-Петербурге, 2004.

49. Реттиева А. Н. Кооперативное регулирующее условие в задаче разделения биоресурсов // Математическая теория игр и ее приложения. 2009. T. 1. № 3. С. 71-86.

50. Рогов М. А., Седаков А. А. Согласованное влияние на мнения участников социальной сети // Математическая теория игр и ее приложения. 2018. T. 10. № 4. С. 30-58.

51. Севастьянов Б. А. Курс теории вероятностей и математической статистики, 2-е изд. М: Наука, 2004.

52. Седаков А. А. О сильной динамической устойчивости c-ядра // Математическая теория игр и ее приложения. 2015. T. 7. № 2. С. 69-84; Sedakov A. A. On the Strong Time Consistency of the Core // Automation and Remote Control. 2018. Vol. 79. N. 4. P. 757-767.

53. Серяков И. А. Теоретико-игровая транспортная задача на сети с заданными пропускными способностями // Математическая теория игр и ее приложения. 2012. T. 4. № 3. С.101-116.

54. Соболев А. И. О функциональных уравнениях, задающих выигрыши игроков в игре n лиц // Успехи теории игр: Труды II Всесоюзной конференции по теории игр (под ред. Э. Вилкаса). Вильнюс: МИНТИС, 1973. С. 151-153.

55. Чеботарев П. Ю., Агаев Р. П. Об асимптотике в моделях консенсуса // Управление большими системами. 2013. № 43. С. 55-77.

56. Abouheaf M. I., Lewis F. L., Vamvoudakis K. G., Haesaert S., Babuska R. Multi-agent discrete-time graphical games and reinforcement learning solutions // Automatica. 2014. Vol. 50. N. 12. P. 3038-3053.

57. Abreu D., Dutta P., Smith L. The Folk theorem for repeated games: a NEU condition // Econometrica. 1994. Vol. 62. P. 939-948.

58. Acemoglu D., Ozdaglar A. Competition in Parallel-Serial Networks // IEEE Journal on Selected Areas in Communications. 2007. Vol. 25. N. 6. P. 1180-1192.

59. Acemoglu D., Ozdaglar A. Opinion dynamics and learning in social networks // Dynamic Games and Applications. 2011. Vol. 1. N. 1. P. 3-49.

60. Allouch N., King M. Constrained public goods in networks // Journal of Public Economic Theory. 2019. Vol. 21. P. 895-902.

61. Alparslan Gok S. Z. On the interval Shapley value // Optimization. 2014. Vol. 63. N. 5. P. 747-755.

62. Alparslan Gok S. Z., Branzei R., Tijs S. The interval Shapley value: an axiomatization // Central European Journal of Operations Research. 2010. Vol. 18. P. 131-140.

63. Alparslan Gok S. Z., Miquel S., Tijs S. Cooperation under interval uncertainty // Mathematical Methods of Operations Research. 2009. Vol. 69. P. 99-109.

64. Altman E., Avrachenkov K., Garnaev A. Fair resource allocation in wireless networks in the presence of a jammer // Performance Evaluation. 2010. Vol. 67. P. 338-349.

65. Altman E., Avrachenkov K., Garnaev A. Jamming in Wireless Networks Under Uncertainty // Mobile Networks and Applications. 2011. Vol. 16. N. 2. P. 246-254.

66. Altman E., Ba§ar T., Jiménez T., Shimkin N.. Competitive routing in networks with polynomial costs // IEEE Transactions on Automatic Control. 2002. Vol. 47. N. 1. P. 92-96.

67

68

69

70

71

72.

73.

74

75.

76

77

78

79

80

81

Altman E., Wynter L. Equilibrium, Games, and Pricing in Transportation and Telecommunication Networks // Networks and Spatial Economics. 2004. Vol. 4. N. 1. P. 7-21. Anshelevich E., Dasgupta A., Kleinberg J., Tardos E., Wexler T., Roughgarden T. The price of stability for network design with fair cost allocation // In: 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004. P. 59-73.

Aumann R. Acceptable points in general cooperative n-person games // In: Tucker L. (ed.) Contributions to the theory of games IV, Annals of Mathematics Studies 40, 1959. P. 287324.

Aumann R. The core of a cooperative game without side payments // Transactions of the American Mathematical Society. 1961. Vol. 98. P. 539-552.

Aumann R., Myerson R. Endogenous Formation of Links Between Players and Coalitions: An Application of the Shapley Value // In: Roth A. (ed.) The Shapley Value: Essays in Honor of Lloyd S. Shapley, Cambridge University Press, 1988. P. 175-191. Aumann R., Shapley L. Long-Term Competition—A Game-Theoretic Analysis // In: Me-giddo N. (ed.) Essays in Game Theory. In Honor of Michael Maschler. Springer-Verlag, 1994. P. 1-15.

Avrachenkov K., Elias J., Martignon F., Neglia G., Petrosyan L. Cooperative network design: A Nash bargaining solution approach // Computer Networks. 2015. Vol. 83. N. 4. P. 265-279.

Bala V., Goyal S. A non-cooperative model of network formation // Econometrica. 2000. Vol. 68. N. 5. P. 1181-1231.

Ba§ar T., Olsder G. J. Dynamic Noncooperative Game Theory, 2nd edition. USA: Academic Press, 1999.

Ba§ar T., Zhu Q. Price of Anarchy, Information, and Cooperation in Differential Games // Dynamic Games and Applications. 2011. Vol. 1. N. 1. P. 50-73.

Bauso D., Cannon M. Consensus in opinion dynamics as a repeated game // Automatica. 2018. Vol. 90. P. 204-211.

Bellman R. Dynamic Programming. Princeton: Princeton University Press, 1957. Béal S., Khmelnitskaya A., Solal P. Two-step values for games with two-level communication structure // Journal of Combinatorial Optimization. 2018. Vol. 35. N. 2. P. 563-587. Billand P., Bravard C., Durieu J., Sarangi S. Firm heterogeneity and the pattern of R&D collaborations // Economic Inquiry. 2019. Vol. 57. N. 4. P. 1896-1914. Bilo V., Fanelli A., Flammini M., Moscardelli L. Graphical Congestion Games // Algorith-mica. 2011. Vol. 61. N. 2. P. 274-297.

82. Bindel D., Kleinberg J., Oren S. How bad is forming your own opinion? // Games and Economic Behavior. 2015. Vol. 92. P. 248-265.

83. Bolouki S., Nedic A., Ba§ar T. Social Networks // In: Ba§ar T., Zaccour G. (eds.) Handbook of Dynamic Game Theory. Cham: Springer, 2018.

84. Borkotokey S., Kumar R., Sarangi S. A solution concept for network games: The role of multilateral interactions // European Journal of Operational Research. 2015. Vol. 243. P. 912-920.

85. Borm P., Owen G., Tijs S. On the position value for communication situations // SIAM Journal on Discrete Mathematics. 1992. Vol. 5. N. 3. P. 305-320.

86. Bramoulle Y. Anti-coordination and social interactions // Games and Economic Behavior. 2007. Vol. 58. P. 30-49.

87. Bramoulle Y., Kranton R. Public goods in networks // Journal of Economic Theory. 2007. Vol. 135. N. 1. P. 478-494.

88. Bramoulle Y., Kranton R., D'Amours M. Strategic Interaction and Networks // American Economic Review. 2014. Vol. 104. N. 3. P. 898-930.

89. Branzei R., Dimitrov D., Pickl S., Tijs S. How to cope with division problems under interval uncertainty of claims // International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems. 2004. Vol. 12. P. 191-200.

90. Branzei R., Dimitrov D., Tijs S. Shapley-like values for interval bankruptcy games // Economics Bulletin. 2003. Vol. 3. P. 1-8.

91. Buechel B., Hellmann T., KloBner S. Opinion dynamics and wisdom under conformity // Journal of Economic Dynamics and Control. 2015. Vol. 52. P. 240-257.

92. Bulgakova M., Petrosyan L. About strongly time-consistency of core in the network game with pairwise interactions // In: Tkhai V. N. (ed.) Proceedings of 2016 International Conference Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiy's Conference), 2016. 4 p.

93. Bure V., Parilina E., Sedakov A. Consensus in social networks with heterogeneous agents and two centers of influence // In: Petrosyan L. A., Zhabko A. P. (eds.) Proceedings of the 2015 International Conference Stability and Control Processes in Memory of V. I. Zubov (SCP), 2015. P. 233-236.

94. Calvo E., Rubio S. J. Dynamic models of international environmental agreements: A differential game approach // International Review of Environmental and Resource Economics. 2012. Vol. 6. N. 4. P. 289-339.

95. Chander P., Tulkens H. A core of an economy with multilateral environmental externalities // International Journal of Game Theory. 1997. Vol. 26. P. 379-401.

96. Chen J., Gao Z., Zhao Q. Load-aware dynamic spectrum access in ultra-dense small cell networks // Proceedings of the 2015 International Conference on Wireless Communications and Signal Processing (WCSP), 2015. 5 P.

97. Cole R., Dodis Y., Roughgarden T. How much can taxes help selfish routing? // Journal of Computer and System Sciences. 2006. Vol. 72. P. 444-467.

98. Contreras J., Gross G., Arroyo J. M., Muñoz J. I. An incentive-based mechanism for transmission asset investment// Decision Support Systems. 2009. Vol. 47. P. 22-31.

99. Corbae D., Duffy J. Experiments with network formation // Games and Economic Behavior. 2008. Vol. 64. P. 81-120.

100. Correa J. R., Schulz A. S., Stier Moses N. E. Selfish Routing in Capacitated Networks // Mathematics of Operations Research. 2004. Vol. 29. N. 4. P. 961-976.

101. Correa J. R., Schulz A. S., Stier Moses N. E. Fast, Fair and Efficient Flows in Networks // Operations Research. 2007. Vol. 55. N. 2. P. 215-225.

102. Davis M., Maschler M. The kernel of cooperative games // Naval Research Logistics Quarterly. 1965. Vol. 12. P. 223-259.

103. DeGroot M. H. Reaching a Consensus // Journal of the American Statistical Association. 1974. Vol. 69. N. 345. P. 118-121.

104. Demange G. On group stability in hierarchies and networks // Journal of Political Economy. 2004. Vol. 112. P. 754-778.

105. Dockner E., J0rgensen S., Long N. V., Sorger G. Differential Games in Economics and Management Science. Cambridge: Cambridge University Press, 2000.

106. Doob J. L. Stochastic Processes. New York: John Wiley and Sons, Inc., 1990.

107. Drechsel J., Kimms A. Computing core allocations in cooperative games with an application to cooperative procurement // International Journal of Production Economics. 2010. Vol. 128. P. 310-321.

108. Driessen T. S. H. A survey of consistency properties in cooperative game theory // SIAM Review. 1991. Vol. 33. P. 43-59.

109. Driessen T. S. H., Funaki Y. Coincidence of and collinearity between game theoretic solutions // OR Spektrum. 1991. Vol. 13. N. 1. P. 15-30.

110. Driessen T. S. H., Meinhardt H. I. Convexity of oligopoly games without transferable technologies // Mathematical Social Sciences. 2005. Vol. 50. P. 102-126.

111. Dutta B., van den Nouweland A., Tijs S. Link formation in cooperative situations // International Journal of Game Theory. 1998. Vol. 27. P. 245-256.

112. Dyer M., Mohanaraj V. Pairwise-Interaction Games // In: Aceto L., Henzinger M., Sgall J. (eds.) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science. Vol. 6755, 2011. P. 159-170.

113. Elkind E., Goldberg L. A., Goldberg P. Nash equilibria in graphical games on trees revisited // In: Feigenbaum J., Chuang J., Pennock D. M. (eds.) Proceedings of the 7th ACM conference on Electronic commerce, 2006. P. 100-109.

114. Epstein L., van Stee R. The price of anarchy on uniformly related machines revisited // Information and Computation. 2012. Vol. 212. P. 37-54.

115. Etesami S. R., Ba§ar T. Game-theoretic analysis of the Hegselmann-Krause model for opinion dynamics in finite dimensions // IEEE Transactions on Automatic Control. 2015. Vol. 60. N. 7. P. 1886-1897.

116. Etesami S. R., Ba§ar T. Network Games // In: Ba§ar T., Zaccour G. (eds.) Handbook of Dynamic Game Theory. Cham: Springer, 2018.

117. Farahat A., Perakis G. A Comparison of Bertrand and Cournot Profits in Oligopolies with Differentiated Product// Operations Research. 2011. Vol. 59. N. 2. P. 507-513.

118. Farahat A., Perakis G. On the efficiency of price competition // Operations Research Letters. 2011. Vol. 39. N. 6. P. 414-418.

119. Feri F. Stochastic stability in networks with decay // Journal of Economic Theory. 2007. Vol. 135. P. 442-457.

120. Feri F., Melendez-Jimenez M. Coordination in evolving networks with endogenous decay // Journal of Evolutionary Economics. 2013. Vol. 23. P. 955-1000.

121. Fershtman C. Identification of Classes of Differential Games for Which the Open Loop Is a Degenerate Feedback Nash Equilibrium // Journal of Optimization Theory and Applications. 1987. Vol. 55. N. 2. P. 217-231.

122. Fosco C., Mengel F. Cooperation through imitation and exclusion in networks // Journal of Economic Dynamics & Control. 2011. Vol. 35. P. 641-658.

123. Freeman L. C. Centrality in Social Networks Conceptual Clarification // Social Networks. 1978. Vol. 1. N. 3. P. 215-239.

124. Friedkin N. E., Johnsen E. C. Social influence and opinions // Journal of Mathematical Sociology. 1990. Vol. 15. N. 3-4. P. 193-206.

125. Galeotti A., Goyal S. The Law of the Few // The American Economic Review. 2010. Vol. 100. N. 4. P. 1468-1492.

126. Galeotti A., Goyal S., Jackson M. O., Vega-Redondo F., Yariv L. Network Games // The Review of Economic Studies. 2010. Vol. 77. N. 1. P. 218-244.

127. Galeotti A., Goyal S., Kamphorst J. Network formation with heterogeneous players // Games and Economic Behavior. 2006. Vol. 54. P. 353-372.

128. Gao H., Petrosyan L., Qiao H., Sedakov A. Cooperation in two-stage games on undirected networks // Journal of Systems Science and Complexity. 2017. Vol. 30. N. 3. P. 680-693.

129. Gao H., Petrosyan L., Qiao H., Sedakov A., Xu G. Transformation of Characteristic Function in Dynamic Games // Journal of Systems Science and Information. 2013. Vol. 1. N. 1. P. 22-37.

130. Gao H., Petrosyan L., Sedakov A. Strongly Time-consistent Solutions for Two-stage Network Games // Procedia Computer Science. 2014. Vol. 31. P. 255-264.

131. Gao H., Petrosyan L., Sedakov A. Dynamic Shapley value for repeated network games with shock // Control and Decision Conference (CCDC), 2015 27th Chinese, 2015. P. 64496455.

132. Genc T., Reynolds S.S., Sen S. Dynamic oligopolistic games under uncertainty: A stochastic programming approach // Journal of Economic Dynamics & Control. 2007. Vol. 31. N. 1. P. 55-80.

133. Germain M., Toint P., Tulkens H., de Zeeuw A. Transfers to sustain dynamic core-theoretic cooperation in international stock pollutant control // Journal of Economic Dynamics and Control. 2003. Vol. 28. N. 1. P. 79-99.

134. Germain M., Tulkens H., Magnus A. Dynamic core-theoretic cooperation in a two-dimensional international environmental model // Mathematical Social Sciences. 2010. Vol. 59. P. 208-226.

135. Ghaderi J., Srikant R. Opinion dynamics in social networks with stubborn agents: Equilibrium and convergence rate // Automatica. 2014. Vol. 50. N. 12. P. 3209-3215.

136. Gillies D. B. Solutions to general non-zero-sum games // In: Tucker A. W., Luce R. D. (eds.) Contributions to the Theory of Games IV, Annals of Mathematics Studies 40. Princeton: Princeton University Press, 1959. P. 47-85.

137. Golub B., Jackson M. O. Naive learning in social networks and the wisdom of crowds // American Economic Journal: Microeconomics. 2010. Vol. 2. N. 1. P. 112-49.

138. Goyal S. Connections: An Introduction to the Economics of Networks. Princeton: Princeton University Press, 2007.

139. Goyal S., Joshi S. Networks of collaboration in oligopoly // Games and Economic Behavior. 2003. Vol. 43. N. 1. P. 57-85.

140. Goyal S., Vega-Redondo F. Network formation and social coordination // Games and Economic Behavior. 2005. Vol. 50. P. 178-207.

141. Grabisch M., Rusinowska A. A model of influence based on aggregation functions // Mathematical Social Sciences. 2013. Vol. 66. P. 316-330.

142. Gromova E. The Shapley Value as a Sustainable Cooperative Solution in Differential Games of Three Players // In: Petrosyan L. A., Mazalov V. V. (eds.) Recent Advances in Game Theory and Applications. Static & Dynamic Game Theory: Foundations & Applications. Basel: Birkhäuser, 2016. P. 67-89.

143. Haller H. Network extension // Mathematical Social Sciences. 2012. Vol. 64. P. 166-172.

144. Hamiache G. Associated consistency and Shapley value // International Journal of Game Theory. 2001. Vol. 30. P. 279-289.

145. Hamiache G. A matrix approach to the associated consistency with an application to the Shapley value // International Game Theory Review. 2010. Vol. 12. N. 2. P. 175-187.

146. Han Z., Niyato D., Saad W., Ba§ar T., Hj0rungnes A. Game theory in wireless and communication networks: Theory, models, and applications. Cambridge: Cambridge University Press, 2011.

147. Han W., Sun H., Xu G. A new approach of cooperative interval games: The interval core and Shapley value // Operations Research Letters. 2012. Vol. 40. P. 462-468.

148. Hart S., Mas-Colell A. Potential, value, and consistency // Econometrica. 1989. Vol. 57. P. 589-614.

149. Haurie A., Krawczyk J., Zaccour G. Games and dynamic games. Singapore: World Scientific, 2012.

150. Haurie A., Zaccour G. S-Adapted Equilibria in Games Played over Event Trees: An Overview // In: Nowak A. S., Szajowski K. (eds.) Advances in Dynamic Games. Annals of the International Society of Dynamic Games, Vol. 7. Boston: Birkhäuser, 2005. P 417-444.

151. Haurie A., Zaccour G., Smeers Y. Stochastic equilibrium programming for dynamic oligopolistic markets // Journal of Optimization Theory and Applications. 1990. Vol. 66. N. 2. P. 243-253.

152. Haviv M., Ravner L. Strategic timing of arrivals to a finite queue multi-server loss system // Queueing Systems. 2015. Vol. 81. N. 1. P. 71-96.

153. Haviv M., Roughgarden T. The price of anarchy in an exponential multi-server // Operations Research Letters. 2007. Vol. 35. P. 421-426.

154. Hegselmann R., Krause U. Opinion dynamics and bounded confidence models, analysis, and simulation // Journal of Artificial Societies and Social Simulation. 2002. Vol. 5. N. 3.

155. Herings P. J. J., van der Laan G., Talman A. J. J. The average tree solution for cycle-free graph games // Games and Economic Behavior. 2008. Vol. 62. P. 77-92.

156. Herings P. J. J., van der Laan G., Talman A. J. J., Yang Z. The average tree solution for cooperative games with communication structure // Games and Economic Behavior. 2010. Vol. 68. P. 626-633.

157. Heuvel W. van den, Borm P., Hamers H. Economic lot-sizing games // European Journal of Operational Research. 2007. Vol. 176. N. 2. P. 1117-1130.

158. Hwang Y. A., Chen M. C. A new axiomatization of the Shapley value under uncertainty // Economics Bulletin. 2012. Vol. 32. P. 799-810.

159. Immorlica N., Markakis E., Piliouras G. Coalition formation and price of anarchy in Cournot oligopolies // Lecture Notes in Computer Science. 2010. Vol. 6484. P. 270-281.

160. Ingene C. A., Taboubi S., Zaccour G. Game-Theoretic Coordination Mechanisms in Distribution Channels: Integration and Extensions for Models Without Competition // Journal of Retailing. 2012. Vol. 88. N. 4. P. 476-496.

161. Jackson M. Allocation rules for network games // Games and Economic Behavior. 2005. Vol. 51. N. 1. P. 128-154.

162. Jackson M. O. Social and Economic Networks. Princeton: Princeton University Press, 2008.

163. Jackson M., Watts A. On the formation of interaction networks in social coordination games // Games and Economic Behavior. 2002. Vol. 41. N. 2. P. 265-291.

164. Jackson M. O., Wolinsky A. A Strategic Model of Social and Economic Networks // Journal of Economic Theory. 1996. Vol. 71. P. 44-74.

165. J0rgensen S. A dynamic game of waste management // Journal of Economic Dynamics & Control. 2010. Vol. 34. N. 2. P. 258-265.

166. J0rgensen S., Martín-Herrán G., Zaccour G. Dynamic Games in the Economics and Management of Pollution // Environmental Modeling and Assessment. 2010. Vol. 15. N. 6. P. 433-467.

167. Kamijo Y. A two-step Shapley value for cooperative games with coalition structures // International Game Theory Review. 2009. Vol. 11. N. 2. P. 207-214.

168. Kearns M., Littman M. L., Singh S. Graphical models for game theory // In: Breese J., Koller D. (eds.) Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers Inc., 2001. P. 253-260.

169. Khmelnitskaya A. Values for games with two-level communication structures // Discrete Applied Mathematics. 2014. Vol. 166. P. 34-50.

170. Khmelnitskaya A., Parilina E., Sedakov A. Endogenous formation of cooperation structure in TU games // In: Petrosyan L., Mazalov V., Zenkevich N. (eds.) Frontiers of Dynamic

Games. Static & Dynamic Game Theory: Foundations & Applications. Cham: Birkhäuser, 2019. P. 49-64.

171. Khmelnitskaya A. B., van der Laan G., Talman A. J. J. Centrality rewarding Shapley and Myerson values for undirected graph games // Memorandum 2057. Department of Applied Mathematics, University of Twente, 2016.

172. Kimms A., Kozeletskyi I. Core-based cost allocation in the cooperative traveling salesman problem // European Journal of Operational Research. 2016. Vol. 248. N. 3. P. 910-916.

173. Koller D., Milch B. Multi-agent influence diagrams for representing and solving games // Games and Economic Behavior. 2003. Vol. 45. N. 1. P. 181-221.

174. Koutsougeras L. C. A two-stage core with applications to asset market and differential information economies // Economic Theory. 1998. Vol. 11. P. 563-584.

175. Koutsoupias E., Papadimitriou C. H. Worst-case equilibria // In: Meinel C., Tison S. (eds.) STACS 99. STACS 1999. Lecture Notes in Computer Science, Vol. 1563. Berlin: Springer, 1999. P. 404-413.

176. Kranich L., Perea A., Peters H. Core concepts for dynamic TU games // International Game Theory Review. 2005. Vol. 7. N. 1. P. 43-61.

177. Krawczyk J. B., Tidball M. A discrete-time dynamic game of seasonal water allocation // Journal of Optimization Theory and Applications. 2006. Vol. 128. N. 2. P. 411-429.

178. Kuhn H. W. Extensive games and the problem of information // In: Kuhn H. W., Tucker A. W. (eds.) Contributions to the theory of games II. Princeton: Princeton University Press, 1953. P. 193-216.

179. Kwon O. H., Tarashnina S. On a time-consistent solution of a cooperative differential timeoptimal pursuit game // Journal of the Korean Mathematical Society. 2002. Vol. 39. N. 5. P. 745-764.

180. La Mura P. Game networks // In: Boutilier C., Goldszmidt M. (eds.) Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers Inc., 2000. P. 335-342.

181. Lehrer E., Scarsini M. On the Core of Dynamic Cooperative Games // Dynamic Games and Applications. 2013. Vol. 3. N. 3. P. 359-373.

182. Liao Y. H. Alternative axiomatizations of the Shapley value under interval uncertainty // International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems. 2012. Vol. 20. N. 4. P. 619-628.

183. Lin N. Foundations of social research. New York: McGraw-Hill, 1976.

184. Long N. V. Applications of dynamic games to global and transboundary environmental issues: A review of the literature // Strategic Behavior and the Environment. 2012. Vol. 2. N. 1. P. 1-59.

185. Martín-Herrán G., Zaccour G. Credibility of Incentive Equilibrium Strategies in LinearState Differential Games // Journal of Optimization Theory and Applications. 2005. Vol. 126. N. 2. P. 367-389.

186. Martínez-De-Albéniz V., Roels G. Competing for shelf space // Production and Operations Management. 2011. Vol. 20. N. 1. P. 32-46.

187. Martínez-De-Albéniz V., Simchi-Levi D. Competition in the supply option market // Operations Research. 2009. Vol. 57. N. 5. P. 1082-1097.

188. Maschler M., Solan E., Zamir S. Game Theory. Cambridge: Cambridge University Press, 2013.

189. Mazalov V., Parilina E. Game of Competition for Opinion with Two Centers of Influence // In: Khachay M., Kochetov Y., Pardalos P. (eds.) Mathematical Optimization Theory and Operations Research. MOTOR 2019. Lecture Notes in Computer Science, Vol. 11548. Springer, 2019. P. 673-684.

190. Meng F., Chen X., Tan C. Cooperative fuzzy games with interval characteristic functions // Operational Research. 2016. Vol. 16. N. 1. P. 1-24.

191. Meng F., Liu F. The interval Shapley value for type-2 interval games // Research Journal of Applied Sciences, Engineering and Technology. 2012. Vol 4. N. 10. P. 1334-1342.

192. Meng F., Zhang Q., Wang Y. Cooperative fuzzy games with a coalition structure and interval payoffs // International Journal of Computational Intelligence Systems. 2013. Vol. 6. N. 3. P. 548-558.

193. Meshkati F., Poor H. V., Schwartz S. C. Energy-Efficient Resource Allocation in Wireless Networks // IEEE Signal Processing Magazine. 2007. Vol. 24. N. 3. P. 58-68.

194. Moore R. Methods and applications of interval analysis. Philadelphia: SIAM, 1979.

195. Moulin H. Axioms of cooperative decision making. Cambridge: Cambridge University Press, 1988.

196. Muto S., Nakayama M., Potters J. A. M., Tijs S. H. On big boss games // The Economic Studies Quarterly. 1988. Vol. 39. N. 4. P. 303-321.

197. Myerson R. Graphs and cooperation in games // Mathematics of Operations Research. 1977. Vol. 2. P. 225-229.

198. Myerson R. Game Theory: Analysis of Conflict. Cambridge: Harvard University Press, 1997.

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

Nash J. Equilibrium points in «-person games // Proceedings of the National Academy of Sciences. 1950. Vol. 36. N. 1. P. 48-49.

Nash J. Non-Cooperative Games // The Annals of Mathematics. 1951. Vol. 54. N. 2. P. 286-295.

Niazi M. U. B., Ozguler A. B., Yildiz A. Consensus as a Nash Equilibrium of a Dynamic Game // Proceedings of the 12th International Conference on Signal Image Technology and Internet-based Systems (SITIS), 2016. P. 365-372.

Norde H., Pham Do K. H., Tijs T. Oligopoly games with and without transferable technologies // Mathematical Social Sciences. 2010. Vol. 43. P. 187-207. Owen G. Game Theory. Monterey, CA: Emerald Group Publishing Limited, 2013. Pandit P., Kulkarni A. A. Refinement of the equilibrium of public goods games over networks: Efficiency and effort of specialized equilibria // Journal of Mathematical Economics. 2018. Vol. 79. P. 125-139.

Parilina E., Sedakov A. Stable cooperation in graph-restricted games // Contributions to Game Theory and Management. 2014. Vol. 7. P. 271-281.

Parilina E., Sedakov A. Stable Cooperation in a Game with a Major Player // International Game Theory Review. 2016. Vol. 18. N. 2, Art.No. 1640005.

Parilina E., Sedakov A., Zaccour G. Price of Anarchy in a Linear-State Stochastic Dynamic Game // European Journal of Operational Research. 2017. Vol. 258. P. 790-800. Parilina E., Zaccour G. Approximated cooperative equilibria for games played over event trees // Operations Research Letters. 2015. Vol. 43. N. 5. P. 507-513. Parilina E., Zaccour G. Node-consistent core for games played over event trees // Automatica. 2015. Vol. 53. P. 304-311.

Parilina E. M., Zaccour, G. Node-Consistent Shapley Value for Games Played over Event Trees with Random Terminal Time // Journal of Optimization Theory and Applications. 2017. Vol. 175. N. 1. P. 236-254.

Perakis G., Roels G. The price of anarchy in supply chains: Quantifying the efficiency of price-only contracts // Management Science. 2007. Vol. 53. N. 8. P. 1249-1268. Perakis G., Sun W. Price of anarchy for supply chains with partial positive externalities // Operations Research Letters. 2012. Vol. 40. N. 2. P. 78-83.

Petrosjan L. A. The time consistency of the optimality principles in non-zero sum differential games // In: Hamalainen P. R., Ehtamo H. K. (eds.) Dynamic Games in Economic Analysis, Vol. 157, Lecture Notes in Control and Information Sciences, 1991. P. 299-311.

214. Petrosjan L. A. Cooperative differential games // In: Nowak A. S., Szajowski K. (eds.) Advances in Dynamic Games. Annals of the International Society of Dynamic Games. Vol. 7. Boston: Birkhäuser, 2005. P. 183-200.

215. Petrosjan L. A. Cooperative stochastic games // In: Haurie A., Muto S., Petrosjan L. A., Raghavan T. E. S. (eds.) Advances in Dynamic Games. Annals of the International Society of Dynamic Games. Vol. 8. Boston: Birkhäuser, 2006, P. 52-59.

216. Petrosyan L., Bulgakova M., Sedakov A. Time-Consistent Solutions for Two-Stage Network Games with Pairwise Interactions // Mobile Networks and Applications. 2018. P. 1-10. https://doi.org/10.1007/s11036-018-1127-7.

217. Petrosyan L., Bulgakova M., Sedakov A. The Time-Consistent Shapley Value for Two-Stage Network Games with Pairwise Interactions // In: Song J., Li H., Coupechoux M. (eds) Game Theory for Networking Applications. EAI/Springer Innovations in Communication and Computing. Springer, 2019. P. 15-23.

218. Petrosyan L., Sedakov A. One-way flow two-stage network games // Vestnik Sankt-Peterburgskogo Universiteta. Seriya 10: Prikladnaya Matematika, Informatika, Protsessy Upravleniya. 2014. N. 4. P. 72-81.

219. Petrosyan L., Sedakov A. Strategic support of cooperation in dynamic games on networks // In: Petrosyan L. A., Zhabko A. P. (eds.) Proceedings of the 2015 International Conference Stability and Control Processes in Memory of V. I. Zubov (SCP), 2015. P. 256-260.

220. Petrosyan L., Sedakov A. The Subgame-Consistent Shapley Value for Dynamic Network Games with Shock // Dynamic Games and Applications. 2016. Vol. 6. N. 4. P. 520-537.

221. Petrosyan L., Sedakov A. Two-Level Cooperation in Network Games // In: Avrachenkov K., Huang L., Marden J., Coupechoux M., Giovanidis A. (eds.) Game Theory for Networks. GameNets 2019. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, Vol. 277. Springer, 2019. P. 71-81.

222. Petrosyan L., Sedakov A., Sun H., Xu G. Time consistency of the interval Shapley-like value in dynamic games // Journal of Intelligent & Fuzzy Systems. 2016. Vol. 30. N. 4. P. 1965-1972.

223. Petrosyan L., Sedakov A., Sun H., Xu G. Convergence of strong time-consistent payment schemes in dynamic games // Applied Mathematics and Computation. 2017. Vol. 315. P. 96-112.

224. Petrosjan L., Zaccour G. Time-consistent Shapley value allocation of pollution cost reduction // Journal of Economic Dynamics and Control. 2003. Vol. 27. N. 3. P. 381-398.

225. Petrosyan L. A., Zenkevich N. A. Game Theory. Singapore: World Scientific Publishing Company, 2016.

226. Pineau P. O., Murto P. An oligopolistic investment model of the Finnish electricity market // Annals of Operations Research. 2003. Vol. 121. P. 123-148.

227. Pineau P. O., Rasata H., Zaccour G. Impact of some parameters on investments in oligopolistic electricity markets // European Journal of Operational Research. 2011. Vol. 213. N. 1. P. 180-195.

228. Predtetchinski A. The strong sequential core for stationary cooperative games // Games and Economic Behavior. 2007. Vol. 61. P. 50-66.

229. Predtetchinski A., Herings P. J. J., Peters H. The strong sequential core for two-period economies // Journal of Mathematical Economics. 2002. Vol. 38. P. 465-482.

230. Predtetchinski A., Herings P. J. J., Peters H. The strong sequential core in a dynamic exchange economy // Economic Theory. 2004. Vol. 24. P. 147-162.

231. Rajan R. Endogenous Coalition Formation in Cooperative Oligopolies // International Economic Review. 1989. Vol. 30. N. 4. P. 863-876.

232. Ravner L., Haviv M. Equilibrium and socially optimal arrivals to a single server loss system // In: International Conference on NETwork Games Control and Optimization: NetG-Coop'14. Trento, Italy, 2014.

233. Reddy P. V., Shevkoplyas E., Zaccour G. Time-consistent Shapley value for games played over event trees // Automatica. 2013. Vol. 49. N. 6. P. 1521-1527.

234. Rosen J. B. Existence and uniqueness of equilibrium points for concave n-person games // Econometrica. 1965. Vol. 33. N. 3. P. 520-534.

235. Rosenthal E. C. Shortest path games // European Journal of Operational Research. 2013. Vol. 224. N. 1. P. 132-140.

236. Roughgarden T. Selfish Routing and the Price of Anarchy. MIT Press, 2005.

237. Roughgarden T., Schoppmann F. Local smoothness and the price of anarchy in splittable congestion games // Journal of Economic Theory. 2015. N. 156. P. 317-342.

238. Roughgarden T., Tardos E. How Bad is Selfish Routing? // Journal of the ACM. 2002. Vol. 49. N. 2. P. 236-259.

239. Sabidussi G. The centrality index of a graph // Psychometrika. 1966. Vol. 31. N. 4. P. 581603.

240. Salehisadaghiani F., Pavel L. Distributed Nash equilibrium seeking: A gossip-based algorithm // Automatica. 2016. Vol. 72. P. 209-216.

241. Salehisadaghiani F., Pavel L. Distributed Nash equilibrium seeking in networked graphical games // Automatica. 2018. Vol. 87. P. 17-24.

242. Sedakov A. Network Formation in Competition Model // Contributions to Game Theory and Management. 2012. Vol. 5. P. 286-292.

243. Sedakov A. Characteristic Functions in a Linear Oligopoly TU Game // In: Petrosyan L., Mazalov V., Zenkevich N. (eds.) Frontiers of Dynamic Games. Static & Dynamic Game Theory: Foundations & Applications. Cham: Birkhäuser, 2018. P. 219-235.

244. Sedakov A. Characteristic function and time consistency for two-stage games with network externalities //Mathematics. 2020. Vol. 8. N. 1. 38.

245. Sedakov A., Qiao H. Strong time-consistent core for a class of linear-state games // Journal of Systems Science and Complexity. 2019. (accepted for publication)

246. Sedakov A. A., Zhen M. Opinion dynamics game in a social network with two influence nodes // Vestnik Sankt-Peterburgskogo Universiteta. Prikladnaya Matematika. Informatika. Protsessy Upravleniya. 2019. Vol. 15. N. 1. P. 118-125.

247. Selten R. Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit // Zeitschrift für die Gesamte Staatswissenschaft. 1965. Vol. 121. P. 301-324, 667-689.

248. Shapley L. A value for n-person games // In: Kuhn H. W., Tucker A. W. (eds.) Contributions to the theory of games II. Princeton: Princeton University Press, 1953. P. 307-317.

249. Shapley L. Cores of convex games // International Journal of Game Theory. 1971. Vol. 1. N. 1. P. 11-26.

250. Starr A. W., Ho Y. C. Further Properties of Nonzero-Sum Differential Games // Journal of Optimization Theory and Applications. 1969. Vol. 3. N. 4. P. 207-219.

251. Thomson W. Consistent allocation rules // RCER Working Paper 418, University of Rochester, 1996.

252. Tijs S. Bounds for the core of a game and the T-value // In: Moeschlin O., Pallaschke D. (eds.) Game Theory and Mathematical Economics. Amsterdam: North-Holland Publishing Company, 1981. P. 123-132.

253. Tijs S. An axiomatization of the T-value // Mathematical Social Sciences. 1987. Vol. 13. N. 2. P. 177-181.

254. Toriello A., Uhan N. A. Dynamic cost allocation for economic lot sizing games // Operations Research Letters. 2014. Vol. 42. N. 1. P. 82-84.

255. Toriello A., Uhan N. A. Dynamic linear programming games with risk-averse players // Mathematical Programming. 2017. Vol. 163. N. 1. P. 25-56.

256. Valqui Vidal R. V. On the Sufficiency of the Linear Maximum Principle for Discrete-Time Control Problems // Journal of Optimization Theory and Applications. 1987. Vol. 54. N. 3. P. 583-589.

257. Vega-Redondo F. Complex Social Networks. Cambridge: Cambridge University Press, 2007.

258. Von Neumann J., Morgenstern O. Theory of Games and Economic Behavior. Princeton: Princeton University Press, 1944.

259. Watts A. A dynamic model of network formation // Games and Economic Behavior. 2001. Vol. 34. P. 331-341.

260. Xie F., Cui W., Lin J. Prisoners dilemma game on adaptive networks under limited foresight//Complexity. 2013. Vol. 18. P. 38-47.

261. Xu G., Driessen T. S. H., Sun H. Matrix analysis for associated consistency in cooperative game theory // Linear Algebra and its Applications. 2008. Vol. 428. P. 1571-1586.

262. Xu G., van den Brink R., van der Laan G., Sun H. Associated consistency characterization of two linear values for TU games by matrix approach // Linear Algebra and its Applications. 2015. Vol. 471. P. 224-240.

263. Xu N., Veinott A. F. Sequential stochastic core of a cooperative stochastic programming game // Operations Research Letters. 2013. Vol. 41. N. 5. P. 430-435.

264. Yeung D. W. K. An Irrational-Behavior-Proof Condition in Cooperative Differential Games // International Game Theory Review. 2006. Vol. 8. N. 4. P. 739-744.

265. Yeung D. W. K. Dynamically consistent collaborative environmental management with production technique choices // Annals of Operations Research. 2014. Vol. 220. N. 1. P. 181204.

266. Yeung D. W. K., Petrosyan L. A. Subgame Consistent Economic Optimization: An Advanced Cooperative Dynamic Game Analysis. Basel: Birkhäuser, 2012.

267. Yeung D. W. K., Petrosyan L. A. Subgame-consistent cooperative solutions in randomly furcating stochastic dynamic games // Mathematical and Computer Modelling. 2013. Vol. 57. N. 3-4. P. 976-991.

268. Yeung D. W. K., Petrosyan L. A. Subgame Consistent Cooperation A Comprehensive Treatise. Singapore: Springer, 2016.

269. Zaccour G. Théorie des jeux et marchés énergétiques: marché européen de gaz naturel et é changes d'électricité // Ph.D. Thesis, HEC Montréal, 1987.

270. Zachary W. W. An Information Flow Model for Conflict and Fission in Small Groups // Journal of Anthropological Research. 1977. Vol. 33. N. 4. P. 452-473.

271. Zhang J. Tipping and Residential Segregation: A Unified Schelling Model // Journal of Regional Science. 2011. Vol. 51. N. 1. P. 167-193.

272. Zhao J. A necessary and sufficient condition for the convexity in oligopoly games // Mathematical Social Sciences. 1999. Vol. 37. P. 189-204.

273. Zhen M. Stackelberg equilibrium of opinion dynamics game in social network with two influence nodes // Contributions to Game Theory and Management. 2019. Vol. 12. P. 366386.

274. Zheng J., Cai Y., Chen X., Li R., Zhang H. Optimal base station sleeping in green cellular networks: A distributed cooperative framework based on game theory // IEEE Transactions on Wireless Communications. 2015. Vol. 14. N. 8. P. 4391-4406.

275. Zyskowski M., Zhu Q. Price and Variance of Anarchy in Mean-Variance Cost Density-Shaping Stochastic Differential Games // In: Proceedings of the 52nd IEEE Conference on Decision and Control, December 10-13, Florence, Italy, 2013.

Saint Petersburg State University

Printed as a manuscript

Artem Aleksandrovich Sedakov

Dynamic network games

Specialization

01.01.09 Discrete Mathematics and Mathematical Cybernetics

Thesis

submitted in conformity with the requirements for the degree of Doctor of Physico-Mathematical Sciences

Translation from Russian

Scientific consultant:

Doctor of Physico-Mathematical Sciences Professor Leon Aganesovich Petrosyan

Saint Petersburg 2020

Contents

Introduction 322

1 Time-consistent cooperative solutions for dynamic network games 333

1.1 Dynamic network game............................................................338

1.2 Cooperation in dynamic games....................................................341

1.2.1 Noncooperative dynamic game............................................341

1.2.2 Cooperative dynamic game................................................343

1.2.3 Time consistency and strong time consistency............................346

1.3 Strong time consistency of the core................................................350

1.3.1 Sufficient conditions for the strong time consistency of the core .... 350

1.3.2 Sufficient conditions for the strong time consistency of the imputation distribution procedure for a core imputation..............................353

1.3.3 The relationship between the strong time consistency of the core, the irrational-behavior-proof condition, and the cooperative regulatory condition 358

1.4 Transformation of the characteristic function in cooperative dynamic games . . 360

1.4.1 Modified characteristic function..........................................360

1.4.2 Strong time-consistent IDPs for an imputation from the modified core

and for the modified Shapley value........................................364

1.4.3 Convergence of the transformation mechanism for the characteristic function....................................................................366

1.4.4 Limiting characteristic function..........................................369

1.4.5 Strong time-consistent IDPs for an imputation from the limiting core and

for the limiting Shapley value ............................................376

1.5 Time consistency and strong time consistency in dynamic games with discounting 378

1.6 Strong time consistency of the core for a class of dynamic games with discounting 381

1.6.1 The model ................................................................381

1.6.2 Construction of the characteristic function in the game..................384

1.6.3 Properties of the characteristic functions..................................390

1.6.4 Strong time consistency of the core ......................................393

1.6.5 An example................................................................397

Conclusion to Chapter 1 ..................................................................400

2 Cooperation in dynamic network games 403

2.1 Two-stage network games ..........................................................406

2.1.1 Definition of a two-stage network game..................................406

2.1.2 Noncooperative two-stage network game ................................408

2.1.3 Two-stage network game with cooperation at the second stage..........411

2.1.4 Cooperation in a two-stage network game................................415

2.1.5 Two applications of cooperative two-stage network games ..............423

2.1.6 Two-stage network games with pairwise interactions....................429

2.1.7 Allocations in two-level hierarchies......................................437

2.2 Formation of a directed network in a two-stage game............................447

2.2.1 Key difference from the case of undirected networks....................447

2.2.2 Cooperation in a two-stage network game played over directed networks 448

2.2.3 Two-stage network game with cooperation at the second stage in the case

of directed networks ......................................................450

2.3 Multistage network games ........................................................451

2.3.1 Definition of a multistage network game..................................451

2.3.2 Cooperation in multistage network games ................................452

2.3.3 Strategic support of cooperation in multistage network games ..........454

2.3.4 Repeated network game and strategic support of cooperation ............456

2.4 Multistage network games with shock ............................................459

2.4.1 Definition of a multistage network game with shock ......................459

2.4.2 History and strategies in a multistage network game with shock . . . . 464

2.4.3 Cooperation in a multistage network game with shock ..................466

2.4.4 Subgame consistency for a cooperative solution..........................471

2.4.5 An example ................................................................473

2.4.6 Explicit expressions for the characteristic function and the Shapley value 477

2.4.7 An alternative multistage network game with shock ......................479

Conclusion to Chapter 2 ..................................................................484

3 Consensus and influence in models of social networks 486

3.1 Opinion dynamics and the reachability of a consensus in a network with two principals..........................................................................488

3.1.1 The basic opinion dynamics model........................................488

3.1.2 Consensus in a network with two principals without direct influence on each other..................................................................490

3.1.3 Consensus in a network with two principals having direct influence on each other..................................................................495

3.1.4 Consensus in a network with two principals without direct influence on each other and heterogeneous agents ......................................498

3.2 Cooperation and equilibrium in an opinion dynamics game......................502

3.2.1 The basic model of an opinion dynamics game..........................502

3.2.2 Cooperative strategy profile in the opinion dynamics game..............504

3.2.3 Allocation of the cooperative payoff......................................506

3.2.4 Characteristic function for cooperative payoff allocation ................508

3.2.5 Nash equilibrium..........................................................511

3.2.6 Price of anarchy ..........................................................511

3.2.7 Modification of the basic model: an alternative objective................512

3.2.8 Estimation of the levels of trust ..........................................513

3.2.9 Numerical simulation......................................................514

Conclusion to Chapter 3..................................................................527

4 Dynamic games with perfect information played over trees 529

4.1 Multistage network games with perfect information..............................531

4.1.1 Definition of a multistage network game with perfect information ... 531

4.1.2 Construction of a Nash equilibrium in a multistage network game . . . 534

4.1.3 An example................................................................537

4.2 Solutions to multistage games with restricted communication and perfect information ..............................................................................539

4.2.1 Preliminaries ..............................................................540

4.2.2 Dynamic formation of a communication graph: model 1................543

4.2.3 Dynamic formation of a communication graph: model 2................545

4.2.4 Game with a major player................................................546

4.2.5 Dynamic formation of a communication graph in the game with a major player: model 1 ............................................................550

4.2.6 Dynamic formation of a communication graph in the game with a major

player: model 2............................................................552

4.3 Cooperation in multistage games with interval payoffs............................554

4.3.1 Operations on closed intervals............................................554

4.3.2 An interval dynamic game with perfect information......................554

4.3.3 Cooperative interval dynamic game with perfect information ............555

4.3.4 Time consistency of the interval Shapley-like value......................557