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

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

Введение 2
Обзор литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Глава I Ромбовидная иерархическая структура 4
1.1. Описание теоретико-игровой модели . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2. Постановка задач оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3. Формулировка кооперативной игры . . . . . . . . . . . . . . . . . . . . . . . . 16

Глава II Численный эксперимент 19
2.1. Модификация метода Монте-Карло и алгоритм программы . . . . . . . . . . 19
2.2. Результаты эксперимента с нахождением ситуации равновесия по Нэшу . . . 39
2.3. Результаты эксперимента с кооперативной игрой . . . . . . . . . . . . . . . . . 42

Заключение 45

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

Приложение 48

В данной работе рассмотрена проблематика задачи распределения ресурсов в ромбо-
видной иерархической теоретико-игровой модели, которая описывает свойства рыночных,
межрегиональных, экологических и иных классов задач.
Конкретизация теоретико-игровой модели через определение множеств стратегий игро-
ков в игре Γ показала, что добавление связи поставок ресурсов между центром и игроком
нижнего уровня, которая учитывает формализацию производства с использованием ресур-
сов управляющего центра отдельно от производства с использованием ресурсов игроков
среднего уровня, приводит к появлению дополнительной системы линейных неравенств
игрока нижнего уровня. Данное расширение обосновывается тем, что игроки среднего
уровня посылают игроку нижнего уровне не тот же набор типов ресурсов, что и управля-
ющий центр. Это существенное для реальных задач дополнение является оригинальным
и не рассматривалось ранее в литературе.
Рассмотрен процесс нахождения ситуации равновесия по Нэшу в определенной игре Γ.
Для этого доказана лемма о существовании ситуации равновесия по Нэшу и игре Γ. Кон-
кретизирована теоретико-игровая модель через определение множеств стратегий игроков,
в частности, составление систем неравенств. Показано, что добавление связи поставок
ресурсов между центром и игроком нижнего уровня приводит к появлению второй систе-
мы неравенств игрока нижнего уровня, которая учитывает формализацию производства
с использованием ресурсов управляющего центра отдельно от производства с помощью
ресурсов игроков среднего уровня. Были построены оптимизационные задачи линейно-
го и нелинейного программирования с параметрами и показана возможность нахожде-
ния ситуации равновесия по Нэшу. Чтобы разрешить проблему нахождения равновесия
в игре Γ была введена кооперативная подыгра между игроками среднего уровня. Раз-
работано и учтено три варианта одноэлементных характеристических функций игроков
среднего уровня для вычисления тремя различными способами минимальной гарантиро-
ванной полезности, необходимой для вычисления вектора Шепли – принятого принципа
оптимальности. Представлены численные примеры, показывающие специфику значений
вектора Шепли при использовании трех различных подходов к определению минималь-
ной гарантированной полезности. Сформулирована в общем виде кооперативная игра на
ромбовидной структуре, составлены равенства, которые определяют действия игроков в
рамках антагонистической игры двух коалиций. Для каждой из коалиции в кооператив-
ной игре выведены формулы для вычисления вектора Шепли. Для программной реализа-
ции составлен алгоритм с модифицированным методом Монте-Карло, который позволил
конкретнее описать методику случайного поиска для нахождения ситуации равновесия
по Нэшу, значений характеристических функций в кооперативной игре и вектора Ше-
пли через полное покрытие области допустимых решений систем линейных неравенств
игроков среднего уровня. Определена структура алгоритма, проведен алгоритмический
анализ и выявлены особенности применения модифицированного метода Монте-Карло к
решению задачи. По алгоритму построена программная реализация, которая позволила
численно решить данную задачу. Приведен пример выполнения программы по заданному
алгоритму, который показывает специфику в использовании трех подходов к определению
одноэлементных характеристических функций.
В ходе решения численного примера наглядно показано, что от способа расчета ми-
нимальной гарантированной полезности зависит то, какие значения компонент вектора
Шепли будут найдены для игроков среднего уровня, и то, что игрокам не всегда выгод-
но исходить из “оптимистичного”варианта, при котором управляющий центр отправляет
только один или два нулевых вектора ресурсов непосредственно игрокам среднего уровня.
В рамках продолжения данной научной проблематики возможны улучшения по части эв-
ристик и методов, которые можно использовать для решения систем линейных неравенств
в данной структуре. Рассмотрение динамики процесса также позволит полно раскрыть
потенциал представленной иерархической структуры. Не исключается также дальнейшее
расширение структуры для лучшего отражения отношений в иерархии между игроками.

[1] Amer R., Carreras F. Cooperation Indices and Weighted Shapley Values.
Mathematics of Operations Research. – Informs, USA, 1997, 14p. URL:
https://pubsonline.informs.org/doi/pdf/10.1287/moor.22.4.955