Содержание к диссертации
Введение
1 Кооперативные дифференциальные игры со случайной продолжительностью . 13
1.1 Определение кооперативной дифференциальной игры Ту(х$)
в форме характеристической функции .13
1.2 Принцип динамической устойчивости в игре Гу(жо) 20
1.3 Случай разрывной функции распределения момента окончания игры 24
1.4 Регул яризованные динамически устойчивые принципы оптимальности 29
1.5 Уравнение Гамильтона-Якоби-Беллмана 33
1.6 Алгоритм регуляризации принципов оптимальности в игре 1>Ы 38
1.7 Регуляризация С~ядра и вектора Шепли в игре Гу(жд) 39
1.8 Сильно динамически устойчивые принципы оптимальности 44
1,9 Сильная динамическая устойчивость регуляризованных принципов оптимальности 46
1.10 Пример регуляризации вектора Шепли 47
1.11 Кооперативные игры с дисконтированными выигрышами 58
2 Многошаговые кооперативные игры со случайным числом шагов . 65
2.1 Определение многошаговой кооперативной игры GY{ZQ) В форме характеристической функции 65
2.2 Принцип динамической устойчивости в игре Gy{z) . 74
2.3 Введение новой характеристической функции 82
2.4 Регуляризованные динамически устойчивые принципы оптимальности 83
2.5 Регуляризация вектора Шепли и С-ядра в игре GY(ZQ) . 86
2.6 Алгоритм регуляризации вектора Шепли в игре GV{ZQ) 88
2.7 Сильно динамически устойчивые принципы оптимальности 91
2.8 Регуляризованные сильно динамически устойчивые принципы оптимальности 93
2.9 Пример динамически устойчивого решения в'кооперативной многошаговой игре двух лиц 95
2.10 Пример регуляризации вектора Шепли в кооперативно многошаговой игре двух лиц 106
Заключение 113
Список литературы 114
Приложение 121
- Принцип динамической устойчивости в игре Гу(жо)
- Регуляризация С~ядра и вектора Шепли в игре Гу(жд)
- Регуляризованные динамически устойчивые принципы оптимальности
- Регуляризованные сильно динамически устойчивые принципы оптимальности
Введение к работе
Актуальность темы. Одной из основных задач современной теории игр является конструирование и анализ принципов оптимального поведения участников в различных задачах конфликтного управления. Естественным подходом к изучению кооперативных динамическкх игр, как игр дележей, является попытка переноса результатов классической кооперативной теории "однократных"игр Неймана-Моргенштерна [19]. Однако при использовании результатов классической теории необходимо дополнительно исследовать вопрос о динамической и сильно динамической устойчивости полученного решения. Попытки применения динамически неустойчивых принципов оптимальности при решении прикладных задач в области экономики, экологии, менеджмента приводят к нереализуемости таких принципов, поскольку в некоторый момент времени возникают условия, когда соглашение о кооперации могут быть пересмотрено.
Это обстоятельство впервые было замечено Л.А. Петросяном в 1977 году [25]. Позднее введенные им термины динамической и сильно динамической устойчивости в англоязычной литературе трансформировались в "состоятельность во времени"и "сильную состоятельность во времени "соответственно. Исследованиям проблемы динамической устойчивости посвящены работы [9], [23], [24], [29] и др.
В настоящее время одним из наиболее бурно развивающихся разделов теории игр являются кооперативные дифференциальные игры [4], [13], [15], [39]. Также следует отметить перспективное направление, связанное с развитием теории стохастических игр, введенных Шепли в 1953 году [56], а также дифференциальных игр при наличии неопределенности [11], [12] , [14], [33], [49], поскольку использование при моделировании фактора той или иной неопределенности позволяет наиболее адекватно описывать самые разнообразные процессы, происходящие в экономике, экологии, менеджменте, торговле, при принятии решений в области международных отношений, систем безопасности и щ>.
В данной работе вводится новый класс дифференциальных игр — кооперативные дифференциальные игры п лиц со случайной продолжительностью Т — to. Случайность времени существования любого организма, системы, процесса заложена в окружающую человека реальность, поэтому спектр приложений кооперативных дифференциальных игр со случайной продолжительностью может быть велик. Отметим, что в работе Л.А. Петросяна и Н.В. Мурзова "Теоретико-игровые задачи меха-ники"в 1966 г. [30] впервые были исследованы дифференциальные игры преследования двух лиц со случайной продолжительностью. В рассматриваемой авторами задаче продолжительность игры Т являлась случайной величиной с абсолютно непрерывной функцией распределения F(t) и множеством возможных значений в отрезке [0,Tq]. В этой же работе впервые было выведено уравнение типа Айзекса-Беллмана для заданной таким образом игры преследования.
В кооперативных дифференциальных играх супераддитивность характеристической функции не обеспечивает сохранение кооперации меж- ду игроками во время всей игры.Предположим, что перед началом игры игроки договариваются об использовании ими некоторого'принципа оптимальности C(xq) и по окончанию игры рассчитывают получить некоторый соответствующий ему дележ є С(хо). Развитию игры во времени соответствует движение вдоль оптимальной траектории x*(t), на которой по определергаю игроки получают наибольший ожидаемый дележ. Однако движение вдоль оптимальной траектории еще не обеспечивает., сохранение кооперации. Действительно, при движении вдоль x*(t) игроки попадают в подыгры с текущими начальными состояниями, в которых один и тот же игрок имеет различные возможности. Следовательно, в некоторый момент $ может возникнуть ситуация, когда решение текущей игры будет неоптимальным в смысле первоначально выбранного принципа оптимальности C(xq). В таком случае перед игроками встанет вопрос о целесообразности придерживаться далее намеченного перед началом игры соглашения действовать "совместно оптимально". Последнее будет означать динамическую неустойчивость принципа оптимальности C{xq) и, соответственно, самого движения по траектории x*(t). Следовательно, проблема динамической устойчивости является очень важной для кооперативных дифференциальных игр со случайной продолжительностью. Разрешить данную проблему предлагается путем введения специальных выплат (процедуры распределения дележа), которые будут регулировать распределение общего выигрыша во времени так, чтобы ни в какой момент времени і Є [і0, сю) ни у кого из игроков не возникло желание уклониться от первоначального соглашения.
В диссертации также рассматриваются кооперативные многошаговые игры со случайным числом шагов как дискретный аналог кооперативных дифференциальных игр со случайной продолжительностью. Развитию игры соответствует пошаговый переход из одного состояния в другое, под динамической.устойчивостью понимается реализуемость принципа оптимальности на всех шагах игры. Для построения динамически устойчивых принципов оптимальности используется процедура распределения дележа, согласно которой игрокам на каждом шаге выплачивается некоторая сумма, обеспечивающая сохранение кооперации.
Основной целью работы являлось изучение динамической и сильно динамической устойчивости решений кооперативных дифференциальных игр со случайной продолжительностью, а также решений кооперативных многошаговых игр со случайным числом шагов. В диссертации решалась задача построения динамически и сильно динамически устойчивых принципов оптимальности на основе классических решений для указанных классов игр.
Научная новизна работы заключается в том, что в ней: введены новые классы кооперативных динамических игр — кооперативные дифференциальные игры со случайной продолжительностью и кооперативные многошаговые игры со случайным числом шагов, предложены алгоритмы построения новых принципов оптимальности на основе классических решений, которые удовлетворяют свойствам динамической и сильной динамической устойчивости. получено и обосновано уравнение Гамильтона-Якоби-Белл мана для кооперативных дифференциальных игр со случайной продолжительностью.
Практическая ценность. Полученные в диссертации результаты представляют теоретический в: практический интерес. Кооперативные дифференциальные игры со случайной продолжительностью, а также их дискретный вариант - кооперативные многошаговые игры со случайным числом шагов, являются удобными математическими моделями для описания процессов, происходящих б экономике, экологии, менеджменте и прочих сферах человеческой деятельности. Особый интерес представляют алгоритмы построения динамически устойчивых принципов оптимальности для данных классов игр.
Основные положения, выносимые на защиту:
Построена формализация кооперативных дифференциальных игр со случайной продолжительностью. Введены понятия процедуры распределения дележа, динамической и сильно динамической устойчивости принципа оптимальности для данного класса игр.
Получено аналитическое выражение для процедуры распределения дележа при динамической устойчивости принципа оптимальности.
Проведена регуляризация классических принципов оптимальности, приводящая к динамической и сильно динамической устойчивости. Регуляризация задана в форме алгоритма.
Получено уравнение Беллмана-Гамильтона-Якоби для нахождения значения кооперативной дифференциальной игры со случайной продолжительности .
Определены кооперативные многошаговые игры со случайным числом шагов. Введены понятия процедуры распределения дележа, ди- намической и сильно динамической устойчивости принципа оптимальности. Предложен алгоритм регуляризации принципов оптимальности, приводящий к динамической и сильно динамической устойчивости принципов оптимальности для данного класса игр.
Апробация работы. Основные результаты были представлены на семинарах кафедры математической теории игр и статистических решений, на семинарах Центра теории игр, на XXX и XXXI научных конференциях "Процессы управления и устойчивость" (Санкт-Петербург, 1999, 2000 гг.), на 3 международной конференции "Logic, Game Theory and Social Choices" (Италия, University of Sciena, 2003), на семинаре Механико-математического факультета Саратовского государственного университета имени Н.Г. Чернышевского (Саратов, 2004).
По материалам диссертации опубликованы работы [28], [36]; [37], [32], [53], [54], [55].
Структура и объем работы. Диссертация состоит из введения, двух глав, разбитых на параграфы, заключения, списка используемой литературы и приложения,
В первой главе рассматриваются кооперативные дифференциальные игры со случайной продолжительностью. В 1.1 вводится определение кооперативной дифференциальной игры со случайной продолжительностью в форме характеристической функции, В 1.2 определяется понятие процедуры распределения дележа (ПРД), формализуется принцип динамической устойчивости решения кооперативной дифференциальной игры п лиц со случайной продолжительностью. Получено аналитическое выражение для вычисления ПРД в случае динамической устойчивости.
В 1.3 изучаются кооперативные дифференциальные игры с разрывной функцией распределения ее продолжительности,исследуется проблема динамической устойчивости решений для данного класса игр. Получено интегральное выражение для вычисления ПРД.
В 1.4 предлагается конструктивный способ улучшения или регуляризации классических принципов оптимальности, не являющихся динамически устойчивыми в общем случае. Доказывается, что построенные новые принципы оптимальности будут обладать свойством динамической устойчивости. Для регуляризованиой игры определяется новая характеристическая функция,
В 1,5 получено уравнение Гамильтона-Якоби-Беллмана, с помощью которого можно находить значение кооперативной дифференциальной игры со случайной продолжительностью. Результат проверен на примере игры с показательным распределением момента ее окончания в 1.10.
Предложенные в параграфах 1.4, 1.5 методы нахождения оптимальной траектории и построения динамически устойчивого принципа оптимальности при помощи новой ПРД, приводятся в форме алгоритма в параграфе 1.6.
В 1.7 изучается вопрос регуляризации вектора Шепли и С-ядра. Приводятся необходимые условия динамической устойчивости с-ядра, сведения о его видоизменении при регуляризации, а также предлагается другой способ регуляризации вектора Шепли.
В 1.8 формулируется понятие сильной динамической устойчивости принципов оптимальности. В 1.9 доказывается, что регуляризованные принципы оптимальности являются сильно динамически устойчивыми. Результаты, полученные в предыдущих параграфах, демонстрируются на примере в 1.10.
В 1.11 формализуются кооперативные дифференциальные игры со случайной продолжительностью для случая дисконтирования выигрышей игроков. Дается определение динамической устойчивости принципа оптимальности, а также предлагается конструктивный способ построения ДУПО на примере вектора Шепли. В данном параграфе также рассматривается нестандартный способ задания характеристической функции.
Во второй главе рассматривается дискретный вариант кооперативных дифференциальных игр со случайной продолжительностью — кооперативные многошаговые игры со случайным числом шагов. В 2.1 кооперативная многошаговая игра со случайным числом шагов определяется в форме характеристической функции, В 2.2 вводится определение процедуры распределения дележа (ПРД) по шагам, объясняется принцип динамической устойчивости. Получено аналитической выражение для ПРД в случае динамической устойчивости принципа оптимальности.
В 2.3 определяется новая характеристическая функция, которая в дальнейшем будет использоваться как характеристическая функция ре-гуляризованной игры. В 2.4 проводится регуляризация классических принципов оптимальности при помощи новой ПРД, которая приводит к динамической устойчивости решений для данного класса игр. В 2.5 изучается вопрос регуляризации вектора Шепли и С-ядра. В 2.6 приводится алгоритм регуляризации вектора Шепли.
В 2.7 формулируется понятие сильной динамической устойчивости, в 2.8 предлагается способ построения новых принципов оптимальности, обладающих свойством сильно динамической устойчивости. В 2.9 приводится пример динамически устойчивого решения в многошаговой игре двух лиц. Регуляризация вектора Шепли представлена в примере 2.10.
Заключение содержит в себе обзор полученных результатов. В приложении представлен текст программы, использованной при вычислениях в примерах главы II.
В диссертационной работе использована тройная нумерация формул. Первая цифра означает номер главы, вторая - номер параграфа в главе, третья - номер в параграфе. Для теорем, определений, следствий, замечаний используется сквозная нумерация. Параграфы пронумерованы для каждой главы отдельно. Литература приведена в алфавитном порядке.
Принцип динамической устойчивости в игре Гу(жо)
В кооперативных дифференциальных играх для сохранения кооперации между игроками во время всей игры одной супераддитивности характеристической функции V(S,XQ) недостаточно. Предположим, что перед начал0 игры игроки договариваются об использовании ими некоторого принципа оптимальности (ПО) С(ж0). Пусть = {&} Є С(%о), т.е. — некоторый оптимальный в смысле ПО С(жо) дележ. Это означает, что в состоянии XQ игроки выбирают распределение общего дохода таким образом, что после окончания игры доля игрока г, Ї = 1,..., п составляет &. Рассмотрим вектор-функцию 7 00 = {УІ(Ї}}, такую, что Вектор-функцию 7(і?) = {7гО#) не обеспечивает сохранение кооперации. Действительно, при движении вдоль х {t) игроки попадают в подыгры с текущими начальными состояниями, в которых один и тот же игрок имеет различные возможности. Следовательно, в некоторый момент г? может возникнуть ситуация, когда решение текущей игры Ту{х {$)) будет неоптимальным в смысле первоначально выбранного принципа оптимальности C(XQ). В таком случае перед игроками встанет вопрос о целесообразности придерживаться далее намеченного перед началом игры соглашения действовать "совместно оптимально". Последнее будет означать динамическую неустойчивость принципа оптимальности C(XQ) И, соответственно, самого движения по траектории x (t). Определение 2. Пусть С(х ($)) ф, V# є [і0,оо). Принцип оптимальности C(XQ) назовем динамически устойчивым принципом оптимальности (ДУПО), если для любого дележа є С(х$) существует ПРД {уі(т)} 0, т Є [іо, оо); такая, что вектор = {f} (ожидаемый дележ в игре Ту (% ($))), вычисленный по формуле принадлежит тому оке принципу оптимальности, т.е. Є С(х ("&)). Введение такого определения обоснованно тем фактом, что для реализуемости некоторого дележа из принятого игроками принципа оптималь ности в подыгре дележ должен вычисляться "по той же формуле"(а точнее, с той же ПРД) с поправкой на условную 0}, і? Є [ о,оо] будем называть процедурой распределения дележа (ПРД). ПРД определяет правило, согласно которому математическое ожидание дележа во всей игре распределено во времени (to, со).
Доход, полученный игроком на промежутке [to, ] обозначим сиДі?) : Итак, игроки в начальный момент t0 договорились о реализации некоторого принципа оптимальности C(XQ) И рассчитывают получить соответствующий ему дележ . Предположим, что С(х (-&)) ф во всех подыг-рах (в противном случае игроки не имеют возможности следовать этому принципу в течение всей игры). Заметим, что вопрос о непустоте принципа оптимальности вдоль всей оптимальной траектории является нетривиальным. В работах [6], [46], [47] представлены критерии проверки непустоты С-ядра. Развитию игры во времени соответствует движение вдоль оптимальной траектории х (і) , на которой по определению игроки получают наибольший ожидаемый дележ:. Однако движение вдоль оптимальной траектории еще не обеспечивает сохранение кооперации. Действительно, при движении вдоль х {t) игроки попадают в подыгры с текущими начальными состояниями, в которых один и тот же игрок имеет различные возможности. Следовательно, в некоторый момент г? может возникнуть ситуация, когда решение текущей игры Ту{х {$)) будет неоптимальным в смысле первоначально выбранного принципа оптимальности C(XQ). В таком случае перед игроками встанет вопрос о целесообразности придерживаться далее намеченного перед началом игры соглашения действовать "совместно оптимально". Последнее будет означать динамическую неустойчивость принципа оптимальности C(XQ) И, соответственно, самого движения по траектории x (t). Определение 2. Пусть С(х ($)) ф, V# є [і0,оо). Принцип оптимальности C(XQ) назовем динамически устойчивым принципом оптимальности (ДУПО), если для любого дележа є С(х$) существует ПРД {уі(т)} 0, т Є [іо, оо); такая, что вектор = {f} (ожидаемый дележ в игре Ту (% ($))), вычисленный по формуле принадлежит тому оке принципу оптимальности, т.е. Є С(х ("&)). Введение такого определения обоснованно тем фактом, что для реализуемости некоторого дележа из принятого игроками принципа оптималь ности в подыгре дележ должен вычисляться "по той же формуле"(а точнее, с той же ПРД) с поправкой на условную функцию распределения ify(i) в подыгре ГУ(ж ($)): Учитывая определение (ДУ) (1.2.3) и обозначение (1.2.2), путем несложных преобразований получим необходимый и достаточный вид любого дележа Є C(XQ) при динамической устойчивости C(XQ) : Последнее слагаемое представляет собой математическое ожидание выигрыша игрока в игре Гу(ж (і?)) при условии, что игра не закончилась до момента $. Здесь мы под выигрышем в подыгре Ту(х (&)) подразумеваем ожидаемый выигрыш Щ и уже накопленную к моменту & сумму It li{T) T- Таким образом, в подыгре Гу(ж (#)) мы учитываем "прошлое "до момента Ф. Содержательно определение (ДУПО) означает следующее. Представим себе, что реализация дележа происходит следующим образом. На отрезке времени [о $] игроки по предварительной договоренности получают ОЧ(Ї?), а если игра продолжится после момента $, то к этому
Регуляризация С~ядра и вектора Шепли в игре Гу(жд)
Если изначально выбранный игроками принцип оптимальности С(ж0) имеет частный вид — С-ядро, проверка свойства динамической устойчивости данного ПО может быть осуществлена согласно следующей теореме. Теорема 2. Пусть С(хо) — С-ядро. Необходимыми условиями динамической устойчивости С-ядра C(XQ) являются 1) непустота С-ядра вдоль всей оптимальной траектории x (t): 7(ж (#)) Ф%, V$ Є [to,oo); 2) существование такой ПРД 7(г); Т Є [ 0J ) для любого дележа Є C(XQ), что в любой момент времени & Є [to, со) выполняются следующие ограничения: Доказательство. Докажем первое неравенство (второе доказывается аналогично). Очевидно, что если C(XQ) является динамически устойчивым принципом оптимальности, то для любого дележа из него Е C(XQ) уравнение (1.2.7) имеет место. Кроме того, вектор , вычисленный по формуле (1.2.3) должен принадлежать С(ж (#)) в подыгре Гу(ж (#)), Добавляя к обеим частям неравенства (1.7.3) значение 6и получаем Таким образом мы доказали верхнее ограничение. Нижнее ограничение доказывается аналогично. П Замечание 1. При S = N неравенства (1.7.1) вырождаются в равенство: Доказательство. Поскольку имеет место уравнение Беллмана (1.1.10), при динамической устойчивости С-ядра получаем следующее условие на ПРД 7(т), т Є [t0, об) при S = N: Следующая теорема дает представление о видоизменении С-ядра при регуляризации. Теорема 3. Пусть изначально выбранный игроками принцип оптимальности C(XQ) является С-ядром, которое не является динамически устойчивым. Рассмотрим У(5, жо) и {x S) — новую характеристическую функцию и соответствующее ей С-лдро. Согласно формуле (1.4-5) определим регуляризованный принцип оптимальности С(хо) на основе С-ядра C(XQ). Справедливо следующее включение: т.е. построенная регуляризация С-ядра С(х$) будет принадлежать С-ядру, соответствующему характеристической функции V(S,XQ). Доказательство, Для доказательства данного утверждения воспользуемся необходимым и достаточным условием принадлежности дележа С-ядру: В нашем случае V& Є С(жо) имеем Т.к. С(жо) является С-ядром, должно выполняться неравенство п Следовательно, получаем, что Следовательно, компоненты вектора Шепли в игре Гу-(жо) (кооператив-ном варианте игры Г(а?о) с новой характеристической функцией V(5, XQ)) имеют вид; Назовем Sh[xo) регуляризованным вектором Шепли. Из формул (1.4.1) и (1.7.5) получаем выражение для компонент регуляризованного вектора Шепли: Как нетрудно показать, компоненты вектора Шепли 3h(x (r)) в подыгре Гу(х (т)) вычисляются по формуле: Таким образом, вектор
Шепли Shi(xo): вычисленный для характеристи ческой функции V(S,XQ), является динамически устойчивым. Итак, регуляризованный вектор Шепли может быть построен как согласно приведенному ранее алгоритму (т.е. используя непосредственно Shi(xo)), так и вычислен для новой характеристической функции V{S,xo). Аналог Теоремы 4 справедлив и для всех принципов оптимальности, основанных на вычислении математического ожидания вклада игрока в коалицию, т.е. величины \V(S, XQ) — V(S\ {г}, XQ)]. Согласно предложенному определению динамической устойчивости принципа оптимальности C(XQ), для любого дележа из него существует такая ПРД 7( ) Є [ о )J что имеет место представление данного дележа в виде (1.2,3); где й - некоторый дележ из С(х (,д)). С точки зрения приложений, более предпочтительными были бы те принципы оптимальности, которые обладают следующим свойством: если в формуле (1.2.3) в качестве можно было бы использовать любой дележ из текущего решения (7(ж (і?)) и дележ, составленный таким образом, все равно принадлежал бы изначально выбранному ПО С(жо), то такой принцип оптимальности был бы еще удобнее для реализации, чем динамически устойчивый ПО. Дадим формальное определение сильно динамической устойчивости принципа оптимальности. Определение 4. Принцип оптимальности 0{SCQ) (или решение игры Ту(хо)) назовем сильно динамически устойчивым принципом оптимальности (СДУПО); если для любого делеоюа Є C(XQ) существует ПРД {7і(т) 0}5 Т Є [to, со)3 такая, что вектор , , определенный по следующей формуле принадлежит C(XQ) для любого селектора & є (7(ж (#)). Используя обозначение ф : [а Ф В (а + Ь, Ъ Є В)}, имеем эквивалентное определение: Таким образом, свойство сильной динамической устойчивости является усилением свойства, динамической устойчивости. Определение СДУ-ПО означает, что если дележ Є C(XQ) И ПРД { {(г)} выбраны, то после получения игроками на отрезке [to ,Щ величины rt (при условии, что игра продолжилась после момента $), математическое ожидание любого оптимального в смысле ПО 0(ж ($)) выигрыша на полуинтервале [#, со) вместе с уже полученным доходом образует дележ, принадлежащий ПО C(XQ) В первоначальной игре TV{XQ). Итак, сильная динамическая устойчивость означает, что любое продолжение выплат после момента і? (если игра не закончилась) соответственно с любым вектором Є С(х ( &)) также приведет к некоторым выплатам в игре Гу(жо), удовлетворяющим изначально выбранному принципу оптимальности C{XQ), Другими словами, при движении вдоль оптимальной траектории не будут появляться решения текущих подыгр, которые могут вывести общее решение из выбранного перед началом игры Гу(жо) принципа оптимальности G{XQ). Одним из недостатков данной концепции является отсутствие способа проверки, является ли динамически устойчивый ПО сильно динамически устойчивым. Поскольку выражение (1.8.1) должно выполняться для любой подыгры Ту (ж (г?)) и любого селектора й Є С (х { &)), не удается выписать аналог аналитического уравнения (1.4.2). Однако в случае, когда ПО не является динамически устойчивым, можно сразу использовать указанную ниже регуляризацию,., приводящую к сильно динамической устойчивости. В том случае, когда принцип оптимальности C(XQ) состоит из единственного дележа (например, вектор Шепли), определения динамической и сильно динамической устойчивости эквивалентны. Построим СДУПО на основе некоторого ПО C(XQ). Пусть Сіх )) ф для всех подыгр вдоль оптимальной траектории x (t). Определим для некоторого селектора Є C(x (t)),t Є [to, oo] вектор i по формуле:
Регуляризованные динамически устойчивые принципы оптимальности
Принцип оптимальности не обязательно является динамически устойчивым, поскольку в (2.2.17) нельзя гарантировать существование (ПРД) 0i 0. Перейдем к построению улучшенного (регуляризованного) принципа оптимальности C(ZQ) на основе некоторого классического принципа оптимальности C(ZQ) , который будет обладать свойством динамической устойчивости. Предположим, что C(zk) ф во всех подыграх G(zk). Определим для { } Є C(zk),i = 1,..., п, к 0,1,2,..., / вектор { } по формуле: Нетрудно заметить, что (} является распределением общего выигрыша V(N,ZQ) в игре Gy{z). Действительно, Утверждение 2. Для &; построенного по формуле (2.4-1), выполняется свойство индивидуальной рациональности: & У"({г},#о) Доказательство. Согласно Лемме 1 (см. 1.4), характеристическая функция регуляризованной игры имеет вид (2.3.1). Отметим, что поскольку fc является дележом в подыгре Gv(zk), то ? V({i},zT). Следовательно, Таким образом, вектор { }, построенный по формуле 2.4.1), является дележом в игре Gy(zo), где С?у(о) - некоторое расширение игры Gv{3o)- Напомним, что для игры на бесконечном древовидном графе ( суммирование производится до бесконечности и, соответственно, вектор вводится по формуле Дальнейшие рассуждения полностью совпадают со случаем игры на конечном графе, если подразумевать / — оо. Определим Фактически, мы вводим новую (ПРД) /3 = {/З } 1 , /3 0, обеспечивающую динамическую устойчивость: На последнем шаге Ї, в случае игры па конечном графе G, выплаты игрокам назначаются прежние: Для того, чтобы показать это, рассмотрим подыгры G(zs) и определим Очевидно, что X)f=if = "W s)- Кроме того, мы имеем: Теорема 6. Множество C(ZQ) представляет собой динамически устойчивый принцип оптимальности (ДУЛО) в регуляризовапной игре Gy(zo). Заметим, что введенная по формуле (2.4.4) ПРД обладает важным свойством осуществимости таких выплат — суммарные выплаты игрокам на каждом шаге к в точности равны заработанной ими сумме: Таким образом, при использовании выплат игрокам на каждом шаге по формуле (2.4.4), мы обеспечиваем динамическую устойчивость принципа оптимальности C(zo) и при этом не требуются дополнительные инвестиции. Предположим, что в качестве принципа оптимальности () игроки выбрали вектор Шепли (1.7.4). В том случае, когда компоненты вектора Шепли не могут быть представлены в виде (2.2.7) при помощи неотрицательных выплат на каждом шаге к (т.е. ПРД {fif}), требуется провести улучшение или регуляризацию вектора Шепли. Говоря другими словами, необходимо построить некоторый другой принцип оптимальности — регуляризованный вектор Шепли (РВШ), применяя который игроки не имели бы оснований для отклонений от оптимальной траектории в течение всей игры. Справедлива следующая теорема. Теорема 7. Вектор Шепли, вычисленный для характеристической функции V(S, fft), S С N (2.3.1), всегда динамически устойчив в игре Gy{zo).
Доказательство. Доказательство данной теоремы аналогично доказательству теоремы 4 главы I. Поскольку вектор Шепли вычисляется по формуле (1.7,4), то компоненты вектора Шепли в игре GV(ZQ) с характеристической функцией V(S,ZQ) имеют вид: ляризованного вектора Шепли Shi(zo): Таким образом, РВШ имеет вид (2.4.1),, который, согласно доказанной теореме 1 главы II, означает динамическую устойчивость регуляризован ного вектора Шепли {Shi(zo}. Таким образом, вектор Шепли 8hi{zo), вычисленный для характеристической функции V(S7 ZQ), является дина мически устойчивым. Согласно доказанной теореме, регуляризованный вектор Шепли может быть построен как при помощи непосредственных вычислений нового вида ПРД (2.4.4), так и вычислен для новой характеристической функции V(S,ZQ) (2.3.1). Если игроки выбрали С-ядро в качестве принципа оптимальности, в соответствии с которым, они собираются разделить ожидаемый выигрыш V(N,zo), справедлива следующая теорема. Теорема 8. Пусть C(ZQ) — С-ядро игры Gy(zo), построенное для характеристической функции V(S,ZQ). Если изначально выбранный принцип оптимальности С {ZQ) является С-ядром (что означает, " ?Х/гє5 — 1/(5, VS), то построенный на его основе принцип оптимальности C(ZQ) будет принадлежать G(zo): Доказательство. Доказательство аналогично приведенному в I главе. Дележ принадлежит С-ядру C{ZQ) тогда и только тогда, когда выполнено следующее условие : Поскольку характеристическая функция V(S,ZQ) вычисляется по формуле (2.3.1)), получаем, что Рассмотрим игру на конечном графе G длины L Предположим, игроками был выбран вектор Шепли в качестве решения игры. На основании представленной выше теории, приведем алгоритм регуляризации вектора Шепли. Алгоритм может быть использован для регуляризации любого классического ПО с соответствующими изменениями при вычислениях дележей. Этап 0. Вычисление вектора Шепли {Shi} в игРе Gy(zo). (1) Находим оптимальную траекторию z как последовательность вершин ZQ, Z\} ..., i, которая соответствует набору стратегий й = ({ }, {Щ1},..., {й })( максимизирующему совокупный ожидаемый выигрыш (2.1.4). В дальнейшем для уменьшения громоздкости будем обозначать выбранную стратегию на шаге к (в вершине Zk) как и\. (2) Вычисляем значение игры V(N, zG) по формуле (2.1.7). (3) Для вычисления V(S,ZQ) рассматриваются вспомогательные антагонистические игры на основе игры G(ZQ), где S — первый, т.е. максимизирующий игрок (применяет стратегию ii " ,2!)a N\S — минимизирующий игрок (стратегия uz V s,Zt), Соответственно, значения V(S, ZQ) для всевозможных S С N находятся по формулам (2.1.5). (4) Находим компоненты вектора Шепли по формуле (1.7.4) в игре GV(ZQ). В общем случае дележ является некоторым распределением значения V{N,z0). Этап 1. Вычисление компонент вектора Шепли {Shfji = 1,..., п во всех подыграх Gy(zfc), к = 1}2,.. .,1. (1) Рассмотрим семейство подыгр, в которое могут попасть игроки при сдвиге на 1 шаг по оптимальной траектории z, т.е. подыгру Gy(z{), начинающуюся из вершины %\. Тогда, поскольку для выражения
Регуляризованные сильно динамически устойчивые принципы оптимальности
Построим СДУПО C(ZQ) на основе некоторого (ПО) C(zo). Пусть C(zk) ф 0 для всех подыгр вдоль оптимальной траектории z. Определим для селектора {$} С( ), і — 1,..., п, к — 1,..., I вектор по формуле: Нетрудно заметить, что {&} — дележ в игре Gy (ZQ) (см. построение (ДУ-ПО)). Зафиксируем s и введем /3 = { } 1 : Заметим, что все компоненты j3 = {Д } 1 ;;; - неотрицательные числа. Предположим, что принципу оптимальности C(ZQ) соответствует не единственный дележ {f} Є 0(), поскольку тогда определение динамической и сильно динамической устойчивости являются эквивалентными. Выбе-рем другой произвольный дележ {f} С(2ь), k = s,... ,1 та. определим дележ в кдинамически устойчивым принципом оптимальности. Доказательство Теоремы 2 аналогично доказательству Теоремы 2 главы I. Сильно динамически устойчивая регуляризация игры на бесконечном древовидном графе Gi проводится аналогично. Рассмотрим кооперативную многошаговую игру G(ZQ) двух лиц, заданную на следующем графе G; Игра происходит следующим образом: на нулевом шаге игроки участвуют в одновременной игре Г (го), заданной биматрицей После этого игра G(ZQ) либо заканчивается с вероятностью ро = 0.25, либо переходит в следующую из возможных четырех вершину z\} причем этот переход зависит от реализовывается ситуации в вершине ZQ. Если в игре T(ZQ) реализуется ситуации (1,1), то из вершины ZQ игра переходит в вершину z\ = #ід, если реализуется ситуация (1,2), то из вершины ZQ игра переходит в вершину z\ = zifi] ситуации (2,1) соответствует переход в вершину z\ — z\$\ ситуации (2,2) соответствует переход В Z\ = zit±. В вершине z\ игроки играют в игру Г( і) двух лиц, которая, в зависимости от реализованной на предыдущем шаге ситуации, задается одной из следующих биматриц: На этом шаге игра может закончиться с вероятностью р\ =0.5 или перейти в следующую вершину 2. Правила перехода в вершину z i (одну из четырех возможных из позиции z{) такие же: в случае реализации ситуации (1,1) игра переходит в последнюю вершину Z2 І в которой осуществляется игра Т{%%) с матрицей Н\\ ситуации (1,2) соответствует переход в такую вершину z% , в которой осуществляется игра Г( з) с матрицей В.2\ ситуации (2,1) соответствует переход в z% , в которой осуществляется игра Г( г) с матрицей #з; выбору ситуации (2,2) соответствует переход в вершину, в которой разыгрывается игра с матрицей Н . Вероятность окончания игры на втором шаге равна р2 = 0.25. Для начала решим одновременные игры Гц., ..., Г4. Тогда в подыграх, начинающихся на последнем шаге, будут следующие 4 вида значений характеристических функцийаждой подыгре по формуле: Рассмотрим Теорема 9. Множество C(ZQ) является сильно динамически устойчивым принципом оптимальности. Доказательство Теоремы 2 аналогично доказательству
Теоремы 2 главы I. Сильно динамически устойчивая регуляризация игры на бесконечном древовидном графе Gi проводится аналогично. Рассмотрим кооперативную многошаговую игру G(ZQ) двух лиц, заданную на следующем графе G; Игра происходит следующим образом: на нулевом шаге игроки участвуют в одновременной игре Г (го), заданной биматрицей После этого игра G(ZQ) либо заканчивается с вероятностью ро = 0.25, либо переходит в следующую из возможных четырех вершину z\} причем этот переход зависит от реализовывается ситуации в вершине ZQ. Если в игре T(ZQ) реализуется ситуации (1,1), то из вершины ZQ игра переходит в вершину z\ = #ід, если реализуется ситуация (1,2), то из вершины ZQ игра переходит в вершину z\ = zifi] ситуации (2,1) соответствует переход в вершину z\ — z\$\ ситуации (2,2) соответствует переход В Z\ = zit±. В вершине z\ игроки играют в игру Г( і) двух лиц, которая, в зависимости от реализованной на предыдущем шаге ситуации, задается одной из следующих биматриц: На этом шаге игра может закончиться с вероятностью р\ =0.5 или перейти в следующую вершину 2. Правила перехода в вершину z i (одну из четырех возможных из позиции z{) такие же: в случае реализации ситуации (1,1) игра переходит в последнюю вершину Z2 І в которой осуществляется игра Т{%%) с матрицей Н\\ ситуации (1,2) соответствует переход в такую вершину z% , в которой осуществляется игра Г( з) с матрицей В.2\ ситуации (2,1) соответствует переход в z% , в которой осуществляется игра Г( г) с матрицей #з; выбору ситуации (2,2) соответствует переход в вершину, в которой разыгрывается игра с матрицей Н . Вероятность окончания игры на втором шаге равна р2 = 0.25. Для начала решим одновременные игры Гц., ..., Г4. Тогда в подыграх, начинающихся на последнем шаге, будут следующие 4 вида значений характеристических функций:
