Решения игр с остовным деревом тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Ли Инь

• Ли Инь
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Ли Инь

Введение

Глава 1. Динамический вектор Шепли в двухшаговой игре с

остовным деревом или остовным лесом с шоком

1.1 Основные определения

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

1.2.1 Описание игры

1.2.2 Характеристическая функция

1.2.3 Динамический вектор Шепли

1.2.4 Теоремы для построения динамического вектора Шепли, динамически устойчивого в двухшаговой игре с

остовным деревом

1.3 Динамический вектор Шепли в двухшаговой игре со скоропортящимися товарами

1.3.1 Описание игры

1.3.2 Характеристическая функция

1.3.3 Динамический вектор Шепли

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

лесом с шоком

1.4.1 Описание игры

1.4.2 Характеристическая функция

1.4.3 Динамический вектор Шепли

1.4.4 Теорема для построения динамического вектора Шепли, динамически устойчивого в двухшаговой игре с

остовным лесом с шоком

Глава 2. Решение двухшаговой стохастической игры с

остовным деревом

2.1 Динамический вектор Шепли в двухшаговой стохастической

игре с остовным деревом

2.1.1 Описание игры

2.1.2 Модель

2.1.3 Характеристическая функция

2.1.4 Динамический вектор Шепли

2.1.5 Теоремы для построения динамического вектора Шепли, динамически устойчивого в двухшаговой стохастической

игре с остовным деревом

2.2 Динамическая арбитражная схема Нэша в двухшаговой

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

2.2.1 Модель

2.2.2 Кооперативная игра

2.2.3 Динамическая арбитражная схема Нэша

2.2.4 Теорема для построения динамической арбитражной схемы Нэша, динамически устойчивой в двухшаговой стохастической игре с остовным деревом

Глава 3. Сильная динамическая устойчивость в многошаговых

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

3.1 Описание игры

3.1.1 Многошаговая игра

3.1.2 Кооперативная игра

3.1.3 Процедура Распределения Дележа

3.2 Теоремы для построения сильно-динамически устойчивого

С-ядра в многошаговых играх с остовным деревом

Заключение

Список литературы

Список рисунков

Список таблиц

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

Введение

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

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

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

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

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

После формализации данного сложного конфликтного процесса с помощью теории игр, важным условием для получения общего приемлемого решения является выбор критерия оптимальности. К сожалению, что неудивительно, не существует универсального принципа оптимальности, который соответствовал бы всем конфликтным процессам. Поэтому теория игр обладает обширным семейством принципов оптимальности, удовлетворяющих различным аксиоматическим системам. Одним из наиболее распространенных принципов оптимальности в теории некооперативных игр является равновесие по Нэшу, предложенное Джоном Нэшем в 1950 году [1; 2]. В кооперативных играх, Дональд Б. Гиллис ввёл концепцию «С-ядра» в 1959 году [3], а Рейнхард Зельтен ввёл концепцию равновесия по Нэшу в динамический анализ и предложил концепцию равновесия, совершенного в подыграх [4]. В 1953 г. Шепли ввел понятие вектора Шепли, используя аксиоматизацию [5]. Впоследствии вектор Шепли и О-ядро стали двумя важными решениями в кооперативных играх.

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

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

Стохастические игры—подкласс позиционных игр (игр в развёрнутой форме), впервые определённый в работе Г. Куна [6]. Стохастические игры были подробно изучены Ллойдом С. Шепли [7]: он ввёл понятие стохастической игры и доказал существование значений антагонистических стохастических игр бесконечной продолжительности. Приведённое или функциональное уравнение для значения игры фактически является обобщением уравнения Беллмана для динамических игр [8]. В работах Такахаши и Финк [9; 10], результаты Шепли были обобщены на случай стохастических игр п лиц, а существование равновесия по Нэшу в стационарных стратегиях было доказано для стохастических игр с компактным множеством стратегий и конечным множеством состояний. После этого появилось множество публикаций, посвященных доказательству существования равновесия по Нэшу в различных классах стратегий, изучению стохастических игр с неполной информацией, стохастических игр с асимметричными игроками; см. работы Солана и Виелле, Мертенса и Неймана, Неймана, Новака, Хорнера и других авторов [11—15].

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

При изучении сетевых игр, связанных со стохастическими играми, в работах Галеотти и др. [20] и Халлера [21] в качестве решения игры рассмотрено равновесие по Нэшу. А игра, основанная на кооперативном двухшаговом формировании сети, представлена в исследовании Гао и др. [22]. В работах Фери, Фери и др., Фоско и Менгеля, Уоттса [23—26] рассмотрены динамические процессы формирования сетей, в том числе с учётом стохастических факторов или

кооперативного поведения. В работе Гао и др. [27] изучена динамическая устойчивость кооперативных решений в повторяющихся сетевых играх.

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

В работе [28] Петросян и Седаков предложили класс решений, обладающих свойством динамической устойчивости в сетевых играх (например, вектор Шепли [5]), в которых стратегия игрока определяется как в работе Г. Куна [6]. Другие методы формирования сети изучены Бала и Гоялем, Галеотти и др., Хал-лером [20; 21; 29], где основой некооперативного решения является равновесие по Нэшу, а кооперативное решение может быть найдено с помощью уравнения Беллмана [30]. Конкретный игрок, выходящий из игры с заданной вероятностью на различных шагах игры, теряет возможность получить какой-либо выигрыш. Этот эффект называется «шоком».

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

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

Условия динамической устойчивости решений для стохастических игр подробно описаны Янгом и Петросяном [33]. Различные подходы к этой проблеме можно найти в работе Заккура [34]. Петросян усилил условия динамической устойчивости кооперативных решений и назвал кооперативные решения, удовлетворяющие этим условиям, сильно динамически устойчивыми [35].

Проблема построения остовного дерева. Проблема построения остовного дерева является классической в теории графов и комбинаторной оптимизации. В то время как специалисты по исследованию операций обычно интересуются такими вопросами, как вычислительная сложность и разработка эффективных алгоритмов, экономисты обращаются к важному аспекту распределения затрат в эффективных структурах сети. Игра с остовным деревом возникла из проблемы построения остовного дерева и была впервые представлена Клаусом и Клейтманом [36] в 1973 году. Они рассмотрели следующую ситуацию: находящиеся в разных географических точках игроки хотят получить конкретную услугу, которую может предоставить единственный поставщик (так называемый источник). Игроки получат услуги, подключившись к источнику (напрямую или через других игроков), и оба эти действия требуют затрат, независимо от того, связаны ли они с источником напрямую или нет. Цель работы — найти сеть, которая минимизирует затраты. Эта сеть не только соединяет всех

игроков с источником, но и является способом распределения минимальных затрат между игроками. Поэтому в игре с остовным деревом сначала следует обратиться к алгоритмам решения задачи минимизации суммарных затрат; соответствующие алгоритмы взяты из самых ранних работ Крускаля, Прима, и Дейкстры [37—39]. Все они предлагали алгоритмы построения дерева с минимальными затратами. Обзор таких работ можно найти в статье Грэхема и Хэлла [40].

Для решения игры с остовным деревом отметим три важных подхода, дав краткое описание каждого из них. Наиболее известным решением является решение, предложенное Бёрдом [41]. В работе Грано и Губермана [42] оказано, что это решение принадлежит С-ядру и является вершиной ядерного многогранника. Несмотря на то, что это самая известная схема распределения затрат для игр с остовным деревом, решение Бёрда имеет некоторые недостатки. Например, условие монотонности затрат не выполняется. Монотонность затрат означает, что если затраты на подключение игрока к источнику или к другим игрокам возрастают, то доля игрока в затратах не уменьшается. По этой причине исследователи предложили несколько новых и более разумных решений для распределения затрат. Дутта и Кар [43] предложили решение ДК (Дутта-Кар), удовлетворяющее монотонности затрат. Они улучшили решение Бёрда, позволяя сначала выбранному игроку обменяться затратами с выбранным впоследствии игроком в процессе генерации минимального остовного дерева с использованием алгоритма Прима [38]. Решение ДК удовлетворяет условиям монотонности затрат и принадлежит C-ядру. В дополнение к своему решению, Бёрд [41] ввёл понятие неприводимого C-ядра (irreducible core). Неприводимое C-ядро совпадает с C-ядром игры, соответствующим неприводимому графу. Игра, полученная из неприводимого графа, является выпуклой и, как следствие, удовлетворяет многим хорошим свойствам.

Другим важным решением является так называемое «народное решение» (Folk solution); см. работы Фельткампа, Тейса и Муто, Бергантиньоса и Видаль-Пуга [44; 45]. Оно равно вектору Шепли соответствующей игры на неприводимом графе. Народные решения удовлетворяют некоторым свойствам, которых нет у решения Бёрда, в частности, солидарность (solidarity), монотонность населения (population monotonicity), и монотонность затрат. Здесь солидарность означает, что при повышении общих затрат на минимальном остовном дереве доля затрат каждого игрока не уменьшится. Монотонность

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

Третье решение называется полным по циклам решением (cycle-complete solution) или решением Трюдо [46]. Оно является подмножеством ядра, также удовлетворяет строгой монотонности затрат и может быть вычислено за экспоненциальное время.

Вектор Шепли, рассмотренный в данной диссертации, получается путем модификации вектора Шепли в динамической игре, предложенной в работе Кара [47], где представлено аксиоматическое описание вектора Шепли в рамках игр с остовным деревом. В данной диссертации рассматриваются динамические векторы Шепли, построенные на этой основе, и обсуждается природа их устойчивости в контексте кооперативных стохастических игр с остовным деревом. К этой теме относятся публикации Ли Инь [31; 48; 49].

Кроме того, в настоящей диссертации исследуется динамическая игра с остовным лесом, обобщающая предыдущую модель. Розенталь [50] впервые предложил модель игры с остовным лесом, в которой существуют два и более источника, а игроки должны иметь путь, по меньшей мере, к одному источнику. Таким образом, результирующая сеть в такой модели не обязательно должна быть задана в виде дерева. Д. Грано, Ф. Грано [51] ввели игру с остовным лесом и фиксированными затратами (fixed cost spanning forest game) и установили достаточные условия для существования непустого ядра в игре. В работе Ли Инь [49] рассмотрена кооперативная стохастическая игра с остовным лесом, в которой конкретный игрок выходит из игры с вероятностью, зависящей от общего поведения всех игроков на предыдущем шаге. В отличие от постановки Розенталя [50], в которой рассматривается несколько одинаковых источников, в модели Ли Инь [9] существует несколько различных источников, и делается предположение, что каждому игроку необходимо соединить несколько различных источников в соответствии с их потребностями. Это предположение широко распространено в реальных задачах управления цепочками поставок. В исследовании Ли Инь [49] показано, что динамические векторы Шепли, построенные с использованием процедуры распределения дележа, при определённых условиях удовлетворяют принципу динамической устойчивости.

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

остовным деревом необходимо учитывать скорость порчи товара и скорость потери его стоимости в различных построенных сетях. Согласно практическому опыту, чем больше затраты на транспортировку, тем выше скорость транспортировки; чем лучше защита скоропортящегося товара, тем меньше потери стоимости. Таким образом, все эти потери стоимости, помимо затрат на минимальном остовном дереве, также составляют часть общих затрат на транс-портно-логистической сети. Текущие исследования в области скоропортящихся товаров сосредоточены на стратегиях управления запасами и ценообразования, управления транспортом и т.д. Нахмиас и Баккер [52; 53] представили обзор исследований по системам хранения скоропортящихся товаров. Сюй Сяолан [54] проанализировал взаимосвязь между временем транзита скоропортящихся товаров и доходами розничных продавцов. Ли и др. [55] изучили проблемы товарно-материальных запасов и совместного ценообразования, когда на скоропортящиеся товары существует случайный спрос. Богатай [56] показал, что изменения в температуре транспортировки и времени транспортировки скоропортящихся товаров приводят к изменениям в стоимости цепочки поставок.

С помощью статических кооперативных игр решены следующие задачи, связанные со скоропортящимся товарами: транспортная кооперация и распределение затрат на скоропортящиеся товары (см. работу Ли и Цаи [57]), а также выбор транспортного оборудования для скоропортящихся товаров (см. работу Джун и Цаи [58]).

Впервые кооперативные стохастические игры со скоропортящимися товарами в постановке с минимальным остовным деревом были исследованы в работе Ли Инь [48]. Динамическая устойчивость кооперативных решений этих игр изучается в данной диссертации.

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

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

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

Первое направление исследований инициировано работой Герцога и др. [60], где была предложена следующая модель: в каждой вершине сети может одновременно находится несколько игроков, так что все вершины делятся на 2 типа — общие и частные. Далее, в модели Монтеманни [61], случайная природа отражается в том, что затраты на связь в сети принадлежат некоторым интервалам, а не являются фиксированным числом, как в игре с остовным деревом. Задача с интервальными затратами осложняется тем, что невозможно напрямую построить минимальное остовное дерево. В указанном выше исследовании предложена концепция относительной робастности.

Второе направление исследований, посвящённых моделированию сетей с неопределенными затратами, можно найти в работе Суйс [62]. В данном исследовании предполагается, что затраты в сети состоят из двух компонент, а именно: затраты на построение и затраты на техническое обслуживание сети. При этом, первую компоненту можно считать детерминированной, а вторую компоненту обычно считают стохастической.

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

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

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

Для достижения целей в работе ставятся и решаются следующие задачи:

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат наук Ли Инь, 2022 год

Список литературы

[1] Nash J. Non-cooperative games // Annals of mathematics. 1951. С. 286-295.

[2] Nash Jr J.F. The bargaining problem // Econometrica: Journal of the econometric society. 1950. Т. 18. № 2. С. 155-162.

[3] Gilles D. Solutions to general nonzero sum games // Annals of Mathematics. 1959. Т. 4. С. 194-220.

[4] Bielefeld R.S. Reexamination of the perfectness concept for equilibrium points in extensive games // Models of Strategic Rationality. : Springer, 1988. С. 1-31.

[5] Shapley L.S. A value for n-person games // Contributions to the Theory of Games. 1953. Т. 2. № 28. С. 307-317.

[6] Kuhn H.W. Extensive Games and the Problem of Information, Contributions to the Theory of Games II // Annals of Mathematics Studies. 1953. Т. 28. С. 193-216.

[7] Shapley L.S. Stochastic games // Proceedings of the national academy of sciences. 1953. Т. 39. № 10. С. 1095-1100.

[8] Bellman R. Some functional equations in the theory of dynamic programming // Proceedings of the National Academy of Sciences of the United States of America. 1953. Т. 39. № 10. С. 1077.

[9] Takahashi M. Stochastic games with infinitely many strategies // Hiroshima Mathematical Journal. 1962. Т. 26. № 2. С. 123-134.

[10] Fink A.M. Equilibrium in a stochastic n-person game // Hiroshima Mathematical Journal. 1964. Т. 28. № 1. С. 89-93.

[11] Solan E., Vieille N. Correlated equilibrium in stochastic games // Games and Economic Behavior. 2002. Т. 38. № 2. С. 362-399.

[12] Mertens J.F., Neyman A. Stochastic games // International Journal of Game Theory. 1981. Т. 10. № 2. С. 53-66.

[13] Neyman A. Existence of optimal strategies in Markov games with incomplete information // International Journal of Game Theory. 2008. Т. 37. № 4. С. 581-596.

[14] Nowak A.S. Existence of equilibrium stationary strategies in discounted noncooperative stochastic games with uncountable state space // Journal of Optimization Theory and Applications. 1985. Т. 45. № 4. С. 591-602.

[15] Horner J., Rosenberg D., Solan E., Vieille N. On a Markov game with one-sided information // Operations Research. 2010. Т. 58. № 4 PART 2. С.1107-1115.

[16] Petrosjan L.A. Cooperative stochastic games // Annals of the International Society of Dynamic Games. , 2006. С. 139-145.

[17] Petrosyan L.A., Baranova E.M. Cooperative stochastic games in stationary strategies // Game Theory and Applications. 2006. Т. 11. С. 1-7.

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

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

[20] Galeotti A., Goyal S., Kamphorst J. Network formation with heterogeneous players // Games and Economic Behavior. 2006. Т. 54. № 2. С. 353-372.

[21] Haller H. Network extension // Mathematical Social Sciences. 2012. Т. 64. № 2. С. 166-172.

[22] Gao H, Petrosyan L., Sedakov A. Strongly time-consistent solutions for two-stage network games // Procedia Computer Science. 2014. Т. 31. С. 255-264.

[23] Feri F. Stochastic stability in networks with decay // Journal of Economic Theory. 2007. Т. 135. № 1. С. 442-457.

[24] Feri F., Meléndez-Jiménez M. A. Coordination in evolving networks with endogenous decay // Journal of Evolutionary Economics. 2013. T. 23. № 5. C. 955-1000.

[25] Fosco C., Mengel F. Cooperation through imitation and exclusion in networks // Journal of Economic Dynamics and Control. 2011. T. 35. № 5. C. 641-658.

[26] Watts A.A. Dynamic Model of Network Formation // Games and Economic Behavior. 2001. T. 34. № 2. C. 331-341.

[27] Gao H., Petrosyan L., Sedakov A. Dynamic Shapley value for repeated network games with shock // Proceedings of the 2015 27th Chinese Control and Decision Conference, CCDC 2015. , 2015. C. 6449-6455.

[28] Petrosyan L., Sedakov A. The Subgame-Consistent Shapley Value for Dynamic Network Games with Shock // Dynamic Games and Applications. 2016. T. 6. № 4. C. 520-537.

[29] Bala V., Goyal S. A noncooperative model of network formation // Econometrica. 2000. T. 68. № 5. C. 1181-1229.

[30] Bellman R. Dynamic Programming (DP) // Economica. 1959. T. 26. № 104.

[31] Yin L. The dynamic Shapley Value in the game with spanning tree // Proceedings of 2016 International Conference «Stability and Oscillations of Nonlinear Control Systems» (Pyatnitskiy's Conference), STAB 2016. , 2016. C. 1-4.

[32] Li Y. The dynamic Nash bargaining solution for 2-stage cost sharing game // Contributions to Game Theory and Management. 2020. T. 13. № 1. C. 296-303.

[33] Yeung D.W.K., Petrosyan L.A. Cooperative Stochastic Differential Games. : Springer Science and Business Media, 2006. 1-299 c.

[34] Zaccour G. Time consistency in cooperative differential games: A tutorial // INFOR: Information Systems and Operational Research. 2008. T. 46. № 1. C. 81-92.

[35] Петросян Л.А. Сильно динамически устойчивые принципы оптимальности в многокритериальных задачах оптимального управления // Техническая кибернетика. 1993. № 1. С. 169-174.

[36] Claus A., Kleitman D.J. Cost allocation for a spanning tree // Networks. 1973. Т. 3. № 4. С. 289-304.

[37] Kruskal J.B. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem // Proceedings of the American Mathematical Society. 1956. Т. 7. № 1. С. 48.

[38] Prim R.C. Shortest Connection Networks And Some Generalizations // Bell System Technical Journal. 1957. Т. 36. № 6. С. 1389-1401.

[39] Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. Т. 1. № 1. С. 269-271.

[40] Graham R.L., Hell P. On the History of the Minimum Spanning Tree Problem // Annals of the History of Computing. 1985. Т. 7. № 1. С. 43-57.

[41] Bird C.G. On cost allocation for a spanning tree: A game theoretic approach // Networks. 1976. Т. 6. № 4. С. 335-350.

[42] Granot D., Huberman G. Minimum cost spanning tree games // Mathematical Programming. 1981. Т. 21. № 1. С. 1-18.

[43] Dutta B., Kar A. Cost monotonicity, consistency and minimum cost spanning tree games // Games and Economic Behavior. 2004. Т. 48. № 2. С. 223-248.

[44] Feltkamp V., Tijs S., Muto S. On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems. : Center for Economic Research, Tilburg University, 1994. 1-36 с.

[45] Bergantinos G., Vidal-Puga J.J. A fair rule in minimum cost spanning tree problems // Journal of Economic Theory. 2007. Т. 137. № 1. С. 326-352.

[46] Trudeau C. A new stable and more responsive cost sharing solution for minimum cost spanning tree problems // Games and Economic Behavior. 2012. Т. 75. № 1. С. 402-412.

[47] Kar A. Axiomatization of the Shapley value on minimum cost spanning tree games // Games and Economic Behavior. 2002. T. 38. № 2. C. 265-277.

[48] Yin L. Dynamic Shapley Value for 2-stage cost sharing game with perishable products // Proceedings of the 29th Chinese Control and Decision Conference, CCDC 2017. , 2017. C. 3770-3774.

[49] Yin L. Dynamic Shapley value in the game with spanning forest // 2017 Constructive Nonsmooth Analysis and Related Topics (Dedicated to the Memory of V.F. Demyanov), CNSA 2017 - Proceedings. , 2017. C. 1-4.

[50] Rosenthal E.C. The minimum cost spanning forest game // Economics Letters. 1987. T. 23. № 4. C. 355-357.

[51] Granot D., Granot F. Computational Complexity of a Cost Allocation Approach to a Fixed Cost Spanning Forest Problem // Mathematics of Operations Research. 1992. T. 17. № 4. C. 765-780.

[52] Nahmias S. Perishable Inventory Theory: a Review. // Operations Research. 1982. T. 30. № 4. C. 680-708.

[53] Bakker M., Riezebos J., Teunter R.H. Review of inventory systems with deterioration since 2001 // European Journal of Operational Research. 2012. T. 221. № 2. C. 275-284.

[54] Xu X. Optimal decisions in a time -sensitive supply chain with perishable products // ProQuest Dissertations and Theses. 2006.

[55] Li S., Zhang J., Tang W. Joint dynamic pricing and inventory control policy for a stochastic inventory system with perishable products // International Journal of Production Research. 2015. T. 53. № 10. C. 2937-2950.

[56] Bogataj M. Stability of perishable goods in cold logistic chains // International Journal of Production Economics. , 2005. C. 345-356.

[57] LI J., CAI X. Cost Allocation for Transporuation Facility Choice of Perishable Products Based on Cooperative Game // Chinese Journal of Management Science. 2007. T. 4. № 4. C. 51-58.

[58] LI, Jun and CAIX. Transportation facility choice game of perishable products // Journal of Management Sciences in China. 2009. T. 1.

[59] Pankratova Y.B., Petrosyan L.A. New characteristic function for multistage dynamic games // Vestnik Sankt-Peterburgskogo Universiteta, Prikladnaya Matematika, Informatika, Protsessy Upravleniya. 2018. T. 14. № 4. C. 316-324.

[60] Herzog S., Shenker S., Estrin D. Sharing Multicast Costs // Internet Economics. 1997. C. 169-212.

[61] Montemanni R.A. Benders decomposition approach for the robust spanning tree problem with interval data // European Journal of Operational Research. 2006. T. 174. № 3. C. 1479-1490.

[62] Suijs J. Cost allocation in spanning network enterprises with stochastic connection costs // Games and Economic Behavior. 2003. T. 42. № 1. C. 156-171.

[63] Petrosian O, Shi L., Li Y., Gao H. Moving information horizon approach for dynamic game models // Mathematics. 2019. T. 7. № 12.

[64] Petrosian O., Nastych M., Li Y. The Looking Forward Approach in a Differential Game Model of the Oil Market with Non-transferable Utility // Static and Dynamic Game Theory: Foundations and Applications. , 2020. C. 215-244.

[65] Myerson R.B. Graphs and Cooperation in Games // Mathematics of Operations Research. 1977. T. 2. № 3. C. 225-229.

[66] Bolton J.M., Liu W.B. Creating an effective china cold supply chain-Current status, challenges and implementation considerations // Accenture report. 2006.

[67] Qian Z, Ying X., Mingke H, Hao Z. Multi-objective Model of Distribution Route Problem for Fresh Electricity Commerce under Uncertain Demand // Xitong Fangzhen Xuebao / Journal of System Simulation. 2019. T. 31. № 8. C.1582-1590.

[68] Hadamard J. Resolution d'une question relative aux determinants // Bull Sci Math. 1893. T. 2. № 17. C. 240- 248.

[69] Parilina E.M. Stable cooperation in stochastic games // Automation and Remote Control. 2015. Т. 76. № 6. С. 1111-1122.

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

[71] Shapley L.S. Cores of convex games // International Journal of Game Theory. 1971. Т. 1. № 1. С. 11-26.

Список рисунков

1.1 Полный граф с затратами для четырех игроков..........................22

1.2 Графы с разными затратами на рёбрах, соответствующие разным стратегиям игроков..........................................................24

1.3 Минимальное остовное дерево после построения графа игроками. . . 26

1.4 Путь Рт0, непосредственный предшественник вершины т, предшественник вершины т и ветка Вт..................................28

1.5 Диаграмма игры............................................................29

1.6 Пример вероятности того, что игрок т покинет игру ..................32

1.7 Коалиция 5 и коалиция N \Б в игре 4-х лиц с остовным деревом. . 33

1.8 Двухшаговая игра 2-х лиц с остовным деревом..........................37

1.9 т — терминальная вершина в дереве....................................43

1.10 Три типа товаров с различной динамикой полезности..................52

1.11 Двухшаговая игра 2-х лиц со скоропортящимися товарами............60

1.12 Вероятность того, что игрок т покинет игру............................66

1.13 Диаграмма игры с остовным лесом ......................................67

2.1 Влияние а-матрицы на затраты на рёбрах графа. Ребро, на котором затраты равны бесконечности, не может быть ребром минимального остовного дерева............................................74

2.2 Диаграмма игры..............................................................75

2.3 Диаграмма игры с остовным деревом....................................81

2.4 Диаграмма игры с минимальным остовным деревом для коалиции

5", где 5" = 5 и{0}, 5 = {1,2,3}..........................................82

2.5 Древовидный граф игры (слева) и граф на каждом шаге игры (справа)......................................................................86

2.6 На каждом шаге игры игрок % Е N подключён к источнику без

N \И........................................................................95

2.7 Древовидный граф игры (слева) и граф на каждом шаге игры (справа)......................................................................99

3.1 Дерево игры Н = (г,Г)..........................105

3.2 Коалиция 5 и коалиция N \ 5 в одношаговой игре 4-х лиц с остовным деревом............................................................111

3.3 Характеристическая функция V(х,5'), 5 Е %..........112

Список таблиц

1 Все возможные затраты на рёбрах при разных действиях игроков. . 25

2 Все возможные затраты с\2, выделенные красным цветом..............37

3 Возможные вероятности перехода от к х2 или ......................87

Saint-Petersburg State University

Manuscript copyright

Li Yin

Solutions of Spanning Tree Games

Scientific specialisation 1.2.3. Theoretical informatics, cybernetics

Dissertation is submitted for the degree of Candidate of Physical and Mathematical Sciences

Translation from Russian

Thesis supervisor:

Doctor of Physical and Mathematical Sciences, Professor

Leon Aganesovich Petrosyan

Saint-Petersburg — 2021

Contents

Introduction...................................135

Chapter 1. Dynamic Shapley Value in Two-Stage Spanning Tree

or Forest Game with Shock..................149

1.1 Main Definitions.............................149

1.2 Dynamic Shapley value in two-stage spanning tree game.......156

1.2.1 Game description........................156

1.2.2 Characteristic function.....................159

1.2.3 Dynamic Shapley value.....................162

1.2.4 Theorems for constructing time-consistent dynamic Shapley value in two-stage spanning tree game ..........................166

1.3 Dynamic Shapley value in two-stage perishable goods game.....177

1.3.1 Game description........................177

1.3.2 Characteristic function.....................181

1.3.3 Dynamic Shapley value.....................183

1.4 Dynamic Shapley value in two-stage spanning forest game with shock 188

1.4.1 Game description........................188

1.4.2 Characteristic function.....................193

1.4.3 Dynamic Shapley value.....................194

1.4.4 Theorem for constructing time-consistent dynamic Shapley value in two-stage spanning forest game ........................196

Chapter 2. Solution of Two-Stage Stochastic Spanning Tree Game 197

2.1 Dynamic Shapley value in two-stage stochastic spanning tree game . 197

2.1.1 Game description........................197

2.1.2 Model..............................199

2.1.3 Characteristic function.....................205

2.1.4 Dynamic Shapley value.....................208

2.1.5 Theorems for constructing time-consistent dynamic Shapley value in two-stage stochastic spanning tree game.......211

2.2 Dynamic Nash bargaining solution in two-stage stochastic spanning

tree game ................................................................216

2.2.1 Model..............................216

2.2.2 Cooperative game........................218

2.2.3 Dynamic Nash bargaining solution...............221

2.2.4 Theorem for constructing time-consistent dynamic Nash bargaining solution in two-stage stochastic spanning tree game 225

Chapter 3. Strong Time Consistency in Multistage Spanning Tree

Games...............................227

3.1 Game description............................227

3.1.1 Multistage game ........................231

3.1.2 Cooperative game........................233

3.1.3 Imputation Distribution Procedure ..............237

3.2 Theorems for constructing strongly time-consistent core in

multistage spanning tree games .................... 238

Conclusion .................................... 244

References .................................... 245

List of figures..................................252

List of tables..................................253

Introduction

This dissertation contains various models of cooperative stochastic spanning tree games and is devoted to constructing cooperative solutions for these models. In addition, the results obtained below are extended to cooperative stochastic spanning forest games and multistage cooperative spanning tree games with complete information.

Research relevance. Approaches of dynamic game theory are increasingly used in solving various applied problems in the modeling and optimization of complex socioeconomic and ecological systems. A characteristic feature of such systems is the presence of several players, whose actions affect the system when the players make decisions in their interests. Stochastic games with uncertainty are also of great importance in modeling real conflict processes since they consider random factors.

In cost allocation game theory, a spanning tree game is closely related to the network structure defining the game. Networks play an important role in economics, so the study of spanning tree games associated with dynamic networks is crucial for solving economic problems, especially when allocating cost. The research presented in this dissertation is the first to associate dynamic games with spanning tree games, taking into account changes in networks. The research aims to study cooperative solutions in dynamics and changes in the network structure in dynamics generating these solutions, consider methods for implementing cooperative solutions in dynamics, and analyze their properties.

A feature of the main model considered below is that all one-stage ^-player games are spanning tree games. Players build a network by their joint actions. The structure of the minimum cost tree, which links all players in this network, affects the network structure at the next stage of the game. In real life, this process can be illustrated with a simple example. Suppose that there are N logistics companies, each with a different geographic location. They plan to create a common transport and logistics network. Whatever joint actions the companies take, they must get a transport and logistics network connecting all geographic points (vertices). Obviously, this must be a connected graph. According to the results of graph theory, a connected graph containing all the vertices on a given graph and having the minimum number of edges is the minimum spanning tree on this graph. However, after some time, the companies need to rebuild the overall transport and

logistics network again: there are various factors that can lead to changes in the original transport and logistics network structure. For example, some routes within the transport and logistics network may be used with high load and require repair or modernization (become unavailable). On the other hand, low additional load or repaired and modernized routes can reduce transport logistics cost. Therefore, when building a common transport and logistics network, all N companies must agree on a cost allocation scheme, thinking rationally. In this difficult situation, some companies can no longer fully determine the result of the dynamic game. Therefore, it is crucial for all players to reach commonly acceptable solutions in advance.

After formalizing this complex conflict process based on game theory, an important condition for obtaining a commonly acceptable solution is the choice of an optimality criterion. Unfortunately, not surprisingly, there is no universal principle of optimality that would correspond to all conflict processes. Therefore, game theory has a rich family of optimality principles that satisfy various axiomatic systems. One of the most common optimality principles in the theory of noncooperative games is the Nash equilibrium, proposed in 1950 by John Nash [1; 2]. In cooperative games, Donald B. Gillies introduced in 1959 the concept of the core [3], and Reinhard Selten introduced the concept of Nash equilibrium into dynamic analysis and proposed the concept of subgame perfect equilibrium [4]. In 1953, Shapley introduced the concept of the Shapley value using an axiomatization [5]. Subsequently, the Shapley value and the core became two important solutions in the class of cooperative games.

In this dissertation, the network structure of a one-stage game changes randomly, and the probability of such a change depends on the joint actions of the players. Therefore, the game combines both the stochastic game model and the spanning tree game model. We present new results in the field of combining stochastic and spanning tree games.

Stochastic games is a subclass of positional games (games in extensive form), first defined by G. Kuhn [6]. Stochastic games were studied in detail by Lloyd S. Shapley [7]: he introduced the concept of stochastic games and proved the existence of values for the antagonistic stochastic games of infinite duration. The reduced or functional equation for the game value is a generalization of the Bellman equation for dynamic games [8]. In the works of Takahashi and Fink [9; 10], Shapley's results were generalized to the case of stochastic n-player games, and the existence of Nash equilibrium in stationary strategies was proved for stochastic games with a compact set of strategies and a finite set of states. After that, there were many

publications devoted to proving the existence of Nash equilibrium in various classes of strategies, the study of stochastic games with incomplete information, stochastic games with asymmetric players; see the works of Solan and Vieille, Mertens and Neyman, Neyman, Nowak, Horner and other authors [11—15].

In the work [16] L.A. Petrosyan pioneered a method for constructing cooperative stochastic games realized on finite trees. For this class of games, he formulated the problem of the time consistency of the Shapley value and solved the problem of regularizing the time-inconsistent Shapley value. Parilina and Petrosyan [17] applied this method for cooperative stochastic games of infinite duration. In the paper [18] Petrosyan presented the property of dynamic stability (time consistency) of cooperative solutions for differential games. Petrosyan and Danilov [19] proposed a method for determining payments to players when regularizing a time-inconsistent cooperative solution using the imputation distribution procedure.

In the study of network games related to stochastic games, Galeotti et al. [20] and Haller [21] considered the Nash equilibrium as a solution principle. A game based on cooperative two-stage network formation was presented by Gao et al. [22]. Feri, Feri et al., Fosco and Mengel, and Watts [23—26] considered dynamic network formation processes, including stochastic factors or cooperative behavior. Gao et al. [27] studied the dynamic stability of cooperative solutions in repeated network games.

Provided that all players adhere to the cooperation agreement, the Shapley value is called time-consistent if the Shapley value component of any player in the original game is equal to the sum of its Shapley value component in the subgame in which he begins to participate and the payoffs accumulated in all previous stages. The notion of time consistency was introduced by Petrosyan [16] for cooperative stochastic games. In several dynamic game-theoretic models with one-stage spanning tree games presented in this dissertation, various cooperative solutions are constructed according to the Imputation Distribution Procedure (IDP) first proposed by Petrosyan and Danilov [19]. These cooperative solutions are time-consistent under the given conditions, and the players follow the terms of the cooperative agreement throughout the game.

In the paper [28], Petrosyan and Sedakov proposed a class of solutions possessing the property of time consistency in network games (for example, the Shapley value [5]), in which the player's strategy is defined like in Kuhn's approach [6]. Bala and Goyal, Galeotti et al., Haller [20; 21; 29] studied other network formation

methods, where the noncooperative solution is based on Nash equilibrium, and the cooperative solution can be found using the Bellman equation [30]. A particular player leaving the game with a given probability at various stages of the game loses the opportunity to obtain any payoff. This effect is called "shock."

The shock effect was investigated by Li Yin [31] for a two-stage spanning tree game. In this model, a particular player leaves the game with a probability depending on the previous behavior of all players. Such a minimum spanning tree game changes the network structure, which is also random. The cited paper was devoted to the implementability of cooperative agreements, namely, their time consistency. This dissertation assumes that the cooperative solution (the dynamic Shapley value) in a two-stage spanning tree game is time-inconsistent. This model describes various economic and social processes (logistics and transport networks, communication networks, etc.). Further research in this direction was presented in [32]. In a two-stage spanning tree game, the network structure at the second stage changes with a given probability depending on the behavior of all players at the first stage. Due to this effect, one or more players move from a favorable position in the network structure to an unfavorable one, or vice versa (in terms of cost allocation). In [32], a two-stage dynamic cooperative solution (Nash bargaining solution or arbitration scheme) was constructed, and a special scheme of step-by-step payments to players based on the Nash bargaining solution was proposed to guarantee the time consistency of the cooperative solution (dynamic Nash bargaining solution). This model suggests a new way to change the network structure at the second stage. A new a-matrix was defined to change the cost matrix in the network at the second stage, provided that all players cooperate at the first stage. This dynamic game model is compared to the game model proposed in [31], and although no player leaves the game with some probability, all players at the second stage are influenced by their joint behavior at the first stage.

The time consistency conditions for solutions of stochastic games were described in detail by Yeung and Petrosyan [33]. Various approaches to this problem can be found in Zaccour's paper [34]. Petrosyan strengthened the time consistency conditions for cooperative solutions and called cooperative solutions that satisfy these conditions strongly time-consistent [35].

The problem of constructing a spanning tree. The problem of constructing a spanning tree is classical in graph theory and combinatorial optimization. While operations researchers are usually interested in computational complexity and effi-

cient algorithm design, economists turn to an important aspect of cost allocation in efficient network structures. The spanning tree game arose out of the spanning tree problem and was first introduced in 1973 by Claus and Kleitman [36]. They considered the following statement: players at different geographic locations need a specific service provided by a single supplier (the so-called source). Players will receive service by connecting to the source (either directly or through other players), and both of these actions incur cost. The goal is to find a network minimizing the cost. This network connects all players to the source. Moreover, it is a way of allocating the minimum cost among the players. Therefore, in a spanning tree game, one should first turn to algorithms for minimizing the total cost; these algorithms are taken from the earliest works of Kruskal, Prim, and Dijkstra [37—39]. All of them suggested algorithms for building a minimum cost tree. An overview of such works can be found in Graham and Hell's paper [40].

We mention three approaches to solve a spanning tree game, describing each of them in brief. The most famous solution is Bird's [41]. Granot and Huberman [42] demonstrated that this solution belongs to the core and is a vertex of the core's polytope. Despite being the most well-known cost allocation scheme for spanning tree games, Bird's solution has some drawbacks. For example, cost monotonicity is not met. Cost monotonicity means that if the cost of connecting a player to the source or other players increases, the player's share in the total cost will not decrease. For this reason, the researchers proposed several new (and more rational) cost allocation solutions. Dutta and Kar [43] proposed the DK (Dutta-Kar) solution that satisfies cost monotonicity. They improved Bird's solution by allowing the first selected player to exchange cost with the subsequently selected one when generating the minimum spanning tree using Prim's algorithm [38]. The DK solution satisfies cost monotonicity and belongs to the core. In addition to his solution, Bird [41] introduced the concept of an irreducible core. An irreducible core coincides with the core of the game corresponding to an irreducible graph. The game obtained from an irreducible graph is convex and, as a consequence, satisfies many good properties.

Another important solution is the so-called Folk solution; see works by Feltkamp et al., Bergantinos and Vidal-Puga [44; 45]. It is equal to the Shapley value of the corresponding game on an irreducible graph. Folk solutions satisfy some of the properties that Bird's solution does not, in particular solidarity, population monotonicity, and cost monotonicity. Here, solidarity means that as the total cost of the minimum spanning tree increases, the share of each player's cost will

not decrease. Population monotonicity means that when a new player is added, the cost shared by each player will not increase.

The third solution is called the cycle-complete solution, or Trudeau's solution [46]. A subset of the core, this solution also satisfies strict cost monotonicity, and can be computed in exponential time.

The Shapley value considered below is obtained by modifying the Shapley value in the dynamic game proposed by Kar [47], where the axiomatic description of the Shapley value for spanning tree games was presented. This dissertation examines the dynamic Shapley values constructed on this basis and discusses the nature of their stability in the context of cooperative stochastic spanning tree games. Also, see Li Yin's publications [31; 48; 49].

In addition, this dissertation explores a dynamic spanning forest game that generalizes the previous model. Rosenthal [50] first proposed a spanning forest game model in which there are two or more sources, and players must have a path to at least one source. Thus, the resulting network is not necessarily a tree. D. and F. Granot [51] introduced a fixed cost spanning forest game and established sufficient conditions for the existence of a non-empty core in the game. Li Yin's work [49] considered a cooperative stochastic spanning forest game in which a particular player leaves the game with a probability depending on the previous behavior of all players. Unlike Rosenthal's statement [50] with several identical sources, Li Yin's model [49] has several different sources, and each player needs to connect several sources according to their requirements. This assumption is widespread in real-world supply chain management problems. As demonstrated in [49], dynamic Shapley values constructed using the imputation distribution procedure satisfy the principle of time consistency under definite conditions.

In supply chain management problems, the dynamic game model with perishable goods is also actively used. In a dynamic spanning tree game with perishable goods, it is necessary to consider the rates of deterioration and loss in value when distributing such goods through transport and logistics networks. According to practical experience, the greater the transportation cost is, the higher the transportation speed will be; the better the protection of perishable goods is, the smaller the loss in value will be. Besides the minimum spanning tree cost, all these losses in value are part of the total cost on transport and logistics network. Current research into the logistics of perishable goods focuses on inventory management and pricing strategies, transport management, etc. Nahmias and Bakker [52; 53] surveyed the studies of

storage systems for perishable goods. X. Xu [54] analyzed the relationship between transit times for perishable goods and retailers' income. Li et al. [55] considered the problems of inventories and co-pricing under a random demand for perishable goods. Bogataj [56] showed that changes in transport temperatures and transit times for perishable goods affect the value in supply chain inventory management.

The following problems related to perishable goods were solved using static cooperative games: transport cooperation and cost allocation for perishable goods (see Li and Cai [57]), as well as the choice of transport equipment for perishable goods (see Li, Jun, and Cai [58]).

For the first time, cooperative stochastic games with perishable goods in the minimum cost spanning tree statement were investigated by Li Yin [48]. Time-consistent cooperative solutions of these games are studied in this dissertation.

In addition to cooperative stochastic spanning tree games, dynamic spanning tree games with complete information can be considered. In [59], Pankratova and Petrosyan examined dynamic n-player games of finite duration with transferable payoffs. More specifically, a new method for constructing characteristic functions was proposed: the value of this function for each coalition in a multistage game was determined through the values of the characteristic functions for the coalition in one-stage games. Also, the time consistency and strong time consistency of the core constructed using the new characteristic function were proved.

In this dissertation, a new characteristic function is considered. For each coalition, the value of this function is constructed using a similar approach in a game with complete information containing a spanning tree game. The new characteristic function depends on the a-matrix described above. As established below, under certain conditions, the new characteristic function satisfies strong time consistency for a subset of the core.

The development of spanning tree games with uncertainty has outlined two main lines of research.

The first line of research was initiated by Herzog et al. [60], who proposed the following model. Each network vertex can contain several players simultaneously, and all vertices are divided into two types—general and private. Further, the Montemanni model [61] reflected the random nature via the assumption that the communication cost on the network belongs to some intervals, unlike a fixed cost in spanning tree games. The problem with interval cost is complicated since

a minimum spanning tree cannot be built directly. In the cited study, the concept of relative robustness was suggested.

The second line of research on modeling networks with uncertain cost can be found in Suijs's paper [62]. It was assumed that network cost has two components: the cost of building and the cost of maintaining the network. Moreover, the first component can be considered deterministic, and the second component is usually stochastic.

In contrast to the existing research, this dissertation is based on the following assumption: the uncertainty of the minimum spanning tree in dynamic games manifests itself through a random change in the network depending on the players' behavior in the game, causing a random change in the network structure. Also, this dissertation examines cooperative solutions, and the imputation distribution procedure [18] is employed to design cooperative solutions satisfying time consistency under definite conditions.

Aim of this dissertation is to formalize and construct optimal strategies of players for finding the minimum total cost in a spanning tree game and construct cooperative solutions that satisfy time consistency.

For achieving these purposes, the following tasks are set and solved below:

1. To construct a two-stage spanning tree game with shock. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage.

2. To determine the cooperative behavior of all players in the two-stage spanning tree game with shock, find the values of the characteristic function for each coalition along the cooperative trajectory, and determine the imputation distribution procedure for constructing a dynamic Shapley value satisfying time consistency.

3. To construct a two-stage spanning tree game with shock for perishable goods based on existing models. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage and on the quantity of perishable goods he needs.

4. To determine the cooperative behavior of all players in the two-stage spanning tree game with perishable goods, find the values of the characteristic function for each coalition along the cooperative trajectory.

5. To study the problem of constructing a spanning tree with several sources and define a two-stage spanning forest game with shock. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage.

6. To determine the cooperative behavior of all players in the two-stage spanning forest game with shock, construct the characteristic function along the cooperative trajectory, and construct dynamic Shapley values satisfying time consistency in this game using the imputation distribution procedure.

7. To define a new a-matrix in the one-stage spanning tree game that can modify the network built by the players.

8. To construct a two-stage cooperative stochastic spanning tree game in which at the second stage the network is modified using the a-matrix with some probability depending on the behavior of all players at the first stage. For solving this task, the following subtasks are solved:

— To determine the cooperative behavior of all players in the two-stage cooperative stochastic spanning tree game. To construct the characteristic function and cooperative trajectory in this game. To construct a dynamic Shapley value satisfying time consistency using an imputation distribution procedure.

— To determine the cooperative behavior of all players in the two-stage cooperative stochastic spanning tree game. To construct characteristic functions along the cooperative trajectory. To construct a dynamic Nash bargaining solution satisfying time consistency using the imputation distribution procedure.

9. To construct an /-stage spanning tree game with complete information using the a-matrix. To determine the cooperative behavior of all players in this game, to construct characteristic functions and find their values for each coalition along the cooperative trajectory. To determine a new characteristic function in the multistage game based on the characteristic functions of the one-stage game. To construct the core satisfying strong time consistency based on the new characteristic function in this game.

Scientific novelty of this dissertation consists in the following:

1. A two-stage spanning tree game with shock is studied. For this game, an imputation distribution procedure is determined, and a dynamic Shapley value is constructed that satisfies time consistency.

2. A two-stage spanning tree game with shock for perishable goods is investigated.

3. A two-stage spanning forest game with shock is studied, and a dynamic Shapley vector is constructed using an imputation distribution procedure that satisfies time consistency.

4. A new a-matrix is determined to modify the network built by the players in a one-stage spanning tree game.

5. A two-stage cooperative stochastic spanning tree game is investigated. For this game, a dynamic Shapley value and a dynamic Nash bargaining solution are constructed using an imputation distribution procedure, both satisfying time consistency.

6. A multistage spanning tree game with complete information is studied. Based on the characteristic functions of one-stage games, a new characteristic function is constructed and then used to construct the core of the multistage game that satisfies strong time consistency.

Practical significance: The results of this dissertation are of practical importance. The mathematical model of designing a spanning tree or spanning forest network proposed by the author and his solution of the cost allocation problem for dynamic networks can be used in real applications for minimizing cost in economic and economic-social networks. For example, cost allocation issues commonly arise in transportation problems. A two-stage spanning tree game with shock and perishable goods can serve as a mathematical model for planning the transportation of perishable goods in dynamics. The mathematical models considered in this dissertation are also useful for analyzing the problems of building networks and allocating cost in other fields of human activity.

Methods and methodology: When conducting this research, the author relied on the methodology and used the methods of applied mathematics, combinatorial mathematics, optimization theory, and game theory, as well as other principles and research methods generally accepted in this area.

Thesis statements to be defended: The purpose of this dissertation is to formalize and construct optimal strategies of players, determine the minimum cost in a spanning tree game, and construct cooperative solutions satisfying time consistency. For achieving these purposes, the following results have been obtained:

1. A two-stage spanning tree game with shock has been constructed. At the second stage, a particular player leaves the game with some probability

depending on his position in the network built by all players at the first stage.

2. The cooperative behavior of all players in the two-stage spanning tree game with shock has been determined, and the characteristic function and the dynamic Shapley value satisfying time consistency have been constructed using the imputation distribution procedure.

3. Based on the applications described in the literature, a two-stage spanning tree game with shock and perishable goods has been constructed. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage, as well as on the quantity of perishable goods he needs.

4. The cooperative behavior of all players in the two-stage spanning tree game with perishable goods has been determined, and a characteristic function has been constructed.

5. The problem of several sources in the network has been considered, and a two-stage spanning forest game with shock has been constructed. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage.

6. The cooperative behavior of all players in the two-stage spanning forest game with shock has been determined. The characteristic function has been constructed, and the dynamic Shapley values satisfying time consistency in the game have been determined using the imputation distribution procedure.

7. A new a-matrix has been defined for modifying the network built by the players in the one-stage spanning tree game.

8. A two-stage cooperative stochastic spanning tree game has been defined. At the second stage of this game, the network is changed using the a-matrix with some probability depending on the joint behavior of all players at the first stage.

- The cooperative behavior of all players in the two-stage cooperative stochastic spanning tree game has been defined. In this game, a characteristic function has been constructed. In addition, a dynamic Shapley value satisfying time consistency has been constructed using an imputation distribution procedure.

- The cooperative behavior of all players in a two-stage cooperative stochastic spanning forest game has been defined. In this game, a characteristic function has been constructed. In addition, a dynamic Nash bargaining solution satisfying time consistency has been constructed using a payoff distribution procedure.

9. A /-stage spanning tree game with complete information has been defined using the a-matrix. The cooperative behavior of all players in this game has been determined, and the characteristic function has been constructed. A new characteristic function W has been defined based on the characteristic function of the one-stage game. The new characteristic function of the game has been adopted for constructing the core satisfying strong time consistency.

Publications: 6 papers have been published on the topic of the dissertation, including the ones [31; 48; 49; 63; 64] in journals and conference proceedings indexed by Scopus.

Reliability: The reliability of the results obtained is based on rigorous proof of all the formulated mathematical statements.

In the papers [31; 48; 49], the models of a two-stage spanning tree game with shock, a two-stage spanning forest game with shock, and a two-stage spanning tree game with perishable goods have been constructed, respectively. The dynamic Shap-ley values for these models have been constructed using an imputation distribution procedure. It has been shown that the corresponding dynamic Shapley values do not satisfy time consistency.

In the papers [63; 64], cooperative solutions in a spanning tree game have been generalized and transformed with application to different problems.

In the paper [32], a two-stage cooperative stochastic spanning tree game has been studied, and a Nash bargaining solution has been proposed. The time consistency of this solution has been ensured by introducing a Payoff Distribution Procedure (PDP).

Approbation: The main results of this dissertation have been presented at the following international conferences: Stability and Oscillations of Nonlinear Control Systems (Moscow, 2016), 29th Chinese Control and Decision Conference (CCDC) (China, 2017), Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of VF Demyanov) (St. Petersburg, 2017), and Game Theory and Management (St. Petersburg, 2019).

Personal contribution: All results submitted for defense are received personally by the author.

Scope and structure of the work. The dissertation consists of introduction, 3 chapters, conclusion. The full volume of the dessertation are 122 pagess, including 23 Figures and 3 Tables. The list of references contains 71 titles.

1. Chapter 1 provides definitions for a two-stage spanning tree game with shock, a two-stage spanning forest game with shock, and a two-stage spanning tree game with shock and perishable goods.

- Section 1.1 describes the one-stage spanning tree game.

- Section 1.2 describes the two-stage spanning tree game with shock. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage. The cooperative behavior of all players is determined. The characteristic function is calculated: its values for each coalition along the cooperative trajectory are found. An imputation distribution procedure can be used to construct a dynamic Shapley value satisfying time consistency.

- Section 1.3 describes a two-stage spanning tree game with shock and perishable goods. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage, as well as on the quantity of perishable goods he needs. The cooperative behavior of all players is determined. The characteristic function is calculated: its values for each coalition along the cooperative trajectory are found. An imputation distribution procedure can be used to construct a dynamic Shapley value satisfying time consistency.

- Section 1.4 describes the problem with several network sources and defines a two-stage spanning forest game with shock. At the second stage, a particular player leaves the game with some probability depending on his position in the network built by all players at the first stage. The cooperative behavior of all players in the two-stage spanning forest game with shock is determined, and the characteristic function is calculated: its values for each coalition along the cooperative trajectory are found, and a dynamic Shapley value

satisfying time consistency is constructed using an imputation distribution procedure.

2. Chapter 2 describes a two-stage cooperative stochastic spanning tree game. At the second stage of this game, the network changes with some probability using the a-matrix, which depends on the joint behavior of all players at the first stage. A dynamic Shapley value and a dynamic Nash arbitration scheme satisfying time consistency are determined using an imputation distribution procedure.

- Section 2.1 describes the game process and defines the cooperative behavior of all players. The characteristic function along the cooperative trajectory is determined, and the dynamic Shapley value that satisfies time consistency is constructed using an imputation distribution procedure.

- Section 2.2 describes the game process and defines the cooperative behavior of all players. The values of the characteristic function are calculated for each coalition along the cooperative trajectory, and a dynamic Nash bargaining solution that satisfies time consistency is constructed using a payoff distribution procedure.

3. Chapter 3 defines an /-stage spanning tree game with complete information.

- Section 3.1 defines a multistage spanning tree game with complete information and describes the game process.

- Section 3.2 defines the cooperative behavior of all players. Choosing their strategies, players build a minimum spanning tree at each stage. Based on the values of the characteristic function for each coalition in the subgames, a new characteristic function W is constructed. The core is determined using a new characteristic function, which can be treated as a new principle of optimality. This optimality principle has strong time consistency in the spanning tree game.

Chapter 1. Dynamic Shapley Value in Two-Stage Spanning Tree or

Forest Game with Shock

1.1 Main Definitions

This chapter considers the dynamic Shapley value in a two-stage spanning tree game. First of all, we describe the game model. When defining the two-stage game under consideration, we begin with the one-stage game, which is a spanning tree game. Following [31], let us introduce the main definitions and necessary background from graph theory.

Definition 1.1.1. Let N = {1,... ,n} be a finite set of players, {0} be a source, and N' = N U{0}.

Definition 1.1.2. A graph defined on the set N' will be denoted by G(N',E), where

E = {(i,j):(i,j) e L c N'}.

Definition 1.1.3. A pair (i,j) is called an edge in a graph G(N',E) if (i,j) e E,

Vi,j e N.

Definition 1.1.4. Two vertices i and j e N' are said to be connected in a graph G(N',E) if 3(M2), (i2,h), ..., (in-i,in) : (ik h+i) e G(N',E), 1 ^ k ^ n - 1, i\ = i, and in = j.

Definition 1.1.5. A graph G(N',E) is said to be connected on the set N' if any two vertices i,j e N' are connected in G(N', E).

Definition 1.1.6. The set of connected graphs on the set N' will be denoted by Q^'.

Definition 1.1.7. It is possible to associate with any i and j in a graph G(N',E) some cost Cij on the edge (i,j),i = j e N', where Cij = Cji e R+ and Vi e N' : Cn = The cost Cio = c0i on the edge (i, {0}),f e N, is a nonnegative constant.

Depending on the interpretation of the model, the cost on an edge (i,j) can be the consumption of some resource (e.g., fuel consumption when shipping a cargo from vertex i to vertex j) or the value of some service (e.g., the price of connecting vertex i to vertex j).

The cost on a graph G(N',E) can be represented as a cost matrix

C = {Cij }(n+1)x(n+1).

(1.1)

Note that a cost matrix is nonnegative and symmetric and has order (n +1) x (n + 1).

Example 1.1.1. Consider an example shown in Fig. 1.1. The red vertex 0 is the source, and the four vertices indicated by green numbers are the players. In this example, the graph is complete, and each edge has a specific cost.

Figure 1.1 — Cost on complete graph with four players.

The corresponding cost matrix is given by

0/ 1

C = {Cij }5x5 = 2

3

4

0

OG

1

6

V

6 +TO

3 8

15 5

11 10

2

3 8

4 12

3

15

5

4

9

4 11 10 12 9

, Vi,j e {0,1,2,3,4}

Definition 1.1.8. At each stage, player i chooses a strategy vector

Xi (Xi,l, . . . y^i^-i yTi,i+i, . . . ,Xi,n

where Xij G Xij denotes an action of player i against player j, Vi,j G N. Similarly, Xj,i G Xj,i is an action of player j against player i.

Definition 1.1.9. The cost on an edge (i,j) of a graph G(N',E) is defined in the following way:

Cij = C3l = fc{xi,j,Xjji), Qo = Co, > 0, Mi,j G N. (1.2)

where a function fc maps the set of all strategies of players i,j into the set R+ U of all admissible cost on the edges (i,j) G E.

In other words, the cost on an edge Cij = Cji is completely defined by the strategies xhj,Xj^ of players i,j, where Xij G Xij,Xj^ G Xjj,Vi,j G N. The cost on all edges between the players is defined by a given strategy profile x = (x1,...,xn). Note that Cx = {c^}(n+i)x(n+i) is a unique cost matrix constructed by Definition 1.1.9. Thus, for a cost matrix Cx = {c^}(n+1)x(n+1), there is a unique graph G(N',E) G Gn' on the set N'. Here Gn' denotes the set of all possible connected graphs on the set N'.

Figure 1.2 — Graphs with different cost on edges corresponding to different

strategies of players.

Example 1.1.2. Consider a three-player game. Let the function fc be fc(xi,j ,Xj,i) = Xi,j x Xj,i, where Xij e Xij, Xj,i e XjIf players 1-3 choose the strategy profiles

X1 = (x1,2,x1,3) = (3,10),^2 = (x2,1,x2,3) = (4,2),^3 = (x3,1,x3,2) = (1,2)

respectively, we easily calculate the cost on all edges between the players. In the left-hand part of Fig. 1.2, the red edges are obtained under the strategy profile (x1, x'2, x'3). For example, for edge (1,2), we have c12 = c21 = x\2 x x'2l = 3 x 4=12. When choosing the strategy profiles

X1 = (x1, 2,X1,3) = (5,1),X2 = (x2 , l,X2 , 3) = (5,2),x3 = (x3 ,1,X3,2) = (1,3),

the cost on all edges between the players varies. In the right-hand part of Fig. 1.2, the blue edges are obtained under the strategy profile (x'{,x%,x'3). For example, for edge (2,3), we have c23 = c32 = x'233 x x'322 = 2 x 3 = 6.

Definition 1.1.10. A minimum cost spanning tree on the set N' is the tree

T(N',CX) = arg min V cl3,

N (i,j)€G(N> ,E)

where Cx = {cij}(n+1)x(n+1) denotes a cost matrix on a graph G(N',E), which is uniquely defined by the strategy profile x = (x1,... ,xn). Here Qn> denotes the set of all possible connected graphs on the set N'.

Definition 1.1.11. The total cost on the edges of a minimum cost spanning tree T(N',CX) is given by

C [T (N',CX)] = £ q, .

(t,j)eT (N> , Cx )

Obviously, a graph with a minimum cost represents a tree. Otherwise, we would eliminate an extra edge to get a connected graph with a smaller cost.

Example 1.1.3. As an illustrative example, consider a one-stage three-player game. Let N = {1,2,3} be the set of players, {0} be the source, and N' = N U {0}. The corresponding graph on the set N' is shown in Fig. 1.3. Assume that edges (0,1), (0,2), and (0,3) are fixed, and the cost on these edges is c01 = c10 = 30, cq2 = c20 = 51, and Cq3 = c30 = 16, respectively. The function Cij = fc(xij ,Xjj) has the form fc(xij,xjii) = xhJ x Xjj, Vi,j G N.

All possible cost on the edges (i,j), Vi = j G {1,2,3}, is combined in Table 1. Here the red, green, and blue colors indicate different edges. Let X2,3 = {2,21} be the set of actions of player 2 against player 3, and X3,2 = {12,19} be the set of actions of player 3 against player 2, where x2,3 G X2,3 and x3,2 G X3,2. If player 1 chooses the action x2,3 = 21, and player 2 chooses the action x3,2 = 12, then the cost makes up c23 = fc(x2,3,x3,2) = 21 x 12 = 252.

Table 1 — All possible costs on edges under different actions of players

C12 ^2,1 C13 *3,1 C23 ^3,2

7 10 9 11 12 19

6 42 60 X13 3 27 33 ^2,3 2 24 39

17 119 170 15 135 165 21 252 399

Different strategies result in different cost matrices, and a minimum spanning tree can be obtained for each cost matrix. Assume that the players choose their strategies, and the strategy profile in the game is

xi = (^1,2,^1,3) = (6,3) ,x2 = (^2,1,^2,3) = (7,2),Z3 = (^3,1,^3,2) = (9,12).

The graph with cost corresponding to the strategy profile (9,12) is shown in Fig. 1.3.

i ! t

Figure 1.3 — Minimum cost spanning tree for graph constructed by players. The cost matrix takes the form

Ct. —

0 1 2 3

0 ^ œ 30 51 16 \

1 30 42 27

2 51 42 24

3 I16 27 24 /

After obtaining the cost matrix, the minimum cost spanning tree T(N',CX) on the graph consists of edges (0,3), (1,3), and (2,3); see dotted lines in Fig. 1.3. Therefore, the total cost in the minimum cost spanning tree T(N',CX) in the strategy profile x = (x\,x2,x3) is

C [T (N',CX)] = 67,

where xi = (x\,2,xi,3) = (6,3),X2 = (x2,i,x2,s) = (7,2),x3 = (xs\,xs,2) = (9,12).

Definition 1.1.12. A route in a tree T(N',CX) is a sequence of vertices il,i2,... ,%k and edges (ik,ik+i) for all k e [1,K — 1} and K e N+, K ^ 2. We say that this route passes the edges (ik,ik+\) and the vertices i\,i2,... ,%k. If a route il,i2,... ,%k in a tree T(N',CX) passes none of the edges (ik,ik+\) twice, it is called a path. In this case, vertex i\ is called the start vertex of the path, and vertex %k the end vertex of the path. In a tree T(N',CX), we denote by pi1iK a path from vertex i\ to vertex %k, and by Pm0 a path from any vertex m e N to the source {0}.

Definition 1.1.13. Vertex j is called a predecessor of vertex m if Pj0 ^ Pm0, where Pj0 is a path from the source {0} to vertex j in a tree T(N',CX), j e N.

Definition 1.1.14. Consider a tree T(N',CX). Assume that for any vertex m e N, a path Pm0 from the start vertex m to the end vertex {0} passes vertices m\,m2,... ,mx and edges (nik,mk+\), where k e [1,K — 1], m\ = m,mx = {0}, K e N+, and K ^ 2. Then vertex mk is called a direct predecessor of vertex mk+\. A direct predecessor of vertex m will be denoted by P(m). If the path includes only two vertices m and m', then P(m) = m'.

Definition 1.1.15. For any subtree T(S,C^) of a tree T(N',CX), S ^ N, consider vertex i e S. If after deleting this vertex i in the subtree T(S,C3), for all j e S\{f} the path Pj0 does not exist, then the set of all edges of the subtree T(S,C3) is called a branch in the tree T(N',CX). This set will be denoted by B\

Definition 1.1.16. Vertex i e N is said to be terminal in a tree T(N',CX) if there does not exist a vertex j e N \ {¿} such that P0i c P0j and P0j e T(N',CX).

Example 1.1.4. Consider an example in Fig. 1.4. Here {0} is the source in a spanning tree T(N',CX). The following facts can be established directly by definition. - All blue edges (0,j\), (j\,j2), (j2,j3) make a path Pm0 from the source {0} to vertex m.

— Each of the vertices j1,j2,j3 is a predecessor of vertex m. Moreover, vertex j3 is a direct predecessor of vertex m, i.e., P(m) = j3.

— Let S be the set of all red vertices, and m £ S. Then Bm is the set of all edges in the yellow domain.

Figure 1.4 — Path Pm0, direct predecessor of vertex m, predecessor of vertex m,

and branch Bm.

1.2 Dynamic Shapley value in two-stage spanning tree game

In the paper [31], a dynamic Shapley value was constructed for a two-stage spanning tree game. The cooperative behavior of the players was specified, and the values of the characteristic function and the dynamic Shapley value were determined along the cooperative trajectory using the Imputation Distribution Procedure (IDP).

1.2.1 Game description

Consider a group of players that have different geographic locations. Assume that a fixed cost between each player and the source is determined before the game starts. In other words, each player can directly connect to the source but the cost of connection is fixed.

Since the players choose different strategies, the cost on the edges established by them will differ. As a consequence, the cost in the spanning tree game will also differ. According to [42], different spanning tree games have different cost allocations.

Figure 1.5 — Diagram of game.

As shown in Fig. 1.5, player m £ N can leave the game after the first stage with a probability p, which depends on the previous behavior of the players. If player m leaves the game, the set of players changes. Otherwise (player m stays in the game), the game is repeated.

The optimal strategies for minimizing the cost in two-stage stochastic games were determined in the paper [16].

Provided that all players jointly choose their strategies to minimize the total expected cost, the value of the characteristic function for the set N was found as a solution of an optimization problem with cooperative strategies.

Now consider how the game runs at the first stage, and how the first stage of the game affects the second one.

Stage 1: At the first stage, the spanning tree game represents a simultaneous n-player game; see Fig. 1.5.

Definition 1.2.1. At the first stage in vertex z1} the players simultaneously choose their strategies in the form of the n-dimensional profiles

X1 - (X1 x1 )

tAJ - y^tX/ 1 • • • tAJ ^ J

X1 = (x1,1, • • • ,X1,i-1, X1,i+1, • • • ,X1,n), (1.3)

V* = j £ N,

where xjj £ Xfj denotes an action of player i against player ]•

According to Definition 1.1.9, at the first stage, players i and j choose their actions x) ■ and x]- from the finite sets X} ■ and X}-, respectively, and define some cost

'' U Jt'' '' ,J JT1

Cij = C3l = fc(x\3xli) on the edge (i,j). Then, a cost matrix Cxi = {cl3}(n+1)x(n+1) is formed on the graph G(N,E) using the strategy profiles (1.3). This process has been described in detail in Example 1.1.3. Stage 2:

Definition 1.2.2. If player m still participates in the game after the first stage in vertex z1, the spanning tree game evolves to the second stage in vertex z2; see Fig. 1.5. All players again (like at the first stage) simultaneously choose their strategies in the form of the n-dimensional profiles

2 = ( 2 2)

x — (x 1, • • • ,x ^),

2 = (2 2 2 2 ) (1 4)

xi = \xi,1, • • • iXi,i-1,Xi,i+1, • • • ,xi,n), (1.4)

v* = j £ N,

where xj^ G Xfj denotes an action of player i against player j.

Then the cost matrix Cx2 = {cij^«^^(n^), Vi = j G N is formed on the graph G(N',E) by the strategy profiles (1.4); see Definition 1.1.9.

Definition 1.2.3. If player m leaves the game, the set of players will be N \ {m}. The spanning tree game evolves to the second stage in vertex z3; see Fig. 1.5. All players, except player m, simultaneously choose their strategies in the form of the (n — 1)-dimensional profiles

\ S'rn \ — ( )

& \ {m} = (^1, . . . ,^m—1,^m+1, . . . ,^n),

Xi = (xi, 1, . . . ,xi, i—1 ,xi, i+1, . . . ,xi, n), (1.5)

Vi = j G N \{m},

where xf j G Xfj denotes an action of player i against player j.

Then the cost matrix Cx2\{m} = {cij}nxn, Vi = j G N \ {m} is formed on the graph G(N' \ {m},E) by the strategy profiles (1.5); see Definition 1.1.9.

Definition 1.2.4. The probability that player m will leave the game at the second stage is calculated as

_ i,j)eBm c'i-j

P = C[T(N',CX)],

where the minimum cost spanning tree T(N',CX) is given by Definition 1.1.10 on the graph G(N',E) constructed in the strategy profile x = (x1,... ,xn). Due to 1.1.15, Bm is a branch in T(N',CX).

According to this definition, the probability that player m will leave the game at the second stage is related to the spanning tree T(N',CX) obtained at the first stage. The greater total cost player m has on the branch Bm compared to C[T(N',CX)], the higher this probability will be. However, at the first stage in the tree T(N',CX), all players determine the strategy profile x. Thus, the probability that player m will leave the game at the second stage completely depends on the strategies of all players at the first stage. We give an illustrative example and calculate the probability that a player will leave the game in the tree T(N',CX).

Example 1.2.1. Consider a minimum cost spanning tree T(N',CX) in Fig. 1.6. The cost on the edges between player m and all other players is also indicated here. Then

Figure 1.6 — Probability that player m will leave game.

C [T (N',CX)] = C01 + C02 + C03 + C34 + c3m + cmb + cm6 + cml = 71, and the probability that player m will leave the game is

_ ,j)£Bm Cij _ Cm5 + Cm6 + Cm7 _ 22 QAQQ

p = c [T (N <A)] = 71 = 71 * U-3U99,

where x denotes the strategy profile in the game.

1.2.2 Characteristic function

Assume that in the two-stage game, the cost on the edges between the players is the sum of the corresponding cost at the first and second stages. Consider a cooperative version of the game in which all players jointly choose their strategies to minimize the expected total cost on the edges.

Let us define a characteristic function for the coalition N• Suppose that some path z'',z" is realized during the game. Performing transition from the one-stage game to the two-stage one, we define the mathematical expectation of the total cost

of all players. The strategy Xi() of player i e N is a mapping that assigns, for each stage of the game, a local strategy Xi to be chosen at this stage. Thus, Xi(z') = xj and Xi(z") = x2,i e N, x = (xl,x2).

Definition 1.2.5. The value of the characteristic function for the coalition N is given by

V j(N' ) = min{ C [T (N',Cxi)]

+ [pC[T(Nf \ {rn},Cx2\{m})] + (1 - p)C[T(N',Cx2)]] } = C[T(N',Cxi)] + [pC[T(N' \ {m},C,2\{m})] + (1 - p)C[T(N',CX2)]'

where p = ^^¡j^1^^. The strategies Xi(;),i e N, are said to be cooperative, and their set x(^) = (x\,... ,xn) is called a cooperative strategy profile.

Let S ^ N,S' = S U {0}. Bird [41] defined a characteristic function for the coalition S, V(S'), as the minimum total cost of connecting all players from S to the source, without the players from N \ S. In the four-player game in Fig. 1.7, the coalitions S and N \ S lie in the yellow and green domains, respectively. When considering the characteristic function for the coalition S, the players from the coalition N \ S in the green domain are not connected to the players from S and {0}.