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

Ли Инь

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

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

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

Дипломы

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

ID: 5a6f88247966e12684eea0ff

UUID: f452d91c-95cc-4ef2-a51a-80b4e94ab525

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

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

Просмотры: 12

Ли Инь

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

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

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

Скачать - 1,5 МБ

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

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

Оглавление Стр. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Глава 1. Определение многошаговой игры . . . . . . . . . . . . . . . 1.1 Условия временной состоятельности кооперативного решения . . 1.2 Пример временной временной несостоятельности кооперативного решения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Формула для временной состоятельности . . . . . . . . . . . . . . 1.4 Пример о временной состоятельности кооперативного решения с процедурой распределения выигрыша . . . . . . . . . . . . . . . . 7 10 Глава 2. Стратегическая поддержка Парето-оптимальных решений . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Существование ситуации равновесия по Нэшу в стратегиях наказания с ПРВ . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Теорема о стратегической поддержке Парето-оптимальных решений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Пример Стратегической поддержки Парето-оптимальных решений. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава 3. Построение сильно динамически устойчивого кооперативных играх с полной информацией 3.1 Динамическое ядро . . . . . . . . . . . . . . . . . . . . 3.2 Пример динамического ядра . . . . . . . . . . . . . . 3.3 Упрощение динамического ядра . . . . . . . . . . . . 12 15 18 . . . . 24 . . . . 26 . . . . 27 . . . . 30 ядра в . . . . . . . . . . . . . . . . . . . . . . . . 36 38 40 42 Глава 4. Динамический Вектор Шепли в игре с остовным деревом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Построение двухшаговой игры с минимальным остовным деревом 4.2 Динамической устойчивости . . . . . . . . . . . . . . . . . . . . . 44 44 45 Глава 5. Многошаговая игра с остовным деревом . . . . . . . . . . 48 2 . . . .

5.1 Определение многошаговой игры с остовным деревом . . . . . . 5.2 Временная состоятельность кооперативного решения (оптимальность по Парето) . . . . . . . . . . . . . . . . . . . . . 5.3 Пример временной несостоятельности кооперативного решения 5.4 Пример временной состоятельности кооперативного решения с процедурой распределения выигрыша (ПРВ) . . . . . . . . . . . . 48 . . 52 53 . 58 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Публикации по теме диссертации . . . . . . . . . . . . . . . . . . . . 67 3

Введение В данной диссертации мы исследуем временную состоятельность и представляем формулу для процедуры распределения выигрыша в многошаговой игре кооперации. С помощью формулы процедуры распределения выигрыша в многошаговой игре кооперации мы исследуем пример, чтобы каждый игрок удовлетворил условию индивидуальной рациональности. Далее построим стратегии наказания. Потому что некоторые игроки обращаются к иррациональному поведению. Мы используем стратегии наказания и накажем их. С помощью стратегий наказания мы построим теорему 2 и докажем, что существует равновесие по Нэшу, в котором выигрыш равен выигрышу вдоль оптимальной траектории по Парето. Далее мы исследуем сильную динамическую устойчивость принципов оптимальности в многошаговых кооперативных играх с полной информацией. С помощью понятия процедуры распределения дележа построено динамическое ядро и доказывается его сильная динамическая устойчивость. Из-за сложности построения динамического ядра предложно его упрощение, которое существенно уменьшает объём вычислений. В ряде случаев упрощенное динамическое ядро принадлежит динамическому ядру. Далее, мы исследуем динамический Вектор Шепли в двухшаговой игре с минимальным остовным деревом. На каждом шаге игроки строят минимальное остовное дерево, и вычисляется Вектор Шепли. На втором шаге один из игроков выбывает из игры с вероятностью 𝑝, зависящей от предыдущих стратегий игроков. Используя процедуру распределения дележа проводится регуляризация исходной игры. В конце мы исследуем временную состоятельность для процедуры распределения выигрыша в многошаговой игре кооперации с остовным деревом. Предполагается, что на каждом ребре и в каждой окончательной позиции происходит игра 𝑛-лиц с остовным деревом. С помощью формулы процедуры распределения выигрыша в многошаговой игре кооперации мы исследуем пример, в котором каждый игрок удовлетворяет условию индивидуальной рациональности. Теорию математических моделей принятия оптимальных решений принято называть исследованием операций, поэтому теорию игр можно рассматривать как составную часть исследования операций. [1] 4

Кооперативные игры предполагают собой способность расширения выгоды участников в ситуациях, включающих в себя стратегические взаимодействия. Различные типы кооперативных решений предлагались:устойчивое множество (фон Нейман и Моргенштерн 1954г. ), решение Нэша для переговоров (1950г., 1953 г. ). Индивидуальная рациональность- это основное свойство кооперативных игр. Это значит, что выигрыши, получаемые каждым игроком в кооперативной игре, не меньше, чем выигрыши, получаемые в изначальной некооперативной игре. И выигрыши всех игроков в кооперативных играх должны удовлетворять условиям – эффективности по Парето. Эффективность по Парето гарантирует, что любой игрок не может повысить свои выигрыши без снижения выигрышей других игроков. Кооперация - это одно из основных форм человеческого поведения. Поэтому по многим практическим причинам нам нужно исследовать кооперацию, чтобы она была устойчивой на всей траектории её реализации в многошаговой игре кооперации. В данной диссертации мы исследуем временную состоятельность в многошаговой игре кооперации. см..Петросян (1979 г.) [2], Петросян и Зенкевич (1996 г.), Yeung и Петросян (2004 г. и 2006 г.) [3]. Исследования Петросяна (1979 г.) предлагают метод, с помощью которого легко исследовать временную состоятельность. Мы предполагаем, что если игрок в любой момент кооперации отклоняется от оптимальной траектории, то кооперация будет нарушаться и игроки используют стратегии как в случае антагонистической игры. Мы предоставляем формулу процедуры распределения выигрыша для того, чтобы никто не захотел отклоняться от оптимальной траектории в многошаговой игре кооперации с полной информацией. Однако в многошаговой игре кооперации с полной информацией игрок может обратиться к иррациональному поведению с целью вымогательства дополнительных выгод, если дальшейшая ситуация позволяет. Это почему мы построить стратегии наказания и накажем их. Сначала мы представляем основные понятия кооперативной многошаговой игры с полной информацией и временной состоятельности (динамической устойчивости) в многошаговой игре кооперации. Далее приведём пример о временной несостоятельности. Чтобы решить эту проблему, мы представляем формулу для процедуры распределения выигрыша в многошаговой игре коопера5

ции. 𝛽𝑖𝑘 = 𝐻𝑖 (𝑧0 ) − 𝑉 𝑖 (𝑧0 ; {𝑖}, 𝑁/{𝑖}) − [𝑉 𝑖 (𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖}) − 𝑉 𝑖 (𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})] 𝑙+1 where 𝛽𝑖𝑘 - это процедура распределения выигрыш (ПРВ) в игре Γ𝑧0 . 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︀ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑙) - выигрыш игрока 𝑖, вдоль оптимальной по Парето траек𝑘=0 тория 𝑧¯ = (𝑧1 , . . . , 𝑧𝑙 ). 𝑉 𝑖 (𝑧𝑘 ; {𝑖}, 𝑁/{𝑖}) - характеристическая функция в игре, которая исходная позиция 𝑧𝑘 . 𝑙 - длины игры, под которым будем понимать длину наибольшего пути в графе. Потом мы выводим эту формулу процедуры распределения выигрыша в многошаговой игре кооперации.(формула для 𝛽𝑖𝑘 ) Эта формула выводится в теореме 1 в данной диссертации. С помощью формулы процедуры распределения выигрыша в многошаговой игре кооперации мы пересматриваем и снова исследуем пример 1, чтобы каждый игрок удовлетворил условию индивидуальной рациональности. При исследовании многошаговых неантагонистических игр с полной информацией можно выявить множество ситуаций равновесия, сужения которых не всегда являются ситуациями равновесия во всех подыграх исходной игры. К числу таких ситуаций равновесия относятся равновесия в стратегиях наказания. [4] Мы составляем стратегию наказания с помощью теоремы для того, чтобы доказать, что существует равновесие по Нэшу, в котором выигрыш равен выигрышу вдоль оптимальной траектории по Парето. Потом приводим пример 2. В второй главе исследуем сильную динамическую устойчивость принципов оптимальности в многошаговых кооперативных играх с полной информацией. Сильная динамическая устойчивость была определена и исследована в работе [8]. Используя результаты этой работы, введём основные понятия. Определим процедуру распределения дележа (ПРД) 𝛽𝑖𝑘 (𝛽𝑖𝑘 — выплаты игроку 𝑖 на шаге 𝑘 игры Γ𝑧0 ) и сильную динамическую устойчивость. В четвёртой главе исследуем динамический Вектор Шепли в двухшаговой игре с минимальным остовным деревом. В пятой главе исследуем многошаговую игру с остовным деревом. 6

Глава 1. Определение многошаговой игры Определение. Кооперативная игра в развёрнутой форме с полной информацией Γ = (𝑁, {𝑈𝑖 }𝑖∈𝑁 , {𝐾𝑖 }𝑖∈𝑁 ), где 𝑁 = {1, . . . , 𝑖, . . . , 𝑁 } - множество игроков, 𝑈𝑖 - множество стратегий игрока - 𝑖, 𝐾𝑖 - функция выигрыша игрока 𝑖 [4]. Определение. Пусть 𝑋 - множество вершины дерева игры, Γ = (𝑁, {𝑈𝑖 }𝑖∈𝑁 , {𝐾𝑖 }𝑖∈𝑁 ) игра на древовидном конечном графе. Определение. Пусть 𝐹 - отображение 𝑋 в 𝑋, и 𝐴 ⊂ 𝑋. Под образом множества 𝐴 будем понимать множество 𝐹 (𝐴) = ∪𝑥∈𝐴 𝐹𝑥 . Полагаем 𝐹 (∅) = ∅. Можно убедиться в том, что если 𝐴𝑖 ⊂ 𝑋, 𝑖 = 1, . . . , 𝑛, то 𝑛 𝑛 𝑛 𝑛 ⋃︁ ⋃︁ ⋃︁ ⋂︁ 𝐹 ( 𝐴𝑖 ) = 𝐹 (𝐴𝑖 ), 𝐹 ( 𝐴𝑖 ) ⊂ 𝐹 (𝐴𝑖 ) 𝑖=1 𝑖=1 𝑖=1 𝑖=1 Определение. Рассмотрим разбиение множества вершин 𝑋 на 𝑛+1 множество 𝑋1 , 𝑋2 , 𝑋3 . . . , 𝑋𝑛 , 𝑋𝑛+1 , 𝑛+1 ∪ 𝑋𝑖 = 𝑋, 𝑋𝑘 ∩ 𝑋𝑙 = ∅, 𝑘 ̸= 𝑙 𝑖=1 здесь 𝐹𝑥 = ∅, 𝑥 ∈ 𝑋𝑛+1 . 𝑋𝑖 - это множество очередности игрока 𝑖. 𝑋𝑛+1 - это множество окончательное позиций. Определение. Пара (𝑋, 𝐹 ) называется графом, если 𝑋 - некоторое конечное множество, а 𝐹 - отображение 𝑋 в 𝑋. Граф (𝑋, 𝐹 ) будем обозначать символом 𝐺. В дальнейшем элементы множества 𝑋 будем изображать точками на плоскости, а пары точек 𝑥 и 𝑦, для которых 𝑦 ∈ 𝐹𝑥 , соединять непрерывной линией со стрелкой, направленной от 𝑥 к 𝑦. Тогда каждый элемент множества 𝑋 называется вершиной или узлом графа, а пара элементов (𝑥, 𝑦), в которой 𝑦 ∈ 𝐹𝑥 - ребром графа. Для ребра 𝑝 = (𝑥, 𝑦) вершины 𝑥 и 𝑦 называются граничными вершинами ребра, причем 𝑥 - начало, а 𝑦 - конец дуги. [4] Вершина 𝑦, которая находится непосредственно после позиции 𝑥, называется альтернативой в позиции 𝑥 (𝑦 ∈ 𝐹𝑥 ). 7

Определение. Пусть кооперативная игра Γ = (𝑁, {𝑈𝑖 }𝑖∈𝑁 , {𝐾𝑖 }𝑖∈𝑁 ) в развёрнутой форме с полной информацией имеет вид древовидного графа 𝐺(𝑋, 𝐹 ), где 𝑖 ∈ 𝑁 . Для каждого 𝑥 ∈ / 𝑋𝑛+1 и 𝑦 ∈ 𝐹𝑥 определен ребро (𝑥,𝑦) в древовидном графе 𝐺(𝑋, 𝐹 ). На каждом ребре (𝑥,𝑦) определены 𝑛 действительных чисел ℎ𝑖 (𝑥,𝑦), 𝑖 = 1, . . . ,𝑛, ℎ𝑖 ≥ 0 (выигрыш 𝑖-го игрока на ребре (𝑥,𝑦)), и для каждой окончательной позиций 𝑥 ∈ 𝑋𝑛+1 определены 𝑔𝑖 (𝑥) ≥ 0, 𝑖 = 1, . . . ,𝑛. Определение. Будем предполагать, что для каждого пути игры 𝑧 = (𝑧0 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ), 𝑘 ∈ {0, 1, . . . , 𝑛}, 𝑧𝑙 ∈ 𝑋𝑛+1 выигрыш 𝑖-го игрока определяется как 𝑙−1 ∑︁ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ), ℎ𝑖 ≥ 0, 𝑔𝑖 ≥ 0 𝐻𝑖 (𝑧0 ) = 𝑘=0 Определение. Если 𝑧 = (𝑧0 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 путь реализованный ситуацией 𝑢(·) = (𝑢1 , . . . , 𝑢𝑖 , . . . , 𝑢𝑛 ), 𝑖 ∈ 𝑁 , и существует соответственный 𝑛 ∑︀ вектор весов 𝛼 = (𝛼1 , . . . , 𝛼𝑛 ) и 𝛼𝑖 = 1, 𝛼𝑖 ≥ 0, такой, что max 𝑛 (︂ ∑︁ 𝑙−1 ∑︁ 𝑧0 ,...,𝑧𝑘 ,...,𝑧𝑙 𝑖=1 𝑖=1 )︂ ∑︁ )︂ 𝑛 (︂ ∑︁ 𝑙−1 𝛼𝑖 ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝛼𝑖 𝑔𝑖 (𝑧𝑙 ) = 𝛼𝑖 ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝛼𝑖 𝑔𝑖 (¯ 𝑧𝑙 ) 𝑖=1 𝑘=0 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 , 𝑧𝑙 ∈ 𝑋𝑛+1 , 𝑛 ∑︁ 𝑘=0 𝛼𝑖 = 1, 𝛼𝑖 > 0, ℎ𝑖 ≥ 0, 𝑔𝑖 ≥ 0 𝑖=1 Игра Γ𝑧0 развивается вдоль траектории 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ), 𝑧¯𝑙 ∈ 𝑋𝑛+1 , которую будем назывется оптимальной траекторией. Определение. Для игры Γ𝑧0 набор стратегий 𝑢¯(·) = (¯ 𝑢1 , . . . , 𝑢¯𝑖 , . . . , 𝑢¯𝑛 ), 𝑖 ∈ 𝑁 , соответствует пути 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ), 𝑧¯𝑙 ∈ 𝑋𝑛+1 . Выигрыш игрока 𝑖 в Γ𝑧0 : 𝑙−1 ∑︁ 𝐻𝑖 (𝑧0 ) = ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) 𝑘=0 ∀𝑖 ∈ 𝑁, 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 , 𝑧𝑙 ∈ 𝑋𝑛+1 , ℎ𝑖 ≥ 0, 𝑔𝑖 ≥ 0 8

Определение. 𝛽𝑖𝑘 - это процедура распределения выигрыша (ПРВ). То. 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︁ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ) = 𝑙 ∑︁ 𝑘=0 𝑘=0 9 𝛽𝑖𝑘

1.1 Условия временной состоятельности кооперативного решения Пусть вектор значений игр 𝑉 𝑖 (𝑧0 ; {𝑖}, 𝑁/{𝑖}) в антагонистической игре 2 игроков Γ(𝑧0 ; {𝑖}, 𝑁/{𝑖}), игроки {𝑖}, 𝑁/{𝑖}, в которой игре игрок 𝑖 играет против игрока 𝑁/{𝑖}. Т.е. 𝑉 𝑁/{𝑖} (𝑧0 ; {𝑖}, 𝑁/{𝑖}) = −𝑉 𝑖 (𝑧0 ; {𝑖}, 𝑁/{𝑖}) Пусть 𝑉 𝑖 (𝑧𝑘 ; {𝑖}, 𝑁/{𝑖}), 𝑉 𝑖 (𝑧𝑘 ) - значения подыгр в которой исходная позиция подыгры в 𝑧𝑘 , 𝑘 = 1, . . . ,𝑙. То значение игр в играх Γ(𝑧0 ; {𝑖}, 𝑁/{𝑖}). 𝑉 1 (𝑧0 ; {1}, 𝑁/{1}), 𝑉 2 (𝑧0 ; {2}, 𝑁/{2}), . . . , 𝑉 𝑖 (𝑧0 ; {𝑖}, 𝑁/{𝑖}), ∀𝑖 ∈ 𝑁 В игре Γ𝑧0 , должно выполняться условие 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︁ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ) ≥ 𝑉 𝑖 (𝑧0 ; {𝑖}, 𝑁/{𝑖})] 𝑘=0 (условие индивидуальной рациональности) Игра Γ𝑧0 развивается вдоль оптимальной траектории 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ), 𝑧¯𝑙 ∈ 𝑋𝑛+1 Для выполнения определения условия временной состоятельности, должно выполняться условие 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) ≥ 𝑉 𝑖 (¯ 𝑧1 ; {𝑖}, 𝑁/{𝑖}) 𝑘=1 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) ≥ 𝑉 𝑖 (¯ 𝑧2 ; {𝑖}, 𝑁/{𝑖}) 𝑘=2 ... 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) ≥ 𝑉 𝑖 (¯ 𝑧𝑚 ; {𝑖}, 𝑁/{𝑖}) 𝑘=𝑚 ... 10

𝑔𝑖 (¯ 𝑧𝑙 ) ≥ 𝑉 𝑖 (¯ 𝑧𝑙 ; {𝑖}, 𝑁/{𝑖}) 𝑚 ∈ {1, 2, . . . , 𝑙 − 1} Т.К. если это не имеет место, то игроки может быть отклонятся от ранее выбранной траектории; Если 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) < 𝑉 𝑖 (¯ 𝑧𝑚 ; {𝑖}, 𝑁/{𝑖})], 𝑚 ∈ {0, 1, . . . , 𝑙} 𝑘=𝑚 для некоторых 𝑖 ∈ 𝑁 . Это временная несостоятельность решения. Здесь 𝑧¯𝑘 ∈ / 𝑋𝑛+1 , 𝑧¯𝑘+1 ∈ 𝐹𝑧¯𝑘 , 𝑧¯𝑙 ∈ 𝑋𝑛+1 , ℎ𝑖 ≥ 0, 𝑔𝑖 ≥ 0 11

1.2 Пример временной временной несостоятельности кооперативного решения Пример 1. Пусть кооперативная многошаговая игра Γ𝑧0 с полной информацией. Игроки 𝑁 = {1, 2}. Обозначаем вершины где ходит игрок 1 через кольцо, и вершины где ходит игрок 2 прямоугольником. Стратегии игроков 𝑖 - 𝑢𝑧𝑖 0 , 𝑖 ∈ {1, 2}, ситуация 𝑢 = {𝑢𝑧10 , 𝑢𝑧20 }, соответствующая траектория (𝑧0 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ). 𝑙−1 ∑︀ Выигрыши игроков 𝑖 - 𝐻𝑖 (𝑧0 ) = ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ). Пусть вектор весов 𝑘=0 1 2, тогда для оптимальной по Парето траектории выполняется 𝑧¯ = 𝛼1 = 𝛼2 = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ). max 𝛼1 (︂ ∑︁ 𝑙−1 𝑘=0 )︂ (︂ ∑︁ )︂ 𝑙−1 1 ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧𝑙 ) + 𝛼2 ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧𝑙 ) , 𝛼1 = 𝛼2 = 2 𝑘=0 Рисунок 1.1 Нашли что оптимальная по Парето траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ). Т.к. 1 max × 2 (︂ ∑︁ 3 𝑘=0 )︂ (︂ ∑︁ )︂ 3 1 ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) + × ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 ) = 2 𝑘=0 = 1 1 × 8 + × 5 = 6.5 2 2 Т.е. 𝐻1 (𝑧0 ) = 3 ∑︁ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 4 + 0 + 1 + 0 + 3 = 8 𝑘=0 12

𝐻2 (𝑧0 ) = 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 ) = 0 + 1 + 0 + 1 + 3 = 5 𝑘=0 В этой игре Значение игры для игрока 1: 𝑉 1 (𝑧0 ) = 5 , и 𝐻1 (𝑧0 ) = 3 ∑︁ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 4 + 0 + 1 + 0 + 3 = 8 ≥ 𝑉 1 (𝑧0 ) = 5 𝑘=0 Значение игры для игрока 2: 𝑉 2 (𝑧0 ) = 1, и 𝐻2 (𝑧0 ) = 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 ) = 0 + 1 + 0 + 1 + 3 = 5 ≥ 𝑉 2 (𝑧0 ) = 1 𝑘=0 Оптимальная по Парето траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ). Продолжаем исследовать подыгру Γ𝑧1 - исходная позиция игры в 𝑧1 Рисунок 1.2 Значение подыгры для игрока 1: 𝑉 1 (𝑧1 ) = 0 , и 3 ∑︁ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 0 + 1 + 0 + 3 = 4 ≥ 𝑉 1 (𝑧1 ) = 0 𝑘=1 Значение подыгры для игрока 2: 𝑉 2 (𝑧1 ) = 6, и 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 ) = 1 + 0 + 1 + 3 = 5 < 𝑉 2 (𝑧1 ) = 6 𝑘=1 Т.е. на оптимальной траектории 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето имеет место временная несостоятельность. 13

Т. к. Существует 𝑚 ∈ {0, 1, . . . , 𝑙}, такой что 𝑙−1 ∑︁ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ) < 𝑉 𝑖 (𝑧𝑚 ; {𝑖}, 𝑁/{𝑖}) 𝑘=𝑚 где 𝑧𝑙 ∈ 𝑋𝑛+1 , 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 . 14

1.3 Формула для временной состоятельности Мы представляем ПРВ 𝛽𝑖𝑘 , чтобы решать это вопрос. Из определения процедура распределения выигрыша, 𝛽𝑖𝑘 (ПРВ) должна удовлетворять следующим условиям 𝑙 ∑︁ 𝛽𝑖𝑘 ≥ 𝑉 𝑖 (𝑧1 ; {𝑖}, 𝑁/{𝑖}) 𝑘=1 𝑙 ∑︁ 𝛽𝑖𝑘 ≥ 𝑉 𝑖 (𝑧2 ; {𝑖}, 𝑁/{𝑖}) (1.1) 𝑘=2 ... Вдоль траектории оптимальной по Парето Теорема 1. Пусть 𝛽𝑖𝑘 ПРВ в Γ𝑧0 , и 𝛽𝑖𝑘 = 𝐻𝑖 (¯ 𝑧0 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) − [𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖}) − 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})] 𝑙+1 (1.2) здесь 𝐻𝑖 (¯ 𝑧0 ) = 𝑙−1 ∑︀ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ). Вдоль оптимальной траектории 𝑧¯ = 𝑘=0 (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ) по Парето, тогда она удовлетворяет условию 1.1. Доказательство: 𝛽𝑖𝑘 𝐻𝑖 (¯ 𝑧0 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) − [𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖})− = 𝑙+1 𝑙−1 ∑︀ −𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})] = ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑘=0 𝑙+1 −[𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖}) − 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})] 15 −

𝑙 ∑︁ 𝑙 (︂ ∑︁ 𝛽𝑖𝑘 = 𝑙−1 ∑︀ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑘=0 𝑘=0 𝑘=0 − 𝑙+1 )︂ −[𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖}) − 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})] = 𝑙−1 ∑︀ = ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑙 ∑︁ 𝑘=0 𝑙+1 𝑘=0 − 𝑙 ∑︁ − [𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖}) − 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})] = 𝑘=0 𝑙−1 ∑︀ = ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑙 ∑︁ 𝑘=0 𝑙+1 𝑘=0 − [︂ ∑︁ 𝑙 𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖}) − 𝑘=0 = 𝑙 ∑︁ 𝑙 ∑︁ − ]︂ 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖}) = 𝑘=0 𝑙−1 ∑︀ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑘=0 − 𝑙+1 𝑘=0 −[𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖}) + 𝑉 𝑖 (¯ 𝑧𝑘+2 ; {𝑖}, 𝑁/{𝑖}) + · · · + +𝑉 𝑖 (¯ 𝑧𝑙 ; {𝑖}, 𝑁/{𝑖}) − 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖}) − 𝑉 𝑖 (¯ 𝑧𝑘+1 ; {𝑖}, 𝑁/{𝑖})− − · · · − 𝑉 𝑖 (𝑧𝑙 ; {𝑖}, 𝑁/{𝑖})] = = 𝑙 ∑︁ 𝑙−1 ∑︀ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑘=0 − 𝑙+1 𝑘=0 𝑙−1 ∑︀ −[−𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})] = ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑙 ∑︁ 𝑘=0 𝑙+1 𝑘=0 +𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})) ≥ 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})) 16 +

Так как 𝑙−1 ∑︀ = ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑙 ∑︁ 𝑘=0 𝑙+1 𝑘=0 ≥0 То 𝑙 ∑︁ 𝑘=0 𝑙−1 ∑︀ 𝛽𝑖𝑘 = ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) − 𝑉 𝑖 (¯ 𝑧0 ; {𝑖}, 𝑁/{𝑖}) 𝑙 ∑︁ 𝑘=0 𝑙+1 𝑘=0 +𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})) ≥ 𝑉 𝑖 (¯ 𝑧𝑘 ; {𝑖}, 𝑁/{𝑖})) Т.е. 𝑙 ∑︁ 𝛽𝑖𝑘 ≥ 𝑉 𝑖 (¯ 𝑧𝑚 ; {𝑖}, 𝑁/{𝑖})); 𝑚 = 0, 1, . . . , 𝑙 𝑘=𝑚 17 +

1.4 Пример о временной состоятельности кооперативного решения с процедурой распределения выигрыша Введём ПРВ и проверим предыдущий пример, чтобы индивидуальная рациональность выполнялась для всех игроков. В игре Γ𝑧0 , пусть игроки 𝑁 = {1, 2}. Выигрыши игроков 𝑖: 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︀ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ), 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 , 𝑧𝑙 ∈ 𝑋𝑛+1 . 𝑘=0 Вектор весов 𝛼1 = 𝛼2 = 12 , т.е. 𝑧¯ = (𝑧0 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ) выполняется на оптимальной по Парето траектории max 𝛼1 (︂ ∑︁ 𝑙−1 )︂ (︂ ∑︁ )︂ 𝑙−1 ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧𝑙 ) + 𝛼2 ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧𝑙 ) 𝑘=0 𝑘=0 Нашли, что в этой игре Γ𝑧0 на оптимальной по Парето траектории 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) 𝐻1 (𝑧0 ) = 3 ∑︁ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 8, 𝐻2 (𝑧0 ) = 𝑘=0 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 ) = 5 𝑘=0 Теперь мы найдём значение игры 𝑉 1 (𝑧𝑘 ) и 𝑉 2 (𝑧𝑘 ) в антагонистическом игре двух игроков 𝑉 (𝑧0 ; {1}, {2})). 𝑘 = 0, 1, 2, 3, 4 Далее мы обозначаем 𝑉 𝑖 (𝑧𝑘 ; {1}, {2}) упрощённым образом через 𝑉 𝑖 (𝑧𝑘 ) 𝑘 ∈ {0, . . . , 1, . . . , 𝑙}, 𝑖 ∈ 𝑁 . Случай 1. В игре 𝑧0 . Как показано на рисунке 1.3. Рисунок 1.3 Тогда значение игры: Для игрока 1: 𝑉 1 (𝑧0 ) = 5, 18

Для игрока 2: 𝑉 2 (𝑧0 ) = 1. Случай 2. В подыгре Γ𝑧1 , в этой игре исходная позиция 𝑧1 . Как показано на рисунке 1.4. Рисунок 1.4 Тогда значение игры: Для игрока 1: 𝑉 1 (𝑧1 ) = 0, Для игрока 2: 𝑉 2 (𝑧1 ) = 6. Случай 3. В подыгре Γ𝑧2 , в этой игре исходная позиция игры 𝑧2 . Как показано на рисунке 1.5. Рисунок 1.5 Тогда значение игры: Для игрока 1: 𝑉 1 (𝑧2 ) = 3, Для игрока 2: 𝑉 2 (𝑧2 ) = 3. Случай 4. В подыгре Γ𝑧3 , в этой игре исходная позиция игры 𝑧3 . Как показано на рисунке 1.6. Тогда значение игры: Для игрока 1: 𝑉 1 (𝑧3 ) = 2, Для игрока 2: 𝑉 2 (𝑧3 ) = 4. Случай 5. При этом на множестве окончательном позиций Тогда значение игры: 19

Рисунок 1.6 Для игрока 1: 𝑉 1 (¯ 𝑧4 ) = 3, Для игрока 2: 𝑉 2 (¯ 𝑧4 ) = 3. Используем теорему 1 (1.2). 𝛽𝑖𝑘 = 𝐻𝑖 (𝑧0 ) − 𝑉 𝑖 (𝑧0 ; {1}, {2}) − [𝑉 𝑖 (𝑧𝑘+1 ; {1}, {2}) − 𝑉 𝑖 (𝑧𝑘 ; {1}, {2})] 𝑙+1 (1.3) здесь 𝛽𝑖𝑘 процедура распределения выигрыш (ПРВ) в Γ𝑧0 , 𝑖 ∈ {1, 2}, 𝐻𝑖 (𝑧0 ) = 3 ∑︀ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧4 ). 𝑘 ∈ {0, 1, 2, 3, 4}. 𝑘=0 По оптимальной траектории 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето Для игрока 1 𝛽10 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 8−5 = − [𝑉 1 (𝑧1 ) − 𝑉 1 (𝑧0 )] = − [0 − 5] = 5.6 5 5 8−5 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) − [𝑉 1 (𝑧2 ) − 𝑉 1 (𝑧1 )] = − [3 − 0] = −2.4 5 5 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 8−5 𝛽12 = − [𝑉 1 (𝑧3 ) − 𝑉 1 (𝑧2 )] = − [2 − 3] = 1.6 5 5 8−5 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 3 𝛽1 = − [𝑉 1 (𝑧4 ) − 𝑉 1 (𝑧3 )] = − [3 − 2] = −0.4 5 5 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 8−5 4 𝛽1 = − [0 − 𝑉 1 (𝑧4 )] = − [0 − 3] = 3.6 5 5 Для игрока 2 𝛽11 = 𝛽20 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 5−1 = − [𝑉 1 (𝑧1 ) − 𝑉 2 (𝑧0 )] = − [6 − 1] = −4.2 5 5 𝛽21 = 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 5−1 − [𝑉 1 (𝑧2 ) − 𝑉 2 (𝑧1 )] = − [3 − 6] = 3.8 5 5 20

𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 5−1 = − [𝑉 1 (𝑧3 ) − 𝑉 2 (𝑧2 )] = − [4 − 3] = −0.2 5 5 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 5−1 3 𝛽2 = − [𝑉 1 (𝑧4 ) − 𝑉 2 (𝑧3 )] = − [3 − 4] = 1.8 5 5 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 5−1 4 𝛽2 = − [0 − 𝑉 2 (𝑧4 )] = − [0 − 3] = 3.8 5 5 𝛽22 С помощью 𝛽𝑖𝑘 , 𝑖 ∈ {1, 2}, 𝑘 ∈ {0, 1, 2, 3, 4} (ПРВ) мы построим новую игру Γ′𝑧0 . Случай 1. Как показано на рисунке 1.7. Рисунок 1.7 Найдём значение игры 𝑉 1 (𝑧0 ) и 𝑉 2 (𝑧0 ) в антагонистической игре 2-х игроков Γ′𝑧0 . Значение игры для игрока 1: 𝑉 1 (𝑧0 ) = 5.6. Тогда 𝐻1 (𝑧0 ) = 𝛽10 + 𝛽11 + 𝛽12 + 𝛽13 + 𝛽14 = 5.6 − 2.4 + 1.6 − 0.4 + 3.6 = 8 ≥ 𝑉 1 (𝑧0 ) = 5.6 Значение игры для игрока 2: 𝑉 2 (𝑧0 ) = 1, То 𝐻2 (𝑧0 ) = 𝛽20 + 𝛽21 + 𝛽22 + 𝛽23 + 𝛽24 = −4.2 + 3.8 − 0.2 + 1.8 + 3.8 = 5 ≥ 𝑉 2 (𝑧0 ) = 1 Оптимальная траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето Случай 2. Продолжаем исследовать игру Γ′𝑧1 , в которой исходная позиция игры 𝑧1 . Как показано на рисунке 1.8. Значение подыгры для игрока 1: 𝑉 1 (𝑧1 ) = 0, и 𝛽11 + 𝛽12 + 𝛽13 + 𝛽14 = −2.4 + 1.6 − 0.4 + 3.6 = 2.4 ≥ 𝑉 1 (¯ 𝑧1 ) = 0 Значение подыгры для игрока 2: 𝑉 2 (¯ 𝑧1 ) = 6.8, и 𝛽21 + 𝛽22 + 𝛽23 + 𝛽24 = 3.8 − 0.2 + 1.8 + 3.8 = 9.2 ≥ 𝑉 2 (¯ 𝑧1 ) = 6.8 21

Рисунок 1.8 Оптимальная траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето. Случай 3. Продолжаем исследовать подыгру Γ′𝑧2 , в которой исходная позиция игры 𝑧2 . Как показано на рисунке 1.9. Рисунок 1.9 Значение подыгры для игрока 1: 𝑉 1 (𝑧2 ) = 3.6, и 𝛽12 + 𝛽13 + 𝛽14 = 1.6 − 0.4 + 3.6 = 4.8 ≥ 𝑉 1 (𝑧2 ) = 3.6 Значение подыгры для игрока 2: 𝑉 2 (𝑧2 ) = 3, и 𝛽22 + 𝛽23 + 𝛽24 = −0.2 + 1.8 + 3.8 = 5.4 ≥ 𝑉 2 (𝑧2 ) = 3 Оптимальная по Парето траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ). Случай 4. Продолжаем исследовать игру Γ′𝑧3 . Как показано на рисунке 1.10. Значение подыгры для игрока 1: 𝑉 1 (𝑧3 ) = 2, и 𝛽13 + 𝛽14 = −0.4 + 3.6 = 3.2 ≥ 𝑉 1 (𝑧3 ) = 2 Значение подыгры для игрока 2: 𝑉 2 (𝑧3 ) = 5.6, и 𝛽23 + 𝛽24 = 1.8 + 3.8 = 5.6 ≥ 𝑉 2 (𝑧3 ) = 5.6 22

Рисунок 1.10 Оптимальная по Парето траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ). Случай 5. Очевидно 𝛽14 = 3.6 ≥ 𝑉 1 (𝑧4 ) = 3.6 𝛽24 = 3.8 ≥ 𝑉 2 (𝑧4 ) = 3.8 Резюмируя вышесказанное, используя теорему, получили 𝛽𝑖𝑘 , 𝑖 ∈ {1, 2}, 𝑘 ∈ {0, 1, 2, 3, 4} в примере, 𝛽𝑖𝑘 удовлетворяет 4 ∑︁ 𝛽𝑖𝑘 ≥ 𝑉 𝑖 (𝑧𝑚 ; {𝑖}, 𝑁/{𝑖}), 𝑖 ∈ {1, 2}, 𝑚 ∈ {0, 1, 2, 3, 4} 𝑘=𝑚 23

Глава 2. Стратегическая поддержка Парето-оптимальных решений Пусть, для кооперативной многошаговой игры Γ𝑧0 с остовным деревом мы имеем оптимальную по Парето траекторию 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) и 𝛽𝑖𝑘 (ПРВ). Будем определять стратегий наказания. Для упрощения ограничимся случаем неантагонистической игры 2-х лиц ¯ 1 ,𝐾 ¯ 2⟩ Γ = ⟨𝑈¯1 ,𝑈¯2 ,𝐾 С игрой Γ свяжем две антагонистические игры Γ1 и Γ2 : Антагонистическая игра Γ1 , построенная на основе игры Γ, в этой игре Γ1 второй игрок играет против первого игрока, 𝐾2 = −𝐾1 . Антагонистическая игра Γ2 , построенная на основе игры Γ, в этой игре Γ2 первый игрок играет против второго игрока, 𝐾1 = −𝐾2 . Ситуация равновесия в игре Γ1 : (𝑢*11 , 𝑢*21 ). Ситуация равновесия в игре Γ2 : (𝑢*12 , 𝑢*22 ). Обозначим через Γ1𝑥 , Γ2𝑥 подыгры игр Γ1 , Γ2 . И обозначим значения этих *𝑥 *𝑥 *𝑥 подыгр через 𝑣1 (𝑥), 𝑣2 (𝑥). То в играх Γ1𝑥 , Γ2𝑥 , ситуации {𝑢*𝑥 11 , 𝑢21 } и {𝑢12 , 𝑢22 } *𝑥 𝑥 *𝑥 *𝑥 называются равновесными. 𝑣1 (𝑥) = 𝐾1𝑥 (𝑢*𝑥 11 , 𝑢21 ), 𝑣2 (𝑥) = 𝐾2 (𝑢12 , 𝑢22 ). Продумываем пару (𝑢1 , 𝑢2 ) стратегий в игре Γ. Заметно, эта пара стратегий является таковой в играх Γ1 , Γ2 . Предполагается, что путь 𝑧 = (𝑧0 , . . . , 𝑧𝑙 ), реализуемый в ситуации (𝑢1 ,𝑢2 ). Пусть 𝑍 = {𝑧0 , 𝑧1 , . . . , 𝑧𝑙 } - здесь 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ) путь, реализуемый в ситуации (𝑢1 , 𝑢2 ). Определение. Стратегия 𝑢˜1 (·) называется стратегией наказания [5] игрока 1, если: 𝑢˜1 (𝑧𝑘 ) = 𝑧𝑘+1 , 𝑧𝑘 ∈ 𝑍 ∩ 𝑋1 𝑢˜1 (𝑦) = 𝑢*12 (𝑦), 𝑦 ∈ 𝑋1 , 𝑦 ∈ /𝑍 Стратегия 𝑢˜2 (·) называется стратегией наказания игрока 2, если: 𝑢˜2 (𝑧𝑘 ) = 𝑧𝑘+1 , 𝑧𝑘 ∈ 𝑍 ∩ 𝑋2 𝑢˜2 (𝑦) = 𝑢*21 (𝑦), 𝑦 ∈ 𝑋2 , 𝑦 ∈ /𝑍 𝑧𝑘+1 Теперь. Мы заменим выигрыши ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) и 𝑔𝑖 (𝑧𝑙 ), 𝑖 = 1, . . . , 𝑛, 𝑧𝑘 ∈ / 𝑋𝑛+1 , ∈ 𝐹𝑧𝑘 ∩ 𝑍, 𝑧𝑙 ∈ 𝑋𝑛+1 ∩ 𝑍, ℎ𝑖 ≥ 0, 𝑔𝑖 ≥ 0 соответственно через 𝛽𝑖𝑘 (ПРВ). 24

Далее найдём равновесие по Нэшу в стратегиях наказания, чтобы путь 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 стал оптимальной траекторией так же в равновесии по Нэшу. Вдоль пути 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 , при стратегиях наказания (˜ 𝑢1 (·), 𝑢˜2 (·)) имеет место 𝐾1 (˜ 𝑢1 (·), 𝑢˜2 (·)) = 𝑙 ∑︁ 𝛽1𝑘 𝑘=0 𝐾2 (˜ 𝑢1 (·), 𝑢˜2 (·)) = 𝑙 ∑︁ 𝑘=0 25 𝛽2𝑘

2.1 Существование ситуации равновесия по Нэшу в стратегиях наказания с ПРВ Теперь мы представляем теорему 2 и покажем, что существует равновесие по Нэшу в стратегиях наказания и что выигрыш в этом равновесии равен выигрышу вдоль оптимальной траектории по Парето. Из теоремы 1 мы получили 𝛽𝑖𝑘 (ПРВ) для кооперативной многошаговой игры Γ𝑧0 с полной информацией. После того, как мы заменили соответственные выигрыши ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) и 𝑔𝑖 (𝑧𝑙 ) на (ПРВ) 𝛽𝑖𝑘 , здесь 𝑖 = 1, . . . , 𝑛, 𝑘 = 0, . . . , 𝑙, 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 ∩ 𝑍, 𝑧𝑙 ∈ 𝑋𝑛+1 ∩ 𝑍, ℎ𝑖 ≥ 0, 𝑔𝑖 ≥ 0, 𝑍 = {𝑧0 , 𝑧1 , . . . , 𝑧𝑙 } и 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ) путь, реализуемый в ситуации (𝑢1 , 𝑢2 ). Потом мы получим новую игру Γ′𝑧0 . Однако стратегии игроков, которые добились пути 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 , могут быть не равновесными по Нэшу. Для того, чтобы путь 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 был оптимальным траектория в игре Γ𝑧0 . Мы используем стратегии наказания. Выше мы определили, что стратегии наказания (˜ 𝑢1 (·), 𝑢˜2 (·)) в кооперативной многошаговой игре Γ𝑧0 двух лиц с полной информацией. 26

2.2 Теорема о стратегической поддержке Парето-оптимальных решений В игре Γ𝑧0 , пусть (˜ 𝑢1 (·), 𝑢˜2 (·)) - ситуация в стратегиях наказания, в которых реализовался путь 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 . Для всех 𝐾 = (0, 1, . . . , 𝑙 − 1), стратегии наказания (˜ 𝑢1 (·), 𝑢˜2 (·)) образуют равновесия по Нэшу, если выполняется неравенства 𝐾1 (𝑧𝑘 ; 𝑢˜1 (·), 𝑢˜2 (·)) ≥ 𝑉 1 (𝑧𝑘 ) 𝐾2 (𝑧𝑘 ; 𝑢˜1 (·), 𝑢˜2 (·)) ≥ 𝑉 2 (𝑧𝑘 ) где 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 - путь, реализовавшийся в ситуации (˜ 𝑢1 (·), 𝑢˜2 (·)). Доказательство Во-первых построим стратегий наказания. 𝑢˜1 (·) - это стратегии наказания игрока 1 𝑢˜1 (𝑧𝑘 ) = 𝑧𝑘+1 , 𝑧𝑘 ∈ 𝑍 ∩ 𝑋1 𝑢˜1 (𝑦) = 𝑢*12 (𝑦), 𝑦 ∈ 𝑋1 , 𝑦 ∈ /𝑍 𝑢˜2 (·) – это стратегий наказания игрока 2 𝑢˜2 (𝑧𝑘 ) = 𝑧𝑘+1 , 𝑧𝑘 ∈ 𝑍 ∩ 𝑋2 𝑢˜2 (𝑦) = 𝑢*21 (𝑦), 𝑦 ∈ 𝑋2 , 𝑦 ∈ /𝑍 𝑍 = {𝑧0 , 𝑧1 , . . . , 𝑧𝑙 } - здесь 𝑧¯ = (𝑧0 , 𝑧1 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 путь, реализуемый в ситуации (˜ 𝑢1 (·), 𝑢˜2 (·)). Т.е. 𝑙 ∑︁ 𝑘=0 𝛽1𝑘 = 𝐾1 (𝑧0 ; 𝑢˜1 (·), 𝑢˜2 (·)), 𝑙 ∑︁ 𝑘=0 27 𝛽2𝑘 = 𝐾2 (𝑧0 ; 𝑢˜1 (·), 𝑢˜2 (·))

Из определения теоремы 1, будет 𝑙 ∑︁ 𝛽1𝑘 1 ≥ 𝑉 (𝑧𝑘 ), 𝑙 ∑︁ 𝛽2𝑘 ≥ 𝑉 2 (𝑧𝑘 ), 𝑘 = 0, 1, . . . , 𝑙 𝑘 𝑘 Т.е. 𝐾1 (˜ 𝑢1 (𝑧0 ), 𝑢˜2 (𝑧0 )) = 𝑙 ∑︁ 𝛽1𝑘 1 ≥ 𝑉 (𝑧0 ), 𝐾2 (˜ 𝑢1 (𝑧0 ), 𝑢˜2 (𝑧0 )) = 𝑙 ∑︁ 𝛽2𝑘 ≥ 𝑉 2 (𝑧0 ) 𝑘=0 𝑘=0 𝑘 = 0, 1, . . . , 𝑙 Пусть игрок 1 использует стратегию 𝑢1 (·), отличную от стратегии наказания 𝑢˜1 (·) для ∀𝑧𝑘 ∈ 𝑍 ∩ 𝑋1 . Из определения наказывающей стратегии 𝑢˜2 (·) следует, что игрок 2 проиграет не больше значения подыгры 𝑉 1 (𝑧𝑘 ), а игрок 1 в Γ′1 выиграет не больше, чем 𝑉 1 (𝑧𝑘 ) 𝐾1 (𝑧𝑘 ; 𝑢1 (·), 𝑢˜2 (·)) ≤ 𝑉 1 (𝑧𝑘 ) ∀𝑧𝑘 ∈ 𝑍 ∩ 𝑋1 Аналогично, если игрок 2 использует стратегию 𝑢2 (·) для ∀𝑧𝑘 ∈ 𝑍 ∩ 𝑋2 , то из определения наказывающей стратегии 𝑢˜1 (·) следует, что игрок 1 проиграет не больше значения подыгры 𝑉 2 (𝑧𝑘 ), а игрок 2 в Γ′2 выиграет не больше, чем 𝑉 2 (𝑧𝑘 ) 𝐾2 (𝑧𝑘 ; 𝑢˜1 (·), 𝑢2 (·)) ≤ 𝑉 2 (𝑧𝑘 ) ∀𝑧𝑘 ∈ 𝑍 ∩ 𝑋2 Теперь, предположим, что вышеуказанные неравенства имеют место. Докажем, что (˜ 𝑢1 (·), 𝑢˜2 (·)) - равновесия по Нэшу. На основании определения равновесия по Нэшу, 𝐾1 (˜ 𝑢1 (·), 𝑢˜2 (·)) ≥ 𝐾1 (𝑢1 (·), 𝑢˜2 (·)) 𝐾2 (˜ 𝑢1 (·), 𝑢˜2 (·)) ≥ 𝐾1 (˜ 𝑢1 (·), 𝑢2 (·)), однако 𝐾1 (𝑧0 ; 𝑢˜1 (·), 𝑢˜2 (·)) ≥ 𝑉 1 (𝑧0 ), 28

и 𝐾1 (𝑧𝑘 ; 𝑢1 (·), 𝑢˜2 (·)) ≤ 𝑉 1 (𝑧𝑘 ), ∀𝑧𝑘 ∈ 𝑍 ∩ 𝑋1 , и 𝐾2 (𝑧0 ; 𝑢˜1 (·), 𝑢˜2 (·)) ≥ 𝑉 2 (𝑧0 ), в то же время 𝐾2 (𝑧𝑘 ; 𝑢˜1 (·), 𝑢2 (·)) ≤ 𝑉 2 (𝑧𝑘 ), ∀𝑧𝑘 ∈ 𝑍 ∩ 𝑋2 Следовательно, определение равновесий по Нэшу выполняется и ситуация (˜ 𝑢1 (·), 𝑢˜2 (·)) – равновесия по Нэшу. 29

2.3 Пример Стратегической поддержки Парето-оптимальных решений. Пример 3 Для кооперативной многошаговой игры Γ𝑧0 с полной информацией. Как показано на рисунке 2.1. Рисунок 2.1 Выигрыши игроков 𝑖 - 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︀ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ), 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝑘=0 𝐹𝑧𝑘 , 𝑧𝑙 ∈ 𝑋𝑛+1 , ℎ𝑖 ≥ 0, 𝑔𝑖 ≥ 0. Вектор весов 𝛼1 = 𝛼2 = 12 . Для оптимальной по Парето траектории выполняется 𝑧¯ = (𝑧0 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ), 𝑙 ∈ 𝑋𝑛+1 . max 𝛼1 (︂ ∑︁ 𝑙−1 )︂ (︂ ∑︁ )︂ 𝑙−1 ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧𝑙 ) + 𝛼2 ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧𝑙 ) 𝑘=0 𝑘=0 Получили оптимальную траекторию основании результата. Обозначим 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 ) оптимальную траекторию. Т.е. 𝐻1 (𝑧0 ) = ℎ1 (𝑧0 , 𝑧2 ) + ℎ1 (𝑧1 , 𝑧2 ) + ℎ1 (𝑧2 , 𝑧3 ) + 𝑔1 (𝑧3 ) = 11 30

𝐻2 (𝑧0 ) = ℎ2 (𝑧0 , 𝑧2 ) + ℎ2 (𝑧1 , 𝑧2 ) + ℎ2 (𝑧2 , 𝑧3 ) + 𝑔2 (𝑧3 ) = 6 Вдоль пути 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 ), получили значения игр для игроков. 𝑉 1 (𝑧0 ) = 9, 𝑉 1 (𝑧1 ) = 8, 𝑉 1 (𝑧2 ) = 10, 𝑉 1 (𝑧3 ) = 9 𝑉 2 (𝑧0 ) = 6, 𝑉 2 (𝑧1 ) = 6, 𝑉 2 (𝑧2 ) = 5, 𝑉 2 (𝑧3 ) = 5 По теореме 1 (1.2), пусть 𝛽𝑖𝑘 процедура распределения выигрыш (ПРВ) в Γ𝑧0 , и 𝐻𝑖 (𝑧0 ) − 𝑉 𝑖 (𝑧0 ) 𝑘 − [𝑉 𝑖 (𝑧𝑘+1 ) − 𝑉 𝑖 (𝑧𝑘 )] 𝛽𝑖 = 𝑙+1 здесь 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︀ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ). Вдоль оптимальной траектории 𝑧¯ = 𝑘=0 (𝑧0 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ). Игрок 1 - 𝛽𝑖𝑘 , 𝑘 ∈ {0, 1, 2, 3}(ПРВ) 𝛽10 = 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 11 − 9 − [𝑉 1 (𝑧1 ) − 𝑉 1 (𝑧0 )] = − [8 − 9] = 1.5 4 4 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 11 − 9 = − [𝑉 1 (𝑧2 ) − 𝑉 1 (𝑧1 )] = − [10 − 8] = −1.5 4 4 11 − 9 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 2 − [𝑉 1 (𝑧3 ) − 𝑉 1 (𝑧2 )] = − [9 − 10] = 1.5 𝛽1 = 4 4 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 11 − 9 3 − [−𝑉 1 (𝑧3 )] = − [0 − 9] = 9.5 𝛽1 = 4 4 𝛽11 Игрок 2 - 𝛽2𝑘 , 𝑘 ∈ {0, 1, 2, 3}(ПРВ) 𝛽20 66 − 6 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) = − [𝑉 2 (𝑧1 ) − 𝑉 2 (𝑧0 )] = − [6 − 6] = 0 4 4 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 66 − 6 − [𝑉 2 (𝑧2 ) − 𝑉 2 (𝑧1 )] = − [5 − 6] = 1 4 4 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 66 − 6 2 𝛽2 = − [𝑉 2 (𝑧3 ) − 𝑉 2 (𝑧2 )] = − [5 − 5] = 0 4 4 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 66 − 6 3 𝛽2 = − [0 − 𝑉 2 (𝑧3 )] = − [0 − 5] = 5 4 4 𝛽21 = Т.е. Мы заменим 𝛽𝑖𝑘 , 𝑖 ∈ 1, 2, 𝑘 ∈ {0, 1, 2, 3}(ПРВ) соответственными выигрышами ℎ𝑖 (𝑧0 , 𝑧1 ), ℎ𝑖 (𝑧1 , 𝑧2 ), ℎ2 (𝑧2 , 𝑧3 ) и 𝑔𝑖 (𝑧3 ), 𝑖 ∈ 1, 2. 31

Получили новую игру Γ′𝑧0 , как показано на рисунке 2.2. Рисунок 2.2 Для игрока 1: 𝑢1 = {(𝐴𝐴𝐵𝐴𝐴), (𝐴𝐴𝐵𝐴𝐵), (𝐴𝐴𝐵𝐵𝐴), (𝐴𝐴𝐵𝐵𝐵)}, Для игрока 2: 𝑢2 = {(𝐵𝐴), (𝐵𝐵)}, когда дают одни и те же выигрыши. Чтобы путь 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 ) был оптимальной траектории так же, мы построим стратегии наказания. Пусть Γ′1 - это антагонистическая игра, построенная на основе игры Γ′𝑧0 в которой игрок 2 играет против игрока 1, Т.е. 𝐾2 = −𝐾1 . Игра Γ′2 это антагонистическая игра, построенная на основе игры Γ′𝑧0 , в которой игрок 1 играет против игрока 2, Т.е. 𝐾1 = −𝐾2 . Графы игры Γ′1 , Γ′2 , Γ′𝑧0 и множества стратегий в них совпадают. Обозначим через (𝑢*11 , 𝑢*21 ), (𝑢*12 , 𝑢*22 ) ситуации абсолютного равновесия в играх Γ′1 и Γ′2 . * * * * , 𝑈21 ), (𝑈12 , 𝑈22 ) Пусть 𝑉1 (𝑧𝑘 ), 𝑉2 (𝑧𝑘 ) значения этих подыгр. Тогда ситуации (𝑈11 являются равновесными в играх Γ′1 и Γ′2 соответственно и 𝑉1 (𝑧𝑘 ) = 𝐾1 (𝑢*11 , 𝑢*21 ), 𝑉2 (𝑧𝑘 ) = 𝐾2 (𝑢*12 , 𝑢*22 ) 32

Т.е. Γ′1 , как показано на рисунке 2.3. Рисунок 2.3 𝑢*11 = (𝐴𝐴𝐵𝐵𝐵) 𝑢*21 = (𝐵𝐵) Т.е. Γ′2 , как показано на рисунке 2.4. 𝑢*12 = (𝐴𝐴𝐴𝐵𝐵) 𝑢*22 = (𝐴𝐴) Из определение стратегий наказания имеем 𝑢˜1 (·) - это стратегии наказания игрока 1 𝑢˜1 (𝑧𝑘 ) = 𝑧𝑘+1 , 𝑧𝑘 ∈ 𝑍 ∩ 𝑋1 𝑢˜1 (𝑦) = 𝑢*12 (𝑦), 𝑦 ∈ 𝑋1 , 𝑦 ∈ /Z 𝑍 = {𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 } 𝑋1 = {𝑧0 , 𝑧2 , 𝑧5 , 𝑧6 , 𝑧7 } 33

Рисунок 2.4 𝑢˜2 (·) - это стратегии наказания игрока 2 𝑢˜2 (𝑧𝑘 ) = 𝑧𝑘+1 , 𝑧𝑘 ∈ 𝑍 ∩ 𝑋2 𝑢˜2 (𝑦) = 𝑢*21 (𝑦), 𝑦 ∈ 𝑋2 , 𝑦 ∈ /Z 𝑍 = {𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 } 𝑋2 = {𝑧1 , 𝑧4 } Путь 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 ) оптимальная траектория, тогда равновесие по Нэшу в стратегиях наказания имеет вид. В этой ситуации выигрыши игроков равны соответственно 11 для игрока 1 и 6 для игрока 2. Случая игрока 1: В 𝑧0 , игрок 1: 𝑢˜1 (𝑧0 ) = 𝐴 и до позиции 𝑧1 . 34

В 𝑧1 , если игрок 2 выбирает стратегию В. То в 𝑧5 . Игрок 1 будет действовать согласно стратегии наказания: 𝑢˜1 (𝑧5 ) = 𝑢˜12 (𝑧5 ) = 𝐴 В 𝑧2 , игрок 1 выбирает стратегию:A и до позиции 𝑧3 . Случая игрока 2: В 𝑧0 , если игрок 1 выбирает стратегию В. то в 𝑧4 . Игрок 2 будет действовать согласно стратегии наказания: 𝑢˜2 (𝑧(𝑧4 )) = 𝑢˜21 (𝑧4 ) = 𝐵 Потом до позиции 𝑧7 , игрок 1 выбирает стратегию: B. Резюмируя вышесказанное, нашли равновесия по Нэшу в стратегиях наказания. 35

Глава 3. Построение сильно динамически устойчивого ядра в кооперативных играх с полной информацией Как уже было отмечено, в многошаговой кооперативной игре Γ𝑧0 с полной информацией сильная динамическая устойчивость означает, что если выигрыши осуществляются в соответствии с ПРД 𝛽, то, получая на первых 𝑘 шагах суммы 𝛽 1 + · · · + 𝛽 𝑘 , игроки (если принципы оптимальности в подыгре Γ𝑧𝑘 и в игре Γ𝑧0 одинаковые), пересматривая оптимальный дележ в этой подыгре, во всяком случае получат в результате в игре Γ𝑧0 выигрыш в соответствии с некоторым дележом, оптимальным в предшествующем смысле, т. е. дележом, принадлежащим принципу оптимальности игры Γ𝑧0 . В игре Γ𝑧0 максимальная сумма выигрышей игроков реализовывается на траектории 𝑧¯ = {¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 }, т. е. кооперативная игра Γ𝑧¯𝑘 развивается по траектории 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ), которую будем называть оптимальной траекторией [9]. Определяется подыгра Γ𝑧¯𝑘 , 𝑘 = 1, . . . , 𝑙, начинающаяся в позиции 𝑧¯𝑘 на оптимальной траектории 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ). Предполагаем, что С-ядро 𝐶(¯ 𝑧0 ) не является пустым в игре Γ𝑧¯0 , и вычисляем С-ядро 𝐶(¯ 𝑧0 ), также предполагаем, что С-ядро 𝐶(¯ 𝑧𝑘 ) не является пустым в подыгре Γ𝑧¯𝑘 , и вычисляем С-ядро 𝐶(¯ 𝑧𝑘 ), 𝑘 = 1, . . . , 𝑙. Выбираем дележи 𝜉 0, . . . , 𝜉 𝑘 , . . . , 𝜉 𝑙 , где 𝜉 𝑘 ∈ 𝐶(¯ 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙. Пусть 𝛽 𝑘 = 𝜉 𝑘 − 𝜉 𝑘+1 (𝛽 𝑙 = 𝜉 𝑙 ). Получаем ПРД 𝛽 0 , . . . , 𝛽 𝑘 , . . . , 𝛽 𝑙 . Определим 𝛽¯𝑘 = {𝛽𝑖𝑘 , 𝑖 ∈ 𝑁 }, 𝑘 = 0, . . . , 𝑙, 𝑁 - множество игроков. Для разных дележей 𝜉 0 , . . . , 𝜉 𝑘 , . . . , 𝜉 𝑙 , где 𝜉 𝑘 ∈ 𝐶(¯ 𝑧𝑘 ), получаем разные 𝛽¯𝑘 , 𝑘 = 0, . . . , 𝑙. ¯ 𝑘 — множество всевозможных 𝛽¯𝑘 для всех 𝜉 𝑘 ∈ 𝐶(¯ Пусть 𝐵 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙. ¯ 𝑘 , 𝑘 = 0, . . . , 𝑙, построим множество Получив такие множества 𝐵 ¯ (¯ ¯𝑘} 𝑀 𝑧0 ) = {𝜉¯0 : 𝜉¯0 = 𝜉¯0 + · · · + 𝜉¯𝑘 + · · · + 𝜉¯𝑙 , 𝛽¯𝑘 ∈ 𝐵 ¯ (¯ Множество 𝑀 𝑧0 ) будем называть обобщенным динамическим ядром. 36

Из-за сложности построения обобщенного динамического ядра, предлагается его упрощение, которое существенно уменьшает объём вычислений. Упрощенное динамическое ядро строится с помощью вспомогательных величин 𝛼𝑘 , 𝑘 = 0, . . . , 𝑙. Выбираем последовательность дележей 𝜉 0, . . . , 𝜉 𝑘 , . . . , 𝜉 𝑙 , где 𝜉 𝑘 ∈ 𝐶(¯ 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙. Пусть ПРД 𝛽˜𝑘 = 𝛼𝑘 𝜉 𝑘 , 𝑘 = 0, . . . , 𝑙. Тогда соответственно получаем ПРД 𝛽˜0 , . . . , 𝛽˜𝑘 , . . . , 𝛽˜𝑙 . Определим 𝛽˜˜𝑘 = {𝛽˜𝑖𝑘 , 𝑖 ∈ 𝑁 }, 𝑘 = 0, . . . , 𝑙. Для разных дележей 𝜉 0, . . . , 𝜉 𝑘 , . . . , 𝜉 𝑙 , где 𝜉 𝑘 ∈ 𝐶(¯ 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙, получаем разные значения 𝛽˜0 , . . . , 𝛽˜𝑘 , . . . , 𝛽˜𝑙 , и таким образом разные 𝛽˜˜𝑘 , 𝑘 = 0, . . . , 𝑙. ˜ 𝑘 — множество всевозможных 𝛽˜˜𝑘 для всех 𝜉 𝑘 ∈ 𝐶(¯ Пусть 𝐵 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙. ˜ 𝑘 , 𝑘 = 0, . . . , 𝑙, строим множество С помощью 𝐵 ˜˜ (¯ ˜ 𝑘 }, 𝑀 𝑧0 ) = {𝜉˜˜0 : 𝜉˜˜0 = 𝛽˜˜0 + · · · + 𝛽˜˜𝑘 + · · · + 𝛽˜˜𝑙 , 𝛽˜˜𝑘 ∈ 𝐵 которое называется упрощенным динамическим ядром. 37

3.1 Динамическое ядро В первую очередь напомним основные понятия многошаговых кооперативных игр [8]. Предполагаем, что в многошаговых кооперативных играх 𝑛 лиц с полной информацией для любого пути игры 𝑧 = (𝑧1 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ), выигрыш 𝑖-го игрока в позиции 𝑧𝑘 , выражается как ℎ𝑖 (𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙, 𝑖 ∈ 𝑁 . Пусть в игре Γ𝑧¯0 характеристическая функция 𝑉 (𝑆), S ⊂ N, определяется как значение игры с нулевой суммой, которая происходит между коалицией S ⊂ N и 𝑁 \𝑆. Аналогично, в подыгре Γ𝑧¯𝑘 , 𝑘 = 1, . . . , 𝑙 определяется характеристическая функция 𝑉 (𝑆, 𝑧¯𝑘 ). Определение Предположим, что 𝜉 = {𝜉1 , . . . , 𝜉𝑖 , . . . , 𝜉𝑛 } ∈ 𝐼(𝑧0 ) Всякая матрица 𝛽 = {𝛽𝑖𝑘 }, 𝑖 = 1, . . . , n, 𝑘 = 0, . . . , 𝑙, такая, что 𝜉𝑖 = 𝛽𝑖0 + · · · + 𝛽𝑖𝑙 называется процедурой распределения дележа (ПРД). Здесь 𝐼(𝑧0 ) — множество дележей игры Γ𝑧0 , 𝛽𝑖𝑘 — выплата игроку 𝑖 на шаге 𝑘 игры Γ𝑧0 . Сумма 𝛽𝑖 (𝑘) = 𝛽𝑖0 + · · · + 𝛽𝑖𝑘 получатся игроком 𝑖 на первых 𝑘 шагах игры Γ𝑧0 [10]. Определение Принцип оптимальности M(𝑧0 ) называется сильно динамически устойчивым, если для каждого 𝜉 ∈ 𝑀 (𝑧0 ) существует ПРД 𝛽 такая, что 𝛽(𝑘) ⊕ M(z̄𝑘 ) ⊂ M(𝑧0 ), 𝑘 = 1, . . . , 𝑙 ′ ′ где 𝑎 ⊕ 𝐴 = {𝑎 + 𝑎 : 𝑎 ∈ 𝐴, 𝑎 ∈ R𝑛 , 𝐴 ⊂ R𝑛 } [8]. Используя предыдущий подход, можно представить динамическое ядро ¯0 ¯0 ¯ (¯ 𝑀 𝑧0 ) = {𝜉 : 𝜉 = 𝑙 ∑︁ 𝑘=0 в игре Γ𝑧¯0 , 𝑘 = 0, . . . , 𝑙. 38 ¯𝑘} 𝛽¯𝑘 , 𝛽¯𝑘 ∈ 𝐵

Далее сформулируем теорему, в которой доказывается сильная динамическая устойчивость обобщенного динамического ядра. Теорема Если ПРД 𝛽 определена как 𝛽¯𝑘 , 𝑘 = 0, . . . , 𝑙. то всегда выполняется ¯ ¯ (¯ ¯ (¯ 𝛽(𝑘) ⊕𝑀 𝑧𝑘 ) ⊂ 𝑀 𝑧0 ) ¯ (𝑧0 ) — сильно динамически устойчиво. Т. е. динамическое ядро 𝑀 ¯ ¯𝑚 𝛽(𝑘) = 𝛽¯0 + · · · + 𝛽¯𝑚 + · · · + 𝛽¯𝑘−1 , 𝛽¯𝑚 ∈ 𝐵 ¯ ¯ ¯ (¯ Здесь множество 𝛽(𝑘) ⊕𝑀 𝑧𝑘 ) есть множество всех векторов 𝛽(𝑘) + 𝜉¯𝑘 , ¯ (¯ где 𝜉¯𝑘 ∈ 𝑀 𝑧𝑘 ). Доказательства ¯ ¯ (¯ Пусть 𝜉¯ ∈ 𝛽(𝑘) ⊕𝑀 𝑧𝑘 ). Тогда 𝜉¯ = 𝑘−1 ∑︁ 𝛽¯𝑚 + 𝜉¯𝑘 , 𝑚=0 ¯ 𝑚 , m = 0, . . . , 𝑘 − 1. 𝛽¯𝑚 ∈ 𝐵 ¯ 𝑚 , m = 𝑘, . . . , 𝑙 Но 𝜉¯𝑘 = 𝛽¯𝑚 + · · · + 𝛽¯𝑙 , 𝛽¯𝑚 ∈ 𝐵 Рассмотрим {︃ 𝛽¯𝑚 , m = 𝑘, . . . , 𝑙, ¯¯ 𝑚 (𝛽) = 𝛽¯𝑚 , m = 0, . . . , 𝑘 − 1, ¯ 𝑚 , 𝑚 = 𝑘, . . . , 𝑙 и 𝛽¯𝑚 ∈ 𝐵 ¯ 𝑚 , 𝑚 = 0, . . . , 𝑘−1, следовательно, Так как 𝛽¯𝑚 ∈ 𝐵 ¯ ¯ (𝑧0 ). ¯ 𝑚 , 𝑚 = 0, . . . , 𝑙. Из определения 𝜉¯ = 𝛽¯¯0 +· · ·+𝛽¯¯𝑙 получаем, что 𝜉¯ ∈ 𝑀 𝛽¯𝑚 ∈ 𝐵 Теорема доказана. 39

3.2 Пример динамического ядра Пусть Γ𝑧0 — кооперативная многошаговая игра с полной информацией (рис. 1). Игроки N = {1, 2, 3}. Будем обозначать вершины, где ходит игрок 1, значком ∘, вершины, где ходит игрок 2, — значком ⋆, и вершины, где ходит игрок 3, — значком ∙. С помощью MATLAB найдена оптимальная траектория z̄ = (z̄0 , z̄1 , z̄2 , z̄3 , z̄4 ), для которой имеет место max z̄0 ,z̄1 ,z̄2 ,z̄3 ,z̄4 3 ∑︁ 4 ∑︁ h𝑖 (𝑧𝑘 ) = 137. 𝑖=1 𝑘=0 ¯ (¯ Вычисляем С-ядро 𝐶(¯ 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙, и строим динамическое ядро 𝑀 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙, в игре Γ𝑧0 и подыграх Γ𝑧𝑘 , 𝑘 = 1, . . . , 𝑙. Рисунок 3.1 — Кооперативная многошаговая игра Γ𝑧0 с полной информацией Рассмотрим некоторые дележи. ¯ (¯ ¯ (¯ Пусть это будут (70, −15, 82) ∈ 𝑀 𝑧0 ) и (44, 41, 50) ∈ 𝑀 𝑧2 ). Согласно данным результатам MATLAB, выбираем дележ 𝜉 0 = (80, 20, 37) ∈ 𝐶(¯ 𝑧0 ) 𝜉 1 = (50, 70, 16) ∈ 𝐶(¯ 𝑧1 ) 40

′ 𝜉 1 = (40, 35, 61) ∈ 𝐶(¯ 𝑧1 ) ′ 𝜉 2 = (44, 41, 50) ∈ 𝐶(¯ 𝑧2 ) ПРД будет 𝛽 0 = (30, −50, 21), 𝛽 1 = (−4, −6, 11). Таким образом, выполняется выражение ¯ (¯ (30, −50, 21) + (−4, −6, 11) + +(44, 41, 50) = (70, −15, 82) ∈ 𝑀 𝑧0 ) ¯ (¯ Это значит, что для дележа (70, −15, 82) ∈ 𝑀 𝑧0 ) существует ПРД 𝛽 0 = (30, −50, 21), 𝛽 1 = (−4, −6, 11) ¯ (¯ ¯ (¯ такая, что 𝛽 0 + 𝛽 1 + (44, 41, 50) ∈ 𝑀 𝑧0 ), здесь (44, 41, 50) ∈ 𝑀 𝑧2 ). ¯ (¯ С помощю MATLAB можно выбрать любой 𝜉 ∈ 𝑀 𝑧0 ), и найдётся 𝛽(𝑘), ¯ (¯ ¯ (¯ такая 𝛽(𝑘) + 𝜉 𝑘 ∈ 𝑀 𝑧0 ), если 𝜉 𝑘 ∈ 𝑀 𝑧𝑘 ). 41

3.3 Упрощение динамического ядра Для того чтобы уменьшить объём вычислений при построении динамического ядра, упростим его. Определяется вспомогательный вектор 𝛼 = (𝛼0 , . . . , 𝛼𝑘 , . . . , 𝛼𝑙 ), 𝑘 = 0, . . . , 𝑙 𝑉 (¯ 𝑧𝑘 , 𝑁 ) − 𝑉 (¯ 𝑧𝑘+1 , 𝑁 ) , 𝛼𝑘 = 𝑉 (¯ 𝑧𝑘 , 𝑁 ) где 𝑉 (¯ 𝑧𝑘 , 𝑁 ) = 𝜉1𝑘 + · · · + 𝜉𝑖𝑘 , 𝑖 ∈ N, дележ 𝜉𝑖𝑘 ∈ 𝐶(¯ 𝑧𝑘 ), 𝑘 = 0, . . . , 𝑙, 𝑖 ∈ 𝑁 . Для построения упрощенного динамического ядра в игре Γ𝑧¯0 используем предыдущий подход 𝑙 ∑︁ ˜ ˜˜ (¯ ˜˜ 𝑘 }. 𝑀 𝑧0 ) = {𝜉˜˜0 : 𝜉˜˜0 = 𝛽˜𝑘 , 𝛽˜˜𝑘 ∈ 𝐵 𝑘=0 ˜˜ (¯ Множество 𝑀 𝑧0 ) - новый принцип оптимальности в игре Γ𝑧¯0 . Теперь сформулируем теорему о динамической устойчивости упрощенного динамического ядра. Теорема Если ПРД 𝛽 определена как 𝛽˜˜𝑘 , 𝑘 = 0, . . . , 𝑙. то всегда выполняется ˜˜ ˜˜ (¯ ˜˜ (¯ 𝛽(𝑘) ⊕𝑀 𝑧𝑘 ) ⊂ 𝑀 𝑧0 ) ˜˜ (𝑧 ) — сильно динамически устойчиво, т. е. упрощенное динамическое ядро 𝑀 0 ˜˜ ˜˜ 𝑚 𝛽(𝑘) = 𝛽˜˜0 + · · · + 𝛽˜˜𝑚 + · · · + 𝛽˜˜𝑘−1 , 𝛽˜˜𝑚 ∈ 𝐵 ˜˜ ˜˜ ˜˜ (¯ Здесь множество 𝛽(𝑘) ⊕𝑀 𝑧𝑘 ) есть множество всех векторов 𝛽(𝑘) + 𝜉˜˜𝑘 , ˜˜ (¯ где 𝜉˜˜𝑘 ∈ 𝑀 𝑧𝑘 ). Доказательства ˜˜ ˜˜ (¯ Пусть 𝜉˜˜ ∈ 𝛽(𝑘) ⊕𝑀 𝑧𝑘 ), тогда 𝑘−1 ∑︁ ˜ ˜ 𝜉= 𝛽˜˜𝑚 + 𝜉˜˜𝑧¯𝑘 , ˜˜ 𝑚 , 𝛽˜˜𝑚 ∈ 𝐵 𝑚=0 42 m = 0, . . . , 𝑘 − 1

¯ ¯ ¯ ¯ ˜˜ 𝑚 , m = 𝑘, . . . , 𝑙. Рассмотрим Но 𝜉˜˜𝑧¯𝑘 = 𝛽˜˜𝑘 + · · · + 𝛽˜˜𝑚 + · · · + 𝛽˜˜𝑙 , 𝛽˜˜𝑚 ∈ 𝐵 ⎧ ¯ ¯˜ 𝑚 ⎨𝛽˜˜𝑚 , m = 𝑘, . . . , 𝑙, ˜ = (𝛽) ⎩𝛽˜˜𝑚 , m = 0, . . . , 𝑘 − 1, ¯ ˜ 𝑚 , 𝑚 = 𝑘, . . . , 𝑙 и 𝛽˜˜𝑚 ∈ 𝐵 ˜ 𝑚, Так как 𝛽˜˜𝑚 ∈ 𝐵 ¯ ˜ 𝑚 , 𝑚 = 0, . . . , 𝑙. Из определения 𝜉˜˜ = 𝛽˜˜𝑚 ∈ 𝐵 Теорема доказана. 43 𝑚 = 0, . . . , 𝑘 − 1, следовательно, ¯ ¯ ¯ (𝑧 ). 𝛽˜˜0 + · · · + +𝛽˜˜𝑙 , тогда 𝜉˜˜ ∈ 𝑀 0

Глава 4. Динамический Вектор Шепли в игре с остовным деревом В этой главе, исследуется динамический Вектор Шепли в двухшаговой игре с минимальным остовным деревом. На каждом шаге игроки строят минимальное остовное дерево, и вычисляется Вектор Шепли. На втором шаге один из игроков выбывает из игры с вероятностью 𝑝, зависящей от предыдущих стратегий игроков. Используя процедуру распределения дележа проводится регуляризация исходной игры. Stage 1 The player m leaves the game The player m stays in the game Stage 2 Stage 2 Рисунок 4.1 4.1 Построение двухшаговой игры с минимальным остовным деревом Пусть 𝑁 ′ = 𝑁 ∪ {0} конечное множество, интерпретируемое как множество вершин конечного полного графа 𝐺. Вершину {0} назовём истоком. Элементы множества 𝑁 являются игроками в игре. На первом шаге игроки выбирают стратегии 𝑥𝑖 = (𝑥𝑖,1 , . . . , 𝑥𝑖,𝑖−1 , 𝑥𝑖,𝑖+1 , . . . , 𝑥𝑖,𝑛 ), 44

где 𝑥𝑖,𝑗 подразумевает воздействие игрока 𝑖 на игрока 𝑗. Для 𝑖, 𝑗 ∈ 𝑁 положим расходы на ребре (𝑖, 𝑗) равными 𝑐𝑖𝑗 = 𝑐𝑗𝑖 = 𝑓𝑐 (𝑥𝑖,𝑗 , 𝑥𝑗,𝑖 ), 𝑐𝑖0 = 𝑐0𝑖 > 0, ∀𝑖, 𝑗 ∈ 𝑁. Обозначим через 𝐸 множество всех рёбер графа 𝐺. Получаем сеть 𝐺(𝑁 , 𝐸) с единственном истоком {0}. Обозначим через 𝑇 (𝑁 ′ , 𝐶) минимальное остовное дерево сети 𝐺(𝑁 ′ , 𝐸). Очевидно, что 𝐺(𝑁 ′ , 𝐸) зависит от ситуации 𝑥 = (𝑥1 , . . . , 𝑥𝑛 ), поэтому естественно писать 𝑇𝑥 (𝑁 ′ , 𝐶). Обозначим через 𝐶(𝑇𝑥 (𝑁 ′ , 𝐶)) суммарные расходы в остовном дереве 𝑇𝑥 (𝑁 ′ , 𝐶) в ситуации 𝑥. 𝑃 (𝑚) будем называться непосредственным предшественником 𝑚, если имеет место 𝑃 (𝑚) ∈ 𝑃𝑚0 и (𝑃 (𝑚), 𝑚) ∈ 𝑇𝑥 (𝑁 ′ , 𝐶). Где 𝑃𝑚0 - путь из истока {0} в вершину 𝑚. Последовательность 𝑖1 , . . . , 𝑖𝐾−1 разный и все отличные от 𝑚 и 0, (𝑖𝑘 , 𝑖𝑘+1 ) ∈ 𝑃𝑚0 , 𝑘 ∈ [0, 𝐾 − 1], 𝐾 > 1. Если 𝑗 ∈ 𝑃𝑚0 , 𝑗 - предшественник-𝑚. Множество 𝐵(𝑚) называется веткой, если ∃𝑆, |𝑆| > 1, когда 𝑚 ∈ 𝑆, iff ∀𝑖 ∈ 𝑆, 𝑚 - предшественник - 𝑖. Обозначим через 𝐵(𝑚) множество дуг (𝑖, 𝑗) в поддереве остовного дерева с корнем 𝑚: 𝐵(𝑚) = 𝑆. Зафиксируем некоторого игрока 𝑚 ∈ 𝑁 . В данной постановке считаем, что на втором шаге игры игрок 𝑚 может покинуть игру с вероятностью ∑︀ (𝑖,𝑗)∈𝐵(𝑚) 𝑐𝑖𝑗 𝑝= 𝐶(𝑇𝑥 (𝑁 ′ , 𝐶)) ′ и игра повторяется или на прежней сети или на сети без игрока 𝑚. 4.2 Динамической устойчивости Предположим что затраты игрока 𝑖 ∈ 𝑁 в двухшаговой игре суммируются из затрат на первом и втором шаге. Рассмотрим кооперативный вариант игры. Сперва определим характеристическую функцию в двухшаговой игре. Для этого определим минимальные суммарные затраты за два шага. 𝑉 1 (𝑁 ) = min[𝐶(𝑇𝑥 (𝑁 ′ , 𝐶)) + [𝑝𝐶(𝑇𝑥 (𝑁 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥 (𝑁 ′ , 𝐶))]] 𝑥 45

= 𝐶(𝑇𝑥⋆ (𝑁 ′ , 𝐶)) + [𝑝𝐶(𝑇𝑥⋆ (𝑁 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥⋆ (𝑁 ′ , 𝐶))]. Ситуацию 𝑥⋆ = (𝑥⋆1 , 𝑥⋆2 , . . . , 𝑥⋆𝑛 ) будем называть кооперативным поведением игроков. Аналогично, значение характеристической функции для коалиции 𝑆 ⊆ 𝑁 , определяется по формуле 𝑉 1 (𝑆) = min[𝐶(𝑇𝑥𝑠 (𝑆 ′ , 𝐶)) + [𝑝𝐶(𝑇𝑥𝑠 (𝑆 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥𝑠 (𝑆 ′ , 𝐶))]] 𝑥𝑠 = 𝐶(𝑇𝑥⋆𝑠 (𝑆 ′ , 𝐶)) + [𝑝𝐶(𝑇𝑥⋆𝑠 (𝑆 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥⋆𝑠 (𝑆 ′ , 𝐶))] если 𝑚 ∈ 𝑆, 𝑆 ′ = 𝑆 ∪ {0}. 𝑉 1 (𝑆) = min[2𝐶(𝑇𝑥𝑠 (𝑆 ′ , 𝐶))] = 2𝐶(𝑇𝑥𝑠 (𝑆 ′ , 𝐶)), 𝑆 ′ = 𝑆 ∪ {0}. 𝑥𝑠 если 𝑚 ∈ / 𝑆, где 𝑥𝑠 = {𝑥𝑖 , 𝑖 ∈ 𝑆}. Вектор Шепли для двухшаговой игры равен 𝑆ℎ1𝑖 (𝑁 ′ , 𝐶) = 1 ∑︁ 1 [𝑉 (𝑆𝜋(𝑖) ∪ {𝑖}) − 𝑉 1 (𝑆𝜋(𝑖) )], ∀𝑖 ∈ 𝑁, 𝑆 ⊂ 𝑁. 𝑛! 𝜋∈Π Где Π множество упорядочений множества игроков 𝑁 . Характеристическая функция 𝑉 2 на втором шаге в одношаговой игре на сети порождённой ситуацией 𝑥⋆ = (𝑥⋆1 , 𝑥⋆2 , . . . , 𝑥⋆𝑛 ) имеет вид 𝑉 2 (𝑁 ) = min[𝑝𝐶(𝑇𝑥 (𝑁 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥 (𝑁 ′ , 𝐶))] 𝑥 = 𝑝𝐶(𝑇𝑥⋆ (𝑁 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥⋆ (𝑁 ′ , 𝐶)) и 𝑉 2 (𝑆) = min[𝑝𝐶(𝑇𝑥𝑠 (𝑆 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥𝑠 (𝑆 ′ , 𝐶))] 𝑥𝑠 = 𝑝𝐶(𝑇𝑥⋆𝑠 (𝑆 ′ ∖ {𝑚}, 𝐶)) + (1 − 𝑝)𝐶(𝑇𝑥⋆𝑠 (𝑆 ′ , 𝐶)), если 𝑚 ∈ 𝑆, 𝑆 ′ = 𝑆 ∪ {0} 𝑉 2 (𝑆) = min[𝐶(𝑇𝑥𝑠 (𝑆 ′ , 𝐶))] = 𝐶(𝑇𝑥⋆𝑠 (𝑆 ′ , 𝐶)), 𝑥𝑠 46

если 𝑚 ∈ / 𝑆, 𝑆 ′ = 𝑆 ∪ {0}, где 𝑥𝑠 = {𝑥𝑖 , 𝑖 ∈ 𝑆}. Аналогично Вектор Шепли в одношаговой игре на втором шаге 𝑆ℎ2𝑖 (𝑁 ′ , 𝐶) = 1 ∑︁ 2 [𝑉 (𝑆𝜋(𝑖) ∪ {𝑖}) − 𝑉 2 (𝑆𝜋(𝑖) )], ∀𝑖 ∈ 𝑁, 𝑆 ⊂ 𝑁. 𝑛! 𝜋∈Π Где Π множество упорядочений множества игроков 𝑁 . Для получения состоятельного во времени (динамически устойчивого) Вектора Шепли вводим ПРД (процедура распределения дележа 𝛽 = (𝛽 1 , 𝛽 2 )). По формулам 𝛽 1 = 𝑆ℎ1 (𝑁 ′ , 𝐶) − 𝑆ℎ2 (𝑁 ′ , 𝐶) 𝛽 2 = 𝑆ℎ2 (𝑁 ′ , 𝐶) если игроки на каждом шаге будут распределять затраты согласно ПРД 𝛽, то вектор Шепли будет динамически устойчив. 47

Глава 5. Многошаговая игра с остовным деревом 5.1 Определение многошаговой игры с остовным деревом Определение Будем предполагать, что для каждого пути игры 𝑧 = (𝑧0 , . . . , 𝑧𝑙 ), 𝑧𝑙 ∈ 𝑋𝑛+1 пусть на каждом ребре (𝑧𝑘 , 𝑧𝑘+1 ), 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 и в каждом окончательном позиции 𝑧𝑙 ∈ 𝑋𝑛+1 задана игра 𝑛-лиц с остовным деревом и определяется как 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )), 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ), 𝑧𝑘 ∈ 𝑋𝑛+1 где 𝑁 ′ = 𝑁 ∪{0} конечное множество, интерпретируемое как множество вершин конечного полного графа 𝐺. Вершину {0} назовём истоком. Обозначим через 𝐸 множество всех рёбер графа 𝐺. 𝐸 = {(𝑖, 𝑗) : ∀𝑖 ̸= 𝑗, 𝑖, 𝑗 ∈ 𝑁 ′ }. Определение Пусть 𝐶𝑒 матрица расходов рёбер графа 𝐺. 𝐶𝑒 = (𝑐𝑖𝑗 )(𝑖,𝑗)∈𝐸 . 𝑐𝑖𝑗 расход ребра (𝑖, 𝑗), 𝑖, 𝑗 ∈ 𝑁 ′ . Определение Цикл 𝑝𝑙𝑙 - в графе 𝐺 существуют 𝐾 рёбра (𝑖𝑘 , 𝑖𝑘+1 ), 𝐾 ≥ 3, 𝑘 ∈ [0, 𝐾 − 1] такой, что 𝑖0 = 𝑖𝐾 = 𝑙 и последовательность 𝑖1 , . . . ,𝑖𝐾−1 разная и все отличные от 𝑙. Определение Путь 𝑝𝑙𝑚 - в графе 𝐺 существуют 𝐾 ребер (𝑖𝑘 , 𝑖𝑘+1 ), 𝐾 ≥ 1, 𝑘 ∈ [0, 𝐾 − 1] таких, что 𝑖0 = 𝑙, 𝑖𝐾 = 𝑚. Последовательности 𝑖1 , . . . ,𝑖𝐾−1 разные и отличны от 𝑙 и 𝑚. 𝑛 Определение Граф 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )), 𝑧𝑘 ∈ ∪ 𝑋𝑖 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 или 𝑖=1 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ), 𝑧𝑘 ∈ 𝑋𝑛+1 называется связным, если для каждой пары вершин 𝑖, 𝑗 ∈ 𝑁 ′ , в графе есть путь из вершины 𝑖 в вершину 𝑗. Определение Дерево - это связный граф без циклов. 𝑛 Определение Остовное дерево графа 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )), 𝑧𝑘 ∈ ∪ 𝑋𝑖 , 𝑖=1 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 или 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ), 𝑧𝑘 ∈ 𝑋𝑛+1 - это любой его подграф, которой содержает все вершины графа 𝐺 и являет деревом. 48

Определение Обозначим через 𝑇 (𝑁 ′ , 𝐶𝑒 , (𝑧𝑘 , 𝑧𝑘+1 )) минимальное остов𝑛 ное дерево сети 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )), 𝑧𝑘 ∈ ∪ 𝑋𝑖 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 . 𝑖=1 𝑇 (𝑁 ′ , 𝐶𝑒 , (𝑧𝑘 , 𝑧𝑘+1 )) = arg ∑︁ min ′ ,𝐸,(𝑧 ,𝑧 ¯ 𝐺∈𝐺(𝑁 𝑘 𝑘+1 )) 𝑐𝑖𝑗 ¯ (𝑖,𝑗)∈𝐺 ¯ - подграф 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )), который включает все вершин 𝑁 ′ . где 𝐺 Аналогично, обозначим через 𝑇 (𝑁 ′ , 𝐶𝑒 , 𝑧𝑘 ) минимальное остовное дерево сети 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ), 𝑧𝑘 ∈ 𝑋𝑛+1 . ′ 𝑇 (𝑁 , 𝐶𝑒 , 𝑧𝑘 ) = arg ∑︁ min ′ ,𝐸,𝑧 ) ¯ 𝐺∈𝐺(𝑁 𝑘 𝑐𝑖𝑗 ¯ (𝑖,𝑗)∈𝐺 ¯ - подграф 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ), который включает все вершин 𝑁 ′ . где 𝐺 Определение Обозначим через 𝐶(𝑇 (𝑁 ′ , 𝐶𝑒 , (𝑧𝑘 , 𝑧𝑘+1 ))) суммарные рас𝑛 ходы в остовном дереве 𝑇 (𝑁 ′ , 𝐶𝑒 , (𝑧𝑘 , 𝑧𝑘+1 )), 𝑧𝑘 ∈ ∪ 𝑋𝑖 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 . 𝑖=1 ∑︁ 𝐶(𝑇 (𝑁 ′ , 𝐶𝑒 , (𝑧𝑘 , 𝑧𝑘+1 ))) = 𝑐𝑖𝑗 (𝑖,𝑗)∈𝑇 (𝑁 ′ ,𝐶𝑒 ,(𝑧𝑘 ,𝑧𝑘+1 )) Аналогично, обозначим через 𝐶(𝑇 (𝑁 ′ , 𝐶𝑒 , 𝑧𝑘 )) суммарные расходы в остовном дереве 𝑇 (𝑁 ′ , 𝐶𝑒 , 𝑧𝑘 ), 𝑧𝑘 ∈ 𝑋𝑛+1 . ∑︁ ′ 𝐶(𝑇 (𝑁 , 𝐶𝑒 , 𝑧𝑘 )) = 𝑐𝑖𝑗 (𝑖,𝑗)∈𝑇 (𝑁 ′ ,𝐶𝑒 ,𝑧𝑘 ) 𝑛 Определение На каждом графе 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )), 𝑧𝑘 ∈ ∪ 𝑋𝑖 , 𝑧𝑘+1 ∈ 𝑖=1 𝐹𝑧𝑘 определены 𝑛 действительных чисел 𝑐𝑖 (𝑧𝑘 , 𝑧𝑘+1 ), 𝑖 = 1, . . . ,𝑛, 𝑐𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) ≥ 0 так чтобы выполнялись следующее условие ′ 𝐶(𝑇 (𝑁 , 𝐶𝑒 , (𝑧𝑘 , 𝑧𝑘+1 ))) = 𝑛 ∑︁ 𝑐𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) 𝑖=1 (𝑐1 (𝑧𝑘 , 𝑧𝑘+1 ), . . . , 𝑐𝑛 (𝑧𝑘 , 𝑧𝑘+1 )) является вектором распределений расходов графа 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )). Аналогично, на каждом графе 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ), 𝑧𝑘 ∈ 𝑋𝑛+1 определены 𝑛 действительных чисел 𝑐𝑖 (𝑧𝑘 ), 𝑖 = 1, . . . ,𝑛, 𝑐𝑖 (𝑧𝑘 ) ≥ 0 так чтобы выполнялись следу49

ющее условие ′ 𝐶(𝑇 (𝑁 , 𝐶𝑒 , 𝑧𝑘 )) = 𝑛 ∑︁ 𝑐𝑖 (𝑧𝑘 ) 𝑖=1 (𝑐1 (𝑧𝑘 ), . . . , 𝑐𝑛 (𝑧𝑘 )) является вектором распределений расходов графа 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ). Определение На основании исследования Bird(1976), определим Birdраспределение расходов между игроками. Для любой вершины 𝑖 в графе 𝑛 𝐺(𝑁 ′ , 𝐸, (𝑧𝑘 , 𝑧𝑘+1 )), 𝑧𝑘 ∈ ∪ 𝑋𝑖 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 или 𝐺(𝑁 ′ , 𝐸, 𝑧𝑘 ), 𝑧𝑘 ∈ 𝑋𝑛+1 , пусть 𝑖=1 𝑝𝑖0 это путь между игроком 𝑖 и источником {0}, и пусть (𝑖, 𝑚) это ребро, которое содержит вершины 𝑖 и 𝑚, в пути 𝑝𝑖0 , такой что ℎ𝑖 (𝑧𝑘 ,𝑧𝑘+1 ) = 𝑐𝑖 (𝑧𝑘 ,𝑧𝑘+1 ) = 𝑐𝑖𝑚 , 𝑧𝑘 ∈ / 𝑋𝑛+1 , 𝑧𝑘+1 ∈ 𝐹𝑧𝑘 𝑔𝑖 (𝑧𝑘 ) = 𝑐𝑖 (𝑧𝑘 ) = 𝑐𝑖𝑚 , 𝑧𝑘 ∈ 𝑋𝑛+1 где 𝑖 ̸= 𝑚 ∈ 𝑁 ′ , 𝑐𝑖𝑚 - это расход ребра (𝑖, 𝑚) в графе. Определение. Если 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ), 𝑧¯𝑙 ∈ 𝑋𝑛+1 путь реализованный ситуацией 𝑢¯(·) = (¯ 𝑢1 ,..., 𝑢¯𝑖 ,..., 𝑢¯𝑛 ), 𝑖 ∈ 𝑁 , и существует соответственный 𝑛 ∑︀ 𝛼𝑖 = 1, 𝛼𝑖 ≥ 0, вектор весов 𝛼 = (𝛼1 , . . . , 𝛼𝑛 ) и 𝑖=1 такой,что min 𝑧0 ,...,𝑧𝑖 ,...,𝑧𝑙 𝑛 ∑︁ 𝑙−1 ∑︁ 𝛼𝑖 ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝛼𝑖 𝑔𝑖 (𝑧𝑙 ) = 𝑙−1 𝑛 ∑︁ ∑︁ 𝛼𝑖 ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝛼𝑖 𝑔𝑖 (¯ 𝑧𝑙 ) 𝑖=1 𝑘=0 𝑖=1 𝑘=0 ℎ𝑖 ≥ 0, ℎ𝑖 ≥ 0, 𝛼𝑖 > 0, 𝑛 ∑︁ 𝛼𝑖 = 1 𝑖=1 тогда кооперативная игра Γ𝑧0 развивается вдоль траектории 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑙 ), 𝑧¯𝑙 ∈ 𝑋𝑛+1 , которую будем казывется оптимальной траекторией. Для игры Γ𝑧0 набор стратегий 𝑢¯(·) = (¯ 𝑢1 , . . . , 𝑢¯𝑖 , . . . , 𝑢¯𝑛 ), 𝑖 ∈ 𝑁 , соответствует пути 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑘 , . . . , 𝑧¯𝑙 ), 𝑧¯𝑙 ∈ 𝑋𝑛+1 . Выигрыш игрока 𝑖 в Γ𝑧0 : ¯ 𝑖 (𝑧0 ) = 𝐻 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ), ℎ𝑖 , 𝑔𝑖 ≥ 0 𝑘=0 50

Как выше, пусть 𝛽𝑖𝑘 процедура распределения выигрыша (ПРВ). Т.е. 𝑙 𝑙−1 ∑︁ ∑︁ ¯ 𝛽𝑖𝑘 ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) = 𝐻𝑖 (𝑧0 ) = 𝑘=0 𝑘=0 51

5.2 Временная состоятельность кооперативного решения (оптимальность по Парето) Вдоль оптимальной траектории 𝑧¯ = (𝑧0 , . . . , 𝑧𝑙 ) нашли минимальную сумму расходов игроков в многошаговых кооперативных играх с остовным деревом. Т.е. в игре Γ𝑧0 , должно выполняться условие ¯ 𝑖 (𝑧0 ) = 𝐻 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) ≤ 𝑉 𝑖 (𝑧0 ; {𝑖},𝑁/{𝑖}) 𝑘=0 (условие индивидуальной рациональности) Игра Γ𝑧0 развивается вдоль оптимальной траектории 𝑧¯ = (¯ 𝑧0 , . . . , 𝑧¯𝑙 ), 𝑧¯𝑙 ∈ 𝑋𝑛+1 . Для выполнения условия временной состоятельности, должно выполняться условие 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) ≤ 𝑉 𝑖 (𝑧1 ; {i} ,𝑁/ {𝑖}) 𝑘=1 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) ≤ 𝑉 𝑖 (𝑧2 ; {i} ,𝑁/ {𝑖}) 𝑘=2 ... 𝑙−1 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) ≤ 𝑉 𝑖 (𝑧𝑚 ; {i} ,𝑁/ {𝑖}) 𝑘=𝑚 ... 𝑔𝑖 (¯ 𝑧𝑙 ) ≤ 𝑉 𝑖 (𝑧𝑙 ; {i} ,𝑁/ {𝑖}) 𝑚 ∈ {1,2,...,𝑙} Аналогично выше, если 𝑙 ∑︁ ℎ𝑖 (¯ 𝑧𝑘 , 𝑧¯𝑘+1 ) + 𝑔𝑖 (¯ 𝑧𝑙 ) > 𝑉 𝑖 (𝑧𝑚 ; {𝑖} , 𝑁/ {𝑖}), 𝑚 ∈ {0,1, . . . , 𝑙} 𝑘=𝑚 для некоторых 𝑖 ∈ 𝑁 , то это временная несостоятельность решения. 52

5.3 Пример временной несостоятельности кооперативного решения Пример Пусть кооперативная многошаговая игра Γ𝑧0 с остовным деревом. Игроки N = {1,2}. Мы будем обозначать вершины где ходит игрок 1 через кольцо, и вершины где ходит игрок 2 прямоугольником. Стратегии игроков i - u𝑧i 0 ,i ∈ {1,2}, ситуация u = {u𝑧10 ,u𝑧20 }, соответствующая траектория (𝑧0 , . . . ,𝑧𝑘 , . . . ,𝑧𝑙 ). На каждом ребре и в каждой окончательной позиции определена 2-х игра с остовным деревом. Как показано на рисунке ниже, граф 𝐺(𝑁 ′ , 𝐸, (𝑧0 , 𝑧1 )) на ребре (𝑧0 , 𝑧1 ). {0} - источник. Рисунок 5.1 𝐶𝑧0 ,𝑧1 матрица расходов рёбер графа 𝐺(𝑁 ′ , 𝐸, (𝑧0 , 𝑧1 )). ⎛ 𝐶𝑧0 ,𝑧1 ⎞ 0 2 10 ⎜ ⎟ =⎝ 2 0 6 ⎠ 10 6 0 Минимальное остовное дерево 𝑇 (𝑁 ′ , 𝐶𝑧0 ,𝑧1 , (𝑧0 , 𝑧1 )) Рисунок 5.2 53

Суммарные расходы в остовное дерево 𝑇 (𝑁 ′ , 𝐶𝑧0 ,𝑧1 , (𝑧0 , 𝑧1 )): 𝐶(𝑇 (𝑁 ′ , 𝐶𝑧0 ,𝑧1 , (𝑧0 , 𝑧1 ))) = 2 + 6 = 8 Нашли что Bird-распределение расходов в графе 𝐺(𝑁 ′ , 𝐸, (𝑧0 , 𝑧1 )): ℎ1 (𝑧0 , 𝑧1 ) = 𝑐1 (𝑧0 , 𝑧1 ) = 𝑐01 = 2 ℎ2 (𝑧0 , 𝑧1 ) = 𝑐2 (𝑧0 , 𝑧1 ) = 𝑐21 = 6 Аналогично, определим матрицы расходов рёбер графа на других рёбрах и в окончательном позиции. ⎛ 𝐶𝑧0 ,𝑧5 ⎞ 0 2 10 ⎜ ⎟ ℎ1 (𝑧0 , 𝑧5 ) = 𝑐1 (𝑧0 , 𝑧5 ) = 2 =⎝ 2 0 6 ⎠ ℎ2 (𝑧0 , 𝑧5 ) = 𝑐2 (𝑧0 , 𝑧5 ) = 6 10 6 0 ⎛ 𝐶𝑧1 ,𝑧2 𝐶𝑧1 ,𝑧6 𝐶𝑧2 ,𝑧3 𝐶𝑧2 ,𝑧7 𝐶𝑧3 ,𝑧4 0 6 15 ⎜ =⎝ 6 0 5 15 5 0 ⎛ 0 6 15 ⎜ =⎝ 6 0 5 15 5 0 ⎛ 0 5 19 ⎜ =⎝ 5 0 6 19 6 0 ⎛ 0 5 19 ⎜ =⎝ 5 0 6 19 6 0 ⎛ 0 6 15 ⎜ =⎝ 6 0 5 15 5 0 ⎞ ⎟ ℎ1 (𝑧1 , 𝑧2 ) = 𝑐1 (𝑧1 , 𝑧2 ) = 6 ⎠ ℎ2 (𝑧1 , 𝑧2 ) = 𝑐2 (𝑧1 , 𝑧2 ) = 5 ⎞ ⎟ ℎ1 (𝑧1 , 𝑧6 ) = 𝑐1 (𝑧1 , 𝑧6 ) = 6 ⎠ ℎ2 (𝑧1 , 𝑧6 ) = 𝑐2 (𝑧1 , 𝑧6 ) = 5 ⎞ ⎟ ℎ1 (𝑧2 , 𝑧3 ) = 𝑐1 (𝑧2 , 𝑧3 ) = 5 ⎠ ℎ2 (𝑧2 , 𝑧3 ) = 𝑐2 (𝑧2 , 𝑧3 ) = 6 ⎞ ⎟ ℎ1 (𝑧2 , 𝑧7 ) = 𝑐1 (𝑧2 , 𝑧7 ) = 5 ⎠ ℎ2 (𝑧2 , 𝑧7 ) = 𝑐2 (𝑧2 , 𝑧7 ) = 6 ⎞ ⎟ ℎ1 (𝑧3 , 𝑧4 ) = 𝑐1 (𝑧3 , 𝑧4 ) = 6 ⎠ ℎ2 (𝑧3 , 𝑧4 ) = 𝑐2 (𝑧3 , 𝑧4 ) = 5 54

⎛ ⎞ 0 6 15 ⎜ ⎟ ℎ1 (𝑧3 , 𝑧8 ) = 𝑐1 (𝑧3 , 𝑧8 ) = 6 𝐶𝑧3 ,𝑧8 = ⎝ 6 0 5 ⎠ ℎ2 (𝑧3 , 𝑧8 ) = 𝑐2 (𝑧3 , 𝑧8 ) = 5 15 5 0 ⎛ ⎞ 0 3 3 ⎜ ⎟ 𝑔1 (𝑧4 ) = 𝑐1 (𝑧4 ) = 3 𝐶𝑧4 = ⎝ 3 0 10 ⎠ 𝑔2 (𝑧4 ) = 𝑐2 (𝑧4 ) = 3 3 10 0 ⎛ ⎞ 0 23 23 ⎜ ⎟ 𝑔1 (𝑧5 ) = 𝑐1 (𝑧5 ) = 23 𝐶𝑧5 = ⎝ 23 0 100 ⎠ 𝑔2 (𝑧5 ) = 𝑐2 (𝑧5 ) = 23 23 100 0 ⎛ ⎞ 0 18 13 ⎜ ⎟ 𝑔1 (𝑧6 ) = 𝑐1 (𝑧6 ) = 18 𝐶𝑧6 = ⎝ 18 0 90 ⎠ 𝑔2 (𝑧6 ) = 𝑐2 (𝑧6 ) = 13 13 90 0 ⎞ ⎛ 0 11 9 ⎟ 𝑔1 (𝑧7 ) = 𝑐1 (𝑧7 ) = 11 ⎜ 𝐶𝑧7 = ⎝ 11 0 70 ⎠ 𝑔2 (𝑧7 ) = 𝑐2 (𝑧7 ) = 9 9 70 0 ⎛ ⎞ 0 4 5 ⎜ ⎟ 𝑔1 (𝑧8 ) = 𝑐1 (𝑧8 ) = 4 𝐶𝑧8 = ⎝ 4 0 17 ⎠ 𝑔2 (𝑧8 ) = 𝑐2 (𝑧8 ) = 5 5 17 0 Выигрыши игроков 𝑖, 𝑖 ∈ {1, 2}: 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︁ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ) 𝑘=0 Пусть вектор весов 𝛼1 = 𝛼2 = 21 , тогда для оптимальной по Парето траектории выполняется 𝑧¯ = (𝑧0 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ). 𝑙−1 𝑙−1 ∑︁ ∑︁ 1 min 𝛼1 [ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧𝑙 )] + 𝛼2 [ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧𝑙 )], 𝛼1 = 𝛼2 = 2 𝑘=0 𝑘=0 55

Рисунок 5.3 Оптимальная по Парето траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) т.к. 3 3 ∑︁ ∑︁ 1 1 min × [ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 )] + × [ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 )] = 2 2 𝑖=0 𝑖=0 = Т.е. 𝐻1 (𝑧0 ) = 3 ∑︁ 1 1 × 22 + × 25 = 23.5 2 2 ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 2 + 6 + 5 + 6 + 3 = 22 𝑘=0 𝐻2 (𝑧0 ) = 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 6 + 5 + 6 + 5 + 3 = 25 𝑘=0 В этой игре: Игрок 1 𝑉 1 (𝑧0 ) = 25, и 𝐻1 (𝑧0 ) = 3 ∑︁ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 22 ≤ 𝑉 1 (𝑧0 ) = 25 𝑘=0 Игрок 2 𝑉 2 (𝑧0 ) = 29, и 𝐻2 (𝑧0 ) = 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 ) = 25 ≤ 𝑉 2 (𝑧0 ) = 29 𝑘=0 Оптимальная по Парето траектория¯ 𝑧 = (¯ 𝑧0 ,¯ 𝑧1 ,¯ 𝑧2 ,¯ 𝑧3 ,¯ 𝑧4 ). В подыгре Γ𝑧1 56

Рисунок 5.4 Игрок 1: 𝑉 1 (𝑧1 ) = 24 3 ∑︁ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧4 ) = 20 ≤ 𝑉 1 (𝑧1 ) = 24 𝑘=1 Игрок 2: 𝑉 2 (𝑧1 ) = 18 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧4 ) = 19 > 𝑉 2 (¯ 𝑧1 ) = 18 𝑘=1 Т.е. на оптимальной траектории 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето имеет место временная несостоятельность Т. к. существует 𝑚 ∈ {0,1, . . . , 𝑙}, такой что 𝑙−1 ∑︁ hi (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ) > 𝑉 𝑖 (𝑧𝑚 ; {𝑖}, 𝑁/{𝑖}) 𝑘=𝑚 57

5.4 Пример временной состоятельности кооперативного решения с процедурой распределения выигрыша (ПРВ) Аналогично выше, введём 𝛽𝑖𝑘 ПРВ и проверим пример 1 (1.2), чтобы индивидуальная рациональность выполнялась для каждого игрока. Как показано на рисуноке ниже, граф 𝐺(𝑁 ′ , 𝐸, (𝑧0 , 𝑧1 )) на ребере (𝑧0 , 𝑧1 ). {0} - источник. Матрицы расходов в графах, на рёбрах, определены как выше. Рисунок 5.5 Игроки N = {1,2}. Выигрыши игроков 𝑖: 𝐻𝑖 (𝑧0 ) = 𝑙−1 ∑︀ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧𝑙 ). 𝑘=0 Пусть вектор весов 𝛼1 = 𝛼2 = 12 , то на оптимальной по Парето траектории выполняется 𝑧¯ = (𝑧1 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ) 𝑙−1 𝑙−1 ∑︁ ∑︁ 1 min 𝛼1 [ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧𝑙 )] + 𝛼2 [ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧𝑙 )], 𝛼1 = 𝛼2 = 2 𝑘=0 𝑘=0 Вычислили, что в этой игре Γ𝑧0 на оптимальной по Парето траектории 𝑧¯ = (𝑧1 , . . . , 𝑧𝑘 , . . . , 𝑧𝑙 ) 𝐻1 (𝑧0 ) = 3 ∑︁ ℎ1 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔1 (𝑧𝑘 ) = 22 𝑘=0 𝐻2 (𝑧0 ) = 3 ∑︁ ℎ2 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔2 (𝑧𝑘 ) = 25 𝑘=0 Найдём значение игры 𝑉 1 (𝑧𝑘 ) и 𝑉 2 (𝑧𝑘 ) в антагонистическом игре двух игроков 𝑉 (𝑧0 ; {1}, {2})). 𝑘 ∈ {0,1,2,3,4}. Обозначаем 𝑉 𝑖 (𝑧𝑘 ; {1}, {2}) упрощённым образом через 𝑉 𝑖 (𝑧𝑘 ), 𝑘 ∈ {0,1, . . . ,𝑙}, 𝑖 ∈ 𝑁 . Случай 1. В игре 𝑧0 . 58

Рисунок 5.6 Игрок 1: 𝑉 1 (𝑧0 ) = 25. Игрок 2: 𝑉 2 (𝑧0 ) = 29. Случай 2. В подыгре Γ𝑧1 Рисунок 5.7 Игрок 1: 𝑉 1 (𝑧1 ) = 24. Игрок 2: 𝑉 2 (𝑧1 ) = 18. Случай 3. В подыгре Γ𝑧2 . Рисунок 5.8 Игрок 1: Игрок 2: Случай Игрок 1: Игрок 2: Случай 𝑉 1 (𝑧2 ) = 15. 𝑉 2 (𝑧2 ) = 15. 4. В подыгре Γ𝑧3 𝑉 1 (𝑧3 ) = 10. 𝑉 2 (𝑧3 ) = 8. 5. При этом на множестве окончательном позиций. 59

Рисунок 5.9 Игрок 1: 𝑉 1 (𝑧4 ) = 3. Игрок 2: 𝑉 2 (𝑧4 ) = 3. Используем теорему 1 𝛽𝑖𝑘 = 𝐻𝑖 (𝑧0 ) − 𝑉 𝑖 (𝑧0 ; {1}, {2}) − [𝑉 𝑖 (𝑧𝑘+1 ; {1}, {2}) − 𝑉 𝑖 (𝑧𝑘 ; {1}, {2})] 𝑙+1 𝛽𝑖𝑘 ПРВ в Γ𝑧0 и 𝐻𝑖 (𝑧0 ) = 3 ∑︀ ℎ𝑖 (𝑧𝑘 , 𝑧𝑘+1 ) + 𝑔𝑖 (𝑧4 ), 𝑖 ∈ {1, 2}, 𝑘 ∈ {0, 1, 2, 3, 4} 𝑘=0 По оптимальной траектории 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето: Для игрока 1 𝛽10 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 22 − 25 = − [𝑉 1 (𝑧1 ) − 𝑉 1 (𝑧0 )] = − [24 − 25] = 0.4 5 5 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 22 − 25 = − [𝑉 1 (𝑧2 ) − 𝑉 1 (𝑧1 )] = − [15 − 24] = 8.4 5 5 22 − 25 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) − [𝑉 1 (𝑧3 ) − 𝑉 1 (𝑧2 )] = − [10 − 15] = 4.4 𝛽12 = 5 5 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 22 − 25 𝛽13 = − [𝑉 1 (𝑧4 ) − 𝑉 1 (𝑧3 )] = − [3 − 10] = 6.4 5 5 22 − 25 𝐻1 (𝑧0 ) − 𝑉 1 (𝑧0 ) 4 𝛽1 = − [0 − 𝑉 1 (𝑧4 )] = − [0 − 3] = 2.4 5 5 Для игрока 2 𝛽11 𝛽20 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 25 − 29 = − [𝑉 2 (𝑧1 ) − 𝑉 2 (𝑧0 )] = − [18 − 29] = 10.2 5 5 𝛽21 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 25 − 29 = − [𝑉 2 (𝑧2 ) − 𝑉 2 (𝑧1 )] = − [15 − 18] = 2.2 5 5 60

𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 25 − 29 = − [𝑉 2 (𝑧3 ) − 𝑉 2 (𝑧2 )] = − [8 − 15] = 6.2 5 5 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 25 − 29 3 𝛽2 = − [𝑉 2 (𝑧4 ) − 𝑉 2 (𝑧3 )] = − [3 − 8] = 4.2 5 5 𝐻2 (𝑧0 ) − 𝑉 2 (𝑧0 ) 25 − 29 4 𝛽2 = − [0 − 𝑉 2 (𝑧4 )] = − [0 − 3] = 2.2 5 5 𝛽22 С помощью 𝛽𝑖𝑘 ,𝑖 ∈ {1,2}, 𝑘 ∈ {0,1,2,3,4} (ПРВ) построим новую игру Γ′𝑧0 . Случай 1. Рисунок 5.10 Значение игры 𝑉 1 (𝑧0 ) и 𝑉 2 (𝑧0 ) в антагонистической игре 2 игроков Γ′𝑧0 . Игрок 1: 𝑉 1 (𝑧0 ) = 24.4 Тогда 𝐻1 (𝑧0 ) = 𝛽10 + 𝛽11 + 𝛽12 + 𝛽13 + 𝛽14 = 22 ≤ 𝑉 1 (𝑧0 ) = 24.4 Игрок 2: 𝑉 2 (𝑧0 ) = 29,То 𝐻2 (𝑧0 ) = 𝛽20 + 𝛽21 + 𝛽22 + 𝛽23 + 𝛽24 = 25 ≤ 𝑉 2 (𝑧0 ) = 29 Оптимальная траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето. Случай 2. В игре Γ′𝑧1 . Рисунок 5.11 61

Игрок 1: 𝑉 1 (𝑧1 ) = 24, 𝛽11 + 𝛽12 + 𝛽13 + 𝛽14 = 21.6 ≤ 𝑉 1 (𝑧1 ) = 24 Игрок 2: 𝑉 2 (𝑧1 ) = 17.2, 𝛽21 + 𝛽22 + 𝛽23 + 𝛽24 = 14.8 ≤ 𝑉 2 (𝑧1 ) = 17.2 Оптимальная траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ) по Парето. Случай 3. В подыгре Γ′𝑧2 . Рисунок 5.12 Игрок 1: 𝑉 1 (𝑧2 ) = 14.4 𝛽12 + 𝛽13 + 𝛽14 = 13.2 ≤ 𝑉 1 (𝑧2 ) = 14.4 Игрок 2: 𝑉 2 (𝑧2 ) = 15 𝛽22 + 𝛽23 + 𝛽24 = 12.6 ≤ 𝑉 2 (𝑧2 ) = 15 Оптимальная по Парето траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ). Случай 4. В игре Γ′𝑧3 . Рисунок 5.13 62

Игрок 1: 𝑉 1 (𝑧3 ) = 10, и 𝛽13 + 𝛽14 = 8.8 ≤ 𝑉 1 (𝑧3 ) = 10 Игрок 2: 𝑉 2 (𝑧3 ) = 6.4, и 𝛽23 + 𝛽24 = 6.4 ≤ 𝑉 2 (𝑧3 ) = 6.4 Оптимальная по Парето траектория 𝑧¯ = (𝑧0 , 𝑧1 , 𝑧2 , 𝑧3 , 𝑧4 ). Случай 5. Очевидно 𝛽14 = 2.4 ≤ 𝑉 1 (𝑧4 ) = 2.4 𝛽24 = 2.2 ≤ 𝑉 2 (𝑧4 ) = 2.2 Используя теорему 1, получили 𝛽𝑖𝑘 , 𝑖 ∈ {1,2}, 𝑘 ∈ {0,1,2,3,4} (ПРВ) в примере, и 𝛽𝑖𝑘 , 𝑖 ∈ {1,2}, 𝑘 ∈ {0,1,2,3,4} удовлетворяет 4 ∑︁ 𝛽𝑖𝑘 ≤ 𝑉 𝑖 (𝑧𝑚 ; {𝑖}, 𝑁/{𝑖}), 𝑖 ∈ {1,2}, 𝑚 ∈ {0,1,2,3,4} 𝑘=𝑚 63

Заключение В данной диссертации во-первых мы исследуем временную состоятельность и представляем формулу для процедуры распределения выигрыша в многошаговой игре кооперации. Мы предоставляем формулу процедуры распределения выигрыша для того, чтобы никто не захотел отклоняться от оптимальной траектории в многошаговой игре кооперации с полной информацией. Это значит с помощью формулы процедуры распределения выигрыша мы преобразуем игру, чтобы кооперация была устойчивой при её реализации в многошаговой игре кооперации. В части исследования теоремы 2 мы построили стратегии наказания и накажем игроков, которые обращаются к иррациональному поведению. С помощью стратегий наказания игроки придерживаются одного и того же принципа оптимальности в любой момент, и поэтому не имеют объективных мотивов, чтобы отклоняться от ранее выбранного решения кооперации. Во-вторых мы исследуем сильную динамическую устойчивость принципов оптимальности в многошаговых кооперативных играх с полной информацией. С помощью понятия процедуры распределения дележа построено динамическое ядро и доказывается его сильная динамическая устойчивость. Из-за сложности построения динамического ядра предложно его упрощение, которое существенно уменьшает объём вычислений. В ряде случаев упрощенное динамическое ядро принадлежит динамическому ядру. Далее, мы исследуем динамический Вектор Шепли в двухшаговой игре с минимальным остовным деревом. На каждом шаге игроки строят минимальное остовное дерево, и вычисляется Вектор Шепли. На втором шаге один из игроков выбывает из игры с вероятностью 𝑝, зависящей от предыдущих стратегий игроков. Используя процедуру распределения дележа проводится регуляризация исходной игры. В конце мы исследуем временную состоятельность для процедуры распределения выигрыша в многошаговой игре кооперации с остовным деревом. С помощью формулы процедуры распределения выигрыша в многошаговой игре кооперации мы исследуем пример, в котором каждый игрок удовлетворяет условию индивидуальной рациональности. 64

Список литературы 1. Neumann L J, Morgenstern O. Theory of games and economic behavior. Princeton, NJ: Princeton university press, 1947. 2. Петросян Л А, Данилов Н Н. Устойчивость решений в неантагонистических дифференциальных играх с трансферабельными выигрышами// Вестник Ленинградского университета, 1979, 1: 52-59. 3. Yeung D W K. Technical Note:"An Irrational-Behavior-Proof Condition In Cooperative Differential Games"// International Game Theory Review, 2006, 8(04): 739-744. 4. Петросян Л А, Зенкевич Н А, Семина Е А. Теория игр: Учебное пособие для университетов// М.: Высшая школа, 1998. 5. Петросян Л А, Принципы оптимальности в многошаговых играх// Соросовский образовательный журнал, 1996 (10): 120-125. 6. Р.Ф. Хабибуллин ,Игры с непротивоположными интересами: учеб. пособие//сост. – Казань: Казан. гос. ун-т, 2009. – 24 с. 7. Nash Jr J F. The bargaining problem[J]. Econometrica: Journal of the Econometric Society, 1950: 155-162. 8. Петросян Л. А., Козловская Н. В., Ильина А. В. Коалиционное решение в задаче сокращения выбросов // Вестник Санкт-Петербургского университета. Серия 10: Прикладная математика. Информатика. Процессы управления. 2010. № 2. С. 46–59. 9. Петросян Л. А., Кузютин Д. В. Устойчивые решения позиционных игр. СПБ.: Изд-во С.-Петерб. ун-та, 2008. 77 c. 10. Петросян Л. А., Зенкевич Н. А. Принципы устойчивой кооперации // Математическая теория игр и её приложения. 2009. Т. 1. № 1. С. 106-–123. 11. L.A. Petrosyan, Vestnik of the Leningrad State University. 13, 1977. 65

12. L.A. Petrosyan and N.N. Danilov, Vestnik of the Leningrad State University. 1, 1979 13. C. Trudeau, Minimum cost spanning tree problems with indifferent agents. Games and Economic Behavior, 84, pp. 137-151, 2014. 14. D. Granot and G. Huberman, Minimum cost spanning tree games. Mathematical programming, 21(1), pp. 1-18, 1981. 15. L. Petrosyan, Cooperative stochastic games. Advances in dynamic games. Birkhauser Boston, pp. 139-145, 2006. 16. Bird C G. On cost allocation for a spanning tree: a game theoretic approach. Networks, 6(4), pp. 335-350, 1976. 17. Kar A. Axiomatization of the Shapley value on minimum cost spanning tree games. Games and Economic Behavior, 38(2), pp. 265-277, 2002. 66

Публикации по теме диссертации 1. Li Yin, Построение сильно динамически устойчивого ядра в кооперативных играх с полной информацией, Процессы управления и устойчивость (CPS’15). 2015 2(1):63 2. Li Yin, The dynamic Shapley Value in the game with spanning tree//Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiy’s Conference), 2016 International Conference. IEEE, 2016: 1-4. DOI: 10.1109/STAB.2016.7541206 3. Li Yin, Dynamic Shapley value in the game with spanning forest (принято к печати)//Constructive Nonsmooth Analysis and Related Topics, St. Petersburg, Russia, 2017 International Conference. IEEE. 4. Li Yin, Dynamic Shapley Value for 2-stage cost sharing game with perishable products (принято к печати)//The 29th Chinese Control and Decision Conference (CCDC), Chongqing, China 2017 International Conference. IEEE. 5. Li Yin, Petrosyan L.A., Dynamic Shapley Value for Irreducible Networks (тезис)//SING12 European Meeting on Game Theory, Odense, Denmark, 2016 6. Li Yin, Dynamic Shapley Value for 2-stage cost sharing game with optimistic players (тезис)//Seventh Workshop on Dynamic Games in Management Science, Paris, France, 2016 7. Li Yin, Dynamic Shapley Value for n-stage cost sharing game with spanning tree (тезис)//Game Theory and Management(GTM2016), Saint Petersburg, Russia, 2016 8. Li Yin, NTU solution formula for finite games with perfect information (тезис)//SING11 European Meeting on Game Theory, Saint Petersburg, Russia, 2015 67

Рецензии:

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

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

Отзывы:

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