Введение 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
Купить

Задача относится к проблеме распределения ресурсов в иерархической структуре. В работе [10] представлена модель классической иерархической игры, в которой задан один управляющий центр и некоторое число подчиненных подразделений с разными связями между игроками. В данной работе мы рассмотрим расширение этой математической модели.
В иерархической многошаговой игре с полной информацией геометрическая структура самой игры является ромбом, то есть из одного центра ресурсы поступают в два подчиненных подразделения, а они, в свою очередь, посылают произведенную промежуточную продукцию последнему подразделению. Последнее подразделение производит продукцию, от которой зависит величина полезности каждого игрока. Теоретико-игровые модели, основанные на такой структуре отношений игроков, называются ромбовидными. Рассматривается модель ромбовидной структуры иерархической игры с расширением, в которой присутствует прямая связь между распределяющим центром и нижним производящим подразделением.
Интерпретацией данной задачи может служить экономическая, экологическая или меж-региональная характеристика, когда какой-то ресурс, в рамках межрегиональной проблематики, например воспринимаемый как человеческий капитал, распределяется федеральным центром, а те, в свою очередь, отправляют его в муниципальные районы. Либо экономическая иерархия с предприятиями, а именно в случае, когда в конгломерате от управляющего центра распределяются финансы. Другой экономической интерпретацией данных процессов может служить несовершенная конкуренция, когда в ходе конфлитогенеза среди разных экономических агентов выстраивается иерархическая структура монопольного подчинения. В рамках этой работы будем считать такую структуру уже сложившейся. Для игры с характеристической функцией будет определена проблема посредничества и производственной кооперации в коалиционном разбиении подмножества игроков всех уровней.
Целью данной работы является нахождение ситуации равновесия по Нэшу в общем и численном виде игры Г, и получение значений определенных характеристических функций кооперативной игры с распределением трансферабельной полезности между игроками согласно принципу оптимальности - вектору Шепли, для чего необходима разработка алгоритма и программной реализации по математической модели, заданной на ромбовидной структуре.
Рассмотрен процесс нахождения ситуации равновесия по Нэшу в определенной игре Г. Для этого доказана лемма о существовании ситуации равновесия по Нэшу и игре Г. Конкретизирована теоретико-игровая модель через определение множеств стратегий игроков, в частности, составление систем неравенств. Показано, что добавление связи поставок ресурсов между центром и игроком нижнего уровня приводит к появлению второй системы неравенств игрока нижнего уровня, которая учитывает формализацию производства с использованием ресурсов управляющего центра отдельно от производства с помощью ресурсов игроков среднего уровня. Были построены оптимизационные задачи линейного и нелинейного программирования с параметрами и показана возможность нахождения ситуации равновесия по Нэшу. Чтобы разрешить проблему нахождения равновесия в игре Г была введена кооперативная подыгра между игроками среднего уровня. Разработано и учтено три варианта одноэлементных характеристических функций игроков среднего уровня для вычисления тремя различными способами минимальной гарантированной полезности, необходимой для вычисления вектора Шепли - принятого принципа оптимальности. Представлены численные примеры, показывающие специфику значений вектора Шепли при использовании трех различных подходов к определению минимальной гарантированной полезности. Сформулирована в общем виде кооперативная игра на ромбовидной структуре, составлены равенства, которые определяют действия игроков в рамках антагонистической игры двух коалиций. Для каждой из коалиции в кооперативной игре выведены формулы для вычисления вектора Шепли. Для программной реализации составлен алгоритм с модифицированным методом Монте-Карло, который позволил конкретнее описать методику случайного поиска для нахождения ситуации равновесия по Нэшу, значений характеристических функций в кооперативной игре и вектора Шепли через полное покрытие области допустимых решений систем линейных неравенств игроков среднего уровня. Определена структура алгоритма, проведен алгоритмический анализ и выявлены особенности применения модифицированного метода Монте-Карло к решению задачи. По алгоритму построена программная реализация, которая позволила численно решить данную задачу. Приведен пример выполнения программы по заданному алгоритму, который показывает специфику в использовании трех подходов к определению одноэлементных характеристических функций.
Обзор литературы
Первая группа литературы относится к классическим работам по теории игр в области неантагонистических многошаговых игр, проблематика которых затрагивается в [10], [8], [4]. Для связи оптимизационных проблем с теоретико-игровыми решениями был использован источник [3] и [11]. Также к первой группе относятся работы в области популярных решений для теоретико-игровых задач, например [9] и [1]. И, также, работы в области алгоритмической теории игр, учитывающие особенности различных моделей [5]. Для понимания теории систем линейных неравенств был использован источник [7].
Вторая группа научной литературы посвящена работам в области иерархических игр, которые освещали аспекты классических решений теории игр. К таким работам относятся научные статьи, например [2], [6].

Купить