Содержание к диссертации
Введение
1 Кооперативные динамические игры 11
1.1 Эволюционное уравнение для характеристической функции в специальном классе многошаговых кооперативных игр 12
1.2 Исследование динамической устойчивости и внутренней динамической устойчивости принципов оптимальности в многошаговой кооперативной игре с древовидной структурой 25
1.3 Исследование возможности построения внутренне устойчивого принципа оптимальности в многошаговой кооперативной игре 37
2 Построение "сильного"равновесия в повторяющихся иерархических играх 55
2.1 Сильное равновесие по Нэшу в повторяющейся иерархической древовидной игре 56
2.2 Построение "сильного"равновесия 66
2.3 Построение "сильного"равновесия в повторяющейся ромбовидной игре 72
3 Исследование параметров кооперативного поведения в многошаговых играх 86
3.1 Описание игры, разыгрываемой на каждом шаге 87
3.2 Определение оптимальной доли отчислений на развитие системы в многошаговой кооперативной древовидной игре 89
3.3 Описание ромбовидной игры, разыгрываемой на каждом шаге 99
3.4 Определение оптимальной доли отчислений на развитие системы в многошаговой кооперативной ромбовидной игре 102
- Исследование динамической устойчивости и внутренней динамической устойчивости принципов оптимальности в многошаговой кооперативной игре с древовидной структурой
- Исследование возможности построения внутренне устойчивого принципа оптимальности в многошаговой кооперативной игре
- Построение "сильного"равновесия в повторяющейся ромбовидной игре
- Определение оптимальной доли отчислений на развитие системы в многошаговой кооперативной древовидной игре
Введение к работе
Актуальность проблемы определяется необходимостью построения математических моделей кооперативного поведения в условиях наличия угроз, затрагивающих интересы большого числа участников конфликта. При этом особо актуальны динамические модели, поскольку реальные конфликты развиваются во времени. Важное значение имеет вопрос об условиях, при которых игроки будут вступать в соглашение, а также сохранение условий кооперации на всем протяжении многошаговой игры. Различным аспектам динамических кооперативных игр посвящены работы [4, 7, 19, 21, 25, 33, 38, 46, 55].
Теория динамических кооперативных игр отличается множественностью принципов оптимальности, привнесенных из классической кооперативной теории [3, 11, 23, 29, 33, 34, 50, 51]. Однако, попытка переноса "статических"принципов оптимальности в динамические модели требует разработки особого механизма, учитывающего особенности динамического процесса принятия решений. Таким механизмом является концепция динамической устойчивости принципов оптимальности. Динамическая устойчивость решения означает, что любой отрезок оптимальной траектории от данного состояния до конечного определяет оптимальное движение относительно соответствующих начальных состояний. Отсутствие динамической устойчивости приводит к возможности отказа от ранее принятого плана действий в некоторый текущий момент. В связи со сказанным, при исследовании динамических кооперативных игр важное значение имеет построение динамически устойчивых решений. В разное время исследованиям динамической устойчивости решений были посвящены работы [13, 14, 33, 46, 52].
В данной работе исследуется динамическая устойчивость и внутренняя динамическая устойчивость принципов оптимальности в многошаговых иерархических играх, выводится эволюционное уравнение для характеристической функции в многошаговых кооперативных иерархических играх. В разное время исследованию иерархических игр были посвящены работы [6, 20, 33].
Для данного класса игр строится сильное равновесие по Нэшу. Выводятся аналитически условия существования сильного равновесия для повторяющихся иерархических игр с древовидной и ромбовидной структурами.
Основной целью работы является исследование кооперативных динамических игр, построение уравнений эволюции характеристической функции в многошаговых кооперативных иерархических играх, исследование свойств динамической устойчивости и внутренней динамической устойчивости принципов оптимальности указанного класса игр, исследование возможности построения принципа оптимальности, для которого всегда выполнялось бы свойство внутренней динамической устойчивости, вывод достаточных условий существования сильного равновесия в повторяющихся играх распределения ресурсов специального.
Научная новизна. В диссертационной работе впервые были исследованы вопросы динамической устойчивости решений для много- шаговых кооперативных иерархических игр, предложен способ построения новых принципов оптимальности, для которых выполнялось бы свойство внутренней динамической устойчивости, выведены уравнения эволюции характеристической функции, получены достаточные условия существования сильного равновесия (равновесия, устойчивого относительно отклонения коалиций игроков) в бесконечношаговых повторяющихся играх с иерархическими играми распределения ресурсов на каждом шаге.
Практическая ценность. Исследуемые в диссертации иерархические игры являются удобными моделями для описания систем распределения материальных, финансовых и трудовых ресурсов и имеют применение в области экономики.
Основные положения выносимые на защиту:
Построение многошаговых динамических кооперативных игр на основе вывода новых уравнений, определяющих эволюцию характеристической функции в процессе игры.
Исследование для указанного класса игр динамически устойчивых и внутренне динамически устойчивых принципов оптимальности. Иллюстрация указанного подхода на примере иерархических игр распределения ресурсов и ромбовидных игр.
Вывод достаточных условий существования сильного равновесия для повторяющихся иерархических игр распределения ресурсов специального вида.
Определение оптимальной доли отчислений на эволюцию системы с целью достижения максимального выигрыша за определенное число шагов.
Апробация работы. Научные и практические результаты докладывались на конференциях "Процессы управления и устойчивость "в Санкт-Петербургском Государственном университете в 1999, 2000, 2003 гг, на 10 Международном симпозиуме по динамическим играм и приложениям
В первой главе приводится постановка задачи. Описывается процесс построения многошаговой кооперативной игры, с использованием выигрышей игроков, полученных на предыдущих шагах. Выводятся уравнения, описывающие эволюцию характеристической функции в процессе игры, на примере иерархической кооперативной древовидной игры.
В 1.1 рассматривается многошаговая игра G на каждом шаге которой разыгрывается одношаговая иерархическая древовидная игра (n + 1)-го игрока. Описывается процесс построения многошаговой кооперативной игры, выводятся уравнения эволюции характеристической функции в процессе игры. В данном параграфе приводятся определения процедуры распределения дележа, динамически устойчивого и внутренне динамически устойчивого принципа оптимальности.
В 1.2 проводится полное исследование динамической устойчивости и внутренней динамической устойчивости принципа оптимальности многошаговой игры, описанной в 1.1, отличие рассматриваемой модели заключается в том, что все параметры модели принадлежат R1. В результате получены явные аналитические формулы для оптимального дележа, эволюционные уравнения для характеристической функции, в явном виде построена характеристическая функция многошаговой игры.
В 1.3 исследуется вопрос, можно ли построить такой принцип оптимальности, для которого всегда будет выполняться свойство внутренней динамической устойчивости? Построение такого принципа достаточно сложно. Делается предположение, что один из способов заключается в нахождении пересечения принципов оптимальности многошаговой игры, порожденных различными дележами.
Во второй главе рассматривается бесконечношаговая игра G с кооперативной иерархической игрой Г на каждом шаге. Для этой игры строится сильное равновесие по Нэшу с использованием механизма регуляризации [47, 48]. Определяется "кооперативная траектория", предыстория и функция выигрыша игроков для игры G и подыгр Gk, начинающихся с шага к = 0,1,2,... этой игры. Вводится процедура распределения дележа и на этой основе проводится регуляризация игры вдоль кооперативной траектории. Вводятся стратегии, которые включают возможность наказания игроков, отклоняющихся от заранее оговоренной траектории. Формулируются достаточные условия, при выполнении которых эти стратегии образуют сильное равновесие по Нэшу для случаев, когда мгновенная игра, разыгрываемая на каждом шаге имеет древовидную или ромбовидную структуру.
В 2.1 приводится постановка задачи, определение сильного равновесия по Нэшу, определение выигрыша в бесконечношаговой игре. Рассматривается бесконечношаговая повторяющаяся иерархическая игра G, выводятся условия существования сильного равновесия по Нэшу в повторяющейся иерархической древовидной игре.
В 2.2 рассмотрен частный случай бесконечношаговой повторяю- щейся игры G с иерархической древовидной игрой (п + 1)-го игрока на каждом шаге. Выводятся условия существования сильного равновесия в явной аналитической форме.
В 2.3 рассматривается частный случай бесконечношаговой повторяющейся игры G с иерархической ромбовидной игрой четырех лиц, разыгрываемой на каждом шаге. В данном параграфе также получены условия существования сильного равновесия по Нэшу в аналитической форме.
В третьей главе рассматривается кооперативная многошаговая динамическая игра G. На каждом шаге многошаговой игры разыгрывается одношаговая иерархическая кооперативная игра Г. Рассматриваются две модели одношаговых иерархических игр с древовидной и ромбовидной структурами. Многошаговая кооперативная игра с древовидной игрой на каждом шаге подробно описана в первой главе. Описание иерархической ромбовидной игры дано во второй главе. Многошаговая игра строится следующим образом. На каждом шаге игроки отчисляют какую-то долю от заработанного дохода на развитие системы, а другую часть оставляют на собственные нужды. Под развитием системы понимаем закупку ресурсов, улучшение производства. На каждом следующем шаге параметры нашей задачи строятся с использованием отчислений от выигрышей игроков, заработанных на предыдущем шаге. Отличие этой главы от главы 1 состоит в том, что нас интересует, какую именно долю от собственного выигрыша игроки должны отчислять на развитие системы, для получения максимального дохода, тогда как в первой главе доля отчислений от выигрыша игроков использовались только для построения многошаговой игры.
В 3.1 приводится описание древовидной модели игры четырех иг- роков. Строятся характеристическая функция и вектор Шепли для данной игры.
В 3.2 строится многошаговая игра, с использованием отчислений игроков от полученного выигрыша на развитие системы. Отличие процесса построения многошаговой игры заключается в том, что в качестве принципа оптимальности на каждом шаге используется вектор Шепли. Для данной модели была получена оптимальная доля отчислений игроков, направляемая на развитие системы. Приводится численный пример, результаты примера иллюстрируются диаграммами.
В 3.3 приводится описание ромбовидной модели четырех игроков. Определяются новые стратегии игроков, строятся характеристическая функция и вектор Шепли.
В 3.4 строится многошаговая игра, с использованием отчислений игроков от полученного выигрыша на развитие системы. Здесь также качестве принципа оптимальности на каждом шаге используется вектор Шепли. Выводятся аналитические формулы для вектора Шепли многошаговой ромбовидной игры. Вычисляется оптимальная доля отчислений игроков, направляемая на развитие системы. Приводится численный пример, результаты которого проиллюстрированы диаграммами.
Исследование динамической устойчивости и внутренней динамической устойчивости принципов оптимальности в многошаговой кооперативной игре с древовидной структурой
Рассмотрим многошаговую игру G, на каждом шаге которой разыгрывается кооперативная иерархическая древовидная игра (n + 1)-го игрока. Пусть на первом шаге разыгрывается игра Г. Нормальная форма одношаговой игры выглядит следующим образом: где N = (AQ, В\,..., Вп) - множество игроков, AQ - административный центр, и ВІ, г = 1,п - подчиненные производственные подразделения. Множества стратегий будут немного изменены, по сравнению с общим случаем. Будем считать, что все параметры игры Г из Я1. Множество стратегий игрока AQ, Множество стратегий игрока Д, г = 1,п, ЖІ - это производственная программа центра ВІ, щ - коэффициенты производительности, СХІ - количество имеющихся ресурсов центра В{. Определим функции выигрыша игроков HQ - функция выигрыша административного центра AQ, где Q Є R1 -полезность для центра AQ, ОТ продукции выпускаемой подразделени ями Д, г = 1,п. НІ - функция выигрыша центра Д, і = 1,п, где di Є Rl - полезность выпускаемой продукции для центра Б . {и, х\(-),..., хп(-)} назовем ситуацией в игре Г. Характеристическая функция игры Г принимает конкретный вид: СІ -\- d Обозначим через Qi — -, г = 1,...,n, тогда величины щ определяются следующим образом Действительно из (1.24) мы имеем ХІ — —. Возьмем выраже (щ + он) ниє для суммарного выигрыша и подставим вместо Х{, тогда "(d + d iai + Ui) получим 2 Мы видим что для нахождения г;(TVJ г=1 аі нам необходимо найти максимум линейной функции по переменной и. Из (1.23) мы имеем щ Ъ. Коэффициенты —, г = 1,..., п г=1 аі (с,- + dj) (ci + di) . есть постоянные и если — — = max , г = 1,... ,п, тогда dj аі исходная сумма достигает максимума при Щ = Ь. Рассмотрим следующий вектор 7 — (то 7ь 7п): .27) Легко проверить, что вектор 7) построенный по формулам (1.27) является дележом из С-ядра, одношаговой игры Г. Рассмотрим процесс построения многошаговой игры G. Предположим, что на первом шаге игры G реализовалась игра Г1 с характеристической функцией v1 (S) и ядром С1. Пусть 71 = (7о 7і 7n) — дележ из ядра С . Компоненты этого дележа имеют вид: сц Мы полагаем, что на всех шагах игры G будет выполняться условие (ci 4- d\)/a\ = max(cj + di)/a,i, і = 1,..., n и следовательно щ = b, остальные щ = О, і = 2,..., п. Опишем процедуру изменения параметров задачи. Обозначим через р процент отчислений игроков на развитие системы. На первом шаге многошаговой игры G каждый из игроков отчисляет какую-то часть на развитие системы, которая переходит на следующий шаг, то есть pjj, г = 0,1,...,п. Вектор 71 — (7о 7і In) Є 1 можно интерпретировать как вектор инвестиций. Эти инвестиции могут быть использованы на различные нужды игроков (закупку ресурсов, улучшение производственных возможностей или собственные нужды игроков). Величину (1 —p) i каждый из игроков оставляет себе. Это будет личный выигрыш каждого игрока. Здесь 7о _ компонента дележа для административного центра Дь 7i 7n соответственно компон{, тогда "(d + d iai + Ui) получим 2 Мы видим что для нахождения г;(TVJ г=1 аі нам необходимо найти максимум линейной функции по переменной и. Из (1.23) мы имеем щ Ъ. Коэффициенты —, г = 1,..., п г=1 аі (с,- + dj) (ci + di) . есть постоянные и если — — = max , г = 1,... ,п, тогда dj аі исходная сумма достигает максимума при Щ = Ь.
Рассмотрим следующий вектор 7 — (то 7ь 7п): .27) Легко проверить, что вектор 7) построенный по формулам (1.27) является дележом из С-ядра, одношаговой игры Г. Рассмотрим процесс построения многошаговой игры G. Предположим, что на первом шаге игры G реализовалась игра Г1 с характеристической функцией v1 (S) и ядром С1. Пусть 71 = (7о 7і 7n) — дележ из ядра С . Компоненты этого дележа имеют вид: сц Мы полагаем, что на всех шагах игры G будет выполняться условие (ci 4- d\)/a\ = max(cj + di)/a,i, і = 1,..., n и следовательно щ = b, остальные щ = О, і = 2,..., п. Опишем процедуру изменения параметров задачи. Обозначим через р процент отчислений игроков на развитие системы. На первом шаге многошаговой игры G каждый из игроков отчисляет какую-то часть на развитие системы, которая переходит на следующий шаг, то есть pjj, г = 0,1,...,п. Вектор 71 — (7о 7і In) Є 1 можно интерпретировать как вектор инвестиций енты дележа 71 Для производственных подразделений Д,г = 1,... ,п. Будем предполагать, что заработанный игроками выигрыш может быть потрачен на закупку ресурсов или личные нужды. Используя эти рассуждения на втором шаге параметры нашей задачи могут быть записаны следующим образом где Si - стоимость ресурсов н каждом шаге для каждого из подчиненных производственных подразделений, so - стоимость ресурсов для административного центра. Используя новые параметры б2, а2, і = 1,... ,п мы получим значение характеристической функции на втором шаге:
Исследование возможности построения внутренне устойчивого принципа оптимальности в многошаговой кооперативной игре
Возникает вопрос, можно ли построить такой принцип оптимальности, для которого всегда будет выполняться условие внутренней динамической устойчивости? Его построить достаточно сложно. Одним из способов является построение пресечения принципов оптимальности многошаговой игры, порожденных различными дележами. Покажем как будет строится это пересечение. Для этих целей рассмотрим одношаговую иерархическую игру Г, имеющую такую же структуру, как в 1.2. На первом шаге рассмотрим характеристическую функцию vl(S) и С1 — ядро одношаговой игры, построенное с помощью функции Vі(S). С-ядро множественный принцип оптимальности, и поэтому на втором шаге мы можем построить множество характеристических функций следующим образом. Возьмем некоторое конечное множество дележей из ядра С1 и обозначим его через Д = {j, 2) р}- С помощью этого множества дележей Л построим множество характеристических функций vj(S; j), j = 1,... ,р. Соответственно на втором шаге игры мы уже имеем мно жество игр Gj, длинною два шага, каждой из которых соответствует свой принцип оптимальности Cj. На третьем шаге мы получим множество характеристических функций Vj(S\ ?) и соответственно множество принципов оптимальности Cj. Продолжая процесс далее, на шаге к для каждой из многошаговых G мы имеем свою характеристическую функцию Vj(S; j l), и соответствующий ей принцип оптимальности С , j = 1,... , р. После га шагов мы имеем множество многошаговых игр Gj. Каждая из этих игр имеет характеристическую функцию При помощи этой функции построим принципы оптимальности Cj для каждой из многошаговых игр Gj, j = 1,... , p. Рассмотрим пересечение множеств Cj. Обозначим его через М: Рассмотрим некоторое подмножество множества дележей А, обозначим его через L = {д,..., jt], j = 1,... ,р, L С А. Ставится вопрос о том, будут ли множества CjS, порожденные L принадлежать пересечению М. Если это выполняется, тогда мы можем утверждать, что для любого дележа jS, s = 1,... ,t, будет выполняться s Є C(jS), то есть множества CjS, принадлежащие М можно считать внутренне динамически устойчивым принципом оптимальности. Однако проверка принадлежности множеств Cj, порожденных L пересечению М заключает в себе некоторую сложность, поскольку надо проверить принадлежность дележей jS каждому из множеств, входящих в пересечение. Для того, чтобы обойти эту трудность введем новую функцию U)(S), которая имеет вид Построенная таким образом фун
Продолжая процесс далее, на шаге к для каждой из многошаговых G мы имеем свою характеристическую функцию Vj(S; j l), и соответствующий ей принцип оптимальности С , j = 1,... , р. После га шагов мы имеем множество многошаговых игр Gj. Каждая из этих игр имеет характеристическую функцию При помощи этой функции построим принципы оптимальности Cj для каждой из многошаговых игр Gj, j = 1,... , p. Рассмотрим пересечение множеств Cj. Обозначим его через М: Рассмотрим некоторое подмножество множества дележей А, обозначим его через L = {д,..., jt], j = 1,... ,р, L С А. Ставится вопрос о том, будут ли множества CjS, порожденные L принадлежать пересечению М. Если это выполняется, тогда мы можем утверждать, что для любого дележа jS, s = 1,... ,t, будет выполняться s Є C(jS), то есть множества CjS, принадлежащие М можно считать внутренне динамически устойчивым принципом оптимальности. Однако проверка принадлежности множеств Cj, порожденных L пересечению М заключает в себе некоторую сложность, поскольку надо проверить принадлежность дележей jS каждому из множеств, входящих в пересечение. Для того, чтобы обойти эту трудность введем новую функцию U)(S), которая имеет вид Построенная таким образом функция может не быть супераддитивной. Дележ jS, для которого будет выполняться следующее условие будет принадлежать M и для него будет выполняться , Є С ( ). Пример 1.1. Данный пример мы приводим с целью показать трудность проверки условия (1.35), а также нетривиальность его выполнения даже в простейших случаях. Рассмотрим кооперативную четырехшаговую кция может не быть супераддитивной. Дележ jS, для которого будет выполняться следующее условие будет принадлежать M и для него будет выполняться , Є С ( ). Пример 1.1. Данный пример мы приводим с целью показать трудность проверки условия (1.35), а также нетривиальность его выполнения даже в простейших случаях. Рассмотрим кооперативную четырехшаговую игру трех лиц. Обозначим ее через G. На первом шаге разыгрывается игра Г1, имеющая такую же структуру, как в 1.2. Обозначим через v1(S) и С1 соответственно характеристическую функцию и принцип оптимальности этой игры. Будем считать, что в качестве принципа оптимальности выбрано С-ядро. Пусть 1 = (oifi.$) Є С Дележ из ядра С1, где fj -компонента дележа, соответствующая административному центру AQ, и, соответственно, і,г компоненты, относящиеся к подчиненным центрам В\, В2- На втором шаге, используя дележ мы получим характеристическую функцию v2(S; 1) и, соответственно ядро С2. Для всех последующих шагов действуем аналогично. Обозначим через к = (j, f, j,), fc = 1,2,3,4 дележ, принадлежащий принципу оптимальности Ск на шаге к. Выпишем значения характеристической функции v(S; ), j = 1, 2, 3. многошаговой игры G.
Построение "сильного"равновесия в повторяющейся ромбовидной игре
Рассмотрим бесконечношаговую повторяющуюся игру G, но изменим структуру одношаговой игры, повторяющейся на каждом шаге. В этом разделе на каждом шаге бесконечношаговой игры G будет разыгрываться иерархическая ромбовидная игра четырех лиц, которую обозначим через Г. Будем считать, что на первом шаге ходит игрок AQ И выбирает стратегию и = (ui,U2) из некоторого множества U1, где U — множество стратегий игрока AQ. Элемент (стратегия) и Є U ограничивает возможности выборов игроков 5і, Вч на следующем шаге. Таким образом множество выборов игрока В[ оказывается функцией параметра и\ (обозначим его через B[(ui)), и, аналогично, множество выборов игрока В2 оказывается функцией параметра ui (обозначим его через B2(u2))- Параметры ш\ Є В[(щ) и ш\ Є В2(и2), выбираемые игроками В\ И B I задают ограничения на множество выборов игрока С" на третьем шаге игры, то есть это множество оказывается функцией параметров UJ\ и ш2. Обозначим его через C (OJI,U)2), а элементы этого множества производственные программы) — через v. Пусть выигрыши всех игроков Ао, Bi, ?2, зависят только от производственной программы и, выбираемой игроком С, и равны соответственно h(v)t /гМ, зМ, hiy), где ІІ(І/) 0, і = 1,2,3,4. Такую иерархическую игру можно представить как бескоалиционную игру четырех лиц в нормальной форме, если считать стратегиями игрока Ао элементы и = (щ,и2) Є U , а стратегиями игроков ?і, В% и С — считать функции ш\{и\), Ш2(и2) и ( 1,0 ), со значениями в множествах B[(ui), B 2(u2), С" (0 ,0) соответственно (обозначим множества таких функций через В ъ В ъ С). Полагая получим нормальную форму игры Г Рассмотрим вспомогательную кооперативную игру Г, на основе игры Г. Для игры Г, для каждой коалиции S С {AQ,BI, В2,С] определим v(S) как наибольший гарантированный выигрыш S в антаго нистической игре между коалицией S выступающей в качестве максимизирующего игрока, и коалицией S = {Лз, В\, Вг, С} \S. Предположим, ЧТО Существует Такое V Є С" ( 1,60) ДЛЯ ВСеХ и \, Съ 2, что Будем различать два вида коалиций: В первом случае 5 С {AQ, В\, В2} и игрок С, являющийся членом коалиции N \ 5, может выбрать стратегию VQ : 1{(ь о) = 0 і = 1, 2, 3,4, поэтому г;(5) = 0. Во втором случае определим характеристическую функцию v(S) следующими равенствами: При таком определении характеристическая функция обладает свойством супераддитивности, т.е. для любых S, R С {Ао, В\, Z?2, С}, для которых S U R = 0, имеет место неравенство v(S П R) v(S) + v(R). Рассмотрим дальше конкретный случай, когда множества U , В{, В 2, С имеют следующий вид: здесь / 0,h,Ui,U2 Є Д1, /г — это ограничения на ресурсы центра Ао, аі, а,2, Ь\, &2) (і Д1 - это коэффициенты производительности, все числа аі, 22, &і, &2, d неотрицательны. Из условий на множества стратегий имеем следующие ограничения 0 ІІІ —, 0 112 —, что центры Bi, ?2,
С не могут закупать ресурсы вне этой системы, а используют только те, что им поставил административный центр Ао. Вычислим значение характеристической функции для конкретных функции выигрыша и рассмотрим способ вычисления на примере некоторых коалиций. Для примера возьмем S = {С}, S = {Ао, В\, В2, С}. Пусть функции выигрыша игроков выглядят следующим образом Берем максимумы и минимумы и получаем Далее имеем уже функцию от переменных o i, w2 и рассматриваем uj\ как постоянную. Так как минимальное значение для ы2 достигается в О, то получаем аналогично c i минимально в 0. В результате имеем и, соответственно значение характеристической функции v(C) будет раВНО ZA. Применим подобные рассуждения для вычисления v(S), v(S) = max max max max (4j3 v + z\ + z2 + 2 + zA Используя, описанный ранее способ, получили следующее выражение: Далее получаем функцию двух переменных «і и «2 и решаем систему считаем что z\ + z2 + 2 + 2:4 на максимум не влияют и мы можем эту добавку не рассматривать. Из условий, наложенных на множества Подставляем выражение для и2 в функцию максимума и получаем (и\ h — a\U\\ max -—I : после привидения слагаемых получаем подставляя максимальное значение для и\ = —, (и2 = 0) получаем h „ значение максимума, равное ——. В случае подстановки выражения h — а2и2 h для щ = , а затем максимального значения для и2 = — а\ а2 (щ = 0) получаем следующее выражение тахг;(5) = ——, таким образом V(AQ, В\, В2, С) = 4/3-7—тт + 21 + 2:2 + 2:3 + z±, при условии на коэффициенты производительности — — и Остальные значения характеристической функции даны ниже. z4; d(aibi) 4P 7 ГТ + z\ + z2 + ZZ + 2T4, S = {Ao,i,2,C}, v{S) = \ ai a2 62 61 d (a2b2) P—, _ r \ +21+22 + 23 + Z4, CL\ 0-2 b2 h Здесь P и Z{ - заданные константы. Пусть 7 = (70)7i5 72) 7з) дележ из ядра С (Г) одношаговой игры Г с компонентами hi а\ а2 d (аібі) 62 61 7о = hi a\ a2 d (a2b2) 62 61 7i = z2, 72 = 3, 73 = Z4. Введем обозначение у = {и, 0 (-),0 (-), (-)) Пусть {u,o7i(-),072(-),1/(-)} - ситуация в игре Г в которой выигрыш игроков максимален. 2Hi(u,UJi(-),u2(-),T7(-)) = max Y.Hi(u,uji,Lj2,v) = iN {и,"і,"2,"}іЄлг (2.30) = v(N). В повторяющейся кооперативной игре на каждом шаге будет разыгрываться у = {%ЇЇІ(-),Ш2(-),Р(-)}. Обозначим G(h ) подыгру бесконечношаговой игры G, начинающейся с шага тп = 0,1,... с предысторией h = (( ,07 (-),07 (-),
Определение оптимальной доли отчислений на развитие системы в многошаговой кооперативной древовидной игре
Рассмотрим бесконечношаговую игру G, на каждом шаге которой разыгрывается одношаговая игра Гк и рассмотрим первые т шагов. Обозначим через G игру, реализовавшуюся за эти т шагов. Многошаговая игра G представляет собой т - кратное повторение кооперативной игры Тк. От шага к шагу параметры игры (характеристические функции) Гк изменяются. Процесс построения многошаговой игры G совпадает с уже описанным в первой главе. Напомним основные моменты. Пусть на первом шаге реализовалась игра Г1 с характеристической функцией vi(S) и вектором Шепли Ф1, выбранном в качестве принципа оптимальности. Пусть Ф = (ф(Ао),ф(Ві),ф(В2),ф(Вз)), ф(Ао) — компонента вектора Шепли, соответствующая административному центру AQ, ф(Ві), і = 1,2,3 — компонента, относящаяся к г-му производственному подразделению. На первом шаге игры игроки инвестируют долю от заработанного выигрыша компонент вектора Шепли на развитие системы на следующем шаге. Обозначим эту долю через р, тогда эти отчисления запишутся как рф(Ао), рф(Ві), рф(В2), рф(В ), р Є (0,1). Предполагается что административный центр AQ может вложить свою компоненту вектора Шепли на увеличение ресурсов системы и свои собственные нужды, аналогично на каждом шаге каждый из центров В{ может инвестировать свой доход ф(Вг), г = 1,2,3 на улучшение производительности, увеличение запаса собственных ресурсов центра и на личные нужды. Такое инвестирование приведет к изменению параметров задачи, а значит на втором шаге мы получим новую характеристическую функцию V2(S) и новый вектор Шепли Ф2. Аналогично предыдущим шагам предположим, что на шаге к — 1 реализовалась игра Тк 1 с характеристической функцией Vk-i(S) и вектором Шепли Фк_1. Тогда игра Г строится с использованием компонент вектора Шепли игры Г&_і следующим образом (идею использования вектора Шепли на следующем шаге предложили Петросян Л.А., Filar G.A. [33]). Предполагается что административный центр AQ может вложить свою компоненту вектора Шепли на увеличение ресурсов системы и на свои собственные нужды, аналогично на каждом шаге каждый из центров В{ может инвестировать свою компоненту вектора Шепли на увеличение производительности, увеличение запаса лич ных ресурсов и на собственные нужды. Таким образом на шаге к мы получим новую характеристическую функцию Vk(S) и новый вектор Шепли Фк. Предположим, что доля отчислений не зависит от шага. Общая сумма отчислений будет выглядеть следующим образом N - коалиция всех игроков. Предположим, что на шаге к, величина T&_i будет инвестирована игроками на развитие системы, значит доход всех центров возрастет. Значение (1 — p)Vk(N) центры будут оставлять для своего собственного развития.
Это и будет выигрыш всех игроков на каждом шаге. Суммарный доход игроков за т шагов обозначим как WP(N) = m (1 — p)vk(N). Будем искать такое значение р при котором функция fc=i WP(N) будет максимальна после т шагов. Для этого будем искать на каждом шаге значение функции Vk(N). Выпишем динамику изменения функции Vk(N) на каждом шаге. (vfc- iV), !"1, /-1. Pt\ /-1) - неотрицательная функция, fit1 - вспомогательные, фиксированные величины, которые показывают, как будет распределяться Тк-\ между игроками на к шаге. Введем дополнительные обозначения: Предположим, что множества стратегий С/, Ц,(щ), игроков AQ, ВІ, і = 1,2,3 имеют вид (3.1). Предположим, что в нашей модели запасы ресурсов для центра AQ и запасы личных ресурсов центров ВІ вычисляются по следующим формулам: Ь = bo -Ь уг , и а.{ = OLQ + yf\ sf, і = 1,2,3,4 стоимость ресурсов на к шаге, ctQ, 6о начальные запасы, имеющихся ресурсов центров AQ И Д, г = 1,2,3. В данной модели мы предполагаем, что игроки могут инвестировать общий выигрыш только на увеличение запасов ресурсов и на личные нужды. Ввиду обозначений (3.4) мы имеем три различных варианта. Предположим, что выражение {c\ + di)/ai максимально среди величин (СІ + di)/ai, г = 1,2, 3. Тогда применяя формулы для расчета характеристических функций и обозначения (3.8) мы получим выражения для vk{N) Мы ищем максимум функции Vk-i(N) по /?г- 1, г = 1,2,3,4. Ра (ci + di) (CJ + di) нее мы сделали предположение о том, что - = max , г = 1,2,3, поэтому распределение компонент вектора Шепли с шага к — 1 между величинами /-1) А -1 не приведет к увеличению значения Vk(S). Поэтому в нашем случае /-1 = Р% 1 = 0. Между @і г и @2 1 величину Тк-і можно распределить одним из следующих способов, Pi l = Tfc_i, p2 l = Tfc_i или какими-то долями между Рі г и /ЗІ-1- Предположим, что способ распределения Tk-l между вспомогательными величинами /?i_1, /-1 фиксирован. Пусть рк і _ _71A;_1) 1 - jfc_i тогда используя выражение (3.6) мы по-лучим На каждом шаге выигрыш каждого игрока равен его компоненте вектора Шепли. В этом случае значение (1 — p)vk(N) распределяется между центрами на шаге к. Таким образом в игре G компоненты вектора Шепли на fc-ом шаге имеют следующий вид: В случае, когда ft "1 = ft "1 = 0 и /З "1 = izU, /-1 = \тк-і и
